18EC35 COMPUTER ORGANIZATION| MODULE 3: INPUT/OUTPUT ORGANIZATION

MODULE 4: MEMORY SYSTEM

4.1 BASIC CONCEPTS

• Maximum size of memory that can be used in any computer is determined by addressing mode.

• If MAR is k-bits long then

→ memory may contain upto 2K addressable-locations

• If MDR is n-bits long, then
→ n-bits of data are transferred between the memory and processor.
• The data-transfer takes place over the processor-bus (Figure 8.1).
• The processor-bus has
1) Address-Line
2) Data-line &
3) Control-Line (R/W‟, MFC – Memory Function Completed).
• The Control-Line is used for coordinating data-transfer.
• The processor reads the data from the memory by
→ loading the address of the required memory-location into MAR and
→ setting the R/W‟ line to 1.
• The memory responds by
→ placing the data from the addressed-location onto the data-lines and
→ confirms this action by asserting MFC signal.
• Upon receipt of MFC signal, the processor loads the data from the data-lines into MDR.
• The processor writes the data into the memory-location by
→ loading the address of this location into MAR &
→ setting the R/W‟ line to 0.

COMPUTER ORGANIZATION | DEPT. OF ELECTRONICS & COMMUNICATION ENGG.

72
 COMPUTER ORGANIZATION|MODULE 4: MEMORY SYSTEM 18EC35

• Memory Access Time: It is the time that elapses between

→ initiation of an operation &
→ completion of that operation.
• Memory Cycle Time: It is the minimum time delay that required between the initiation of the two
successive memory-operations.

RAM (Random Access Memory)

• In RAM, any location can be accessed for a Read/Write-operation in fixed amount of time,
Cache Memory
 It is a small, fast memory that is inserted between
→ larger slower main-memory and
→ processor.
 It holds the currently active segments of a program and their data.
Virtual Memory
 The address generated by the processor is referred to as a virtual/logical address.
 The virtual-address-space is mapped onto the physical-memory where data are actually
stored.
 The mapping-function is implemented by MMU. (MMU = memory management unit).
 Only the active portion of the address-space is mapped into locations in the physical-memory.
 The remaining virtual-addresses are mapped onto the bulk storage devices such as magnetic
disk.
 As the active portion of the virtual-address-space changes during program execution, the
MMU
→ changes the mapping-function &
→ transfers the data between disk and memory.
 During every memory-cycle, MMU determines whether the addressed-page is in the memory.
If the page is in the memory.
Then, the proper word is accessed and execution proceeds.
Otherwise, a page containing desired word is transferred from disk to memory.
• Memory can be classified as follows:
1) RAM which can be further classified as follows:
i) Static RAM
ii) Dynamic RAM (DRAM) which can be further classified as synchronous & asynchronous
DRAM.
2) ROM which can be further classified as follows:
i) PROM
ii) EPROM
iii) EEPROM &
iv) Flash Memory which can be further classified as Flash Cards & Flash Drives.

4.2 SEMI CONDUCTOR RAM MEMORIES

4.2.1 INTERNAL ORGANIZATION OF MEMORY-CHIPS

• Memory-cells are organized in the form of array (Figure 8.2).

• Each cell is capable of storing 1-bit of information.
• Each row of cells forms a memory-word.
• All cells of a row are connected to a common line called as Word-Line.
• The cells in each column are connected to Sense/Write circuit by 2-bit-lines.
• The Sense/Write circuits are connected to data-input or output lines of the chip.
• During a write-operation, the sense/write circuit
→ receive input information &
→ store input info in the cells of the selected word.
COMPUTER ORGANIZATION | DEPT. OF ELECTRONICS & COMMUNICATION ENGG. 73
 18EC35 COMPUTER ORGANIZATION| MODULE 3: INPUT/OUTPUT ORGANIZATION

• The data-input and data-output of each Sense/Write circuit are connected to a single bidirectional
data-line.
• Data-line can be connected to a data-bus of the computer.
• Following 2 control lines are also used:
1) R/W’  Specifies the required operation.
2) CS’  Chip Select input selects a given chip in the multi-chip memory-system.

COMPUTER ORGANIZATION | DEPT. OF ELECTRONICS & COMMUNICATION ENGG.

74
 COMPUTER ORGANIZATION|MODULE 4: MEMORY SYSTEM 18EC35

4.2.2 STATIC RAM (OR MEMORY)

• Memories consist of circuits capable of retaining their state as long as power is applied are known.

• Two inverters are cross connected to form a latch (Figure 8.4).

• The latch is connected to 2-bit-lines by transistors T1 and T2.
• The transistors act as switches that can be opened/closed under the control of the word-line.
• When the word-line is at ground level, the transistors are turned off and the latch retain its state.
Read Operation
• To read the state of the cell, the word-line is activated to close switches T1 and T2.
• If the cell is in state 1, the signal on bit-line b is high and the signal on the bit-line b‟ is low.
• Thus, b and b‟ are complement of each other.
• Sense/Write circuit
→ monitors the state of b & b‟ and
→ sets the output accordingly.
Write Operation
• The state of the cell is set by
→ placing the appropriate value on bit-line b and its complement on b‟ and
→ then activating the word-line. This forces the cell into the corresponding state.
• The required signal on the bit-lines is generated by Sense/Write circuit.

CMOS Cell
• Transistor pairs (T3, T5) and (T4, T6) form the inverters in the latch (Figure 8.5).
• In state 1, the voltage at point X is high by having T5, T6 ON and T4, T5 are OFF.

COMPUTER ORGANIZATION | DEPT. OF ELECTRONICS & COMMUNICATION ENGG. 75

 18EC35 COMPUTER ORGANIZATION| MODULE 3: INPUT/OUTPUT ORGANIZATION

• Thus, T1 and T2 returned ON (Closed), bit-line b and b‟ will have high and low signals respectively.
• Advantages:
1) It has low power consumption „.‟ the current flows in the cell only when the cell is active.
2) Static RAM‟s can be accessed quickly. It access time is few nanoseconds.
• Disadvantage: SRAMs are said to be volatile memories „.‟ their contents are lost when power
is interrupted.

4.2.3 ASYNCHRONOUS DRAM

• Less expensive RAMs can be implemented if simple cells are used.
• Such cells cannot retain their state indefinitely. Hence they are
called Dynamic RAM (DRAM).
• The information stored in a dynamic memory-cell in the form of a
charge on a capacitor.
• This charge can be maintained only for tens of milliseconds.
• The contents must be periodically refreshed by restoring this capacitor
charge to its full value.

• In order to store information in the cell, the transistor T is turned „ON‟

(Figure 8.6).
• The appropriate voltage is applied to the bit-line which charges the capacitor.
• After the transistor is turned off, the capacitor begins to discharge.
• Hence, info. stored in cell can be retrieved correctly before threshold value of
capacitor drops down.
• During a read-operation,
→ transistor is turned „ON‟
→ a sense amplifier detects whether the charge on the capacitor is above the
threshold value.
 If (charge on capacitor) > (threshold value)  Bit-line will have logic value „1‟.
 If (charge on capacitor) < (threshold value)  Bit-line will set to logic value „0‟.

ASYNCHRONOUS DRAM DESCRIPTION

• The 4 bit cells in each row are divided into 512 groups of 8 (Figure 5.7).
• 21 bit address is needed to access a byte in the memory. 21 bit is divided as
follows:
1) 12 address bits are needed to select a row.

COMPUTER ORGANIZATION | DEPT. OF ELECTRONICS & COMMUNICATION ENGG.

76
 COMPUTER ORGANIZATION|MODULE 4: MEMORY SYSTEM 18EC35

i.e. A8-0 → specifies row-address of a byte.

2) 9 bits are needed to specify a group of 8 bits in the selected row.
i.e. A20-9 → specifies column-address of a byte.

• During Read/Write-operation,
→ row-address is applied first.
→ row-address is loaded into row-latch in response to a signal pulse on RAS’ input of chip.
(RAS = Row-address Strobe CAS = Column-address Strobe)
• When a Read-operation is initiated, all cells on the selected row are read and
refreshed.
• Shortly after the row-address is loaded, the column-address is
→ applied to the address pins &
→ loaded into CAS’.

• The information in the latch is decoded.

• The appropriate group of 8 Sense/Write circuits is selected.
R/W’=1(read-operation)  Output values of selected circuits are transferred to
data-lines D0-D7.
R/W’=0(write-operation)  Information on D0-D7 are transferred to the selected
circuits.
• RAS‟ & CAS‟ are active-low so that they cause latching of address when they
change from high to low.
• To ensure that the contents of DRAMs are maintained, each row of cells is accessed
periodically.
• A special memory-circuit provides the necessary control signals RAS‟ & CAS‟ that
govern the timing.
• The processor must take into account the delay in the response of the memory.
Fast Page Mode
 Transferring the bytes in sequential order is achieved by applying the consecutive sequence
of column-address under the control of successive CAS‟ signals.
 This scheme allows transferring a block of data at a faster rate.
 The block of transfer capability is called as fast page mode.

COMPUTER ORGANIZATION | DEPT. OF ELECTRONICS & COMMUNICATION ENGG. 77

 18EC35 COMPUTER ORGANIZATION| MODULE 3: INPUT/OUTPUT ORGANIZATION

SYNCHRONOUS DRAM
• The operations are directly synchronized with clock signal (Figure 8.8).
• The address and data connections are buffered by means of registers.
• The output of each sense amplifier is connected to a latch.
• A Read-operation causes the contents of all cells in the selected row to be loaded in these latches.
• Data held in latches that correspond to selected columns are transferred into data-output register.
• Thus, data becoming available on the data- output pins.

• First, the row-address is latched under control of RAS‟ signal (Figure 8.9).
• The memory typically takes 2 or 3 clock cycles to activate the selected row.
• Then, the column-address is latched under the control of CAS‟ signal.
• After a delay of one clock cycle, the first set of data bits is placed on the data-lines.
• SDRAM automatically increments column-address to access next 3 sets of bits in the selected row.

COMPUTER ORGANIZATION | DEPT. OF ELECTRONICS & COMMUNICATION ENGG.

78
 COMPUTER ORGANIZATION|MODULE 4: MEMORY SYSTEM 18EC35

LATENCY & BANDWIDTH

• A good indication of performance is given by 2 parameters: 1) Latency 2) Bandwidth.
Latency
• It refers to the amount of time it takes to transfer a word of data to or from the memory.
• For a transfer of single word, the latency provides the complete indication of memory performance.
• For a block transfer, the latency denotes the time it takes to transfer the first word of data.
Bandwidth
• It is defined as the number of bits or bytes that can be transferred in one second.
• Bandwidth mainly depends on
1) The speed of access to the stored data &
2) The number of bits that can be accessed in parallel.

DOUBLE DATA RATE SDRAM (DDR-SDRAM)

• The standard SDRAM performs all actions on the rising edge of the clock signal.
• The DDR-SDRAM transfer data on both the edges (loading edge, trailing edge).
• The Bandwidth of DDR-SDRAM is doubled for long burst transfer.
• To make it possible to access the data at high rate, the cell array is organized into two banks.
• Each bank can be accessed separately.
• Consecutive words of a given block are stored in different banks.
• Such interleaving of words allows simultaneous access to two words.
• The two words are transferred on successive edge of the clock.

STRUCTURE OF LARGER MEMORIES

Dynamic Memory System

• The physical implementation is done in the form of memory-modules.

• If a large memory is built by placing DRAM chips directly on the Motherboard,
then it will occupy large amount of space on the board.
• These packaging consideration have led to the development of larger memory units known as SIMM‟s
& DIMM‟s.
1) SIMM  Single Inline memory-module
2) DIMM  Dual Inline memory-module
• SIMM/DIMM consists of many memory-chips on small board that plugs into a socket on motherboard.

MEMORY-SYSTEM CONSIDERATION
MEMORY CONTROLLER
• To reduce the number of pins, the dynamic memory-chips use multiplexed-address inputs.
• The address is divided into 2 parts:
1) High Order Address Bit
 Select a row in cell array.
 It is provided first and latched into memory-chips under the control of RAS‟ signal.
2) Low Order Address Bit
 Selects a column.
 They are provided on same address pins and latched using CAS‟ signals.

COMPUTER ORGANIZATION | DEPT. OF ELECTRONICS & COMMUNICATION ENGG. 79

 18EC35 COMPUTER ORGANIZATION| MODULE 3: INPUT/OUTPUT ORGANIZATION

• The Multiplexing of address bit is usually done by Memory Controller Circuit (Figure 5.11).
• The Controller accepts a complete address & R/W‟ signal from the processor.
• A Request signal indicates a memory access operation is needed.
• Then, the Controller
→ forwards the row & column portions of the address to the memory.
→ generates RAS‟ & CAS‟ signals &
→ sends R/W‟ & CS‟ signals to the memory.

RAMBUS MEMORY
• The usage of wide bus is expensive.
• Rambus developed the implementation of narrow bus.
• Rambus technology is a fast signaling method used to transfer information between chips.
• The signals consist of much smaller voltage swings around a reference voltage Vref.
• The reference voltage is about 2V.
• The two logical values are represented by 0.3V swings above and below Vref.
• This type of signaling is generally is known as Differential Signalling.
• Rambus provides a complete specification for design of communication called as Rambus Channel.
• Rambus memory has a clock frequency of 400 MHz.
• The data are transmitted on both the edges of clock so that effective data-transfer rate is 800MHZ.
• Circuitry needed to interface to Rambus channel is included on chip. Such chips are called RDRAM.
(RDRAM = Rambus DRAMs).
• Rambus channel has:
1) 9 Data-lines (1st-8th line ->Transfer the data, 9th line->Parity checking).
2) Control-Line &
3) Power line.
• A two channel rambus has 18 data-lines which has no separate Address-Lines.
• Communication between processor and RDRAM modules is carried out by means of packets
transmitted on the data-lines.
• There are 3 types of packets:
1) Request
2) Acknowledge &
3) Data.

COMPUTER ORGANIZATION | DEPT. OF ELECTRONICS & COMMUNICATION ENGG.

80
 COMPUTER ORGANIZATION|MODULE 4: MEMORY SYSTEM 18EC35

4.3 READ ONLY MEMORY (ROM)

• Both SRAM and DRAM chips are volatile, i.e. They lose the stored information if power is turned off.
• Many application requires non-volatile memory which retains the stored information if power is
turned off.
• For ex:
OS software has to be loaded from disk to memory i.e. it requires non-volatile memory.
• Non-volatile memory is used in embedded system.
• Since the normal operation involves only reading of stored data, a memory of this type is called ROM.
 At Logic value ‘0’  Transistor(T) is connected to the ground point (P).
Transistor switch is closed & voltage on bit-line nearly drops to zero (Figure 8.11).
 At Logic value ‘1’  Transistor switch is open.
The bit-line remains at high voltage.

• To read the state of the cell, the word-line is activated.

• A Sense circuit at the end of the bit-line generates the proper output value.

TYPES OF ROM
• Different types of non-volatile memory are
1) PROM
2) EPROM
3) EEPROM &
4) Flash Memory (Flash Cards & Flash Drives)

PROM (PROGRAMMABLE ROM)

• PROM allows the data to be loaded by the user.
• Programmability is achieved by inserting a „fuse‟ at point P in a ROM cell.
• Before PROM is programmed, the memory contains all 0‟s.
• User can insert 1‟s at required location by burning-out fuse using high current-pulse.
• This process is irreversible.
• Advantages:
1) It provides flexibility.
2) It is faster.
3) It is less expensive because they can be programmed directly by the user.

COMPUTER ORGANIZATION | DEPT. OF ELECTRONICS & COMMUNICATION ENGG. 81

 18EC35 COMPUTER ORGANIZATION| MODULE 3: INPUT/OUTPUT ORGANIZATION

EPROM (ERASABLE REPROGRAMMABLE ROM)

• EPROM allows
→ stored data to be erased and
→ new data to be loaded.
• In cell, a connection to ground is always made at „P‟ and a special transistor is used.
• The transistor has the ability to function as
→ a normal transistor or
→ a disabled transistor that is always turned „off‟.
• Transistor can be programmed to behave as a permanently open switch, by injecting charge into it.
• Erasure requires dissipating the charges trapped in the transistor of memory-cells.
This can be done by exposing the chip to ultra-violet light.
• Advantages:
1) It provides flexibility during the development-phase of digital-system.
2) It is capable of retaining the stored information for a long time.
• Disadvantages:
1) The chip must be physically removed from the circuit for reprogramming.
2) The entire contents need to be erased by UV light.

EEPROM (ELECTRICALLY ERASABLE ROM)

• Advantages:
1) It can be both programmed and erased electrically.
2) It allows the erasing of all cell contents selectively.
• Disadvantage: It requires different voltage for erasing, writing and reading the stored data.

FLASH MEMORY
• In EEPROM, it is possible to read & write the contents of a single cell.
• In Flash device, it is possible to read contents of a single cell & write entire contents of a block.
• Prior to writing, the previous contents of the block are erased.
Eg. In MP3 player, the flash memory stores the data that represents sound.
• Single flash chips cannot provide sufficient storage capacity for embedded-system.
• Advantages:
1) Flash drives have greater density which leads to higher capacity & low cost per bit.
2) It requires single power supply voltage & consumes less power.
• There are 2 methods for implementing larger memory: 1) Flash Cards & 2) Flash Drives
1) Flash Cards
 One way of constructing larger module is to mount flash-chips on a small card.
 Such flash-card have standard interface.
 The card is simply plugged into a conveniently accessible slot.
 Memory-size of the card can be 8, 32 or 64MB.
 Eg: A minute of music can be stored in 1MB of memory. Hence 64MB flash cards can store an
hour of music.
2) Flash Drives
 Larger flash memory can be developed by replacing the hard disk-drive.
 The flash drives are designed to fully emulate the hard disk.
 The flash drives are solid state electronic devices that have no movable parts.
Advantages:
1) They have shorter seek & access time which results in faster response.
2) They have low power consumption. .‟. they are attractive for battery driven
application.
3) They are insensitive to vibration.
Disadvantages:
1) The capacity of flash drive (<1GB) is less than hard disk (>1GB).
2) It leads to higher cost per bit.
COMPUTER ORGANIZATION | DEPT. OF ELECTRONICS & COMMUNICATION ENGG.
82
 COMPUTER ORGANIZATION|MODULE 4: MEMORY SYSTEM 18EC35

3) Flash memory will weaken after it has been written a number of times (typically at
least 1 million times).
SPEED, SIZE COST

• The main-memory can be built with DRAM (Figure 8.14)

• Thus, SRAM‟s are used in smaller units where speed is of essence.
• The Cache-memory is of 2 types:
1) Primary/Processor Cache (Level1 or L1 cache)
 It is always located on the processor-chip.
2) Secondary Cache (Level2 or L2 cache)
 It is placed between the primary-cache and the rest of the memory.
• The memory is implemented using the dynamic components (SIMM, RIMM, DIMM).
• The access time for main-memory is about 10 times longer than the access time for L1 cache.

COMPUTER ORGANIZATION | DEPT. OF ELECTRONICS & COMMUNICATION ENGG. 83

 18EC35 COMPUTER ORGANIZATION| MODULE 3: INPUT/OUTPUT ORGANIZATION

4.4 CACHE MEMORIES

• The effectiveness of cache mechanism is based on the property of „Locality of Reference’.
Locality of Reference
• Many instructions in the localized areas of program are executed repeatedly during some time period
• Remainder of the program is accessed relatively infrequently (Figure 8.15).
• There are 2 types:
1) Temporal
 The recently executed instructions are likely to be executed again very soon.
2) Spatial
 Instructions in close proximity to recently executed instruction are also likely to be executed soon.
• If active segment of program is placed in cache-memory, then total execution time can be reduced.
• Block refers to the set of contiguous address locations of some size.
• The cache-line is used to refer to the cache-block.

• The Cache-memory stores a reasonable number of blocks at a given time.

• This number of blocks is small compared to the total number of blocks available in main-memory.
• Correspondence b/w main-memory-block & cache-memory-block is specified by mapping-function.
• Cache control hardware decides which block should be removed to create space for the new block.
• The collection of rule for making this decision is called the Replacement Algorithm.
• The cache control-circuit determines whether the requested-word currently exists in the cache.
• The write-operation is done in 2 ways: 1) Write-through protocol & 2) Write-back protocol.
Write-Through Protocol
 Here the cache-location and the main-memory-locations are updated simultaneously.
Write-Back Protocol
 This technique is to
→ update only the cache-location &
→ mark the cache-location with associated flag bit called Dirty/Modified Bit.

 The word in memory will be updated later, when the marked-block is removed from cache.
During Read-operation
• If the requested-word currently not exists in the cache, then read-miss will occur.
• To overcome the read miss, Load–through/Early restart protocol is used.
Load–Through Protocol
 The block of words that contains the requested-word is copied from the memory into cache.
 After entire block is loaded into cache, the requested-word is forwarded to processor.
During Write-operation
• If the requested-word not exists in the cache, then write-miss will occur.
1) If Write Through Protocol is used, the information is written directly into main-memory.
2) If Write Back Protocol is used,
→ then block containing the addressed word is first brought into the cache &
→ then the desired word in the cache is over-written with the new information.

MAPPING-FUNCTION
• Here we discuss about 3 different mapping-function:
1) Direct Mapping
COMPUTER ORGANIZATION | DEPT. OF ELECTRONICS & COMMUNICATION ENGG.
84
 COMPUTER ORGANIZATION|MODULE 4: MEMORY SYSTEM 18EC35

2) Associative Mapping
3) Set-Associative Mapping

DIRECT MAPPING
• The block-j of the main-memory maps onto block-j modulo-128 of the cache (Figure 8.16).
• When the memory-blocks 0, 128, & 256 are loaded into cache, the block is stored in cache-block 0.
Similarly, memory-blocks 1, 129, 257 are stored in cache-block 1.
• The contention may arise when
1) When the cache is full.
2) When more than one memory-block is mapped onto a given cache-block position.
• The contention is resolved by
allowing the new blocks to overwrite the currently resident-block.
• Memory-address determines placement of block in the cache.

• The memory-address is divided into 3 fields:

1) Low Order 4 bit field
 Selects one of 16 words in a block.
2) 7 bit cache-block field
 7-bits determine the cache-position in which new block must be stored.
3) 5 bit Tag field
 5-bits memory-address of block is stored in 5 tag-bits associated with cache-location.
• As execution proceeds,
5-bit tag field of memory-address is compared with tag-bits associated with cache-location.
COMPUTER ORGANIZATION | DEPT. OF ELECTRONICS & COMMUNICATION ENGG. 85
 18EC35 COMPUTER ORGANIZATION| MODULE 3: INPUT/OUTPUT ORGANIZATION

If they match, then the desired word is in that block of the cache.
Otherwise, the block containing required word must be first read from the memory.
And then the word must be loaded into the cache.

ASSOCIATIVE MAPPING
1) The memory-block can be placed into any cache-block position. (Figure 8.17).
2) 12 tag-bits will identify a memory-block when it is resolved in the cache.
3) Tag-bits of an address received from processor are compared to the tag-bits of each block of
cache.
4) This comparison is done to see if the desired block is present.

5) It gives complete freedom in choosing the cache-location.

6) A new block that has to be brought into the cache has to replace an existing block if the cache
is full.
7) The memory has to determine whether a given block is in the cache.
8) Advantage: It is more flexible than direct mapping technique.
9) Disadvantage: Its cost is high.

COMPUTER ORGANIZATION | DEPT. OF ELECTRONICS & COMMUNICATION ENGG.

86
 COMPUTER ORGANIZATION|MODULE 4: MEMORY SYSTEM 18EC35

SET-ASSOCIATIVE MAPPING
• It is the combination of direct and associative mapping. (Figure 8.18).
• The blocks of the cache are grouped into sets.
• The mapping allows a block of the main-memory to reside in any block of the
specified set.
• The cache has 2 blocks per set, so the memory-blocks 0, 64, 128…….. 4032 maps
into cache set „0‟.
• The cache can occupy either of the two block position within the set.
6 bit set field
 Determines which set of cache contains the desired block.
6 bit tag field
 The tag field of the address is compared to the tags of the two blocks of the set.
 This comparison is done to check if the desired block is present.

• The cache which contains 1 block per set is called direct mapping.
• A cache that has „k‟ blocks per set is called as “k-way set associative cache‟.
• Each block contains a control-bit called a valid-bit.
• The Valid-bit indicates that whether the block contains valid-data.
• The dirty bit indicates that whether the block has been modified during its cache
residency.
Valid-bit=0  When power is initially applied to system.

COMPUTER ORGANIZATION | DEPT. OF ELECTRONICS & COMMUNICATION ENGG. 87

 18EC35 COMPUTER ORGANIZATION| MODULE 3: INPUT/OUTPUT ORGANIZATION

Valid-bit=1  When the block is loaded from main-memory at first time.

If the main-memory-block is updated by a source & if the block in the source is already exists

in the cache, then the valid-bit will be cleared to “0‟.

• If Processor & DMA uses the same copies of data then it is called as Cache Coherence Problem.
• Advantages:
1) Contention problem of direct mapping is solved by having few choices for block placement.
2) The hardware cost is decreased by reducing the size of associative search.

REPLACEMENT ALGORITHM
• In direct mapping method,
the position of each block is pre-determined and there is no need of replacement strategy.
• In associative & set associative method,
The block position is not pre-determined.
If the cache is full and if new blocks are brought into the cache,
then the cache-controller must decide which of the old blocks has to be replaced.
• When a block is to be overwritten, the block with longest time w/o being referenced is over-written.
• This block is called Least recently Used (LRU) block & the technique is called LRU algorithm.
• The cache-controller tracks the references to all blocks with the help of block-counter.
• Advantage: Performance of LRU is improved by randomness in deciding which block is to be over-
written.

Eg:
Consider 4 blocks/set in set associative cache.
 2 bit counter can be used for each block.
 When a ‘hit’ occurs, then block counter=0; The counter with values originally lower than the
referenced one are incremented by 1 & all others remain unchanged.
 When a ‘miss’ occurs & if the set is full, the blocks with the counter value 3 is removed, the
new block is put in its place & its counter is set to “0‟ and other block counters are incremented
by 1.

PERFORMANCE CONSIDERATION
• Two key factors in the commercial success are 1) performance & 2) cost.
• In other words, the best possible performance at low cost.
• A common measure of success is called the Pricel Performance ratio.
• Performance depends on
→ how fast the machine instructions are brought to the processor &
→ how fast the machine instructions are executed.
• To achieve parallelism, interleaving is used.
• Parallelism means both the slow and fast units are accessed in the same manner.

INTERLEAVING
• The main-memory of a computer is structured as a collection of physically separate modules.
• Each module has its own
1) ABR (address buffer register) &
2) DBR (data buffer register).
• So, memory access operations may proceed in more than one module at the same time (Fig 5.25).
• Thus, the aggregate-rate of transmission of words to/from the main-memory can be increased.

COMPUTER ORGANIZATION | DEPT. OF ELECTRONICS & COMMUNICATION ENGG.

88
 COMPUTER ORGANIZATION|MODULE 4: MEMORY SYSTEM 18EC35

• The low-order k-bits of the memory-address select a module.

While the high-order m-bits name a location within the module.
In this way, consecutive addresses are located in successive modules.
• Thus, any component of the system can keep several modules busy at any one time T.
• This results in both
→ faster access to a block of data and
→ higher average utilization of the memory-system as a whole.
• To implement the interleaved-structure, there must be 2k modules;
Otherwise, there will be gaps of non-existent locations in the address-space.

Hit Rate & Miss Penalty

• The number of hits stated as a fraction of all attempted accesses is called the Hit Rate.
• The extra time needed to bring the desired information into the cache is called the Miss Penalty.
• High hit rates well over 0.9 are essential for high-performance computers.
• Performance is adversely affected by the actions that need to be taken when a miss occurs.
• A performance penalty is incurred because
of the extra time needed to bring a block of data from a slower unit to a faster unit.
• During that period, the processor is stalled waiting for instructions or data.
• We refer to the total access time seen by the processor when a miss occurs as the miss penalty.
• Let h be the hit rate, M the miss penalty, and C the time to access information in the cache. Thus,
the average access time experienced by the processor is
tavg = hC + (1 − h)M

4.5 VIRTUAL MEMORY

• It refers to a technique that automatically move program/data blocks into the main-memory when
they are required for execution (Figure 8.24).
• The address generated by the processor is referred to as a virtual/logical address.
• The virtual-address is translated into physical-address by MMU (Memory Management Unit).
• During every memory-cycle, MMU determines whether the addressed-word is in the memory.
If the word is in memory.
Then, the word is accessed and execution proceeds.
Otherwise, a page containing desired word is transferred from disk to memory.
• Using DMA scheme, transfer of data between disk and memory is performed.

COMPUTER ORGANIZATION | DEPT. OF ELECTRONICS & COMMUNICATION ENGG. 89

 18EC35 COMPUTER ORGANIZATION| MODULE 3: INPUT/OUTPUT ORGANIZATION

VIRTUAL MEMORY ADDRESS TRANSLATION

• All programs and data are composed of fixed length units called Pages (Figure 8.25).
The Page consists of a block-of-words. The words occupy contiguous locations in the memory.
The pages are commonly range from 2K to 16K bytes in length.
• Cache Bridge speed-up the gap between main-memory and secondary-storage.
• Each virtual-address contains
1) Virtual Page number (Low order bit) and
2) Offset (High order bit).
Virtual Page number + Offset  specifies the location of a particular word within a page.
• Page-table: It contains the information about
→ memory-address where the page is stored &
→ current status of the page.
• Page-frame: An area in the main-memory that holds one page.
• Page-table Base Register: It contains the starting address of the page-table.
• Virtual Page Number + Page-table Base register  Gives the starting address of the page if that page
currently resides in memory.
• Control-bits in Page-table: The Control-bits is used to
1) Specify the status of the page while it is in memory.
2) Indicate the validity of the page.
3) Indicate whether the page has been modified during its stay in the memory.

COMPUTER ORGANIZATION | DEPT. OF ELECTRONICS & COMMUNICATION ENGG.

90
 COMPUTER ORGANIZATION|MODULE 4: MEMORY SYSTEM 18EC35

TRANSLATION LOOKASIDE BUFFER (TLB)

• The Page-table information is used by MMU for every read/write access (Figure 8.26).
• The Page-table is placed in the memory but a copy of small portion of the page-table is located within
MMU. This small portion is called TLB (Translation LookAside Buffer).
TLB consists of the page-table entries that corresponds to the most recently accessed pages.
TLB also contains the virtual-address of the entry.

COMPUTER ORGANIZATION | DEPT. OF ELECTRONICS & COMMUNICATION ENGG. 91

 18EC35 COMPUTER ORGANIZATION| MODULE 3: INPUT/OUTPUT ORGANIZATION

• When OS changes contents of page-table, the control-bit will invalidate corresponding entry in TLB.
• Given a virtual-address, the MMU looks in TLB for the referenced-page.
If page-table entry for this page is found in TLB, the physical-address is obtained immediately.
Otherwise, the required entry is obtained from the page-table & TLB is updated.
Page Faults
• Page-fault occurs when a program generates an access request to a page that is not in memory.
• When MMU detects a page-fault, the MMU asks the OS to generate an interrupt.
• The OS
→ suspends the execution of the task that caused the page-fault and
→ begins execution of another task whose pages are in memory.
• When the task resumes the interrupted instruction must continue from the point of interruption.
• If a new page is brought from disk when memory is full, disk must replace one of the resident pages.
In this case, LRU algorithm is used to remove the least referenced page from memory.
• A modified page has to be written back to the disk before it is removed from the memory.
In this case, Write–Through Protocol is used.

COMPUTER ORGANIZATION | DEPT. OF ELECTRONICS & COMMUNICATION ENGG.

92
 COMPUTER ORGANIZATION|MODULE 4: MEMORY SYSTEM 18EC35

MEMORY MANAGEMENT REQUIREMENTS

• Management routines are part of the Operating-system.
• Assembling the OS routine into virtual-address-space is called System Space.
• The virtual space in which the user application programs reside is called the User Space.
• Each user space has a separate page-table.
• MMU uses the page-table to determine the address of the table to be used in the translation process.
• The process has two stages:
1) User State: In this state, the processor executes the user-program.
2) Supervisor State: In this state, the processor executes the OS routines.
Privileged Instruction
• In user state, the machine instructions cannot be executed.
• Hence a user-program is prevented from accessing the page-table of system-spaces.
• The control-bits in each entry can be set to control the access privileges granted to each program.
i.e. One program may be allowed to read/write a given page.
While the other programs may be given only read access.

4.6 SECONDARY-STORAGE
• The semi-conductor memories do not provide all the storage capability.
• The secondary-storage devices provide larger storage requirements.
• Some of the secondary-storage devices are:
1) Magnetic Disk
2) Optical Disk &
3) Magnetic Tapes.

MAGNETIC DISK
• Magnetic Disk system consists of one or more disk mounted on a common spindle.
• A thin magnetic film is deposited on each disk (Figure 8.27).
• Disk is placed in a rotary-drive so that magnetized surfaces move in close proximity to R/W heads.
• Each R/W head consists of 1) Magnetic Yoke & 2) Magnetizing-Coil.
• Digital information is stored on magnetic film by applying current pulse to the magnetizing-coil.
• Only changes in the magnetic field under the head can be sensed during the Read-operation.
• Therefore, if the binary states 0 & 1 are represented by two opposite states,
then a voltage is induced in the head only at 0-1 and at 1-0 transition in the bit stream.
• A consecutive of 0‟s & 1‟s are determined by using the clock.
• Manchester Encoding technique is used to combine the clocking information with data.

COMPUTER ORGANIZATION | DEPT. OF ELECTRONICS & COMMUNICATION ENGG. 93

 18EC35 COMPUTER ORGANIZATION| MODULE 3: INPUT/OUTPUT ORGANIZATION

• R/W heads are maintained at small distance from disk-surfaces in order to achieve high bit densities.
• When disk is moving at their steady state, the air pressure develops b/w disk-surfaces & head.
This air pressure forces the head away from the surface.
• The flexible spring connection between head and its arm mounting permits the head to fly at the
desired distance away from the surface.
Winchester Technology
• Read/Write heads are placed in a sealed, air–filtered enclosure called the Winchester Technology.
• The read/write heads can operate closure to magnetic track surfaces because
the dust particles which are a problem in unsealed assemblies are absent.
Advantages
• It has a larger capacity for a given physical size.
• The data intensity is high because
the storage medium is not exposed to contaminating elements.
• The read/write heads of a disk system are movable.
• The disk system has 3 parts: 1) Disk Platter (Usually called Disk)
2) Disk-drive (spins the disk & moves Read/write heads)
3) Disk Controller (controls the operation of the system.)

ORGANIZATION & ACCESSING OF DATA ON A DISK

• Each surface is divided into concentric Tracks (Figure 8.28).
• Each track is divided into Sectors.
• The set of corresponding tracks on all surfaces of a stack of disk form a Logical Cylinder.
• The data are accessed by specifying the surface number, track number and the sector number.
• The Read/Write-operation start at sector boundaries.
• Data bits are stored serially on each track.

COMPUTER ORGANIZATION | DEPT. OF ELECTRONICS & COMMUNICATION ENGG.

94
 COMPUTER ORGANIZATION|MODULE 4: MEMORY SYSTEM 18EC35

• Each sector usually contains 512 bytes.

• Sector Header --> contains identification information.
It helps to find the desired sector on the selected track.
• ECC (Error checking code)- is used to detect and correct errors.
• An unformatted disk has no information on its tracks.
• The formatting process divides the disk physically into tracks and sectors.
• The formatting process may discover some defective sectors on all tracks.
• Disk Controller keeps a record of various defects.
• The disk is divided into logical partitions:
1) Primary partition
2) Secondary partition
• Each track has same number of sectors. So, all tracks have same storage capacity.
• Thus, the stored information is packed more densely on inner track than on outer track.
Access Time
• There are 2 components involved in the time-delay:
1) Seek time: Time required to move the read/write head to the proper track.
2) Latency/Rotational Delay: The amount of time that elapses after head is positioned over
the correct track until the starting position of the addressed sector passes under the R/W head.
Seek time + Latency = Disk access time
Typical Disk
 One inch disk-weight = 1 ounce, size -> comparable to match book
Capacity -> 1GB
 Inch disk has the following parameter
Recording surface=20
Tracks=15000 tracks/surface
Sectors=400.
Each sector stores 512 bytes of data

Capacity of formatted disk=20x15000x400x512=60x109 =60GB Seek time=3ms

Platter rotation=10000 rev/min

Latency=3ms

Internet transfer rate=34MB/s

COMPUTER ORGANIZATION | DEPT. OF ELECTRONICS & COMMUNICATION ENGG. 95

 18EC35 COMPUTER ORGANIZATION| MODULE 3: INPUT/OUTPUT ORGANIZATION

DATA BUFFER/CACHE
• A disk-drive that incorporates the required SCSI circuit is referred as SCSI Drive.
• The SCSI can transfer data at higher rate than the disk tracks.
• A data buffer can be used to deal with the possible difference in transfer rate b/w disk and SCSI bus
• The buffer is a semiconductor memory.
• The buffer can also provide cache mechanism for the disk.
i.e. when a read request arrives at the disk, then controller first check if the data is available in
the cache/buffer.
If data is available in cache.
Then, the data can be accessed & placed on SCSI bus.
Otherwise, the data will be retrieved from the disk.

DISK CONTROLLER
• The disk controller acts as interface between disk-drive and system-bus (Figure 8.13).
• The disk controller uses DMA scheme to transfer data between disk and memory.
• When the OS initiates the transfer by issuing R/W‟ request, the controllers register will load the
following information:
1) Memory Address: Address of first memory-location of the block of words involved in the
transfer.
2) Disk Address: Location of the sector containing the beginning of the desired block of words.
3) Word Count: Number of words in the block to be transferred.

• The disk-address issued by the OS is a logical address.

• The corresponding physical-address on the disk may be different.
• The controller's major functions are:
1) Seek - Causes disk-drive to move the R/W head from its current position to desired track.
2) Read - Initiates a Read-operation, starting at address specified in the disk-address register.
Data read serially from the disk are assembled into words and placed into the data buffer
for transfer to the main-memory.
3) Write - Transfers data to the disk.
4) Error Checking - Computes the error correcting code (ECC) value for the data read from a
given sector and compares it with the corresponding ECC value read from the disk.
In case of a mismatch, it corrects the error if possible;
Otherwise, it raises an interrupt to inform the OS that an error has occurred.

COMPUTER ORGANIZATION | DEPT. OF ELECTRONICS & COMMUNICATION ENGG.

96
 COMPUTER ORGANIZATION|MODULE 4: MEMORY SYSTEM 18EC35

Problem 1:
Consider the dynamic memory cell. Assume that C = 30 femtofarads (10−15 F) and that leakage current
through the transistor is about 0.25 picoamperes (10−12 A). The voltage across the capacitor when it is
fully charged is 1.5 V. The cell must be refreshed before this voltage drops below 0.9 V. Estimate the
minimum refresh rate.
Solution:
The minimum refresh rate is given by

Therefore, each row has to be refreshed every 8 ms.

Problem 2:
Consider a main-memory built with SDRAM chips. Data are transferred in bursts & the burst length is
8. Assume that 32 bits of data are transferred in parallel. If a 400-MHz clock is used, how much time
does it take to transfer:
(a) 32 bytes of data
(b) 64 bytes of data
What is the latency in each case?
Solution:
(a) It takes 5 + 8 = 13 clock cycles.

(b) It takes twice as long to transfer 64 bytes, because two independent 32-byte transfers have
to be made. The latency is the same, i.e. 38 ns.

Problem 3:
Give a critique of the following statement: “Using a faster processor chip results in a corresponding
increase in performance of a computer even if the main-memory speed remains the same.”
Solution:
A faster processor chip will result in increased performance, but the amount of increase will not
be directly proportional to the increase in processor speed, because the cache miss penalty will
remain the same if the main-memory speed is not improved.

Problem 4:
A block-set-associative cache consists of a total of 64 blocks, divided into 4-block sets. The main-
memory contains 4096 blocks, each consisting of 32 words. Assuming a 32-bit byte-addressable
address-space,
(a) how many bits are there in main-memory address
(b) how many bits are there in each of the Tag, Set, and Word fields?
Solution:
(a) 4096 blocks of 128 words each require 12+7 = 19 bits for the main-memory address.
(b) TAG field is 8 bits. SET field is 4 bits. WORD field is 7 bits.

Problem 5:
The cache block size in many computers is in the range of 32 to 128 bytes. What would be the main
advantages and disadvantages of making the size of cache blocks larger or smaller?
Solution:
Larger size
 Fewer misses if most of the data in the block are actually used
 Wasteful if much of the data are not used before the cache block is ejected from the
cache

COMPUTER ORGANIZATION | DEPT. OF ELECTRONICS & COMMUNICATION ENGG. 97

 18EC35 COMPUTER ORGANIZATION| MODULE 3: INPUT/OUTPUT ORGANIZATION

Smaller size
 More misses
Problem 5:
Consider a computer system in which the available pages in the physical memory are divided among
several application programs. The operating system monitors the page transfer activity and
dynamically adjusts the number of pages allocated to various programs. Suggest a suitable strategy
that the operating system can use to minimize the overall rate of page transfers.
Solution:
The operating system may increase the main-memory pages allocated to a program that has a
large number of page faults, using space previously allocated to a program with a few page
faults

Problem 6:
In a computer with a virtual-memory system, the execution of an instruction may be interrupted by a
page fault. What state information has to be saved so that this instruction can be resumed later? Note
that bringing a new page into the main-memory involves a DMA transfer, which requires execution of
other instructions. Is it simpler to abandon the interrupted instruction and completely re-execute it
later? Can this be done?
Solution:
Continuing the execution of an instruction interrupted by a page fault requires saving the entire
state of the processor, which includes saving all registers that may have been affected by the
instruction as well as the control information that indicates how far the execution has
progressed. The alternative of re-executing the instruction from the beginning requires a
capability to reverse any changes that may have been caused by the partial execution of the
instruction.

Problem 7:
When a program generates a reference to a page that does not reside in the physical main-memory,
execution of the program is suspended until the requested page is loaded into the main-memory from
a disk. What difficulties might arise when an instruction in one page has an operand in a different
page? What capabilities must the processor have to handle this situation?
Solution:
The problem is that a page fault may occur during intermediate steps in the execution of a
single instruction. The page containing the referenced location must be transferred from the
disk into the main-memory before execution can proceed.
Since the time needed for the page transfer (a disk operation) is very long, as compared to
instruction execution time, a context-switch will usually be made.
(A context-switch consists of preserving the state of the currently executing program, and
”switching” the processor to the execution of another program that is resident in the main-
memory.) The page transfer, via DMA, takes place while this other program executes. When the
page transfer is complete, the original program can be resumed.
Therefore, one of two features are needed in a system where the execution of an individual
instruction may be suspended by a page fault. The first possibility is to save the state of
instruction execution. This involves saving more information (temporary programmer-
transparent registers, etc.) than needed when a program is interrupted between instructions.
The second possibility is to ”unwind” the effects of the portion of the instruction completed
when the page fault occurred, and then execute the instruction from the beginning when the
program is resumed.

COMPUTER ORGANIZATION | DEPT. OF ELECTRONICS & COMMUNICATION ENGG.

98
 COMPUTER ORGANIZATION|MODULE 4: MEMORY SYSTEM 18EC35

Problem 8:
Magnetic disks are used as the secondary storage for program and data files in most virtual-memory
systems. Which disk parameter(s) should influence the choice of page size?
Solution:
The sector size should influence the choice of page size, because the sector is the smallest
directly addressable block of data on the disk that is read or written as a unit. Therefore, pages
should be some small integral number of sectors in size.

Problem 9:
A disk unit has 24 recording surfaces. It has a total of 14,000 cylinders. There is an average of 400
sectors per track. Each sector contains 512 bytes of data.
(a) What is the maximum number of bytes that can be stored in this unit?
(b) What is the data-transfer rate in bytes per second at a rotational speed of 7200 rpm?
(c) Using a 32-bit word, suggest a suitable scheme for specifying the disk address.
Solution:
(a) The maximum number of bytes that can be stored on this disk is 24 X 14000 X 400 X 512 =
68.8 X 109 bytes.
(b) The data-transfer rate is (400 X 512 X 7200)/60 = 24.58 X 106 bytes/s.
(c) Need 9 bits to identify a sector, 14 bits for a track, and 5 bits for a surface.
Thus, a possible scheme is to use address bits A8-0 for sector, A22-9 for track, and A27-23 for surface
identification. Bits A31-28 are not used.

COMPUTER ORGANIZATION | DEPT. OF ELECTRONICS & COMMUNICATION ENGG. 99