# Comprehensive Review on Divisible Load Theory: Concepts, Strategies, and Approaches

Authors: Shamsollah Ghanbari; Mohamed Othman
Journal: Mathematical Problems in Engineering
 (2014)

---

## Abstract

There is extensive literature concerning the divisible load theory. The divisible load theory is mainly applied for scheduling in the area of distributed computing. It is based on the fact that the load can be divided into some arbitrarily independent parts, in which each part can be processed independently by a processor. This paper reviews the literature concerning the divisible load theory, while focusing on the details of the basic concepts, approaches, strategies, typologies, and open problems.


---

## Body

## 1. Introduction

The first articles about the divisible load theory (DLT) were published in 1988 [1, 2]. Based on the DLT, the load can be partitioned into some arbitrary size, in which each part can be executed independently by a processor [3]. Some advantages of the DLT have been listed in [4]. In the past two decades the DLT has found a wide variety of applications in the area of parallel processing. During these two decades, many researchers have investigated various aspects of the DLT [1–131]. In this paper, we have classified the existing research and provided a survey on the DLT in which we focus on the concepts, strategies, approaches, applications, and open problems. The main objectives of this paper are to(i)
provide a comprehensive review of the literature;
(ii)
categorize the literature according to the typology of the research;
(iii)
explore the open problems in the field of the divisible load theory;
(iv)
summarize the existing research results for the different types of problem.


## 2. A Bird’s Eye Review on the Divisible Load Theory

The divisible load theory originated in 1988 [1, 2]. Five years later, a formal mathematical proof appeared [6], and closed forms for the divisible load theory under the bus and tree networks topologies were proposed [7]. Subsequently, the DLT model with start-up costs was proposed [28] and the effects of start-up delays on divisible load scheduling on bus networks were investigated [96]. A few years later, the model was examined concerning the processors with front-end properties [46].According to the literature, three main strategies have been applied on the DLT in order to improve the performance. Thefirst strategy is multi-installment processing, which was proposed for the first time in 1995 [13]. Multi-installment processing can reduce the scheduling time in the DLT [93]. Subsequently, multi-installment divisible load was improved by other researchers. Thesecond strategy is an adaptive strategy that estimates network parameter values using a probing technique. The adaptive model can also reduce the scheduling time. It was proposed in [119] for the first time. Subsequently, a genetic algorithm based method for the adaptive DLT was proposed [66]. A few years later, that work was improved and other adaptive algorithms, including ADLT, A
2
D
L
T, and IDLT, were proposed [65, 66, 68]. Thethird proposed strategy for improving the performance of the DLT was a multi-source divisible load which was proposed by [114, 115]. A few years later, multi-source DLT was developed in order to calculate closed form formulation [70]. Subsequently, multi-source divisible load was continued by the other researchers [52, 67, 114, 124].In the early part of 2002, a group of researchers proved that the DLT with limited memory is NP-hard problem [33, 35]. Subsequently, the DLT with finite-size buffers in the heterogeneous single level tree networks was investigated [30]. Simultaneously, the investigation was continued by analyzing the effects of finite-size buffers on the multi-installment divisible load [47]. Subsequently, the DLT with limited memory was investigated [56]. The investigation was continued by the application of limited memory on both in the multi-installment divisible load [93] and heterogeneous divisible load [100]. A few years later, the limitation of memory was comprehensively investigated [64]. We have found some intensive surveys on the DLT. Thefirst one is a technical review concerning the DLT, which includes models, approaches, performance analysis, applications, and concepts [42]. Thesecond survey explores open problems in the DLT [105]. Thethird survey categorizes the research concerning the DLT as well as its applications [106]. In addition, for further studies some comprehensive information concerning the DLT can be found in [17, 92, 112]. Table 1 indicates a brief list of topics in the divisible load area.Table 1
A brief list of studied topics in the area of divisible load theory.
Topics
Developer(s)
References
The DLT originated
Cheng, Agrawal
[1, 2]
Closed form for bus and tree
Robertazzi, Sameer, Hsiung
[6, 7]
Optimal condition for the DLT
Sohn, Robertazzi
[3]
Linear programming model for the DLT
Hillier, Robertazzi
[112, 131]
Multi-installment processing  of the DLT
Veeravalli, Ghose, mani
[13]
The DLT with finite-size buffers
Veeravalli, Li, Ko
[32]
The DLT with memory limitation
Drozdowski, Berlinska
[33, 35, 64]
The DLT applied for grid computing
Moges, Yu, Robertazzi
[70, 75]
The adaptive DLT
Ghose, Kim, Kim
[55, 119]
Cheat processors in the DLT
Carroll, Grosu
[62, 63]
The DLT with nonlinear cost
Tsun, Suresh, Kim, Robertazzi
[53, 71]
The DLT and Markov chain models
Moges, Robertazzi
[51, 118]
Multi-source/Multi-site
Moges, Veeravalli, Li, Min, Yu, Robertazzi
[52, 67][114, 115]
The real time DLT
Lin, Mamat, Lu
[58, 61, 108]
Time varying in the DLT
Sohn, Robertazzi
[16, 19]
Multi-criteria divisible load
Ghanbari, Othman
[77]
Complexity problem concerning the DLT
Yang, Casanova, Drozdowski, Berlinska
[64, 76]


## 3. Concepts of Divisible Load Theory

### 3.1.  Basic Definitions and Notations

Notation section indicates the basic notations in the divisible load theory.


### 3.2. Mathematical Model for the Divisible Load Theory

#### 3.2.1. Load Allocation in Single Level Tree (Star) Network Topology

In general the DLT assumes that the computation and communication can be divided into some parts of arbitrary sizes, and these parts can be independently processed in parallel. The DLT assumes that, initially, amountV of load is held by the originator p
0. A common assumption is that the originator does not conduct any computation. It only distributes the load into parts α
0
,
α
1
,
…
,
α
m to be processed on worker processors p
0
,
p
1
,
…
,
p
m. The condition for the optimal solution is that the processors stop processing at the same time; otherwise, the load could be transferred from busy to idle processors to improve the solution time [3]. The goal is to calculate α
0
,
α
1
,
…
,
α
m in the DLT timing equation. In general, the timing equations (i.e., closed form) for the DLT can be depicted as follows:
(1)
T
i
(
α
)
=
{
α
0
w
0
i
=
0
∑
j
=
1
i
‍
α
j
z
j
+
α
i
w
i
i
=
1,2
,
…
,
m
,
where α
0
+
α
1
+
⋯
+
α
m
=
V. Moreover, α
i can be calculated as the following equations:
(2)
α
i
=
k
i
α
i
-
1
,
k
j
=
w
j
-
1
z
j
+
w
j
,
α
0
=
V
1
+
∑
i
=
1
m
∏
j
=
1
i
k
j
.
In this case, we assume that the load is sequentially distributed and simultaneously executed. As a result, the load is distributed from a root node to one child at a time. A Gantt chart-like timing diagram for this case can be depicted as Figure 1(a), while Figure 1(b) indicates that the load is simultaneously distributed with the starting staggered. Therefore, the worker processors are connected to the root processor by direct communication links. In this case, after receiving all of its assigned fraction of the load, each processor begins computing immediately. A timing equation for this form can be found in [112]. Furthermore, the time equation and Gantt chart-like diagram for the other possible forms of distribution and execution in the DLT model can be found in [92, 112].Gantt chart-like timing diagrams for divisible load.
(a)
Gantt chart-like timing diagram for divisible load in single level tree network
(b)
Gantt chart-like timing diagram for divisible load in a bus network topology


#### 3.2.2. Load Allocation in Multi-Level Tree

In a multi-level tree, the load is distributed from top to bottom, passing through each level. The optimal solution is obtained by traversing the tree from bottom to top, replacing single level subtrees with single equivalent processors untilT is reduced to one processor, which is denoted by w
i
eq. The Gantt chart-like timing diagram for multi-level tree divisible load is depicted in Figure 2(a).Gantt chart-like timing diagrams for divisible load.
(a)
Gantt chart-like timing diagram for a multi-level tree network
(b)
Gantt chart-like diagram for multi-round divisible load [60]


#### 3.2.3. Other Topologies

Up until 1999, the closed form for the DLT with various topologies including hypercubes [14], arbitrary graphs [99], daisy chain networks [6, 100], two-dimensional meshes [24], and three-dimensional meshes [25] were proposed. Subsequently, a closed form for k-dimensional meshes was proposed [50].


## 3.1.  Basic Definitions and Notations

Notation section indicates the basic notations in the divisible load theory.


## 3.2. Mathematical Model for the Divisible Load Theory

### 3.2.1. Load Allocation in Single Level Tree (Star) Network Topology

In general the DLT assumes that the computation and communication can be divided into some parts of arbitrary sizes, and these parts can be independently processed in parallel. The DLT assumes that, initially, amountV of load is held by the originator p
0. A common assumption is that the originator does not conduct any computation. It only distributes the load into parts α
0
,
α
1
,
…
,
α
m to be processed on worker processors p
0
,
p
1
,
…
,
p
m. The condition for the optimal solution is that the processors stop processing at the same time; otherwise, the load could be transferred from busy to idle processors to improve the solution time [3]. The goal is to calculate α
0
,
α
1
,
…
,
α
m in the DLT timing equation. In general, the timing equations (i.e., closed form) for the DLT can be depicted as follows:
(1)
T
i
(
α
)
=
{
α
0
w
0
i
=
0
∑
j
=
1
i
‍
α
j
z
j
+
α
i
w
i
i
=
1,2
,
…
,
m
,
where α
0
+
α
1
+
⋯
+
α
m
=
V. Moreover, α
i can be calculated as the following equations:
(2)
α
i
=
k
i
α
i
-
1
,
k
j
=
w
j
-
1
z
j
+
w
j
,
α
0
=
V
1
+
∑
i
=
1
m
∏
j
=
1
i
k
j
.
In this case, we assume that the load is sequentially distributed and simultaneously executed. As a result, the load is distributed from a root node to one child at a time. A Gantt chart-like timing diagram for this case can be depicted as Figure 1(a), while Figure 1(b) indicates that the load is simultaneously distributed with the starting staggered. Therefore, the worker processors are connected to the root processor by direct communication links. In this case, after receiving all of its assigned fraction of the load, each processor begins computing immediately. A timing equation for this form can be found in [112]. Furthermore, the time equation and Gantt chart-like diagram for the other possible forms of distribution and execution in the DLT model can be found in [92, 112].Gantt chart-like timing diagrams for divisible load.
(a)
Gantt chart-like timing diagram for divisible load in single level tree network
(b)
Gantt chart-like timing diagram for divisible load in a bus network topology


### 3.2.2. Load Allocation in Multi-Level Tree

In a multi-level tree, the load is distributed from top to bottom, passing through each level. The optimal solution is obtained by traversing the tree from bottom to top, replacing single level subtrees with single equivalent processors untilT is reduced to one processor, which is denoted by w
i
eq. The Gantt chart-like timing diagram for multi-level tree divisible load is depicted in Figure 2(a).Gantt chart-like timing diagrams for divisible load.
(a)
Gantt chart-like timing diagram for a multi-level tree network
(b)
Gantt chart-like diagram for multi-round divisible load [60]


### 3.2.3. Other Topologies

Up until 1999, the closed form for the DLT with various topologies including hypercubes [14], arbitrary graphs [99], daisy chain networks [6, 100], two-dimensional meshes [24], and three-dimensional meshes [25] were proposed. Subsequently, a closed form for k-dimensional meshes was proposed [50].


## 3.2.1. Load Allocation in Single Level Tree (Star) Network Topology

In general the DLT assumes that the computation and communication can be divided into some parts of arbitrary sizes, and these parts can be independently processed in parallel. The DLT assumes that, initially, amountV of load is held by the originator p
0. A common assumption is that the originator does not conduct any computation. It only distributes the load into parts α
0
,
α
1
,
…
,
α
m to be processed on worker processors p
0
,
p
1
,
…
,
p
m. The condition for the optimal solution is that the processors stop processing at the same time; otherwise, the load could be transferred from busy to idle processors to improve the solution time [3]. The goal is to calculate α
0
,
α
1
,
…
,
α
m in the DLT timing equation. In general, the timing equations (i.e., closed form) for the DLT can be depicted as follows:
(1)
T
i
(
α
)
=
{
α
0
w
0
i
=
0
∑
j
=
1
i
‍
α
j
z
j
+
α
i
w
i
i
=
1,2
,
…
,
m
,
where α
0
+
α
1
+
⋯
+
α
m
=
V. Moreover, α
i can be calculated as the following equations:
(2)
α
i
=
k
i
α
i
-
1
,
k
j
=
w
j
-
1
z
j
+
w
j
,
α
0
=
V
1
+
∑
i
=
1
m
∏
j
=
1
i
k
j
.
In this case, we assume that the load is sequentially distributed and simultaneously executed. As a result, the load is distributed from a root node to one child at a time. A Gantt chart-like timing diagram for this case can be depicted as Figure 1(a), while Figure 1(b) indicates that the load is simultaneously distributed with the starting staggered. Therefore, the worker processors are connected to the root processor by direct communication links. In this case, after receiving all of its assigned fraction of the load, each processor begins computing immediately. A timing equation for this form can be found in [112]. Furthermore, the time equation and Gantt chart-like diagram for the other possible forms of distribution and execution in the DLT model can be found in [92, 112].Gantt chart-like timing diagrams for divisible load.
(a)
Gantt chart-like timing diagram for divisible load in single level tree network
(b)
Gantt chart-like timing diagram for divisible load in a bus network topology


## 3.2.2. Load Allocation in Multi-Level Tree

In a multi-level tree, the load is distributed from top to bottom, passing through each level. The optimal solution is obtained by traversing the tree from bottom to top, replacing single level subtrees with single equivalent processors untilT is reduced to one processor, which is denoted by w
i
eq. The Gantt chart-like timing diagram for multi-level tree divisible load is depicted in Figure 2(a).Gantt chart-like timing diagrams for divisible load.
(a)
Gantt chart-like timing diagram for a multi-level tree network
(b)
Gantt chart-like diagram for multi-round divisible load [60]


## 3.2.3. Other Topologies

Up until 1999, the closed form for the DLT with various topologies including hypercubes [14], arbitrary graphs [99], daisy chain networks [6, 100], two-dimensional meshes [24], and three-dimensional meshes [25] were proposed. Subsequently, a closed form for k-dimensional meshes was proposed [50].


## 4. Strategies

In this section, we explain some strategies that have been applied to the divisible load in order to improve the performance. According to the literature, there are three main strategies including multi-installment, adaptive, and multi-source.


### 4.1. Multi-Installment Divisible Load

Based on multi-installment (i.e., multi-round) processing, the load is sent to a processor in more than one chunk. Therefore, the processorp
1 will start execution earlier, and the whole processing time will be shorter. Multi-installment processing may reduce the scheduled length to 0.632 of the initial length [56, 92]. It also depends on the proper number of installments [60]. The first paper about multi-installment divisible load was published in 1995 [8, 13]. Subsequently, a closed form formula for multi-installment divisible load was proposed in [8, 13]. A few years later, the multi-installment DLT was developed by considering the communication start-up cost function [38]. A year later, the memory limitation in multi-installment was investigated [93]. Subsequently, the multi-installment divisible load method was improved on k-dimensional meshes [95]. According to researchers the multi-installment divisible load consists of two main forms including uniform multi-round (UMR) and robust-UMR (RUMR) [54]. In the recent research related to multi-installment divisible load a number of heuristics for the scheduling of multi-installment divisible loads were proposed [64]. The time Gantt chart-like diagram for multi-installment divisible load is shown in Figure 2(b). Moreover, Table 2 summarizes the research related to the multi-installment divisible load theory.Table 2
Important events in multi-installment divisible load scheduling.
Author(s)
Description/issues
Veeravalli et al. [8]
Multi-installment DLT originated
Veeravali et al. [13]
Closed form for multi-installment divisible load was propped
Wolniewicz [56]
Effects of multi-installment processing on the total finish time in divisible load scheduling
Yang and Casanova [54]
UMR and RUMR were classified
Drozdowksi and Wolniewicz [33], Yang et al. [76]
Complexity of multi-installment divisibleload was studied
Drozdowski and Lawenda [93]
Multi-installment DLT with limited memory
Berlińska and Drozdowski [64]
Heuristics for multi-installment divisible load


### 4.2. Adaptive Divisible Load Model

Initially, the adaptive strategy was introduced under the name of feedback strategy for divisible load allocation [119]. Adaptive divisible load scheduling requires less finish time than the other methods [55]. The basic adaptive load distribution strategy consists of two phases. In the first phase (probe phase), a small part of the load (probe installment) is partitioned and communicated to individual processing nodes. Each node sends back a communication task completion message when it finishes receiving its load fraction. The second phase is called the optimal load distribution phase [55]. Furthermore, three adaptive strategies for divisible load were proposed. The three proposed strategies are as follows:(i)
probing and delayed distribution (PDD) strategy;
(ii)
probing and continuous distribution (PCD) strategy;
(iii)
probing and selective distribution (PSD) strategy. Furthermore, closed form formulations for PDD, PCD, and PSD have been calculated and can be found in [55]. In addition, some useful conclusions concerning the adaptive divisible load can be found in [65, 66, 68].


### 4.3. Divisible Load with Multiple Sources/Sites

The basic idea about the divisible load scheduling was based on the fact that the load originated from a single (root) processor. In 1994, a multi-job divisible job on bus networks was proposed [9]. The results of that work indicated that a multi-job scheme outperforms a single-job scheme in terms of the total solution finish time. After that, the divisible load with multiple sources (i.e., multiple sites) was studied in [124] for the first time and developed in [52]. The last paper focused on multiple source grid scheduling with capacity limitations. A few years later, grid scheduling divisible loads from multiple sources using the linear programming method was investigated [115]. Subsequently, a close form for divisible load with multiple source was proposed [114]. Lastly, a closed form of divisible load with two sources was calculated [70]. That paper contains several open problems and new ideas for further research in the field of divisible load theory with multiple sources. More recently, the divisible load with multiple sites in multi-tree network was investigated [67]. Although the results of the related research show that multiple source approach in divisible load may reduce scheduling time [67], a formal proof has not yet been published about this problem. Hence, investigating a formal proof for the effects of multi-sources divisible load can be considered as an open problem in this field.


## 4.1. Multi-Installment Divisible Load

Based on multi-installment (i.e., multi-round) processing, the load is sent to a processor in more than one chunk. Therefore, the processorp
1 will start execution earlier, and the whole processing time will be shorter. Multi-installment processing may reduce the scheduled length to 0.632 of the initial length [56, 92]. It also depends on the proper number of installments [60]. The first paper about multi-installment divisible load was published in 1995 [8, 13]. Subsequently, a closed form formula for multi-installment divisible load was proposed in [8, 13]. A few years later, the multi-installment DLT was developed by considering the communication start-up cost function [38]. A year later, the memory limitation in multi-installment was investigated [93]. Subsequently, the multi-installment divisible load method was improved on k-dimensional meshes [95]. According to researchers the multi-installment divisible load consists of two main forms including uniform multi-round (UMR) and robust-UMR (RUMR) [54]. In the recent research related to multi-installment divisible load a number of heuristics for the scheduling of multi-installment divisible loads were proposed [64]. The time Gantt chart-like diagram for multi-installment divisible load is shown in Figure 2(b). Moreover, Table 2 summarizes the research related to the multi-installment divisible load theory.Table 2
Important events in multi-installment divisible load scheduling.
Author(s)
Description/issues
Veeravalli et al. [8]
Multi-installment DLT originated
Veeravali et al. [13]
Closed form for multi-installment divisible load was propped
Wolniewicz [56]
Effects of multi-installment processing on the total finish time in divisible load scheduling
Yang and Casanova [54]
UMR and RUMR were classified
Drozdowksi and Wolniewicz [33], Yang et al. [76]
Complexity of multi-installment divisibleload was studied
Drozdowski and Lawenda [93]
Multi-installment DLT with limited memory
Berlińska and Drozdowski [64]
Heuristics for multi-installment divisible load


## 4.2. Adaptive Divisible Load Model

Initially, the adaptive strategy was introduced under the name of feedback strategy for divisible load allocation [119]. Adaptive divisible load scheduling requires less finish time than the other methods [55]. The basic adaptive load distribution strategy consists of two phases. In the first phase (probe phase), a small part of the load (probe installment) is partitioned and communicated to individual processing nodes. Each node sends back a communication task completion message when it finishes receiving its load fraction. The second phase is called the optimal load distribution phase [55]. Furthermore, three adaptive strategies for divisible load were proposed. The three proposed strategies are as follows:(i)
probing and delayed distribution (PDD) strategy;
(ii)
probing and continuous distribution (PCD) strategy;
(iii)
probing and selective distribution (PSD) strategy. Furthermore, closed form formulations for PDD, PCD, and PSD have been calculated and can be found in [55]. In addition, some useful conclusions concerning the adaptive divisible load can be found in [65, 66, 68].


## 4.3. Divisible Load with Multiple Sources/Sites

The basic idea about the divisible load scheduling was based on the fact that the load originated from a single (root) processor. In 1994, a multi-job divisible job on bus networks was proposed [9]. The results of that work indicated that a multi-job scheme outperforms a single-job scheme in terms of the total solution finish time. After that, the divisible load with multiple sources (i.e., multiple sites) was studied in [124] for the first time and developed in [52]. The last paper focused on multiple source grid scheduling with capacity limitations. A few years later, grid scheduling divisible loads from multiple sources using the linear programming method was investigated [115]. Subsequently, a close form for divisible load with multiple source was proposed [114]. Lastly, a closed form of divisible load with two sources was calculated [70]. That paper contains several open problems and new ideas for further research in the field of divisible load theory with multiple sources. More recently, the divisible load with multiple sites in multi-tree network was investigated [67]. Although the results of the related research show that multiple source approach in divisible load may reduce scheduling time [67], a formal proof has not yet been published about this problem. Hence, investigating a formal proof for the effects of multi-sources divisible load can be considered as an open problem in this field.


## 5. Approaches

### 5.1.  Divisible Load Model and Markov Chain

The equivalence between various divisible loads and continuous time Markov chain models helps in understanding the behavior of divisible load. These equivalences were investigated by Moges and Robertazzi [51, 118]. In [118] the closed form for divisible load with various topologies using the Markov chain model was demonstrated. Figure 3 shows the equivalence of Markov model and DLS with single tree level topology.Figure 3
Morkov model for single level tree divisible load [118].


### 5.2. Linear Programming Approach in Divisible Load Scheduling

Linear programming is a traditional approach to solving optimization problems. It is easy to understand and simple in implementation. A linear programming model can be solved by various methods such as simplex and duality methods. There is a wide variety of software to solve a linear programming problem. Moreover, linear programming problem can be solved very fast. Fortunately, divisible load scheduling can be modeled as a linear programming problem. A simple form of divisible load scheduling has been modeled as linear programming in [112]. The complexity of this model in a simple form is Ω
(
n
). Generally, divisible load scheduling may be modeled as a more complex form of linear programming; for example, a linear programming model for multi-round divisible load scheduling with limited memory is very complicated. It can be solved by branch and bound method which is an NP-hard problem [64]. The various linear programming model for multi-installment divisible load can be found in [92, 131].


### 5.3. Nonlinear Divisible Load

The general assumption is that both the computation and communication in divisible load model are linear. A nonlinear model is also possible for a divisible load. The first nonlinear model was proposed in [112]. Subsequently, the nonlinear model of divisible load was developed by the researchers [53, 71]. The basic assumptions and definition of nonlinear divisible load, closed form for nonlinear divisible load, and Gantt chart-like timing diagram for nonlinear divisible load can be found in [71]. In general, a closed form for divisible load with nonlinear cost can be written as the following equation:
(3)
T
i
(
α
)
=
{
α
0
w
0
i
=
0
∑
j
=
1
i
‍
α
j
z
j
γ
+
α
i
w
i
θ
i
=
1,2
,
…
,
m
,
where α
0
+
α
1
+
⋯
+
α
m
=
V.


## 5.1.  Divisible Load Model and Markov Chain

The equivalence between various divisible loads and continuous time Markov chain models helps in understanding the behavior of divisible load. These equivalences were investigated by Moges and Robertazzi [51, 118]. In [118] the closed form for divisible load with various topologies using the Markov chain model was demonstrated. Figure 3 shows the equivalence of Markov model and DLS with single tree level topology.Figure 3
Morkov model for single level tree divisible load [118].


## 5.2. Linear Programming Approach in Divisible Load Scheduling

Linear programming is a traditional approach to solving optimization problems. It is easy to understand and simple in implementation. A linear programming model can be solved by various methods such as simplex and duality methods. There is a wide variety of software to solve a linear programming problem. Moreover, linear programming problem can be solved very fast. Fortunately, divisible load scheduling can be modeled as a linear programming problem. A simple form of divisible load scheduling has been modeled as linear programming in [112]. The complexity of this model in a simple form is Ω
(
n
). Generally, divisible load scheduling may be modeled as a more complex form of linear programming; for example, a linear programming model for multi-round divisible load scheduling with limited memory is very complicated. It can be solved by branch and bound method which is an NP-hard problem [64]. The various linear programming model for multi-installment divisible load can be found in [92, 131].


## 5.3. Nonlinear Divisible Load

The general assumption is that both the computation and communication in divisible load model are linear. A nonlinear model is also possible for a divisible load. The first nonlinear model was proposed in [112]. Subsequently, the nonlinear model of divisible load was developed by the researchers [53, 71]. The basic assumptions and definition of nonlinear divisible load, closed form for nonlinear divisible load, and Gantt chart-like timing diagram for nonlinear divisible load can be found in [71]. In general, a closed form for divisible load with nonlinear cost can be written as the following equation:
(3)
T
i
(
α
)
=
{
α
0
w
0
i
=
0
∑
j
=
1
i
‍
α
j
z
j
γ
+
α
i
w
i
θ
i
=
1,2
,
…
,
m
,
where α
0
+
α
1
+
⋯
+
α
m
=
V.


## 6. Issues and Challenges in Special Studies

This section mainly focuses on certain problems related to the features or limitations of processors or processing in divisible load scheduling.


### 6.1. Cheat Processors in the Divisible Load Model

The main idea of the processor cheating refers to misreporting and time varying problems, which were investigated in respect of divisible load scheduling in 1998 [63]. Subsequently, Carroll and Grosu focused on the application case of misreporting in the divisible load scheduling [62, 63]. They proposed a strategy proof mechanism for the divisible load scheduling under various topologies including the bus and multi-level tree network [62, 63, 102, 103]. However, the cheating problem may occur, if the processors execute their fraction of loads with different rate. Assume that p
0
,
p
1
,
…
,
p
m are m
+
1 processors in a divisible load scheduling model. We also assume that p
0 is the root processor and p
1
,
p
2
,
…
,
p
m are the worker processors. Consider that w
=
(
w
0
,
w
1
,
…
,
w
m
) and z
=
(
z
0
,
z
1
,
…
,
z
m
) denote the computation and communication rates for processors, respectively. In the first stage, the computation rates of processors are sent to the root processor. The root processor allocates α
=
(
α
0
,
α
1
,
…
,
α
m
) fraction of load for the processors. The DLT with cheat processors has been investigated in several works [62, 63, 102, 103] by Carroll and Grosu. They examined various network topologies including bus [63], chain [102, 103], and multi-level tree [62]. They considered p
1 as the cheating processor, since its position gives a great influence over the allocations. They investigated the effects of cheating on the makespan, system utility, and verification. They proved that when the worker processors in a divisible load model do not report their true computation rates, they cannot obtain optimal performance. Figures 4(a) and 4(b) indicate the effects of the cheat processor on the makespan.The effects of a cheat processor on the makespan.
(a)
p
1 is high cheat
(b)
p
1 is low cheat


### 6.2. Time Varying

Time varying models are the most challenging problems in the recent research on the divisible load theory. It is also an open problem in the field of divisible load theory. The time varying problem means that communication and computation speeds may change in time. Time varying was discussed for the first time in [19]. Analysis of time varying in a continuous and discrete time can be found in [16, 19, 92, 112]. A closed form formula for divisible load with a time varying system can be formulated by changing the DLT model. In this case, t
i
m
e may change from 0 to T, while T is considered as the total scheduling time. A simple form of time varying models in divisible load can be formulated as the following equation:
(4)
T
i
(
α
)
=
{
α
0
w
0
(
t
)
i
=
0
∑
j
=
1
i
‍
α
j
z
j
(
t
)
+
α
i
w
i
(
t
)
i
=
1,2
,
…
,
m
,
where α
0
+
α
1
+
⋯
+
α
m
=
V. Furthermore, some useful conclusions about time varying models concerning the DLT can be found in [112].


### 6.3. Memory Limitation in the Divisible Load Scheduling

Scheduling divisible load with limited memory buffers was first analyzed in [35]. Subsequently, a multi-installment processing of divisible loads in systems with limited memory was analyzed [64]. Some details about divisible load with the memory model and hierarchical memory model can be found in [93, 100]. Furthermore, some algorithms and heuristics about divisible load with limited memory were investigated in [64].


### 6.4. Multi-Criteria Approach

The existing divisible load scheduling algorithms do not consider any priority for processors to allocate a fraction of the load. In some situation, the fractions of load must be allocated based on some certain priorities. For example, when we have some limitations in resources and so on, we need to allocate fractions of load based on some priority. In this case, a multi-criteria divisible load scheduling algorithm would be very useful. In [77] a multi-criteria divisible load model has been proposed for the first time. However, a closed form formula under multi-criteria has not appeared and it is still considered to be an open problem.


## 6.1. Cheat Processors in the Divisible Load Model

The main idea of the processor cheating refers to misreporting and time varying problems, which were investigated in respect of divisible load scheduling in 1998 [63]. Subsequently, Carroll and Grosu focused on the application case of misreporting in the divisible load scheduling [62, 63]. They proposed a strategy proof mechanism for the divisible load scheduling under various topologies including the bus and multi-level tree network [62, 63, 102, 103]. However, the cheating problem may occur, if the processors execute their fraction of loads with different rate. Assume that p
0
,
p
1
,
…
,
p
m are m
+
1 processors in a divisible load scheduling model. We also assume that p
0 is the root processor and p
1
,
p
2
,
…
,
p
m are the worker processors. Consider that w
=
(
w
0
,
w
1
,
…
,
w
m
) and z
=
(
z
0
,
z
1
,
…
,
z
m
) denote the computation and communication rates for processors, respectively. In the first stage, the computation rates of processors are sent to the root processor. The root processor allocates α
=
(
α
0
,
α
1
,
…
,
α
m
) fraction of load for the processors. The DLT with cheat processors has been investigated in several works [62, 63, 102, 103] by Carroll and Grosu. They examined various network topologies including bus [63], chain [102, 103], and multi-level tree [62]. They considered p
1 as the cheating processor, since its position gives a great influence over the allocations. They investigated the effects of cheating on the makespan, system utility, and verification. They proved that when the worker processors in a divisible load model do not report their true computation rates, they cannot obtain optimal performance. Figures 4(a) and 4(b) indicate the effects of the cheat processor on the makespan.The effects of a cheat processor on the makespan.
(a)
p
1 is high cheat
(b)
p
1 is low cheat


## 6.2. Time Varying

Time varying models are the most challenging problems in the recent research on the divisible load theory. It is also an open problem in the field of divisible load theory. The time varying problem means that communication and computation speeds may change in time. Time varying was discussed for the first time in [19]. Analysis of time varying in a continuous and discrete time can be found in [16, 19, 92, 112]. A closed form formula for divisible load with a time varying system can be formulated by changing the DLT model. In this case, t
i
m
e may change from 0 to T, while T is considered as the total scheduling time. A simple form of time varying models in divisible load can be formulated as the following equation:
(4)
T
i
(
α
)
=
{
α
0
w
0
(
t
)
i
=
0
∑
j
=
1
i
‍
α
j
z
j
(
t
)
+
α
i
w
i
(
t
)
i
=
1,2
,
…
,
m
,
where α
0
+
α
1
+
⋯
+
α
m
=
V. Furthermore, some useful conclusions about time varying models concerning the DLT can be found in [112].


## 6.3. Memory Limitation in the Divisible Load Scheduling

Scheduling divisible load with limited memory buffers was first analyzed in [35]. Subsequently, a multi-installment processing of divisible loads in systems with limited memory was analyzed [64]. Some details about divisible load with the memory model and hierarchical memory model can be found in [93, 100]. Furthermore, some algorithms and heuristics about divisible load with limited memory were investigated in [64].


## 6.4. Multi-Criteria Approach

The existing divisible load scheduling algorithms do not consider any priority for processors to allocate a fraction of the load. In some situation, the fractions of load must be allocated based on some certain priorities. For example, when we have some limitations in resources and so on, we need to allocate fractions of load based on some priority. In this case, a multi-criteria divisible load scheduling algorithm would be very useful. In [77] a multi-criteria divisible load model has been proposed for the first time. However, a closed form formula under multi-criteria has not appeared and it is still considered to be an open problem.


## 7. Algorithms

There are various algorithms for solving the divisible load scheduling problem. The algorithms have different behaviors. It is clear that using a suitable algorithm helps us to solve the problem without wasting time. Table3 summarizes the algorithm applied for divisible load scheduling. In this section, we discuss the two main problems concerning the algorithms, including complexity and convergence.Table 3
Comparing the algorithm applied for divisible load scheduling.
Algorithm
Advantages
Disadvantages
Approach
Reference
CDLT, IDLT, and TDP
Flexible
Complexity
Programming
[124]
Tractable recursive linear equation
Convergence
Complexity
Mathematical
[112, 131]
Linear programming
Convergence
NP-hard
Mathematical
[112]
Branch and bound
No limitation
NP-hard
Mathematical
[64]
Greedy algorithm
Certainty
Np-hard
Heuristics
[20]
Genetic algorithm
Fast
Divergence
Evolutionaryheuristics
[68, 76]
Game theory
Truthful
Divergence
Heuristics
[62, 63]
Mixed integer linear programming
Certainty
Complexity
Mathematical
[76]


### 7.1. Complexity

The complexity of divisible load algorithms has been investigated by several researchers [64, 76, 92, 100]. In a general form of divisible load scheduling the problem can be formulated as a linear programming problem. A simple form of linear programming can be solved by classical methods, such as the simplex method. Although the simplex method is a linear method in nature [131], a divisible load scheduling algorithm would be NP-hard even in the one-round case [76]. However, according to [76] multi-installment divisible load scheduling is also NP-hard. In fact, divisible load algorithms by considering some limitations, such as memory, have more complexity than a normal case. For instance, using the branch and bound method for solving multi-installment with limited memory would be an NP-hard problem [118]. As a result, the complexity is still one of the most important open issues of divisible load scheduling algorithms.


### 7.2.  Convergence

Convergence is mainly considered in random heuristic based algorithms, for example, the genetic algorithm. However, the convergence issue in the genetic algorithm means that if too many operations are performed on a primary offspring, some offspring of the population cannot be produced. In general, a genetic algorithm based method may not be able to find optimum value in the DLT. There is a wide range of research that has been applied in the genetic algorithm concerning the DLT [68, 100, 125]. However, the existing research has not considered the convergence of the problem. Hence, it can be considered as an open problem in the area of genetic algorithms and divisible load scheduling.


## 7.1. Complexity

The complexity of divisible load algorithms has been investigated by several researchers [64, 76, 92, 100]. In a general form of divisible load scheduling the problem can be formulated as a linear programming problem. A simple form of linear programming can be solved by classical methods, such as the simplex method. Although the simplex method is a linear method in nature [131], a divisible load scheduling algorithm would be NP-hard even in the one-round case [76]. However, according to [76] multi-installment divisible load scheduling is also NP-hard. In fact, divisible load algorithms by considering some limitations, such as memory, have more complexity than a normal case. For instance, using the branch and bound method for solving multi-installment with limited memory would be an NP-hard problem [118]. As a result, the complexity is still one of the most important open issues of divisible load scheduling algorithms.


## 7.2.  Convergence

Convergence is mainly considered in random heuristic based algorithms, for example, the genetic algorithm. However, the convergence issue in the genetic algorithm means that if too many operations are performed on a primary offspring, some offspring of the population cannot be produced. In general, a genetic algorithm based method may not be able to find optimum value in the DLT. There is a wide range of research that has been applied in the genetic algorithm concerning the DLT [68, 100, 125]. However, the existing research has not considered the convergence of the problem. Hence, it can be considered as an open problem in the area of genetic algorithms and divisible load scheduling.


## 8. Applications and Open Problem

This section focuses on applications and open problems in the field of divisible load theory.


### 8.1. Applications of Divisible Load Theory

A wide range of applications has been reported for the DLT in the literature. In the following list, we have addressed the most important applications of DLT according to the research: large size matrix-vector [27], image and vision processing [37], pipelined communication [87, 122], wireless sensor networks and processing measurement data [10, 11, 120], sequence alignment [59], video and multimedia applications [29, 81], computer vision [29], large scale data file processing [116], data intensive applications [78], query processing in database systems [22], monetary cost optimization [121], efficient movie retrieval for network-based multimedia [42], grid computing [70, 75, 89], cloud computing [118], real-time computing [15, 39, 58, 61, 108, 110], flat file database [79], radar and infrared tracking [84], and multimedia and broadcasting [123]. More references for applications of divisible load scheduling can be found in [92, 105, 112].


### 8.2. Open Problems in Divisible Load Theory

The divisible load theory has high capabilities for application in homogeneous or heterogeneous environments. Our study shows that there are several important issues that still remain as open problems in the field of the divisible load theory. According to the literature, the following list refers to the main topics of open problems in the divisible load field study: reducing the number of variables in the linear programming model of divisible load [112]; analyzing the convergence of evolutionary algorithms such as genetic algorithms in divisible load [68, 100, 125]; investigating the complexity of algorithm [33, 76]; investigating the effects of cheat processors in the adaptive divisible load model [102, 103]; calculating a close form nonlinear divisible load model [53, 71]; applying the divisible load on the high performance computing, that is, cloud computing; investigating the effects of time varying problem on the divisible load model [16, 19, 92, 112]; investigating the relationship between the DLT and Markov chain [51, 118]; and investigating the closed form of the divisible load model with memory limitation [93, 100].


## 8.1. Applications of Divisible Load Theory

A wide range of applications has been reported for the DLT in the literature. In the following list, we have addressed the most important applications of DLT according to the research: large size matrix-vector [27], image and vision processing [37], pipelined communication [87, 122], wireless sensor networks and processing measurement data [10, 11, 120], sequence alignment [59], video and multimedia applications [29, 81], computer vision [29], large scale data file processing [116], data intensive applications [78], query processing in database systems [22], monetary cost optimization [121], efficient movie retrieval for network-based multimedia [42], grid computing [70, 75, 89], cloud computing [118], real-time computing [15, 39, 58, 61, 108, 110], flat file database [79], radar and infrared tracking [84], and multimedia and broadcasting [123]. More references for applications of divisible load scheduling can be found in [92, 105, 112].


## 8.2. Open Problems in Divisible Load Theory

The divisible load theory has high capabilities for application in homogeneous or heterogeneous environments. Our study shows that there are several important issues that still remain as open problems in the field of the divisible load theory. According to the literature, the following list refers to the main topics of open problems in the divisible load field study: reducing the number of variables in the linear programming model of divisible load [112]; analyzing the convergence of evolutionary algorithms such as genetic algorithms in divisible load [68, 100, 125]; investigating the complexity of algorithm [33, 76]; investigating the effects of cheat processors in the adaptive divisible load model [102, 103]; calculating a close form nonlinear divisible load model [53, 71]; applying the divisible load on the high performance computing, that is, cloud computing; investigating the effects of time varying problem on the divisible load model [16, 19, 92, 112]; investigating the relationship between the DLT and Markov chain [51, 118]; and investigating the closed form of the divisible load model with memory limitation [93, 100].


## 9. Comparison and Typology of the Existing Research

In this section, we have focused on the typology of the related research. According to ISI, IEEE, Springer, and Google Scholar about 200 scientific documents, including journal papers, conference papers, PhD theses, and books, are available in this field. However, we compared the number of citations based on the articles in [1–131]. The related documents cover over 5,812 citations from 1988 to 2013. We found that more than 20 subjects have the most citations in this field. We have classified these subjects into five main categories, including “development,” “strategies,” “approaches,” “applications,” and “others.” The five main groups and related subjects are listed in Table 4. We also compared the total numbers of papers based on the five research groups from 1988 to 2013. This is depicted in Figure 5(a). Moreover, the figure shows that “Development” has the highest number of papers from 1988 to 1997 and 2003 to 2007, while “Approaches” has the highest number of papers from 2008 to 2013. The figure also indicates that “Analysis” has the highest number of papers from 1998 to 2002. In addition, the figure illustrates that the highest number of papers was published between 2003 and 2007. Similarly, Figure 5(b) gives some information about the number of citations to the documents from 1988 to 2013. The figure indicates that the papers published from 1988 to 1997 and 2002 to 2007 in the category of “Developments” have the highest number of citations.Table 4
Typology of researches in divisible load scheduling.
Groups
Related topic(subjects)
The number of
papers
citations
Development
Foundations, closed form, topologies, …
32
2181
Strategies
Multi-installment, multi-site, and adaptive
27
709
Applications
Image processing, grid computing, real time, …
19
467
Approaches
Markov chain model, memory limitation, convergence, …
30
1117
Analysis
Algorithm, complexity, …
14
206
Others
Books, review papers, surveys, …
9
1132Comparison and typology of the researches.
(a)
The number of papers
(b)
The number of citations


## 10. Conclusion

The divisible load theory has found a wide range of applications in the area of distributed computing. There are several intensive researches in the field of divisible load scheduling that employ various strategies in their approach to the problem. This paper has provided a comprehensive review of the research related to the divisible load theory. Furthermore, we classified the papers according to the concepts, strategies, approaches, algorithms, and open problems. We also provided a list of applications and open problems in the related area. Finally, we compared the related research based on the typology of papers in the field of the divisible load theory.



---

*Source: 460354-2014-07-20.xml*