sudha@cutter.SRC.Honeywell.COM (Sudha Yalamanchili) (11/02/88)
In article <3405@hubcap.UUCP> bjornl@tds.kth.se (Bj|rn Lisper) writes: > %One big difference is that the CM hypercube is synchronous (i.e., a 12-D > %network requires 12 steps to transfer data, even if the target is a nearest > %neighbor). > > I wonder if this is true. If there is congestion, messages will have to wait > until the line is free. Therefore it might take more than twelve cycles to > complete an instruction. This implies that there must be some mechanism by > which completion of all transfers is detected. This mechanism should be > able to work even when the transfers complete in less than 12 cycles, i.e. > when all processors issue nearest neighbor transfers. As I understand it, each processor chip in the CM-1 has 16 processors with 4K processors arranged in a 12 dimensional hypercube. Routing through the cube is synchronous consisting of petit cycles. Each petit cycle consists of 12 dimension cycles. In each dimension cycle every node checks locally for messages that have to traverse that dimension. If there is more than one, the highest priority (by age I believe) is selected and the other is buffered. This buffered message cannot reach its destination until at least the next petit cycle (> 12 dimension cycles later ) since messages can traverse a dimension only only once in the course of a petit cycle. In addition, since you can have messages comming into the router in each petit cycle it is possible that your buffers may overflow. In this case. messages can be sent out on some available dimension, in effect sending it one hop farther from its destination. Thus a message can take even longer to reach its destination. I think all messages are gauranteed to reach their destinations eventually since messages are assigned priorities based on "age". However, in the absence of conflicts messages do not have to take 12 cycles, just the number of cycles equal to the number of hops apart that they are. Sudhakar Yalamanchili Honeywell Systems and Research Center (612)782-7426 3660 Technology Drive, Minneapolis, MN 55418 UUCP: sudha@srcsip.uucp