Design Tradeoffs of Low-cost Multi-computer Networks Part 3

5 Results We present results for simulated performance, latency, area, timing, and some cost-effective designs. Then we present some results on buffer sharing, a comparison to an output buffered design, and finally some observations on our experiments. 5.1 Simulated Performance Results are presented in several tables each having a similar but slightly obscure format. To save space in the captions we describe that format here and thereby also summarize the switch configurations we have tested. Each cell contains a measured attribute, e.g. capacity or frequency, for a particular switch design. The columns are differentiated by switching mode (VCT or WH), wiring (unidirectional or bidirectional), wraparound or not (mesh/torus), and other attributes particular to a switching mode. For WH, we measured both standard and T3D-style virtual channel selection (marked whSt and whT3D). For VCT we measured both deadlock prevention strategies, strict and relaxed (marked vctStr and vctRel). There is only a single column for the mesh topology: it is much more likely to be advantageous for wormhole networks and it does not require virtual channel selection. The rows are differentiated by total lanes per dimension and by buffer size. Each design is duplicated for 1, 2, and 4 lanes per (virtual) channel. The offsets are because i) bidirectional networks have double the channels as unidirectional networks and because ii) WH torus networks have two virtual channels per direction per dimension while VCT networks only have one. The following tables 4 to 9 show the performance, in flits / cycle, for the design options investigated. 42 Table 4 Performance with random communication pattern and a packet size of 6. Unidirectional Lns/Bfsz whSt 1/ 6 1 / 12 1 / 24 1 / 48 2/ 6 2 / 12 2 / 24 2 / 48 4/ 6 4 / 12 4 / 24 4 / 48 8/ 6 8 / 12 8 / 24 8 / 48 16 / 6 16 / 12 16 / 24 16 / 48 whT3D vctStr Bidirectional vctRel 0.088 0.155 0.188 0.161 0.189 0.211 0.171 0.197 0.212 0.199 0.229 0.241 0.180 0.221 0.246 0.227 0.239 0.255 0.223 0.244 0.253 0.240 0.255 0.264 0.236 0.253 0.270 0.247 0.255 0.268 0.251 0.263 0.272 0.263 0.272 0.277 mshwh 0.287 0.333 0.367 0.390 0.389 0.427 0.450 0.471 0.441 0.465 0.484 0.490 whSt whT3D 0.441 0.525 0.605 0.675 0.626 0.712 0.788 0.825 0.710 0.792 0.827 0.837 vctStr 0.546 0.638 0.722 0.780 0.694 0.780 0.804 0.839 0.739 0.780 0.804 0.832 vctRel 0.422 0.514 0.585 0.442 0.526 0.596 0.632 0.750 0.797 0.712 0.769 0.792 0.750 0.825 0.838 0.784 0.820 0.848 Table 5 Performance with random communication pattern and a packet size of 24. Unidirectional Lns/Bfsz 1/ 6 1 / 12 1 / 24 1 / 48 2/ 6 2 / 12 2 / 24 2 / 48 4/ 6 4 / 12 4 / 24 4 / 48 8/ 6 8 / 12 8 / 24 8 / 48 16 / 6 16 / 12 16 / 24 16 / 48 whSt whT3D vctStr 0.165 0.126 0.152 0.172 0.096 0.171 0.197 0.176 0.195 0.216 0.190 0.213 0.233 0.213 0.232 0.244 0.225 0.239 0.258 0.209 0.227 Bidirectional vctRel mshwh whSt whT3D vctStr vctRel 0.166 0.198 0.234 0.189 0.240 0.266 0.309 0.268 0.319 0.343 0.413 0.298 0.334 0.392 0.429 43 0.272 0.295 0.403 0.480 0.341 0.401 0.465 0.485 0.386 0.450 0.476 0.486 0.315 0.347 0.446 0.484 0.352 0.422 0.491 0.510 0.377 0.416 0.502 0.506 0.358 0.445 0.512 0.523 0.520 0.534 Table 6 Performance with hot-spot communication pattern and a packet size of 6. Unidirectional Lns/Bfsz 1/ 6 1 / 12 1 / 24 1 / 48 2/ 6 2 / 12 2 / 24 2 / 48 4/ 6 4 / 12 4 / 24 4 / 48 8/ 6 8 / 12 8 / 24 8 / 48 16 / 6 16 / 12 16 / 24 16 / 48 whSt whT3D vctStr Bidirectional vctRel 0.141 0.157 0.163 0.094 0.134 0.157 0.144 0.159 0.169 0.161 0.176 0.183 0.172 0.178 0.246 0.154 0.172 0.255 0.176 0.184 0.186 0.176 0.183 0.190 0.176 0.182 0.187 0.174 0.188 0.188 0.187 0.188 0.191 0.186 0.192 0.195 mshwh 0.206 0.225 0.237 0.242 0.266 0.284 0.298 0.309 0.289 0.302 0.312 0.319 whSt whT3D 0.326 0.361 0.384 0.405 0.401 0.435 0.450 0.463 0.429 0.448 0.469 0.474 vctStr 0.363 0.388 0.418 0.441 0.417 0.433 0.450 0.469 0.450 0.448 0.469 0.474 vctRel 0.234 0.246 0.270 0.244 0.270 0.297 0.390 0.422 0.458 0.439 0.463 0.474 0.427 0.454 0.463 0.465 0.464 0.478 Table 7 Performance with hot-spot communication pattern and a packet size of 24. Unidirectional Lns/Bfsz 1/ 6 1 / 12 1 / 24 1 / 48 2/ 6 2 / 12 2 / 24 2 / 48 4/ 6 4 / 12 4 / 24 4 / 48 8/ 6 8 / 12 8 / 24 8 / 48 16 / 6 16 / 12 16 / 24 16 / 48 whSt whT3D vctStr 0.188 0.117 0.134 0.154 0.096 0.148 0.165 0.152 0.166 0.176 0.162 0.169 0.178 0.169 0.186 0.188 0.176 0.180 0.188 0.169 0.176 Bidirectional vctRel mshwh whSt whT3D vctStr vctRel 0.211 0.159 0.178 0.162 0.182 0.203 0.227 0.225 0.239 0.258 0.286 0.242 0.277 0.293 0.307 44 0.230 0.268 0.322 0.375 0.309 0.360 0.389 0.420 0.322 0.373 0.427 0.455 0.253 0.279 0.359 0.390 0.315 0.364 0.398 0.435 0.330 0.384 0.416 0.461 0.225 0.273 0.380 0.432 0.450 0.472 Table 8 Performance with near communication pattern and a packet size of 6. Unidirectional Lns/Bfsz 1/ 6 1 / 12 1 / 24 1 / 48 2/ 6 2 / 12 2 / 24 2 / 48 4/ 6 4 / 12 4 / 24 4 / 48 8/ 6 8 / 12 8 / 24 8 / 48 16 / 6 16 / 12 16 / 24 16 / 48 whSt whT3D vctStr Bidirectional vctRel 0.107 0.169 0.206 0.173 0.206 0.225 0.189 0.218 0.234 0.214 0.246 0.262 0.186 0.238 0.270 0.246 0.263 0.274 0.244 0.265 0.281 0.261 0.277 0.287 0.258 0.277 0.292 0.270 0.281 0.291 0.277 0.292 0.298 0.285 0.295 0.302 mshwh 0.317 0.380 0.429 0.465 0.458 0.506 0.558 0.591 0.527 0.570 0.579 0.615 whSt whT3D 0.530 0.619 0.724 0.788 0.745 0.848 0.887 0.893 0.806 0.887 0.893 0.888 vctStr 0.666 0.772 0.834 0.868 0.788 0.853 0.876 0.889 0.825 0.900 0.888 0.902 vctRel 0.462 0.553 0.645 0.490 0.605 0.684 0.761 0.885 0.881 0.829 0.860 0.879 0.855 0.877 0.895 0.885 0.893 0.891 Table 9 Performance with near communication pattern and a packet size of 24. Unidirectional Lns/Bfsz 1/ 6 1 / 12 1 / 24 1 / 48 2/ 6 2 / 12 2 / 24 2 / 48 4/ 6 4 / 12 4 / 24 4 / 48 8/ 6 8 / 12 8 / 24 8 / 48 16 / 6 16 / 12 16 / 24 16 / 48 whSt whT3D vctStr 0.133 0.141 0.169 0.190 0.120 0.185 0.214 0.191 0.212 0.244 0.209 0.232 0.251 0.234 0.253 0.272 0.246 0.259 0.277 0.216 0.262 Bidirectional vctRel mshwh whSt whT3D vctStr vctRel 0.173 0.223 0.246 0.212 0.263 0.312 0.362 0.300 0.349 0.417 0.459 0.319 0.380 0.436 0.499 45 0.311 0.390 0.463 0.503 0.371 0.448 0.540 0.510 0.411 0.459 0.553 0.539 0.328 0.450 0.448 0.499 0.401 0.488 0.506 0.546 0.414 0.488 0.499 0.540 0.394 0.458 0.504 0.535 0.530 0.556 5.2 Latency In order for a packet to come into the node there must be room in the node for the packet. There is some handshaking that goes on between the transmitter node and the receiver node. For VCT this handshaking is simple and can be easily spread over multiple cycles. Because the nature of VCT guarantees that packets can’t be halted mid-packet. For WH this handshaking is more complex and can be spread across two or more cycles by careful management of buffer space. The requirements of the handshaking time are less stringent than the other times, so this really doesn’t play into the latency. InBuf 0 InBuf 1 InBuf 2 • • • OutBuf 1 2 3 4 5 6 - Flit 0 - Flit 0 Flit 1 - Flit 1 Flit 2 - Flit 2 Flit 3 - Flit 3 Flit 4 - - - - Flit 0 Flit 1 Flit 2 Select Path Arbitrate Crossbar Figure 15 Packet latency through node. When a packet comes into the node we first must decide which input buffer to place it in. We start filling buffers from Buffer 0. Buffers are filled in order, that is, if Buffer 2 has valid data, then Buffer 1 and Buffer 0 must also have valid data. In order to decide which buffer to place an incoming flit in we do three two things. Firstly, we determine if a flit is being transferred from Buffer 0 to a node output. This determination is simple for all but the first flit of a packet. In the case of the first flit, this is the end of the arbitration path. Second, we determine which is the lowest numbered empty buffer. This is equivalent to a priority encode of the number of buffers. The logic design is optimized for the path that results when the first flit wins its output arbitration and starts transmitting data. 46 When the flit in Buffer 0 is a packet head we must determine where it wants to go. First, its destination address is compared to this node’s address. (Say, X address) Since we assume each node is specifically designed for its address this path reduces to an inverter and AND gate. If the address doesn’t match, the packet continues in the same direction. If the address matches, this flit is “eaten” and on the next cycle the address is compared to this node’s address of the next dimension. (Say, Y address) In any case, a request is made to the appropriate output queue. We’ve called this address decode. Because of lane multiplexing, at most one new header flit will enter the node on each physical channel at a time. Path selection for an output channel by one header flit block path selection requests for this same output channel from all other input buffers from the same input channel. e.g. If in the X+ input channel, lane A requests an X+ output channel, all other lanes of the X+ input channel are blocked from making requests to the X+ output channel. They can make requests to other output channels. When a packet completes it stops blocking. The packet that arrived at its Buffer 0 next is then allowed to make a request. In the event of a tie (lane A and lane were transmitting to different output queues and they finished at the same time and both have packets behind them) a one packet, randomly chosen, is allowed to request. Each output queue lane will receive a request from each lane of each input queue that can transmit a packet to it. The output queue lane will arbitrate. If an output queue lane isn’t busy, it will arbitrate among the requestors and choose one. Because of lane multiplexing only one lane of an output queue will be ready to arbitrate at a time.. Finally, the results of this arbitration must be fed back to the logic along the path. See the accompanying drawing for a visual explanation. After an output has selected an input, it can transfer flits directly from the input queue’s Buffer 0 to the output queue through the crossbar. Our crossbars are implemented as a multiplexer for each 47 output with an input for each possible source. The path through the crossbar is directly related to the number of inputs and how fact the logic reduce these inputs to one output. We’ve divided this up into cycles that are practical. The latency through our nodes is three cycles. The first cycle has the flit going into the input buffer. The second cycle had the address decode and the arbitration. The third cycle is through the crossbar. Each cycle had the delay time for the appropriate path plus the FlipFlop setup and output delay time plus the delay for clock skew and jitter. By using a logic design trick, we’ve cut out a little time from the second and third cycles by not actually latching between these cycles, but by making this delay part of a two-cycle path. This saves us some setup, output delay, and clock skew time. Because we only arbitrate when Buffer 0 has a head flit, this isn’t too hard to do. Our control state machines control when we use this two-cycle path or not. Our cycle time ends up being defined by the greater of: crossbar cycle path delay or address decode>arbitration->crossbar path delay 2 Note that in a cascaded crossbar node, the latency is 3 cycles for X to X, Y to Y, or Y to P. But is 6 cycles for X to Y, or X to P. Also note that for nodes that have multiple lanes per channel, the latency can be higher because each lane has to share a physical channel. 5.3 Area The cell area we determine is the area in mm2 that a router node would occupy in LSI Logic’s G10-p Cell Based 0.18 micron technology. The base design was coded in Verilog HDL. The Synopsys logic synthesis tools were run on this design using LSI Logic’s G10-p as the target technology. This yielded area estimates for the base design. The router node design is very 48 modular. There are input buffers, output queues, and a very small amount of logic in-between. This makes evaluating the options easier because they are a change to one of the modules. The design options were evaluated in either of two ways. Some options were coded into Verilog and the cell area was determined with the Synopsys logic synthesis tools. The FIFO size, crossbar, and lane multiplexing options were determined this way. The input buffer sharing options were determined by investigating the logic of the base design and shared FIFO designs and scaling. The G10-p RAM cell characteristics were examined and a two port, 1read 1write, asynchronous RAM was chosen as the one used for these designs. (M10P211LA) Using the data points for RAM size in words and bit width and cell area, a formula was developed that would provide cell areas for data points not listed in the databook. The RAM area is determined for all RAM options without forcing the number of words to a power of 2. This would unnecessarily distort the area results to an implementation in a particular technology and make the results less general. Then formulas were created for the various design options. These formulas are in the form of Visual Basic programs used in a Microsoft Excel spreadsheet. A sample program follows. This is for a bidirectional virtual cut-through node with cascaded crossbar. The main function calculates two major parts, fifoarea and crossbararea. fifoarea is basically a count of the number of input queues from the Crossbar times the area for an input queue with the particular FIFO size , number of lanes, and sharing option. crossbararea is a count of the output queues times their size. The functions IQ_bivct and OQ determine the size of a single input and output queue. 'bidirectional virtual cut-through, cascaded crossbar Function bivct(lanes, fifo, share) Dim l, fifoarea, crossbararea If (s = 2) Then s = 1 'for bivct share 1 and 2 are the same End If l = lanes fifoarea = (6 * l) * IQ_bivct(fifo, l, share) crossbararea = 2 * ((l * OQ(3 * l)) + ((2 * l) * OQ(2 * l))) bivct = fifoarea + crossbararea 49 End Function Function IQ_bivct(fifo_int, lanes, share) Dim Base, rm Dim fifo fifo = fifo_int * 1# Base = cells2mm(7032#) If (fifo <= 4) Then share = 0 'no sharing for fifos <= 4 End If If (share = 0) Then rm = 1# End If If (share = 1) Then rm = Switch(lanes = 1, 1#, lanes = 2, 1.53, lanes = 4, 2.25) 'reg multiplier End If If (share = 2) Then rm = Switch(lanes = 1, 1#, lanes = 2, 1.53, lanes = 4, 2.25) 'reg multiplier End If IQ_bivct = (rm * Base) + (ramarea(lanes * (fifo - 4#) / 2, 20, lanes) / lanes) If (share = 3) Then 'vct node sharing uses this rm = Switch(lanes = 1, 4.92, lanes = 2, 5.42, lanes = 4, 6.75) IQ_bivct = (rm * Base) + (1.75 * ramarea(lanes * (fifo - 4#) / 2, 20, lanes) / lanes) End If End Function ' ram area with no increments on #words or #bits ' good for up to 512 words, 72 bits ' w - words in RAM ' b - bit width of RAM ' rd - number of read ports Function ramarea(w, b, rd) Dim Area If (w <= 0) Then ramarea = 0 End If Area = (180.6 + (6.839 * w)) + (42.29 + (1.217 * w)) * b ramarea = (Area * 0.0001) * ((1 + rd) / 2) End Function Function OQ(ports) OQ = cells2mm(374.3 + (225.7 * ports)) End Function Function cells2mm(cells) cells2mm = (cells / 3.2) / 13082 End Function Figure 16 Visual Basic code for bidirectional VCT area. The following two pages show the cell areas, in mm2 for the design options investigated. They are extracted from a Microsoft Excel spreadsheet. 50 Table 10 Area of designs with no input buffer sharing. Bidirectional –Cascaded Crossbar Lns/Bfsz mshwh 1/ 6 1 / 12 1 / 24 1 / 48 2/ 6 2 / 12 2 / 24 2 / 48 4/ 6 4 / 12 4 / 24 4 / 48 8/ 6 8 / 12 8 / 24 8 / 48 1.75 1.81 1.92 2.15 3.35 3.52 3.85 4.53 6.99 7.55 8.68 10.92 whSt 3.61 3.73 3.95 4.40 7.04 7.38 8.05 9.40 13.34 14.27 16.14 19.88 whT3D 3.61 3.73 3.95 4.40 7.04 7.38 8.05 9.40 13.34 14.27 16.14 19.88 vctStr Bidirectional – Full Crossbar VctRel 1.81 1.92 2.15 1.81 1.92 2.15 3.52 3.85 4.53 3.52 3.85 4.53 7.55 8.68 10.92 7.55 8.68 10.92 mshwh 1.35 1.40 1.49 1.68 2.20 2.33 2.58 3.09 3.95 4.34 5.14 6.73 whSt 2.57 2.66 2.82 3.16 4.51 4.75 5.22 6.18 8.68 9.45 11.00 14.08 whT3D 2.57 2.66 2.82 3.16 4.51 4.75 5.22 6.18 8.68 9.45 11.00 14.08 vctStr vctRel 1.40 1.49 1.68 1.40 1.49 1.68 2.33 2.58 3.09 2.33 2.58 3.09 4.34 5.14 6.73 4.34 5.14 6.73 Table 11 Area of designs with input buffer sharing between lanes. Bidirectional –Cascaded Crossbar Lns/Bfsz mshwh 1/ 6 1 / 12 1 / 24 1 / 48 2/ 6 2 / 12 2 / 24 2 / 48 4/ 6 4 / 12 4 / 24 4 / 48 8/ 6 8 / 12 8 / 24 8 / 48 1.75 1.81 1.92 2.15 3.35 4.59 4.92 5.60 6.99 12.59 13.72 15.96 whSt 3.61 3.73 3.95 4.40 7.04 9.52 10.19 11.54 13.34 22.67 24.54 28.28 whT3D 3.61 3.73 3.95 4.40 7.04 9.52 10.19 11.54 13.34 22.67 24.54 28.28 vctStr Bidirectional – Full Crossbar vctRel 1.81 1.92 2.15 1.81 1.92 2.15 4.59 4.92 5.60 4.59 4.92 5.60 12.59 13.72 15.96 12.59 13.72 15.96 51 mshwh 1.35 1.40 1.49 1.68 2.20 2.33 2.58 3.09 3.95 4.34 5.14 6.73 whSt 2.57 2.66 2.82 3.16 4.51 6.26 6.74 7.69 8.68 16.38 17.92 21.01 whT3D 2.57 2.66 2.82 3.16 4.51 6.26 6.74 7.69 8.68 16.38 17.92 21.01 vctStr vctRel 1.40 1.49 1.68 1.40 1.49 1.68 2.33 2.58 3.09 2.33 2.58 3.09 4.34 5.14 6.73 4.34 5.14 6.73 Table 12 Area of designs with input buffer sharing within a physical channel. Bidirectional –Cascaded Crossbar Lns/Bfsz mshwh 1/ 6 1 / 12 1 / 24 1 / 48 2/ 6 2 / 12 2 / 24 2 / 48 4/ 6 4 / 12 4 / 24 4 / 48 8/ 6 8 / 12 8 / 24 8 / 48 1.75 1.81 1.92 2.15 3.35 4.59 4.92 5.60 6.99 12.59 13.72 15.96 whSt 3.61 4.18 4.40 4.85 7.04 11.49 12.17 13.52 13.34 40.27 42.14 45.88 whT3D 3.61 4.18 4.40 4.85 7.04 11.49 12.17 13.52 13.34 40.27 42.14 45.88 vctStr Bidirectional – Full Crossbar vctRel 1.81 1.92 2.15 1.81 1.92 2.15 4.59 4.92 5.60 4.59 4.92 5.60 12.59 13.72 15.96 12.59 13.72 15.96 mshwh 1.35 1.40 1.49 1.68 2.20 3.13 3.38 3.89 3.95 7.91 8.71 10.30 whSt 2.57 2.66 2.82 3.16 4.51 4.75 5.22 6.18 8.68 9.45 11.00 14.08 whT3D vctStr 2.57 2.66 2.82 3.16 4.51 4.75 5.22 6.18 8.68 9.45 11.00 14.08 vctRel 1.40 1.49 1.68 1.40 1.49 1.68 3.13 3.38 3.89 3.13 3.38 3.89 7.91 8.71 10.30 7.91 8.71 10.30 Table 13 Area of designs with input buffer sharing within the entire node. Bidirectional –Cascaded Crossbar Lns/Bfsz mshwh 1/ 6 1 / 12 1 / 24 1 / 48 2/ 6 2 / 12 2 / 24 2 / 48 4/ 6 4 / 12 4 / 24 4 / 48 8/ 6 8 / 12 8 / 24 8 / 48 1.75 6.26 6.46 6.85 3.35 13.25 13.84 15.01 6.99 32.31 34.28 38.20 whSt 3.61 13.64 14.04 14.82 7.04 32.20 33.38 35.73 13.34 71.19 74.46 81.01 whT3D 3.61 13.64 14.04 14.82 7.04 32.20 33.38 35.73 13.34 71.19 74.46 81.01 vctStr Bidirectional – Full Crossbar vctRel 6.26 6.46 6.85 6.26 6.46 6.85 13.25 13.84 15.01 13.25 13.84 15.01 32.31 34.28 38.20 32.31 34.28 38.20 52 mshwh 1.35 5.11 5.28 5.60 2.20 9.63 10.07 10.95 3.95 21.88 23.27 26.05 whSt 2.57 10.09 10.39 10.98 4.51 22.33 23.16 24.83 8.68 56.41 59.11 64.51 whT3D 2.57 10.09 10.39 10.98 4.51 22.33 23.16 24.83 8.68 56.41 59.11 64.51 vctStr vctRel 5.11 5.28 5.60 5.11 5.28 5.60 9.63 10.07 10.95 9.63 10.07 10.95 21.88 23.27 26.05 21.88 23.27 26.05 5.4 Timing Timing is determined based on the designs being implemented in LSI Logic’s G10-p Cell Based 0.18 micron technology. Using the LSI Logic G10-p databook and Microsoft Excel, the delay for NAND gates with various fan-in and fan-out are determined and put into a function. See Appendix B. The paths were determined by inspection of the design. The logic is designed using almost exclusively NAND gates. This simplifies the analysis and while it may alter the absolute numbers to a small degree, it preserves the relative delays. Fan-in and fan-out are used as parameters to the NAND delay function generated for Microsoft Excel. The paths are entered into a Microsoft Excel spreadsheet and tabulated. See Appendix B. The following table shows the resultant cycle times for some of the design options investigated. The bidirectional nodes are cascaded crossbar, and the unidirectional nodes are full crossbar. Refer to Appendix B for details on the components of the path delays and the determination of the gate delays themselves. As a general observation, the path delays are very small. This is because the router designs are relatively simple compared to other kinds of logic, say like you’d find in a processor. The other important observation is that the delay is roughly proportional to a constant, plus the log of the number of ports in the crossbar, k + .65 * log10(# crossbar ports). Where k = .83 for the bidirectional case and k = .86 for the unidirectional case. The constant is due to the path constants, flip-flop clock to output delay, setup time, clock skew and jitter allotments, and the path delays that are independent of the number of ports (i.e. address matching). The constant is slightly bigger for the unidirectional cases because these are 53 implemented as full crossbars and the path selection logic has slightly more delay due to the more turning options. The remainder of the path’s delay is in the arbitration and crossbar logic. This logic has a delay proportional to the log of the number of ports in the crossbar. Table 14 Cycle time summary. 1 lane 1.18 1.39 1.18 1.42 2 lane 1.39 1.49 1.39 1.53 4 lane 1.50 1.70 1.53 1.73 1 lane 2 lane 4 lane .41 .42 .10 .25 1.18 .41 .63 .10 .25 1.39 .41 .71 .10 .25 1.47 FIFO > AD > PA > CB > LM > Output reg FIFO reg clk to output .41 Addr match/path select .62 Path arbitrate .49 Crossbar,lane multiplex .42 Output reg setup .10 clock skew, jitter .25 Total 2.28 Total / 2 1.14 .41 .58 .73 .63 .10 .25 2.69 1.35 .41 .66 .88 .71 .10 .25 3.00 1.50 1.18 1.39 1.50 1 lane 2 lane 4 lane .41 .63 .10 .25 1.39 .41 .71 .10 .25 1.47 .41 .92 .10 .25 1.68 FIFO > AD > PA > CB > LM > Output reg FIFO reg clk to output .41 Addr match/path select .70 Path arbitrate .67 Crossbar,lane multiplex .63 .41 .58 .93 .71 .41 .66 1.05 .92 Bidirectional VCT Bidirectional Wormhole Unidirectional VCT Unidirectional Wormhole Bidirectional Virtual Cut-Through FIFO reg > CB > LM > Output reg FIFO reg clk to output Crossbar,lane multiplex Output reg setup clock skew, jitter Total Cycle time (max of both) Bidirectional Wormhole FIFO reg > CB > LM > Output reg FIFO reg clk to output Crossbar,lane multiplex Output reg setup clock skew, jitter Total 54 Output reg setup clock skew, jitter Total Total / 2 .10 .25 2.76 1.38 .10 .25 2.98 1.49 .10 .25 3.39 1.70 Cycle time (max of both) 1.39 1.49 1.70 1 lane 2 lane 4 lane .41 .42 .10 .25 1.18 .41 .63 .10 .25 1.39 .41 .71 .10 .25 1.47 FIFO > AD > PA > CB > LM > Output reg FIFO reg clk to output .41 Addr match/path select .63 Path arbitrate .53 Crossbar,lane multiplex .42 Output reg setup .10 clock skew, jitter .25 Total 2.33 Total / 2 1.17 .41 .59 .77 .63 .10 .25 2.74 1.37 .41 .67 .92 .71 .10 .25 3.05 1.53 1.18 1.39 1.53 1 lane 2 lane 4 lane .41 .63 .10 .25 1.39 .41 .71 .10 .25 1.47 .41 .92 .10 .25 1.68 FIFO > AD > PA > CB > LM > Output reg FIFO reg clk to output .41 Addr match/path select .75 Path arbitrate .69 Crossbar,lane multiplex .63 Output reg setup .10 clock skew, jitter .25 Total 2.84 Total / 2 1.42 .41 .63 .96 .71 .10 .25 3.05 1.53 .41 .71 1.08 .92 .10 .25 3.47 1.73 1.58 1.73 Unidirectional Virtual Cut-Through FIFO reg > CB > LM > Output reg FIFO reg clk to output Crossbar,lane multiplex Output reg setup clock skew, jitter Total Cycle time (max of both) Unidirectional Wormhole FIFO reg > CB > LM > Output reg FIFO reg clk to output Crossbar,lane multiplex Output reg setup clock skew, jitter Total Cycle time (max of both) 1.42 55 5.5 Cost-Effective Designs The following graphs show cost-effectiveness of each design option in terms of performance vs. cell area for each combination of traffic pattern and packet size. The cost-effective designs, those that have higher performance for a given cell area, are easy to spot because they are on the top left frontier. Figure 17 Legend for capacity versus area graphs. 56 Figure 18 Capacity versus area graph for a random pattern with a packet size of 6, top, and 24, bottom. 57 Figure 19 Capacity versus area graph for a hot-spot pattern with a packet size of 6, top, and 24, bottom. 58 Figure 20 Capacity versus area graph for a near pattern with a packet size of 6, top, and 24, bottom. 59 Table 15 Cost-effective designs. Random, packet size of 6 Unidirectional VCT – Relaxed, 1 lane, buffer size = 12 Unidirectional VCT – Relaxed, 1 lane, buffer size = 24 Unidirectional VCT – Relaxed, 1 lane, buffer size = 48 Bidirectional VCT – Relaxed, 1 lane, buffer size = 12 Bidirectional VCT – Relaxed, 1 lane, buffer size = 24 Bidirectional VCT – Relaxed, 1 lane, buffer size = 48 Bidirectional VCT – Relaxed, 2 lane, buffer size = 12 Bidirectional VCT – Relaxed, 2 lane, buffer size = 24 Bidirectional VCT – Relaxed, 2 lane, buffer size = 48 Random, packet size of 24 Unidirectional VCT – Relaxed, 1 lane, buffer size = 48 Bidirectional VCT – Relaxed, 1 lane, buffer size = 48 Hot-spot, packet size of 6 Unidirectional VCT – Strict, 1 lane, buffer size = 12 Unidirectional VCT – Strict, 1 lane, buffer size = 24 Unidirectional VCT – Strict, 1 lane, buffer size = 48 Bidirectional VCT – Relaxed, 1 lane, buffer size = 12 Bidirectional VCT – Relaxed, 1 lane, buffer size = 24 Bidirectional VCT – Relaxed, 1 lane, buffer size = 48 Bidirectional VCT – Relaxed, 2 lane, buffer size = 12 Bidirectional VCT – Relaxed, 2 lane, buffer size = 24 Bidirectional VCT – Relaxed, 2 lane, buffer size = 48 Hot-spot, packet size of 24 Unidirectional VCT – Relaxed, 1 lane, buffer size = 48 Bidirectional WH T3D, 1 lane, buffer size = 24 Bidirectional WH T3D, 1 lane, buffer size = 48 Bidirectional VCT – Relaxed, 2 lane, buffer size = 48 Near, packet size of 6 Unidirectional VCT – Relaxed, 1 lane, buffer size = 12 Unidirectional VCT – Relaxed, 1 lane, buffer size = 24 Unidirectional VCT – Relaxed, 1 lane, buffer size = 48 Bidirectional VCT – Relaxed, 1 lane, buffer size = 12 Bidirectional VCT – Relaxed, 1 lane, buffer size = 24 Bidirectional VCT – Relaxed, 1 lane, buffer size = 48 Bidirectional VCT – Relaxed, 2 lane, buffer size = 12 Bidirectional VCT – Relaxed, 2 lane, buffer size = 24 Near, packet size of 24 Unidirectional VCT – Relaxed, 1 lane, buffer size = 48 Bidirectional VCT – Relaxed, 1 lane, buffer size = 48 60 5.6 Buffer Sharing Figure 20 shows the cost/benefit of buffer sharing for bidirectional WH networks. Table 16 identifies the cost-effective alternatives. Sharing has virtually no benefit for random loads but some benefit for hot spot loads. This observation is similar to that of [3] although our sharing schemes retain the deterministic routing algorithm. The sharing designs that prove cost-effective under hot spot loads are those with a single lane per virtual channel and sharing between the pair of lanes in a virtual channel pair. These have relatively low area overhead and no added latency. Table 16 Cost-effective designs with sharing. Random No sharing, 1 lane, 6 flit buffer No sharing, 1 lane, 12 flit buffer No sharing, 1 lane, 24 flit buffer No sharing, 1 lane, 48 flit buffer Hot-spot No sharing, 1 lane, 6 flit buffer No sharing, 1 lane, 12 flit buffer No sharing, 1 lane, 24 flit buffer No sharing, 1 lane, 48 flit buffer Sharing among lanes in a virtual channel pair, 1 lane, 48 flit buffer Sharing among all lanes in a node, 1 lane, 24 flit buffer Sharing among all lanes in a node, 1 lane, 48 flit buffer 61 Figure 21 Buffer sharing capacity versus area graphs for random and hot-spot patterns with a packet size of 6. 62 5.7 Comparison to an Output Queue Design We investigate an output queue design, after the SP2 implementation [21], to verify that we aren’t missing something fundamental. We try to keep the design optimized for our choice of technology and application in the same manner as for our other designs. We discover that we are not able to make some of the optimizations we had made for the input queue designs. Particularly bothersome is the requirement that the pointer array be written or read in one cycle. (Our input queue designs are able to spread an array read or write over two cycles.) The cell area and timing characteristics of this design follow. When we use the upper bound on performance of 1 flit per node per cycle to get an upper bound for the performance of the output queue design, we see that it is not cost-effective for the Random or Near traffic patterns. For the Hot Spot traffic pattern we believe that the performance of the output queue design will be reduced by the same factors that reduced the performance of the other designs and that the output queue design will not be cost-effective for the Hot Spot traffic pattern either. Table 17 Output Queue Design Characteristics. Buffer Size 6 12 24 48 Area (mm2) Cycle Time Performance Upper Bound Not practical because register portion exceeds buffer size. 2.38 3.05 ns .328 flit/node/ns 2.82 3.11 ns .322 flit/node/ns 3.69 3.19 ns .313 flit/node/ns 5.8 Experiments and Observations Topology, latency, and capacity For reasons discussed above, the only latency results presented are those shown in Figure 13. With no congestion, latencies of the three topologies are related to the average path length: k for the unidirectional torus, about 2/3 k for the mesh, and 1/2 k for the bidirectional torus. However, since the injection time is a significant part of the latency, 2 times the packet size or 10 in Figure 63 13, and identical for all three topologies, the average path length may not be the most critical aspect of changing topology for small networks. Rather, it is the effect on capacity. There are three related reasons why topology affects capacity: i) differences in total internode bandwidth , ii) the shorter path length gets packets out more quickly and so they interfere less with each other, and iii) the intrinsic variation in quality among the buffer load balancing opportunities. These latency/bandwidth effects can be seen in Figure 13 as follows. The level of the `flat parts' of each bundle are due to differences in average path length while the locations of the knees are given by differences in the capacity-related properties. WH virtual channel selection This and the next several sets of observations are based on Tables 4 through 9. For bidirectional torus WH networks, T3D virtual channel selection was found to extremely effective with increases in capacity of up to 30% over the standard method. The advantage is diminished with the number of channels, however. This is because lanes within virtual channels are selected dynamically. Therefore, in a configuration with, say, four total lanes per direction, the two pairs of lanes are selected statically while the lanes within the virtual channels are selected dynamically. As the number of lanes increases, the quality of the initial selection becomes less important. The impact of optimized channel selection is much less pronounced for the unidirectional torus. This is somewhat surprising because of the dramatic reduction in channel imbalance due to T3Dstyle optimization. The impact of optimized virtual channel selection method is also less for non-random communication patterns. This may be because both unidirectional and bidirectional selection tables were optimized for a random load. Performance versus the near-random load can 64 certainly be improved by recomputing the lane selections, but the hot-spot load, which is inherently unpredictable, is more problematic. VCT buffer control Relaxing the VCT buffer control policy increases the usable buffer space for packets entering X from the input and Y from X. As expected, the improvement is most pronounced the smaller buffer sizes and is particularly important when routing the 24 flit packets with 48 flit buffers. Size of buffers Increasing the buffer size has the predictably positive effect on capacity. The improvement starts to tail off only for the designs with the largest total buffer capacity. For packets larger than 24 flits, larger buffers may be called for. Number of buffers Dally, in his study of virtual channel flow control, keeps the total buffer size constant while dividing that space among from 1 to 16 lanes [8]. Although not tabulated separately, we have done this for a buffer size of 48 per direction. In most cases, the improvement in network capacity when the number of lanes per (virtual) channel is increased from 1 to 2 was significant while the improvement from 2 to 4 was slight, and, in some cases, negative. For the bidirectional WH torus networks, the improvement was much greater with standard virtual channel selection than with the optimized version. Clearly this is another manifestation of the diminishing return of increasing the number of lanes. When area and cycle time are accounted for, the 4 lane per (virtual) channel designs are clearly poor. For VCT designs, 2 lanes per channel is often cost-effective. For WH designs, 2 lanes per virtual channel (4 lanes per direction per dimension) is almost never cost-effective. 65 Effect of Topology The unidirectional networks were found to be cost-effective only for the very simplest designs which have no bidirectional equivalent, VCT with one lane per channel which equates to one lane per dimension. In the case of two lanes per dimension, mesh WH with one lane per direction per dimension was found to be better than either unidirectional VCT or WH with two lanes per direction per dimension. In general, however, mesh networks were also found to be costeffective only were there was no bidirectional equivalent, that is, in the case with one lane per direction per dimension with small buffer size. Wormhole versus virtual cut-through switching One difference is that VCT networks can be created with a single buffer per node per ring. Such a WH network can only be constructed by either removing the wrap-around connections or adding buffers. Therefore cost-effective VCT networks exist in niches where WH networks do not. For the two buffer per ring case, VCT retains a distinct advantage in capacity, up to 10% greater for random loads, 8-14% for hot-spot loads, and up to 8% for near-random loads. As discussed earlier, this disparity in differences is due to the different ways buffers are selected, static for WH and dynamic for VCT. For reasons stated above, the near-random comparison is probably not valid and the performances are probably closer than shown. However, the hot-spot load, which is much more likely to occur in practice than a purely random load, accentuates the VCT advantage. As the number of buffers increases and the initial static selection becomes less important, WH and VCT performance converges. Certain mesh and bidirectional torus WH configurations also have niches where they are the most cost-effective. These are the lowest cost mesh WH networks and the bidirectional torus WH networks with buffer sizes smaller than twice the packet size. 66 Accounting for area and operating frequency Figures 16 to 18 contain the plots of network capacity in flits per node per nanosecond versus switch area in cells. The cost-effective designs are those toward the left and top of each graph. The four or five best designs for each combination of communication pattern and packet size are identified. Figures 16 to 18 combine three sets of results: i) the operating frequencies, ii) that the cell area, and iii) the capacity measures. Putting these together it is clear that an architect working on an application where area is important will be tempted to only select candidate switches from the left edges of the graphs. Specifically: • If increasing the number of lanes per direction to four or beyond was questionable from the cycle-based capacity results alone, accounting for the slower clock shows that it is clearly not cost-effective. • The decision on larger buffers is less clear-cut, but the capacity/area graphs are again illuminating. The designs with larger buffers cannot be eliminated out-right for the reason that another design has both lower cost and better performance. Yet, a doubling of area appears to yield only a few percent increase in capacity. Buffer Sharing Figure 20 shows the cost/benefit of buffer sharing for bidirectional WH networks. Table 17 identifies the cost-effective alternatives. Sharing has virtually no benefit for random loads but some benefit for hot spot loads. This observation is similar to that of [3] although our sharing schemes retain the deterministic routing algorithm. The sharing designs that prove cost-effective under hot spot loads are those with a single lane per virtual channel and sharing between the pair of lanes in a virtual channel pair. These have relatively low area overhead and no added latency. 67 In the hot-spot graph, one of the central queue designs appears cost-effective, in reality it is not. In Figure 20 we do not penalize the central queue designs for output contention overhead which would certainly eliminate the 8% advantage which had been achieved at a cost of a factor of 2.5 increase in area. 68 6 Conclusions In this work we have endeavored to exhaustively explore the design space of low-cost multicomputer networks including issues in switching, lane selection, buffer size, topology, routing algorithm, and packet size. Virtual Cut-Through is examined and found to be both more and less like Wormhole switching than previously described. More in that virtually all of the critical hardware including multi-lane channels can be identical to that of WH switches. Less in that VCT has its own deadlock issues and is open to a different lane selection paradigm. It has been stated elsewhere that VCT versus WH routing is a tradeoff between buffering and congestion. We suggest that for small packets and equal buffering, it is really mostly the difference between static and dynamic lane selection. Each design was characterized in two ways: with and RTL simulator that measured its capacity with respect to several workloads, and by synthesizing it to obtain its cell area and operating frequency. These results are analyzed with respect to the various parameters. Finally, the most promising designs are determined. 69