Bounds on the Number of Processors and Time for Multiprocessor Optimal Schedules
Bounds on the Number of Processors and Time for Multiprocessor Optimal Schedules
复制标题
多处理器最佳调度的处理器数量和时间的界限
DOI：
10.1109/tc.1973.5009153
复制
发表时间：
1973
影响因子：
3.7
通讯作者：
B. Bussell
中科院分区：
文献类型：
--
作者：
E. Fernández;B. Bussell
本文讨论了由相同部件组成的多处理机系统调度的两个重要问题。1)给定一个由无环有向图的顶点表示的计算的偏序集合及其相关的执行时间，找出在不超过该图的关键路径长度的时间内执行它们的最小处理器数量。2)确定当有固定数量的处理器可用时，处理这组计算的最短时间。一个统一的配方上的最小处理器数量和时间的下限。这些下限比以前已知的值更清晰，并提供了一个通用的框架，为推导简化的表达式提供了见解。给出了一个新的最小处理器数上界，该上界比已知的上界更精确。这些界限的计算方面进行了讨论。
Two problems of importance for the scheduling of multiprocessing systems composed of identical units are discussed in this paper. 1) Given a partially ordered set of computations represented by the vertices of an acyclic directed graph with their associated execution times, find the minimum number of processors in order to execute them in a time not exceeding the length of the critical path of this graph. 2) Determine the minimum time to process this set of computations when a fixed number of processors is available. A unified formulation for lower bounds on the minimum number of processors and on time is presented. These lower bounds are sharper than previously known values and provide a general framework that gives insight for deriving simplified expressions. A new upper bound on the minimum number of processors is presented, which is sharper than the known bounds. The computational aspects of these bounds are also discussed.