Scaleable low-latency switch for usage in an interconnect structure

Abstract

A scalable low-latency switch extends the functionality of a multiple level minimum logic interconnect structure for usage in computers of all types, networks and communication systems. The multiple level minimum logic interconnect structure employs a data flow technique based on timing and positioning of messages moving through the structure. The scalable low-latency switch is distributed throughout multiple nodes in the structure so that a supervisory controller providing a global control function and complex logic structures are avoided while the interconnect structure operates as a “deflection” or “hot potato” system in which processing and storage overhead at each node is reduced. The interconnect structure using the scalable low-latency switch employs a method of achieving wormhole routing through an integrated circuit chip by a novel procedure for inserting messages into the chip. Rather than simultaneously inserting a message into each unblocked node on the outer cylinder at every angle, messages are inserted simultaneously into two columns A and B only if an entire message fits between A and B. Messages are inserted into column,at time,Messages are inserted into column,at time t,+t,, where time t,is the time for a first bit of a message to move from column,to column,on the top level. Messages are inserted into column,at time t,+2t,, and so forth. The strategy prevents the first bit of one message from colliding with an interior bit of another message already in the switch. Contention between entire messages is addressed by resolving the contention between the first bit only so that messages wormhole through many cells.