{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/69392"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/69392","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Reducing Interprocessor Communication in Parallel Architectures: System Configuration and Task Assignment","abstract":"Most future supercomputers will be based on parallel processing architectures. Currently, many applications with sufficient parallelism cannot efficiently run on large parallel processing systems because interprocessor communication and synchronization significantly degrade performance. Interprocessor communication is incurred on message passing systems when two processors exchange data through communication links and in shared memory systems when variables stored in shared memory are written into by one processor and then read out by another processor.","abstract_html":"Most future supercomputers will be based on parallel processing architectures. Currently, many applications with sufficient parallelism cannot efficiently run on large parallel processing systems because interprocessor communication and synchronization significantly degrade performance. Interprocessor communication is incurred on message passing systems when two processors exchange data through communication links and in shared memory systems when variables stored in shared memory are written into by one processor and then read out by another processor.","abstract_has_math":false,"creators":["Abraham, Santosh George"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Electrical Engineering","degree_department":null,"school":null,"contributors":["Davidson, Edward S."],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2014,"date_issued":"2014-12-15T19:05:32Z","date_published":"2014-12-15T19:05:32Z","updated_at":"2026-07-22T22:26:00Z","subjects":["Engineering, Electronics and Electrical"],"languages":[],"rights":[],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier","label":"Identifier","values":["(UMI)AAI8823067"],"render_values":[{"text":"(UMI)AAI8823067","href":null,"code":true}]}]},"links":{"outbound_url":"http://hdl.handle.net/2142/69392","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Davidson, Edward S."]},{"key":"dc:creator","label":"Author","values":["Abraham, Santosh George"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2014-12-15T19:05:32Z","10000-01-01","1988"]},{"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"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/69392","(UMI)AAI8823067"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Most future supercomputers will be based on parallel processing architectures. Currently, many applications with sufficient parallelism cannot efficiently run on large parallel processing systems because interprocessor communication and synchronization significantly degrade performance. Interprocessor communication is incurred on message passing systems when two processors exchange data through communication links and in shared memory systems when variables stored in shared memory are written into by one processor and then read out by another processor.","Two aspects of the communication bottleneck in multiprocessors, namely, delay and bandwidth, are identified. The tradeoff between the cost of the processors and the cost of the communication structure is analyzed and expressions are derived for the optimum number of processors that minimizes the total cost of achieving a desired performance level. Maximum speedups are limited by communication delays for most combinations of applications and parallel architectures.","Communication delay models are developed for a hierarchical multiprocessor where all processors share a global memory and processors are grouped into disjoint clusters, each with a cluster memory shared by the processors in that cluster. Three different classes of algorithms are analyzed and techniques are derived to determine the optimum cluster size, i.e., the number of processors in each cluster, that minimizes average communication delays and hence completion times. The effectiveness of hierarchical multiprocessors in emulating common interconnection schemes, viz., ring, mesh, and hypercube, is analyzed.","The solution of sparse systems of equations on the Alliant FX/8 multiprocessor is used to explore computation-communication tradeoffs. Blocking improves communication time but reduces parallelism. Optimal block sizes for various blocking schemes are determined both on the Alliant FX/8 and on an emulation of a multiprocessor with slower global memory. The execution of a linear system solver, Block Solve, on a hierarchical multiprocessor is simulated and optimum cluster sizes that minimize completion times are determined.","Algorithms that use flow graph techniques to assign tasks to processors with the objective of minimizing the sum total of all communication costs are described. An algorithm that obtains a complete assignment with a worst-case bound of less than twice the optimal is described.","Made available in DSpace on 2014-12-15T19:05:32Z (GMT). No. of bitstreams: 1 8823067.pdf: 7794796 bytes, checksum: 0bb5614bfb460e7672cf1a0e2867c3b8 (MD5) Previous issue date: 1988","Embargo set by: Seth Robbins for item 69558 Lift date: Forever Reason: Restricted to the U of I community idenfinitely during batch ingest of legacy ETDs","Restricted to the U of I community idenfinitely during batch ingest of legacy ETDs","U of I Only","227 p.","Thesis (Ph.D.)--University of Illinois at Urbana-Champaign, 1988."]},{"key":"dc:title","label":"Title","values":["Reducing Interprocessor Communication in Parallel Architectures: System Configuration and Task Assignment"]}]}],"canonical_facts":{"dc:contributor":["Davidson, Edward S."],"dc:creator":["Abraham, Santosh George"],"dc:date":["2014-12-15T19:05:32Z","10000-01-01","1988"],"dc:description":["Most future supercomputers will be based on parallel processing architectures. Currently, many applications with sufficient parallelism cannot efficiently run on large parallel processing systems because interprocessor communication and synchronization significantly degrade performance. Interprocessor communication is incurred on message passing systems when two processors exchange data through communication links and in shared memory systems when variables stored in shared memory are written into by one processor and then read out by another processor.","Two aspects of the communication bottleneck in multiprocessors, namely, delay and bandwidth, are identified. The tradeoff between the cost of the processors and the cost of the communication structure is analyzed and expressions are derived for the optimum number of processors that minimizes the total cost of achieving a desired performance level. Maximum speedups are limited by communication delays for most combinations of applications and parallel architectures.","Communication delay models are developed for a hierarchical multiprocessor where all processors share a global memory and processors are grouped into disjoint clusters, each with a cluster memory shared by the processors in that cluster. Three different classes of algorithms are analyzed and techniques are derived to determine the optimum cluster size, i.e., the number of processors in each cluster, that minimizes average communication delays and hence completion times. The effectiveness of hierarchical multiprocessors in emulating common interconnection schemes, viz., ring, mesh, and hypercube, is analyzed.","The solution of sparse systems of equations on the Alliant FX/8 multiprocessor is used to explore computation-communication tradeoffs. Blocking improves communication time but reduces parallelism. Optimal block sizes for various blocking schemes are determined both on the Alliant FX/8 and on an emulation of a multiprocessor with slower global memory. The execution of a linear system solver, Block Solve, on a hierarchical multiprocessor is simulated and optimum cluster sizes that minimize completion times are determined.","Algorithms that use flow graph techniques to assign tasks to processors with the objective of minimizing the sum total of all communication costs are described. An algorithm that obtains a complete assignment with a worst-case bound of less than twice the optimal is described.","Made available in DSpace on 2014-12-15T19:05:32Z (GMT). No. of bitstreams: 1 8823067.pdf: 7794796 bytes, checksum: 0bb5614bfb460e7672cf1a0e2867c3b8 (MD5) Previous issue date: 1988","Embargo set by: Seth Robbins for item 69558 Lift date: Forever Reason: Restricted to the U of I community idenfinitely during batch ingest of legacy ETDs","Restricted to the U of I community idenfinitely during batch ingest of legacy ETDs","U of I Only","227 p.","Thesis (Ph.D.)--University of Illinois at Urbana-Champaign, 1988."],"dc:identifier":["http://hdl.handle.net/2142/69392","(UMI)AAI8823067"],"dc:subject":["Engineering, Electronics and Electrical"],"dc:title":["Reducing Interprocessor Communication in Parallel Architectures: System Configuration and Task Assignment"],"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:26:00Z"}