{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/69554"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/69554","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Program Partitioning and Synchronization on Multiprocessor Systems (Parallel, Computer Architecture, Compiler)","abstract":"Since the mid 1970's, vector machines have dominated the supercomputer market. Because of technological limitations, faster circuits and more levels of pipelining of vector processors can no longer satisfy the increasing demand for high-speed computation. Multiprocessing problems in parallel is a natural trend. Five essential issues are identified in solving problems on multiprocessor systems: control structure, program partitioning, scheduling, synchronization, and memory access. The solutions of these problems determine the performance and efficiency of future multiprocessor machines.","abstract_html":"Since the mid 1970's, vector machines have dominated the supercomputer market. Because of technological limitations, faster circuits and more levels of pipelining of vector processors can no longer satisfy the increasing demand for high-speed computation. Multiprocessing problems in parallel is a natural trend. Five essential issues are identified in solving problems on multiprocessor systems: control structure, program partitioning, scheduling, synchronization, and memory access. The solutions of these problems determine the performance and efficiency of future multiprocessor machines.","abstract_has_math":false,"creators":["Peir, Jih-Kwon"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Computer Science","degree_department":null,"school":null,"contributors":[],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2014,"date_issued":"2014-12-15T19:25:44Z","date_published":"2014-12-15T19:25:44Z","updated_at":"2026-07-22T22:26:01Z","subjects":["Computer Science"],"languages":[],"rights":[],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier","label":"Identifier","values":["(UMI)AAI8623388"],"render_values":[{"text":"(UMI)AAI8623388","href":null,"code":true}]}]},"links":{"outbound_url":"http://hdl.handle.net/2142/69554","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:creator","label":"Author","values":["Peir, Jih-Kwon"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2014-12-15T19:25:44Z","10000-01-01","1986"]},{"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/69554","(UMI)AAI8623388"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Since the mid 1970's, vector machines have dominated the supercomputer market. Because of technological limitations, faster circuits and more levels of pipelining of vector processors can no longer satisfy the increasing demand for high-speed computation. Multiprocessing problems in parallel is a natural trend. Five essential issues are identified in solving problems on multiprocessor systems: control structure, program partitioning, scheduling, synchronization, and memory access. The solutions of these problems determine the performance and efficiency of future multiprocessor machines.","This thesis introduces new solutions for the synchronization and partitioning problems. The bit-map method synchronizes concurrent executing processes at the data level. Each synchronized data element has an attached sync field, and each synchronization memory operation contains a mask value. The data can be accessed only when the mask matches the sync. A proper referencing order for the data can be maintained. Two factors are considered when partitioning a program into processes executing in parallel: amount of parallelism and memory access and synchronization overhead. This thesis introduces a minimum distance method which partitions a recurrence loop into independent execution sets. This method uses the minimum dependence distance of each dimension of all dependence cycles to divide the index set of the loop into independent partitions. When a loop does not have a sufficient number of independent sets, the block and the interleaved methods partition the loop using a proper synchronization mechanism. A programmer assistance tool helps programmers in using these partitioning and synchronization methods. A simulator in the tool compares different partitioning strategies. This programmer assistance methodology allows users to explore several algorithms and select one which fits the appropriate multiprocessor architecture.","Made available in DSpace on 2014-12-15T19:25:44Z (GMT). No. of bitstreams: 1 8623388.pdf: 5024705 bytes, checksum: 24d680bb71a27f6b92751ddd1f4f6707 (MD5) Previous issue date: 1986","Embargo set by: Seth Robbins for item 69720 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","170 p.","Thesis (Ph.D.)--University of Illinois at Urbana-Champaign, 1986."]},{"key":"dc:title","label":"Title","values":["Program Partitioning and Synchronization on Multiprocessor Systems (Parallel, Computer Architecture, Compiler)"]}]}],"canonical_facts":{"dc:creator":["Peir, Jih-Kwon"],"dc:date":["2014-12-15T19:25:44Z","10000-01-01","1986"],"dc:description":["Since the mid 1970's, vector machines have dominated the supercomputer market. Because of technological limitations, faster circuits and more levels of pipelining of vector processors can no longer satisfy the increasing demand for high-speed computation. Multiprocessing problems in parallel is a natural trend. Five essential issues are identified in solving problems on multiprocessor systems: control structure, program partitioning, scheduling, synchronization, and memory access. The solutions of these problems determine the performance and efficiency of future multiprocessor machines.","This thesis introduces new solutions for the synchronization and partitioning problems. The bit-map method synchronizes concurrent executing processes at the data level. Each synchronized data element has an attached sync field, and each synchronization memory operation contains a mask value. The data can be accessed only when the mask matches the sync. A proper referencing order for the data can be maintained. Two factors are considered when partitioning a program into processes executing in parallel: amount of parallelism and memory access and synchronization overhead. This thesis introduces a minimum distance method which partitions a recurrence loop into independent execution sets. This method uses the minimum dependence distance of each dimension of all dependence cycles to divide the index set of the loop into independent partitions. When a loop does not have a sufficient number of independent sets, the block and the interleaved methods partition the loop using a proper synchronization mechanism. A programmer assistance tool helps programmers in using these partitioning and synchronization methods. A simulator in the tool compares different partitioning strategies. This programmer assistance methodology allows users to explore several algorithms and select one which fits the appropriate multiprocessor architecture.","Made available in DSpace on 2014-12-15T19:25:44Z (GMT). No. of bitstreams: 1 8623388.pdf: 5024705 bytes, checksum: 24d680bb71a27f6b92751ddd1f4f6707 (MD5) Previous issue date: 1986","Embargo set by: Seth Robbins for item 69720 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","170 p.","Thesis (Ph.D.)--University of Illinois at Urbana-Champaign, 1986."],"dc:identifier":["http://hdl.handle.net/2142/69554","(UMI)AAI8623388"],"dc:subject":["Computer Science"],"dc:title":["Program Partitioning and Synchronization on Multiprocessor Systems (Parallel, Computer Architecture, Compiler)"],"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"}