{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/45394"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/45394","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Automatic algorithm derivation and exploration in linear algebra for parallelism and locality","abstract":"\"Parallelization is one of the major challenges for programmers. But parallelizing existing code is a hard task that can lead to less than optimal solutions since sequential programs can su er from impediments to parallelization resulting from the semantic of the languages or the data structures used rather than the nature of the problem being solved. To avoid such artifacts, programmers can analyze the algorithms to decide which dependencies are \"\"real\"\" and which can be ignored. But even then, conventional algorithms were developed with speci c objectives in mind, such as reducing the total number of operations, which while good to achieve sequential performance, may not be the primary objective when considering parallel machines. We propose to focus on a speci c domain and attack the parallelizing issue at the source, starting from a high level description of the equations without any knowledge of existing algorithms to solve the problem and automatically derive parallel solutions. Hydra accepts an equation written in terms of operations on matrices and automatically produces highly e cient code to solve these equations. Processing of the equation starts by tiling the matrices. This transforms the equation into either a single new equation containing terms involving tiles or into multiple equations some of which can be solved in parallel with each other. Hydra continues transforming the equations using tiling and seeking terms that Hydra knows how to compute or equations it knows how to solve. The end result is that by transforming the equations Hydra can produce multiple solvers with di erent locality behavior and/or di erent parallel execution pro les. Next, Hydra applies empirical search over this space of possible solvers to identify the most e cient version. In this way, Hydra enables the automatic production of e cient solvers requiring very little or no coding at all and delivering performance approximating that of the highly tuned library routines such as Intels MKL. With faster development time for modern architecture, the time available for hand-tuning of high performance libraries diminishes. Intel already started o ering auto-tuned library routines (From Spiral) in their IPP library, to broaden the scope of application of the collection, without having to increase the man hours required to hand-tune everything.\"","abstract_html":""Parallelization is one of the major challenges for programmers. But parallelizing existing code is a hard task that can lead to less than optimal solutions since sequential programs can su er from impediments to parallelization resulting from the semantic of the languages or the data structures used rather than the nature of the problem being solved. To avoid such artifacts, programmers can analyze the algorithms to decide which dependencies are ""real"" and which can be ignored. But even then, conventional algorithms were developed with speci c objectives in mind, such as reducing the total number of operations, which while good to achieve sequential performance, may not be the primary objective when considering parallel machines. We propose to focus on a speci c domain and attack the parallelizing issue at the source, starting from a high level description of the equations without any knowledge of existing algorithms to solve the problem and automatically derive parallel solutions. Hydra accepts an equation written in terms of operations on matrices and automatically produces highly e cient code to solve these equations. Processing of the equation starts by tiling the matrices. This transforms the equation into either a single new equation containing terms involving tiles or into multiple equations some of which can be solved in parallel with each other. Hydra continues transforming the equations using tiling and seeking terms that Hydra knows how to compute or equations it knows how to solve. The end result is that by transforming the equations Hydra can produce multiple solvers with di erent locality behavior and/or di erent parallel execution pro les. Next, Hydra applies empirical search over this space of possible solvers to identify the most e cient version. In this way, Hydra enables the automatic production of e cient solvers requiring very little or no coding at all and delivering performance approximating that of the highly tuned library routines such as Intels MKL. With faster development time for modern architecture, the time available for hand-tuning of high performance libraries diminishes. Intel already started o ering auto-tuned library routines (From Spiral) in their IPP library, to broaden the scope of application of the collection, without having to increase the man hours required to hand-tune everything."","abstract_has_math":false,"creators":["Duchateau, Alexandre"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Computer Science","degree_department":null,"school":null,"contributors":["Padua, David A.","Barthou, Denis","Kale, Laxmikant V.","Heath, Michael T.","Garzaran, Maria J."],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2013,"date_issued":"2013-08-22T16:38:53Z","date_published":"2013-08-22T16:38:53Z","updated_at":"2026-07-22T22:25:34Z","subjects":["Autotuning","Linear Algebra","Parallelism","Multicore","Tiling"],"languages":["en"],"rights":["Copyright 2013 Alexandre Xavier Duchateau"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/2142/45394","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Padua, David A.","Barthou, Denis","Kale, Laxmikant V.","Heath, Michael T.","Garzaran, Maria J."]},{"key":"dc:creator","label":"Author","values":["Duchateau, Alexandre"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2013-08-22T16:38:53Z","2013-08"]},{"key":"dc:type","label":"Dc Type","values":["text"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Computer Science"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Dissertation"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Ph.D."]},{"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":["Autotuning","Linear Algebra","Parallelism","Multicore","Tiling"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2013 Alexandre Xavier Duchateau"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/45394"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["\"Parallelization is one of the major challenges for programmers. But parallelizing existing code is a hard task that can lead to less than optimal solutions since sequential programs can su er from impediments to parallelization resulting from the semantic of the languages or the data structures used rather than the nature of the problem being solved. To avoid such artifacts, programmers can analyze the algorithms to decide which dependencies are \"\"real\"\" and which can be ignored. But even then, conventional algorithms were developed with speci c objectives in mind, such as reducing the total number of operations, which while good to achieve sequential performance, may not be the primary objective when considering parallel machines. We propose to focus on a speci c domain and attack the parallelizing issue at the source, starting from a high level description of the equations without any knowledge of existing algorithms to solve the problem and automatically derive parallel solutions. Hydra accepts an equation written in terms of operations on matrices and automatically produces highly e cient code to solve these equations. Processing of the equation starts by tiling the matrices. This transforms the equation into either a single new equation containing terms involving tiles or into multiple equations some of which can be solved in parallel with each other. Hydra continues transforming the equations using tiling and seeking terms that Hydra knows how to compute or equations it knows how to solve. The end result is that by transforming the equations Hydra can produce multiple solvers with di erent locality behavior and/or di erent parallel execution pro les. Next, Hydra applies empirical search over this space of possible solvers to identify the most e cient version. In this way, Hydra enables the automatic production of e cient solvers requiring very little or no coding at all and delivering performance approximating that of the highly tuned library routines such as Intels MKL. With faster development time for modern architecture, the time available for hand-tuning of high performance libraries diminishes. Intel already started o ering auto-tuned library routines (From Spiral) in their IPP library, to broaden the scope of application of the collection, without having to increase the man hours required to hand-tune everything.\"","Item withdrawn by Mark Zulauf (zulauf@illinois.edu) on 2013-07-01T14:39:43Z Item was in collections: University of Illinois Theses & Dissertations (ID: 1) No. of bitstreams: 2 Duchateau_Alexandre_Xavier.rar: 370203 bytes, checksum: 802c894b4d8aa662840670d9f1a5014f (MD5) Duchateau_Alexandre_Xavier.pdf: 548097 bytes, checksum: cc323ab8940885eeba50ff7a67a5627f (MD5)","Made available in DSpace on 2013-08-22T16:38:53Z (GMT). No. of bitstreams: 3 Alexandre_Duchateau.pdf: 548097 bytes, checksum: cc323ab8940885eeba50ff7a67a5627f (MD5) Duchateau_Alexandre_Xavier.rar: 370203 bytes, checksum: 802c894b4d8aa662840670d9f1a5014f (MD5) license.txt: 4065 bytes, checksum: 06876209876464b5fb30aab772c2a95f (MD5)"]},{"key":"dc:title","label":"Title","values":["Automatic algorithm derivation and exploration in linear algebra for parallelism and locality"]}]}],"canonical_facts":{"dc:contributor":["Padua, David A.","Barthou, Denis","Kale, Laxmikant V.","Heath, Michael T.","Garzaran, Maria J."],"dc:creator":["Duchateau, Alexandre"],"dc:date":["2013-08-22T16:38:53Z","2013-08"],"dc:description":["\"Parallelization is one of the major challenges for programmers. But parallelizing existing code is a hard task that can lead to less than optimal solutions since sequential programs can su er from impediments to parallelization resulting from the semantic of the languages or the data structures used rather than the nature of the problem being solved. To avoid such artifacts, programmers can analyze the algorithms to decide which dependencies are \"\"real\"\" and which can be ignored. But even then, conventional algorithms were developed with speci c objectives in mind, such as reducing the total number of operations, which while good to achieve sequential performance, may not be the primary objective when considering parallel machines. We propose to focus on a speci c domain and attack the parallelizing issue at the source, starting from a high level description of the equations without any knowledge of existing algorithms to solve the problem and automatically derive parallel solutions. Hydra accepts an equation written in terms of operations on matrices and automatically produces highly e cient code to solve these equations. Processing of the equation starts by tiling the matrices. This transforms the equation into either a single new equation containing terms involving tiles or into multiple equations some of which can be solved in parallel with each other. Hydra continues transforming the equations using tiling and seeking terms that Hydra knows how to compute or equations it knows how to solve. The end result is that by transforming the equations Hydra can produce multiple solvers with di erent locality behavior and/or di erent parallel execution pro les. Next, Hydra applies empirical search over this space of possible solvers to identify the most e cient version. In this way, Hydra enables the automatic production of e cient solvers requiring very little or no coding at all and delivering performance approximating that of the highly tuned library routines such as Intels MKL. With faster development time for modern architecture, the time available for hand-tuning of high performance libraries diminishes. Intel already started o ering auto-tuned library routines (From Spiral) in their IPP library, to broaden the scope of application of the collection, without having to increase the man hours required to hand-tune everything.\"","Item withdrawn by Mark Zulauf (zulauf@illinois.edu) on 2013-07-01T14:39:43Z Item was in collections: University of Illinois Theses & Dissertations (ID: 1) No. of bitstreams: 2 Duchateau_Alexandre_Xavier.rar: 370203 bytes, checksum: 802c894b4d8aa662840670d9f1a5014f (MD5) Duchateau_Alexandre_Xavier.pdf: 548097 bytes, checksum: cc323ab8940885eeba50ff7a67a5627f (MD5)","Made available in DSpace on 2013-08-22T16:38:53Z (GMT). No. of bitstreams: 3 Alexandre_Duchateau.pdf: 548097 bytes, checksum: cc323ab8940885eeba50ff7a67a5627f (MD5) Duchateau_Alexandre_Xavier.rar: 370203 bytes, checksum: 802c894b4d8aa662840670d9f1a5014f (MD5) license.txt: 4065 bytes, checksum: 06876209876464b5fb30aab772c2a95f (MD5)"],"dc:identifier":["http://hdl.handle.net/2142/45394"],"dc:language":["en"],"dc:rights":["Copyright 2013 Alexandre Xavier Duchateau"],"dc:subject":["Autotuning","Linear Algebra","Parallelism","Multicore","Tiling"],"dc:title":["Automatic algorithm derivation and exploration in linear algebra for parallelism and locality"],"dc:type":["text"],"thesis:degree_discipline":["Computer Science"],"thesis:degree_level":["Dissertation"],"thesis:degree_name":["Ph.D."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:25:34Z"}