×

A new load distribution strategy for linear network with communication delays. (English) Zbl 1155.90344

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

MSC:

90B18 Communication networks in operations research
68M20 Performance evaluation, queueing, and scheduling in the context of computer systems

Software:

MPI
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] http://www.ee.sunysb.edu/tom/dlt.html.; http://www.ee.sunysb.edu/tom/dlt.html.
[2] Banini, C.; Beaumont, O.; Carter, L.; Ferrante, J.; Legrand, A.; Robert, Y., Scheduling strategies for masterslave tasking on heterogeneous processor platforms, IEEE Transactions on Parallel and Distributed Systems, 15, 4, 319-330 (2004)
[3] Barlas, D. G., 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, 9, 5, 429-441 (1998)
[4] Bataineh, S.; Robertazzi, T. G., Bus oriented load sharing for a network of sensor driven processors, IEEE Transactions on Systems Man Cybernetics, 21, 5, 1202-1205 (1991)
[5] Beaumont, O.; Legrand, A.; Robert, Y., The master-slave paradigm with heterogeneous processors, IEEE Transactions on Aerospace and Electronic Systems, 14, 9, 897-908 (2003)
[6] Bharadwaj, V.; Ghose, D.; Mani, V., Optimal sequencing and arrangement in distributed single-level tree networks with communication delays, IEEE Transactions on Parallel and Distributed Systems, 5, 9, 968-976 (1994)
[7] Bharadwaj, V.; Ghose, D.; Mani, V., An efficient load distribution strategy for a distributed linear network of processors with communication delays, Computer Mathematics with Applications, 29, 9, 95-112 (1995) · Zbl 0821.90044
[8] Bharadwaj, V.; Ghose, D.; Mani, V.; Robertazzi, T. G., Divisible Loads Scheduling in Parallel and Distributed Systems (1996), IEEE CS Press: IEEE CS Press Los Alamitos, CA
[9] Blazewicz, J.; Drozdowski, M., Scheduling divisible jobs on hypercubes, Parallel Computing, 21, 12, 1945-1956 (1995)
[10] Blazewicz, J.; Drozdowski, M., The performance limits of a two-dimensional network of load sharing processors, Foundations of Computing and Decision Sciences, 21, 1, 3-15 (1996) · Zbl 0860.68006
[11] Blazewicz, J.; Drozdowski, M.; Guinand, F.; Trystram, D., Scheduling a divisible task in a 2-dimensional mesh, Discrete Applied Mathematics, 94, 1-3, 35-50 (1999) · Zbl 0937.68012
[12] Cheng, Y. C.; Robertazzi, T. G., Distributed computation for a tree network with communication delay, IEEE Transactions on Aerospace and Electronic Systems, 26, 3, 511-516 (1990)
[13] Cheng, Y. C.; Robertazzi, T. G., Distributed computation with communication delay, IEEE Transactions on Aerospace and Electronic Systems, 24, 6, 700-712 (1998)
[14] Das, T. K.; Kim, H. J.; Maitra, S., Security evaluation of generalized patchwork algorithm from cryptanalytic viewpoint, Lecture Notes in Artificial Intelligence, 3681, 1, 1240-1247 (2005)
[15] Drozdowski, M., Selected Problems of Scheduling Tasks in Multiprocessor Computer Systems (1997), Wydawnictwa Politechniki Poznanskiej: Wydawnictwa Politechniki Poznanskiej Poznan, Poland
[16] Drozdowski, M.; Glazek, W., Scheduling divisible loads in a 3-dimensional mesh of processors, Parallel Computing, 25, 4, 381-404 (1999) · Zbl 1047.68520
[17] Ghose, D.; Mani, V., Distributed computation with communication delays: asymptotic performance analysis, Journal of Parallel and Distributed Computing, 23, 3, 293-305 (1994)
[18] Glazek, G., A multistage load distribution strategy for three-dimensional meshes, Cluster Computing, 6, 1, 31-39 (2003)
[19] Gropp, W.; Lusk, E.; Skjellum, A., Using MPI: Portable Parallel Programming with the Message-Passing Interface (1994), MIT Press
[20] Issue, S., Divisible load scheduling, Cluster Computing, 6, 1, 5-86 (2003)
[21] Jeng, J. F.; Sahni, S., Reconfigurable mesh algorithms for Hough Transform, Journal of Parallel and Distributed Computing, 20, 1, 69-74 (1994) · Zbl 0825.68398
[22] Lee, C.; Wang, Y. F.; Uecker, D.; Wang, Y., Image analysis for automated tracking in robot assisted endoscopic surgery, (Proceedings of 12th International Conference Pattern Recognition (1994))
[23] C. Lee, Y.F. Wang, T. Yang, Static global scheduling for optimal computer vision and image processing operations on distributed memory multiprocessors, Technical Report-TRC 9423, University of California, Santa Barbara, 1994.; C. Lee, Y.F. Wang, T. Yang, Static global scheduling for optimal computer vision and image processing operations on distributed memory multiprocessors, Technical Report-TRC 9423, University of California, Santa Barbara, 1994.
[24] Li, K., Parallel processing of divisible loads on partitionable static interconnection networks, Cluster Computing, 6, 1, 47-55 (2003)
[25] Mani, V., An equivalent network methodology for efficient utilization of front-ends in linear network, Cluster Computing, 6, 1, 57-62 (2003)
[26] F.A.P. Petitcolas, R.J. Anderson, K.M. G, Information hiding—a survey, IEE Proceedings of the Special Issue on Protection of Multimedia Content 87 (7) (1999) 1062-1078.; F.A.P. Petitcolas, R.J. Anderson, K.M. G, Information hiding—a survey, IEE Proceedings of the Special Issue on Protection of Multimedia Content 87 (7) (1999) 1062-1078.
[27] Robertazzi, T. G., Processor equivalence for daisy chain load sharing processors, IEEE Transactions on Aerospace and Electronic Systems, 29, 4, 1216-1221 (1993)
[28] Ruanaidh, J. J.K. O.; Dowling, W. J.; Boland, F. M., Watermarking digital images for copyright protection, IEE Proceedings of the Vision, Image and Signal Processing, 134, 4, 250-256 (1996)
[29] Sohn, J.; Robertazzi, T. G., Optimal divisible job load sharing on bus networks, IEEE Transactions on Aerospace and Electronic Systems, 32, 1, 34-40 (1996)
[30] Suresh, S.; Omkar, S. N.; Mani, V., Parallel implementation of backpropagation algorithm in networks of workstations, IEEE Transactions on Parallel and Distributed Systems, 16, 1, 24-34 (2004)
[31] Yeo, I.-K.; Kim, H. J., Generalized patchwork algorithm for image watermarking, ACM Multimedia Systems, 9, 1, 261-265 (2003)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.