Assignment of Tasks in a Distributed Processor System with Limited Memory
- 1 April 1979
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers
- Vol. C-28 (4) , 291-299
- https://doi.org/10.1109/tc.1979.1675348
Abstract
A recently published algorithm shows how to assign modules to a two-processor computer system with distributed execution so as to minimize the total of execution costs and interprocessor communication costs. In this paper we consider the same problem except that one processor has limited memory capacity. Although this problem is NP-complete, techniques based on the Gomory–Hu tree from network flow theory can be applied to instances of the problem to obtain a reduction in complexity. A new technique based on a graph called the inclusive cut graph is shown to be an even more powerful tool. These two techniques can solve some instances of the problem completely; still others are reduced sufficiently to be susceptible to enumerative techniques. In the worst case, the techniques yield no reduction in problem size.Keywords
This publication has 8 references indexed in Scilit:
- Computational Complexity of Combinatorial and Graph-Theoretic ProblemsPublished by Springer Nature ,2011
- Multiprocessor Scheduling with the Aid of Network Flow AlgorithmsIEEE Transactions on Software Engineering, 1977
- Experience with distributed processing on a host/satellite graphics systemPublished by Association for Computing Machinery (ACM) ,1976
- Intelligent satellites for interactive graphicsProceedings of the IEEE, 1974
- Some observations on semiconductor technology and the architecture of large digital modulesComputer, 1973
- 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