{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/19722"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/19722","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Compiler techniques for optimizing communication and data distribution for distributed-memory multicomputers","abstract":"Distributed-memory multicomputers, such as the Intel iPSC/860, the Intel Paragon, the IBM SP-1 /SP-2, the NCUBE/2, and the Thinking Machines CM-5, offer significant advantages over shared-memory multiprocessors in terms of cost and scalability. However, lacking a global address space, they present a very difficult programming model in which the user must specify how data and computation are to be distributed across processors and determine those sections of data to be communicated to specific processors. To overcome this difficulty, significant research effort has been aimed at source-to-source parallelizing compilers for multicomputers that relieve the programmer from the task of program partitioning and communication generation, while the specification of data distributions has remained a responsibility of the programmer.","abstract_html":"Distributed-memory multicomputers, such as the Intel iPSC/860, the Intel Paragon, the IBM SP-1 /SP-2, the NCUBE/2, and the Thinking Machines CM-5, offer significant advantages over shared-memory multiprocessors in terms of cost and scalability. However, lacking a global address space, they present a very difficult programming model in which the user must specify how data and computation are to be distributed across processors and determine those sections of data to be communicated to specific processors. To overcome this difficulty, significant research effort has been aimed at source-to-source parallelizing compilers for multicomputers that relieve the programmer from the task of program partitioning and communication generation, while the specification of data distributions has remained a responsibility of the programmer.","abstract_has_math":false,"creators":["Palermo, Daniel Joseph"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Electrical Engineering","degree_department":null,"school":null,"contributors":["Banerjee, Prithviraj"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2011,"date_issued":"2011-05-07T12:16:27Z","date_published":"2011-05-07T12:16:27Z","updated_at":"2026-07-22T22:25:14Z","subjects":["Engineering, Electronics and Electrical","Computer Science"],"languages":["eng"],"rights":["Copyright 1996 Palermo, Daniel Joseph"],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier","label":"Identifier","values":["9780591198485","AAI9712391","(UMI)AAI9712391"],"render_values":[{"text":"9780591198485","href":null,"code":true},{"text":"AAI9712391","href":null,"code":true},{"text":"(UMI)AAI9712391","href":null,"code":true}]}]},"links":{"outbound_url":"http://hdl.handle.net/2142/19722","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":["Palermo, Daniel Joseph"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2011-05-07T12:16:27Z","10000-01-01","1996"]},{"key":"dc:type","label":"Dc Type","values":["text"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Electrical Engineering"]},{"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":["Engineering, Electronics and Electrical","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 Palermo, Daniel Joseph"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["9780591198485","AAI9712391","(UMI)AAI9712391","http://hdl.handle.net/2142/19722"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Distributed-memory multicomputers, such as the Intel iPSC/860, the Intel Paragon, the IBM SP-1 /SP-2, the NCUBE/2, and the Thinking Machines CM-5, offer significant advantages over shared-memory multiprocessors in terms of cost and scalability. However, lacking a global address space, they present a very difficult programming model in which the user must specify how data and computation are to be distributed across processors and determine those sections of data to be communicated to specific processors. To overcome this difficulty, significant research effort has been aimed at source-to-source parallelizing compilers for multicomputers that relieve the programmer from the task of program partitioning and communication generation, while the specification of data distributions has remained a responsibility of the programmer.","The quality of the data distribution for a given application is crucial to obtaining high performance on distributed-memory multicomputers. By selecting an appropriate data distribution, the amount of communication required by an application can be dramatically reduced. The resulting performance using a given data distribution therefore depends on how well the compiler can optimize the remaining communication. In this thesis, we present and analyze several techniques to optimize communication and, based on the performance of these optimizations, automatically select the best data partitioning for a given application.","Previous work in the area of optimizing data distribution used constraints based on performance estimates (which model the communication optimizations) to select high quality data distributions which remain in effect for the entire execution of an application. For complex programs, however, such static data distributions may be insufficient to obtain acceptable performance. The selection of distributions that dynamically change over the course of a program's execution (taking into account the added overhead of performing redistribution) adds another dimension to the data partitioning problem. In this thesis, we present a technique that extends the static data partitioning algorithm to automatically determine those distributions most beneficial over specific sections of a program while taking into account the added overhead of performing redistribution. Finally, we also present an interprocedural data-flow framework that performs the conversion between a distribution-based representation (as specified by the data partitioner and required for compilation) and a redistribution-based form (as specified by HPF) while optimizing the amount of redistribution that must be performed.","These techniques have been implemented as part of the PARADIGM (PARAllelizing compiler for DIstributed-memory General-purpose Multicomputers) project at the University of Illinois. The complete system strives to provide a fully automated means to parallelize sequential programs obtaining high performance on a wide range of distributed-memory multicomputers.","Made available in DSpace on 2011-05-07T12:16:27Z (GMT). No. of bitstreams: 2 license.txt: 4922 bytes, checksum: 910b249b4beec47e7ab768910c8f966f (MD5) 9712391.pdf: 7174822 bytes, checksum: 7d0cb43ba5662efb1cc4661dd1c8084f (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:38:59Z Item is restricted indefinitely.","Restriction data tranferred 2014-07-01T11:16:20-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 techniques for optimizing communication and data distribution for distributed-memory multicomputers"]}]}],"canonical_facts":{"dc:contributor":["Banerjee, Prithviraj"],"dc:creator":["Palermo, Daniel Joseph"],"dc:date":["2011-05-07T12:16:27Z","10000-01-01","1996"],"dc:description":["Distributed-memory multicomputers, such as the Intel iPSC/860, the Intel Paragon, the IBM SP-1 /SP-2, the NCUBE/2, and the Thinking Machines CM-5, offer significant advantages over shared-memory multiprocessors in terms of cost and scalability. However, lacking a global address space, they present a very difficult programming model in which the user must specify how data and computation are to be distributed across processors and determine those sections of data to be communicated to specific processors. To overcome this difficulty, significant research effort has been aimed at source-to-source parallelizing compilers for multicomputers that relieve the programmer from the task of program partitioning and communication generation, while the specification of data distributions has remained a responsibility of the programmer.","The quality of the data distribution for a given application is crucial to obtaining high performance on distributed-memory multicomputers. By selecting an appropriate data distribution, the amount of communication required by an application can be dramatically reduced. The resulting performance using a given data distribution therefore depends on how well the compiler can optimize the remaining communication. In this thesis, we present and analyze several techniques to optimize communication and, based on the performance of these optimizations, automatically select the best data partitioning for a given application.","Previous work in the area of optimizing data distribution used constraints based on performance estimates (which model the communication optimizations) to select high quality data distributions which remain in effect for the entire execution of an application. For complex programs, however, such static data distributions may be insufficient to obtain acceptable performance. The selection of distributions that dynamically change over the course of a program's execution (taking into account the added overhead of performing redistribution) adds another dimension to the data partitioning problem. In this thesis, we present a technique that extends the static data partitioning algorithm to automatically determine those distributions most beneficial over specific sections of a program while taking into account the added overhead of performing redistribution. Finally, we also present an interprocedural data-flow framework that performs the conversion between a distribution-based representation (as specified by the data partitioner and required for compilation) and a redistribution-based form (as specified by HPF) while optimizing the amount of redistribution that must be performed.","These techniques have been implemented as part of the PARADIGM (PARAllelizing compiler for DIstributed-memory General-purpose Multicomputers) project at the University of Illinois. The complete system strives to provide a fully automated means to parallelize sequential programs obtaining high performance on a wide range of distributed-memory multicomputers.","Made available in DSpace on 2011-05-07T12:16:27Z (GMT). No. of bitstreams: 2 license.txt: 4922 bytes, checksum: 910b249b4beec47e7ab768910c8f966f (MD5) 9712391.pdf: 7174822 bytes, checksum: 7d0cb43ba5662efb1cc4661dd1c8084f (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:38:59Z Item is restricted indefinitely.","Restriction data tranferred 2014-07-01T11:16:20-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":["9780591198485","AAI9712391","(UMI)AAI9712391","http://hdl.handle.net/2142/19722"],"dc:language":["eng"],"dc:rights":["Copyright 1996 Palermo, Daniel Joseph"],"dc:subject":["Engineering, Electronics and Electrical","Computer Science"],"dc:title":["Compiler techniques for optimizing communication and data distribution for distributed-memory multicomputers"],"dc:type":["text"],"thesis:degree_discipline":["Electrical Engineering"],"thesis:degree_level":["Dissertation"],"thesis:degree_name":["Ph.D."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:25:14Z"}