A heuristic fault-tolerant routing algorithm in mesh using rectilinear-monotone polygonal fault blocks

TY - JOUR

T1 - A heuristic fault-tolerant routing algorithm in mesh using rectilinear-monotone polygonal fault blocks

AU - Wang, Dajin

PY - 2007/9

Y1 - 2007/9

N2 - A new, rectilinear-monotone polygonally shaped fault block model, called Minimal-Connected-Component (MCC), was proposed in [D. Wang, A rectilinear-monotone polygonal fault block model for fault-tolerant minimal routing in mesh, IEEE Trans. Comput. 52 (3) (2003) 310-320] for minimal adaptive routing in mesh-connected multiprocessor systems. This model refines the widely used rectangular model by including fewer non-faulty nodes in fault blocks. The positions of source/destination nodes relative to faulty nodes are taken into consideration when constructing fault blocks. Adaptive routing algorithm was given in Wang (2003), that constructs a minimal "Manhattan" route avoiding all fault blocks, should such routes exist. However, if there are no minimal routes, we still need to find a route, preferably as short as possible. In this paper, we propose a heuristic algorithm that takes a greedy approach, and can compute a nearly shortest route without much overhead. The significance of this algorithm lies in the fact that routing is a frequently performed task, and messages need to get to their destinations as soon as possible. Therefore one would prefer to have a fast answer about which route to take (and then take it), rather than spend too much time working out an absolutely shortest route.

AB - A new, rectilinear-monotone polygonally shaped fault block model, called Minimal-Connected-Component (MCC), was proposed in [D. Wang, A rectilinear-monotone polygonal fault block model for fault-tolerant minimal routing in mesh, IEEE Trans. Comput. 52 (3) (2003) 310-320] for minimal adaptive routing in mesh-connected multiprocessor systems. This model refines the widely used rectangular model by including fewer non-faulty nodes in fault blocks. The positions of source/destination nodes relative to faulty nodes are taken into consideration when constructing fault blocks. Adaptive routing algorithm was given in Wang (2003), that constructs a minimal "Manhattan" route avoiding all fault blocks, should such routes exist. However, if there are no minimal routes, we still need to find a route, preferably as short as possible. In this paper, we propose a heuristic algorithm that takes a greedy approach, and can compute a nearly shortest route without much overhead. The significance of this algorithm lies in the fact that routing is a frequently performed task, and messages need to get to their destinations as soon as possible. Therefore one would prefer to have a fast answer about which route to take (and then take it), rather than spend too much time working out an absolutely shortest route.

KW - Adaptive routing

KW - Fault block model

KW - Fault tolerance

KW - Interconnection network

KW - Mesh

UR - http://www.scopus.com/inward/record.url?scp=34248553603&partnerID=8YFLogxK

U2 - 10.1016/j.sysarc.2006.12.005

DO - 10.1016/j.sysarc.2006.12.005

M3 - Article

SN - 1383-7621

VL - 53

SP - 619

EP - 628

JO - Journal of Systems Architecture

JF - Journal of Systems Architecture

IS - 9

ER -