Chapter 5.

The Memory System

Overview

Basic memory circuits Organization of the main memory Cache memory concept Virtual memory mechanism Secondary storage

Some Basic Concepts

Basic Concepts

The maximum size of the memory that can be used in any computer is determined by the addressing scheme.
16-bit addresses = 216 = 64K memory locations

Most modern computers are byte addressable.

Word address 0 0 Byte address 1 2 3 0 3 Byte address 2 1 0

k k k k k k k k

k k

2 -4

2 -4

2 -3

2- 2

2 - 1

2 - 4

2- 1

2 - 2

2 -3

2 -4

(a) Big-endian assignment

(b) Little-endian assignment

Traditional Architecture
Processor MAR n-bit data bus Up to 2k addressable locations Word length =n bits Control lines ( R / W , MFC, etc.)

k-bit address bus

Memory

MDR

Figure 5.1. Connection of the memory to the processor.

Basic Concepts

Block transfer bulk data transfer Memory access time Memory cycle time RAM any location can be accessed for a Read or Write operation in some fixed amount of time that is independent of the locations address. Cache memory Virtual memory, memory management unit

Semiconductor RAM Memories

Internal Organization of Memory Chips

b7 W0 FF A0 A1 A2 A3 W15 Address decoder W1 Memory cells Sense / Write circuit Sense / Write circuit R/W CS b1 b0 FF b7 b1 b1 b0 b0

16 words of 8 bits each: 16x8 memory org.. It has 16 external connections: Sense / Write circuit addr. 4, data 8, control: 2, power/ground: 2 1K memory cells: memory, Data 128x8 input /output lines: b7 external connections: ? 19(7+8+2+2) 1Kx1:? 15 (10+1+2+2)

Figure 5.2. Organization of bit cells in a memory chip.

A Memory Chip
5-bit row address W0 W1 5-bit decoder W31 32 32 memory cell array Sense / Write circuitry

10-bit address

32-to-1 output multiplexer and input demultiplexer 5-bit column address Data input/output

R/ W

CS

Figure 5.3. Organization of a 1K 1 memory chip.

Static Memories

The circuits are capable of retaining their state as long as power is applied.
b b

T1

T2

Word line Bit lines

Figure 5.4. A static RAM cell.

Vsupply

T3 T1 X

T4 T2 Y

T5

T6

Word line Bit lines

Static Memories
Figure 5.5. An example of a CMOS memory cell.

CMOS cell: low power consumption

Asynchronous DRAMs

Static RAMs are fast, but they cost more area and are more expensive. Dynamic RAMs (DRAMs) are cheap and area efficient, but they can not retain their state indefinitely need to be periodically refreshed.

Bit line Word line

T C

Figure 5.6. A single-transistor dynamic memory cell

A Dynamic Memory Chip

RA S

Row Addr. Strobe

Row address latch Row decoder 4096 (512 8) cell array

A20 - 9 A 8 -

Sense / Write circuits

CS R/ W

Column address latch

Column decoder

CA S

D7

D0

Column Addr. Strobe

Figure 5.7. Internal organization of a 2M 8 dynamic memory chip.

Fast Page Mode

When the DRAM in last slide is accessed, the contents of all 4096 cells in the selected row are sensed, but only 8 bits are placed on the data lines D7-0, as selected by A8-0. Fast page mode make it possible to access the other bytes in the same row without having to reselect the row. A latch is added at the output of the sense amplifier in each column. Good for bulk transfer.

Synchronous DRAMs

The operations of SDRAM are controlled by a clock signal.

Refresh counter

Row address latch Row/Column address Column address counter

Row decoder

Cell array

Column decoder

Read/Write circuits & latches

Clock RA S CA S R/ W CS

Mode register and timing control

Data input register

Data output register

Figure 5.8. Synchronous DRAM.

Data

Synchronous DRAMs
Clock R/ W

RA S

CA S

Address

Row

Col

Data

D0

D1

D2

D3

Figure 5.9. Burst read of length 4 in an SDRAM.

Synchronous DRAMs

No CAS pulses is needed in burst operation. Refresh circuits are included (every 64ms). Clock frequency > 100 MHz Intel PC100 and PC133

Latency and Bandwidth

The speed and efficiency of data transfers among memory, processor, and disk have a large impact on the performance of a computer system. Memory latency the amount of time it takes to transfer a word of data to or from the memory. Memory bandwidth the number of bits or bytes that can be transferred in one second. It is used to measure how much time is needed to transfer an entire block of data. Bandwidth is not determined solely by memory. It is the product of the rate at which data are transferred (and accessed) and the width of the data bus.

DDR SDRAM

Double-Data-Rate SDRAM Standard SDRAM performs all actions on the rising edge of the clock signal. DDR SDRAM accesses the cell array in the same way, but transfers the data on both edges of the clock. The cell array is organized in two banks. Each can be accessed separately. DDR SDRAMs and standard SDRAMs are most efficiently used in applications where block transfers are prevalent.

Structures of Larger Memories

21-bit addresses A0 A1 19-bit internal chip address A19 A20

2-bit decoder

512K 8 memory chip

D31-24

D23-16

D 15-8

D7-0

512K 8 memory chip

19-bit address

8-bit data input/output

Chip select

Figure 5.10. Organization of a 2M 32 memory module using 512K 8 static memory chips.

Memory System Considerations

The choice of a RAM chip for a given application depends on several factors: Cost, speed, power, size SRAMs are faster, more expensive, smaller. DRAMs are slower, cheaper, larger. Which one for cache and main memory, respectively? Refresh overhead suppose a SDRAM whose cells are in 8K rows; 4 clock cycles are needed to access each row; then it takes 81924=32,768 cycles to refresh all rows; if the clock rate is 133 MHz, then it takes 32,768/(13310-6)=24610-6 seconds; suppose the typical refreshing period is 64 ms, then the refresh overhead is 0.246/64=0.0038<0.4% of the total time available for accessing the memory.

Memory Controller
Address R/ W Request Processor Clock Memory controller Row/Column address RA S CA S R/ W CS Clock Memory

Data

Figure 5.11. Use of a memory controller.

Read-Only Memories

Read-Only-Memory

Volatile / non-volatile memory ROM Bit line PROM: programmable ROM Word line EPROM: erasable, reprogrammable ROM EEPROM: can be programmed and erased T Not connected to store a 1 electrically P
Connected to store a 0

Figure 5.12. A ROM cell.

Flash Memory

Similar to EEPROM Difference: only possible to write an entire block of cells instead of a single cell Low power Use in portable equipment Implementation of such modules

Flash cards Flash drives

Speed, Size, and Cost

Processor

Registers
Increasing size Primary L1 cache Increasing Increasing speed cost per bit

SecondaryL2 cache

Main memory

Magnetic disk secondary memory

Figure 5.13. Memory hierarchy.

Cache Memories

Cache

What is cache? Page 315 Why we need it? Locality of reference (very important) - temporal - spatial Cache block cache line

A set of contiguous address locations of some size

Cache
Processor Cache Main memory

Figure 5.14. Use of a cache memory.

Replacement algorithm Hit / miss Write-through / Write-back Load through

Memory Hierarchy Main Memory

CPU

I/O Processor

Cache

Magnetic Disks

Magnetic Tapes
30 / 19

Cache Memory High speed (towards CPU speed)

Small size (power & cost)

Miss

CPU
Cache (Fast) Cache 95% hit ratio

Main Memory (Slow)

Mem

Hit

Access = 0.95 Cache + 0.05 Mem

31 / 19

Cache Memory

CPU

30-bit Address Cache 1 Mword Only 20 bits !!! Main Memory 1 Gword

32 / 19

Cache Memory
00000 00001 FFFFF

Cache

00000000 00000001 3FFFFFFF

Main Memory

Address Mapping !!!

33 / 19

Main memory

Direct Mapping
Block j of main memory maps onto block j modulo 128 of the cache
Cache
tag tag Block 0 Block 1

Block 0 Block 1

Block 127 Block 128 Block 129

4: one of 16 words. (each block has 16=24 words)

7: points to a particular block in the cache (128=27)

tag

Block 127

Block 255 Block 256 Block 257

Figure 5.15. Direct-mapped cache.

5: 5 tag bits are compared with the tag bits associated with its location in the cache. Identify which of the 32 blocks that are resident in the cache (4096/128).

Block 4095 Tag 5 Block 7 Word 4 Main memory address

Direct Mapping Address

000 00500

What happens when Address = 100 00500

00000
00500 00900 01400 FFFFF

Cache
000 0 1 A 6 Tag Data 080 4 7 C C 150 0 0 0 5 Match No match 000 0 1 A 6

Compare

20 10 16 Bits Bits Bits (Addr) (Tag) (Data)

35 / 19

Direct Mapping with Blocks Address

000 0050 0

Block Size = 16

00000

Cache
Tag Data 000 0 1 A 6

00500 01A6 000 00501 0254 00900 47CC 080 00901 A0B4 01400 0005 150 01401 5C04 FFFFF

Compare

Match No match

20 10 16 Bits Bits Bits (Addr) (Tag) (Data)

36 / 19

Direct Mapping
Tag 5 Block 7 Word 4 Main memory address

11101,1111111,1100

Tag: 11101 Block: 1111111=127, in the 127th block of the cache Word:1100=12, the 12th word of the 127th block in the cache

Associative Mapping
Cache tag tag Block 0 Block 1

Main memory Block 0 Block 1

Block i tag

Block 127

4: one of 16 words. (each block has 16=24 words) 12: 12 tag bits Identify which of the 4096 blocks that are resident in the cache 4096=212.
Block 4095 Tag 12 Word 4 Main memory address

Figure 5.16. Associative-mapped cache.

Associative Memory
Cache Location
00000 Cache 00001 00012000 15000000 FFFFF 08000000
00000000 00000001 00012000 08000000 15000000 3FFFFFFF

Main Memory

Address (Key)

Data
39 / 19

Associative Mapping
Address

00012000

Can have any number of locations

Cache
00012000 15000000 08000000 01A6 Data 0005 01A6

47CC

How many comparators?

30 Bits (Key)

16 Bits (Data)

40 / 19

Associative Mapping
Tag 12 Word 4 Main memory address

111011111111,1100

Tag: 111011111111 Word:1100=12, the 12th word of a block in the cache

Main memory Block 0

Set-Associative Mapping
Cache tag Set 0 tag tag Set 1 Block 0 Block 1

Block 1

Block 63
Block 64 Block 2 Block 65

tag

Block 3

4: one of 16 words. (each block has 16=24 words)

tag Set 63 tag

Block 127 Block 126 Block 128 Block 127 Block 129

6: points to a particular set in the cache (128/2=64=26) 6: 6 tag bits is used to check if the desired block is present (4096/64=26).

Block 4095

Figure 5.17. Set-associative-mapped cache with two blocks per set.

Tag
6

Set
6

Word
4 Main memory address

Set-Associative Mapping Address

000 00500 2-Way Set Associative

00000
00500 00900 01400 FFFFF

Cache
000 0 1 A 6 010 0 7 2 1 Tag1 Data1 080 4 7 C C 000 0 8 2 2 150 0 0 0 5 000 0 9 0 9 Tag2 Data2 000 0 1 A 6 010 0 7 2 1

Compare

Compare

20 10 16 10 16 Bits Bits Bits Bits Bits (Addr) (Tag) (Data) (Tag) (Data)

Match

No match

43 / 19

Set-Associative Mapping
Tag 6 Set 6 Word 4 Main memory address

111011,111111,1100

Tag: 111011 Set: 111111=63, in the 63th set of the cache Word:1100=12, the 12th word of the 63th set in the cache

Replacement Algorithms

Difficult to determine which blocks to kick out Least Recently Used (LRU) block The cache controller tracks references to all blocks as computation proceeds. Increase / clear track counters when a hit/miss occurs

Replacement Algorithms For Associative & Set-Associative Cache

Which location should be emptied when the cache is full and a miss occurs? First In First Out (FIFO) Least Recently Used (LRU)

Distinguish an Empty location from a Full one

Valid Bit

46 / 19

CPU Reference

Replacement Algorithms
A B C A D E
Miss Miss Miss Hit Miss Miss

D
Hit

C
Hit

F
Miss

Miss

Cache FIFO

A B

A B C

A B C

A B C D

E B C D

E A C D

E A C D

E A C D

E A F D

Hit Ratio = 3 / 10 = 0.3

47 / 19

CPU Reference

Replacement Algorithms
A B C A D E
Miss Miss Miss Hit Miss Miss

D
Hit

C
Hit

F
Miss

Hit

Cache LRU

B A

C B A

A C B

D A C B

E D A C

A E D C

D A E C

C D A E

F C D A

Hit Ratio = 4 / 10 = 0.4

48 / 19

Performance Considerations

Overview

Two key factors: performance and cost Price/performance ratio Performance depends on how fast machine instructions can be brought into the processor for execution and how fast they can be executed. For memory hierarchy, it is beneficial if transfers to and from the faster units can be done at a rate equal to that of the faster unit. This is not possible if both the slow and the fast units are accessed in the same manner. However, it can be achieved when parallelism is used in the organizations of the slower unit.

Interleaving

If the main memory is structured as a collection of physically separated modules, each with its own ABR (Address buffer register) and DBR( Data buffer register), memory access operations may proceed in more than one module at the same time.
m bits k bits Module m bits Address in module MM address Address in module k bits Module MM address

ABR DBR ABR DBR ABR DBR Module i ABR DBR Module n- 1

ABR DBR

ABR DBR

Module 0

Module 0

Module i

Module k 2 - 1

(b) Consecutive words in consecutive modules (a) Consecutive words in a module

Figure 5.25. Addressing multiple-module memory systems.

Hit Rate and Miss Penalty

The success rate in accessing information at various levels of the memory hierarchy hit rate / miss rate. Ideally, the entire memory hierarchy would appear to the processor as a single memory unit that has the access time of a cache on the processor chip and the size of a magnetic disk depends on the hit rate (>>0.9). A miss causes extra time needed to bring the desired information into the cache. Example 5.2, page 332.

Hit Rate and Miss Penalty (cont.)

Tave=hC+(1-h)M Tave: average access time experienced by the processor h: hit rate M: miss penalty, the time to access information in the main memory C: the time to access information in the cache Example: Assume that 30 percent of the instructions in a typical program perform a read/write operation, which means that there are 130 memory accesses for every 100 instructions executed. h=0.95 for instructions, h=0.9 for data C=10 clock cycles, M=17 clock cycles, interleaved memory Time without cache 130x10 = 5.04 Time with cache 100(0.95x1+0.05x17)+30(0.9x1+0.1x17) The computer with the cache performs five times better

How to Improve Hit Rate?

Use larger cache increased cost Increase the block size while keeping the total cache size constant. However, if the block size is too large, some items may not be referenced before the block is replaced miss penalty increases. Load-through approach

Caches on the Processor Chip

On chip vs. off chip Two separate caches for instructions and data, respectively Single cache for both Which one has better hit rate? -- Single cache Whats the advantage of separating caches? parallelism, better performance Level 1 and Level 2 caches L1 cache faster and smaller. Access more than one word simultaneously and let the processor use them one at a time. L2 cache slower and larger. How about the average access time? Average access time: tave = h1C1 + (1-h1)h2C2 + (1-h1)(1-h2)M where h is the hit rate, C is the time to access information in cache, M is the time to access information in main memory.

Other Enhancements

Write buffer processor doesnt need to wait for the memory write to be completed Prefetching prefetch the data into the cache before they are needed Lockup-Free cache processor is able to access the cache while a miss is being serviced.

Virtual Memories

Overview

Physical main memory is not as large as the address space spanned by an address issued by the processor. 232 = 4 GB, 264 = When a program does not completely fit into the main memory, the parts of it not currently being executed are stored on secondary storage devices. Techniques that automatically move program and data blocks into the physical main memory when they are required for execution are called virtual-memory techniques. Virtual addresses will be translated into physical addresses.

Overview
Memory Management Unit

Address Translation

All programs and data are composed of fixedlength units called pages, each of which consists of a block of words that occupy contiguous locations in the main memory. Page cannot be too small or too large. The virtual memory mechanism bridges the size and speed gaps between the main memory and secondary storage similar to cache.

Example: Example of Address Translation

Code Data Heap Stack
Prog 1 Virtual Address Space 1
Data 2 Stack 1 Heap 1 Code 1 Stack 2 Data 1 Heap 2 Code 2 OS code

Code Data Heap Stack

Prog 2 Virtual Address Space 2

Translation Map 1

OS data OS heap & Stacks

Translation Map 2

Physical Address Space

Page Tables and Address Translation

Page table register Page table

Virtual page number

Valid bits Other flags

Main memory

The role of page table in the virtual-to-physical address translation process.

Address Translation
Page table base register

Virtual address from processor

Page table address

Virtual page number

Offset

+
PAGE TABLE

Control bits

Page frame in memory

Page frame

Offset

Figure 5.27. Virtual-memory address translation.

Physical address in main memory

Address Translation

The page table information is used by the MMU for every access, so it is supposed to be with the MMU. However, since MMU is on the processor chip and the page table is rather large, only small portion of it, which consists of the page table entries that correspond to the most recently accessed pages, can be accommodated within the MMU. Translation Lookaside Buffer (TLB)

Virtual address from processor

TLB
TLB Virtual page number

Virtual page number

Offset

Control bits

Page frame in memory

No

=? Yes

Miss

Hit

Page frame

Offset

Physical address in main memory

Figure 5.28. Use of an associative-mapped TLB.

TLB

The contents of TLB must be coherent with the contents of page tables in the memory. Translation procedure. Page fault Page replacement Write-through is not suitable for virtual memory. Locality of reference in virtual memory

Memory Management Requirements

Multiple programs System space / user space Protection (supervisor / user state, privileged instructions) Shared pages

Secondary Storage

Magnetic Hard Disks

Disk Disk drive Disk controller

Organization of Data on a Disk

Sector 3, trackn

Sector 0, track 1 Sector 0, track 0

Figure 5.30. Organization of one surface of a disk.

Access Data on a Disk

Sector header Following the data, there is an errorcorrection code (ECC). Formatting process Difference between inner tracks and outer tracks Access time seek time / rotational delay (latency time) Data buffer/cache

Disk Controller
Processor Main memory

System bus Disk controller

Disk drive

Disk drive

Figure 5.31. Disks connected to the system bus.

Disk Controller

Seek Read Write Error checking

RAID Disk Arrays

Redundant Array of Inexpensive Disks Using multiple disks makes it cheaper for huge storage, and also possible to improve the reliability of the overall system. RAID0 data striping RAID1 identical copies of data on two disks RAID2, 3, 4 increased reliability RAID5 parity-based error-recovery

Aluminum

Acrylic

Label

Optical Disks

Pit

Land

Polycarbonate plastic (a) Cross-section

Pit

Land

Reflection

Reflection

No reflection

Source

Detector

Source

Detector

Source

Detector

(b) Transition from pit to land

0 1 0 0

1 0 0 0 0

1 0 0 0 1

0 0 1 0 0

1 0

(c) Stored binary pattern

Figure 5.32. Optical disk.

Optical Disks

CD-ROM CD-Recordable (CD-R) CD-ReWritable (CD-RW) DVD DVD-RAM

Magnetic Tape Systems

File mark

File File mark

7 or 9 bits

File gap

Record

Record gap

Record

Record gap

Figure 5.33. Organization of data on magnetic tape.

Homework

Page 361: 5.6, 5.9, 5.10(a) Due time: 10:30am, Monday, March 26

Requirements for Homework

5.6. (a): 1 credits 5.6. (b): Draw a figure to show how program words are mapped on the cache blocks: 2 Sequence of reads from the main memory blocks into cache blocks:2 Total time for reading blocks from the main memory: 2 Executing the program out of the cache:

Beginning section of program:1 Outer loop excluding Inner loop:1 Inner loop:1 End section of program:1

Total execution time:1

Hints for Homework

Assume that consecutive addresses refer to consecutive words. The cycle time is for one word Total time for reading blocks from the main memory: the number of readsx128x10 Executing the program out of the cache

MEM word size for instructionsxloopNumx1

Outer loop excluding Inner loop: (outer loop word size-inner loop word size)x10x1 Inner loop: inner loop word sizex20x10x1

MEM word size from MEM 23 to 1200 is 1200-22 MEM word size from MEM 1201 to 1500(end) is 1500-1200