In this chapter, the problem of constructing minimal cycle-breaking connectivity preserving sets of turns for graphs that model regular or near regular multiprocessor systems, as a method to prevent deadlocks is investigated. Cycle-breaking provides for deadlock-free wormhole routing defined by turns prohibited at some nodes. The lower and upper bounds for minimal cardinalities of cycle-breaking connectivity preserving sets for several classes of graphs such as homogeneous meshes, p-ary n-cubes, cube-connected cycles, hexagonal and honeycomb meshes and tori, Hamiltonian graphs and others are obtained and presented along with some preliminary experimental results.
Top1. Introduction
In previous chapter, we analyzed communication networks that are irregular, where nodes have arbitrary number of adjacent neighbor nodes. Because of the way they evolve in an ad hoc manner, networks of workstations (NOWS) are as a rule irregular. This chapter is devoted to procedures that guarantee deadlock-free wormhole routing in multiprocessor systems with regular or almost regular interconnection topologies. The approach is based on minimizing the number of turns that are prohibited and therefore are not available for routing. The regularities in the structure of networks make it possible to derive simple and efficient solutions for the turn prohibition problem. Thus, the general algorithms developed previously for arbitrary topologies, e.g., (Dally & Seitz, 1987; Boppana & Chalasani, 1993; Chalasani & Boppana, 1995; Duato, Yalamancili, & Ni, 1997; Ni & McKinley, 1993), (Dally & Seitz, 1986), (Duato, 1993), (Dally & Aoki, 1997), (Zakrevski, Jaiswal, Levitin, & Karpovsky, 1999; Zakrevski, Jaiswal, & Karpovsky, 1999; Zakrevski, Mustafa, & Karpovsky, 2000; Lysne, Skeie, Reinemo, & Theiss, 2006; Schroeder, Birrel, Burrows, Murray, Needham, Rodeheer, et al., 1990; Sancho & Robles, 2000), (Skeie, Lysne, & Theiss, 2002; Sancho et al., 2004; Pellegrini et al., 2004, 2006), (Mustafa et al., 2005; Levitin et al., 2006; Levitin et al., May, 2009, 2010) are not used here. Instead, optimal or asymptotically optimal solutions of the turn prohibition problem for general classes of special topologies, prevalent in multiprocessor systems are presented. These solutions are obtained by application of simple rules, run-time complexities of which do not exceed 
(i.e., linear in the number of nodes N), and, in many cases, is 
(i.e., constant). The memory requirements for computing the solutions do not exceed
The proposed turn prohibition rules can be easily implemented for execution in a distributed way.
It should be pointed out that turn prohibition algorithms are, in fact, pre-routing procedures; they do no prescribe any specific routing policy, but just restrict the set of turns permitted for use in routing tables. Therefore, they are compatible with any routing algorithm, in particular, with the fully adaptive minimal routing (of course, paths that include prohibited turns are excluded from consideration during the construction of the routing tables).
A few particular regular topologies have been considered in several papers (Glass & Ni, 1994; Horst, 1996; Decayeux & Seme, 2005; Nocetti, Stojmenovic, & Zhang, 2002; Parhami & Kwai, 2001; Stojmenovic, 1997; Dolter, Ramanathan, & Shin, 1991), (Dally & Seitz, 1986). This chapter presents methods applicable to a number of classes of popular regular graphs, such as homogeneous meshes, p-ary n-cubes, cube connected cycles, hexagonal and honeycomb meshes and tori and Hamiltonian graphs.