|
|
|
|
|
|
|
are buffered at intermediate nodes, hence removing them from the network. With the wormhole routing, if the node C were busy, the message would be blocked at B and the channel between A and B would be occupied until the node C was free. With virtual cut-through, the channel between A and B is available as soon as the message is transmitted to and buffered at B. |
|
|
|
|
|
|
|
|
While the above schemes govern the flow of packets in the network, the routing algorithm determines the actual path messages take. These can be deterministic (packets follow a fixed path, depending entirely on the source and destination addresses) or adaptive (the paths taken by packets are selected by intervening nodes, based on local network congestion as well as current and destination addresses). |
|
|
|
|
|
|
|
|
The message to be transmitted between two nodes contains data and a header. The header is simply the address of the destination node. Once the header is decoded at an intermediate node, that node can determine whether the message is for it or for another node. The intermediate node selects a minimum distance path to the destination node. If multiple paths have the same distance, then this intermediate node will select the path that is currently unblocked or available to it. If multiple paths are unblocked, it can select a path either according to a schedule or randomly. |
|
|
|
|
|
|
|
|
Dynamic networks are usually indirect, which we assume in this discussion. The processor and presumably some local memory are separated from the switching mechanism which forms the interconnection network. The shared global memory may be located as separate nodes or may be included in processor-local memory nodes. In the latter case, each processor node includes its local memory and a fraction of the global memory. Thus, there can be three separate access times for the processor to access an item in memory: |
|
|
|
|
|
|
|
|
1. The access time for local memory. |
|
|
|
|
|
|
|
|
2. The access time for that portion of global memory which is located at the node (this could be rather similar to the access time for local memory). |
|
|
|
|
|
|
|
|
3. Access time to global memory that is not part of the node. |
|
|
|
|
|
|
|
|
The dynamic indirect network is shown in Figure 8.50a. For ease of representation, the network is usually shown as in Figure 8.50b. The access time to global memory that is not part of the processor node is generally uniform across all portions of the global memory (ignoring traffic-based contention). |
|
|
|
|
|
|
|
|
Usually, the basic element in the dynamic network is a crossbar switch (Figure 8.51). The crossbar simply connects one of k points to any of another k points. Multiple messages can be concurrently executed across the crossbar switch, so long as two messages do not have the same destination. The cost of the crossbar switch increases as n2, so that for larger networks, use of a crossbar switch only becomes prohibitively expensive. In order to contain the cost of the switch, we can use a small crossbar switch as the basis of a |
|
|
|
|
|