Computer Architecture A Quantitative Approach PDF

Preview

Summary

Computer Architecture ...

Description

1

Solutions to Exercises for Appendix E in Computer Architecture: A Quantitative Approach, 4th Edition c Wai Hong Ho and Timothy Mark Pinkston  Interconnects Group University of Southern California

E-1 Refer to “Computer Architecture: A Quantitative Approach (3rd Edition)” Chapter 8 solutions for Problem 8.9. E-2 Refer to “Computer Architecture: A Quantitative Approach (3rd Edition)” Chapter 8 solutions for Problem 8.10. E-3 Refer to “Computer Architecture: A Quantitative Approach (3rd Edition)” Chapter 8 solutions for Problem 8.11. E-4 Refer to “Computer Architecture: A Quantitative Approach (3rd Edition)” Chapter 8 solutions for Problem 8.12. E-5 Refer to “Computer Architecture: A Quantitative Approach (3rd Edition)” Chapter 8 solutions for Problem 8.13. E-6 Refer to “Computer Architecture: A Quantitative Approach (3rd Edition)” Chapter 8 solutions for Problem 8.1. E-7 Refer to “Computer Architecture: A Quantitative Approach (3rd Edition)” Chapter 8 solutions for Problem 8.2. E-8 Refer to “Computer Architecture: A Quantitative Approach (3rd Edition)” Chapter 8 solutions for Problem 8.3. E-9 Refer to “Computer Architecture: A Quantitative Approach (3rd Edition)” Chapter 8 solutions for Problem 8.4. E-10 Refer to “Computer Architecture: A Quantitative Approach (3rd Edition)” Chapter 8 solutions for Problem 8.18. E-11 At each stage of an Omega network, the address of the output port is equal to the address of the input port shifted left by one bit with the lowest order bit replaced by a bit from destination address, starting from highest order bit for the first stage, and so on. Therefore, the output ports at each stage can be obtained by constructing a sliding window of width n across the concatenated source and destination address. Conflicts occur if the addresses of output ports

0

Source 0 0

Destination 0 0 0

0

Destination 0 0 0

0

0

1

1

0

0

0

0

1

1

0

0

0

1

0

0

1

0

0

1

0

0

1

0

0

1

1

1

1

0

0

1

1

1

1

0

1

0

0

0

0

1

1

0

0

0

0

1

1

0

1

1

0

1

1

0

1

1

0

1

1

1

0

0

1

1

1

1

0

0

1

1

1

1

1

1

1

1

1

1

1

1

1

1

(a) Fig. 1.

Source 0 0

(b)

Sliding windows showing the output ports required at: (a) the first, and (b) second stage of an Omega network for the

bit-reversal permutation.

as identified by the sliding windows are not unique in any of the stages. It can be easily seen that for any permutation communication patterns where destination addresses are unique, there can be no conflicts at the third stage. Thus, we need to consider conflicts only in the first and second stages. a. Bit-reversal permutation reverses the order of the bits. For an 8-node network, node with address a2 , a1 , a0 sends to node with addresss a0 , a1 , a2 . Figure 1 shows the sliding windows for the source and destination addresses. There are conflicts in both the first and second stages as indicated in the figure. Therefore, the permutation pattern can not be realized using the Omega network. b. For the perfect shuffle permutation, input with address a2 , a1 , a0 sends packets to output with address a1 , a0 , a2 . Figure 2 shows the sliding windows for the first and second stages. As indicated in the figure, there are conflicts in both stages meaning that the perfect shuffle permutation pattern cannot be realized in the Omega network. c. For the bit-complement permutation, input with address a2 , a1 , a0 sends packets to output with address a2 , a1 , a0 . Figure 3 shows the sliding windows for the first and second stages. There are no conflicts in the first and second stage as shown in the figure. Since there cannot be any conflicts in the third stage, the bit-complement permutation is realizable in an 8-node Omega network. d. For the butterfly permutation, the first and last bit are swapped, which means input with address a2 , a1 , a0 sends packet to output with address a0 , a1 , a2 . That is the same as the bit-reversal permutation for an 8-node network. From the results in part (a), we can conclude that the butterfly permutation is not realizable. e. Since there are an odd number of bits in the address of an 8-node network, there are two ways in which we can divide the address for the matrix transpose permutation. 2

0

Source 0 0

Destination 0 0 0

0

Source 0 0

0

0

1

0

1

0

0

0

1

0

1

0

0

1

0

1

0

0

0

1

0

1

0

0

0

1

1

1

1

0

0

1

1

1

1

0

1

0

0

0

0

1

1

0

0

0

0

1

1

0

1

0

1

1

1

0

1

0

1

1

1

1

0

1

0

1

1

1

0

1

0

1

1

1

1

1

1

1

1

1

1

1

1

1

(a) Fig. 2.

Destination 0 0 0

(b)

Sliding windows showing the output ports required at: (a) the first, and (b) second stage of an Omega network for the

perfect shuffle permutation.

0

Source 0 0

Destination 1 1 1

0

Destination 1 1 1

0

0

1

1

1

0

0

0

1

1

1

0

0

1

0

1

0

1

0

1

0

1

0

1

0

1

1

1

0

0

0

1

1

1

0

0

1

0

0

0

1

1

1

0

0

0

1

1

1

0

1

0

1

0

1

0

1

0

1

0

1

1

0

0

0

1

1

1

0

0

0

1

1

1

1

0

0

0

1

1

1

0

0

0

(a) Fig. 3.

Source 0 0

(b)

Sliding windows showing the output ports required at: (a) the first, and (b) second stage of an Omega network for the

bit-complement permutation.

We can divide the address a2 , a1 , a0 into a2 and a1 , a0 , or into a2 , a1 and a0 . For the first partition method, the destination address is a1 , a0 , a2 . For the second method, the destination address is a0 , a2 , a1 . Figure 4 shows the sliding windows for both cases. As indicated in the figure, there are conflicts in the first and second stages for both cases, meaning that none of them are realizable by the Omega network. f. The barrel shift permutation specifies that a source node with address i communicates with a destination node with address (i + 1) mod N . The communication pattern and the sliding windows are shown in Figure 5. As shown in the figure, there is no conflicts in both stages. Therefore, the permutation is realizable for the Omega network. E-12 Refer to “Computer Architecture: A Quantitative Approach (3rd Edition)” Chapter 8 solutions for Problem 8.19. E-13 Refer to “Computer Architecture: A Quantitative Approach (3rd Edition)” Chapter 8 solutions 3

0

Source 0 0

Destination 0 0 0

0

Source 0 0

Destination 0 0 0

0

0

1

0

1

0

0

0

1

0

1

0

0

1

0

1

0

0

0

1

0

1

0

0

0

1

1

1

1

0

0

1

1

1

1

0

1

0

0

0

0

1

1

0

0

0

0

1

1

0

1

0

1

1

1

0

1

0

1

1

1

1

0

1

0

1

1

1

0

1

0

1

1

1

1

1

1

1

1

1

1

1

1

1

(a)

0

Source 0 0

(b) Destination 0 0 0

0

Source 0 0

Destination 0 0 0

0

0

1

1

0

0

0

0

1

1

0

0

0

1

0

0

0

1

0

1

0

0

0

1

0

1

1

1

0

1

0

1

1

1

0

1

1

0

0

0

1

0

1

0

0

0

1

0

1

0

1

1

1

0

1

0

1

1

1

0

1

1

0

0

1

1

1

1

0

0

1

1

1

1

1

1

1

1

1

1

1

1

1

1

(c)

(d)

Fig. 4. Sliding windows showing the output ports required at: (a) the first and (b) second stage of an Omega network for the matrix transpose permutation a1 , a0 , a2 . Also showing (c) the first stage and (d) the second stage for the matrix transpose permutation a0 , a2 , a1 .

0

Source 0 0

Destination 0 0 1

0

Source 0 0

Destination 0 0 1

0

0

1

0

1

0

0

0

1

0

1

0

0

1

0

0

1

1

0

1

0

0

1

1

0

1

1

1

0

0

0

1

1

1

0

0

1

0

0

1

0

1

1

0

0

1

0

1

1

0

1

1

1

0

1

0

1

1

1

0

1

1

0

1

1

1

1

1

0

1

1

1

1

1

1

0

0

0

1

1

1

0

0

0

(a)

(b)

Fig. 5. Sliding windows showing the output ports required at: (a) the first, and (b) second stage of an Omega network for the barrel shift permutation.

4

for Problem 8.20. E-14 Refer to “Computer Architecture: A Quantitative Approach (3rd Edition)” Chapter 8 solutions for Problem 8.21. E-15 Refer to “Computer Architecture: A Quantitative Approach (3rd Edition)” Chapter 8 solutions for Problem 8.22. E-16 Refer to “Computer Architecture: A Quantitative Approach (3rd Edition)” Chapter 8 solutions for Problem 8.17. E-17 Assume the number of nodes equals N . Also assume that all links are bidirectional links and that k × k switches are used for each of the following networks, except for the bus and ring. •

Bus: A bus network is a shared medium network. Therefore, its bisection bandwidth, and maximum/average hop count remains the same independent of network size. The bisection is one. The maximum and average hop count are both one. Each end node has a link connecting to the bus and the bus network consists of only the one shared medium link, giving a total of N + 1 links. The bus does not contain any switches.

•

Ring: A ring network connects the nodes in the network in a ring structure that grows with network size. However, a ring can always be broken down into two fragments by removing two links. Therefore, the bisection bandwidth is always two. A packet needs to travel at most half of the ring in order to get to its destination (assuming bidirectional), meaning that the maximum hop count is N/2. The average hop count is half of that, which is equal to N/4, because the number of nodes reachable by a certain hop count is evenly distributed. A ring network contains switches with 3 links connecting to the end-node and two adjacent nodes. Number of switches is equal to the number of nodes. The number of network links is N while the total number of links is 2N , which includes links connecting the end nodes to the network.

•

Mesh: For a mesh network with k × k switches, the number of dimensions, n, can be found by using the relationship 2n + 1 = k or n = (k − 1)/2 since each switch contains 2 links along each dimension and 1 link connecting the end-node. Therefore, the number of nodes along each dimension, m, is m = N 1/n = N 2/(k−1) . The bisection of a mesh cuts accross one of the dimension to divide the nodes into two sets with equal number of nodes. Since there are 1/m of the nodes along that dimension at each side of the bisection, the number of links going across the bisection is equal to N/m = N 1−2/(k−1) .

5

A packet needs to travel all the way across each and every dimension in the worst case to reach its destination. Therefore, the maximum hop count is n × (m − 1) = (k − 1)(N 2/(k−1) − 1)/2. On average, a packet needs to travel half of each dimension, which means the average hop count is about half of the maximum hop count. The number of ports is obviously k and the number of switches is equal to the number of nodes, N . Due to the lack of wrap around, the number of links along each dimension is (m − 1)mn−1 . Therefore, the number of network links is n(m − 1)mn−1 = n(m − 1)N/m = (k − 1)(N 2/(k−1) − 1)N 1−2/(k−1) /2. The total number of links is equal to the number of network links above plus the number of links connecting to end-nodes (N of these). •

Torus: Torus networks differ from mesh networks only by the wrap-around links. The number of dimensions, n, and the number of nodes along each dimension, m, is the same as those of mesh networks. The number of links cut by the bisection, however, is doubled due to the wrap-around links. Packets can travel through the wrap-around links to get to the other side of the torus. Therefore, the maximum number of hops per dimension is only half the number of nodes along that dimension. The maximum hop count is, therefore, equal to nm/2 = (k − 1)N 2/(k−1) /4. The average hop count is half of that. The number of ports per switch is k and the number of switches equals the number of nodes N . Since each switch is connected to exactly two adjacent nodes in each dimension, the number of network links is simply nN = (k − 1)N/2. The total number of links is nN + N = (k + 1)N/2.

•

Hypercube: For hypercubes with k × k switches, there is one link connecting the end-nodes and k − 1 links (one for each dimension) for each switch. The size of the network, N , is equal to 2(k−1). The bisection cuts all the links along one dimension. Since there are as many links that cross the bisection as there are nodes in one of the partitions, the bisection width is N/2. The maximum hop count occurs for packets that needs to be forwarded in all dimensions, which means it is equal to (k − 1). The average hop count is half that, or (k − 1)/2. The number of ports per switch is equal to k and the number of switches equals the number of nodes N . Each switch is connected to k − 1 other switches. Therefore, the number of network links equals (k − 1)N/2. The total number of links is the number of network links plus the number of links connecting to the end-nodes, which sum up to (k + 1)N/2.

•

Fat tree: 6

Assume half of the ports are going toward the root and half of the ports are going toward the leaves. The number of stages required for a fat tree network is logk/2 N . The bisection cuts through the links connecting between the last stage and the second-to-last stage. Half of the links of a switch in one of the partitions connects to switches in the other partition, and there are N/2k switches for each of the last and the second-to-last stages in each partition. We can conclude that the number of links crossing the bisection is k/2 × N/k = N/2. In the worst case, a packet must travel from the first stage to the last stage and then back to the first stage to reach its destination. The maximum number of hops is two times the number of stages minus one, which is 2 logk/2 N − 1. The average hop distance, unlike other networks, does not equal half of the maximum number of hops. Consider the second to last stage: k/2 − 1 out ...