{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/20771"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/20771","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Compiler and run-time support for irregular computations","abstract":"There are many important applications in computational fluid dynamics, circuit simulation and structural analysis that can be more accurately modeled using iterations on unstructured grids. In these problems, regular compiler analysis for Massively Parallel Processors (MPP) with distributed address space fails because the communication can only be determined at run-time. However, in many of these applications the communication pattern repeats for every iteration. Therefore, equivalent optimizations to the regular case can be achieved with a combination of run-time support (RTS) and compiler analysis.","abstract_html":"There are many important applications in computational fluid dynamics, circuit simulation and structural analysis that can be more accurately modeled using iterations on unstructured grids. In these problems, regular compiler analysis for Massively Parallel Processors (MPP) with distributed address space fails because the communication can only be determined at run-time. However, in many of these applications the communication pattern repeats for every iteration. Therefore, equivalent optimizations to the regular case can be achieved with a combination of run-time support (RTS) and compiler analysis.","abstract_has_math":false,"creators":["Lain, Antonio"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Computer Science","degree_department":null,"school":null,"contributors":["Banerjee, Prithviraj"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2011,"date_issued":"2011-05-07T12:48:47Z","date_published":"2011-05-07T12:48:47Z","updated_at":"2026-07-22T22:25:16Z","subjects":["Computer Science"],"languages":["eng"],"rights":["Copyright 1996 Lain, Antonio"],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier","label":"Identifier","values":["AAI9625152","(UMI)AAI9625152"],"render_values":[{"text":"AAI9625152","href":null,"code":true},{"text":"(UMI)AAI9625152","href":null,"code":true}]}]},"links":{"outbound_url":"http://hdl.handle.net/2142/20771","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Banerjee, Prithviraj"]},{"key":"dc:creator","label":"Author","values":["Lain, Antonio"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2011-05-07T12:48:47Z","10000-01-01","1996"]},{"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 1996 Lain, Antonio"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["AAI9625152","(UMI)AAI9625152","http://hdl.handle.net/2142/20771"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["There are many important applications in computational fluid dynamics, circuit simulation and structural analysis that can be more accurately modeled using iterations on unstructured grids. In these problems, regular compiler analysis for Massively Parallel Processors (MPP) with distributed address space fails because the communication can only be determined at run-time. However, in many of these applications the communication pattern repeats for every iteration. Therefore, equivalent optimizations to the regular case can be achieved with a combination of run-time support (RTS) and compiler analysis.","Moreover, many real applications have irregular access patterns with certain structure. This structure is needed to improve sequential performance, better exploiting the memory hierarchy. In many cases this structure is reflected in the array subscript expressions in the form of hybrid accesses, that is, affine combinations of array indirection and regular accesses. We will show that when we get advantage of this structure, we can dramatically reduce pre-processing overheads, both in terms of memory and time, and improve communication and single node performance.","In order to achieve these goals we need a combination of run-time and compiler support. Unfortunately, existing irregular run-time support cannot get advantage of regularity and therefore, our first requirement was to develop a new run-time support for irregular computations, that we called PILAR (Parallel Irregular Library with Application of Regularity). Our second requirement was to automate the task of exploiting regularity in irregular applications through compiler support. For this task we extended the PARADIGM compiler, developed at the University of Illinois, to handle irregular problems. Experimental results will validate the efficacy of our approach.","Made available in DSpace on 2011-05-07T12:48:47Z (GMT). No. of bitstreams: 2 license.txt: 4922 bytes, checksum: 910b249b4beec47e7ab768910c8f966f (MD5) 9625152.pdf: 4718207 bytes, checksum: 3dea6e6e743c725ee4bdb0a4211914b2 (MD5) Previous issue date: 1996","Item marked as restricted to the 'UIUC Users [automated]' Group (id=2) by Howard Ding (hding2@illinois.edu) on 2011-05-07T14:46:09Z Item is restricted indefinitely.","Restriction data tranferred 2014-07-01T11:20:37-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":["Compiler and run-time support for irregular computations"]}]}],"canonical_facts":{"dc:contributor":["Banerjee, Prithviraj"],"dc:creator":["Lain, Antonio"],"dc:date":["2011-05-07T12:48:47Z","10000-01-01","1996"],"dc:description":["There are many important applications in computational fluid dynamics, circuit simulation and structural analysis that can be more accurately modeled using iterations on unstructured grids. In these problems, regular compiler analysis for Massively Parallel Processors (MPP) with distributed address space fails because the communication can only be determined at run-time. However, in many of these applications the communication pattern repeats for every iteration. Therefore, equivalent optimizations to the regular case can be achieved with a combination of run-time support (RTS) and compiler analysis.","Moreover, many real applications have irregular access patterns with certain structure. This structure is needed to improve sequential performance, better exploiting the memory hierarchy. In many cases this structure is reflected in the array subscript expressions in the form of hybrid accesses, that is, affine combinations of array indirection and regular accesses. We will show that when we get advantage of this structure, we can dramatically reduce pre-processing overheads, both in terms of memory and time, and improve communication and single node performance.","In order to achieve these goals we need a combination of run-time and compiler support. Unfortunately, existing irregular run-time support cannot get advantage of regularity and therefore, our first requirement was to develop a new run-time support for irregular computations, that we called PILAR (Parallel Irregular Library with Application of Regularity). Our second requirement was to automate the task of exploiting regularity in irregular applications through compiler support. For this task we extended the PARADIGM compiler, developed at the University of Illinois, to handle irregular problems. Experimental results will validate the efficacy of our approach.","Made available in DSpace on 2011-05-07T12:48:47Z (GMT). No. of bitstreams: 2 license.txt: 4922 bytes, checksum: 910b249b4beec47e7ab768910c8f966f (MD5) 9625152.pdf: 4718207 bytes, checksum: 3dea6e6e743c725ee4bdb0a4211914b2 (MD5) Previous issue date: 1996","Item marked as restricted to the 'UIUC Users [automated]' Group (id=2) by Howard Ding (hding2@illinois.edu) on 2011-05-07T14:46:09Z Item is restricted indefinitely.","Restriction data tranferred 2014-07-01T11:20:37-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":["AAI9625152","(UMI)AAI9625152","http://hdl.handle.net/2142/20771"],"dc:language":["eng"],"dc:rights":["Copyright 1996 Lain, Antonio"],"dc:subject":["Computer Science"],"dc:title":["Compiler and run-time support for irregular computations"],"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:16Z"}