LOWER AND UPPER-BOUNDS ON TIME FOR MULTIPROCESSOR OPTIMAL SCHEDULES

被引：16

作者：

JAIN, KK

RAJARAMAN, V

机构：

[1] Department of Computer Science and Automation, Indian Institute of Science, Bangalore

来源：

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS | 1994年 / 5卷 / 08期

关键词：

BOUNDS ON NUMBER OF PROCESSORS; BOUNDS ON TIME; MULTIPROCESSING; OPTIMAL SCHEDULING; PARALLEL PROCESSING; PERFORMANCE EVALUATION; SCHEDULING DIRECT ACYCLIC TASK GRAPHS;

D O I：

10.1109/71.298216

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

The lower and upper bounds on the minimum time needed to process a given directed acyclic task graph for a given number of processors are derived. It is proved that the proposed lower bound on time is not only sharper than the previously known values but also easier to calculate. The upper bound on time, which is useful in determining the worst caw behavior of a given task graph, is presented for the first time' The lower and upper bounds on the minimum number of processors required to process a given task graph in the minimum possible time are also derived. It is seen with a number of randomly generated dense task graphs that the lower and upper bounds we derive are equal, thus giving the optimal time for scheduling directed acyclic task graphs on a given set of processors.

引用

页码：879 / 886

页数：8

共 22 条

[1]

Coffman E.G., 1976, COMPUTER JOB SHOP SC

[2]

Coffman E. G., 1972, ACTA INFORM, V1, P200

[3] SCHEDULING PRECEDENCE GRAPHS OF BOUNDED HEIGHT [J].