|
|
|
|
|
|
|
7. Suppose processor bus traffic consists of three types of line accesses (CBWA): lI, for instruction line accesses, lDL for data line access used locally, and lSH for shared data line accesses. Find an expression for the bus traffic for N processors for |
|
|
|
 |
|
|
|
|
(a) A "write-invalidate" protocol. |
|
|
|
|
|
|
|
|
(b) A "Firefly" protocol. |
|
|
|
|
|
|
|
|
Assume invalidate increases affected traffic by a factor a. Discuss conditions (relative parameter values) where one would select each protocol. |
|
|
|
|
|
|
|
|
8. Evaluate the effect of the bus model with resubmissions and without resubmissions by evaluating problem 5(c) with both models. |
|
|
|
|
|
|
|
|
9. Suppose we have a baseline network using 4 ´ 4 crossbar switches interconnecting 1,024 nodes. Assume l = 200 bits (both for request and reply), w = 16 bits, and h = 1 (wormhole routing through the switch). |
|
|
|
|
|
|
|
|
(a) How many stages are required? |
|
|
|
|
|
|
|
|
(b) What is the delay in cycles without network contention for a request to be serviced, time to go to a destination node, arrive there completely and return completely? |
|
|
|
|
|
|
|
|
(c) If m (the probability that a node makes a request or reply in a cycle) is m = 0.015, repeat (b) now including switch contention effects (i.e., queueing delays). |
|
|
|
|
|
|
|
|
10. Our treatment of dynamic network delays utilizes an MB/D/1 openqueue model. This assumes that request traffic initiated by a node is insensitive to network delay. Find an MB/D/1 closed-queue model for a dynamic network switch. |
|
|
|
|
|
|
|
|
11. Suppose we have a direct static 32 ´ 32 = 1,024 node network (bidirectional links) arranged as a 2D torus. If l = 200, w = 32, and h = 1, |
|
|
|
|
|
|
|
|
(a) What is the expected distance (number of hops between nodes)? |
|
|
|
|
|
|
|
|
(b) What is the expected delay for a message (source to destination and return, see problem 9b) without contention? |
|
|
|
|
|
|
|
|
(c) Assume m, the probability that a node makes a request or reply in a cycle, is M = 0.015. What isTw per node? |
|
|
|
|
|
|
|
|
(d) What is the total expected delay (as in part b), now including queueing delay? |
|
|
|
|
|
|
|
|
12. Discuss the relative advantage of update and invalidate protocols for bus-based shared memory multiprocessors. |
|
|
|
|
|
|
|
|
13. Discuss the relative advantages of update and invalidate protocols for multi-node switched shared memory multiprocessors. |
|
|
|
|
|
|
|
|
14. Researchers [64, 6] have noted that cycle time or network "hop" time depends on wire length. Higher-dimensional networks have larger "worst-case" wire delay when implemented in two dimensions than |
|
|
|
|
|