6.

Memory Organization
 6.1 Memory Hierarchy
• A computer system is equipped with a hierarchy of memory
subsystems.
• There are several memory types with very different
physical properties.
• The important characteristics of memory devices are cost
per bit, access time, data transfer rate, alterability and
compatibility with processor technologies.
• It shows the hierarchy of memory in a typical memory with a
trend in access time, amount of storage, and cost per
byte.
6.1 Memory Hierarchy

FIGURE 6.1: Memory Hierarchy

6.1 Memory Hierarchy
• Design constraints: How much? How fast? How
expensive?
• Faster access time, greater cost per bit
• Greater capacity, smaller cost per bit
• Greater capacity, slower access time.
6.2 Main Memory
• The main memory (RAM) stores data and instructions.
• The capacity of the memory is 128 words of 8 bits (one
byte) per word.

FIGURE 6.2: Block Diagram of RAM

 6.2 Main Memory
• RAMs are built from semiconductor materials.
• Semiconductor memories fall into two categories, SRAMs
(static RAMs) and DRAMs (dynamic RAMs).
• Dynamic RAM (DRAM): is made with cells that store data
as charge on capacitors.
• The presence or absence of charge in a capacitor is
interpreted as a binary 1 or 0.
• Because capacitors have a natural tendency to discharge,
DRAMs require periodic charge refreshing to maintain
data storage.
6.2 Main Memory
• Static RAM (SRAM): In a SRAM, binary values are stored using
traditional flip-flop logic-gate.
• A static RAM will hold its data as long as power is supplied to it.
• Static RAM’s are faster than dynamic RAM’s.
 6.2 Main Memory
• Differences between Dynamic RAM and Static RAM
Dynamic RAM Static RAM

• It requires periodic refreshing. • A bit of data is stored using the state of

a flip-flop.
• Large storage capacity. • Applying power is enough (no need for
refreshing).
• Used to create main memory • Retains value indefinitely, as long as it
is kept powered.
• Slower and cheaper than SRAM. • Mostly uses to create cache memory of
CPU
• It it is denser and less expensive. • Faster and more expensive than
DRAM.
6.2 Main Memory
• ROM is used for storing programs that are
permanently resident in the computer and for tables
of constants that do not change in value once the
production of the computer is completed.
• The ROM portion of main memory is needed for
storing an initial program called bootstrap
loader, which is to start the computer software
operating when power is turned on.
6.2 Main Memory

FIGURE 6.3 Block diagram of ROM

6.2 Main Memory
Types of ROM
• ROM: The data is actually wired in the factory.
• The data can never be altered.
• PROM: Programmable ROM.
• It can only be programmed once after its fabrication.
• It requires special device to program.
6.2 Main Memory
• EPROM: Erasable Programmable ROM.
• It can be programmed multiple times.
• Whole capacity need to be erased by ultraviolet radiation before a new
programming activity.
• It cannot be partially programmed.
• EEPROM: Electrically Erasable Programmable ROM.
• Erased and programmed electrically.
• It can be partially programmed.
• Write operation takes considerably longer time compared to read operation.
 6.2 Main Memory
• Connection of RAM and CPU: Data transfer between the
main memory and the CPU register takes place through two
registers namely MAR (memory address register) and MDR
(memory data register).
• If MAR is k bits long and MDR is n bits long, the main
memory unit can contain up to 2k addressable locations.
• During a “memory cycle‟ n bits of data are transferred
between main memory and CPU.
• This transfer takes place over the processor bus, which has k
address lines and n data lines.
 6.2 Main Memory
• The CPU initiates a memory operation by loading
the appropriate data into registers MDR and MAR,
and setting either Read or Write memory control line
to 1.
• When the required operation is completed the
memory control circuitry sends Memory Function
Completed (MFC) signal to CPU.
• Memory Address Map is a pictorial representation of
assigned address space for each chip in the system.
6.2 Main Memory

FIGURE 6.4 Connection of RAM to CPU

6.2 Main Memory
• The time that elapses between the initiation of
an operation and completion of that operation is
called memory access time.
• The minimum time delay between two
successive memory operations is called
memory cycle time.
• The cycle time is usually slightly lower than the
access time.
6.3 Cache Memory
• Cache memory is a small, high-speed RAM buffer
located between the CPU and main memory.
• Cache memory holds a copy of the instructions
(instruction cache) or data (operand or data cache)
currently being used by the CPU.
• The main purpose of a cache is to accelerate your
computer while keeping the price of the computer low.
 6.3 Cache Memory
• The cache is the fastest component in the memory hierarchy
and approaches the speed of CPU component.
• When CPU needs to access memory, the 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 is not found in the cache,
the main memory is accessed to read the word.
• When the CPU refers to memory and finds the word in cache,
it is said to produce a hit.
• Otherwise, it is a miss.
6.3 Cache Memory
• The performance of cache memory is frequently measured
in terms of a quantity called hit ratio.
• Hit ratio = hit / (hit+miss)
• The basic characteristic of cache memory is its fast access
time
• Therefore, very little or no time must be wasted when
searching the words in the cache
• The transformation of data from main memory to cache
memory is referred to as a mapping process.
6.3 Cache Memory
• The problem with both measures is that they don’t factor
in the cost of a miss.
• A better measure is the average memory access time,
• Average memory access time = Hit time +
Miss rate × Miss penalty
6.3 Cache Memory
TYPES OF CACHES MAPPING:
1. Direct Mapping
2. Associative Mapping
3. Set Associative Mapping
6.3 Cache Memory
1. Direct Mapping: The direct mapping technique is simple and
inexpensive to implement.
• In general case, there are 2^k words in cache memory and 2^n words in
main memory (in our case, k=9, n=15).
• The n bit memory address is divided into two fields: k-bits for the index and
n-k bits for the tag field.
• When the CPU wants to access data from memory, it places an address.
• The index field of CPU address is used to access address.
• The tag field of CPU address is compared with the associated tag in the
word read from the cache.
6.3 Cache Memory
• If the tag-bits of CPU address is matched with the tag-bits of cache, then
there is a hit and the required data word is read from cache.
• If there is no match, then there is a miss and the required data word is
stored in main memory.
• It is then transferred from main memory to cache memory with the new
tag.
6.3 Cache Memory
2. Associative Mapping: An associative mapping uses an associative
memory.
• This memory is being accessed using its contents.
• Associative memory is expensive compared to RAM
• Each line of cache memory will accommodate the address (main memory)
and the contents of that address from the main memory.
• That is why this memory is also called Content Addressable Memory
(CAM).
• It allows each block of main memory to be stored in the cache.
6.3 Cache Memory
• A CPU address of 15 bits is places in the argument register and the
associative memory us searched for a matching address.
• If the address is found, the corresponding 12 bits data is read and sent to
the CPU.
• If not, the main memory is accessed for the word.
• 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.
6.3 Cache Memory
3. Set Associative Mapping: That is the easy control of the direct mapping cache
and the more flexible mapping of the fully associative cache.
• In set associative mapping, each cache location can have more than one pair of tag +
data items.
• That is more than one pair of tag and data are residing at the same location of cache
memory.
• If one cache location is holding two pair of tag + data items, that is called 2-way set
associative mapping.
• The disadvantage of direct mapping is that two words with the same index in their
address but with different tag values cannot reside in cache memory at the same
time.
• Set-Associative Mapping is an improvement over the direct-mapping in that each
word of cache can store two or more word of memory under the same index address.
6.3 Cache Memory
Replacement Algorithms of Cache Memory
• Replacement algorithms are used when there are no available space in a
cache in which to place a data.
• Four of the most common cache replacement algorithms are described
below:
• Least Recently Used (LRU): The LRU algorithm selects for replacement
the item that has been least recently used by the CPU.
• First-In-First-Out (FIFO): The FIFO algorithm selects for replacement
the item that has been in the cache from the longest time.
• Random: The random algorithm selects for replacement the item
randomly.
6.3 Cache Memory
• When memory write operations are performed, CPU first
writes into the cache memory.
• These modifications made by CPU during a write
operations, on the data saved in cache; need to be
written back to main memory or to auxiliary memory.
• These two popular cache write policies (schemes) are:
Write-Through and Write-Back.
6.3 Cache Memory
• Write-Through: In a write through cache, the main memory is updated
each time the CPU writes into cache.
• The advantage of the write-through cache is that the main memory always
contains the same data as the cache contains.
• This characteristic is desirable in a system which uses direct memory access
scheme of data transfer.
• The I/O devices communicating through DMA receive the most recent data.
6.3 Cache Memory
• Write-Back: In a write back scheme, only the cache memory is updated.
• During the updating, locations in the cache memory are marked by a flag so
that later on, when the word is removed from the cache, it is copied into the
main memory.
• The words are removed from the cache time to time to make room for a new
block of words.
6.3 Cache Memory
• Virtual Memory: The term virtual memory refers to something which
appears to be present but actually it is not.
• The virtual memory technique allows users to use more memory for a
program than the real memory of a computer.
• So, virtual memory is the concept that gives the illusion to the user that they
will have main memory equal to the capacity of secondary storage media.
• A programmer can write a program which requires more memory space
than the capacity of the main memory.
• Such a program is executed by virtual memory technique.
6.3 Cache Memory
• The program is stored in the secondary memory.
• The memory management unit (MMU) transfers the currently needed part
of the program from the secondary memory to the main memory for
execution.
• This to and fro movement of instructions and data (parts of a program)
between the main memory and the secondary memory is called Swapping.
 6.3 Cache Memory
Address Space and Memory Space
• Virtual address is the address used by the programmer and the set of such addresses is
called the address space or virtual memory.
• An address in main memory is called a location or physical address.
• The set of such locations in main memory is called the memory space or physical
memory.
• CPU generated logical address consisting of a logical page number plus the location
within that page (x).
• It must be mapped onto an actual (physical) main memory address by the operating
system using mapper.
• If the page is present in the main memory, CPU gets the required data from the main
memory.
• If the mapper detects that the requested page is not present in main memory, a page
fault occurs and the page must be read from secondary storage into a page frame in
main memory.
6.4 Secondary Memory
• Devices that provides backup storage are called an Auxiliary memory
(Secondary memory).
• It stores information that is not necessarily in current use.
• It is slower and having higher capacity than primary memory.
• This kind of memory is large, slow and inexpensive.
• It is non-volatile storage media i.e. the contents are not erased when the
power is switched off.
• Magnetic disk, Magnetic tape and optical disk are the examples of
secondary storage.
6.4 Secondary Memory
• Magnetic Disk: Magnetic disks are the foundation of external memory on
virtually all computer systems.
• A disk is a circular platter constructed of nonmagnetic material called the
substrate coated with a magnetisable material.
• More suitable than magnetic tapes for a wider range of applications such as
supporting direct access of data
• It is a thin, circular plate made of metal & plastic, which is coated with iron-
oxide.
• We can randomly access the data.
• They must be stored in dust free environment.
• It stores large amount of data.
6.4 Secondary Memory
• The magnetic disks come in different sizes.
• Due to large storage capacity of magnetic disks and lesser failures the use of
these devices increasing day by day.
• Due to their low cost and high data recording densities, the cost per bit of
storage is low for magnetic disks.
• An additional cost benefit is that magnetic disks can be erased and reused
many times
• Suitable for both on-line and off-line storage of data
• Data transfer rate for a magnetic disk system is normally higher than a
magnetic tape system.
6.4 Secondary Memory
• There are two types of Magnetic Disks:
1. Floppy Disk
2. Hard Disk
6.4 Secondary Memory
1. Floppy Disk: Very large amount of data can be stored in a small storage
space.
• It is a portable, inexpensive storage medium that consists of thin, circular,
flexible plastic Mylar film.
• It was introduced by IBM in 1972.
• Standard floppy disk has storage capacity up to 1.44MB.
• Floppy disks are compact, lightweight and easily portable from one place to
another.
• Most popular secondary storage medium used in small computers.
• Also known as floppies or diskettes.
6.4 Secondary Memory
Types of Floppy disks:
• 5¼-inch diskette, whose diameter is 5¼-inch. It is encased in a square, flexible
vinyl jacket.
• 3½-inch diskette, whose diameter is 3½-inch. It is encased in a square, hard
plastic jacket.
Advantages
• Reusable, portable, Handy
• Very low price
• Provide random access of data
Disadvantages
• Not Durable and Prone to damage
• Very low Capacities
6.4 Secondary Memory
2. Hard Disk: Round, flat piece of rigid metal (frequently aluminium) disks coated
with magnetic oxide.
• It is a storage device that contains one or more inflexible, circular patterns that store
data, instructions & information.
• We can store documents, presentation, database, e-mails, messages, music, video,
software etc.
• Come in many sizes, ranging from 1 to 14-inch diameter.
• Hard disk of capacities 10GB, 20GB, 40GB and even more are easily available.
• RAID (Redundant Array of Independent Disks): To achieve greater
performance and higher availability, servers and larger systems use RAID disk
technology.
• RAID is a family of techniques for using multiple disks as a parallel array of data
storage devices, with redundancy built in to compensate for disk failure
6.4 Secondary Memory
• RAID is a set of physical disk drives viewed by the operating system as a
single logical drive.
• Data are distributed across the physical drives of an array.
• Redundant disk capacity is used to store parity information, which
guarantees data recoverability in case of a disk failure.
• The RAID array creates significant performance and reliability gains.
6.4 Secondary Memory
• Optical Disk: Is a Laser beam technology for recording and reading of data on the
disk.
• Laser beam technology is used for recording/reading of data on the disk.
• Also known as laser disk/optical laser disk, due to the use of laser beam technology.
• Proved to be a promising random access medium for high capacity secondary storage
because it can store extremely large amounts of data in a limited space.
• Access times for optical disks are typically in the range of 100 to 300 milliseconds
and that of hard disks are in the range of 10 to 30 milliseconds.
• The most popular optical disk uses a disk of 5.25 inch diameter with storage capacity
of around 650 Megabytes.
6.4 Secondary Memory
• The optical disk became the preferred medium for music, movies and
software programs because, its:
• Compact
• Lightweight
• Durable and digital
• The optical disk also provides a minimum of 650 MB of data storage.
6.4 Secondary Memory
Advantage of Optical Disk
• The cost-per-bit of storage for optical disks is very low because of their low
cost and enormous storage density.
• Optical disk drives do not have any mechanical read/write heads to rub
against or crash into the disk surface.
• This makes optical disks a more reliable storage medium than magnetic
tapes or magnetic disks.
• Optical disks have a data storage life in excess of 30 years.
• This makes them a better storage medium for data archiving as compared
to magnetic tapes or magnetic disks.
6.4 Secondary Memory
Limitation of Optical disk
• Data once recorded, cannot be erased and hence the optical disks cannot be
reused.
• The data access speed for optical disks is slower than magnetic disks.
• Optical disks require a complicated drive mechanism.
6.4 Secondary Memory
Optical Disk Types:
• Compact Disk(CD): Is A non-erasable disk that stores digitized audio information.
• The standard system uses 12cm disks and can record more than 60 minutes of
uninterrupted playing time.
• Compact Disk Read-Only Memory (CD-ROM): A non-erasable disk used for
storing computer data. The standard system uses 12-cm disks and can hold more
than 650 Mbytes.
• Recordable CD (CD-R): The user can write to the disk only once.
• CD-RW: The user can erase and rewrite to the disk multiple times.
• Digital Versatile Disk (DVD): A technology for producing digitized, compressed
representation of video information, as well as large volumes of other digital data.
6.4 Secondary Memory
• DVD Rewritable (DVD-R): the user can write to the disk only once. Only
one-sided disks can be used.
• DVD Rewritable (DVD-RW): The user can erase and rewrite to the disk
multiple times. Only one-sided disks can be used.
• The Blu-ray Disc: is a technology plat form that can store sound and
video while maintaining high quality and also access the stored content in
an easy way to-use.
Advantage of Blu-ray Disc are:
• Large recording capacity up to 27 GB.
• High-speed data transfer rate 36 Mbps.
• Easy to use disc cartridge.
6.4 Secondary Memory
• Both the Compact Disk CD and the CD-ROM (compact disk read-only
memory) share a similar technology.
• The main difference is that CD-ROM players are more rugged and have
error correction devices to ensure that data are properly transferred from
disk to computer.
• The optical disk is removable, allowing the disk itself to be used for archival
storage.
• Most magnetic disks are no removable.
6.4 Secondary Memory
Disadvantages of CD-ROM are as follows:
• It is read-only and cannot be updated.
• It has an access time much longer than that of a magnetic disk drive, as
much as half a second.
• The CD-RW has the obvious advantage over CD-ROM and CD-R that it can
be rewritten and thus used as a true secondary storage.
• A key advantage of the optical disk is that the engineering tolerances for
optical disks are much less severe than for high-capacity magnetic disks.
• Thus, they exhibit higher reliability and longer life,as much as a CD-ROM.
6.4 Secondary Memory
• Magnetic Tape: is a plastic ribbon which is usually ½ inch or ¼ inch
wide & 50 to 2400 feet long.
• It is coated with iron-oxide material.
• It is similar to the tape of audio cassettes of tape recorders.
• Data is stored as binary digits.
• Data is accessed sequentially so searching becomes difficult.
• Tape systems use the same reading and recording techniques as disk
systems.
• Magnetic tape was the first kind of secondary memory.
• It is still widely used as the lowest-cost, slowest-speed member of the
memory hierarchy.
6.4 Secondary Memory
Advantages:
• Store data up to few gigabytes and Low cost.
• Magnetic tape used by both mainframes and microcomputers.
Disadvantages:
• Sequential access so searching becomes difficult.
• We can either read or write data at one time.
5.14 Stack Organization
• A useful feature that is included in the CPU of most computers is a stack or
last- in, first-out (LIFO) list.
• A stack is a storage device that stores information in such a manner that the
item stored last is the first item retrieved.
• The stack in digital computers is essentially a memory unit with an address
register that can count only (after an initial value is loaded into it).
• The register that holds the address for the stack is called a stack pointer
(SP) because its value always points at the top in the stack.
5.14 Stack Organization
• The two operations of a stack are the insertion and deletion of items.
• The operation of the insertion is called PUSH (or push-down) because it can
be thought of as the result of pushing a new item on top.
• The operation of deletion is called POP (or pop-up) because it can be
thought as the result of removing one item so that the stack pops up.
• However, nothing is pushed or popped in a computer stack.
• In computers, these operations are simulated by incrementing or
decrementing the stack pointer register.
• Register Stack: A stack can be placed in a portion of a large memory or it
can be organized as a collection of a finite number of memory words or
registers.
5.14 Stack Organization
• It shows the organizations of a 64-word register stack.
• The stack pointer register SP contains a binary number whose value is equal to the
address of the word that is currently on top of the stack.
• Three items are placed in the stack: A, B and C in that order.
• Item C is on top of the stack so that the content of SP is now 3.
• To remove the top item, the stack is popped by reading the memory word at address
3 and decrementing the content of SP.
• Item B is now on top of the stack since SP holds address 2.
• To insert a new item, the stack is pushed by incrementing SP and writing a word in
the next higher location in the stack.
• Note that item C has been read out but not physically removed.
• This does not matter because when the stack is pushed, a new item is written in its
place.
5.14 Stack Organization

FIGURE 5.8: Block Diagram of 64-word Stack

5.14 Stack Organization
• In a 64-word stack, the stack pointer contains 6-bits because 26 = 64.
• Since SP has only 6-bits it cannot exceed a number greater than 63 (111111
in binary).
• When 63 is incremented by 1, the result is 0 since 111111+ 1 = 1000000 in
binary, but SP can accommodate only the 6 list significant bits.
• Similarly, when 000000 is decremented by 1, the result is 111111.
• The 1-bit register FULL is set to 1 when the stack is full, and the 1-bit
register EMTY is set to 1 when the stack is empty of items.
• DR is the data register that holds the binary data to be written in to or read
out of the stack.
5.14 Stack Organization
• Initially, SP is cleared to 0, EMTY is set to 1 and FULL is cleared to 0, so
that points to the word at address 0 and the stack is marked empty and not
full.
• If the stack is not full (if FULL = 0), a new item is inserted with the PUSH
operation.
• The PUSH operation is implemented with the following sequence of micro-
operations SP SP + 1 Increment stack pointer M[SP] DR Write item on top
of the stack If (SP = 0) then (FULL 1) Check if stack is full EMTY 0.
• Mark the stack not empty.
5.14 Stack Organization
• The stack pointer is incremented so that it points to the address the next higher word.
• A memory write operation inserts the word from DR in to the top of the stack.
• Note that SP holds the address of the top of the stack and that M[SP] denotes the
memory word specified by the address presently available in SP.
• The first item stored in the stack is at address 1.
• The last item is stored at address 0.
• If SP reaches 0, the stack is full of items, so FULL is set to 1.
• This condition is reached if the top item prior to the last push was in location 63 and
after incrementing SP, the last item is stored in location 0.
• Once an item is stored in location 0, there are no more empty registers in the stack.
• If an item is written in the stack, obviously the stack cannot be empty, so EMTY is
cleared to 0.
5.14 Stack Organization
• A new item is deleted from the stack if the stack is not empty (if EMTY = 0).
• The pop operation consists of the following sequences of microoperations:
DR M[SP] Read item from the top of the stack SP SP - 1 Decrement stack
pointer If (SP = 0) then (EMTY 1)
• Check if stack is empty FULL 0 Mark the stack not full.
• The top item is read from the stack into DR.
• The stack pointer is then decremented.
• If its value reaches 0, the stack is empty, so EMTY is set to 1.
• This condition is reached if the item read was in location 1. Once this item is
read out, SP is decremented and reaches the value of 0, which is the initial
value of SP.
5.14 Stack Organization
• Note that if a pop operation reads the item from location 0 and then SP is
decremented, SP changes to 111111, which is equivalent to decimal 63.
• In this configuration the word in address 0 receives the last item in the stack.
• Note also that an erroneous operation will result if the stack is pushed when FULL=1
or popped when EMTY=1.
• Memory Stack: A stack can exist as standalone unit or can be implemented in
random access memory attached to a CPU.
• The implementation of a stack in the CPU is done by assigning a portion of memory
to stack operation and using a processor register as a stack pointer.
• It shows a portion of computer memory partitioned into three segments: Program,
Data, and Stack.
5.14 Stack Organization
• The program counter PC points at the address of the next instruction in the
program.
• The address register ER points at an array of data.
• The stack pointer SP points at the top of the stack.
• The three registers are connected to a common address bus, and either one
can provide an address for memory.
• PC is used during the fetch phase to read an instruction.
• AR is used during the execute phase to read an operand.
• SP is used to push or POP items into or from the stack.
5.14 Stack Organization

FIGURE 5.9: Computer Memory

5.14 Stack Organization
• The initial value of SP is 4001 and the stack grows with decreasing addresses.
• Thus the first item stored in the stack is at address 4000, the second item is stored at
address 3999, and the last address that can be used for the stack is 3000.
• No provisions are available for stack limit checks.
• We assume that the items in the stack communicate with a data register DR.
• A new item is inserted with the push operation as follows: SP ← SP - 1 M[SP] DR.
• The stack pointer is decremented so that it points at the address of the next word.
• A memory write operation inserts the word from DR into the top of the stack. A new
item is deleted with the pop operation as follows:
5.14 Stack Organization
DR M[SP] SP SP + 1
• The top item is read from the stack into DR.
• The stack pointer is then incremented to point at the next item in the stack.
• Most computers do not provide hardware to check for stack overflow (full
stack) or underflow (empty stack).
• The stack limits can be checked by using to processor registers:
• One to hold the upper limit (3000 in our example), and the other to hold
the lower limit (4001 in the example).
• After a push operation, SP is compared with the upper limit register and
after a pop operation SP is compared with the lower limit register.
5.14 Stack Organization
• The two micro-operations needed for either the push or pop are:
1. An access to memory through SP
2. Updating SP.
End of Unit 6
Computer Organization and Architecture
Proposed with: Computer Organization and Architecture