The branch and bound algorithm improvement in divisible load scheduling with result collection on heterogeneous systems by new heuristic function

• Autorzy: Fard F. N. , Mohammadi S. , Parvizi P.
• Języki publikacji: EN

Abstrakty

EN

In this paper we propose a new heuristic function for branch and bound algorithm. By this function we can increase the efficiency of branch and bound algorithm. Divisible loads represent computations which can be arbitrarily divided into parts and performed independently parallel. The scheduling problem consists in distributing the load in a heterogeneous system taking into account communication and computation times, so that the whole processing time is as short as possible. Since our scheduling problem is computationally hard, we propose a branch & bound algorithm. By simulating and comparing results it is observed which this result produces better answers than other methods, it means that branch and bound algorithm have less total average of relative error percentage in the variety Heuristic functions.

Słowa kluczowe

EN

divisible load scheduling; heterogeneous systems; branch and bound algorithm

• Wydawca: Łukasiewicz Industrial Research Institute for Automation and Measurements PIAP
• Czasopismo: Journal of Automation Mobile Robotics and Intelligent Systems
• Rocznik: 2012
• Tom: Vol. 6, No. 3
• Strony: 47--50
• Opis fizyczny: Bibliogr. 22 poz., rys.

Twórcy

autor

Fard F. N.

autor

Mohammadi S.

autor

Parvizi P.

• Mechatronic Department Islamic Azad University – South Tehran Branch,Tehran, Iran,

Bibliografia

• [1] Bharadwaj V., Ghose D., Mani V., Robertazzi T.G., Scheduling Divisible Loads in Parallel And Distributed Systems, IEEE Computer Society Press, Los Alamitos CA, 1996.
• [2] Lee C.H., Shin K.G., “Optimal task assignment in homogeneous networks”, IEEE Trans. Parallel Distrib. Syst., vol. 8, no. 2, Feb. 1997, pp.119-129.
• [3] Barlas G.D., “Collection-aware optimum sequencing of operations and closed-form solutions for the distribution of divisible load on arbitrary processor trees”, IEEE Trans. Parallel Distrib. Syst., vol. 9, no. 5, May 1998, pp.429-441.
• [4] Agrawal R., Jagadish H.V., “Partitioning Techniques for Large-Grained Parallelism”, IEEE Transactions on Computers, vol. 37, no. 12, 1988, pp. 1627-1634.
• [5] Cheng Y.-C., Robertazzi T.G., “Distributed computation with communication delay”, IEEE Transactions on Aerospace and Electronic Systems, vol. 24, 1988, pp. 700-712.
• [6] Robertazzi T.G., “Ten reasons to use divisible load theory”, IEEE Computer, vol. 36, 2003, pp. 63–68.
• [7] Bharadwaj V., Ghose, D., Robertazzi, T. G., “Divisible Load Theory: A New Paradigm for Load Scheduling in Distributed Systems”, Cluster Computing, vol. 6, no. 1, Jan. 2003, pp. 7-17.
• [8] Jingxi J., Bharadwaj V., Ghose D., “Adaptive Load Distribution Strategies for Divisible Load Processing on Resource Unaware Multilevel Tree Networks”, IEEE Transactions on Computers, vol. 65, no. 7, 2007, pp. 99-1005.
• [9] Li X., Bharadwaj V., KO C. C., “Distributed Image Processing on a Network of Workstations”, International J. Computers and Applications, vol. 25, no. 2, 2003, pp. 1-10.
• [10] Blazewicz J., Drozdowski M., Markiewicz M., “Divisible Task Scheduling: Concept and Verification”, Parallel Computing, vol. 25, 1990, pp. 87-98.
• [11] Chan S., Bharadwaj V., Ghose D., “Large Matrix-Vector Products on Distributed Bus Networks with Communication Delays Using the Divisible Load Paradigm: Performance and Simulation”, Math. And Computers in Simulation, vol. 58, 2001, pp.71-92.
• [12] Altilar D., Paker Y., “Optimal Scheduling Algorithms for Communication Constrained Parallel Processing”. In: Proc. 8th Int’l Euro-Par Conf., 2002, pp. 197-206.
• [13] Bharadwaj V., Ghose D., Mani V., “Multi-installment Load Distribution in Tree Networks with Delays”, IEEE Transactions on Aerospace and Electronic Systems, vol. 31, 1995, pp. 555-567.
• [14] Li X., Bharadwaj V., Ko C. C., “Processing divisible loads on single-level tree networks with buffer constraints”, IEEE Transactions on Aerospace and Electronic Systems, vol. 36, 2000, pp. 1298-1308.
• [15] Drozdowski M., Wolniewicz P., “Optimum divisible load scheduling on heterogeneous stars with limited memory”, European Journal of Operational Research, vol. 172, 2006, pp. 545-559.
• [16] Rosenberg A. L., “Sharing Partitionable Workloads in Heterogeneous NOWs: Greedier Is not Better”, IEEE International Conf. on Cluster Computing, Newport Beach, CA, Oct. 2001, pp. 124-131.
• [17] Beaumont O., Marchal L., Rehn V., Robert Y., “FIFO Scheduling of Divisible Loads with Return Messages Under the One Port Model”. In: Proc. Heterogeneous Computing Workshop HCW’06, April 2006.
• [18] Ghatpande A., Nakazato, H., Watanabe, H., Beaumont, O., “Divisible Load Scheduling with Result Collection on Heterogeneous Systems”. In: Proc. Heterogeneous Computing Workshop (HCP 2008), April 2008.
• [19] Ghatpande A., Nakazato H., Beaumont O., Watanabe H., “SPORT: An Algorithm for Divisible Load Scheduling With Result Collection on Heterogeneous Systems”, IEICE Transactions on Communications, vol. E91-B, no. 8, August 2008.
• [20] Ghatpande A., Nakazato H., Beaumont O., Watanabe H., “Analysis of Divisible Load Scheduling with Result Collection on Heterogeneous Systems”, IEICE Transactions on Communications, vol. E91-B, no. 7, July 2008.
• [21] Suresh S., Mani V., Omkar S. N., Kim H. J., “Divisible Load Scheduling in Distributed Systems with Buffer Constraints: Genetic Algorithm and Linear Programming Approach”, International Journal of Parallel, Emergent and Distributed Systems, vol. 21, no. 5, Oct. 2006, pp. 303-321.
• [22] Vanderbei R. J., Linear Programming: Foundations and Extensions, 2nd Ed., International Series in Operations Research & Management, vol. 37, Kluwer Academic Publishers, 2001.