{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/69600"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/69600","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Communication and Synchronization in Parallel Computation","abstract":"In this thesis we study communication and synchronization overheads in parallel algorithms executing on shared memory multiprocessors.","abstract_html":"In this thesis we study communication and synchronization overheads in parallel algorithms executing on shared memory multiprocessors.","abstract_has_math":false,"creators":["Jayasimha, Doddaballapur Narasimha-Murthy"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Computer Science","degree_department":null,"school":null,"contributors":["Loui, Michael C.","Lawrie, Duncan H.,"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2014,"date_issued":"2014-12-15T19:26:07Z","date_published":"2014-12-15T19:26:07Z","updated_at":"2026-07-22T22:26:01Z","subjects":["Computer Science"],"languages":[],"rights":[],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier","label":"Identifier","values":["(UMI)AAI8908719"],"render_values":[{"text":"(UMI)AAI8908719","href":null,"code":true}]}]},"links":{"outbound_url":"http://hdl.handle.net/2142/69600","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Loui, Michael C.","Lawrie, Duncan H.,"]},{"key":"dc:creator","label":"Author","values":["Jayasimha, Doddaballapur Narasimha-Murthy"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2014-12-15T19:26:07Z","10000-01-01","1988"]},{"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":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/69600","(UMI)AAI8908719"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["In this thesis we study communication and synchronization overheads in parallel algorithms executing on shared memory multiprocessors.","In the first part, we focus on the communication requirements of parallel algorithms. We define a communication complexity measure for parallel algorithms, modeling the execution of a parallel algorithm on a shared memory multiprocessor by a directed acyclic graph (DAG). We derive a lower bound on the communication for a particular class of graphs corresponding to nested iterative loops. For the DAG representing a triangular solver of size n, we show that the communication (c) and parallel time (t) product ct = $\\Omega$($n\\sp3$) irrespective of the number of processors used. This result implies there exists a trade-off between computation time and communication. Finally, we define a synchronization complexity measure.","In the second part, we consider the commonly required forms of synchronization in a multiprocessor: barrier, reporting, and mutual exclusion. We study three schemes to implement barrier synchronization and develop analytical models to estimate their performance. For n processes, the first scheme requires $O(n$ log $n$) accesses as opposed to ($2n$ - 1), the minimum number of accesses. The second scheme, which uses a synchronization tree, requires $O(log\\ n)$ accesses to any node of the tree. The third scheme has a linear growth in the number of accesses (approximately 3n). We study two of the synchronization schemes through simulation. The simulator is trace driven and is based on the Omega interconnection network. The simulation results are in broad agreement with our analytical results.","We next introduce a new synchronization primitive, the distributed synchronizer. An efficient implementation of this primitive requires simple hardware enhancements at the switching elements of the processor-memory multistage interconnection network. The primitive implements reporting and the barrier with negligible overheads, and the semaphore operations are bounded fair.","Finally, we study bounded fairness. Bounded fairness is stronger than the usual notion of fairness based on eventuality. We give applications of the bounded fairness concept. We formalize bounded fairness by introducing a new operator $\\langle k\\rangle$ into temporal logic. We show that the new logic is more powerful than the temporal logic with the eventuality operator, and is complete and satisfiable.","Made available in DSpace on 2014-12-15T19:26:07Z (GMT). No. of bitstreams: 1 8908719.pdf: 4980175 bytes, checksum: 28c78f78ec8ed3aaa081851be37f50a7 (MD5) Previous issue date: 1988","Embargo set by: Seth Robbins for item 69766 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","154 p.","Thesis (Ph.D.)--University of Illinois at Urbana-Champaign, 1988."]},{"key":"dc:title","label":"Title","values":["Communication and Synchronization in Parallel Computation"]}]}],"canonical_facts":{"dc:contributor":["Loui, Michael C.","Lawrie, Duncan H.,"],"dc:creator":["Jayasimha, Doddaballapur Narasimha-Murthy"],"dc:date":["2014-12-15T19:26:07Z","10000-01-01","1988"],"dc:description":["In this thesis we study communication and synchronization overheads in parallel algorithms executing on shared memory multiprocessors.","In the first part, we focus on the communication requirements of parallel algorithms. We define a communication complexity measure for parallel algorithms, modeling the execution of a parallel algorithm on a shared memory multiprocessor by a directed acyclic graph (DAG). We derive a lower bound on the communication for a particular class of graphs corresponding to nested iterative loops. For the DAG representing a triangular solver of size n, we show that the communication (c) and parallel time (t) product ct = $\\Omega$($n\\sp3$) irrespective of the number of processors used. This result implies there exists a trade-off between computation time and communication. Finally, we define a synchronization complexity measure.","In the second part, we consider the commonly required forms of synchronization in a multiprocessor: barrier, reporting, and mutual exclusion. We study three schemes to implement barrier synchronization and develop analytical models to estimate their performance. For n processes, the first scheme requires $O(n$ log $n$) accesses as opposed to ($2n$ - 1), the minimum number of accesses. The second scheme, which uses a synchronization tree, requires $O(log\\ n)$ accesses to any node of the tree. The third scheme has a linear growth in the number of accesses (approximately 3n). We study two of the synchronization schemes through simulation. The simulator is trace driven and is based on the Omega interconnection network. The simulation results are in broad agreement with our analytical results.","We next introduce a new synchronization primitive, the distributed synchronizer. An efficient implementation of this primitive requires simple hardware enhancements at the switching elements of the processor-memory multistage interconnection network. The primitive implements reporting and the barrier with negligible overheads, and the semaphore operations are bounded fair.","Finally, we study bounded fairness. Bounded fairness is stronger than the usual notion of fairness based on eventuality. We give applications of the bounded fairness concept. We formalize bounded fairness by introducing a new operator $\\langle k\\rangle$ into temporal logic. We show that the new logic is more powerful than the temporal logic with the eventuality operator, and is complete and satisfiable.","Made available in DSpace on 2014-12-15T19:26:07Z (GMT). No. of bitstreams: 1 8908719.pdf: 4980175 bytes, checksum: 28c78f78ec8ed3aaa081851be37f50a7 (MD5) Previous issue date: 1988","Embargo set by: Seth Robbins for item 69766 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","154 p.","Thesis (Ph.D.)--University of Illinois at Urbana-Champaign, 1988."],"dc:identifier":["http://hdl.handle.net/2142/69600","(UMI)AAI8908719"],"dc:subject":["Computer Science"],"dc:title":["Communication and Synchronization in 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:26:01Z"}