Program Partitioning and Synchronization on Multiprocessor Systems (Parallel, Computer Architecture, Compiler)
Peir, Jih-Kwon
This item is only available for download by members of the University of Illinois community. Students, faculty, and staff at the U of I may log in with your NetID and password to view the item. If you are trying to access an Illinois-restricted dissertation or thesis, you can request a copy through your library's Inter-Library Loan office or purchase a copy directly from ProQuest.
Permalink
https://hdl.handle.net/2142/69554
Description
Title
Program Partitioning and Synchronization on Multiprocessor Systems (Parallel, Computer Architecture, Compiler)
Author(s)
Peir, Jih-Kwon
Issue Date
1986
Department of Study
Computer Science
Discipline
Computer Science
Degree Granting Institution
University of Illinois at Urbana-Champaign
Degree Name
Ph.D.
Degree Level
Dissertation
Keyword(s)
Computer Science
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.
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.
Use this login method if you
don't
have an
@illinois.edu
email address.
(Oops, I do have one)
IDEALS migrated to a new platform on June 23, 2022. If you created
your account prior to this date, you will have to reset your password
using the forgot-password link below.
