Distributed scheduling strategy for divisible loads on arbitrarily configured distributed networks using load balancing via virtual routing

In this paper, we consider a scheduling problem for divisible loads originating from single or multiple sites on arbitrary networks. We first propose a generalized mathematical model and formulate the scheduling problem as an optimization problem with an objective to minimize the processing time of the loads. We derive a number of theoretical results on the solution of the optimization problem. On the basis of these first set of results, we propose an efficient algorithm for scheduling divisible loads using the concept of load balancing via virtual routing for an arbitrary network configuration. The proposed algorithm has three major attractive features. Firstly, the algorithm is simple to realize and can be implemented in a distributed fashion. The second one is in its style of working by avoiding the need for generating a timing diagram explicitly for any complex networks having an arbitrary network topology. The last one is its capability of handling divisible loads originating from both single and multiple sites. When divisible loads originate from a single node, we compare the proposed algorithm with a recently proposed RAOLD algorithm which is based on minimum cost spanning tree [J. Yao, V. Bharadwaj, Design and performance analysis of divisible load scheduling strategies on arbitrary graphs, Cluster Computing 7(2) (2004) 191–207]. When divisible loads originate from multiple sites, we test the performance on sparse, medium and densely connected networks. This is the first time in the divisible load theory (DLT) literature that such a generic approach for handling divisible loads originating from multiple sites on arbitrary networks employing load balancing via virtual routing is attempted.     

Design and performance evaluation of load distribution strategies for multiple divisible loads on heterogeneous linear daisy chain networks

In this paper, we consider the problem of scheduling multiple divisible loads on heterogeneous linear daisy chain networks. Our objective is to design a load distribution strategy such that the total processing time of a set of loads is minimized. We assume that the set of loads are resident in one of the farthest end processors, which has a scheduler that will distribute the load to the other processors in the network. When distributing a load from the set, the distribution pattern of the previous load has to be taken into consideration to ensure that no processors are left idle and there are no collisions in the communication links. We design single and multi-installments strategies to achieve the above objective. We derive certain important conditions to determine whether an optimum solution exists. We propose two heuristic strategies when an optimum solution is unattainable. Using all the above strategies, we conduct four different simulation experiments to track the performance of strategies under several real-life situations. We conducted four different simulation experiments based on the two heuristic strategies to identify the best combination suitable for our multiple-loads distribution strategy. We also run simulations for a homogeneous system to quantify the performance under 3 different policies, that is, when the loads are (a) unsorted, (b) sorted with smallest load first (SLF) and (c) sorted with largest load first (LLF). A detailed analysis of the simulation results is presented and based on these, recommendations are made for the choice of strategies. Finally, we compare the performance of a single-load distribution strategy against the multiple-loads distribution strategy designed in this paper to quantify the exact performance gain that can be achieved. Illustrative examples are also provided for ease of understanding.     

Requirement-aware strategies for scheduling real-time divisible loads on clusters

This paper investigates the real-time scheduling problem for handling heterogeneous divisible loads on cluster systems. Divisible load applications occur in many fields of science and engineering. Such applications can be easily parallelized in a master–worker fashion, but pose several scheduling challenges. We consider divisible loads associated with deadlines to enhance quality-of-service (QoS) and provide performance guarantees in distributed computing environments. In addition, since the divisible loads to be performed may widely vary in terms of their required hardware and software, we capture the loads’ various processing requirements in our load distribution strategies, a unique feature that is applicable for running proprietary applications only on certain eligible processing nodes. Thus in our problem formulation each load can only be processed by certain processors as both the loads and processors are heterogeneous. We propose scheduling algorithms referred to as Requirements-Aware Real-Time Scheduling (RARTS) algorithms, which consist of a novel scheduling policy, referred to as Minimum Slack Capacity First (MSCF), and two multi-round load distribution strategies, referred to as All Eligible Processors (AEP) and Least Capability First (LCF). We perform rigorous performance evaluation studies to quantify the performance of our strategies on a variety of scenarios.     

异构总线网络中实时可分性负载调度算法*

针对异构总线网络提出了一种动态实时可分性负载调度方法.首先,根据可分性负载调度最优性原理,分析了网络中处理器负载分配的最优次序以及参与计算的处理器数目;然后,针对实时任务的截止期限约束提出一种动态负载分配算法,该算法可以利用网络中最少的处理器数目,保证实时任务在其截止期限之前计算完成.理论分析和仿真测试都验证了所提出算法的有效性.     

Scheduling divisible loads on heterogeneous linear daisy chain networks with arbitrary processor release times

The problem of distributing and processing a divisible load in a heterogeneous linear network of processors with arbitrary processors release times is considered. A divisible load is very large in size and has computationally intensive CPU requirements. Further, it has the property that the load can be partitioned arbitrarily into any number of portions and can be scheduled onto processors independently for computation. The load is assumed to arrive at one of the farthest end processors, referred to as boundary processors, for processing. The processors in the network are assumed to have nonzero release times, i.e., the time instants from which the processors are available for processing the divisible load. Our objective is to design a load distribution strategy by taking into account the release times of the processors in such a way that the entire processing time of the load is a minimum. We consider two generic cases in which all processors have identical release times and when all processors have arbitrary release times. We adopt both the single and multiinstallment strategies proposed in the divisible load scheduling literature in our design of load distribution strategies, wherever necessary, to achieve a minimum processing time. Finally, when optimal strategies cannot be realized, we propose two heuristic strategies, one for the identical case, and the other for nonidentical release times case, respectively. Several conditions are derived to determine whether or not optimal load distribution exists and illustrative examples are provided for the ease of understanding.     

异构机群系统上双序列全局比对并行算法

对于处理机节点具有不同的计算速度、通信延迟和存储容量的异构机群系统,考虑通信启动开销,基于可分负载理论,提出一种双序列全局比对问题并行处理的最优分配策略,利用该策略确定出并行迭代次数和分配给各个从处理机的子序列长度。异构PC机群系统上的实验结果表明,提出的双序列全局比对并行算法优于基于平均分配策略的并行比对算法,获得良好的加速和可扩展性。     

A new load distribution strategy for linear network with communication delays

In this paper, we propose a new load distribution strategy called ‘send-and-receive’ for scheduling divisible loads, in a linear network of processors with communication delay. This strategy is designed to optimally utilize the network resources and thereby minimizes the processing time of entire processing load. A closed-form expression for optimal size of load fractions and processing time are derived when the processing load originates at processor located in boundary and interior of the network. A condition on processor and link speed is also derived to ensure that the processors are continuously engaged in load distributions. This paper also presents a parallel implementation of ‘digital watermarking problem’ on a personal computer-based Pentium Linear Network (PLN) topology. Experiments are carried out to study the performance of the proposed strategy and results are compared with other strategies found in literature.     

All-port total exchange in cartesian product networks

We present a general solution to the total exchange (TE) communication problem for any homogeneous multidimensional network under the all-port assumption. More specifically, we consider cartesian product networks where every dimension is the same graph (e.g. hypercubes, square meshes, n-ary d-cubes) and where each node is able to communicate simultaneously with all its neighbors. We show that if we are given an algorithm for a single n-node dimension which requires T steps, we can construct an algorithm for d-dimensions and running time of n^d−1T steps, which is provably optimal for many popular topologies. Our scheme, in effect, generalizes the TE algorithm given by Bertsekas et al. (J. Parallel Distrib. Comput. 11 (1991) 263–275) for the hypercubes and complements our theory (IEEE Trans. Parallel Distrib. Systems 9(7) (1998) 639) for the single-port model.     

Optimal placements of replicas in a ring network with majority voting protocol

In a distributed database system, data replicas are placed at different locations to achieve high data availability in the presence of link failures. With a majority voting protocol, a location survives for read/write operations if and only if it is accessible to more than half of the replicas. The problem is to find out the optimal placements for a given number of data replicas in a ring network. When the number of replicas is odd, it was conjectured by Hu et al. [X.-D. Hu, X.-H. Jia, D.-Z. Du, D.-Y. Li, H.-J. Huang, Placement of data replicas for optimal data availability in ring networks, J. Parallel Distrib. Comput., 61 (2001) 1412–1424] that every uniform placement is optimal, which is proved by Shekhar and Wu later. However, when the number of replicas is even, it was pointed out by Hu et al. that uniform placements are not optimal and the optimal placement problem may be very complicated. In this paper, we study the optimal placement problem in a ring network with majority voting protocol and an even number of replicas, and give a complete characterization of optimal placements when the number of replicas is not too large compared with the number of locations.     

Suboptimal solutions using integer approximation techniques forscheduling divisible loads on distributed bus networks

The problem of optimal divisible load distribution in distributed bus networks employing a heterogeneous cluster of processors is addressed. The objective is to minimize the total processing time of the entire load subject to the communication and computation delays. In the mathematical model we adopt, both the granularity of the load fractions and all the associated overheads (also referred to as start-up costs) in the process of communication and computation, are considered explicitly in the problem formulation. We introduce a directed flow graph model for representing the load distribution process. This representation is novel to this literature. With this model, we first derive a closed-form solution for an optimal processing time. We propose an integer approximation algorithm and derive ultimate performance bounds for the class of homogeneous networks. We then extend the problem to a special class of application problems in which the data partitioning is restricted to a finite number of partitions. For this case, we present a recursive procedure to obtain optimal processing time. We then present two different integer approximation algorithms-PIA and IIA that could generate integer load fractions and yield suboptimal solutions. The choice of these algorithms are also analyzed. All the results are extended to a class of homogeneous networks to obtain ultimate performance bounds. Several illustrative examples are provided for ease of explanation     

Handling biological sequence alignments on networked computing systems: A divide-and-conquer approach

In this paper, we address the biological sequence alignment problem, which is one of the most commonly used steps in several bioinformatics applications. We employ the Divisible Load Theory (DLT) paradigm that is suitable for handling large-scale processing on network-based systems to achieve a high degree of parallelism. Using the DLT paradigm, we propose a strategy in which we carefully partition the computation work load among the processors in the system so as to minimize the overall computation time of determining the maximum similarity between the DNA/protein sequences. We consider handling such a computational problem on networked computing platforms connected as a linear daisy chain. We derive the individual load quantum to be assigned to the processors according to computation and communication link speeds along the chain. We consider two cases of sequence alignment where post-processes, i.e., trace-back processes that are required to determine an optimal alignment, may or may not be done at individual processors in the system. We derive some critical conditions to determine if our strategies are able to yield an optimal processing time. We apply three different heuristic strategies proposed in the literature to generate sub-optimal solutions for processing time when the above conditions cannot be satisfied. To testify the proposed schemes, we use real-life DNA samples of house mouse mitochondrion and the DNA of human mitochondrion obtained from the public database GenBank [GenBank, http://www.ncbi.nlm.nih.gov] in our simulation experiments. By this study, we conclusively demonstrate the applicability and potential of the DLT paradigm to such biological sequence related computational problems.     

On the influence of start-up costs in scheduling divisible loads onbus networks

Optimal distribution of divisible loads in bus networks is considered in this paper. The problem of minimizing the processing time is investigated by including all the overhead components that could penalize the performance of the system, in addition to the inherent communication and computation delays. These overheads are considered to be constant additive factors to the respective communication and computation components. Closed-form solution for the processing time is derived and the influence of overheads on the optimal processing time is analyzed. We derive a necessary and sufficient condition for the existence of the optimal processing time. We then study the effect of changing the load distribution sequence on the time performance. Through rigorous analysis, an optimal sequence to distribute the load among the processors is identified, whenever it exists. In case such an optimal sequence fails to exist, we present a greedy algorithm to obtain a suboptimal sequence based on some important properties of the overhead factors. Then, the effect of granularity of the data that is divisible is considered in the analysis for the case of homogeneous networks. An integer approximation algorithm capable of generating integer values of the load fractions in time O(m), where m is the number of processors in the network, is proposed. We then show that the upper bound on the suboptimal solution generated by our algorithm lies within a radius given by the sum of the computation and communication delays. Several numerical examples are presented to illustrate the concepts     

异构机群系统上近似串匹配并行算法

基于可分负载理论的最优原则,在假定正文串分配顺序固定的前提下,考虑处理机节点具有不同计算速度、不同通信能力的情况,提出一种异构机群计算环境下的最优正文串分配策略,给出最优正文串分配的闭合解。对于节点具有不同计算速度、通信能力、存储容量的异构机群系统,建立正文串最优分配的线性规划模型。针对几种特殊情况讨论正文串的最优分配顺序。实验结果表明,与平均分配正文串策略以及按照从处理机能力分配正文串策略相比,利用该策略进行近似串匹配并行处理所需时间分别缩短了10%~40%和5%~20%。     

关于WDM双环网络网络负荷的研究

针对WDM网络的结构特征,选择具有代表性的有向双环网络G（N;r,s）进行研究。给出一组同余方程,用于快速计算其L-型瓦图的四个参数。根据L-型瓦的结构,给出了计算有向双环网络的网络负荷公式。实验结果分析表明：有向双环网络的一个无限族中可能存在多个负荷平衡的网络。对于有向双环网络G（N;r,s）的任意一个无限族中,其网络负荷的分布呈轴对称图形。网络负荷存在上界和下界,负荷达到下界值的网络称为最优负荷网络。该研究成果对于设计最优双环网络和提高网络通信效率起到决定性的作用。     

Parallel eigenvalue calculation based on multiple shift–invert Lanczos and contour integral based spectral projection method

We discuss the possibility of using multiple shift–invert Lanczos and contour integral based spectral projection method to compute a relatively large number of eigenvalues of a large sparse and symmetric matrix on distributed memory parallel computers. The key to achieving high parallel efficiency in this type of computation is to divide the spectrum into several intervals in a way that leads to optimal use of computational resources. We discuss strategies for dividing the spectrum. Our strategies make use of an eigenvalue distribution profile that can be estimated through inertial counts and cubic spline fitting. Parallel sparse direct methods are used in both approaches. We use a simple cost model that describes the cost of computing k eigenvalues within a single interval in terms of the asymptotic cost of sparse matrix factorization and triangular substitutions. Several computational experiments are performed to demonstrate the effect of different spectrum division strategies on the overall performance of both multiple shift–invert Lanczos and the contour integral based method. We also show the parallel scalability of both approaches in the strong and weak scaling sense. In addition, we compare the performance of multiple shift–invert Lanczos and the contour integral based spectral projection method on a set of problems from density functional theory (DFT).     

Max–min fairness in multi-commodity flows

In this paper, we provide a study of Max–Min Fair (MMF) multi-commodity flows and focus on some of their applications to multi-commodity networks. We first present the theoretical background for the problem of MMF and recall its relations with lexicographic optimization as well as a polynomial approach for achieving leximin maximization. We next describe two applications to telecommunication networks, one on routing and the second on load-balancing. We provide some deeper theoretical analysis of MMF multi-commodity flows, show how to solve the lexicographically minimum load network problem for the link load functions most frequently used in telecommunication networks. Some computational results illustrate the behavior of the obtained solutions and the required CPU time for a range of random and well-dimensioned networks.     

Ten reasons to use divisible load theory

During the past decade, divisible load theory has become a powerful tool for modeling data-intensive computational problems. DLT emerged from a desire to create intelligent sensor networks, but most recent applications involve parallel and distributed computing. Like other linear mathematical models such as Markovian queuing theory and electric resistive circuit theory, DLT offers easy computation, a schematic language, and equivalent network element modeling. While it can incorporate stochastic features, the basic model does not make statistical assumptions, which can be the Achilles' heel of a performance evaluation model.     

Effects of node processing time on optimal load balancing in tree hierarchy network configurations

In this paper, optimal static load balancing in a tree hierarchy network that consists of a set of heterogeneous host computers is considered. It is formulated as a nonlinear optimization problem. By parametric analysis, we study the effects of the node processing time on the optimal link flow rate (i.e. the rate at which a node forwards jobs to other nodes for remote processing), the optimal node load (i.e. the rate at which jobs are processed at a node), and the optimal mean response time. We show that the entire network can be divided into several independent sub-tree networks with respect to the link flow rates and node loads. We find that the processing time of a node affects only the link flow rates and the loads of nodes which are in the same sub-tree network. Generally, an increase in the processing time of an arbitrary node causes an increase in the link flow rates of its ancestor nodes and itself, but causes a decrease in the link flow rates of its descendant nodes and its collateral nodes in the same sub-tree network. It also causes a decrease in the load of the node itself, but causes an increase in the loads of other nodes in the same sub-tree network. Furthermore, it causes an increase in the mean response time. By conducting numerical experiments, we find that the node processing time possesses a large influence on the system performance measures. Knowledge of the effects of node processing time is useful in designing networks or making a parametric adjustment to improve the system performance.     

Handling large-size discrete wavelet transform on network-based computing systems — parallelization via divisible load paradigm

The discrete wavelet transform (DWT) is a powerful signal processing tool, but comes with a considerable computation cost. In this paper, we consider the problem of parallelizing the DWT computation on loosely-coupled networked systems. We first systematically analyze the data dependencies among DWT computations, identify the partitionable portions and then by applying the divisible load theory (DLT), we derive a novel scheduling strategy to schedule DWT computation onto bus networks. Our study is first of its kind in the DLT literature to demonstrate handling a highly coupled recursive computational nature of this problem towards gaining a significant speed-up.     

An incentive-based distributed mechanism for scheduling divisible loads in tree networks

The underlying assumption of Divisible Load Scheduling (DLS) theory is that the processors composing the network are obedient, i.e., they do not “cheat” the scheduling algorithm. This assumption is unrealistic if the processors are owned by autonomous, self-interested organizations that have no a priori motivation for cooperation and they will manipulate the algorithm if it is beneficial to do so. In this paper, we address this issue by designing a distributed mechanism for scheduling divisible loads in tree networks, called DLS-T, which provides incentives to processors for reporting their true processing capacity and executing their assigned load at full processing capacity. We prove that the DLS-T mechanism computes the optimal allocation in an ex post Nash equilibrium. Finally, we simulate and study the mechanism under various network structures and processor parameters.