{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/50588"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/50588","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Scalable parallel tridiagonal algorithms with diagonal pivoting and their optimization for many-core architectures","abstract":"Tridiagonal solvers are important building blocks for a wide range of scientific applications that are commonly performance-sensitive. Recently, many-core architectures, such as GPUs, have become ubiquitous targets for these applications. Therefore, a high-performance general-purpose GPU tridiagonal solver becomes critical. However, no existing GPU tridiagonal solver provides comparable quality of solutions to most common, general-purpose CPU tridiagonal solvers, like Matlab or Intel MKL, due to no pivoting. Meanwhile, conventional pivoting algorithms are sequential and not applicable to GPUs. In this thesis, we propose three scalable tridiagonal algorithms with diagonal pivoting for better quality of solutions than the state-of-the-art GPU tridiagonal solvers. A SPIKE-Diagonal Pivoting algorithm efficiently partitions the workloads of a tridiagonal solver and provides pivoting in each partition. A Parallel Diagonal Pivoting algorithm transforms the conventional diagonal pivoting algorithm into a parallelizable form which can be solved by high-performance parallel linear recurrence solvers. An Adaptive R-Cyclic Reduction algorithm introduces pivoting into the conventional R-Cyclic Reduction family, which commonly suffers limited quality of solutions due to no applicable pivoting. Our proposed algorithms can provide comparable quality of solutions to CPU tridiagonal solvers, like Matlab or Intel MKL, without compromising the high throughput GPUs provide.","abstract_html":"Tridiagonal solvers are important building blocks for a wide range of scientific applications that are commonly performance-sensitive. Recently, many-core architectures, such as GPUs, have become ubiquitous targets for these applications. Therefore, a high-performance general-purpose GPU tridiagonal solver becomes critical. However, no existing GPU tridiagonal solver provides comparable quality of solutions to most common, general-purpose CPU tridiagonal solvers, like Matlab or Intel MKL, due to no pivoting. Meanwhile, conventional pivoting algorithms are sequential and not applicable to GPUs. In this thesis, we propose three scalable tridiagonal algorithms with diagonal pivoting for better quality of solutions than the state-of-the-art GPU tridiagonal solvers. A SPIKE-Diagonal Pivoting algorithm efficiently partitions the workloads of a tridiagonal solver and provides pivoting in each partition. A Parallel Diagonal Pivoting algorithm transforms the conventional diagonal pivoting algorithm into a parallelizable form which can be solved by high-performance parallel linear recurrence solvers. An Adaptive R-Cyclic Reduction algorithm introduces pivoting into the conventional R-Cyclic Reduction family, which commonly suffers limited quality of solutions due to no applicable pivoting. Our proposed algorithms can provide comparable quality of solutions to CPU tridiagonal solvers, like Matlab or Intel MKL, without compromising the high throughput GPUs provide.","abstract_has_math":false,"creators":["Chang, Li-Wen"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"M.S.","degree_level":"Thesis","degree_discipline":"Electrical & Computer Engr","degree_department":null,"school":null,"contributors":["Hwu, Wen-Mei W."],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2014,"date_issued":"2014-09-16T17:24:10Z","date_published":"2014-09-16T17:24:10Z","updated_at":"2026-07-22T22:25:40Z","subjects":["Tridiagonal Solver","SPIKE algorithm","Linear Recurrence","Cyclic Reduction","Diagonal Pivoting","Graphics Processing Unit (GPU) Computing","General Purpose computation on Graphics Processing Units (GPGPU)","Many-core"],"languages":["en"],"rights":["Copyright 2014 Li-Wen Chang"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/2142/50588","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Hwu, Wen-Mei W."]},{"key":"dc:creator","label":"Author","values":["Chang, Li-Wen"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2014-09-16T17:24:10Z","2014-08","2014-09-16"]},{"key":"dc:type","label":"Dc Type","values":["text"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Electrical & Computer Engr"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Thesis"]},{"key":"thesis:degree_name","label":"Degree Name","values":["M.S."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois at Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Tridiagonal Solver","SPIKE algorithm","Linear Recurrence","Cyclic Reduction","Diagonal Pivoting","Graphics Processing Unit (GPU) Computing","General Purpose computation on Graphics Processing Units (GPGPU)","Many-core"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2014 Li-Wen Chang"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/50588"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Tridiagonal solvers are important building blocks for a wide range of scientific applications that are commonly performance-sensitive. Recently, many-core architectures, such as GPUs, have become ubiquitous targets for these applications. Therefore, a high-performance general-purpose GPU tridiagonal solver becomes critical. However, no existing GPU tridiagonal solver provides comparable quality of solutions to most common, general-purpose CPU tridiagonal solvers, like Matlab or Intel MKL, due to no pivoting. Meanwhile, conventional pivoting algorithms are sequential and not applicable to GPUs. In this thesis, we propose three scalable tridiagonal algorithms with diagonal pivoting for better quality of solutions than the state-of-the-art GPU tridiagonal solvers. A SPIKE-Diagonal Pivoting algorithm efficiently partitions the workloads of a tridiagonal solver and provides pivoting in each partition. A Parallel Diagonal Pivoting algorithm transforms the conventional diagonal pivoting algorithm into a parallelizable form which can be solved by high-performance parallel linear recurrence solvers. An Adaptive R-Cyclic Reduction algorithm introduces pivoting into the conventional R-Cyclic Reduction family, which commonly suffers limited quality of solutions due to no applicable pivoting. Our proposed algorithms can provide comparable quality of solutions to CPU tridiagonal solvers, like Matlab or Intel MKL, without compromising the high throughput GPUs provide.","Item withdrawn by Mark Zulauf (zulauf@illinois.edu) on 2014-07-16T19:23:38Z Item was in collections: University of Illinois Theses & Dissertations (ID: 1) No. of bitstreams: 7 Chang_Li-Wen.pdf: 585161 bytes, checksum: fa4904bdd341ba8fc97c1e372c8faa8a (MD5) Chang_Li-Wen.pdf: 585141 bytes, checksum: 88171c1746f89754009e1d0e13aa2253 (MD5) Chang_Li-Wen.pdf: 585497 bytes, checksum: 123eddacf2de5f0e14c054ff17a75116 (MD5) Chang_Li-Wen.pdf: 585384 bytes, checksum: bde40c354a3959a10f30344b8d6aea91 (MD5) Chang_Li-Wen.pdf: 585384 bytes, checksum: bde40c354a3959a10f30344b8d6aea91 (MD5) Chang_Li-Wen.pdf: 585584 bytes, checksum: 1596d5417b746a5e6af19e68fbb16ea5 (MD5) Chang_Li-Wen.pdf: 585144 bytes, checksum: 54f7ab7b6bf6d22f1a3bc6be0c915067 (MD5)","Made available in DSpace on 2014-09-16T17:24:10Z (GMT). No. of bitstreams: 2 Li-Wen_Chang.pdf: 585144 bytes, checksum: 54f7ab7b6bf6d22f1a3bc6be0c915067 (MD5) license.txt: 4062 bytes, checksum: a7169c6407c7a9dd8bfcef1001700755 (MD5)"]},{"key":"dc:title","label":"Title","values":["Scalable parallel tridiagonal algorithms with diagonal pivoting and their optimization for many-core architectures"]}]}],"canonical_facts":{"dc:contributor":["Hwu, Wen-Mei W."],"dc:creator":["Chang, Li-Wen"],"dc:date":["2014-09-16T17:24:10Z","2014-08","2014-09-16"],"dc:description":["Tridiagonal solvers are important building blocks for a wide range of scientific applications that are commonly performance-sensitive. Recently, many-core architectures, such as GPUs, have become ubiquitous targets for these applications. Therefore, a high-performance general-purpose GPU tridiagonal solver becomes critical. However, no existing GPU tridiagonal solver provides comparable quality of solutions to most common, general-purpose CPU tridiagonal solvers, like Matlab or Intel MKL, due to no pivoting. Meanwhile, conventional pivoting algorithms are sequential and not applicable to GPUs. In this thesis, we propose three scalable tridiagonal algorithms with diagonal pivoting for better quality of solutions than the state-of-the-art GPU tridiagonal solvers. A SPIKE-Diagonal Pivoting algorithm efficiently partitions the workloads of a tridiagonal solver and provides pivoting in each partition. A Parallel Diagonal Pivoting algorithm transforms the conventional diagonal pivoting algorithm into a parallelizable form which can be solved by high-performance parallel linear recurrence solvers. An Adaptive R-Cyclic Reduction algorithm introduces pivoting into the conventional R-Cyclic Reduction family, which commonly suffers limited quality of solutions due to no applicable pivoting. Our proposed algorithms can provide comparable quality of solutions to CPU tridiagonal solvers, like Matlab or Intel MKL, without compromising the high throughput GPUs provide.","Item withdrawn by Mark Zulauf (zulauf@illinois.edu) on 2014-07-16T19:23:38Z Item was in collections: University of Illinois Theses & Dissertations (ID: 1) No. of bitstreams: 7 Chang_Li-Wen.pdf: 585161 bytes, checksum: fa4904bdd341ba8fc97c1e372c8faa8a (MD5) Chang_Li-Wen.pdf: 585141 bytes, checksum: 88171c1746f89754009e1d0e13aa2253 (MD5) Chang_Li-Wen.pdf: 585497 bytes, checksum: 123eddacf2de5f0e14c054ff17a75116 (MD5) Chang_Li-Wen.pdf: 585384 bytes, checksum: bde40c354a3959a10f30344b8d6aea91 (MD5) Chang_Li-Wen.pdf: 585384 bytes, checksum: bde40c354a3959a10f30344b8d6aea91 (MD5) Chang_Li-Wen.pdf: 585584 bytes, checksum: 1596d5417b746a5e6af19e68fbb16ea5 (MD5) Chang_Li-Wen.pdf: 585144 bytes, checksum: 54f7ab7b6bf6d22f1a3bc6be0c915067 (MD5)","Made available in DSpace on 2014-09-16T17:24:10Z (GMT). No. of bitstreams: 2 Li-Wen_Chang.pdf: 585144 bytes, checksum: 54f7ab7b6bf6d22f1a3bc6be0c915067 (MD5) license.txt: 4062 bytes, checksum: a7169c6407c7a9dd8bfcef1001700755 (MD5)"],"dc:identifier":["http://hdl.handle.net/2142/50588"],"dc:language":["en"],"dc:rights":["Copyright 2014 Li-Wen Chang"],"dc:subject":["Tridiagonal Solver","SPIKE algorithm","Linear Recurrence","Cyclic Reduction","Diagonal Pivoting","Graphics Processing Unit (GPU) Computing","General Purpose computation on Graphics Processing Units (GPGPU)","Many-core"],"dc:title":["Scalable parallel tridiagonal algorithms with diagonal pivoting and their optimization for many-core architectures"],"dc:type":["text"],"thesis:degree_discipline":["Electrical & Computer Engr"],"thesis:degree_level":["Thesis"],"thesis:degree_name":["M.S."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:25:40Z"}