Article Preview
TopIntroduction
Efficient data routing has many different kinds of applications as there are a lot of contexts with a need to transfer a huge amount of messages between a large number of sources and destinations. Such settings appear in the Internet and telecommunication network routing switches as well as in implementing shared memory abstractions on top of distributed memory systems. Requirements concerning switching differ in these settings. In some cases only the bandwidth of the switch is most important whereas in some cases it is the switching speed and expected delay. Also scalability and simplicity of the solution are important factors.
Efficiency of shared memory based throughput computing relies on the idea to hide the memory access latencies by enabling the nodes to do something useful while memory requests are routed. The latency of routing memory operations can be hidden by being able to execute instructions from several independent threads in each processor node, if there are enough network bandwidth and sufficient number of executable threads. This requires certain properties from the routing machinery.
Our contribution to this setting is an all-optical sparse architecture with a scheduled routing protocol for routing h-relations very efficiently. In particular, our construction is truly scalable, supports very fast switching as no electro-optical conversions are needed on the routing paths, all packets are routed along one of the shortest paths, processor nodes can inject packets at each step into the network, and all the packets injected into the routing machinery reach their targets without collisions.
Our work is motivated by studying to support throughput computing via so-called emulated shared memory with a network of distributed memory modules (Fortune & Wyllie, 1978; Valiant, 1990). If a parallel algorithm has enough parallel “slackness,” i.e., large enough number of independent parallel threads at each processor, the implementation of shared memory can be reduced to efficient routing of an 
-relation (Valiant, 1990). An 
-relation is a routing problem where each processor has at most 
packets to send and is the target of at most 
packets (Adler, Byers, & Karp, 1995). An implementation of an 
-relation is said to be work-optimal at cost c, if all the packets arrive at their targets in time ch. A precondition of work-optimality is that h is greater than the diameter 
of the network and the network can move 
packets in each step, where P is the number of processors. Otherwise slackness cannot be used to “hide” the latency due to travel across the diameter (Adler, Byers, & Karp, 1995; Honkanen, Leppänen, & Penttonen, 2001).
Some architectural solutions satisfying the above are presented, e.g., by Valiant (1990) and by Sibeyn (1998).