DUAL PROCESSOR SCHEDULING WITH DYNAMIC REASSIGNMENT

被引：60

作者：

BOKHARI, SH

机构：

[1] Institute for Computer Applications in Science and Engineering, NASA Langley Research Center, Hampton

来源：

IEEE TRANSACTIONS ON SOFTWARE ENGINEERING | 1979年 / 5卷 / 04期

关键词：

cutsets; distributed computers; dynamic assignment; Index Terms-Computer networks; load balancing; maximum flows; network flow; partitioning;

D O I：

10.1109/TSE.1979.234201

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

The problem of finding an optimal dynamic assignment of a modular program for a two-processor system is analyzed. Stone's formulation of the static assignment problem is extended to include the cost of dynamically reassigning a module from one processor to the other and the cost of module residence without execution. By relocating modules during the course of program execution, changes in the locality of the program can be taken into account. It is shown that network flow algorithms may be used to find a dynamic assignment that minimizes the sum of module execution costs, module residence costs, intermodule communication costs, and module reassignment costs. Techniques for reducing the size of the problem are described for the case where the costs of residence are negligible. Copyright © 1979 by The Institute of Electrical and Electronics Engineers, Inc.

引用

页码：341 / 349

页数：9

共 10 条

[1] Stone H.S., Multiprocessor scheduling with the aid of network flow algorithms, IEEE Trans. Software Eng., SE-3, pp. 85-93, (1977)
[2] Critical load factors in distributed computer systems, IEEE Trans. Software Eng., SE-4, pp. 254-258, (1978)
[3] Dinic E.A., Algorithm for solution of a problem of maximum flow in a network with power estimation, Math. Dokl., 11, 5, pp. 1277-1280, (1970)
[4] Edmonds J., Karp R.M., Theoretical improvements inalgorithmic efficiency for network flow problems, J. Ass. Comput. Mach., 19, pp. 248-264, (1972)
[5] Ford L.R., Fulkerson D.R., Flows in Networks, (1962)
[6] Karzanov A.V., Determining the maximal flow in a network by the method of preflows, Sov. Math. Dokl., 15, 2, pp. 434-437, (1974)
[7] Van Dam A., Stabler G., Harrington R., Intelligent satellites for interactive graphics, Proc. IEEE, 62, pp. 83-92, (1974)
[8] Van Dam A., Computer graphics and its applications, (1974)
[9] Stabler G.M., A system for interconnected processing, (1974)
[10] Michel J., Van Dam A., Experience with distributedprocessing on a host/satellite graphics system, Proc. SIGGRAPH Computer Graphics, 10, 2, (1976)

← 1 →