Homework 6

22C:122, Spring 1998

Due Wednesday Apr 10, 1997, in class (or sooner, if you wish)

1. Consider the problem of building a crossbar switch.

              |   |                       Addr --o-------o-----|--|--
      CPU ----X---X--                            |       |     |  |
              |   |          |            Data --|-------|--o--|--|--
      CPU ----X---X--  Each -X- becomes:         |       |  |  |  |
              |   |          |                decode -- enable |  |
              |   |                                      |  |  |  |
             MEM MEM                                     |   --|--o
                                                          -----o  |
                                                               |  |
   

   This is oversimplified! The problem is that it does nothing to account for the possibility that two CPU's might simultaneously request service from the same memory module at the same time!

   To solve this problem, each crossbar contact (X in the figure) must include bus arbitration logic. Each CPU, in addition to the Address and Data lines, also provides a bus-request signal, and the memory, when addressed and before the start of the actual memory operation, must supply a request-acknowledged signal. If the arbitration logic at a crossbar intersection detects that there are conflicting requests, it must only acknowledge one of them!

   Assume that the CPU's operate synchronously (with a common clock, so that all requests are posted at the same time), and assume that a CPU enters wait states until it receives a request acknowledge signal. Suggest a design for the arbitration logic at each crossbar contact. (Under these constraints, it only takes a few logic gates to do this!)

2. Consider a system where there is a choice between using a fully associative TLB, and a 2-way set-associative TLB with automatic LRU management. Assume that the competing designs involve the same address format -- 10 bits of "segment number" and 10 bits of "page in segment".

   Part A: How much silicon would you expect the two designs to require? Estimate this by assuming that one RAM cell is the same size in both cases (3 gates), but that an associative cell takes an additional 4 gates for comparison. Gate counts, of course, are your measure of silicon, and you can ignore the decoding and other external logic.

   Part B: What difference in hit rates would you expect from these two designs. Assume LRU replacement in both cases, and assume that the reference string is completely random over the series of 20 bit addresses -- you may want to construct a simple simulation model to answer this question!