Designing A Memory System For Effective Access Time And Cost

Secondary Memory - Disk Drive

The purpose of this assignment is to design a memory system using a set of potential components and algorithms. The major 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.

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.

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.

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.

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.

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.

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 ⁶ns per entry in the cache.

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.

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 object. 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?

Seek time (given) = 9ms

RPM = 5400 rpm rotation in 1 min [60 sec]

So, 1 rotation will be =60/5400 =0.01ms [rotation speed]

Rotation latency= 1/2 * 0.01 ms=0.025ms

# To access a file,

  Total time includes =seek time + rot. Latency +transfer time

TO calc. transfer time, find transfer rate

Transfer rate = bytes on track /rotation speed

So, transfer rate = 60*100/6ms =1000 B/ms

Transfer time= total bytes to be transferred/ transfer rate

so, Transfer time =100*150/1000 = 15ms

Given as each sector requires seek tim + rot. latency

= 9ms+0.025ms =9.025ms

Total 7500 sector takes = 7500*9.025ms =67687.5 ms

To read entire file, total time =67687.5 + 100(transfer time)

                                = 67787.5 ms

Seek time (given) = 6ms

RPM = 5400 rpm rotation in 1 min [60 sec]

So, 1 rotation will be =60/7200 =0.0083ms [rotation speed]

Rotation latency= 1/2 * 0.083 ms=0.0415ms

# To access a file,

  Total time includes =seek time + rot. Latency +transfer time

TO calc. transfer time, find transfer rate

Transfer rate = bytes on track /rotation speed

So, transfer rate = 60*67787.5 /6ms =4067 B/ms

Transfer time= total bytes to be transferred/ transfer rate

So, Transfer time =100*150/4067 = 3.688ms

Given as each sector requires seek time + rot. Latency

= 9ms+4067ms =4076ms

Total 7500 sector takes = 7500*4076ms =3057 ms

To read entire file, total time =3057 + 100(transfer time)

                                = 3157ms

Effective Access Time (EAT)

 EAT = (1 – p) x memory access x cost value

 + p (absolute fastest system overhead

 + [fastest system out]

 + Fastest system in

 + restart overhead)

Let’s say memory access (absolute fastest system

Table accesses) = effective cost 3157

Overhead at both ends say 3157 instructions ≈

10000nsecs

Absolute fastest system in = 15 msecs = 4067000 nsecs

50% of time effective access time = 8 000 000 nsecs

So EAT = (1 – p) x 20 + p(10000 + 8 000 000)

 ≈ 20 + 8 000 000p nsecs

~8000020nsecs

Let as consider the Absolute fastest system value=9000ms

Total memory of accessing time=8000020nsecs

Half way of the absolute fastest system on cost=67787.5Ms