Load Balancing Problems for Multiclass Jobs in Distributed/Parallel Computer Systems
Load Balancing Problems for Multiclass Jobs in Distributed/Parallel Computer Systems
复制标题
DOI：
10.1109/12.660168
复制
发表时间：
1998-03
期刊：
影响因子：
--
通讯作者：
Jie Li;H. Kameda
中科院分区：
文献类型：
--
作者：
Jie Li;H. Kameda
考虑了一般网络配置下分布式/并行计算机系统中多类作业的负载平衡问题。我们构建了这样一个分布式/并行计算机系统的一般模型。该系统由通过一般配置的通信/互连网络互连的异构主机计算机/处理器（节点）组成，其中存在若干类作业，每一类作业在每个主机和每个通信链路处具有其不同的延迟功能。该模型被用来制定多类作业负载平衡问题作为一个非线性优化问题，其中的目标是最小化的平均响应时间的作业。对最优化问题的解，导出了一些简单直观的理论结果。在这些结果的基础上，我们提出了一个有效的负载平衡算法，在整个分布式/并行系统的负载平衡。该算法有两个吸引人的特点。一个是该算法可以以分散的方式实现。另一个特点是结构简单直接。模型的节点，通信网络，并说明了一个数值例子。所提出的算法相比，一个著名的标准最速下降算法，FD算法。通过数值实验，我们表明，该算法具有更快的收敛速度的计算时间比FD算法。
Load balancing problems for multiclass jobs in distributed/parallel computer systems with general network configurations are considered. We construct a general model of such a distributed/parallel computer system. The system consists of heterogeneous host computers/processors (nodes) which are interconnected by a generally configured communication/interconnection network wherein there are several classes of jobs, each of which has its distinct delay function at each host and each communication link. This model is used to formulate the multiclass job load balancing problem as a nonlinear optimization problem in which the goal is to minimize the mean response time of a job. A number of simple and intuitive theoretical results on the solution of the optimization problem are derived. On the basis of these results, we propose an effective load balancing algorithm for balancing the load over an entire distributed/parallel system. The proposed algorithm has two attractive features. One is that the algorithm can be implemented in a decentralized fashion. Another feature is simple and straightforward structure. Models of nodes, communication networks, and a numerical example are illustrated. The proposed algorithm is compared with a well-known standard steepest-descent algorithm, the FD algorithm. By using numerical experiments, we show that the proposed algorithm has much faster convergence in terms of computational time than the FD algorithm.