Embedding linear arrays of the maximum length in O-shaped meshes

Fatemeh Keshavarz-Kohjerdi

---

URL :   http://research.shahed.ac.ir/WSR/WebPages/Report/PaperView.aspx?PaperID=158567
Date :  2021/06/02
Publish in :    The Journal of Supercomputing
DOI :  https://doi.org/10.1007/s11227-021-03895-1
Link :  http://dx.doi.org/10.1007/s11227-021-03895-1
Keywords :2D mesh - O-shaped grid graph - Longest path - Embedding - Interconnection networks

Abstract :

---

Embedding an interconnection network into another network is one of the important problems in parallel processing. In this paper, we study embedding of linear arrays (paths) of maximum length in O-shaped meshes (O-shaped grid graphs). This is equal to finding a longest path in an O-shaped mesh (grid graph). An O-shaped mesh is a 2D mesh that a smaller 2D mesh is removed from it. The removed nodes can be considered as faulty processor. We give a linear-time parallel algorithm for this problem. To show the algorithm finds an optimal path, first we prove some upper bounds on the length of the longest paths, then we show that how our algorithm meets these upper bounds.