Processor Scheduling for Linearly Connected Parallel Processors
- 1 July 1986
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers
- Vol. C-35 (7) , 632-638
- https://doi.org/10.1109/tc.1986.1676804
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
This publication has 14 references indexed in Scilit:
- Computational architectures for intelligence and motivationPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- The Piecewise Data Flow Architecture: Architectural ConceptsIEEE Transactions on Computers, 1983
- DDDP-a Distributed Data Driven ProcessorPublished by Association for Computing Machinery (ACM) ,1983
- Heuristic Models of Task Assignment Scheduling in Distributed SystemsComputer, 1982
- A Survey of Interconnection NetworksComputer, 1981
- MIPS: A VLSI Processor ArchitecturePublished by Springer Nature ,1981
- Microcode compactionPublished by Association for Computing Machinery (ACM) ,1981
- Task Allocation in Distributed Data ProcessingComputer, 1980
- Local Microcode Compaction TechniquesACM Computing Surveys, 1980
- Bounds on the Number of Processors and Time for Multiprocessor Optimal SchedulesIEEE Transactions on Computers, 1973