ECS154A Homework #3

• Lab assignments due by 11:59PM on Tuesday, July 29th. Submit your assignment via Smartsite. You can use at most 1 late day for this assignment.
• Written homework due by 4:00PM on Wednesday, July 30th.
  

LAB Assignment:

• Build an entire fully functional 32-bit computer, using only twigs and bits of string.

OR

• See lab3program.pdf

WRITTEN Assignment:

1. In class we presented a 1-bus version of a CPU, and then a 3-bus version. Why did we bother? What is the advantage of using 3 busses?
2. In class we presented a basic CPU, and discussed the many changes to the hardware that must be made in order to support interrupts ... list 4 of them.
3. Assume that in the Daisy-chained arrangement we discussed in class the processor keeps asserting BusGrant (BG) as long as BusRequest (BR) is asserted. When device i is requesting the bus, it becomes the bus master only when it receives a low-to-high transition on its BusGrant (BGi) input.
   
   
   a. Assume that devices are allowed to assert the BusRequest signal at any time. Give a sequence of events to show that the system can enter a deadlock situation, in which one or more devices are requesting the bus, the bus is free, and no device can become the bus master.
   
   
   
   b. Suggest a rule for the devices to observe in order to prevent this deadlock situation from occuring.
   
   
   
4. How would the timing in an asynchronous bus be affected if the distance between the processor and the I/O device is increased? How can this increased distance be accomodated in the case of a synchronous bus?
   
   
5. Here is a string of hex address references given as byte addresses:
   
   1,2,3,1A,A,1B,16,14,3,12,9,23,3A,5,19,1,9
   
   
   a. Assuming a direct mapped cache with 16 one-byte blocks that is initially empty, label each reference in the list as a hit or miss and show the final contents of the cache tag array. Compute the hit rate for this example.
   
   
   b. Show the hits and misses and final cache contents for a direct mapped cache with four-byte blocks (lines) and a *total* size of 16 bytes. Compute the hit rate for this example.
   
   
   c. Show the hits and misses and final cache contents for a two-way set associative cache with one-byte blocks (lines) and a *total* size of 16 bytes. Assume LRU replacement. Compute the hit rate for this example.
   
   
   d. Show the hits and misses and final cache contents for a fully associative cache with one-byte blocks (lines) and a *total* size of 16 bytes. Assume LRU replacement. Compute the hit rate for this example.
   
   
   e. Show the hits and misses and final cache contents for a fully associative cache with four-byte blocks (lines) and a *total* size of 16 bytes. Assume LRU replacement. Compute the hit rate for this example.
   
   
6. A set associative cache consists of 40 lines divided into 5-line sets. (In other words, it is 5-way set associative). Each line is 4 bytes long. Main memory contains 16K blocks of 64 words each, and a word consists of 4 bytes. Show the format of main memory addresses.
   
   
7. Consider a memory system that uses a 32-bit address and is byte addressable, and a cache that uses 64 byte lines.
   
   Assume a direct-mapped cache with a tag field in the address of 17 bits. Show the address format and determine the following parameters: number of lines in the cache and the size of the cache.
   
   Assume a fully-associative cache. Now how big is the tag?
   
   Assume a 3-way set associative cache with a tag field in the address of 8 bits. Show the address format and determine the following parameters: number of lines in the cache, size of the cache, number of lines per set, number of sets in the cache, and the size of the tag.
   
   
8. Consider a machine with a byte addressable main memory of 2^16 (65536) bytes, which has a direct-mapped cache with 32 lines. Lines are 16 bytes long.
   
   a. How is the 16-bit memory address partitioned by the cache? (In other words, how big is the tag field, the entry into the line, etc.)?
   
   b. Into what line would bytes with each of the following addresses be stored?
   0x111B
   0xC334
   0xD01D
   0xAAAA
   
   c. Suppose the byte with address 0x2B2B is stored in the cache. What are the addresses of the other bytes stored along with it?
   
   d. How many total bytes of memory can be stored in the cache?
   
   e. Why is the tag also stored in the cache?
   
   
9. Consider a memory system with the following parameters:

   Tc (cache access time)	= 2ns	Cc (cache cost)		= .001 cents/bit
   Tm (memory access time)	= 300ns	Cm (memory cost)	= .00005 cents/bit
   

   a. What is the cost of 1 Megabyte of main memory?
   b. What is the cost of 1 Megabyte of cache memory?
   c. What is the cost of a memory system with a 512 Megabyte memory and a 64Kbyte cache?
   d. If the effective access time is 13% greater than the cache access time, what is the hit ratio H?
   
   
10. A virtual memory system for a byte-addressable processor with 8-byte words has a page size of 512 words, sixteen virtual pages, and four physical page frames. The page table is as follows:

    Virtual page Number	Page Frame Number
    
            0                        1
            1                        3
            2                        -
            3                        0
            4                        -
            5                        -
            6                        -
            7                        -
    	8			 -
    	9			 -
    	10			 -
    	11			 2
    	12			 -
    	13			 -
    	14			 -
    	15			 -
    

    a. What is the size of the virtual address space? (How many bits in a virtual address?)

    b. What is the size of the physical address space? (How many bits in a physical address?)

    c. What are the physical addresses corresponding to the following decimal virtual addresses (yes, you have to convert from decimal to binary): 0, 3728, 2047, 2048, 10025, 22550, 7596? (Indicate which, if any, cause page faults).
     

11. Give reasons why the page size in a virtual memory system should be neither too large or too small.


12. A computer has a cache, main memory, and a disk. If a reference to the cache is a hit, it takes 6 ns to retrieve the data. If a reference misses in the cache, it takes 89 ns to fetch the item from memory and put it in the cache, at which point the request is reissued to the cache. If the required item is not in main memory, it takes 13 ms to fetch the word from the disk, followed by 81 ns to copy the word to the cache, and then the reference is reissued to the cache. The cache hit ratio is .94 and the main memory hit ratio is .84. What is the average time in nanoseconds to access a data item on this system?



13. Consider a paged logical address space (composed of 32 pages of 2K bytes each) mapped into a .5 MByte physical memory space.

    a. What is the format of the processor's logical address?

    b. What is the length and width of the page table (ignoring any access control bits)?

    c. What is the effect on the page table if the physical memory space is reduced by half?
    



14. The following tables contain information about a segmented, paged virtual memory system and certain select memory locations. Total physical memory size is 2K bytes. All numbers in this table are in Hex unless otherwise noted. The processor is byte-addressable, and uses little-endian storage.

------------------------------------------------------------------------------
                Segment Table

Entry Number    Presence bit    Page Table
     0                0             0
     1                1             1
------------------------------------------------------------------------------

                        Page Table 0

Entry Number    Presence bit    Disk Address    Physical Page Number
     0                0          0x443BH096             0x0
     1                1          0x08D22108             0x3
     2                1          0xF0871A09             0x1
     3                0          0x7BA54C21             0x2

------------------------------------------------------------------------------

                        Page Table 1

Entry Number    Presence bit    Disk Address    Physical Page Number
     0                1          0x88B04136             0x2
     1                0          0xEF444219             0x0
     2                1          0x00222957             0x3
     3                1          0x28756554             0x1

------------------------------------------------------------------------------

Memory

Address Contents
0x02A4  0x7230
0x03A4  0x86a9
0x04A4  0x9723
0x05A4  0x3423
0x06A4  0x8876
0x0FA4  0x2373
0x11A4  0x1346
0x17A4  0x6792
0x1EA4  0x5292
0x37A4  0x7974
0x3BA4  0x3205
0x67A4  0x6623

 

a. Assuming 512-byte pages, convert the virtual address 0xFA4 into a physical address.

b. What is the value in memory stored at the physical address corresponding to the virtual address 0xFA4?

c. Repeat (a) and (b) for the virtual address 0x3A4.

d. Repeat (a) and (b) for the virtual address 0xEA4.

e. Repeat (a) and (b) for the virtual address 0xBA4.

f. What changes to this Virtual Memory structure would need to take place if the page size was increased to 1024 bytes?