CSCI 6643 Operating Systems Fall 2018HW #4 - Memory System DesignDue: November 28, 2018The purpose of this assignment is to design a memory system using a set of potential componentsand algorithms. Th

CSCI 6643 Operating Systems Fall 2018 HW #4 - Memory System DesignDue: November 28, 2018 The purpose of this assignment is to design a memory system using a set of potential components and algorithms. The ma jor design criteria will be the e ective access time of the system and the overall monetary cost of the system. The features of each of the system components are given below.

Secondary memory - disk drive A disk will be used as secondary storage. Each potential disk drive will be big enough to hold the swap space for a virtual memory system of 4GBytes. There are two potential drives to select:

Seek time Rotation speed Transfer rate Cost 9ms 5400 rpm 60MB/s $100 6ms 7200 rpm 100MB/s $150 The seek time is the average overhead necessary to nd the particular track containing the data to be transferred, and is the same regardless of the amount of information being transferred. The rotational speed a ects the latency necessary to nd the proper sector in a track. Assume that one half of a rotation is required on average. The transfer rate is the rate at which data can be read or written to the disk after the appropriate sector has been found.

Main Memory - RAM The amount of physical RAM to be used in the system can be chosen from one of three sizes:

32MB, 128MB or 1GB. The DRAM can be formed using a set of chips with one of two di erent characteristics:

Access time Cost 60ns $60 for every 32MB 50ns $80 for every 32MB The access time is the time taken to read or write a single data item to memory. The total cost of the memory chips depends on the total size of the RAM chosen.

L2 Cache - lower level The amount of L2 (external) cache which can be used in the system can be chosen from one of three sizes: 64K, 256K or 1M. These sizes refer to the number of data entries in the cache. Two di erent chips with di erent characteristics can be chosen: Access time Cost 15ns $8 for every 64K entries 10ns $11 for every 64K entries The access time is the time taken to read a single data entry from the cache. The total cost of the memory chips depends on the size of the cache chosen.

L1 Cache - upper level The amount of L1 (on chip) cache which can be used in the system can be chosen from one of three sizes: 1K, 4K or 32K. These sizes refer to the number of data entries in the cache. Two di erent chip characteristics can be chosen:

Access time Cost 2ns $10 for every 1K entries 1ns $15 for every 1K entries The access time is the time taken to read a single data entry from the cache. The total cost of the cache depends on the size of the cache chosen.

RAM - Disk interface You are implementing a virtual memory of size 4GB. The three possible page sizes that you can choose from are : 1KB, 4KB and 16KB. This choice will a ect the page transfer times, the number of frames in the RAM, and the RAM hit rate. The management of the placement of pages in the RAM and their replacement, will be governed by one of two strategies: FIFO or LRU. The miss rates for the FIFO strategy depend on the size of physical RAM, namely (32MB - 0.001%, 128MB - 0.0001%, and 1GB - 0.00001%). If the LRU strategy is used, the miss rates decrease by 20%. However, the tradeo is a time overhead to do the bookkeeping. The increase in access time for a miss is 0.01ns per frame in the RAM (size of RAM divided by number of pages). The page size also a ects the miss rate. The above values are used for 1KB size pages. For 4KB pages the miss rates are reduced by 5%, and for 16KB pages the miss rates are reduced by 10%. Whenever a page must be replaced, assume that 25% of the time the page to be replaced is dirty and must be written back to the disk, before the new page can be loaded in, and a nal RAM access can be made.

L2 Cache - RAM interface The management of the placement of data in the external L2 cache and its replacement will be governed as follows. The mapping will be either fully associative or 2-way set associative. And either random or LRU replacement will be used. The miss rates for these strategies, given the di erent cache sizes are:

Cache size 2-way Random Full Random 2-way LRU Full LRU 64K entries 1.35% 1.2% 1.25% 1.1% 256K entries 1.02% 0.91% 1.0% 0.9% 1M entries 0.66% 0.6% 0.65% 0.6% While the LRU and Fully associative strategies provide better miss rates, they have a price. In order to perform fully associative mapping additional hardware is needed that increases the cost of the cache by 10%. To use the LRU algorithm requires a time overhead per access of 10 6 ns per entry in the cache.

L1 Cache - L2 Cache interface The management of the placement of data in the on-chip L1 cache is done by a simple direct mapping, which has no overhead. The miss rates for this cache are dependent on cache size:

Cache size Direct mapping miss rate 1K entries 13.3% 4K entries 7.2% 32K entries 2.0% It is assumed that a write through update policy is used for both caches, so cache entries do not need to be written back to a lower level upon replacement. Instead, an extra delay of 20% is imposed on a write operation versus a read operation. For calculation purposes, assume that writes to memory occur 10% of the time. Thus, for reads, a hit in the cache means only the normal access time occurs. For a miss, a cache entry replacement must occur from the lower level. When writing, assume that regardless of a hit or miss the access time is always 20% more than the normal access time of the cache, since no data is ever transferred up from a lower level.

The design Develop a set of equations that compute the e ective access time for this system, given that you have chosen a particular combination of disk, RAM, caches, page size, and mapping and replacement algorithms. While you could do some of these calculations by hand, it would be easiest to write a program (you can use whatever language you would like) that is composed of a set of nested loops that iterate through all of the combinations, and for each one computes the e ective access time and cost of that combination using the information given here. Then consider each of the following scenarios.

1. Assume money is no ob ject. What is the absolute fastest system you can design and what is its e ective access time and cost?

2. Now assume you are poor. After making as many con guration choices as possible based on spending as little money as you can, what is the absolute fastest system you can design and what is its e ective access time and cost?

3. Consider a system that spends an amount of money about half way between the amounts for the cheapest and most expensive systems just discussed. What is the absolute fastest system you can design and is its access time about half way between that of the other two?

Submit the program you wrote to do all of your calculations, along with the answers to the three questions, on Blackboard.