A recursion-based broadcast paradigm in wormhole routed mesh/torus networks

A novel broadcast technique for wormhole-routed mesh and torus parallel computers based on recursion is presented. It works by partitioning the graph into several subgraphs similar to the original one, and identifying a characteristic low-dimensional subgraph from these subgraphs. The source message is first scattered in the characteristic low-dimensional subgraph of the original graph, then through a O(1) number of message transfer and sharing operations, the characteristic low-dimensional subgraphs in each subgraph get the full source message. This procedure continues recursively until the minimum subgraph (a single node) gets all the source message. We have applied this general paradigm to several different cases including the one port/all-port model in mesh/torus with 2 or higher dimension. The network topology can be square or nonsquare, the source node can be located in the corner or not. Comparing to the previous results, our paradigm reduces broadcast latency and is simpler. We also present an analytical comparison of the algorithm against the optimum.