Multiprocessor Scheduling with the Aid of Network Flow Algorithms
- 1 January 1977
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Software Engineering
- Vol. SE-3 (1) , 85-93
- https://doi.org/10.1109/tse.1977.233840
Abstract
In a distributed computing system a modular program must have its modules assigned among the processors so as to avoid excessive interprocessor communication while taking advantage of specific efficiencies of some processors in executing some program modules. In this paper we show that this program module assignment problem can be solved efficiently by making use of the well-known Ford–Fulkerson algorithm for finding maximum flows in commodity networks as modified by Edmonds and Karp, Dinic, and Karzanov. A solution to the two-processor problem is given, and extensions to three and n-processors are considered with partial results given without a complete efficient solution.Keywords
This publication has 8 references indexed in Scilit:
- Using page residency to select the working set parameterCommunications of the ACM, 1973
- Some observations on semiconductor technology and the architecture of large digital modulesComputer, 1973
- A resource sharing executive for the ARPANETPublished by Association for Computing Machinery (ACM) ,1973
- A new minicomputer/multiprocessor for the ARPA networkPublished by Association for Computing Machinery (ACM) ,1973
- Optimal scheduling for two-processor systemsActa Informatica, 1972
- Theoretical Improvements in Algorithmic Efficiency for Network Flow ProblemsJournal of the ACM, 1972
- Resource-sharing computer communications networksProceedings of the IEEE, 1972
- Multi-Terminal Network FlowsJournal of the Society for Industrial and Applied Mathematics, 1961