tailieunhanh - PRINCIPLES OF COMPUTER ARCHITECTURE phần 8

(b) Tính toán tỷ lệ hit cho một chương trình vòng 10 lần từ các địa điểm 15 - 200. Lưu ý rằng mặc dù bộ nhớ được truy cập hai lần trong một bỏ lỡ (một lần cho nhớ, và một lần nữa để đáp ứng các tài liệu tham khảo), một hit không xảy ra cho trường hợp này. | CHAPTER 10 TRENDS IN COMPUTER ARCHITECTURE 437 a c d b f g h Figure 10-15 Network topologies a crossbar b bus c ring d mesh e star f tree g perfect shuffle h hypercube. Figure 10-16 Internal organization of a crossbar. At the other extreme of complexity is the bus topology which is illustrated in Figure 10-15b. With the bus topology a fixed amount of bus bandwidth is shared among the PEs. The crosspoint complexity is N for N PEs and the network diameter is 1 so the bus grows more gracefully than the crossbar. There can 438 CHAPTER 10 TRENDS IN COMPUTER ARCHITECTURE only be one source at a time and there is normally only one receiver so blocking is a frequent situation for a bus. In a ring topology there are N crosspoints for N PEs as shown in Figure 10-15c. As for the crossbar each crosspoint is contained within a PE. The network diameter is N 2 but the collective bandwidth is Ntimes greater than for the case of the bus. This is because adjacent PEs can communicate directly with each other over their common link without affecting the rest of the network. In the mesh topology there are N crosspoints for N PEs but the diameter is only 1JN as shown in Figure 10-15d. All PEs can simultaneously communicate in just 3a N steps as discussed in Leighton 1992 using an off-line routing algorithm in which the crosspoint settings are determined external to the PEs . In the star topology there is a central hub through which all PEs communicate as shown in Figure 10-15e. Since all of the connection complexity is centralized the star can only grow to sizes that are bounded by the technology which is normally less than for decentralized topologies like the mesh. The crosspoint complexity within the hub varies according to the implementation which can be anything from a bus to a crossbar. In the tree topology there are N crosspoints for N PEs and the diameter is 2log2N - 1 as shown in Figure 10-15f. The tree is effective for applications in which there is a great deal of .