Title :
Processor Scheduling for Linearly Connected Parallel Processors
Author :
McDowell, Charles E. ; Appelbe, William F.
Author_Institution :
Department of Computer and Information Sciences, University of Califomia
fDate :
7/1/1986 12:00:00 AM
Abstract :
A low-level parallel processor (LLPP) is one in which two or more machine-level operations are executed in parallel. This paper analyzes the use of linearly connected LLPP´s for parallel evaluation of program fragments. A graph-theoretic model is presented which describes the communication constraints of linearly connected parallel processors. A tight, necessary condition for finding assignments of program fragments to linearly connected LLPP´s that require no communication delays is presented. Also, several weak sufficient conditions have been found and efficient heuristics for determining optimal assignments have been developed.
Keywords :
Compilers; interconnection networks; interprocessor communication; parallel architecture; parallel computation; processor scheduling; Compaction; Computer architecture; Computer networks; Concurrent computing; Delay; Multiprocessor interconnection networks; Optimal scheduling; Parallel architectures; Processor scheduling; Sufficient conditions; Compilers; interconnection networks; interprocessor communication; parallel architecture; parallel computation; processor scheduling;
Journal_Title :
Computers, IEEE Transactions on
DOI :
10.1109/TC.1986.1676804
