Rectangular vs. Triangular Minimal Routing and Performance Study
Dominique Désérable and Rolf Hoffmann
This paper presents a comparative study of the XY–routing protocol in the square grid “S” examined herein with the XYZ protocol in the triangular grid “T” examined elsewhere, both with toroidal connections and N nodes. The routing problem (also called multiple target searching) is performed in a partitioned cellular automata network with agents (or messages) moving from sources to targets, preferably on their minimal routes. The network in S consists of N nodes with 4 buffers per node. Buffers with the same names are connected to their neighboring nodes via unidirectional links. Each buffer may host an agent and each agent situated in a buffer has a computed direction defining the new buffer in the adjacent node. Two scenarios are examined: (i) N − 1 agents are moving to a common target (also called “all-to-one gathering”) (ii) N/2 agents are moving to N/2 targets. It is shown that in both cases the T grid is 1.5 times faster than the S grid. The deterministic minimal routing protocols were also randomized, with agents choosing a random direction in order to cope with congestion and deadlocks. It is shown that randomization can slightly shorten the transfer time in case of congestion, but, more important, deadlocks can be resolved.
Keywords: Cellular automata (CA); multi-agent system; rectangular and triangular minimal routing; network on chip; performances