×

Large matrix-vector products on distributed bus networks with communication delays using the divisible load paradigm: Performance analysis and simulation. (English) Zbl 0991.65042

Summary: We present a performance analysis and experimental simulation results on the problem of scheduling a divisible load on a bus network. In general, the computing requirement of a divisible load is CPU intensive and demands multiple processing nodes for efficient processing. We consider the problem of scheduling a very large matrix-vector product computation on a bus network consisting of a homogeneous set of processors. The experiment was conducted on a PC-based networking environment consisting of Pentium II machines arranged in a bus topology. We present a theoretical analysis and verify these findings on the experimental test-bed. We also developed a software support system with flexibility in terms of scalability of the network and the load size. We present a detailed discussion on the experimental results providing directions for possible future extensions of this work.

MSC:

65F30 Other matrix algorithms (MSC2010)
68M10 Network design and communication in computer systems
65Y20 Complexity and performance of numerical algorithms
68Q25 Analysis of algorithms and problem complexity
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] V. Bharadwaj, D. Ghose, V. Mani, T.G. Robertazzi, Scheduling Divisible Loads in Parallel and Distributed Systems, IEEE Computer Society Press, Los Alamitos, CA, 1996.; V. Bharadwaj, D. Ghose, V. Mani, T.G. Robertazzi, Scheduling Divisible Loads in Parallel and Distributed Systems, IEEE Computer Society Press, Los Alamitos, CA, 1996.
[2] M. Drozdowski, Selected Problems of Scheduling Tasks in Multiprocessor Computer Systems, Wydawnictwa Politechniki Poznanskiej (in English), Book No. 321, Poznan, Poland, 1997.; M. Drozdowski, Selected Problems of Scheduling Tasks in Multiprocessor Computer Systems, Wydawnictwa Politechniki Poznanskiej (in English), Book No. 321, Poznan, Poland, 1997.
[3] M.M. Eshaghian (Ed.), Heterogeneous Computing, Artech House, 1996.; M.M. Eshaghian (Ed.), Heterogeneous Computing, Artech House, 1996. · Zbl 0867.68041
[4] Cheng, Y. C.; Robertazzi, T. G., Distributed computation with communication delays, IEEE Trans. Aerospace Electron. Syst., 24, 700-712 (1988)
[5] Robertazzi, T. G., Processor equivalence for a linear Daisy chain of load sharing processors, IEEE Trans. Aerospace Electron. Syst., 29, 1216-1221 (1993)
[6] Sohn, J.; Robertazzi, T. G., Optimal divisible job load sharing on bus networks, IEEE Trans. Aerospace Electron. Syst., 32, 1, 34-40 (1996)
[7] Bataineh, S.; Hsiung, T.; Robertazzi, T. G., Closed-form solutions for bus and tree network of processors load sharing a divisible job, IEEE Trans. Comput., 43, 10, 1184-1196 (1994) · Zbl 1068.68606
[8] Bharadwaj, V.; Ghose, D.; Mani, V., Optimal sequencing and arrangement in distributed single-level networks with communication delays, IEEE Trans. Parallel Distributed Syst., 5, 968-976 (1994)
[9] G.D. Barlas, Collection-aware optimum sequencing of operations and closed-form solutions for the distribution of a divisible load on arbitrary processor trees, IEEE Trans. Parallel Distributed Syst. 9 (5) (1998) 429-441.; G.D. Barlas, Collection-aware optimum sequencing of operations and closed-form solutions for the distribution of a divisible load on arbitrary processor trees, IEEE Trans. Parallel Distributed Syst. 9 (5) (1998) 429-441.
[10] K. Li, Managing divisible loads in partitionable networks, in: J. Schaeffer, R. Unrau (Eds.), High Performance Computing Systems and Applications, Kluwer Academic Publishers, Dordrecht, 1998, pp. 217-228.; K. Li, Managing divisible loads in partitionable networks, in: J. Schaeffer, R. Unrau (Eds.), High Performance Computing Systems and Applications, Kluwer Academic Publishers, Dordrecht, 1998, pp. 217-228.
[11] X. Li, V. Bharadwaj, C.C. Ko, Scheduling divisible tasks on heterogeneous single-level tree networks with finite-size buffers, IEEE Trans. Aerospace Electron. Syst. 37 (2001), submitted for publication.; X. Li, V. Bharadwaj, C.C. Ko, Scheduling divisible tasks on heterogeneous single-level tree networks with finite-size buffers, IEEE Trans. Aerospace Electron. Syst. 37 (2001), submitted for publication.
[12] J. Sohn, T.G. Robertazzi, A Multi-Job Load Sharing Strategy for Divisible Jobs on Bus Networks, CEAS Technical Report 665, State University of New York at Stony Brook, 1993.; J. Sohn, T.G. Robertazzi, A Multi-Job Load Sharing Strategy for Divisible Jobs on Bus Networks, CEAS Technical Report 665, State University of New York at Stony Brook, 1993.
[13] E. Haddad, Real-time optimization of distributed load balancing, in: Proceedings of the Second Workshop on Parallel and Distributed Real-Time Systems, 1994.; E. Haddad, Real-time optimization of distributed load balancing, in: Proceedings of the Second Workshop on Parallel and Distributed Real-Time Systems, 1994.
[14] V. Bharadwaj, G.D. Barlas, Access Time Minimisation for Distributed Multimedia Applications, Special Issue in Multimedia Tools and Applications, Vol. 12, Issue 2/3, Kluwer Academic Publishers, Dordrecht, 2000, pp. 235-256.; V. Bharadwaj, G.D. Barlas, Access Time Minimisation for Distributed Multimedia Applications, Special Issue in Multimedia Tools and Applications, Vol. 12, Issue 2/3, Kluwer Academic Publishers, Dordrecht, 2000, pp. 235-256. · Zbl 1077.68942
[15] Ghose, D.; Kim, H. J., Load partitioning and trade-off study for large matrix-vector computations in multicast bus networks with communication delays, J. Parallel Distributed Comput., 55, 32-59 (1998) · Zbl 0929.68014
[16] Sahni, S.; Thanvantri, V., Performance metrics: keeping the focus on runtime, IEEE Parallel Distributed Technol., 4, 1, 43-56 (1996)
[17] D.P. Bertsekas, J.N. Tsitsiklis, Parallel and Distributed Computation: Numerical Methods, Prentice-Hall, Englewood Cliffs, NJ, 1989.; D.P. Bertsekas, J.N. Tsitsiklis, Parallel and Distributed Computation: Numerical Methods, Prentice-Hall, Englewood Cliffs, NJ, 1989.
[18] V. Bharadwaj, L. Xiaolin, C.C. Ko, On the influence of start-up costs in scheduling divisible loads on bus networks, IEEE Transactions on Parallel and Distributed Systems 11 (12) (2000) 1288-1305.; V. Bharadwaj, L. Xiaolin, C.C. Ko, On the influence of start-up costs in scheduling divisible loads on bus networks, IEEE Transactions on Parallel and Distributed Systems 11 (12) (2000) 1288-1305.
[19] V. Bharadwaj, L. Xiaolin, C.C. Ko, Efficient partitioning and scheduling of computer vision and image processing data on bus networks using divisible load analysis, Image and Vision Computing, Vol. 18, Elsevier, New York, 2000, pp. 919-938.; V. Bharadwaj, L. Xiaolin, C.C. Ko, Efficient partitioning and scheduling of computer vision and image processing data on bus networks using divisible load analysis, Image and Vision Computing, Vol. 18, Elsevier, New York, 2000, pp. 919-938.
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.