Lecture 10
Computer Memory (II): Internal and External Memory
Recap from Last Lecture ◆Memory hierarchy:
Copyright By PowCoder代写 加微信 powcoder
– Use a hierarchical system of memories to emulate an idea memory (fast, large, and relatively cheap)
– Why is it possible? – Locality of Reference – Example: cache and main memory
Recap from Last Lecture ◆Cache and Main Memory:
– Essence: dynamically allocate M blocks to m lines (m <
stable state 0: C1 is low, C2 is high -> T1 and T4 are ON, T2 and T3 are OFF -> read low voltage from Bit line B
Apply high voltage (1) or low voltage (0) to Bit line B –> force the transistors into the proper states –> corresponding stable states
DRAM vs. SRAM
◆Common: volatile — need continuous power
◆Difference:
– DRAM cell is simpler and smaller, thus denser (more cells
per unit area) and less expensive
– however, DRAM requires the supporting refresh circuitry
– DRAM tends to be favored for large memory requirement
– DRAM for main memory, SRAM for cache
Read-Only Memory (ROM) • ROM characteristics
– contains permanent data that cannot be changed (cannot write) — not exactly, depending on the types of ROM
– data are burned into the chip during fabrication process — relatively large fixed cost, and there is no room for error
– nonvolatile, no need for continous power • Usage
– system programs
– library subroutines for frequently wanted functions
Special Types of ROM
• Programmable ROM (PROM)
– like ROM, it can be written into only once (after fabrication process)
– customers can use special equipment to electrically write once
– idea: each bit is locked by a fuse; initially all 1’s in the chip, if
burn the fuse, change 1 to 0 (write once)
fuse (illustration)
Special Types of ROM
• Read-Mostly Memory (a variation of ROM)
– we can re-write the memory, but at a higher cost
– useful for applications in which read operations are far more frequent then write operations, but for which nonvolatile storage is required
– three common types: EPROM, EEPROM, flash memory
Special Types of ROM
• Erasable Programmable ROM (EPROM)
– before a write operation, all the storage cells must be erased to the same initial state by exposure to ultraviolet radiation
– then write electronically
– read — exposure – write
– erasable: through exposure (could take 20 mins)
– more flexible than PROM
Special Types of ROM
• Electronically Erasable Programmable ROM (EEPROM)
– updates (write operations) happen at byte level (not entire chip) – however, write operation takes considerably longer than read
(several hundred microseconds per byte)
– more expensive and less dence (fewer bits per chip) than EPROM
• Flash Memory
– intermediate between EPROM and EEPROM
– erasure at block level (compred to byte-level and chip level)
Summary of ROM
Read-Mostly Memory
Write once during fabrication
Write once after fabrication
Re-writable at high cost
Flash memory EEPROM
Common feature: nonvolatile at the cost of flexibility
Internal Memory Types
Today’s Lecture
◆An overview of Internal Memory – two types of RAM technologies
– different ROM ◆Chip Logic
– how the bits are organized and accessed in Chip ◆Error detection and correction
– the mechanism to detect/correct errors through coding theory
Chip Logic
◆Semiconductor memory comes in package chips
– each chip contains an array of memory cells
– essential task: provide address to chip, and access bits
– how to organize and wire the cells in chips to satisfy the needs for addressing
Chip Logic
◆Key issue: how to group cells into a logical piece
– how many bits to read/write at a time
– one extreme: 1 bit a time
– the other extreme: one word a time (word: the unit for data processing in CPU)
– in between: k bits for one chip, combine multiple chips to get a word (example later)
Simple Example of 64 Cells
◆Read/Write 1 bit a time (logical data unit = 1 bit)
– each cell needs to have an address
– 64 = 2^{6}, we need 6 address lines
– remember decoder? we can use a 6-to-64 decoder
– 6 input address lines, 64 output select lines — each is connected to the select terminal of the cell
– in the chip package, 6 address pins, 1 data pins
Simple Example of 64 Cells
◆Read/Write 1 bit a time (logical data unit = 1 bit)
– we also need to consider the memory access cyles – in each cycle, we provide an address to access 1 bit – 64 cycles to access 64 bits — too slow
Simple Example of 64 Cells
◆Read/Write 8 bits a time (logical data unit = 8 bits)
– cells are organized into 8 groups, each group containing 8 cells – one group share the same address
– 3 address pins, 8 data pins
– less memory access cycles
Simple Example of 64 Cells
◆Read/Write 4 bits a time (logical data unit = 4 bits)
– we can use two chips A and B
– access 4 bits from A, and 4 bits from B using the same address – together, it is like accessing 8 bits one time
– more flexible for different processors
– the size of the logical data unit is a key design parameter
Example of 16-Mbit DRAM
◆It is implemented using four 4Mbit memory
components
– each 4 Mbit component is a 2048 x 2048 square of cells (2^22 bits)
11 address pins: A0 – A10
4 data pins: D1 – D4 (access 4 bits a time)
other control pins
16-Mbit DRM
Example of 16-Mbit DRAM
◆Use address to locate (select) the cell
– 2048 x 2048 square of cells = 2^{22} cells, intuitively, we need 22 address lines
– however, there are only 11 address pins (A0 – A10)
– solution: use an external select logic (a multiplexer), where input is
the 22 address lines and output is the 11 address pins
– effect: divided the 22 address lines into 2 groups, which are fed into the chip through 11 address pins separately
Example of 16-Mbit DRAM
◆Use address to locate (select) the cell
– 11 row address lines/11 column address lines
– use another two pins to indicate: RAS (row address select) and CAS
(column address select)
– then, use can use a 11-to-2048 decoder to select the corrsponding row and column –> locate a cell in one square
duplicate of 4 squares –> select 4 bits at a time
Example of 16-Mbit DRAM ◆Read/Write operation
– 4 data lines (pins, D1 – D4), each connecting to one square
– write: apply high/low voltage to the data lines to charge the
capacitors
– read: use a sense amplifier to sense the voltage
– two pins to control write/read: WE (write enable) and OE (output enable)
– we can use multiple Chips to read/write a word at a time depending on the processor
Summary of Chip Logic ◆Current technology:
– we can make very large capacity in a very small area
– however, the limit is bounded by the physical space needed for pins — careful design to save number of pins is important
Summary of Chip Logic ◆Chip Logic considerations:
– determine the number of data pins (how many bits to read/write at a time)
– determine the number of address pins (need consideration of address multiplexing)
– need for additional buffers and controls
– layout and wiring need to consider heat distribution (data pins are distributed on the two sides of the chip)
Today’s Lecture
◆An overview of Internal Memory – two types of RAM technologies
– different ROM ◆Chip Logic
– how the bits are organized and accessed in Chip ◆Error detection and correction
– the mechanism to detect/correct errors through coding theory
Memory Errors ◆Hard Failure
– permanent physical defect to cells – replacement
◆Soft Error
– content of the cell is modified, due to random, nondestructive
– the function of cell is still OK
– example: the charging to the capacitor is not sufficient: 1 -> 0
Memory Errors ◆Error Detection
– knowing that there are errors in a block of data ◆Error Correction
– detect, and recover the correct contents
– correction is harder than detection
– example: we know there are an even number of 1’s in the data (detection is easy); correction is hard: there could be multiple combinations of errors
Coding Theory
◆Coding theory itself is a fruitful field of study
– general idea: use redundancy to encode the conditions for which correct data should satisfy — redundancy is a function of original data: K = f(M)
original data M
original data M
original data M
illsutrative example: modular operation K = M mod n
Generally, we will refer to the encoded result as the Error-Correting code
Framework of Error Correction
(M+K) bits are stored together in memory
Example: Hash Functions for Error Detection
We want to download a file M
Along with the file, we can also download a Hash value of the file: SHA1 = Hash(M)
After download, we can generate SHA1′ = Hash(M’)
By comparing SHA1′ and SHA1, we can know whether M’ = M
Warm-up: single parity code ◆Settings
– original data block M has 7 bits (abuse of term, M = 7)
– attach a single bit K to the end of block (K=1)
– the code thus has 8 bits, M|| K — this is a simple encoding process – given M, we need to decide K
Warm-up: single parity code ◆Enconding rule
– function W(D) = number of 1’s in data block D
– Rule: add K such that W(M||K) is even (even parity) – example: M = 000 0011, W(M) = 2 -> set K = 0
– M = 110 0111, W(M) = 5 -> set K = 1
– we also could have odd parity
One Error Detection
◆The single parity code is able to detect one error
– suppose the stored data is D, we can compute W(D)
– if W(D) is even –> no error; else one error
– note that the above detection algorithm relies on one essential assumption: there is at most one error
– why? consider if there are two errors
– also note that, we can only detect error, we do not know the position of the error (cannot correct the error)
One Error Detection ◆Example:
– suppose M = 000 0011, W(M) = 2 –> K = 0
– store M||K = 000 0011 0 in the storage device
– some time later, we check this data block D by computing W(D)
– suppose W(D) = 3 –> error: e.g., 000 0111 0 or 000 0011 1
– suppose W(D) = 2 –> correct; but could also be 000 0101 0 (two errors, we assume that this could not happen)
One Error Detection ◆The Essence:
– we are using 1 redundant bit to encode two cases: – case 1: no error
– case 2: 1 error
– question: can we extend this idea to general error-correcting code?
General Case
◆Consider one error correcting code
– original data M bits, redundancy K bits; together N = M + K bits
– again, we assume that there is at most one error
– our goal is to correct one error (if happens) — in other words, know the position of the error
– there are a total of (N+1) cases. Why?
General Case ◆(N+1) cases:
– case 0: no error
– case 1: error at position 1
– case t: error at position t
– the essence of error correction code: use K bits to encode (N+1) cases
– relation: 2^{K} >= M + K +1
– coding theory deals with the realization of the above encoding process using mathematical tools
General Case
◆Overhead: K/M, which is the redundancy ratio
– M = 4 -> K = 3 ( 2^3 = 8 >= 4 + 3 +1); K/M = 3/4
– M = 8 -> K = 4 ( 2^4 = 16 >= 8 + 4 +1); K/M = 4/8
– M = 16 -> K = 5 ( 2^5 = 32 >= 16 + 5 +1); K/M = 5/16 – as M increases, the overhead decreases
General Case
◆So, is M the larger the better?
– unfortunately, no
– remember the fundamental assumption: at most one error
– as M increases, the probability of having more errors also goes up
Case Study: (7-4) Hamming Code ◆Hamming Code
– the classical one-error correction code, with (7-4) the most common setting
– N = 7, M = 4 (original data), K = 3 (redundancy bits) – we will not dig into the mathematical details
Case Study: (7-4) Hamming Code ◆Idea:
– similar to single parity code, however, we now use three parity bits – data bits: d1, d2, d3, d4
– parity bits: p1, p2, p3, where each parity bit “cover” 3 data bits
p1: cover d1, d2, d4, that is, number of 1’s in p1||d1||d2||d4 should be even
p2: cover d1, d3, d4 p3: cover d2, d3, d4
Case Study: (7-4) Hamming Code ◆Example:
– M = 1011, how to decide K
Case Study: (7-4) Hamming Code ◆Example:
– what if we found that the stored data are as below:
circle B is correct (even parity)
error happens in A and C (assume one error) the common bit is 0
should correct this 0 to 1
Case Study: (7-4) Hamming Code ◆More on Hamming Code (not required)
special organization of bits
Two matrices play important roles:
code generator matrix G: given M, generate the code
parity-check matrix H: check error
Case Study: (7-4) Hamming Code ◆The code words
– there are a total of 16 valid code words (why? 4 “free” data bits) – the Hamming distance between every two code words is 3
– Hamming distance: the number of different bits
– this explains why Hamming code can correct 1 error
code words with 1 error
assume will not happen
a code word is corrected to its closest valid code word
(7-4) Hamming code is able to detect 2 errors
two valid code words (d=3)
Reading ◆Section 5.1
– differences between DRAM and SRAM
– types of ROM
– chip logic (example of 16M-bit organization) – chip packaging (brief understanding)
◆Section 5.2
– concepts of error-detection and correction through coding theory – simple examples of Hamming code (details not required)
Part II: External Memory
• Magnetic Disk
– The most important external memory device on almost all computer systems
– Working mechanism
• The Organization of Multiple Disks
– RAID family
• Other external memory types – SSD
Magnetic Disk
Store bits
Allow the platter to spin
Magnetic Disk
How bits are read/written?
(1) Head moves to the “right position” (2) Platter spins
There could be multiple Platters and Heads
How are the Bits stored on Platter? • Platter
– Nonmagnetic material covered with magnetic “coats”
– On the magnetic surface, there are many magnetized spots –
each spot stores one bit
– More specifically, each magnetized spot has two polarities: S and N
– The orientations (S-N or N-S) are represented as 0 or 1
– Example: 120Gb hard disk drive contains over 120 billion spots!
How are the Bits Read/Written
• The interaction between Head and Platter
– The essence is the electromagnetic fields – the change of current will cause the change the magnetic fields, and vice versa
– Head is covered with magnetic fields and electronic wires
Illustration of Read/Write Head
How are the Bits Read/Written
• The interaction between Head and Platter
– Read and write essentially have the same mechanism: the direction of the current in the Head corresponds to the orientation of the magnetized spot
– Two states of the directions of current = two states of the orientations (S-N or N-S)
– Read: magnetic (Platter) → current (Head)
– Write: current (Head) → magnetic (Platter)
How are the Bits Organized on Platter • Tracks and Sectors on Platter
– The patter contains a set of concentric rings, called tracks – Each track contains a number of sectors
– Sector = a number of magnetized spots ( a block of data) – The size of a sector may vary
How are the Bits Organized on Platter
The size of the Head is the same as the width of the track (the head will read/write the tracks)
Intersector gap and intertrack gap: separate the sectors, to minimize the errors due to misalignment of the head or simply reduce the interference of magnetic fields
One issue with this Organization
• There could be different date rates for different tracks
– The head is fixed while the platter is spinning
– Inner and Outer tracks have different speed relatively to the head – this result in different data rates when reading/writing bits
stored in inner and outer tracks
Arrangement 1: Constant Angular Velocity (CAV)
• Ideal: rotate the platter at a constant speed,
but the densities of spots (bits) on different
tracks are different
– Platter is divided into a number of pie-shaped sectors – advantage: blocks of data can be addressed by tracks and sectors
– Disadvantage: amount of data can be stored on long outer tracks is only the same as what can be stored on short inner tracks (waste of space)
Arrangement 2: Multiple Zone Recording • Platter are organized into zones
– Each zone has multiple tracks
– Outer track has more sectors
– The densities of the sectors are the same – increased capacity
– Various data transfer rate (for some disk designs, the rotation speed may change to achieve constant transfer rate)
Zone in the same color
Components of Disk Drive • Data organization on Disk
– Disk – Platters – Tracks – Sectors
– Head has the same width as that of tracks (or
– Read/Write by sectors (one sector usually contain 512 bytes
– question: how to locate the desired sectors within a track?
How to Locate Sector Positions within Track • Use extra control data as Marks
– Extra control data – used only by disk driver, not accessible by users
– Format of Disk (the organization of user data and control data)
– Example: Format: each track has 30 sectors, each sector has 600 bytes (512 for dat
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com