Divisible Load Scheduling:

Research To Date, October 6, 2015

This research is concerned with scheduling in parallel and distributed systems with divisible loads. A divisible load (job) is one that can be arbitrarily partitioned among the processors and links in a system. For instance, as an example one may have a very large linear data file of numbers that need to be summed. One can send parts of the file to different processors through an interconnection network. The processors compute intermediate sums which are returned to the originating processor for a final summation. This is similar in spirit to the Map Reduce paradigm. Divisible load theory allows one to find the optimal (in the sense of minimizing the makespan/solution time) fractions of load to distribute to processors and links in a scheduled fashion taking into account the scheduling policy, interconnection network used, processor and link speeds and computation and communication intensity.

Applications include parallel and distributed processor network scheduling, cloud computing, grid computing, data intensive computing and metacomputing. The approach is particularly suited to the processing of very large data files as in signal processing, image processing, experimental data processing, linear algebra computation, DNA sequencing, video and computer utility applications.

The methodology that has been developed to date is unique in that it is a linear and continuous one. Both computing time and channel transmission time are modeled linearly. Continuous time modeling is invoked as jobs can be arbitrarily partitioned. This leads to a very tractable overall model and in many cases recursive, linear or closed form solutions.

This new methodology allows a close examination of the integration of computation and communication in networked computing. In fact what has been developed is a robust analytical "calculus" for scheduling problems of networked computation.

Note: An early paper that examines divisible, continuous loads in the somewhat different context of job shop scheduling is E.J. Anderson, “A New Continuous Model for Job-Shop Scheduling,” International Journal of System Science, vol. 12, no. 12, 1981, pp. 1469-1475.

Divisible Load Scheduling Theory Books

(1) Bharadwaj, V., Ghose, D., Mani, V. and Robertazzi, T.G., Scheduling Divisible Loads in Parallel and Distributed Systems, IEEE Computer Society Press, Los Alamitos CA, Sept. 1996, 292 pages.

Erratum: The wrong figure has been inserted in Fig. 4.22. It should be Figure 4 of conference reference (2) below.

(2) Drozdowski, M., Selected Problems of Scheduling Tasks in Multiprocessor Computer Systems, Politechnika Poznanska, Book No. 321, Poznan, Poland, 1997.

This book is available in a postscript form (~8.8Mbytes) from the location: http://www.cs.put.poznan.pl/~maciejd/h.ps

(3) Robertazzi, T.G., Networks and Grids: Technology and Theory, Springer, 2007.

 

Contains a chapter on divisible load theory with end of chapter problems (solutions manual available from author).

 

(4) Drozdowski, M., Scheduling for Parallel Processing, Springer, 2009.

 

Contains an excellent and balanced survey chapter on divisible load theory.  An excellent book.

 

(5) Casanova, H., Legrand, A. and Robert, Y., Parallel Algorithms, CRC Press, 2009.

 

Contains interesting material on divisible load theory.  The book is an excellent tutorial on its topic.

 

Journal and Book Chapters Publications:

1988-1995:

(1) Cheng, Y.C. and Robertazzi, T.G., "Distributed Computation with Communication Delays", IEEE Transactions on Aerospace and Electronic Systems, Vol. 24, No. 6, Nov. 1988, pp. 700-712.

This paper provides the first discussion of the algebraic solution of divisible load scheduling. Erratum: Equation (23): z sub i's should be z sub i+1.

(2) Agrawal, R. and Jagadish, H.V., "Partitioning Techniques for Large Grained Paralleism", IEEE Transactions on Computers, Vol. 37, No. 12, Dec. 1988, pp. 1627-1634.

This paper provides the first discussion of the linear programming solution of divisible load scheduling.

(3) Cheng, Y.C. and Robertazzi, T.G., "Distributed Computation for a Tree Network with Communication Delays", IEEE Transactions on Aerospace and Electronic Systems, Vol. 26, No. 3, May 1990, pp. 511-516.

(4) Bataineh, S. and Robertazzi, T.G., "Bus Oriented Load Sharing for a Network of Sensor Driven Processors", special issue on Distributed Sensor Networks of the IEEE Transactions on Systems, Man and Cybernetics, Sept. 1991, Vol. 21, no.5, pp. 1202-1205.

(5) Bataineh, S. and T.G. Robertazzi, "Ultimate Performance Limits for Networks of Load Sharing Processors", Proceedings of the 1992 Conference on Information Sciences and Systems, Princeton N.J., March 1992, pp. 794-799. Journal Version in IEEE Transactions on Aerospace and Electronic Systems, October 1997, under the title "Performance Limits for Processor Networks with Divisible Jobs".

Errata in Conference Version: Horizontal axis on Fig. 15 should be labeled Z. Fig. 14 is with front-end and Fig. 15 is without front-end. Equation (2.7): first term in denominator is w.

(6) Robertazzi, T.G., "Processor Equivalence for a Linear Daisy Chain of Load Sharing Processors", IEEE Transactions on Aerospace and Electronic Systems, Vol. 29, No. 4, Oct. 1993, pp. 1216-1221.

(7) Sohn, J. and Robertazzi, T.G., "Optimal Load Sharing for a Divisible Job on a Bus Network", Proceedings of the 1993 Conference on Information Sciences and Systems, The Johns Hopkins University, Baltimore MD, March 1993, pp. 835-840. Journal version: IEEE Transactions on Aerospace & Electronic Systems Vol. 32, No. 1, Jan. 1996, pp. 34-40.

Presents an analytic proof for a bus network that for a minimal time solution all processors must stop computing at the same time. The case of processors with front-end sub-processors for communications off-loading appears in this paper. See (5) below for the case without front-end subprocessors.

(8) Bataineh, S., Hsiung, T., and Robertazzi, T.G., "Closed Form Solutions for Bus and Tree Networks of Processors Load Sharing a Divisible Job", 1993 International Conference on Parallel Processing, St. Charles, Ill., August 1993. Journal version in IEEE Transactions on Computers, Vol. 43, No. 10, Oct. 1994, pp. 1184-1196.

Presents closed form solutions for optimal load allocations and minimal finish time for tree networks with front-end sub-processors for communications off-loading.

(9) Mani, V. and Ghose, D., "Distributed Computation in a Linear Network: Closed-Form Solutions and Computational Techniques", IEEE Transactions on Aerospace & Electronic Systems, Vol. 30, No. 2, April 1994.

Examines a linear daisy chain environment and shows that when the load is distributed from the interior of the chain the finish time is the same whether the load is first distributed to the left or the right of the chain. The load distribution sequence is as in Robertazzi and Cheng (1988). Computational algorithms are included.

(10) Ghose, D. and Mani, V., "Distributed Computation with Communication Delays: Asymptotic Performance Analysis", Journal of Parallel and Distributed Computing, Vol. 23, 1994, pp. 293-305.

Presents asymptotic results for large numbers of processors and examines limitations in performance when adding processors.

(11) Bharadwaj, V., Ghose, D. and Mani, V., "Optimal Sequencing and Arrangement in Distributed Single-Level Tree Networks with Communication Delays", IEEE Transactions on Parallel and Distributed Systems, Vol. 5, No. 9, pp. Sept. 1994, pp. 968-976.

This paper investigates optimal load distribution sequences, and the optimal arrangement of links and processors, for cases in which the root may or may not be equipped with a front end processor for communications off loading.

(12) Bharadwaj, V., Ghose, D. and Mani, V., "An Efficient Load Distribution Strategy for a Distributed Linear Network of Processors with Communication Delays", Computer and Mathematics with Applications, Vol. 29, No. 9, May 1995, pp. 95-112.

Proposes and examines a new load distribution strategy for linear daisy chains of processors with front-end processors.

(13) Bharadwaj, V., Ghose, D. and Mani, V., "Multi-installment Load Distribution in Tree Networks with Delays", IEEE Transactions on Aerospace & Electronic Systems, Vol. 31, No. 2, April 1995, pp. 555-567.

Examines distributing load in "installments" in order to improve solution time.

(14) Bataineh, S. and Al-Ibrahim, M., "Effect of Fault Tolerance and Communication Delay on Response Time in Multiprocessor System with Bus Topology", Computer Communications, Vol. 17, No. 12, Dec. 1994, pp. 843-851.

(15) Bataineh, S. and Al-Asir, B., "An Efficient Scheduling Algorithm for Divisible and Indivisible Tasks in Loosely Coupled Multiprocessor Systems", Software Engineering Journal (A joint publication of the IEE and the British Computer Society), Jan. 1994.

(16) Kim, H.J., Jeon, T.B., and Lee, J.G., "An Optimal Load Distribution Algorithm for Elliptic Solver", in Advanced Computational and Design Techniques in Applied Electromagnetic Systems, S.-y. Hahn, editor, Elsevier Studies in Applied Electromagnetics in Materials, 6, 1995, pp. 215-218.

A study and algorithm for the case when data is equally partitioned.

(17) Sohn, J. and Robertazzi, T.G., "An Optimal Load Sharing Strategy for Divisible Jobs with Time-Varying Processor Speeds", Proceedings of the Eighth International (ISCA) Conference On Parallel and Distributed Computing Systems, Sept. 21-23 1995, Orlando, Florida, pp. 27-32. Journal version: IEEE Transactions on Aerospace and Electronic Systems, Vol. 34, No. 3, July 1998, pp. 907-923.

(18) Blazewicz, J. and Drozdowski, M., "Scheduling Divisible Jobs on Hypercubes", Parallel Computing, Vol. 21, 1995, 1945-1956.

1996-2000:

(19) Blazewicz, J. and Drozdowski, M., "The Performance Limits of a Two-Dimensional Network of Load Sharing Processors", Foundations of Computing and Decision Sciences, Vol. 21, No. 1, 1996, pp. 3-15.

(20) Kim, H.J., Jee, G.-I. and Lee, J.G., "Optimal Load Distribution for Tree Network Processors", IEEE Transactions on Aerospace and Electronic Systems, Vol. 32, No. 2, April 1996, pp. 607-612.

Optimal load distribution sequences for tree networks are investigated.

(21) Bharadwaj, V., Li, H.F. and Radhakrishnan, T., "Scheduling Divisible Loads in Bus Networks with Arbitrary Processor Release Times", Computers and Mathematics with Applications, Pergamon Press, Vol. 32, No. 7, 1996, pp. 57-77.

Here it is assumed that processors are only available at certain times known as "release times".

(22) Blazewicz, J. and Drozdowski, M., "Distributed Processing of Divisible Jobs with Communication Startup Costs", Discrete Applied Mathematics, Vol. 76, Issue 1-3, June 13, 1997, pp. 21-41. Also, conference version of same title at Second International Colloquium on Graphs and Optimization, Leukerbad, Switzerland, Aug. 1994.

(23) Bataineh, S. and Al-Ibrahim, M., "Load Management in Loosely Coupled Multiprocessor Systems", Dynamics and Control, Kluwer Academic Publishers, Boston, Vol. 8, 1998, pp. 107-116.

Using a combination of queueing and divisible load theory, bounds are found on the arrival rate of load as a function of system and load parameters.

(24) Sohn, J., Robertazzi, T.G. and Luryi, S., "Optimizing Computing Costs using Divisible Load Analysis", IEEE Transactions on Parallel and Distributed Systems, Vol. 9, No. 3, March 1998, pp. 225-234.

Computing cost is considered along with job finish time. Also related: US Patent No. 5,889,989 awarded to J. Sohn, T, Robertazzi and S. Luryi on March 30, 1999 and titled "Load Sharing Controller for Optimizing Monetary Cost". See US Patent and Trademarks Office patent website for details.

Errata: Pg. 228, 2nd column, 4th line in large equation, first term in parenthesis w sub j+1 should be w sub j+2.

(25) Piriyakumar, D.A.L. and Murthy C.S.R., "Distributed Computation for a Hypercube Network of Sensor-Driven Processors with Communication Delays Including Setup Time", IEEE Transactions on Systems, Man and Cybernetics-Part A: Systems and Humans, vol. 28, no. 2, March 1998, pp. 245-251.

Considers setup time and simultaneous use of links. Introduces concept of fractal hypercube.

(26) Barlas, G.D., "Collection Aware Optimum Sequencing of Operations and Closed Form Solutions for the Distribution of a Divisible Load on Arbitrary Processor Trees", IEEE Transactions on Parallel and Distributed Systems, vol. 9, no. 5, May 1998, pp. 429-441.

(27) Ghose, D. and Kim, H.J., "Load Partitioning and Trade-Off Study for Large Matrix Vector Computations in Multicast Bus Networks with Communication Delays", Journal of Parallel and Distributed Computing, vol. 54, 1998.

(28) Blazewicz, J., Drozdowski, M. and Markiewicz, M. "Divisible Task Scheduling - Concept and Verification", Parallel Computing, vol. 25, Jan. 1999, pp. 87-98.

(29) Drozdowski, M. and Glazek, W., "Scheduling Divisible Loads in a Three-Dimensional Mesh of Processors", Parallel Computing, Vol. 25, No. 4, April 1999, pp. 381-404.

Describes and analyses a family of recursive scheduling algorithms for a 3D mesh.

(30) Blazewicz, J., Drozdowski, M., Guinand, F, and Trystram, D., "Scheduling a Divisible Task in a 2-Dimensional Mesh", Discrete Applied Mathematics, May 1999, pg. 35.

(31) Al-Saideen, A.M. and Bataineh, S., "A heuristic algorithm for scheduling multiclasses of tasks in multiprocessor systems", International Journal of Computers and Applications, Jan. 1999.

The paper presents an algorithm for scheduling divisible and indivisible tasks in multiprocessor systems. In addition to applying both paradigms, the algorithm is proved to be better than all existing ones and its results are very close to optimal values.

(32) Li, K., "Managing Divisible Load on a Partionable Network", High Performance Computing Systems and Applications, J. Schaeffer, editor, Kluwer Academic Publishers, 1998, pp. 217-228.

(33) Bharadwaj, V., Li, X. and, Chung, K.C., "Design and Analysis of Load Distribution Strategies with Start-up Costs in Scheduling Divisible Loads on Distributed Networks", Accepted for publication in Mathematical and Computer Modelling, Pergamon Press, April 1999.

(34) Li, X., Bharadwaj, V. and Ko, C.C., "Optimal Divisible Task Scheduling on Single-Level Tree Networks with Finite Size Buffers", Accepted for publication in IEEE Transactions on Aerospace and Electronic Systems, February 2000.

(35) Blazewicz, J., Drozdowski, M. and Ecker, K., Management of Resources in Parallel Systems, in: Blazewicz, J., Ecker, K., Plateau, B. and Trystram D., Handbook on Parallel and Distributed Processing, Springer, Heidelberg, 2000, 263-341.

(36) Bharadwaj, V., Li, X. and Ko, C. C., "Efficient Partitioning and Scheduling of Computer Vision and Image Processing Data on Bus Networks using Divisible Load Analysis", Image and Vision Computing, Aug. 2000, v 18 n 11, pg. 919.

(37) Charcranoon, S., Robertazzi, T.G. and Luryi, S., "Parallel Processor Configuration Design with Processing/Transmission Costs", IEEE Transactions on Computers. vol. 49, no. 9, Sept. 2000, pp. 987-991.

(38) Han. C.-C., Shin, K.G. and Yun, S.K., "On Load Balancing in Multicomputer/Distributed Systems Equipped with Circuit or Cut-Through Switching Capability," IEEE Transactions on Computers, vol. 49, no. 9, Sept. 2000.

A case where excess load at overloaded nodes is divisible is considered.

(39) Li, X., Bharadwaj, V. and Ko, C.C., "Divisible Load Scheduling on Single Level Tree Networks with Buffer Constraints", IEEE Transactions on Aerospace and Electronic Systems. vol. 36, no. 4, Oct. 2000, pp. 1298-1308.

(40) Drozdowski, M. and Wolniewicz, "Experiments with Scheduling Divisible Tasks in Clusters of Workstations," in in Bode, A., Ludwig, T., Karl, W. and Wismueler, R., editors, EURO-Par-2000, Lecture Notes in Computer Science no. 1900, Springer-Verlag, 2000, pp.311-319.

(41) V. Bharadwaj, Xiaolin Li, and, Ko Chi Chung, "On the Influence of Start-up Costs in Scheduling Divisible Loads on Bus Networks", IEEE Transactions on Parallel and Distributed Systems, Vol. 11, No. 12, pp. 1288-1305, December 2000..

(42) Bharadwaj, V. and Viswanadham, N., "Sub-Optimal Solutions Using Integer Approximation Techniques for Scheduling Divisible Loads on Distributed Bus Networks", IEEE Transactions on Systems, Man, and Cybernetics: Part A, Vol. 30, No. 6, pp. 680-691, November 2000.

(43) Bharadwaj, V. and Barlas, G.D., “Access Time Minimization for Distributed Multimedia Applications,” Multimedia Tools and Applications, vol. 12, 2000, pp. 235-256.

2001-2005:

(44) Kong, C.S., Bharadwaj, V. and Ghose, D., "Large Matrix-Vector Products on Distributed Bus Networks with Communication Delays using the Divisible Load Paradigm: performance and simulation", Accepted for publication in Computers and Mathematics in Simulation, Elsevier Press, 58, (2001), pp. 71-92.

(45) Bharadwaj, V. and Barlas, G., "Efficient Scheduling Strategies for Processing Multiple Divisible Loads on Bus Networks", Accepted for publication in Journal of Parallel and Distributed Computing, Academic Press, July 2001.

(46) Xiaolin, L., Bharadwaj, V. and Ko, C.C., "Experimental study on processing divisible loads for large size image processing applications using PVM clusters", Accepted for publication in International Journal of Computers and Applications, ACTA Press, July 2001.

(47) Comino, N. and Narasimhan, L., "A Novel Data Distribution Technique for Host-Clent Type Parallel Applications," IEEE Transactions on Parallel and Distributed Applications, vol. 13, no. 2, Feb. 2002, pp. 97-110.

(48) Bharadwaj, V. and Barlas, G.D., “Efficient Strategies for Processing Multiple Divisible Loads on Bus Networks,” Journal of Parallel and Distributed Computation, no. 62, 2002, pp. 132-151.

(49) Bharadwaj V. and Ranganath, S., "Theoretical and Experimental Study of Large Size Image Processing Applications using Divisible Load Paradigm on Distributed Bus Networks," Image and Vision Computing, Elsevier Publishers, vol. 20, issues 13-14, Dec. 2002, pp. 917-936.

(50) Li, X., Veeravalli, B. and Ko, C.C., "Distributed Image Processing on a Network of Workstations," International Journal of Computers and Applications, ACTA Press, vol. 25, no. 2, 2003, pp. 1-10.

(51) Suresh, S., Mani, V. and Omkar, S.N., "The Effect of Start-up in Scheduling Divisible Loads on Bus Networks: An Alternate Approach," Computers and Matehmatics with Applications, vol. 46, no. 10, 2003, pp. 1545-1557.

(52) Li, K., "Speedup of Parallel Processing of Divisible Loads on k-Dimensional Meshes and Tori," The Computer Journal, vol. 46, no. 6, pp. 625-631.

(53) Li, K., "Improved Methods for Divisible Load Distribution on k-Dimensional Meshes using Pipelined Communications," IEEE Transactions on Parallel and Distributed Systems, vol. 14, no. 12, Dec. 2003, pp. 1250-1261.

(54) Yao, J. and Veeravalli, B., "Design and Performance Analysis of Divisible Load Scheduling Strategies on Arbitrary Graphs," Cluster Computing, vol. 7, no. 2, 2004, pp. 841-865.

(55) Veeravalli. B. and Yao, J., "Divisible Load Scheduling Strategies on Distributed Multi-level Tree Networks with Communication Delays and Buffer Constraints," Computer Communications, vol. 27, issue 1, Jan. 2004, pp. 93-110.

(56) Drozdowski, M. and Wolniewicz, P., "Out of Core Divisible Load Processing," IEEE Transactions on Parallel and Distributed Systems, vol. 14, no. 10, Oct. 2003, pp. 1048-xx.

(57) Charcranoon, S., Robertazzi, T.G., and Luryi, S., "Load Sequencing for a Parallel Processing Utility," Journal of Parallel and Distributed Computing, vol. 64, 2004, pp. 29-35.

(58) Veeravalli, B. and Min, W.H., "Scheduling Divisible Loads on Heterogeneous Linear Daisy Chain Networks with Arbitrary Processor Release Times," IEEE Transactions on Parallel and Distributed Systems, vol. 15, no. 3, March 2004, pp. 273-288.

(59) Banino, C., Beaumont, O., Carter, L., Ferrante, J., Legrand, A. and Robert, Y., "Scheduling Strategies for Master-Slave Tasking on Heterogeneous Processor Platforms," IEEE Transactions on Parallel and Distributed Systems," vol. 15, no. 4, April 2004, pp. 1-xx.

(60) Ko, K. and Robertazzi, T.G., "Equal Allocation Scheduling for Data Intensive Applications," IEEE Transactions on Aerospace and Electronic Systems, vol. 40, no. 2, April 2004, pp. 695-705.

(61) Hung, J.T. and Robertazzi, T.G., "Divisible Load Cut Through Switching in Sequential Tree Networks," IEEE Transactions on Aerospace and Electronic Systems, vol. 40, no. 3, July 2004, pp. 968-982.

(62) Drozdowski, M. and Wolniewicz, P., "Performance Limits of Divisible Load Processing in Systems with Limited Communication Buffers," Journal of Parallel and Distributed Computing, vol. 64, no. 8, 2004, pp. 960-973.

(63) Beaumont, O., Casanova, H., Legrand, A., Robert, Y. and Yang, Y., "Scheduling Divisible Loads on Star and Tree Networks: Results and Open Problems," IEEE Transactions on Parallel and Distributed Systems, vol. 16, no. 3, March 2005, pp. 207-218.

(64) P. Li, B. Veeravalli and A.A. Kassim, "Design and Implementation of Parallel Video Encoding Strategies using Divisible Load Analysis," to appear in IEEE Transactions on Circuits and Systems for Video technology (CSVT), vol. 15, no. 9, Sept. 2005, pp. 1098-1112.

(65) G. Barlas and B. Veeravalli, "Quantized Load Distribution for Tree and Bus-connected Processors," Parallel Computing, vol. 30, no. 7, July 2004, pp. 841-865.

(66) Veeravalli, B., "Design and Performance Analysis of Heuristic Load Balancing Strategies for Processing Divisible Loads on Ethernet Clusters," International Journal of Computers and Applications, ACTA Press, vol. 27, no. 2, 2005, pp. 97-107.

(67) S. Suresh, S.N. Omkar and V. Mani, "Parallel Implementation of Back-Propagation Algorithm in Network of Workstations," IEEE Transactions on Parallel and Distributed Systems, vol. 16, no. 1, 2005, pp. 23-34.

This paper uses the DLT concept to partition a neural network into sub-networks to reduce the training time.

(68) Ghose, D. and Kim, H.J., “Computing BLAS Level-2 Operations on Workstation Clusters using the Divisible Load Paradigm,” Mathematical and Computing Modeling, vol. 41, no. 1, Jan. 2005, pp. 49-70.  

(69) Suresh, S., Mani, V., Omkar, S.N. and Kim, H.J., "A New Load Distribution Strategy for Linear Network of Communicating Processors," Electronic Letters, Feb. 2005.

(70) Barlas, G.D., “VoD on Steroids: Optimized Content Delivery using Distributed Video Servers over Best-Effort Internet,” Journal of Parallel and Distributed Computing, vol. 65, no. 9, Sept. 2005, pp. 1057-1071. 

(71) D. Ghose, H. J. Kim and T. H. Kim, "Adaptive Divisible Load Scheduling Strategies for Workstation Clusters with Unknown Network Resources," IEEE Transactions on Parallel and Distributed Systems, vol. 16, no. 10, Oct. 2005.

(72) Barlas, G.D. and Veeravalli, B., “Optimized Distributed Delivery of Continuous-Media Documents over Unreliable Communication Links,” IEEE Transactions on Parallel and Distributed Systems, vol. 16, no. 10, Oct. 2005. 

(73) Yang, Y., Raadt, K.v.d. and Casanova, H., "Multiround Algorithms for Scheduling Divisible Loads," IEEE Transcations on Parallel and Distributed Systems, vol. 16, no. 11, Nov. 2005, pp. 1092-1102.

(74) S.M. Bataineh, "Towards Analytical Solution to Task Allocation, Processor Assignment, and Performance Evaluation of Network of Processors," Journal of Parallel and Distributed Computing, vol. 65, 2005, pp. 29-47.

(75) Wong H.M. and B. Veeravalli, "Aligning Biological Sequences on Distributed Bus Networks: A Divisible Load Scheduling Approach," IEEE Transactiosn on Information Technology in BioMedicine, vol. 9, no. 4, Dec. 2005, pp. 489-501.

(76) Suresh, S., Mani, V., Omkar, S.N. and Kim, H.J., "Parallel Video Processing using Divisible Load Scheduling Paradigm," to appear in Korean Journal of Broadcast Engineering.

(77) Suresh, S., Mani, V., Omkar, S.N. and Kim, H.J., "An Equivalent Network for Divisible Load Scheduling in Non-Blocking Mode of Communication," to appear in Computers and Mathematics with Applications.

(78) Wong, H.M., Bharadwaj, V. and Gerassimos, B., "Design and Performance Evaluation of Load Distribution Strategies for Multiple Divisible Loads on Heterogeneous Linear Daisy Chain Networks," Journal of Parallel and Distributed Computing, vol. 65, 2005, pp. 1558-1577.

(79) Drozdowski and Lawenda, M., "The Combinatorics in Divisible Load Scheduling," Foundations of Computing and Decision Sciences, vol. 30, no. 4, 2005, pp. 297-308.

(80) Drozdowski, M. and Lawenda, M., "On Optimum Multi-installment Divisible Load Processing," in J.C. Cunha, P.D. Medeiros (eds.) Euro-Par 2005 Parallel Processing, Lecture Notes in Computer Science 3648, Springer, 231-240.

(81) Drozdowski, M. and Lawenda, M., "Multi-installment Divisible Load Processing in Heterogenous Systems with Limited Memory," to appear Lecture Notes in Computer Science 3911, Springer (Proceedings of PPAM 2005).

(82) Yamamoto, H., Tsuru, M. and Oie., "Parallel Transferable Uniform Multi-Round Algorithm for Achieving Minimum Application Turnaround Times for Divisible Workload," Lecture Notes in Computer Science 3726, Springer, 2005, pp. 817-828.

Cluster Computing Special Issue Jan. 2003, Vol. 6, No. 1:

Special Issue of the journal Cluster Computing on Divisible Load Scheduling, D. Ghose and T. Robertazzi, editors. Publisher: Kluwer Academic Publishers.

(83) V. Bharadwaj, D. Ghose, T. G. Robertazzi, "A New Paradigm for Load Scheduling in Distributed Systems", in special issue of Cluster Computing on Divisible Load Scheduling, Kluwer Academic Publishers, Vol. 6, No. 1, Jan. 2003, pp. 7-18.

(84) M. Drozdowski and P. Wolniewicz, "Divisible Load Scheduling in Systems with Limited Memory," in special issue of Cluster Computing on Divisible Load Scheduling, Kluwer Academic Publishers, Vol. 6, No. 1, Jan. 2003, pp. 19-30.

(85) W. Glazek, "A Multistage Load Distribution Strategy for Three Dimensional Meshes," in special issue of Cluster Computing on Divisible Load Scheduling, Kluwer Academic Publishers, Vol. 6, No. 1, Jan. 2003, pp. 31-40.

(86) H.-J. Kim, "A Novel Optimal Load Distribution Algorithm for Divisible Loads," in special issue of Cluster Computing on Divisible Load Scheduling, Kluwer Academic Publishers, Vol. 6, No. 1, Jan. 2003, pp. 41-46.

(87) K. Li, "Parallel Processing of Divisible Loads on Partitionable Static Interconnection Networks," in special issue of Cluster Computing on Divisible Load Scheduling, Kluwer Academic Publishers, Vol. 6, No. 1, Jan. 2003, pp. 47-56.

(88) V. Mani, "An Equivalent Tree Network Methodology for Efficient Utilization of Front-Ends in Linear Networks," in special issue of Cluster Computing on Divisible Load Scheduling, Kluwer Academic Publishers, Vol. 6, No. 1, Jan. 2003, pp. 57-62.

(89) V. Bharadwaj and G. Barlas, "Scheduling Divisible Loads with Processor Release Times and Finite Size Buffer Capacity Constraints," in special issue of Cluster Computing on Divisible Load Scheduling, Kluwer Academic Publishers, Vol. 6, No. 1, Jan. 2003, pp. 63-74.

(90) E. Balafoutis, M. Paterakis, P. Triantafillou, G. Nerjes, P. Muth and G. Weikum, "Clustered Scheduling Algorithms for Mixed Media Disk Workloads in a Multimedia Server," in special issue of Cluster Computing on Divisible Load Scheduling, Kluwer Academic Publishers, Vol. 6, No. 1, Jan. 2003, pp. 75-86.

2006-2010:

(91) Moges, M. and Robertazzi, T.G., "Wireless Sensor Networks: Scheduling for Measurement and Data Reporting," IEEE Transactions on Aerospace and Electronic Systems, vol. 42, no. 1, Jan. 2006, pp. 327-340.

(92) Drozdowski, M. and Lawenda, M., "Scheduling Multiple Divisible Loads," The International Journal of High Performance Computing Applications, vol. 20, no. 1, spring 2006, pp. 19-30.

(93) Drozdowski, M. and Wolniewicz, P., "Optimum Divisible Load Scheduling on Heterogeneous Stars with Limited Memory," European Journal of Operational Research, vol. 172, issue 2, July 2006, pp. 545-559.

(94) Moges, M. and Robertazzi, T.G., "Divisible Load Scheduling and Markov Chain Models," Computers and Mathematics with Applications, vol. 52, 2006, pp. 1529-1542.

(95) Zeng, Z. and Veeravalli, B., "Distributed Scheduling Strategy for Divisible Loads on Arbitrarily Configured Distributed Networks using Load Balancing via Virtuial Routing," Journal of Parallel and Distributed Computing, vol. 66, 2006, pp. 1404-1418.

(96) Gonzalez-Velez, H., "Self-Adaptive Skeletal Task Farm for Computational Grids," Parallel Computing, vol. 7-8, Sept. 2006, pp. 479-490.

(97) Ghose, D. and Kim, H.J., “A Generalized Linear Programming Based Approach to Optimal Divisible Load Scheduling [book chapter] in Distributed Computing and Internet Technology (Eds. S.K. Madria et. al.), Lecture Notes in Computer Science, Springer Verlag, Berlin, Germany, LNCS 4317, 2006, pp. 235-248. 

(98) Yamamoto, H., Tsuru, M. and Oie, “A Parallel Transferable Uniform Multi-Round Algorithm in Heterogeneous Distributed Computing Environment", Lecture Notes in Computer Science 4208, Springer, 2006, pp. 51-60.

(99) Viswanathan, S., Veeravalli, B., and Robertazzi, T.G., "Resource Aware Distributed Scheduling Strategies for Large-Scale Computational Cluster/Grid Systems," IEEE Transactions on Parallel and Distributed Systems, vol. 18, no. 10, Oct. 2007, pp. 1450-1461.

(100) Chang, Y.-K., Wu, J.-H., Chen, C.-Y. and Chu, C.P., "Improved Methods for Divisible Load Distribution on k-Dimensional Meshes using Multi-Installment," IEEE Transactions on Parallel and Distributed Systems, vol. 18, no. 11, Nov. 2007.

(101) England, D., Veeravalli, B. and Weissman, J., "A Robust Spanning Tree Topology for Data Collection and Dissemination in Distributed Environments," IEEE Transcations on Parallel and Distributed Systems, vol. 18, no. 5, 2007, pp. 608-620.

(101) Jia, J., Bharadwaj, V. and Ghose, D., "Adaptive Load Distribution Strategies for Divisible Load Processing on Resource Unaware Multilevel Tree Networks," IEEE Transactions on Computers, vol. 56, no. 7, 2007, pp. 999-1005.

(102) Ping, D.L.H., Veeravalli, B. and Bader, D., "On the Design of High-Performance Algorithms for Aligning Multiple Protein Sequences in Mesh-Based Multiprocessor Architectures," Journal of Parallel and Distributed Computing, vol. 67, no. 9, 2007, pp. 1007-1017.

(103) Loc, N.T. and Elnaffar, S., "A Dynamic Scheduling Algorithm for Divisible Loads in Grid Environments," Journal of Communications, vol. 2, no. 4,, June 2007, pp. 57-64.

(104) Bataineh, S., "Divisible Load Distribution in a Network of Processors," Journal of Interconnection Networks (JOIN), vol. 9, issue 1/2, March and June 2008, pp. 31-51.

(105) Ko, K. and Robertazzi, T.G., "Signature Search Time Evaluation in Flat File Databases," IEEE Transactions on Aerospace and Electronic Systems, vol. 44, no. 2, April 2008, pp. 493-502.

(106) Hung, J.T. and Robertazzi, T.G., "Scheduling Nonlinear Computational Loads", IEEE Transactions on Aerospace and Electronic Systems, expected publication: July 2008.

(107) Ghatpande, A., Nakazato, H., Beaumont, O. and Watanabe, H., "SPORT: An Algorithm for Divisible Load Scheduling with Result Collection on Heterogeneous Systems," IEICE Transactions on Communications, 2008, E91-B(8): pp. 2571-2588.

(108) Barlas, G.D. and El-Fakih, K., “A GA-Based Movie-on-Demand Platform using Multiple Distributed Servers,” Multimedia Tools and Applications, vol. 40, no. 3, Dec. 2008, pp. 361-383. 

(109) Chin, T.T., Veeravalli, B. and Jia, J., "Handling Large-Size Discrete Wavelet Transform on Network-Based Computing Systems: Parallelization via Divisible Load Paradigm," Journal of Parallel and Distributed Computing, vol. 69, no. 2, Feb. 2009, pp. 143-152.

(110) Xiaolin, L. and Veeravalli, B., "A Processor-Set Partitioning and Data Distribution Algorithm for Handling Divisible Loads from Multiple Sites in Single-Level Tree Networks," to appear in Cluster Computing, 2009.

(111) Moges, M.A. and Robertazzi, T.G., "Grid Scheduling Divisible Loads from Two Sources," Computers and Mathematics with Applications, vol. 58, 2009, pp. 1081-1092.

(112) Berlinska, J., Drozdowski, M. and Lawenda, M., "Experimental Study of Scheduling with Memory Constraints using Hybrid Methods," Journal of Computational and Applied Mathematics, vol. 232, 2009, pp. 638-654.

(113) Gonzalez-Velez, H. and Cole, M., "Adaptive Statistical Scheduling of Divisble Workloads in Heterogeneous Systems," Journal of Scheduling, 2009.

(114) Drozdowski, M., “Energy Considerations for Divisible Load Processing,” Lecture Notes in Computer Science, LNCS 6068, 2010, pp. 92-101, in R. Wyrzykowski, J. Dongarra, K. Karczewski, J. Wasniewski (eds.), Proceedings of the 8th International Conference PPAM 2009, part II.

(115) Shokripour, M. and Othman, M.,“Categorizing DLT researches and its applications,” European Journal of Scientific Research, vol. 37, no. 3, 2009, pp. 496–515.

(116) Shokripour, A. and Othman, M., “A review on divisible load theory applications”, MASAUM Journal of Reviews and Surveys (MJRS), vol. 1, no. 2, 2009, pp. 146–153.

(117)  Berlinska, J. and Drozdowski, M., “Heuristics for Multi-Round Divisible Loads Scheduling with Limited Memory,” Parallel Computing, vol. 26, 2010, pp. 199-211. 

(118) Drozdowski, M. and Wielebski, L., "Isoefficiency Maps for Divisible Computations," IEEE Transactions on Parallel and Distributed Systems, vol. 21, no. 6, June 2010, pp. 872-880.

(119) Suresh, S., Run, C., Kim H.J. and Robertazzi, T.G., “Scheduling Second Order Computational Load in Master-Slave Paradigm,” accepted by IEEE Transactions on Aerospace and Electronic Systems in 2010.

(120) Barlas, G.D., “An Analytical Approach to Optimizing Parallel Image Registration,” IEEE Transactions on Parallel and Distributed Systems, vol. 21, no. 8, Aug. 2010, pp. 1074-1088.

(121) Barlas, G.D., “Optimizing Image Content-Based Query Applications over High Latency Communication Media using Single and Multiple Port Communications ,” Scalable Computing: Practice and Experience (Springer), special issue on “Parallel, Distributed and Network-based Processing: An Application Perspective,” vol. 11, no. 3,  Dec. 2010, pp. 221-237.

(122) Abdullah, M., Othman, M., Ibrahim, H. and Subramaniam, S., “Optimal Workload Allocation Model for Scheduling Divisible Data Grid Applications,” Future Generation Computer Systems, vol. 26, 2010, pp. 971-978.

(123) Shokripour, A., Othman, M. and Ibrahim, H., “A new algorithm for divisible load scheduling with different processor available times”, Lecture Notes in Computer Science, Springer Berlin/Heidelberg, vol. 5990, 2010, pp. 221-230.

2011-2015:

(124) Berlinska, J. and Drozdowski, M., “Scheduling Divisible MapReduce Computations,” Journal of Parallel and Distributed Computing, vol. 71, no. 3, March 2011, pp. 450-459. 

(125) Robertazzi, T.G., “A Product Form Solution for Tree Networks with Divisible Loads,” Parallel Processing Letters, vol. 21, no. 1, March 2011, pp. 13-20.

(126) Li, K., “New Divisible Load Distribution Methods using Pipelined Communication Techniques on Tree and Pyramid Networks,” IEEE Transactions on Aerospace and Electronic Systems, vol. 47, no. 2, April 2011, pp. 806-819.

(127) Choi, K. and Robertazzi, T.G., “An Exhaustive Approach to Release Time Aware Divisible Load Scheduling,” International Journal on Internet and Distributed Computing Systems, accepted in May 2011. 

(128) Shokripour, A., Othman, M., Ibrahim, H. and Subramaniam, S., "A New Method for Scheduling Divisible Data on a Heterogeneous Two-Levels Hierarchical System", Procedia Computer Science, vol. 4, 2011, pp. 2196-2205.

(129) Shokripour, A., Othman, M., Ibrahim, H. and Subramaniam, S., “A Method for Scheduling Heterogeneous Multi-Installment Systems”, Lecture Notes in Artificial Intelligence, Springer Berlin/Heidelberg, vol. 6592, 2011, pp. 221-230.

(130) Shokripour, A., Othman, M., Ibrahim, H. and Subramaniam, S., “A New Method for Job Scheduling in a Non-Dedicated Heterogeneous System”, Procedia Computer Science, Elsevier, vol. 3, 2011, pp. 271-275.

(131) Gamboa, C.F. and Robertazzi, T.G., “Simple Performance Bounds for Multicore and Parallel Channel Systems,” Parallel Processing Letters, vol. 21, no. 4, Dec 2011, pp. 439-459.

(132) Barlas, G., “Cluster-Based Optimized Parallel Video Transcoding,” Parallel Computing, vol. 38, March 2012, pp. 226-244.

(133) Shokripour, A., Othman, M., Ibrahim, H., Subramaniam, S., "New method for scheduling heterogeneous multi-installment systems”, Future Generation Computer Systems, vol 28, no. 8., 2012, pp. 1205-1216.

(134) Shi, H., Wang, W. and Kwok, N., “Energy Dependent Divisible Load Theory for Wireless Sensor Network Workload Allocation,” Mathematical Problems in Engineering, Hindawi, 2012.

(135) Ismail, L. and Zhang, L., “Modeling and Performance Analysis to Predict the Behavior of a Divisible Load Application in a Cloud Computing Environment,” Algorithms, vol. 5., no. 2, 2012, pp. 289-303.

(136) Dai, L., Shen, Z., Chen, T, and Chang, Y., “Analysis and Modeling of Task Scheduling in Wireless Network Based on Divisible Load Theory,” International Journal on Communication Systems, 2012.

(137) Mamat, A., Lu, Y., Deogun, J. and Goddard S., “Efficient Real-Time Divisible Load Scheduling,” Journal of Parallel and Distributed Computing, vol. 72, no. 12, 2012, pp. 1603-1616.

(138) Iyer, G.N., Veeravalli, B. and Krishnamoorthy, S.G., “On Handling Large-Scale Polynomial Multiplication in Compute Cloud Environments using Divisible Load Paradigm,” IEEE Transactions on Aerospace and Electronic Systems, 201, pp. 820-831

(139) Drozdowksi, M., Marszalkowski, J.M and Marszalkowski, J., “Energy Trade-Offs Analysis using Equal-Energy Maps,” Future Generation Computer Systems, Elsevier, 2013.

(140) Hu, M. and Veeravalli, B., “Dynamic Scheduling of Hybrid Real-Time Tasks on Clusters,” IEEE Transactions on Computers, 2013.

(141) Shokripour, A., Othman, M., Ibrahim, H. and Subramaniam, S., “A New Method for Job Scheduling in Two-Levels Hierarchical Systems,” in Selemat, A., Nguyen, T. and Haron, H., (editors) Intelligent Information and Database Systems, Lecture Notes in Computer Science, vol. 7803, 2013, pp. 345-355.

(142) Hu, M. and Veeravalli, B., “Requirement-Aware Strategies for Scheduling Real-Time Divisible Loads on Clusters,” Journal of Parallel and Distributed Computing, vol. 73, no. 8, 2013, pp. 1083-1091.

(143) Wang, M., Wang, X., Meng, K, and Wang, Y., “New Model and Genetic Algorithm for Divisible Load Scheduling in Heterogeneous Distributed Systems,” International Journal of Pattern Recognition and Artificial Intelligence, vol. 27, no. 7, 2013.

(144) Shi, H., Wang, W., Kwok, N. and Chen, S., “Adaptive Indexed Divisible Load Theory for Wireless Sensor Network Workload Allocation,” International Journal of Distributed Sensor Networks, Hindawi Publishing Corp., 2013.

(145) Shakhlevich, N.V., “Scheduling Divisible Loads to Optimize the Computation Time and Cost,” in Altmann, J., Vanmechelen, K., and Rana, O.F. (editors), GECON 2013, Lecture Notes in Computer Science 8193, 2013, pp. 138-148.

(146) Murugesan, G. and Chellappan, C., “Multi-Source Task Scheduling in Grid Computing Environment using Linear Programming,” International Journal of Computer Science and Engineering, Inderscience Publishers, vol. 9, no. 1, 2014, pp. 80-85.

(147) Lin, W., Liang, C., Wang, J.Z. and Buyya, R., “Bandwidth-Aware Divisible Task Scheduling for Cloud Computing,” Software: Practice and Experience, Wiley, vol. 44, no. 2, 2014, pp. 163-174.

(148) Rosas, C., Sikora, A., Jorba, J., Moreno, A., Cesar, E., “Improving Performance on Data-Intensive Applications using a Load Balancing Methodology based on Divisible Load Theory,” International Journal of Parallel Programming, vol. 42, 2013, pp. 94-118.

(149) Ying, Z. and Robertazzi, T.G., “Signature Searching in a Networked Collection of Files,” IEEE Transaction in Parallel and Distributed Systems, vol. 29, no 5, May 2014, pp. 1339-1348.

It has been a pleasure compiling this list of world-wide research on divisible load scheduling theory over the years. However search engines such as Google Scholar have been become good enough and offer many features so for future additions to this list I would recommend using such resources.

Conference Proceedings Publications:

(1) Agrawal, R. and Jagadish, H.V., "Partitioning Technqiues for Large-Grained Parallelism", Proceedings of the Seventh Annual International Phoenix Conference on Computers and Communications, March 1988, pp. 31-38.

This is the first published work on divisible load scheduling and the first to discuss it solution via linear programming.

(2) Cheng, Y.C. and Robertazzi, T.G., "Communication and Computation Tradeoffs in a Linear Network of Sensors", Proceedings of the 1988 Computer Networking Symposium, Washington D.C., April 1988, pp. 152-161.

The first paper to discuss the algebraic solution of divisible load scheduling models. Erratum: Due to a software bug, the performance curves in the conference version are incorrect. The Aerospace Transactions version (see above, journal (1)) contains correct performance curves.

(3) Sohn, J. and Robertazzi, T.G., "A Multi-Job Load Sharing Strategy for Divisible Jobs on Bus Networks", Proceedings of the 1994 Conference on Information Sciences and Systems, Princeton University, Princeton NJ, March 1994.

Erratum: In architecture 3, the timing diagram shows that processors can not transmit and compute at the same time but they can receive and compute at the same time.

(4) Haddad, E., "Communication Protocol for Optimal Redistribution of Divisible Load in Distributed Real-time Systems", Proceedings of the ISMM International Conference on Intelligent Information Management Systems, Washington DC, June 1-3 1994, pp. 39-42.

(5) Haddad, E., "Runtime Reallocation of Divisible Load under Processor Execution Deadlines", Proceedings of the Third Workshop on Parallel and Distributed Real-Time Systems, IEEE Computer Society Press, Santa Barbara, April 1995.

(6) Haddad, E., "Optimal Load Sharing in Dynamically Heterogeneous Systems", Proceedings of the Seventh Annual IEEE Symposium on Parallel and Distributed Processing, San Antonio TX, Oct. 95.

(7) Glazek, W., "Scheduling Divisible Loads on a Chain of Processors", Proceedings of the International Conference on Principles of Distributed Systems (OPODIS '97), Editions Hermes, Paris, Dec. 1997, pp. 123-136.

Deals with load distribution originating from the center of a linear network. Proposes and evaluates a new round robin scheme of distribution in which processors receive data in rounds.

(8) Glazek, W., "Scheduling Divisible Jobs in a Hypercube with Restricted Communication Capabilities, manuscript, June 1998; short version appeared under title "A Greedy Algorithm for Processing a Divisible Load on a Hypercube" in Proceedings of the International Conference on Parallel Computing in Electrical Engineering PARELEC'98, Bialystok, Poland, September 1998, pp. 185-188.

Proposes two scheduling algorithms for a hypercube with restricted communication capabilities: the first algorithm follows a Nearest Layer First rule, the second uses a Largest Layer First approach.

(9) Barlas, G. and Bharadwaj, V., "Theoretical and Practical aspects of multi-installment distribution for the processing of multiple divisible loads on bus networks," Proceedings of ICCI 2000, September 2000.

(10) Li Xiaolin, Bharadwaj, V. and Ko, C.C., "Divisible Load Scheduling on a Hypercube Cluster with Finite-size Buffers and Granularity Constraints", In the Proceedings of the IEEE/ACM International Symposium on Cluster Computing and the Grid (CCGrid 2001), May 2001, Brisbane, Australia.

(11) Rosenberg, A.L., "Sharing Partitionable Workload in Heterogeneous NOWs: Greedier is Not Better," Proc. of IEEE International Conference on Cluster Computing, Newport Beach CA, 2001. pp. 124-131.

Expresses divisible load solution equations in matrix form (see journal papers here (3), (7) and (21) for related work). Uses divisible load modeling to address two network of workstation (NOW) problems: (a) NOW-Rental Problem: rent a NOW for as short a time as possible to complete some given amount of work (b) NOW-Exploitation Probelm: accomplish as much work as possible on a NOW during some given amount of time.

(12) Hung, J.T., Kim, H.J., and Robertazzi, T.G., "Scalable Scheduling in Parallel Processors," Proceedings of the 2002 Conference on Information Sciences and Systems, Princeton University, Princeton NJ, March 2002 (paper available on the Brokered E-Commerce page on this site).

Shows that if one distributes load simultaneously over all links (as proposed by Murthy and Piriyakumar in journal paper (24) above), speedup is scalable.

(13) Ghose, D., "A Feedback Strategy for Load Allocation in Workstation Clusters with Unknown Network Resource Capabilities using the DLT Paradigm," Proceedings of the International Conference on Parallel and Distributed Processing Techniques and Applications (PDPTA'02), Las Vegas, Nevada, USA June 2002, Vol. 1, pp. 425-428.

Proposes sensing available processing effort and adaptively distributing load on this basis.

(14) Ghose, D. and Kim, H.-J., "Matrix-vector Product Computations on Multicast Bus-Oriented Workstation Clusters," Proceedings of the International Conference on Parallel and Distributed Processing Techniques and Applications (PDPTA'02), Las Vegas, Nevada, USA June 2002, Vol. 1, pp. 436-441.

(15) Beaumont, O., Carter, L., Ferrante, J., Legrand A. and Robert, Y., "Bandwidth-Centric Allocation of Independent Tasks on Heterogeneous Platforms," Proceedings of the International Parallel and Distributed Processing Symposium (IPDPS'02), June 2002.

Discusses allocating a large number of independent, equal sized tasks in a heterogeneous grid. Specifically, examines the key role of bandwidth limitations in a tree network, overlapping of computation and communication and equivalent elements for networks.

(16) Yang. Y. and Casanova, H., "UMR: A Multi-Round Algorithm for Scheduling Divisible Workloads," Proceedings of the International Parallel and Distributed Processing Symposium (IPDPS'03), Nice, France, April 2003.

Defines a multi-round (multi-installment) problem involving fixed size rounds and finds an optimal number of rounds and an optimal load distribution algorithm. An extensive simulation section is included.

(17) Kreaseck, B., Carter, L., Casanova, H. and Ferrante, J., "Autonomous Protocols for Bandwidth-Centric Scheduling of Independent-task Applications," Proceedings of the International Parallel and Distributed Processing Symposium (IPDPS'03), Nice, France, April 2003.

(18) Dutot, P.-F., "Divisible Load on Heterogeneous Linear Array," Proceedings of the International Parallel and Distributed Processing Symposium (IPDPS'03), Nice, France, April 2003.

Discusses optimizing load distribution order. A summary of the concept appears on the web (search Pierre-Francois Dutot under Google, for instance).

(19) Adler, M., Gong, Y. and Rosenberg, A.L., "Optimal Sharing of Bags of Tasks in Heterogeneous Clusters," Proc. of ACM SPAA'03, June 2003.

(20) Wong, H.M., Yu, D., Veeravalli, B. and Robertazzi, T.G., "Data Intensive Grid Scheduling: Multiple Sources with Capacity Constraints," Proc. of the IASTED International Conference on Parallel and Distributed Computing and Systems (PDCS 2003), Nov. 2003 (paper available on the Brokered E-Commerce page on this site).

(21) Kim, S. and Weissman, J.B., "A Genetic Algorithm Based Approach for Scheduling Decomposable Data Grid Applications," 2004 International Conference on Parallel Processing (ICPP'04), Montreal, Quebec, Canada, Aug. 2004.

(22) L. Marchal, Y. Yang, H. Casanova and Y. Robert, "A Realistic Network/Application Model for Scheduling Divisible Loads on Large-Scale Platforms," International Parallel and Distributed Processing Symposium (IPDPS 2005), 2005.

(23) Thysebaert, P., De Leenheer, M., Volckaert, B. et. al., "Using Divisible Load Theory to Dimension Optical Transport Networks for Grid Excess Load Handling," Proc. of the International Conference on Autonomic and Autonomous Systems and International Conference on Networking and Service, ICAS/ICNS, Oct. 2005.

(24) Thysebaert, P., Volckaert, B., De Leenheer, M., et. al., "Resource Partitioning Algorithms in a Programmable Service Grid Architecture," ICCS 2005, Lecture Notes in Computer Science, Springer, LNCS Vol. 3516.

(25) Thysebaert, P., De Turck, F., Dhoedt, B. and Demeester, P., "Using Divisible Load Theory to Dimension Optical Transport Networks Computational Grids," Proc. of Optical Fibre Communication Conference, OFC, March. 2005.

(26) Barlas, G.D., “Simulating the Effects of Packet Loss on the Delivery of Continuous Media by Multiple Distributed Servers,” Proceedings of ICMSAO’05, Sharjah, U.A.E., 2005.

(27) Barlas, G.D., “A Taxonomy and DLT Based Analysis of Cluster-based Video Trans/Encoding,” 14th Euromicro Conference on Parallel, Distributed and Network-based Processing (PDIVM 2006), Montbeliard, France, 2006, pp. 388-395.

(28) Lin, X., Lu, Y., Deogun, J. and Goddard, S., "Real-Time Divisible Load Scheduling for Cluster Computing," 13th IEEE Real-Time/Embedded Technology and Applications Symposium (RTAS), Bellevue WA, April 2007.

(29) Lin, X., Lu, Y., Deogun, J. and Goddard, S., "Real-Time Divisible Load Scheduling with Different Processor Available Times," International Conference on Parallel Processing (ICPP), XiAn, China, Sept. 2007.

(30) Lin, X., Lu, Y., Deogun, J. and Goddard, S., "Enhanced Real-Time Divisible Load Scheduling with Different Processor Available Times", 14th International Conference on High Performance Computing (HiPC), Goa, India, Dec. 2007.

(31) Carroll, T.E. and Grosu, D., "Divisible Load Scheduling: An Approach using Coalitional Games," Sixth International Symposium on Parallel and Distributed Computing (ISPDC'07), July 2007, pp 36.

(32) Hu, J. and Klefstad, R., "Scheduling Multiple Divisible and Indiviisble Tasks on Bus Networks," 2007 IEEE International Conference on Cluster Computing, 2007, pp. 222-230.

(33) Suda, R., "Divisible Load Scheduling with Improved Asymptotic Optimality," 2008 IEEE International Conference on Cluster Computing, 2008, pp. 262-267.

(34) Beaumont, O., Bonichon, N. and Eyraud-Dubois, L., “Scheduling Divisible Workloads on Heterogeneous Platforms under Bounded Multi-Port Model,” Heterogeneity in Computing Workshop in IEEE Symposium on Parallel and Distributed Processing, 2008, Miami FL, USA. 

(35) Barlas, G.D., El-Koussa, B. and Afrasiabi, M.-H., “Using a GPU-CPU Hybrid Platform for Image Restoration,” Proceedings of the 21st International Conference on Parallel and Distributed Computing and Communication Systems (PDCCS 2008), New Orleans, USA, pp. 82-87.   

(36) Shokripour, A. and Othman, M., "Categorizing Researches about DLT in Ten Groups," 2009 International Association of Computer Science and Information Technology Spring Conference, 2009, pp. 45-49.

(37) Shokripour, A. and Othman, M., "Survey on Divisible Load Theory and Its Applications," 2009 International Conference on Information Management and Engineering, 2009.

(38) Beaumont, O. and Rosenberg, A., “Link-Heterogeneity vs. Node-Heterogeneity in Clusters,” International Conference on High Performance Computing (HIPC), 2010, Goa, India.

(39) Shokripour, A. and Othman, M. and Ibrahim, H., “A Method for Scheduling Last Installment in a Heterogeneous Multi-Installment System”, IEEE International Conference on Computer Science and Information Technology (IEEE ICCSIT 2010), IEEE Computer Society, Chengdu, China, July 2010, pp. 714-718.

(40) Shokripour, A. and Othman, M., “Scheduling jobs in a heterogeneous system with unreliable network links by DLT”, International Conference on Communication Software and Networks (ICCSN 2010), IEEE Computer Society, Singapore, February 2010, pp. 68-72.

(41) Barlas, G.D., Hassan, A. and Al Jundi, Y., “An analytical Approach to the Design of Parallel Block Cipher Encryption/Decryption: A CPU/GPU Case Study,” Proceedings of PDP 2011, Aiya Napa, Cyprus, Feb. 2011, pp. 247-251.

(42) Beaumont, O., Larcheveque, H. and Marchal, L., “Non-Linear Divisible Loads: There is no Free Lunch,” 27th IEEE International Parallel and Distributed Processing Symposium, 2013.

(43) Balasubramaniam, M. and Ciorba, F.M., “Analyzing the Robustness of Scheduling Algorithms using Divisible Load Theory on Heterogenous Systems,” 2013 IEEE 12th International Symposium on Parallel and Distributed Computing, 2013, pp. 45-52.

(44) Abdullah, M. and Othman, M., “Cost-based Multi-QoS Job Scheduling using Divisible Load Theory in Cloud Computing,” International Conference on Computational Science, 2013.

(45) Berlinska, J. and Drozdowski, M., “Mitigating Partitioning Skew in MapReduce Computations,” Proceedings of the 6th Multidisciplinary International Scheduling Conference: Theory & Applications, Ghent 2013, pp. 80-90.

Technical Reports:

(1) Hsiung, T. and Robertazzi, T.G., "Performance Evaluation of Distributed Communication Systems for Load Balancing", SUNY at Stony Brook College of Engineering and Applied Science Technical Report 612, Dec. 17, 1991, available from T. Robertazzi.

A numerical study evaluating different architectures.

(2) Bharadwaj, V., Ghose, D. and Mani, V., "Design and Analysis of Load Distribution Strategies for Infinitely Divisible Loads in Distributed Processing Networks with Communication Delays", Dept. of Aerospace Engineering, Indian Institute of Science, Bangalore India Technical Report 422/GC/01-92, Oct. 1992.

Contains journal references above (8) thru (12).

(3) Bharadwaj, V., Ghose, D., and Mani, V., "A Study of Optimality Conditions for Load Distribution in Tree Networks with Communication Delays", Dept. of Aerospace Engineering, Indian Institute of Science, Bangalore, India, Technical Report 423/GI/02-92, Dec. 1992.

Conditions for the optimality of load distribution in single level tree networks are examined.

(4) Charcranoon, S. and Robertazzi T.G., "Heuristic Algorithms for Optimizing Computing and Communication Costs for Networked Computer Utilities", SUNY at Stony Brook College of Engineering and Applied Science Technical Report No. 767, Nov. 16, 1998.

(5) Drozdowski, M. and Wolniewicz, P., "On the Complexity of Divisible Job Scheduling," Technical Report RA-001/2001, Poznan University of Technology. Available as pkzipped PostScript (43kB): www.cs.put.poznan.pl/mdrozdowski/rapIIn/div_mNPh.zip

(6) Beaumont, O., Legrand, A. and Robert Y., "Static Scheduling Strategies for Heterogeneous Systems," Research Report No. 2002-29, Laboratoire de l'Informatique du Parallelisme, Ecole Normale Superieure de Lyon, Lyon France.

Surveys three scheduling approaches (minimum makespan, divisible load and steady-state) and their limitations.

(7) Beaumont, O., Legrand, A. and Robert Y., "Optimal Algorithms for Scheduling Divisible Workloads on Heterogeneous Systems," Research Report No. 2002-36, Laboratoire de l'Informatique du Parallelisme, Ecole Normale Superieure de Lyon, Lyon France.

Studies a multi-round algorithm and demonstrates its asymptotic optimality. An extensive simulation section is included.

(8) Beaumont, O. and Marchal, L., “A Novel Form for Scheduling Work Preserving Malleable Tasks and Its Applications,” INRIA Technical Report 00564056.  Available online at http://hal.inria.fr/inria-00564056. 

Patents:

(1) Robertazzi, T.G., Luryi, S.and Sohn, J., Load Sharing Controller for Optimizing Monetary Cost, US Patent 5,889,989, issues March 30, 1999.

(2) Robertazzi, T.G., Luryi, S.and Charcranoon, S., Load Sharing Controller for Optimizing Resource Utilization Cost, US Patent 6,370,560, issued April 9, 2002.