COMPUTER ORGANIZATION AND ARCHITECTURE

UNIT-IV (P2)

MEMORY ORGANIZATION

I. MEMORY HIERARCHY
II. MAIN MEMORY
III. AUXILIARY MEMORY
IV. ASSOCIATE MEMORY
V. CACHE MEMORY

1
G SRUJAN REDDY MEMORY ORGANIZATION
 COMPUTER ORGANIZATION AND ARCHITECTURE

I. MEMORY HIERARCHY

 The memory unit used to store programs and data is an essential component of the computer
system.
 The efficiency of a digital computer can be increased by additional storage along with main memory.
 Computer users accumulate large amounts of data and store it in the memory. Not all accumulated
data is needed by the processor at the same time.
 It is economical to use low-cost storage devices to back up data not currently used by the CPU.
 The main unit that communicates directly with the CPU is called MAIN MEMORY. Currently used
programs and data are stored in main memory
 Devices that are used to provide backup storage are called AUXILIARY MEMORY. Examples of
auxiliary memory are magnetic tapes and magnetic disks. They store large amounts of files,
programs, and backup information. All these data are transferred to the main memory when
needed.
 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 the high-speed processing logic. The figure below illustrates
the memory hierarchy.

 The Hierarchy is as follows

 The slow memories like magnetic tapes occupy the bottom position.
 Next in the hierarchy are the magnetic disks used as backup storage
 Next in the hierarchy is occupied by the main memory which can communicate directly with the
CPU and auxiliary devices through the I/O interface.

2
G SRUJAN REDDY MEMORY ORGANIZATION
 COMPUTER ORGANIZATION AND ARCHITECTURE

 Very high-speed memory called cache is used to increase the processing speed by making current
programs and data available to the CPU at a rapid rate. Cache memory has an operating speed
nearly the same as the CPU. Cache memory occupies the top position in the memory hierarchy.
 By making programs and data available at a rapid rate, it is possible to increase the performance
rate of the computer
 I/O processor manages data transfer between the auxiliary memory and the main memory, and the
cache organization is concerned with the data transfer between the main memory and CPU.
 The main differences between auxiliary memory and cache memory are listed below

AUXILIARY MEMORY CACHE MEMORY

Auxiliary Memory is Slower Cache Memory is Faster
Auxiliary Memory has a large storage capacity Cache Memory has a small storage space
Auxiliary Memory is used to store the backup Cache Memory is used to transfer data between
files. the main memory and the CPU
Data Transfer between Auxiliary Memory and Data Transfer between Cache Memory and CPU is
CPU is slow. fast. (almost equal to the speed of the processor)
Auxiliary Memory is cheaper Cache Memory is Costlier
Auxiliary Memory holds the programs or data Cache Memory holds the program and data that
that are not currently used or frequently used are very frequently used
CPU doesn’t have direct access to auxiliary CPU has direct access to Cache memory and main
memory. The access is through DMA. memory

 Many operating systems are designed to enable the CPU to process several independent
programs concurrently. This concept, called multiprogramming, refers to the existence of two
or more programs in different parts of the memory hierarchy at the same time.
 For example, suppose that a program is being executed in the CPU and an I/O transfer is
required. The CPU initiates the I/O processor to start executing the transfer. This leaves the CPU
free to execute another program.
 In a multiprogramming system, when one program is waiting for input or output transfer, there
is another program ready to utilize the CPU.
 The part of the computer system that supervises the flow of information between auxiliary
memory and main memory is called the memory management system.

3
G SRUJAN REDDY MEMORY ORGANIZATION
 COMPUTER ORGANIZATION AND ARCHITECTURE

II. MAIN MEMORY

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

 Random Access Memory (RAM): RAM uses internal flip-flops to store binary information. RAM is
categorized as Static and Dynamic
 In Static RAM, the stored information remains valid as long as power is applied.
In Dynamic RAM, the stored information remains valid as long as power is applied but can
retain the information for a few milliseconds when power is off.
 In Static RAM, Transistors are used to store information and stored for a short time and they
don’t require refreshing
In Dynamic RAM, Capacitors are used to store information for a longer time and hence
constant refreshing is required
 Static RAM is faster, costlier, and more complex to design
Dynamic RAM is slower, cheaper, and easier to design
 Static RAM is used in cache memory and Dynamic RAM is used in main memory
 Read Only Memory (ROM):
 ROM is used for storing programs that permanently reside in the computer
 Most of the main memory in a general-purpose computer is made of RAM integrated circuit
chips, but a portion of the memory may be constructed with ROM chips.
 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 operating 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 on again.
 The startup of a computer consists of turning the power on and starting the execution of an initial
program. Thus, when power is turned on, the hardware of the computer sets the program counter
to the first address of the bootstrap loader. The bootstrap program loads a portion of the operating
system from disk to main memory and control is then transferred to the operating system, which
prepares the computer for general use

4
G SRUJAN REDDY MEMORY ORGANIZATION
 COMPUTER ORGANIZATION AND ARCHITECTURE

RAM and ROM Chips

RAM:

 RAM is Random Access Memory i.e. user can read or write into RAM which makes the data bus
bidirectional
 A bidirectional buffer is constructed using a tri-state buffer. The three states are 1, 0, Z.
 Logic-1 and logic-0 are normal digital signals
 Logic-Z is high-impedance which makes the bus an open circuit.
 Block diagram of RAM chip of capacity 128 words, each word is byte(8-bits) length is as shown
below

 A 128 x 8 RAM configuration, the specifications indicate the following:

i. Memory Size: The RAM has 128 memory locations (or addresses).
ii. Data Width: Each memory location can hold 8 bits of data.
iii. Address-bits = 7 bits
 Read and Write inputs are memory operations
 Two chip select (CS) inputs are used to enable RAM.
 The Chip selection, Read, and Write operation is as follows
 CS=0 and CS’ =0  None of the chips is selected, we can’t perform read or write
operations. The data bus is at a high impedance
 CS=0 and CS’ =1  None of the chips is selected, we can’t perform read or write
operations. The data bus is at a high impedance
 CS=1 and CS’ =0  One of the chips is selected, if WR=0 and RD=0 the data bus is at
a high impedance
 CS=1 and CS’ =0  One of the chips is selected, if WR=1 and RD=0 the data is written
into the RAM through data bus
 CS=1 and CS’ =0  One of the chips is selected, if WR=0 and RD=1 the data is read
from the RAM through the data bus.

5
G SRUJAN REDDY MEMORY ORGANIZATION
 COMPUTER ORGANIZATION AND ARCHITECTURE

 CS=1 and CS’ =1 None of the chips is selected, we can’t perform read or write
operations. The data bus is at a high impedance

6
G SRUJAN REDDY MEMORY ORGANIZATION
 COMPUTER ORGANIZATION AND ARCHITECTURE

Block diagram of ROM chip of capacity 512 words, each word is byte(8-bits) length is as shown below

 A 512 x 8 ROM configuration, the specifications indicate the following:

i. Memory Size: The RAM has 512 memory locations (or addresses).
ii. Data Width: Each memory location can hold 8 bits of data.
iii. Address- bits = 9
iv. Data-bits = 8
 ROM is used for read-only.
 It has a unidirectional data bus and only read signal
 Let us evaluate how the memory connections are made with an example below

Calculate the number of 128x8 RAM chips and 512x8 ROM chips required to design a computer system that
needs 512 bytes of RAM and 512 bytes of ROM. Also, give the memory address map.

 CPU addresses with 16-bit addresses. (A1-A16)

 The capacity of RAM is 128 words and each word is 1 byte i.e. 128 x8
 Each word in RAM can be accessed using a 7-bit address bus (128 = 27) designated as A1 – A7
 The data bus carries 8 bits of data.
 To achieve 512 bytes of RAM, we require 4 such 128 x 8 RAMS. Let individual RAMs be designated as
RAM#1, RAM#2, RAM#3, and RAM#4. Based on the need, one of the four RAMs is to be selected using
chip-select inputs
 The capacity of ROM is 512 words and each word is 1 byte i.e. 512 x8
 Each word in ROM can be accessed using a 9-bit address bus (512 = 28) designated as A1 – A9
 The data bus carries 8 bits of data.
 The total memory devices are 4 RAMs and 1 ROM. We need a special circuitry to select between one of
the RAM and ROM.
 The RD and WR pins from the CPU are connected RD and WR pins of RAMs and ROM
 The Data Bus from the CPU is connected to the Data pins of RAMs and ROM
 Considering the starting address as 0000H. let us find the address locations of RAM and ROM

7
G SRUJAN REDDY MEMORY ORGANIZATION
 COMPUTER ORGANIZATION AND ARCHITECTURE

Address Bus
Componen Starting Address Ending Address 10 9 8 7 6 5 4 3 2 1
t
RAM#1 0000H 007FH 0 0 0 x x x x x X x
RAM#2 0080H 00FFH 0 0 1 x x x x x X x
RAM#3 0100H 017FH 0 1 0 x x x x x X x
RAM#4 0180H 01FFH 0 1 1 x x x x x X x
ROM 0200H 03FFH 1 x x x x x x x X x

By observation, the bit-10 is 0 for RAM and 1 for ROM. Connect the bit-10 to the CS’ pin of RAM and ROM.
By observation, the bit-9 and bit-8 are as follows
When 00  RAM#1 is selected
When 01  RAM#2 is selected
When 10  RAM#3 is selected
When 11  RAM#4 is selected
Thus bits 9 & 8 are connected to a 2 x 4 decoder. The 4 outputs of the decoder are connected to the CS
pin of each RAM. The entire address mapping is as shown in the figure below.

8
G SRUJAN REDDY MEMORY ORGANIZATION
 COMPUTER ORGANIZATION AND ARCHITECTURE

III. AUXILIARY MEMORY

 The most commonly used Auxiliary Memories are Magnetic Tapes and Magnetic Discs.
 The physical properties of auxiliary devices are complex.
 The most important characteristics of any device are access mode, transfer rate, access time,
capacity, and cost.
 Access Time is the average time required to reach a storage location in memory and obtain its
contents.

9
G SRUJAN REDDY MEMORY ORGANIZATION
 COMPUTER ORGANIZATION AND ARCHITECTURE

IV. ASSOCIATE MEMORY

 An assembler program searches the Symbol address table in order to extract the symbol's binary
equivalent just like a bank account number may be searched in a file to determine the holder's name
and account status. The established way to search a table is to store all items where they can be
addressed in sequence.
 The search procedure is a strategy for choosing a sequence of addresses, reading the content of
memory at 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 than by an address. A memory unit
accessed by content is called an associative memory or content addressable memory (CAM)
 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. The
memory locates all words which match the specified content and marks them for reading.
 An associative memory is more expensive than a random access memory because each cell must have
storage capability as well as logic circuits for matching its content with an external argument
 Associative memories are used in applications where the search time is very critical and must be very
short.

Hardware Organization of Associative Memory:

The hardware representation of Associative Memory is shown below.

 It consists of Memory Array, a logic for m-words of n-bits per word.

 Three registers Argument Register, Key Register, Match Register are used for specific purposes.
 Argument Register A and the Key Register K each have n-bits, one for each bit of word.
 The Match Register M have m-bits, one for each memory word.

10
G SRUJAN REDDY MEMORY ORGANIZATION
 COMPUTER ORGANIZATION AND ARCHITECTURE

 The operation is as follows:

 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
 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 piece of information which specifies how the
reference to memory is made
 Consider an example shown below

A = 101 111100

K = 111 000000

Word1 = 100 111100 no match

Word2 = 101 000001 match

 The content of K is equal to 1 only at the left most 3-bits. Only those corresponding bits of A is
compared with Word1, this results in no-match. Similarly, the corresponding bits of A is compared
with Word2 and there is a match.
 The associative memory array, and the other registers are organized as shown below:
 Cells in array are marked as C with subscripts, one subscripts give the bit position and the other
gives the word number.
 Let the total bits in each of m words be n.

11
G SRUJAN REDDY MEMORY ORGANIZATION
 COMPUTER ORGANIZATION AND ARCHITECTURE

C1n = is the cell for bit-n in word 1

Cmj = is the cell for bit-j in word m
 Let Aj and Kj represents bits in Argument Register and Key Register. Where j=1,2,3, . . . , n

 A bit Aj in the argument register is compared with all the bits in column j of the array provided
that Kj = 1 . This is done for all columns j = 1,2, ... , n.
 If a match occurs between all the unmasked bits of the argument and the bits in word i , the
corresponding bit Mi in the match register is set to 1.
 If one or more unmasked bits of the argument and the word do not match, Mi is cleared to 0.
 The internal organization of the one cell Cij is shown below.
 It consists of a flip-flop storage element Fij and the circuits for reading, writing, and matching the
cell. The input bit is transferred into the storage cell during a write operation. The bit stored is
read out during a read operation.
 The match logic compares the content of the storage cell with the corresponding unmasked bit of
the argument and provides an output for the decision logic that sets the bit in Mi

12
G SRUJAN REDDY MEMORY ORGANIZATION
 COMPUTER ORGANIZATION AND ARCHITECTURE

V. CACHE MEMORY:

 When a program loop is executed, the CPU repeatedly refers to the set of instructions in memory
that constitute the loop. Every time a given subroutine is called, its set of instructions are fetched
from memory.
 Thus, loops and subroutines tend to localize the references to memory for fetching instructions
 If the active portions of the program and data are placed in a fast small memory, the average
memory access time can be reduced, thus reducing the total execution time of the program. Such a
fast small memory is referred to as a cache memory
 It is placed between the CPU and main memory as illustrated in the figure below. The cache
memory access time is less than the access time of the main memory by a factor of 5 to 10. The
cache is the fastest component in the memory hierarchy and approaches the speed of CPU
components.
 The fundamental idea of cache organization is that by keeping the most frequently accessed
instructions and data in the fast cache memory, the average memory access time will approach the
access time of the cache.
 The basic operation of CACHE is as follows:
 When the CPU needs to access memory, it first checks the cache.
 If the word of data is found in the cache, the word is read by cache
 If the word of data is not found in the cache, the main memory is checked and the word is read.
 A block of words that are read frequently is then transferred from main memory to cache
memory. Thus, enabling the CPU to find the frequently used word of data in cache memory
 Hit-Ratio: The performance of the cache memory is calculated based on the hit-ratio. When the
CPU refers to memory and finds the word of data in the cache, then it is a hit. If the word of data is

13
G SRUJAN REDDY MEMORY ORGANIZATION
 COMPUTER ORGANIZATION AND ARCHITECTURE

nor found in cache, then it is a miss. The ratio of the number of hits to the total number of memory
references is called as HIT-RATIO
 If the hit ratio is high enough so that most of the time the CPU accesses the cache memory instead
of the main memory, we can say that the access time is close to the fast cache memory.
 The basic characteristic of cache memory is its fast access.
 The transformation of data from the main memory to the cache memory is referred to as
the mapping process.
 There are three types mapping procedures.
i. Associative mapping
ii. Direct Mapping
iii. Set-Associative Mapping
 Consider a memory organization shown in the figure below.

 The main memory has a capacity of 32K x 12. i.e. 32K words of 12-bits each. [ 32K = 215, hence
15-bit address]
 Cache memory can store up to 512 words of 12 bits each. [512 = 29, hence 9-bit address]
 For every word stored in the cache, there is a duplicate copy of the main memory.
 When the CPU requires access to memory, it first sends the 15-bit address to cache. If it is a hit,
then 12-bit data from the cache is accepted. If it’s a miss, then the CPU receives 12-bit data from
the main memory.

i. Associative Mapping:

The fastest cache organization uses associative memory. This cache organization is illustrated as shown
in figure below.
 The associative memory stores both the address and the data of the memory word. This allows
any location in cache to store any word from main memory.
 The 15-bit address is in octal representation.
 The CPU address is places in the argument register and the associative memory searches for the
address. If the address is found, the corresponding 12 bit data is is read by CPU. If no match,
then the main memory is accessed.

14
G SRUJAN REDDY MEMORY ORGANIZATION
 COMPUTER ORGANIZATION AND ARCHITECTURE

 The matched address and data will be transferred to associative cache memory
 If the cache is full, then sufficient adjustment for address-data pair has to be made by replacing
them in place of old data present in cache.
 The address-data pair replacement is decided by the replacement algorithm. The best used is a
FIFO algorithm.
ii. Direct Mapping:
 The CPU 15-bit address is divided into two fields. The 9 least significant bits are named index
fields, and the remaining bits are named tag fields.
 The main memory is 32K x 12 and hence requires both the index and tag fields.
 The cache memory is 512 x 12 and requires a 9-bit address.
 By comparison, the main memory requires only the index field but not the tag field.
 In general, if there are 2k words in the main memory and 2n words in cache memory, then there
will be n-bit index field and n-k bits of tag field. The direct mapping cache organization uses
an n-bit address to access the main memory and a k-bit address to access cache memory.

 The internal organization of cache memory is as shown in fig(b).

 Each word in cache consists of data word and the tag associated with it.

15
G SRUJAN REDDY MEMORY ORGANIZATION
 COMPUTER ORGANIZATION AND ARCHITECTURE

 When the new word is brought into the cache, the tag bits are stored alongside the data
bits.
 When the CPU needs the memory access, the index field is used for the address to access
the cache.
 The tag field of CPU address is compared with the tag field of the word read from cache. If
they match, there is a hit and the desired data word is in the cache. If they don’t match,
there is a miss and the desired data word is read from the main memory. This data word is
then stored in the cache along with the tag replacing the previous values.
 The main disadvantage of direct mapping is drop in hit-ratio when two or more wors has the
same index fields but different tag field are accessed repeatedly.
 The operation of direct mapping is described below.

 The word at the address 0 is stored in the cache. The index field = 000, tag field = 00, and data
word = 1220.
 If the CPU accesses the word at 02000 with index address 000 and tag field 02.
 Since the index field is 000, it accesses the cache memory. It now compares the tags, the cache
tag is 00 but the address tag is 02 and there is no match. Therefore, the CPU's main memory is
accessed and the data word 5670 is read by the CPU.
 The cache word at index field 000 is then replaced with a tag of 02 and a data word of 5670
 The above example shows the block size of 1 word.
 The direct mapping for a block size of 8 words is shown below.

16
G SRUJAN REDDY MEMORY ORGANIZATION
 COMPUTER ORGANIZATION AND ARCHITECTURE

 Each block consists of 8 words.

 The index field is divided into 2 parts: block field and word field.
 In 512-word cache there are 64 blocks of 8 words each as shown above.
 The block number is identified by a 6-bit field whereas the word within the block is identified by
a 3-bit field.
 The tag field stored within the block is the same for all the words.
 Every time a miss occurs, the entire block of words will be transferred from the main memory to
the cache memory.

iii. Set-Associative Mapping

 The disadvantage of direct Mapping is that the two words with the same index in their address
but with different tag values can't reside in the cache memory at the same time.
 In this set-associative mapping, each word of cache can store two or more words of memory
under the same index number
 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.
 The set-associative memory is shown with an example below.

17
G SRUJAN REDDY MEMORY ORGANIZATION
 COMPUTER ORGANIZATION AND ARCHITECTURE

 Each index address refers to two data words and their associated tags.
 Each tag requires 6 bits and each data requires 12 bits. Thus the word length is 2(6+12) = 36 bits.
 The index is of 9 bits and can accommodate 29 = 512 words.
 This makes the size of cache memory 512 x 36 bits.
 In general, a set-associative cache of set size k will accommodate k words of main memory in
each word of cache.

18
G SRUJAN REDDY MEMORY ORGANIZATION
 COMPUTER ORGANIZATION AND ARCHITECTURE

Writing into Cache:

 When the CPU finds a word in the cache during a read operation, the main memory is not
involved in the transfer. However, if the operation is a write, there are two ways that the system
can proceed.
 write-through method: This is the simplest and the most common way is to update main
memory with every memory write operation, with cache memory with cache memory being
updated in parallel if it contains the word at specified address. This is called write-through
method. This method has the advantage that main memory always contains the same data as
the cache memory. This behaviour is useful in the systems that employ Direct Memory Access
(DMA). It ensures the data available at main memory are valid at all times so that I/O device
communicating through DMA would receive the most recently updated data.
 Write-back method: in this method, only the cache is updated during write operation. This
location is marked as flag, and later when the word is removed from cache it is copied to main
memory. As long as the data resides in the cache and is being updated several times, the same
data need not be present in main memory. But, when this data is removed from cache, it
becomes necessary that a duplicate copy be moved to main memory.

19
G SRUJAN REDDY MEMORY ORGANIZATION