Design Tradeoffs of Low-cost Multi-computer Networks

1 Introduction 1.1 Problem and Motivation As advances in process technology continue with only modest slowdowns expected in the next decade, one of the fundamental questions in computer architecture remains how best to use newly available resources. Several possible approaches have been proposed, although they mostly fall into one of two categories: i) enhancing microprocessors with increased speculative capability, instruction-level parallelism and/or multi-threading and ii) multiprocessing on a chip, that is, integrating multiple discrete microprocessors or digital signal processors (DSPs) on a chip. The latter approach is likely to be preferable for computationally intensive tasks and is our primary interest here. Currently, the focus in building multiprocessor systems on a chip (SOCs) is, understandably, on taking advantage of existing processor and memory designs and the electronic design automation (EDA) technology which makes them easy to replicate and integrate. SOCs based on replicating microprocessors have included studies of symmetric multiprocessors (SMPs) on a chip. Others multiprocessor SOCs have taken a completely different approach, being based on enhancing memory by integrating a large number of simple processing elements (PEs). A critical issue for multiprocessor SOCs that has received very little attention is the question of how the removal of chip boundaries might change the design of the multiprocessor system, including both the design of the components as well as how they are integrated. Since it was the fact that an entire processor could be placed on a single chip--thereby removing long intraprocessor signaling delays--that spurred the microprocessor revolution, it seems possible that removal of packaging boundaries might cause a similar paradigm shift with multiprocessors. At the very least, there is likely to be a major shift in the design space as the distribution of propagation delays and the ratio of propagation delay to switching time is fundamentally altered. 1 The problem we address in this thesis is the design of a network appropriate for a single chip multiprocessor. This problem is important because the changing ratio of switching to propagation time is likely to have a significant effect on the relative benefits of various design choices. The single-chip assumption is also interesting from a methodological standpoint as it allows us to use standard workstation EDA tools for accurate circuit-level simulations. When these are combined with cycle-level simulations as we do in this thesis, it becomes possible to examine a large number of design alternatives without compromising accuracy. In this thesis, a large number of parallel processor network router designs are made and compared in terms of cycle-by-cycle performance, cell area, and cycle time. Although these designs are directed to parallel processor networks for use on a single substrate, they are also applicable to other design situations. The designs are based on a single basic design framework with a large number of different options. By comparing the designs that result from these options, a designer can make deductions about the relative cost and performance benefits of particular options and make decisions about which design to use for his particular situation. 1.2 The Basic Model We envision these multiprocessors on a chip as having dozens of nodes on a silicon substrate, increasing to hundreds as technology allows. Such a chip would have an array of processor node pairs, each with a connection to near neighbors. All processor-to-processor data transfers take place in the network nodes using the following scenario: i) the source processor transfers the data packet to its associated network node, ii) the packet is transferred from network node to network node until it reaches the destination network node, and iii) the packet is then transferred from the destination network node to its associated processor. All processor instruction and control transfers are outside the network and we do not consider them here. The design of the off-chip connections depends on the details of the design external to the chip and the particular 2 pin constraints of the chip’s package. Since this is very design specific we do not consider the details here, except to note that the off-chip connections are allowed for in our designs. While designs with (2N)2 nodes, and array of 2N on a side, may be easier to program than other sizes, our designs do not depend on any particular size. But, our simulated performance is only applicable for designs with the same number of nodes on each side. The following figure shows at a high level how such a chip might be organized. Processor Network Node Processor Network Node Processor Processor Network Node Processor Network Node Processor Network Node Processor Network Node Processor Network Node Figure 1 Sample Chip Organization 3 Network Node Because the processors and network nodes are on a single chip and arranged in a 2 dimensional array with short interconnections, the data transfer between one node to another is very fast. This, combined with the network nodes’ simple and efficient design, presents the opportunity for a design with a short cycle time, and therefore, high performance. The regular organization of the chip simplifies the design and testing of the actual implementation. We assume small fixed size packets and deterministic routing. The routers’ designs are allowed to take advantage of this particular environment whenever possible. The resulting routers are simple, low-cost, and suitable for parallel processor systems on a single substrate. We generally assume input buffering, but to be sure that we are not going down the wrong path, we also study a design that has output buffering. Output buffering has higher performance when considering network throughput per cycle, but the design is more complex and managing the buffer at the output results in a much longer critical path. To see whether the increase in throughput per cycle compensates for the increase in cycle time we evaluate a network with nodes with output queuing, similar to the IBM SP2 design [21], but which still taking advantage of our particular environment. 1.3 Previous Work Although there has been extensive work in the area of switch design and multiprocessor networks, relatively few studies include hardware costs, either in their effect on chip area or on operating frequency. Of the studies that do pay attention to cost, even fewer do so quantitatively, or for more than one particular implementation of a design. An exception is Chien [1, 6], who has performed a detailed hardware cost and operating frequency analysis for a particular class of routers in terms of the number of inputs or outputs, 4 number of virtual channels and routing freedom. But, this analysis does not account for some of the options we would like to consider such as virtual cut-through routing, unidirectional vs. bidirectional switches, the varying buffer sizes, dynamic buffer sharing between lanes and does not address the network performance achieved by varying these parameters. Another gap is that virtual cut-through switching has not been explored to nearly the extent of wormhole switching. This is especially important since even a preliminary glance at the problem of low-cost networks, points to virtual cut-through as a way of cutting down on the number of virtual channels and thereby getting more switch for your silicon. Some that do, Duato et al [x], do not perform a hardware cost analysis or have a design that is not suited for our particular environment. We are designing for an environment where the node to node delay is very small because the nodes are on the same chip and are placed adjacent or very near their communication neighbors. Little work has been done for this environment. (Even Dally’s Torus Routing Chip [10] had offchip delays between nodes and couldn’t operate faster than the off-chip and wire delays.) The Abacus SIMD Array [4] is one that uses network nodes on the same chip, but this network is much too simple for our purposes. Much work is done for nodes that are more featured and complex than we use. The SP2 is an example. Its design is more complex than we use and that makes the operating frequency lower than we are able to achieve. The SP2 design uses this complexity to increase its performance for its particular environment and this is good. The reason is that the SP2 has very long node to node delays and even with extensive pipelining one could not possibly achieve the small cycle times we do for our design. So the additional complexity probably does not affect the operating frequency. 5 And finally, there are just too many parameters. Even if you could try everything, the analysis would be prohibitive. In other words, the questions we need answers for had not been answered. 1.4 Methods Because our focus is how to build an embedded network for single chip coprocessors, we concentrate on low-cost, cost-effective mechanisms: The routing is deterministic dimension order. The topology is either a 2D mesh or torus. A single physical channel exists between nodes per direction per dimension. The packets are small and have fixed size, 6 and 24 flits in our experiments. These sizes approximate transfers of single words or cache lines. Even so, there are still a large number of router design options to consider: These include: • Whether the switching mode is wormhole (WH) or virtual cut-through (VCT) • Whether the connections are unidirectional or bidirectional • Whether the crossbars are full or cascaded • The optimal number of virtual lanes per channel. • The optimal FIFO buffer size. • Whether to share FIFO buffer space for more than 1 lane in the same RAM. We evaluate the design alternatives in terms of both the cost in chip area and the performance in terms of effect on network capacity and operating frequency. This requires using three different methods, which are now described. To determine network capacity, we use a cycle-driven simulator and simulate a network of reasonable size, 8 by 8. We determine network capacity by assigning injectors a fixed capacity (load) and run enough cycles to determine if the network saturates with this load. We believe our method is more representative of real systems, even if it requires more computer time per design. A simulation run consists of a single network type / load / routing pattern / packet size 6 combination. After performing multiple runs with different loads, we determine the network capacity in terms of flits/node/cycle. The routing patterns we use for performance evaluation are standard synthetic patterns: random, hot-spot, and near-random. To determine cell area we represent the designs in Verilog High-level Design Language, HDL, then perform logic synthesis targeting LSI Logic’s G10-p 0.18 micron technology. The logic synthesis package we use, from Synopsys, is very good at deriving a design with optimum cell area. Not all designs are evaluated completely; we take advantage of the hardware design’s modularity to evaluate some of the modules separately. For example, the number of ports in the output queue can be evaluated for many design points and a formula for cell area based on the number of ports generated. These formulas are used in the designs instead of generating a complete Verilog HDL for each design option. Combining these formulas yields a cell area for each design option. To determine cycle time, the designs are evaluated and critical paths determined manually. The logic design involving these critical paths is done by hand and timed using gate delay for the target technology. We do this manually because the logic synthesis package we use, from Synopsys, is not very good at deriving a design with optimum timing. 1.5 Results The results we present in this thesis include some key observations about virtual cut-through routing, performance of the designs with a cycle-driven simulator, router cell area, and router cycle time analysis. The results presented show the effect of these options on the routers’ cell area and cycle timing when mapped into a current generation 0.18 micron technology, LSI Logic’s G10-p Cell-Based ASIC technology. This work adds to previous studies in that it accounts for: 7 • Variations in the number of lanes in the VCT configurations. • Not only bidirectional tori, but meshes and unidirectional tori are considered. • Deadlock and timing considerations unique to VCT. • Static virtual channel selection versus dynamic lane selection methods. • Both physical properties, such as critical path timing and layout area, and latency/bandwidth results from register transfer level simulations. Some of the key results we present are: • Lanes are as useful to VCT networks as they are to wormhole networks. • When operating frequency is factored in, increasing the number of lanes beyond 2 per physical channel is not likely to be cost effective. • For equal numbers of buffers and space per buffer, VCT switching is likely to have better performance than WH switching. The reason is that the space guarantee associated with VCT switching is easy to implement for small packets and has powerful consequences in load balancing among lanes and, to a lesser extent, flow control latency. • All the designs described are evaluated with respect to area/performance for each workload and the cost-effective ones enumerated. While investigating the design framework, it was necessary to work out some issues that are themselves contributions. These are: • Observations about VCT deadlock and how to prevent it. • The application of virtual channel load balancing to unidirectional WH torus networks. 1.6 Significance Our designs take advantage of many of the characteristics of single chip parallel systems and our results are directly applicable to the environment of our primary interest, single chip parallel systems. We believe our results also provide useful insight into other, more general, design 8 areas including SIMD and distributed shared memory. While our designs are mapped to a current technology for evaluation in this paper, we believe the results will be applicable to future ASIC technologies. Although we show the results in tabular form, the equations we have generated for cell area allow network designers to determine some characteristics for designs that have slightly different options than the particular ones we have chosen. For example, it is a simple matter to determine the cell area of a router with a different buffer size, flit size, or crossbar matrix than what we present here. 1.7 Outline The rest of the thesis is organized as follows: 9 2 Design Space We now present the details of our network design space. Since some of the configurations are new and others have non-trivial motivation, we also discuss deadlock in wormhole, WH, and virtual cut-through, VCT, networks and virtual channel selection in WH networks. We end this section with an analysis of the design consequences of the choice between WH and VCT switching. 2.1 Basic Network Assumptions and Parameters Any parameter study, especially one on such a well-studied area as switch design has to be constrained. These constraints are critical since you will never solve everybody's problem! Of course, the constraints also have to be credible since all aspects of the design need to be reasonable if you are going to analyze any particular feature. We divide the parameter space into three categories: 1. The immediate constraints and assumptions following immediately from our domain. 2. The derived decisions which followed from a small amount of analysis or experimentation. 3. The parameters we measured. 2.1.1 Immediate Constraints and Assumptions 1. We have constrained our designs to only have two dimensions. The nodes we are connecting are not boxes or boards to be wired together with copper, but rather, on-chip modules. A two dimensional topology is significantly less expensive, in terms of chip area, because a chip is built in two dimensions. 2. The area used by our network node matters. Although we have much more chip area than, say, Dally did when designing the Torus Routing Chip, we do have a constraint: the more space we spend on the routers, the fewer the processors we can fit on the chip. 10 3. The communication modes we will support are fine-grained message passing and dataparallel communication operations. 4. Our packets are small and fixed size. A packet is made up of N data plus 2 address 8-bit flits. A packet’s route is determined at the source processor before the packet is inserted into the network. Two address flits are pre-pended to the packet. These address flits contain the X and Y destination nodes and the direction the packet is to take to get to these nodes. 7 + + 6 - 5 Next Next 4 3 2 1 X Node Destination Y Node Destination Data flit 0 Data flit 1 • • • Data flit N-1 0 Where + and - indicate which direction to go when entering the X dimension or the Y dimension. And Next indicates that the address will match at the next node and a turn should take place. Figure 2 Packet Structure 5. When a packet travelling in the X dimension reaches its X node destination, the X node destination flit is removed from the packet and the Y node destination flit becomes the packet’s first flit. When the Y destination node is reached, the Y node destination flit is removed and only the data flits are forwarded to the destination processor. 6. Our analysis strives for reasonable technology independence. Since we do not know what the technology will be when these results are used, nor what our timing and area constraints will be, we want to make our study at least moderately technology independent. We have mapped our designs into a standard CMOS 0.18 micron technology. This should be representative, with scaling, of ASIC technologies for some time. 11 7. The entire network operates on a single clock. Single chip clock distribution is very well understood and clocked systems are simpler than unclocked systems. Bolotski, et. al. present several novel techniques for dealing with this [4]. 8. The inter-switch transfer time is on the order of the switch time or smaller. Because our switching nodes are on the same chip and our routing is mesh or torus, the distance, and therefore the transfer time, between nodes is very small. 9. The header flit takes two cycles while the other flits take one cycle to traverse the switch. This constraint turns out to be a good balance between minimizing slack and keeping the number of cycles to a minimum. Although this constraint is not “immediate” and will be discussed further below, we introduce it here since it has fundamental design implications. 2.1.2 Derived Issues Topology Our prime directive of working in two dimensions eliminates all topologies but one-dimensional and two-dimensional meshes as the longer wire lengths for the other choices cannot be justified, especially if there is any locality at all in the communication. This decision will only be truer with advancing process technology causing wires to cause an increasing fraction of the delay. Because the design is intended for parallel processors on a single chip substrate, the designs are simple and low-cost. The network structure is either two dimensional mesh or torus. Each node has one physical channel connection to each neighboring node for each direction. The physical channel is 1 flit, 8 bits, wide with extra handshaking signals. A router node is associated with each processor, and that processor has separate input and output channels to the node. All nodes are considered identical, except for the nodes’ particular address. There is no attempt to simplify any particular node, e.g. edge or corner nodes. The following figure shows a portion of a sample network. 12 P Y- in Y- out X- in X- out P Y- in Y- out X+ out X- in X+ in Y+ out Y+ in X+ in P X- out X+ out X+ in Y+ out Y+ in X+ in Y+ out Y+ in P Y- in Y- out X+ out X- out X- in X+ in X- out Y+ out Y+ in P X- out X+ out P X- in X+ in Y+ out Y+ in X- in X- out Y- in Y- out X+ out Y- in Y- out X- in Y+ out Y+ in Y- in Y- out X- in Y- in Y- out X+ out X- out P X+ out X+ in Y+ out Y+ in P Y- in Y- out X- in X+ out X- out X+ in Y+ out Y+ in P Y- in Y- out X- in X- out X+ out X+ in Y+ out Y+ in Figure 3 Portion of a sample network, bidirectional virtual cut-through Routing Algorithm The constraints applicable here are: • a two dimensional mesh, • minimize area cost, and • small fixed sized packets. The standard choices in routing are between dimension order, random, and adaptive, and all their combinations. The problem with all methods other than dimension order routing is that they cause some additional complexity and so may slow down the clock, cause an increase in area, or both. Although for the simplest random algorithm this is perhaps not true since all the computation can be overlapped. But a more important reason is that dimension order routing causes packets to make the fewest possible turns and turns in two dimensions can cause more congestion than they alleviate. We still have a bit to learn about adaptive algorithms, but Leighton's classic result for store-and- 13 forward is persuasive [17]. While single shot dimension order routing causes virtually no congestion with very high probability, random shortest path causes O(log N) slowdown with very high probability. Because the places where blocking is initiated tend to be where packets try to turn but can't. For small packets and non-trivial buffers, this result applies here as well. We therefore use dimension order routing. Buffering Mechanism We use input buffering and its multi-lane variations exclusively. This is not because output buffering is not effective; it is just not optimal for everything. Output buffering carries more inherent overhead than does input buffering which you can hide completely with long packets and long inter-switch transfer times, but not with short packets and short inter-switch transfer times. We therefore use input buffering with space sharing. Crossbar There is a choice between single and cascaded crossbars. To make the decision, we performed timing and simulation studies which can be summarized as follows: for two dimensional meshes with small numbers of lanes per channel, it does not make much difference. We use cascaded crossbars because they have a faster operating frequency. 2.1.3 Measured Issues Switching mode We consider two switching modes, wormhole, WH, and virtual cut-through, VCT, in our designs. A few points however: 1. The only real difference between wormhole and virtual cut-through, is that in virtual cutthrough, the receiving node provides a guarantee that, if it receives the packet header, it can receive the rest of the packet. 14 2. As a consequence, deadlock prevention is significantly easier in virtual cut-through since preventing deadlock in wormhole routing likely to require using virtual channels. However, beyond these basic differences, they have much in common: 3. For a given buffer size, as long as there is enough space to provide the space guarantee, the buffer size choice in virtual cut-through is not constrained. 4. A similar point for can be made for virtual channels (or lanes) in wormhole routing: once you have enough to prevent deadlock, there are no more constraints. Nor are there ever constraints on lanes in virtual cut-through, again, as long as the space guarantee can be provided. 5. For our domain with small fixed sized packets, the basic hardware support between wormhole and virtual cut-through is nearly identical. 6. VCT has fewer constraints on virtual channel selection. We discuss this in section 2.3. Virtual Channel Selection in Wormhole Switching A very important issue in getting decent performance out of an input buffered wormhole routing network is virtual channel selection. In an early work on virtual channels, Dally proposed the following selection algorithm, all packets that can proceed to their destination (in the dimension) without wraparound use virtual channel 0 while the others use virtual channel 1 until the wraparound point at which time they transfer to channel 0 to complete the route [11]. Bolding noticed that this algorithm leads to an extreme imbalance in buffer usage [2]. It turns out that distributing the load between virtual channels is very important and Scott and Thorson have a very effective way of addressing this problem for bidirectional torus networks with the introduction 15 of datelines and off-line channel selection [20]. We have extended this idea to unidirectional torus networks. The method is a straightforward extension of the bidirectional technique with the exception that no pair of datelines exists such that all packets cross at most one dateline. We address this problem by requiring packets that cross both datelines to switch channels once. This is not as elegant a solution as is available in the bidirectional case, but provides for a substantial improvement in load balance between channels. The initial load imbalance is shown in Table 1 and the load imbalance after the application of the T3D technique is shown in Table 2. We have also made one change to the basic T3D technique. We perform inter-dimension channel selection dynamically and based on availability. Since the inter-dimensional channels do not form a ring, this does not alter the deadlock properties of the network. It does, however, improve network capacity by 3 to 5%. Another critical point is that this load balancing assumes a uniform communication pattern. It is not necessarily optimal for other patterns. The reason why this is so important here, and this is one of the key results of this work, is that virtual cut-through does not have this problem since deadlock considerations do not play a role in lane selection. Table 1 Load imbalance in the standard virtual channel selection algorithm for the unidirectional wormhole torus. Virtual channel 0 is the wrap-around channel and virtual channel 1 is the direct channel. The counts indicate the number of sourcedestination paths that go through the particular channel in each node. Virtual channel 0 1 Imbalance Node 0 1 2 3 4 5 6 7 0 28 1.0 0 28 1.0 1 27 .93 3 25 .79 6 22 .57 10 18 .28 15 13 .07 21 7 .5 16 Average Imbalance Max Imbalance .64 1.0 Table 2 Load imbalance in the T3D-inspired virtual channel selection algorithm for the unidirectional wormhole torus. Virtual channel 0 has node 0 as a dateline and virtual channel 1 has node 4. Virtual channel 0 1 Imbalance Node 0 1 2 3 4 5 6 7 7 21 .50 9 19 .26 13 15 .07 16 12 .14 21 7 .50 19 9 .26 15 13 .07 12 16 .14 Average Imbalance Max Imbalance .24 .50 Crossbar Switches The choice of switching mode also affects the crossbar. Here is an example of the crossbar matrices for two lane wormhole node and a four lane virtual cut-through node. Since there are fewer constraints on virtual channel selection in virtual cut-through, there are more possible lane choices and therefore more crosspoints. It turns out that this is not a bad thing. In comparison to the space we are going to spend on buffering and because of the regular shape, the difference between being 5/9ths and 7/9ths full is less than 1% of the total switch area. 17 P0a P0a P1a P1b X0+a X0+b X1+a X1+b X0-a X0-b X1-a X1-b X0+a X1+a X0-a X1-a C0a C1a X0+b X1+b X0-b X1-b C0b C1b Y0+a Y0+b Y1-a Y1-b Y0+a Y0+b Y1-a Y1-b Y0+a Y1+a Y0-a Y1-a P0a P1a Y0+b Y1+b Y0-b Y1-b P0b P1b Pa Pb Pc Pd X+a X+b X+c X+d X-a X-b X-c X-d X+a X+c X-a X-c Ca Cc X+b X+d X-b X-d Cb Cd Y+a Y+b Y+c Y+d Y-a Y-b Y-c Y-d Y+a Y+c Y-a Y-c Pa Pc Y+b Y+d Y-b Y-d Pb Pd Figure 4 Crossbar comparison for WH (top) and VCT (bottom) Which 2D Topology? The choices are between unidirectional and bidirectional mesh and between mesh and torus. The advantage of the mesh is that it by itself prevents deadlock and so allows you to do 18 wormhole routing without virtual channels. Tori can be constructed without long wires by using the standard interleaving trick. In other words, whatever virtual channels you do have, the selection can be completely dynamic depending only on which one is free. The idea of the unidirectional mesh makes sense in this context since even if it does lead to a great deal of congestion, it can have double the internode bandwidth and much smaller internal buffering. Lanes for Performance There have already been many studies that point to the benefits of having multiple lanes per channel. The reason is because, as is shown below, they allow packets to avoid being blocked. We investigate one, two, and four lanes per virtual channel. Figure 5 Packets A, dark shade, and B, light shade, are traveling in the X dimension, but are blocked because packet A can’t turn into a busy Y dimension, black shade. 19