Comp 255 - Computer Organization - Memory and I/O
"A computer is an electronic (?) device operating under control of instructions
stored in its own memory unit that
- accepts data (input)
- processes data arithmetically and logically
- displays information (output) from the processing and/or
- stores the results for future use"
Memory
Addressable Memory can be thought of a linear sequence of numbered same
sized "cells". Each cell has the same number of bits.
+-----+
| MAR | selects cell address
+-----+
|
+------+ +-------+
0000 | 1234 | <-+-> | M B R | reads/writes
+------+ | +-------+ cell contents
0001 | 7700 | <-|
+------+ |
0002 | 0000 | <-|
+------+ |
0003 | AAFF | <-|
+------+ |
0004 | 0100 | <-|
.... |
|
+------+ |
FFFF | 0000 | <-+
+------+
We distinquish between the address of a cell and the contents
of a cell. Access to memory is controlled by two registers, the Memory Address
Register (MAR) and the Memory Buffer Register (MBR). An "address" placed
in the MAR will select a cell of memory. A memory read will cause
the contents of that cell to be copied to the MBR; a memory write
will cause the contents of the MBR to be copied to the cell.
- smallest "unit" of information is a bit (0/1)- contraction
of BInary digiT. Each cell is a sequence of bits. n bits can store 2^n different
patterns/units of information
- integers stored in a memory cell can be represented in binary (base
2) or binary coded decimal (BCD).
- An m bit memory address can address 2^m memory cells
- A fixed size memory (in bits) can be organized in different ways.
For example a 96 bit memory can be organized into
- 12 8-bit cells or
- 8 12-bit cells or
- 6 16-bit cells
- Memory Cell "sizes". A byte is the amount of memory used
to store a character. A word is the amount of memory used to store
an integer.
- byte = 8 bits
- word (sometimes called half-word) = 16 bits or 2 bytes
- double or longword (word) = 32 bits
- quadword (double word) = 64 bits
- Why do older computer architectures use word lengths which are multiples
of 6 (e.g. 12, 18, or 36)? Answer: Early computers used 6 bit character codes.
- Byte Ordering: the numbering of bytes within a word
- Big Endian - numbering begins at big end (most significant byte);
left to right numbering)
- Little Endian - numbering begins at little end (least significant
byte); right to left numbering)
Example of "Big Endian" vs "Little Endian" Addressing (See Fig 2-12).
A record consisting of the 12 byte string "JIM SMITH " following by two 32
bit integers 21 (15h) and 260 (104h) is stored in a block of 20 bytes.
Problems occur if we copy a record from a Big Endian computer to a Little
Endian computer.
Big Endian Little Endian
+-----+-----+-----+-----+ +-----+-----+-----+-----+
0 | J | I | M | | | | M | I | J | 0
+-----+-----+-----+-----+ +-----+-----+-----+-----+
4 | S | M | I | T | | T | I | M | S | 4
+-----+-----+-----+-----+ +-----+-----+-----+-----+
8 | H | | | | | | | | H | 8
+-----+-----+-----+-----+ +-----+-----+-----+-----+
12 | 0 0 | 0 0 | 0 0 | 1 5 | | 0 0 | 0 0 | 0 0 | 1 5 | 12
+-----+-----+-----+-----+ +-----+-----+-----+-----+
16 | 0 0 | 0 0 | 0 1 | 0 4 | | 0 0 | 0 0 | 0 1 | 0 4 | 16
+-----+-----+-----+-----+ +-----+-----+-----+-----+
If the Big Endian formated record on the right is copied to a Little Endian
computer, the record on the left below results. Note that the integers are
wrong.
If we copy and swap the bytes within a 32 bit word (see below right), the
string comes out backward.
Xfer Big to Little Xfer and Swap
+-----+-----+-----+-----+ +-----+-----+-----+-----+
| | M | I | J | 0 | J | I | M | | 0
+-----+-----+-----+-----+ +-----+-----+-----+-----+
| T | I | M | S | 4 | S | M | I | T | 4
+-----+-----+-----+-----+ +-----+-----+-----+-----+
| | | | H | 8 | H | | | | 8
+-----+-----+-----+-----+ +-----+-----+-----+-----+
| 1 5 | 0 0 | 0 0 | 0 0 | 12 | 0 0 | 0 0 | 0 0 | 1 5 | 12
+-----+-----+-----+-----+ +-----+-----+-----+-----+
| 0 4 | 0 1 | 0 0 | 0 0 | 16 | 0 0 | 0 0 | 0 1 | 0 4 | 16
+-----+-----+-----+-----+ +-----+-----+-----+-----+
integers wrong string wrong
Error Detecting/Correcting Codes
- Parity Checking (even/odd parity) : An additional check bit
is attached to the data bits. It is set or cleared so that the total
number of one bits is even (or odd). Any single-bit error is easily detected
since the number of one bits is odd (even) when it should be even (odd).
- Hamming distance : the number of bit positions in which two codewords
differ. Parity checking has Hamming distance 2.
- Single-Bit Error correcting codes can be defined. They have a Hamming
distance of at least three.
Designing a single-bit error correcting code
There is a lower bounds for the size (i.e. total number of bits needed).
Assume m code bits and r check bits for n bits total.
Each of the 2^m legal codes (there are m code bits) has n illegal code
words at distance 1 from it. So each legal codeword takes up (n+1) codewords
(itself plus n single bit changes) for a total of (n+1)*2^m code word in
all. Thus (n+1)*2^m <= 2^n. Since n = m+r we obtain (m+r+1) <= 2^r.
Given m, this puts a lower bound on the number of check bits r.
Example If m = 16 then r = 5 (16+5+1<=2^5) so we need a 21 bit
codeword. (Note r = 5 works for values of m up to 26). We number the bits
of our code word 1 - 21 and we make bits 1, 2, 4, 8, and 16 (note powers
of 2)the check bits. The other 16 bits are data bits. Each check bit serves
as an (even) parity bit for a special "parity" sub-group of the 21 bits.
- Bit 1 checks bits 1, 3, 5, 7, 9, 11, 13, 17, 19, 21 (Group 1)
- Bit 2 checks bits 2, 3, 6, 7, 10, 11, 14, 15, 18, 19 (Group 2)
- Bit 4 checks bits 4, 5, 6, 7, 12, 13, 14, 15, 20, 21 (Group 4)
- Bit 8 checks bits 8, 9, 10, 11, 12, 13, 14, 15 (Group 8)
- Bit 16 checks bits 16, 17, 18, 19, 20, 21 (Group 16)
The diagram below makes this easier to see.
1 1 1 1 1 1 1 1 1 1 2 2 <- bit number
1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
- - - - - - - - - - - - - - - - - - - - -
x x d x d d d x d d d d d d d x d d d d d <- code word
- - - - - - - - - - - - - - - - - - - - -
1 1 1 1 1 1 1 1 1 1 1 <- Group 1 bits
2 2 2 2 2 2 2 2 2 2 <- Group 2 bits
4 4 4 4 4 4 4 4 4 4 <- Group 4 bits
8 8 8 8 8 8 8 8 <- Group 8 bits
h h h h h h <- Group 16 bits
x - denotes check bit
d - denotes data bit
Note: The sum of the Group numbers for each bit
equals its bit number.
There is a formula that assigns each bit to a parity group. Express the
bit number as a sum of powers of 2. The bit belongs to those groups. For example
11 = 8+2+1 so bit 11 belongs to groups 1, 2, and 8. This is critical since
it permits any single-bit error to be easily identified by summing the parity
group numbers (1,2,4,8,or 16) which fail to have even parity. For example,
if groups 1, 2, and 8 failed to have even parity, bit 11 is the error bit.
Cache Memory
Cache memory is special high speed memory usually located on or very near
the processor chip. When a word is fetched from memory, it (along with any
words close by) is loaded in cache. If the same word is needed again, it's
quicker to locate it in cache. The locality princple is the observation
that memory references over a short period of time tend to come from the
same location in memory. If a word is accessed k times over a short
time inteval, it will require one reference to slow memory and k-1 references
to cache. We can quantitize this as follows.
Let c = cache access time.
m = memory access time
h = hit ratio, fraction of all references satisfied out of cache
that is h = (k-1)/k then
If on a cache miss the word is first loaded into cache and then the word
is read from cache (non Load Through), the mean access time of a
word is c + (1-h)m where (1-h) is sometimes called the miss ratio.
Example If cache access time c is 10 nsec, memory access time m is
200 nsec and h, the hit ratio is 0.9, the mean access time is
mean access = 10 nsec + 0.1 * 200 nsec = 30 nsec
Otherwise, with Load Through (on a cache miss the word is loaded
in parallel to cache and the CPU) the mean acces time of a word is h*c +
(1-h)*m. This would change the mean access time in the above example to 29
nsec.
mean access = 0.9 * 10 nsec + 0.1 * 200
nsec = 29 nsec
Issues in Cache Design
- size of cache line (8 - 64 bytes); memory parititioned into mutually
exclusive cache lines
- size of cache - number of cache slots (cache slot = cache line)
- organization (associative, direct, two-way set associative); see
Small
Memory Cache Examples
- associative - cache line mapped to any cache slot - associative
search on all tag fields
- direct - cache line mapped to only one cache slot - tag fields compared
- set-assocative - cache line mapped to only one set of cache
slots - associative seach on tag fields for set
- replacement policy (associative & set associative origanization
only)
- LRU - least recently used (time stamp last access)
- FIFO - first in first out (time stamp when loaded)
- LFU - least frequently used (count number of accesses)
- Random
- Oracle (Optimal) - predict next access time for all lines
- cache read and write policies
- Read/Cache Miss: load through (load to cache and CPU in parallel)
vs non-load through (load cache only and read again)
- Write/Cache Hit: write through (write to cache and main memory
in parallel) vs write back (write to cache only; defer main memory update
until cache line flushed)
- Write/Cache Miss: write allocate (load into cache and update) vs
non-write allocate (write to main memory only)
- observation: most traffic is towards cache away from main memory
(4 reads to 1 write?)
- unified vs split cache (separate caches for instructions and data;
instruction cache is read only)
- numbers of cache - L1 (on chip) vs L2 cache
Return
to Comp 255 Home Page