Memory Hierarchy

1

krraju.in

What you’ll learn

• What are the basic building blocks of the memory.
• What are the different types of memories used in a computer?
• How are memory contents accessed
• Different accessing techniques
• How to handle the speed mismatch between processor and memory?
• How the memory hierarchy will reduce the memory latency?

2

Memory and I/O Organization Memory Hierarchy, Associative Memory, Cache Memory, Virtual memory.

I/O Organization: Peripheral devices, I/O interface, Asynchronous data transfer, Modes of transfer, Priority interrupt, direct memory access and IOP

​

​

​

Unit-4

krraju.in

3

Terminology

• Capacity: the amount of information that can be contained in a memory unit – words or bytes.
• Word: the natural unit of organization in the memory, typically the number of bits used to represent a number.
• Addressable unit: the functional data element size that can be addressed in the memory – word size or individual bytes.
• Unit of transfer: the number of data elements transferred at a time – bits in main memory and blocks in secondary memory.
• Transfer rate: rate at which data is transferred to/from the memory device.

krraju.in

4

Memory Characteristics

Ideal memory system characteristics:

Size: Infinitely large, no constraints on program or data set size.

Speed: Infinitely fast, latency equal to the fastest memory technology available.

Cost: The per bit cost should approach the lowest cost technology available.

Volatility and Portability

​

krraju.in

5

Design Objective

• Major design objective of any memory system
• To provide adequate storage capacity at
• An acceptable level of performance
• At a reasonable cost

krraju.in

6

How to meet the design objective?

Four interrelated ways to meet this goal

• Use a hierarchy of storage devices
• Develop automatic space allocation methods for efficient use of the memory
• Free the user from memory management tasks through virtual memory techniques
• Design the memory and its related interconnection structure so that the processor can operate at or near its maximum rate

​

krraju.in

7

Overview

Historically, the limiting factor in computer’s performance has been memory access time.

• Memory speed is slower than the processor speed.
• A process could be bottlenecked (von-Neumann bottleneck) by the memory system’s inability to keep up with the processor.

Goal: To develop an effective memory organization that supports the processing power of the CPU.

CPU

I/O

Memory

krraju.in

8

Primary Memory

The part of the memory hierarchy that the CPU accesses directly; excluded are the peripheral storage devices.

• Also called main memory, central memory, core memory, or simply memory.

Main memory is a program addressable storage from which instructions and other data can be loaded directly into registers for subsequent execution or processing.

• The basic cell of the main memory will have the capability of storing 1 bit.

​

krraju.in

9

Memory Cell

• The basic cells are organized as words, and each word contains so many bits depending on the number of bits per word.

krraju.in

10

Memory Organisation

• The memory is addressed by address decoding circuit and the contents of memory location (memory word) are transferred to memory data register

krraju.in

11

Core Memory

• Used in 1^st and 2^nd generation computers
• Magnetic cores (toroids) used to store logical 0 or 1 state by inducing and E-field in them (hysteresis loop)
• 1 core = 1 bit of storage
• Required addressing and sensing wires ran through each core
• Destructive readout
• Obsolete
• Replaced in the 1970s by semiconductor memory.

krraju.in

12

Semiconductor Memory

• Volatile memory: A memory in which a constant electrical power source is required to maintain the contents of memory. If the power is switched off, the stored information is lost.

​

krraju.in

13

ROM (Read Only Memory)

A Semiconductor memory whose contents cannot be altered. (Non-erasable memory).

• Mask Programmed ROM: It is very expensive and programmed at factory only.
• PROM (Programmable ROM): It is expensive and can be programmed once by end user.
• EPROM (Erasable Programmable ROM): It can be programmed many times and the cost is moderate.
• EEPROM (Electrically Erasable Programmable ROM): It is very expensive and the user can program so many times.

​

krraju.in

14

DRAM (Dynamic RAM)

• A RAM whose cells are implemented using capacitors. A dynamic RAM will gradually lose its data unless it is periodically refreshed.
• The refresh operation slows down the processing since memory accessing cannot be performed during refreshing.

krraju.in

15

DRAM chips

• Extended data output (EDO) DRAM is faster than Fast page mode (FPM) DRAM.
• Burst EDO DRAM sends data from the next address also.
• Synchronous DRAM (SDRAM) can synchronize itself with the clock that controls the CPU making data transfers more reliable and faster.
• Rambus DRAM (RDRAM) is very fast. It sends data down a high bandwidth channel, 10 times faster than standard DRAM.
• Double data rate (DDR) RAM: It works during both halves of the signal. It is faster than SDRAM and less costlier than RDRAM.

krraju.in

16

SRAM (Static RAM)

• Faster than DRAM but more expensive. It does not need to have constant refresh and is used for the cache memory.
• Static RAM stores bit information within a flip-flop called binary cell. The reading of data is non destructive and the contents remain stable as long as power is available.

Buffer: A high speed memory interposed between two devices to match the speed of one device with the other.

krraju.in

17

Auxiliary Memory

Auxiliary memory: Devices that provide backup storage. e.g.: magnetic disks, tapes etc.

Secondary memory: Memory located outside the computer system itself, including disk and tape.

Magnetic disk: A flat circular plate with a magnetizable surface layer on which data can be stored by magnetic recording.

​

krraju.in

18

Magnetic Tape

A tape with a magnetizable surface on which data can be stored by magnetic recording.

Advantages: Lowest cost per unit stored.

Disadvantages: Sequential access means slow retrieval speeds.

Applications: Corporate data archiving.

krraju.in

19

Floppy (Flexible) Disks

• The diskette coated with magnetic material is enclosed in a plastic jacket, which has an opening where the Read/Write head makes contact with the diskette.
• A hole in the center of the diskette allows a spindle mechanism in the disk drive to position and rotate the diskette.

krraju.in

20

Micro floppy disks

Single density, double density and high density and sizes like 8 inches, 5¼ inches (mini floppy) and 3½ inches (micro floppy) are available.

• Micro floppy disks are 3½ inches in diameter, track densities of 135 data tracks per inch (TPI), and store 1.44 or 2 megabytes of data.

Advantages: Low cost per diskette and portability.

Disadvantages: Low capacity, very high cost per unit stored, large access times and fragile.

Applications: Personal computers.

krraju.in

21

Floppy Disk

Capacity

Disk capacity can be calculated as:

Disk capacity = (number of surfaces) x (tracks per surface) x (sectors per track) x (bytes per sector)

• Capacity of 5.25” DSDD floppy disk is given by

(2 sides x 40 tracks x 9 sectors x 0.5K bytes=360 KB

• Capacity of 5.25” DSHD floppy disk is given by

(2 sides x 80 tracks x 15 sectors x 0.5K bytes)=1200 KB=1.2 MB

krraju.in

22

Soft and Hard Sectoring

Soft sectored: A flexible disk is soft sectored when it has only one index hole. Each track is divided into sectors by electronic timing after sensing the index hole on each revolution. The number of sectors depends upon the format required for each soft sectored flexible disk.

Hard sectored: A flexible disk that is hard sectored has the index holes punched right into the disk. The number of holes depends on the size of the flexible disk. These holes divide up each track into sectors by a light beam physically sensing each hole.

krraju.in

23

Hard Drive

• Rigid metal platters coated with a magnetizable substance. Each surface has its own arm and head. All the arms are ganged together so they move to different radical positions all at once.
• The set of tracks at a given radial position is called a cylinder.
• Disk performance depends on a variety of factors like seek time and latency time.

krraju.in

24

Disk

Seek time: Time taken to move the read/write head to a required track.

Latency time: Time taken to rotate the disk in such a way that the read/write head is positioned on a particular sector.

​

Drive access time = track seek time + latency + transfer time

krraju.in

25

An Example

A disk has 128 sectors per track with 512 bytes per sector. The rotation rate is 5200 RPM. What is the transfer rate in bytes/second?

​

Solution:

The rotation time is 60/5200 = 11.5 ms.

The transfer rate is

(128 x 512/(11.5 x 10^-3 ))= 5.7M bytes/s.

​

krraju.in

26

Winchester Disk

The disks and the Read/Write heads are placed in a sealed, air filtered enclosure. They have larger capacity for a given physical size compared to unsealed units.

Advantages:

• Relatively high capacity and fast retrieval speed.
• Data integrity tends to be greater where the storage medium is not exposed to contaminating elements.

Disadvantages: Fragile; high cost per unit stored.

Applications: Personal computers through mainframes.

​

krraju.in

27

Magnetic Disks

krraju.in

28

Hard disk technologies

Magneto resistive technology: In this technology, the hard drive heads change resistance in the presence of a magnetic field and allow a smaller flying height and areal densities of 1 GB/sq. inch being achieved.

​

Near field recording technology: It uses a solid immersion lens in the read/write head. This allows a laser beam to be focused on a very small spot thereby increasing the densities.

krraju.in

29

Bubble Memory

Stores binary data in the form of little magnetic bubbles. It is similar to RAM, except it is nonvolatile by design.

Advantages:

• Compact, very reliable and tolerant of dirty environments and vibration.

Disadvantages:

• Cost per bit is relatively high.

​

krraju.in

30

Magneto-optical (MO) drive

An erasable, high capacity removable storage device similar to a CD-ROM drive. They use both magnetic and laser technology to write data to the disk, and use the laser to read that data back again. Writing data takes two passes over the disk, an erase pass followed by the write pass, but reading can be done in just one pass and so is much faster.

Advantages: Portability, high storage capacity and random access.

Disadvantages: Costlier than magnetic storage devices.

Applications: Personal computers.

krraju.in

31

RIAD (Redundant Array of Independent Disks)

Uses a large number of small hard drives to distribute data across all of the disk drives. Data is distributed across this set of drives in a defined manner. Data is duplicated or it can be reconstructed in the event of a disk failure.

Advantages: High capacity; designed for risk of data loss; low cost to minimize per unit stored.

Disadvantages: Semi-permanent installation.

Applications: Corporate data storage that requires frequent, rapid access.

​

krraju.in

32

Optical Storage

CD-ROM (Compact Disk Read Only Memory) is a non-erasable disk used for storing data. It uses 12 cm disks and can hold more than 650 M bytes (about 72 minutes of video).

Advantages: High capacity; moderate cost per unit stored; high durability and portability.

Disadvantages: Slower retrieval speeds than hard drives; only certain types can be rewritten.

Applications: Personal computers to corporate data storage:

krraju.in

33

CD-ROM working

• A very thin layer of reflective aluminum is deposited on the polycarbonate, topped by a protective lacquer.
• The depressions in the polycarbonate substrate are called pits; the unburned areas between the pits are called lands.

krraju.in

34

DVD (Digital Versatile Disk)

Uses two layers on each side of a disk to store data. DVDs use the same general design as CDs, but the difference is

• Smaller pits (0.4 vs 0.8 microns for CDs)
• A tighter spiral (between tracks 0.74 vs 1.6 microns for CDs)
• A red laser (at 0.65 vs 0.78 microns for CDs)
• The DVD capacities are:
• Single Side Single Layer 4.7 GB (2 hours video)
• Single Side Double Layer 8.5 GB (4 hours video)
• Double Sided Single Layer 9.4 GB (4 ½ hours video)
• Double Sided Double Layer 17 GB (8 hours video)

krraju.in

35

Erasable optical disk

An optical disk, that can be repeatedly written and overwritten, as with any magnetic disk.

Advantages:

• High capacity, portability and reliability.

Disadvantages:

• Material used in making disks, permanently loses its desirable properties after a certain number of erase cycles.

Applications:

• Personal computers to corporate data storage.

​

​

krraju.in

36

Flash Memory

Non-volatile EEPROM that can be electrically erased or written.

• PCMCIA (PC Memory Card International Association) cards that use a 68 pin connector.
• Type-I (3.3 mm thick) cards are used for memory enhancements including DRAM, SRAM and EEPROM.
• Type-II (5 mm thick) cards are used for modems or LAN adaptors.
• Type-III (10.5 mm thick) cards are used for mini hard disks.

krraju.in

37

Flash Memory contd..

Advantages:

• Fast retrieval times, compact, portable and require little energy to read and write

Disadvantages: High cost and limited capacity.

Applications:

• Hand held devices like, Personal digital assistants (PDA), organizers, digital cameras, cellular phones, voice recorders etc.
• Modems, Ethernet cards, wireless LAN adapters etc.

krraju.in

Memory Access

38

krraju.in

39

Memory Access

• Access time:
• For RAM, the time to address the unit and perform the transfer.
• For non-random access memory, the time to position the R/W head over the desired location
• Memory cycle time: Access time plus any other time required before a second access can be started.
• Access technique: how are memory contents accessed.

krraju.in

40

Memories and their Access Times

krraju.in

41

Random Access

• Each location has a unique physical address.
• Locations can be accessed in any order and all access times are the same.
• What we term RAM is more aptly called read/write memory since this access technique also applies to ROMs as well.
• Example: Main memory

krraju.in

42

Sequential Access

• Data does not have a unique address.
• Must read all data items in sequence until the desired item is found.
• Access times are highly variable.
• Example: Tape drive

krraju.in

43

Direct Access

• Data items have unique address
• Access is done using a combination of moving to a general memory area followed by a sequential access to reach the desired data item.
• Example: Disk drives

krraju.in

44

Associative Access

Argument Register

Key Register

M

Output

Match Register

Read

Write

m x n

Associative Memory

Array and Logic

Input

• A variation of random access memory
• Data items are accessed based on their contents (content addressable) rather than their actual location (e.g., bank ledger)

krraju.in

45

Content Addressable Memory

• Search all data items in parallel for a match to a given search pattern. All memory locations searched in parallel without regard to the size of the memory.
• Extremely fast for large memory sizes.
• Cost per bit is 5-10 times that of a normal RAM cell
• Example: Cache memory

krraju.in

46

Basis for the Memory Hierarchy

• The widening speed gap between CPU and main memory
• Processor speed of the order of 1 ns, Memory access requires 10s or even 100s of ns
• Memory bandwidth limits the instruction execution rate
• Each instruction execution involves at least one memory access

Moving information into the fast memory infrequently and accessing it many times before replacing with new information

krraju.in

47

Memory Parameters

• CPU Registers (small in number but very fast)
• External storage (relatively large and fast)
• External permanent storage (much larger and much slower)

krraju.in

48

Memory Hierarchy Characteristics

• Consists of distinct levels of memory components
• Each level characterized by its size, access time, and cost per bit
• Each increasing level in the hierarchy consists of modules of larger capacity, slower access time, and lower cost/bit.

CPU

Registers

Main Memory

Fast

Small

High cost

Hierarchical memory

Cache

Disk

Slow

Very Large

Very low cost

krraju.in

49

Goal

Try to match the processor speed with the rate of information transfer from the lowest element in the hierarchy.

​

krraju.in

50

Memory Hierarchy Advantages

• Decrease in frequency of accesses to slow memory.
• Decrease in cost/bit
• Improvement in average access time
• Increased capacity

krraju.in

51

Locality of Reference

The memory hierarchy works because of locality of reference

• Memory references made by the processor, for both instructions and data, tend to cluster together
• Instruction loops, subroutines
• Data arrays, tables
• Keep these clusters in high speed memory to reduce the average delay in accessing data.
• Over time, the clusters being referenced will change – memory management must deal with this.

krraju.in

52

Instructions and data recently referenced by a program are likely to be used again soon.

• Repeated access can be satisfied from the cache.
• Example:
• Program loops

​

Temporal Locality (Locality in Time)

krraju.in

53

Portions of address space near the current locus of reference are likely to be referenced in the near feature.

• This characteristic allows us to perform predictive preloading.
• Example:
• Array elements or sequential instruction code.

Spatial Locality (Locality in Space)

krraju.in

54

Reducing Memory Latency

• The data cache is used as a memory hierarchy technique to reduce the memory latency bottleneck for the processor.
• A cache takes advantage of both the principles of spatial and temporal locality
• Holds frequently used data in a small, fast memory that takes less time to access than main memory.

krraju.in

55

Placement of Cache Memory

CPU

3.8 GHz

Main Memory

533 MHz

Bus 800 MHz

Without Cache

CPU

Main Memory

533 MHz

Bus 800 MHz

With Cache

Cache

3.8 GHz

Front-side Bus

Back-side Bus

krraju.in

56

CPU

Registers

Main Memory

Auxiliary memory

Memory Hierarchy in a Computer System

Cache Memory

Magnetic Tapes

Magnetic Disks

I/O Processor

krraju.in

57

• The I/O processor manages data transfers between auxiliary memory and main memory.
• The cache organisation transfers information between main memory and CPU.

Cache and auxiliary memories are used for different purposes.

• The cache memory holds those parts of the program and data that are most heavily used
• Auxiliary memory holds those parts that are not presently used by the CPU

Hierarchical Memory System

krraju.in

58

Desktop, Drawer, and File Cabinet Analogy

Items on a desktop (register) or in a drawer (cache) are more readily accessible than those in a file cabinet (main memory).

krraju.in

59

Hit Ratio

CPU

Cache

Main Memory

• Performance of cache memory is frequently measured in Hit Ratio
• When CPU refers to memory
• If it finds the word in cache, it is a hit
• If the word is not found in cache, it is in main memory it is a miss

• Hit ratios of 0.9 and higher are common.

krraju.in

60

Assume a hit rate h in the drawer.

• Without the drawer, a document is accessed in 30 s and with drawer in 5 s.
• The drawer causes a fraction h of the cases to be done 6 times as fast, with access time unchanged for the remaining 1 – h.
• Speedup is thus 1/(1 – h + h/6) = 6 / (6 – 5h).
• Improving the drawer access time can increase the speedup factor but as long as the miss rate remains at 1 – h, the speedup can never exceed 1 / (1 – h).
• Given h = 0.9, for instance, the speedup is 4, with the upper bound being 10 for an extremely short drawer access time.

​

Drawer and File Cabinet Analogy

krraju.in

Recap

61

• Fast memory stores the most commonly used data and instructions
• So on average the memory system appears fast
• Large memory stores the remainder of data and instructions
• So the overall capacity is large

krraju.in

Video Links

• Memory Hierarchy by Sudhakar Atchala
• Associative Memory by Sudhakar Atchala
• Memory Hierarchy by Engineering Drive
• Types of Memories by Engineering Drive
• ​

62

krraju.in