Unit 3

Memory Organization

• Memory Hierarchy
  
• Main Memory
  
• Auxiliary Memory
  
• Associative Memory
  
• Cache Memory
  
• Virtual Memory
  

  
   

Memory Hierarchy

 

The memory unit is an essential component in any digital computer since it is needed for storing programs and data. A very small computer with a limited application may be able to fulfill its intended task without the need of additional storage capacity. Most general purpose computers would run more efficiently if they were equipped with additional storage beyond the capacity of the main memory.

 

Auxiliary Memory:

The memory unit that communicates directly with the CPU is called the main memory. Devices that provide backup storage are called auxiliary memory. The most common auxiliary memory devices used in computer systems are magnetic disks and tapes. They are used for storing system programs, large data files, and other backup information. Only programs and data currently needed by the processor reside in main memory. All other information is stored in auxiliary memory and transferred to main memory when needed.

The total memory capacity of a computer can be visualized as being a hierarchy of components. The memory hierarchy system consists of all storage devices employed in a computer system from the slow but high-capacity auxiliary memory to a relatively faster main memory to an even smaller and faster cache memory accessible to high-speed processing logic.

 

Memory hierarchy in a computer system:

 

 

 

At the bottom of the hierarchy are the relatively slow magnetic tapes used to store removable files. Next are the magnetic disks, which is used for backup storage. The main memory occupies a central position by being able to communicate directly with the CPU and with auxiliary memory devices through an I/O processor. When the CPU needs programs not residing in main memory, they are brought in from auxiliary memory. Programs not currently needed in main memory are transferred into auxiliary memory to provide space for currently used programs and data.

 

Cache Memory:

A special very-high speed memory called a cache is sometimes used to increase the speed of processing by making current programs and data available to the CPU at a rapid rate. The cache is used for storing segments of programs currently being executed in the CPU and temporary data frequently needed in the present calculations.

While the I/O processor manages data transfers between auxiliary memory and main memory, the cache organization is concerned with the transfer of information between main memory and CPU. Thus each is involved with a different level in the memory hierarchy system.

 

Reasons for having two or three levels of memory hierarchy:

As the storage capacity of the memory increases, the cost per bit for storing binary information decreases and the access time of the memory becomes longer. The auxiliary memory has a large storage capacity, is relatively inexpensive, but has low access speed compared to main memory. The cache memory is very small, relatively expensive, and has very high access speed. Thus as the memory access speed increases, so does its relative cost. The overall goal of using a memory hierarchy is to obtain the highest-possible average access speed while minimizing the total cost of the entire memory system.

 

MAIN MEMORY:

The main memory is the central storage unit in a computer system. It is a relatively large and fast memory used to store programs and data during the computer operation.

 

RAM (random – access memory):

The principal technology used for the main memory is based on semiconductor integrated circuits. Integrated circuit RAM chips are available in two possible operating modes , static and dynamic. The static RAM consists essentially of internal flip-flops that store the binary information. The stored information remains valid as long as power is applied to the unit. The dynamic RAM stores the binary information in the form of electric charges that are applied to capacitors.

The dynamic RAM offers reduced power consumption and larger storage capacity in a single memory chip. The static RAM is easier to use and has shorter read and write cycles.

 

ROM (read-only memory)

Most of the main memory in a general-purpose computer is made up of RAM integrated circuit chips, but a portion of the memory may be constructed with ROM chips. RAM was used to refer to a random-access memory, but now it is used of designate a read/write memory to distinguish it from a read-only memory, although ROM is also random access. ROM is used for storing programs that are permanently resident in the computer and for tables of constants that donot change in value once the production of the computer is completed.

 

Bootstrap loader:

The ROM portion of main memory is needed for storing an initial program called a bootstrap loader. The bootstrap loader is a program whose function is to start the computer software operation when power is turned on. Since RAM is volatile, its contents are destroyed when power is turned off. The contents of ROM remain unchanged after power is turned off and an again.

 

RAM and ROM Chips:

A RAM chip is better suited for communication with the CPU if it has one or more control inputs that select the chip only when needed. Another common feature is a bidirectional data bus that allows the transfer of data either from memory to CPU during a read operation or from CPU to memory during a write operation.

A bidirectional bus can be constructed with three-state buffers. A three-state buffer output can be placed in one of three possible states: a signal equivalent to logic 1 , a signal equivalent to logic 0 , or a high impedance state. The logic 1 and 0 are normal digital signals. The high impedance state behaves like an open circuit, which means that the output does not carry a signal and has no logic significance.

 

 

 

The capacity of the RAM memory is 128 words of eight bits (one byte) per word. This requires a 7 bit address and an 8-bit data bus. The read and write inputs specify the memory operation and the two chips (CS) control inputs are for enabling the chip only when it is selected by the microprocessor. The availability of more than one control input facilitates the decoding of the address lines when multiple chips are used in the microcomputer. The read and write inputs are sometimes combined into one line labeled R/W. When the chips is selected, the two binary stated in this line specify the two operations of read or write.

 

Operations of the function table:

 

CS1 CS2 RD WR	Memory function	State of data bus
0 0 * *   0 1 * *   1 0 0 0   1 0 0 1   1 0 1 *   1 1 * *	Inhibit   Inhibit   Inhibit   Write   Read   Inhibit	High-impedance   High-impedance   High-impedance   Input data to RAM   Output data from RAM   High-impedance

 

The above function table specifies the operation of the RAM chip. The unit is in operation only when CS1=1 and CS2 =0. The bar on top of the second select variable indicates that its input is enabled when it is equal to 0. If the chip select inputs are not enabled, or if they are enabled but the read or write inputs are not enabled, the memory is inhibited and its data bus is in a high-impedance state. When the WR input is enabled, the memory stores a byte from the data bus into a location specified by the address input lines. When the RD input is enabled, the content of the selected byte is placed into the data bus. The RD and WR signals control the memory operation as well as the bus buffers associated with the bidirectional data bus. The two inputs must be CS1=1 and CS2 =0 for the unit to operate. Otherwise the data bus is in a high-impedance state. There is no need for a read or write control because the unit can only read.

 

Memory Address Map:

The designer of a computer system must calculate the amount of memory required for the particular application and assign it to either RAM or ROM. The addressing of memory can be established by means of a table that specifies the memory address assigned to each chip. The table, called a memory address map, is a pictorial representation of assigned address space for each chip in the system.

Component Hexadecimal Address bus address 10 9 8 7 6 5 4 3 2 1

RAM 1 0000-007F 0 0 0 * * * * * * *   RAM 2 0080-00FF 0 0 0 1 * * * * * *   RAM 3 0100-017F 0 1 0 * * * * * * *   RAM 4 0180-01FF 0 1 1 * * * * * * *   ROM 0200-03FF 1 * * * * * * * * *

 

In the above table the hexadecimal address column assigns a range of hexadecimal equivalent addresses for each chip. The address bus lines are listed in the third column. Although there are 16 lines in the address bus, the table shows only 10 lines because the other 6 are not used in this example and are assumed to be zero. The small *'s under the address bus lines designate those lines that must be connected to the address inputs in each chip. The RAM chips have 128 bytes and need seven address lines. The ROM chip has 512 bytes and needs 9 address lines. The *'s always assigned to the low order bus lines. Lines 1 through 7 for the RAM and lines 1 through 9 for the ROM. It is now necessary to distinguish between four RAM chips by assigning to each a different address. For this particular example we choose bus lines 8 and 9 to represent four distinct binary combinations. The distinction between a RAM and ROM address is done with another bus line. Here we choose line 10 for this purpose. When line 10 is 0, the CPU selects a RAM, and when this line is equal to 1, it selects ROM.

 

The address bus lines are subdivided into groups of four bits each so that each group can be represented with a hexadecimal digit. The first hexadecimal digit represents lines 13 to 16 and is always 0. The next hexadecimal digit represents lines 9 to 12, but lines 11 and 12 are always 0. The range of hexadecimal addresses for each component is determined from the *'s associated with it. These *'s represent a binary number that can range from an all-0's to an all-1'a value.

 

AUXILIARY MEMORY

The most common auxiliary memory devices used in computer systems are magnetic disks and tapes. Other components used, but not as frequently , are magnetic drums , magnetic bubble memory and optical disks. The important characteristics of any device are its access mode , access time , transfer rate , capacity and cost.

The average time required to reach a storage location in memory and obtain its contents is called access time. In electomechanical devices with moving parts such as disks and tapes , the access time consists of a seek time required to position the read-writ head to a location and a transfer time required to transfer data to or from the devices. Because the seek time is usually much linger than the transfer time, auxiliary storage is organized in records or blocks. The transfer rate is the number of characters or words that the device can transfer per second, after it has been positioned at the beginning of the record.

 

Magnetic Disks

 

 

 

 

 

 

A magnetic disk is a circular plate constructed of metal or plastic coated with magnetized material. Often both sides of the disk are used and several disks may be stacked on one spindle with read/write heads available on each surface. All disks rotate together at high speed and are not stopped or started for access purposes. Bits are stored in the magnetized surface in spots along concentric circles called tracks. The tracks are commonly divided into sections called sectors.

Address bits that specify the disk number, the disk surface, the sector number and the track within the sector address a disk system. After the read/write heads are positioned in the specified track , the system has to wait until the rotated disk reaches the specified sector under the read/write head. Information transfer is very fast once the beginning of a sector has been reached.

A track in a given sector near the circumference is longer than a track near the center of the disk. If bits are recorded with equal density, some tracks will contain more recorded bits than others.

Disks that are permanently attached to the unit assembly and cannot be removed by the occasional user are called hard disks. A disk drive with removable disks is called floppy disks. Floppy disks are extensively used in personal computers as a medium for distributing software to computer users.

 

Magnetic Tape:

 

 

 

 

Magnetic tape is a strip of plastic coated with a magnetic recording medium. Bits are recorded as a Magnetic spots on the tape along several tracks. Usually 7 or 8 bits are recorded simultaneously to form a character. Magnetic tape units can be stopped started to move forward or in reveres or can be rewound. But they cannot be started or stopped fast enough between individual characters. By reading the bit pattern at the end of the record, the control recognizes the beginning of a gap. A tape unit is addressed by specifying the record number and the number of characters in the record. Records may be of fixed or variable length.

 

AUXILIARY MEMORY

Many data-processing applications require the search of items in a table stored in memory. An assembler program searches the symbol of address table in order to extract the symbol's binary equivalent. The search procedure is a strategy for choosing a sequence of addresses, reading the content of memory of each address and comparing the information read with the item being searched until a match occurs. The number of accesses to memory depends on the location of the item and the efficiency of the search algorithm.

The time required to find an item stored in memory can be reduced considerably if stored data can be identified for access by the content of the data itself rather by an address. A Memory unit accessed by the content is called an Associative Memory (or) Content addressable memory (CAM)

 

Example:

When a word is written in an Associative memory, no address is given. The memory is capable of finding an empty unused location to store the word. When a word is to be read from an Associative memory, the content of the word or part of the word is specified.

Hardware Organization:

 

 

 

 

 

The above diagram explains the associative memory. It consists of a memory array and logic for m words with n bits per word. The argument register A and key register K each have n bits , one for each bit of a word. The match register M has m bits , one for each memory word. Each word in memory is compared in parallel with the content of the argument register. The words that match the bits of the argument register set a corresponding bit in the match register. After the matching process, those bits in the match register that have been set indicate the fact that their corresponding words have been matched. Reading is accomplished by a sequential access to memory for those words whose corresponding bit in the match register have been sent.

 

The key register provides a mask for choosing a particular field or key in the argument word. The entire argument is compared with each memory word if the key register contains all 1's. Otherwise, only those bits in the argument that have 1's in their corresponding position of the key register are compared. Thus the key provides a mask or identifying a piece of information, which specifies how the reference to memory is made.

 

 

Example

 

A 1 0 1 1 1 1 0 0 0

 

K 1 1 1 0 0 0 0 0 0

 

Word1 1 0 0 1 1 1 1 0 0 (No Match)

 

Word2 1 0 1 0 0 0 0 0 1 (Match)

 

Let us consider that the argument register A and the key register K have the bit configuration shown above. Only the three leftmost bits of A are compared with memory words because K has 1's in these positions.

Word2 matches the unmasked argument field because the three leftmost bits of the argument and the words are equal.

Read Operation:

If more than one word in memory matched the unmasked argument field , all the matched words will have 1's in the corresponding bit position of the Match register. The matched words are read in sequence by applying a read signal to each word line whose corresponding Mi bit is one. If we exclude words having a Zero content , and all zero O/P will indicate that no match occurred and that the searched item is not available in memory.

 

Write Operation:

The Associative memory must have a write capability for storing the information to be searched. Writing in an Associative memory can take different forms depending on the application. Addressing each location in sequence can do if the entire memory is loaded with new information at once prior to a search operation than the writing.

 

Tag Register:

If unwanted words to be deleted and new words to be inserted one at a time, then there is a need for a special register, to distinguish between active and inactive words. This register is called as TAG REGISTER. In Tag register active words are denoted as 1, and inactive words are denoted as 0.

 

CACHE MEMORY

The fundamental idea of cache organization is that by keeping the most frequently accessed instruction and data in the fast cache memory, the average memory access time will approach the access time of the cache. Although the cache is only a small fraction of the size of main memory, a large fraction of memory requests will be found in the fast cache memory because of the locality of reference property of the programs.

 

The basic operations of cache:

When the CPU needs to access the memory, Cache is examined. If the word is found in the cache, it is read from the fast memory. If the word addressed by the CPU not found in the cache, the main memory is accessed to read the word. The performance of Cache memory is frequently measured in terms of a quantity called Hit ratio. When the CPU refers the memory and finds the word in Cache, it is said to produce a HIT, else if the word is not found and it is in Main memory, it counts as a Miss.

The basic characteristic of cache memory is its fast access time. Therefore, very little or no time must be wasted when searching for words in the cache.

 

Mapping:

The transformation of data from main memory to cache memory is referred to as a mapping process. There are three types of mapping procedures. They are as follows:

1. Associative mapping
   
2. Direct mapping
   
3. Set-associative mapping
   

   
    

Example of Cache Memory:

 

 

In the above figure the main memory can store 32K words of 12 bits each. The cache is capable of storing 512 of these words at any given time. For every word stored in cache, there is a duplicate copy in main memory. The CPU communicates with both memories. It first sends a 15-bit address to cache. If there is a hit, the CPU accepts the 12-bit data from cache. If there is a miss, the CPU reads the word from main memory and the word is then transferred to cache.

 

Associative Mapping:

The fastest and most flexible cache organization uses an associative memory. The associative memory stores both the address and content (data) of the memory word. This permits any location in cache to store any word from main memory.

Associative mapping cache(all numbers in octal)

 

 

The above diagram shows three words presently stored in the cache. The address value of 15 bits is shown as five-digit octal number and its corresponding 12-bit word is shown as a four-digit octal number. A CPU address of 15 bits is placed in the argument register and the associative memory is searched for a matching address. If the address is found, the corresponding 12-bit data is read and sent to the CPU. If no match occurs, the main memory is accessed for the word. The address-data pair is then transferred to the associative-memory cache. If the cache is full, an address-data pair must be displaced to make room for a pair that is needed and not presently in the cache.

The decision as to what pair is replaced is determined from the replacement algorithm that the designer chooses for the cache. A simple procedure is to replace cells of the cache in round-robin order whenever a new word is requested from main memory. This constitutes a first-in-first (FIFO) replacement policy.

 

Direct Mapping:

Associative memories are expensive compared to random-access memories because of the added logic associated with each cell.

Addressing relationships between cache and cache memories

 

 

 

The CPU address of 15 bits is divided into two fields. The nine least significant bits constitute the index fields and the reaming six bits for the tag field. The figure shows the main memory needs an address that includes both the tag and the index bits. The number of bits in the index field is equal to the number of address bits required to access the cache memory.

Direct Mapping:

 

 

The word at address zero is presently stored in the cache (index = 000 , tag = 1220 ). Suppose that the CPU now wants to access the word at address 02000. The index address is 000, so it is used to access the cache. The two tags are then compared. The cache tag is 00 but the address tag is 02, which does not produce the match. Therefore, the main memory is accessed and the data word 5670 is transferred to the CPU. The cache word at index address 000 is than replaced with a tag 02 and data of 5670.

 

The disadvantage of direct mapping is that the hit ration can drop considerably if two or more words whose addresses have the same index but different tags are accessed rapidly.

 

 

 

 

 

Set-Associative Mapping:

 

It was mentioned that the disadvantage of direct mapping is that two words with the same index in their address but with different tag values cannot reside in the cache memory at the same time.

 

A third type of cache organization, called set-associative mapping, is an improvement over the direct-mapping organization in that each word of cache can store two or more words of memory under the same index address. Each data word is stored together with its tag and the number of tag-data items in one word of cache is said to form a set.

 

 

 

 

 

 

 

 

 

 

 

 

 

When the CPU generates a memory request, the index value of the address is used to access the cache. The tag field of the CPU address is then compared with both tags in the cache to determine if a match occurs. The comparison logic is done by an associative search of the tags in the set similar to an associative memory search: thus the name "set-associative". The hit ratio will improve as the set size increase because more words with the same index but different tags can reside the cache. However, an increase in the set size increases the number of bits in words of cache and requires more complex comparison logic.

VIRTUAL MEMORY

Virtual memory is a concept used in some large computer systems that permit the user to construct programs as though a large memory space were available, equal to the totality of auxiliary memory. Each address that is referred by the CPU goes through an address mapping from the virtual address to a physical address in main memory. A Virtual memory system provides a mechanism for translating program-generated addresses into correct main memory locations.

 

Address and memory space:

• An address used by Programmer called as Virtual address.
  

 

• The set of such address is called as address space.
  

 

• An address in main memory is called as location or physical address.
  

 

In multiprogramming computer system, programs and data are transferred to and from auxiliary memory and main memory based on demands imposed by the CPU. Suppose that program1 is currently being executed in the CPU. Program1 and a portion of its associated data are moved from auxiliary memory into main memory is shown in the below figure.

 

 

 

 

 

Memory table for mapping a virtual address

    
 

Virtual address

 

 

In a virtual memory system, programmers are told that they have the total address space at their disposal. Moreover, the address field of the instruction code has a sufficient number of bits to specify all virtual address. In the example, the address of an instruction code will consist of 20 bits but physical memory addresses must be specified with only 15 bits. The CPU will reference instructions and data with a 20-bit address, but the information at this address must be taken from physical memory because access to auxiliary storage of r individual word will prohibitively long.

 

A table is needed as shown above, to map a virtual address of 20 bits to a physical address of 15 bits. The mapping is a dynamic operation, which means that every address is translated immediately as CPU references a word.

 

As per the above diagram, the mapping table may be stored in a separate memory in the first case; an additional memory unit is required as well as one extra memory access time. In the second case, the table takes space from main memory and two accesses to memory are required with the program running a half speed. A third alternative is to use an associative memory.