Structured Computer Organization, by Tanenbaum
Chapter 2: Computer Systems Organization
Part 2, Primary Memory

• Memory - That part of the computer where programs and data are stored.
• Bit - the basic unit of memory is the binary digit.
• BCD (Binary Coded Decimal) format - storing decimal numbers using
  binary numbers.
  • Example: 1944 = 0001 1001 0100 0100
  • Each digit, 0-9, is stored using 4 bits
  • Because 16 values are possible with 4 bits, 6 values are unused.
  • The 16 bits in this example can store numbers 0..9999
  • In binary, however, 16 bits can store 65,536 combinations
  • binary is more efficient
• Memory Addresses - Memories consist of a number of cells (or locations)
  each of which can store a piece of information
• Address - each cell has a number, called its address.
• If a memory has n cells, they will have addresses 0 to n-1.
• If a cell consists of k bits, it can hold any one of 2^k different
  bit locations
• Example: three different organizations for a 96-bit memory.
  • 12 cells with 8 bits each (12 * 8 = 96)
    For this configuration, you need an address size of 4 bits in order
    to label 12 different locations
  • 8 cells with 12 bits each (8 * 12 = 96)
    For this configuration you need 3 bits to store 8 different locations
  • 6 cells with 16 bits each (6 * 16 = 96)
    3 bits needed here to store the memory addresses
• Smallest addressable unit - the size of each memory cell
• Most manufacturers have standardized on byte (8 bits)
  
• Bytes are grouped in words -
  A computer with a 32 bit word has 4 bytes/word
  A computer with a 64 bit word has 8 bytes/word
• A 32-bit machine will have 32-bit registers for manipulating 32 bit words
  A 64-bit machine will have 64-bit registers and instructions for moving,
  adding, subtracting, and otherwise manipulating 64-bit words.
• Byte ordering
  • Big Endian - bytes are numbered left to right
  • Little Endian - bytes are numbered right to left
  • Example: storing the 32-bit integer 6:

                        Big Endian          
     
       Byte:    0        1       2        3    
            00000000 00000000 00000000 00000110
    
                        
                        Little Endian
    
       Byte:    3        2       1        0
            00000000 00000000 00000000 00000110
      

  • The 32-bit int is stored the same, the 6 is in the right-most
    bits. In Big Endian, the 6 is in byte 3, in Little Endian, the 6 is
    in byte 0.
    
  • Example 2: Mixing char and int data types
    Strings are read byte by byte, character by character
    Integers are read as a word - in this case, in a group of 4 bytes
    
    
    Name: Jim Smith (string data, read byte by byte)
    Age: 21 (integer data, read word by word - in groups of 4 bytes)
    Dept: 260 (integer data, read word by word - in groups of 4 bytes)

    Big Endian:
             0   1  2   3
    
    0        J   I  M  __
    4        S   M  I   T  
    8        H   0  0   0
    12       0   0  0  21
    16       0   0  1   4
    
    
    Little Endian:
         3   2   1   0 
    
         __  M   I   J      0
         T   I   M   S      4
         0   0   0   H      8
         0   0   0  21     12
         0   0   1   4     16
    

    
    In both Big Endian and Little Endian, the string data is read byte by byte
    starting with numerically lower byte. Both "JIM"'s are read starting with byte
    0 to byte 3. Big Endian reads strings left to right, Little Endian reads strings right to left.
    
    Integer data - read all 4 bytes at one time:
    If the bytes are transferred byte by byte from Big-->Little, the string data
    comes out okay, but the integer data comes out reversed: Little Endian:

         3   2   1   0
    
         __  M   I   J      0
         T   I   M   S      4
         0   0   0   H      8
         21  0   0   0     12
         4   1   0   0     16
    

    
    21 0 0 0, which is interpreted as
    21*256^3 = 21*2^24 in Little Endian
    Both systems look at the integer as one complete word, 4 bytes
    If you try reversing each word after it's been transferred byte by byte,
    the integer comes out okay, but the string data is not right:

       J I  M __    -->       (byte by byte)      __   M  I  J  
                          --> (then reverse) -->   J   I  M  __
     

    which is okay for Big Endian, but is read as " MIJ" in Little Endian.
    
• Error-Correcting Codes - Computer memories can make errors occasionally
  due to voltage spikes on the power line or other causes.
  To guard against such errors, some memories use error-detecting or
  error-correcting codes.
• Given a memory word consists of m data bits to which are added r "check bits"
  n = m + r, an n-bit unit containing m data bits and r check bits is
  often referred to as an n-bit codeword
• Hamming distance: the number of bit positions in which two codewords differ
• If two codewords are a Hamming distance d apart, it will require d
  single bit errors to convert one into the other.
• Example: the codewords 11110001 and 00110000 are a Hamming distance 3 apart
  because it takes 3 single-bit errors to convert one into the other.
• To detect d single-bit errors, you need a distance d + 1 code
• To correct d single-bit errors, you need a distance 2d + 1
• Parity bit - appended to the data so that the number of 1 bits in the
  codeword is even (or odd)
  • This code has a distance 2, since any single-bit error produces a
    codeword with the wrong parity.
  • It takes two single-bit errors to go from a valid codeword to another
    valid codeword.
• Another example: consider a code with only 4 valid codewords:
  0000000000 0000011111 1111100000 1111111111
  This code has a distance 5 (2*2 + 1) which means it can correct
  double errors
  
  • If the codeword 0000000111, the receiver knows that the original must
    have been 0000011111 (if there was no more than a double error)
  • If a triple error changes 0000000000 to 0000000111, the error can't be
    corrected
• Hamming Code: r parity bits are added to an m-bit word, forming a new
  word of length m + r bits.
  
  • The bits are numbered starting at 1, with bit 1 the leftmost (high-order) bit
  • All bits whose bit number is a power of 2 are parity bits, the rest
    are used for data.
  • Example: for a 16-bit word, 5 parity bits are added
    Bits 1,2,4,8, and 16 are parity bits, the rest are data bits.
  • The parity bit is set so that the total number of 1s in the
    checked positions is even (for even parity).
  • The bit positions checked by the parity bits are:
    1. Bit 1 checks bits 1,3,5,7,9,11,13,15,17,19,21
    2. Bit 2 checks bits 2,3,6,7,10,11,14,15,18,19
    3. Bit 4 checks bits 4,5,6,7,12,13,14,15,20,21
    4. Bit 8 checks bits 8,9,10,11,12,13,14,15
    5. Bit 16 checks bits 16,17,18,19,20,21
  • Bit b is checked by those bits b1,b2,..,bn such that
    b1 + b2 + ...+ bn = b.
    Bit 5 is checked by bits 1 and 4 because 1 + 4 = 5
    Bit 6 is checked by bits 2 and 4 because 2 + 4 = 6
  • Example: construct a Hamming code for the 16-bit memory word:
    1111000010101110. The 21-bit codeword is 001011100000101101110
    

    
    0  0  1  0  1  1  1  0  0   0   0   0   1   0   1   1   0   1  1  1  0
    1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18 19 20 21
    -  -     -           -                             --
    
    The parity bits are underlined.
    

  • To simulate a problem, what would happen if bit 5 were inverted
    by a surge in the power line. The new codeword would be:

    0  0  1  0  0  1  1  0  0   0   0   0   1   0   1   1   0   1  1  1  0
    1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18 19 20 21
    -  -     -           -                             --
    

  • Check the 5 parity bits (for even parity):
    1. Parity bit 1 is incorrect: 1,3,5,7,9,11,13,15,17,19,21
       contain five 1s
    2. Parity bit 2 is correct: 2,3,6,7,10,11, 14,15,18,19
       contain six 1s
    3. Parity bit 4 is incorrect: 4,5,6,7,12,13,14,15, 20,21
       contain five 1s
    4. Parity bit 8 is correct: 8,9,10,11,12,13,14,15
       contain two 1s
    5. Parity bit 16 is correct: 16,17,18,19,20,21
       contain four 1s
  • Analysis: Parity bits 1 and 4 are incorrect, so the incorrect
    is a bit that is in both lists: 5, 7, 13, 15, or 21
    7 is also correct in parity bit 2
    13 is also correct in parity bit 8
    15 is correct in parity bit 2
    21 is correct in parity bit 16
    5 is left shared by both parity bit 1 and 4.
    The incorrect bit is in bit 5.
    
  • Faster method: Add up the incorrect parity bits ( 1 + 4 = 5)
  
  
• Cache Memory - a technique of combining a small amount of fast memory (cache)
  with a large amount slow memory (main memory) to get the speed of the fast
  memory (almost) and the capacity of the large memory at a moderate price.
  
  
• The small, fast memory is called a cache: The most heavily used memory
  words are kept in the cache.
  • When the CPU needs a word, it first looks in the cache. Only if the word
    is not there, does it go to main memory.
  • If a substantial fraction of the words are in the cache, the average
    access time can be greatly reduced.
  • Success or failure of this system depends on what fraction of the words
    are in the cache.
  
  
• Locality principle: the observation that the memory references made in
  any short time interval tend to use only a small fraction of the total memory.
  
  
• The locality principle forms the basis for most cache systems.
  
  
• When a word is referenced, it and some of its neighbors are brought from
  the large slow memory into the cache, so that the next time it is used
  it can be accessed quickly.
  
  
• If a word is read or written k times in a short interval, the computer
  will need 1 reference to slow memory and k - 1 references to fast memory.
  The larger k is, the better the overall performance.
  
  
• h = (k - 1)/k where h is the "hit ratio", the fraction of all references
  that can be made from the cache.
  
  
• 1 - h is called the "miss ratio", the percentage of time where the
  reference will be made out of main memory.
  
  
• Mean access time = c + (1 - h)/m where c is the cache access time, and
  m is the main memory access time.
  
  
• As h -> 1, all references can be satisfied ou of the cache, and the
  access time approaches c.
  
  
• As h -> 0, a memory reference is needed every time, so the access time
  approaces c + m, first a time c to check the cache (unsuccessfully), and then
  a time m to do the memory reference.