Mapping Techniques Introduction (Theory 1)

Mapping Function:-

Because there are fewer cache lines than main memory blocks, an algorithm is
needed for mapping main memory blocks into cache lines. Further, a means is
needed for determining which main memory block currently occupies a cache line.
The choice of the mapping function dictates how the cache is organized. Three techniques can be used: direct, associative, and set associative.


1. Direct Mapping:-

The simplest technique, known as direct mapping, maps each block of main memory into only one possible cache line.

The mapping is expressed as

                                           i= j mod n  where

                                           i = line no. to which main memory block is mapped

                                           j= main memory block which is to be mapped.

                                           n= no of lines in the cache.

The direct mapping technique is simple and inexpensive to implement.


Its main disadvantage is that there is a fixed cache location for any given block. Thus, if a program happens to reference words repeatedly from two different blocks that map into the same line, then the blocks will be continually swapped in the cache, and the hit ratio will be low (a phenomenon known as thrashing).


2. Associate Mapping:

Associative mapping overcomes the disadvantage of direct mapping by permitting each main memory block to be loaded into any line of the cache. In this case, the cache control logic interprets a memory address simply as a Tag and a Word field.

The Tag field uniquely identifies a block of main memory. To determine whether a block is in the cache, the cache control logic must simultaneously examine every line’s tag for a match.

Note that no field in the address corresponds to the line number so that the
the number of lines in the cache is not determined by the address format.


The principal disadvantage of associative mapping is the complex circuitry required to examine the tags of all cache lines in parallel.


3.Set-Associative Mapping:-

Set-associative mapping is a compromise that exhibits the strengths of both the direct and associative approaches while reducing their disadvantages.
In this case, the cache contains sets instead of lines, unlike direct mapping.

  • Basically, it is represented as K way set associate where K represents how many cache lines are present in a set.
  • Each direct mapping can be seen as a 1-way set associate.

       The mapping function is given as i= j mod v  where

                                                            i = line no. to which main memory block is mapped

                                                           j= main memory block which is to be mapped.

                                                           v= no of sets in the cache.

 No. of sets = total no. of lines in cache / K








In order to achieve complete understandings of computer systems, it is always important to consider both hardware and software design of various computer components. In other words, every functionality of the computer has to be studied to increase the performance of the computer.

Computer organization and architecture mainly focuses on various parts of the computer in order to reduce the execution time of the program, improve the performance of each part. Generally, we tend to think computer organization and computer architecture as same but there is slight difference.


  • Computer Organization is study of the system from software point of view and gives overall description of the system and working principles without going into much detail. In other words, it is mainly about the programmer’s or user point of view.
  • Computer Architecture is study of the system from hardware point of view and emphasis on how the system is implemented. Basically, throws light on the designer’s point of view.


  1. A chef prepares a certain recipe, then serves it to the customers. Chef knows how to prepare the food item whereas customer cares only about quality and taste of the food. In a same way, “chef” can referred to as computer architecture and “customeras computer organization.
  2. In a system, there are a set of instructions, it is enough for programmer or user to know what are a set of instructions present in case of computer organization; whereas it is important for the system designer worries about how a set of instructions are implemented, algorithm of implementation is the emphasis in the case of architectural studies.



A computer consists of various functional blocks- Input, Output, Memory, arithmetic and logical unit, control units.

INPUT UNITS: Various input devices like keyboard etc, provide input to computer; whenever a key is pressed, the letter or key gets automatically translated to binary codes and then transmitted to either memory or processor. The information is stored in memory for further use


MEMORY UNITS: The main function of memory unit is to store data and programs. The programs must be stored in the device while execution. Inside the system, memory plays a vital role in execution of   set of instructions. Memory can be further classified into:


PRIMARY MEMORY: The data or set of instructions are stored in primary storage before processing and the data is transferred to ALU where further processing is done. These are expensive and also known as Main Memory.

SECONDARY MEMORY: The data or set of instruction are stored permanently; user can use it whenever required in future. They are cheaper than primary memory.

ARITHMETIC LOGIC UNIT (ALU): Any arithmetic or logical operation like addition, multiplication etc has to be carried out by ALU. For instance, two numbers located in the memory are to be multiplied; from memory they have to be transferred to processor where ALU performs the arithmetic operation required. Then product will remain in the processor incase of immediate use, otherwise stored in the memory.

CONTROL UNIT (CU): All the other functional units as in ALU, I/O devices, memory has to be coordinated in some ways. Data transfers between the processor and the memory are controlled by this particular unit through timing signals. Timing signals are the signals to determine which action to take place and when.

OUTPUT UNIT: It provides processed results received from the operations performed. Devices like printers, monitor etc provides the desired output.


  • Input device provides information in the form of program to the computer and stores it in the memory.
  • Further the information is fetched from memory to the processer.

  • Inside the processor, it is processed by the ALU.

  • The processed output further passes to output devices.

  • All these activities are controlled by control unit.

 The most efficient computer depends on how quickly it executes tasks. The performance highly depends on few factors:

  • As the programs are written in high level language, compiler transfers the high level language to machine level language; so the performance is highly affected.
  • The speed of the computer depends on the hardware design and machine instruction sets.

Therefore, for optimum results it is important to design compiler, hardware and machine instruction sets in a coordinated way.

The hardware comprises of processor and memory usually connected by a bus. The execution of the program depends on computer system, the processor time depends on hardware. Cache memory is a part of the processor.


The flow of program instructions and data between processor and memory:

  • All the program and data are fetched from input device, and then stored in main memory.
  • Instructions are fetched one by one over bus from memory into processor and a copy is placed in cache memory for future use whenever required.

  • The processor and small cache memory is fabricated in a small integrated circuit chip which makes the processing speed very high.

  • If the instruction movement between main memory and processor is minimized, program will be executed faster which is achieved by cache memory.


Logical circuits are used to build computer that operates on two valued electric signals which are 0 and 1.  A bit of information is the amount of information received from these electric signals.

  • To represent a number in a computer system by string of bits is called binary number.

  • To represents a text character by string of bits is called character code. Characters can be alphabets, decimal digits, punctuation marks and so on which are represented by 8 bits long codes.

As we need to represent all types of positive and negative numbers which can be represented in three ways where leftmost bit is 0 for positive numbers and 1 for negative numbers:

  1. Sign and magnitude
  2. 1’s complement
  3. 2’s complement

Positive values have identical representation in all the three system whereas negative values have different representations.

  1. In Sign and magnitude representation:

Negative values are represented by changing the most significant bit from 0 to 1. It is most natural and can be manually computed.

Example: +5= 0101 whereas -5=1101 (Most significant bit changed from 0 to 1)

  1. 1’s complement representation:

We get negative number by complementing each bit of the corresponding positive number

Example: +3=0011 whereas 3=1100

  1. 2’s complement representations:

2’s complement is obtained by adding 1 to 1’s complement of that number.


2’s complement has only one representation of 0 whereas for +0 and -0, there are distinct representation for sign and magnitude and 1’s complement. However, 2’s complement is most efficient in carrying out addition and subtraction operations.



  1. Computer Organization by Carl Hamacher and Zaky 5th edition.
  2. IITM- NPTEL lectures by S Raman.
  3. IIT-KGP NPTEL digital computer design by P.K Biswas.


Difference between control memory and control register

Control memory address register specifies the address of the micro-instruction, and the control data register holds the micro-instruction read from memory, The micro-instruction contains a control word that specifies one or more micro operations for the data processor. Once these operations are executed, the control must determine the next address. The location of the next micro-instruction may be the one next in sequence, or it may be located somewhere else in the control memory. for this reason it is necessary to use some bits of the present micro-instruction to control the generation of the address of the next micro-instruction. The next address may also be a function of the external input condition.