{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/23071"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/23071","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Run-time parallelization: A framework for parallel computation","abstract":"The goal of parallelizing, or restructuring, compilers is to detect and exploit parallelism in sequential programs written in conventional languages. Current parallelizing compilers do a reasonable job of extracting parallelism from programs with regular, statically analyzable access patterns. However, if the memory access pattern of the program is input data dependent, then static data dependence analysis and consequently parallelization is impossible. Moreover, in this case the compiler cannot apply privatization and reduction parallelization, the transformations that have been proven to be the most effective in removing data dependences and increasing the amount of exploitable parallelism in the program. Typical examples of irregular, dynamic applications are complex simulations such as SPICE for circuit simulation, DYNA-3D for structural mechanics modeling, DMOL for quantum mechanical simulation of molecules, and CHARMM for molecular dynamics simulation of organic systems. Therefore, since irregular programs represent a large and important fraction of applications, an automatable framework for run-time parallelization is needed to complement existing and future static compiler techniques.","abstract_html":"The goal of parallelizing, or restructuring, compilers is to detect and exploit parallelism in sequential programs written in conventional languages. Current parallelizing compilers do a reasonable job of extracting parallelism from programs with regular, statically analyzable access patterns. However, if the memory access pattern of the program is input data dependent, then static data dependence analysis and consequently parallelization is impossible. Moreover, in this case the compiler cannot apply privatization and reduction parallelization, the transformations that have been proven to be the most effective in removing data dependences and increasing the amount of exploitable parallelism in the program. Typical examples of irregular, dynamic applications are complex simulations such as SPICE for circuit simulation, DYNA-3D for structural mechanics modeling, DMOL for quantum mechanical simulation of molecules, and CHARMM for molecular dynamics simulation of organic systems. Therefore, since irregular programs represent a large and important fraction of applications, an automatable framework for run-time parallelization is needed to complement existing and future static compiler techniques.","abstract_has_math":false,"creators":["Rauchwerger, Lawrence"],"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."],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2011,"date_issued":"2011-05-07T14:01:07Z","date_published":"2011-05-07T14:01:07Z","updated_at":"2026-07-22T22:25:21Z","subjects":["Computer Science"],"languages":["eng"],"rights":["Copyright 1995 Rauchwerger, Lawrence"],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier","label":"Identifier","values":["AAI9624468","(UMI)AAI9624468"],"render_values":[{"text":"AAI9624468","href":null,"code":true},{"text":"(UMI)AAI9624468","href":null,"code":true}]}]},"links":{"outbound_url":"http://hdl.handle.net/2142/23071","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Padua, David A."]},{"key":"dc:creator","label":"Author","values":["Rauchwerger, Lawrence"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2011-05-07T14:01:07Z","10000-01-01","1995"]},{"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":["Computer Science"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["eng"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 1995 Rauchwerger, Lawrence"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["AAI9624468","(UMI)AAI9624468","http://hdl.handle.net/2142/23071"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["The goal of parallelizing, or restructuring, compilers is to detect and exploit parallelism in sequential programs written in conventional languages. Current parallelizing compilers do a reasonable job of extracting parallelism from programs with regular, statically analyzable access patterns. However, if the memory access pattern of the program is input data dependent, then static data dependence analysis and consequently parallelization is impossible. Moreover, in this case the compiler cannot apply privatization and reduction parallelization, the transformations that have been proven to be the most effective in removing data dependences and increasing the amount of exploitable parallelism in the program. Typical examples of irregular, dynamic applications are complex simulations such as SPICE for circuit simulation, DYNA-3D for structural mechanics modeling, DMOL for quantum mechanical simulation of molecules, and CHARMM for molecular dynamics simulation of organic systems. Therefore, since irregular programs represent a large and important fraction of applications, an automatable framework for run-time parallelization is needed to complement existing and future static compiler techniques.","In this thesis we present several original techniques that together sketch how automatic compilation can go beyond statically analyzable codes. The methods described are fundamentally efficient, scalable and general, i.e., their characteristics are not based on heuristics with a wide performance distribution across their input domain but are algorithms that can be analytically proven to produce speedups given the necessary resources and available parallelism. We introduce the idea of testing only for full parallelism in the presence of run-time transformations rather than computing an execution schedule. We introduce the aggressive strategy of speculative parallel execution (scalable to any parallel system--from micros to multiprocessors). We describe a new technique for analyzing and scheduling loops which are only partially parallel. Additionally we present a framework for the parallelization of loops which contain recurrences and have an unknown iteration space.","We believe that within the domain of automatic parallelization the true importance of this work is in breaking the barrier at which automatic parallelization had stopped: regular, well-behaved programs.","We also attempt to convey a few general ideas and dispel some older ones. Namely, optimizing at run-time implies overhead but, can actually reduce overall execution time through better exploitation of resources. Speculating about optimizations, more specifically parallelism, may be an attractive and more generally applicable alternative to the 'inspect first and execute later' strategy. Thus we view this thesis as the first step into the full integration of these techniques into commercial parallelizing compilers.","Made available in DSpace on 2011-05-07T14:01:07Z (GMT). No. of bitstreams: 2 license.txt: 4922 bytes, checksum: 910b249b4beec47e7ab768910c8f966f (MD5) 9624468.pdf: 7232534 bytes, checksum: 87417e204a058e4380fd3b02b1b2c81e (MD5) Previous issue date: 1995","Item marked as restricted to the 'UIUC Users [automated]' Group (id=2) by Howard Ding (hding2@illinois.edu) on 2011-05-07T15:01:58Z Item is restricted indefinitely.","Restriction data tranferred 2014-07-01T11:29:26-05:00 Original Data Group with Access UIUC Users [automated] Release Date: none Reason: ETDs are only available to UIUC Users without author permission","ETDs are only available to UIUC Users without author permission","U of I Only"]},{"key":"dc:title","label":"Title","values":["Run-time parallelization: A framework for parallel computation"]}]}],"canonical_facts":{"dc:contributor":["Padua, David A."],"dc:creator":["Rauchwerger, Lawrence"],"dc:date":["2011-05-07T14:01:07Z","10000-01-01","1995"],"dc:description":["The goal of parallelizing, or restructuring, compilers is to detect and exploit parallelism in sequential programs written in conventional languages. Current parallelizing compilers do a reasonable job of extracting parallelism from programs with regular, statically analyzable access patterns. However, if the memory access pattern of the program is input data dependent, then static data dependence analysis and consequently parallelization is impossible. Moreover, in this case the compiler cannot apply privatization and reduction parallelization, the transformations that have been proven to be the most effective in removing data dependences and increasing the amount of exploitable parallelism in the program. Typical examples of irregular, dynamic applications are complex simulations such as SPICE for circuit simulation, DYNA-3D for structural mechanics modeling, DMOL for quantum mechanical simulation of molecules, and CHARMM for molecular dynamics simulation of organic systems. Therefore, since irregular programs represent a large and important fraction of applications, an automatable framework for run-time parallelization is needed to complement existing and future static compiler techniques.","In this thesis we present several original techniques that together sketch how automatic compilation can go beyond statically analyzable codes. The methods described are fundamentally efficient, scalable and general, i.e., their characteristics are not based on heuristics with a wide performance distribution across their input domain but are algorithms that can be analytically proven to produce speedups given the necessary resources and available parallelism. We introduce the idea of testing only for full parallelism in the presence of run-time transformations rather than computing an execution schedule. We introduce the aggressive strategy of speculative parallel execution (scalable to any parallel system--from micros to multiprocessors). We describe a new technique for analyzing and scheduling loops which are only partially parallel. Additionally we present a framework for the parallelization of loops which contain recurrences and have an unknown iteration space.","We believe that within the domain of automatic parallelization the true importance of this work is in breaking the barrier at which automatic parallelization had stopped: regular, well-behaved programs.","We also attempt to convey a few general ideas and dispel some older ones. Namely, optimizing at run-time implies overhead but, can actually reduce overall execution time through better exploitation of resources. Speculating about optimizations, more specifically parallelism, may be an attractive and more generally applicable alternative to the 'inspect first and execute later' strategy. Thus we view this thesis as the first step into the full integration of these techniques into commercial parallelizing compilers.","Made available in DSpace on 2011-05-07T14:01:07Z (GMT). No. of bitstreams: 2 license.txt: 4922 bytes, checksum: 910b249b4beec47e7ab768910c8f966f (MD5) 9624468.pdf: 7232534 bytes, checksum: 87417e204a058e4380fd3b02b1b2c81e (MD5) Previous issue date: 1995","Item marked as restricted to the 'UIUC Users [automated]' Group (id=2) by Howard Ding (hding2@illinois.edu) on 2011-05-07T15:01:58Z Item is restricted indefinitely.","Restriction data tranferred 2014-07-01T11:29:26-05:00 Original Data Group with Access UIUC Users [automated] Release Date: none Reason: ETDs are only available to UIUC Users without author permission","ETDs are only available to UIUC Users without author permission","U of I Only"],"dc:identifier":["AAI9624468","(UMI)AAI9624468","http://hdl.handle.net/2142/23071"],"dc:language":["eng"],"dc:rights":["Copyright 1995 Rauchwerger, Lawrence"],"dc:subject":["Computer Science"],"dc:title":["Run-time parallelization: A framework for parallel computation"],"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:21Z"}