Abstract

Parallel and distributed computing systems are greatly affected by the structure of the underlying network topology and geometry. In this paper, a new method of parallel computing inspired by geometry is suggested. The Perfect Difference Network (PDN), which is based on perfect difference sets, is employed to develop an efficient parallel matrix multiplication algorithm. To this end, the geometry of the underlying architectures is considered to investigate the connection and communication between the processors. In this regard, it is shown that geometry plays an important role in parallel computing. The suggested algorithm is coded using MPI in a distributed multiprocessor framework. The performance analysis of the algorithm is carried out through experiments performed on networks with varying sizes (N = 7, 13, and 26). Performance indicators like execution time, communication delay, average hop count, and load balancing efficiency are used to evaluate the algorithm's performance. It is shown from the simulation studies that although PDN performs well in terms of routing efficiency and balance, performance is more influenced by communication delay as the number of processors increases.

References

• B. Parhami and M. Rakov, “Perfect difference networks and related interconnection structures for parallel and distributed systems,” IEEE Transactions on Parallel and Distributed Systems, vol. 16, no. 8, pp. 714–724, Aug. 2005.
• J. Singer, “A theorem in finite projective geometry and some applications to number theory,” Transactions of the American Mathematical Society, vol. 43, no. 3, pp. 377–385, 1938.
• W. J. Dally and B. Towles, Principles and Practices of Interconnection Networks. San Francisco, CA, USA: Morgan Kaufmann, 2004.
• F. T. Leighton, Introduction to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes. San Mateo, CA, USA: Morgan Kaufmann, 1992.
• H. J. Siegel, Interconnection Networks for Large-Scale Parallel Processing: Theory and Case Studies. Lexington, MA, USA: Lexington Books, 1990.
• P. P. Pande, C. Grecu, M. Jones, A. Ivanov, and R. Saleh, “Performance evaluation and design trade-offs for network-on-chip interconnect architectures,” IEEE Transactions on Computers, vol. 54, no. 8, pp. 1025–1040, Aug. 2005.
• I. Foster and C. Kesselman, The Grid: Blueprint for a New Computing Infrastructure. San Francisco, CA, USA: Morgan Kaufmann, 2003.
• M. Armbrust et al., “A view of cloud computing,” Communications of the ACM, vol. 53, no. 4, pp. 50–58, Apr. 2010.
• S. Kumar, A. Mamidala, D. Faraj, et al., “Introduction to Blue Gene/L supercomputer architecture,” IBM Journal of Research and Development, vol. 49, no. 2/3, pp. 195–212, 2005.
• R. K. Katare and N. S. Chaudhari, “A comparative study of hypercube and perfect difference network for parallel and distributed systems,” International Journal of Computer Applications, vol. 1, no. 21, pp. 1–5, 2010.
• P. Sharma, R. Begum, R. Katare, and A. Waoo, “Exploring the interplay between communication complexity and network density in PDNs,” ShodhKosh: Journal of Visual and Performing Arts, vol. 5, no. 5, 2024.
• P. Sharma, S. Tripathi, R. Katare, and A. Waoo, “PRAM-based algorithm for perfect difference network analysis,” ShodhKosh: Journal of Visual and Performing Arts, vol. 5, no. 1, 2024.
• S. Shekhar, S. K. Feiner, and W. G. Aref, “Spatial computing: Issues, trends, and challenges,” Communications of the ACM, vol. 63, no. 6, pp. 72–81, 2020.
• J. L. Gross and J. Yellen, Graph Theory and Its Applications. Boca Raton, FL, USA: CRC Press, 2005.
• L. Benini and G. De Micheli, “Networks on chips: A new SoC paradigm,” IEEE Computer, vol. 35, no. 1, pp. 70–78, Jan. 2002.
• Träff, Jesper Larsson. "Distributed Memory Parallel Systems and MPI." Lectures on Parallel Computing. Cham: Springer Nature Switzerland, 2026. 171-287.