|
UNIT – 4 |
||||||||||||||||||
|
INTRODUCTION |
||||||||||||||||||
|
Unit-04/Lecture-01 |
||||||||||||||||||
|
Memory organization: ·
Memory
Maps ·
Memory
Hierarchy ·
Cache
Memory - Organization and mappings ·
Associative
memory ·
Virtual
memory ·
Memory
Management Hardware –
The
design of a computer’s memory system has a significant effect on its overall
performance. This module reviews different memory system designs. –
We begins by examining the hierarchy of
memory systems. The hierarchy seeks to balance the cost of various types of
memory against their performance to achieve an optimal configuration. We then
study associative memory, a type of memory which is accessed by its data
rather than by address. –
Cache memory is a high-speed memory used
to hold data most likely to be needed by the CPU. It is very costly relative
to all other memory, so it is preferable to use a small amount in a computer
system to achieve some performance increase while reducing overall cost. –
Virtual memory is a methodology which
allows the user to run programs which are larger than the computer’s memory
space. It swaps pages of program data in and out of physical memory. –
Memory management hardware coordinates
these transfers. ·
Memory
Map Ř A
memory map is a structure of data (which usually resides in memory
itself) that indicates how memory
is laid out. Memory maps can have a different meaning in different parts of
the operating system. It is the fastest and most flexible cache organization
uses an associative memory. The associative memory stores both the address
and content of the memory word. Ř In
the boot process,
a memory map is passed on from the firmware
in order to instruct an operating system kernel
about memory layout. It contains the information regarding the size of total
memory, any reserved regions and may also provide other details specific to
the architecture. Ř In
virtual memory
implementations and memory
management units, a memory map refers to page tables,
which store the mapping between a certain process's virtual memory layout and
how that space relates to physical memory addresses. Ř In
native debugger
programs, a memory map refers to the mapping between loaded
executable/library files and memory regions. These memory maps are used to
resolve memory addresses
(such as function pointers)
to actual symbols. Ř BIOS
Memory map The
PC BIOS provides a set of routines that can be used by operating system to
get memory layout. Some of the available routines are: BIOS
Function: INT 0x15, AX=0xE801: This
BIOS interrupt call is used by the running OS to get the memory size for
64MB+ configurations. It is supported by AMI BIOSses dated 8/23/94 or later.
The operating system just sets AX to 0xE801 then calls int 0x15. If some
error has happened, the routine returns with CF (Carry Flag) set to 1. If no
error, the routine returns with CF clear and the state of registers is
described as following:
·
Memory Hierarchy Ř Memory is
arranged hierarchically to maximize system performance while reducing system
cost. Main memory is traditional memory, ROM and RAM in a computer system. It
can be accessed directly by the CPU. When the CPU runs a program, it is first
loaded into main memory. Ř Main memory is
relatively slow as compared to the CPU, and it is desirable to reduce the
delay associated with memory access in order to improve system performance. Ř This is done
using cache memory. This is a high-speed memory which is situated between the
CPU and main memory. Data is copied from main memory into the cache; if the
CPU needs this data, it can get it directly from the cache. Cache memory is
relatively expensive, too much so to build an entire memory system out of
cache memory. However, even a small amount of cache can improve system
performance tremendously. Ř Auxiliary memory
is used to give a computer more memory without adding more RAM. A computer
with, say 16 MB of RAM may need to run programs or access data files larger
than this. Ř A disk can be used to serve as additional memory,
say 32 MB. The program now sees a memory system with 48 MB of RAM. Hardware
makes sure that the portion of the program needed by the CPU actually resides
in RAM. This hardware also makes sure that the address genreated by the CPU
is mapped to the correct physical memory location.
Fig. Computer memory Hierarchy Ř Memory Hierarchy is to obtain the highest possible access speed while
minimizing the total cost of the memory system. Ř Memory hierarchy
in a computer system : –
Main Memory: memory unit that
communicates directly with the CPU (RAM). –
Auxiliary Memory: device that provide
backup storage (Disk Drives). –
Cache Memory: special very-high-speed
memory to increase the processing speed (Cache RAM).
Fig: Memory Hierarchy in Computer System
|
||||||||||||||||||
|
Unit-04/Lecture-02 |
||||||||||||||||||
|
Main memory Ř Main memory is where programs and data are kept when the processor is actively using them. When programs and data become active, they are copied from secondary memory into main memory where the processor can interact with them. A copy remains in secondary memory. Ř Main memory is intimately connected to the processor, so moving instructions and data into and out of the processor is very fast. Ř Main memory is sometimes called RAM. RAM stands for Random Access Memory. "Random" means that the memory cells can be accessed in any order. However, properly speaking, "RAM" means the type of silicon chip used to implement main memory. Ř Refers to physical memory that is internal to the computer. The word main is used to distinguish it from external mass storage devices such as disk drives. Another term for main memory is RAM. Ř The computer can manipulate only data that is in main memory. Therefore, every program you execute and every file you access must be copied from a storage device into main memory. The amount of main memory on a computer is crucial because it determines how many programs can be executed at one time and how much data can be readily available to a program. Ř Because computers often have too little main memory to hold all the data they need, computer engineers invented a technique called swapping, in which portions of data are copied into main memory as they are needed. Swapping occurs when there is no room in memory for needed data. When one portion of data is copied into memory, an equal-sized portion is copied (swapped) out to make room. Ř The main memory of the computer is also
known as RAM, standing for Random Access Memory. It is constructed
from integrated circuits and needs to have electrical power in order to
maintain its information. When power is lost, the information is lost too! It
can be directly accessed by the CPU. Ř The access time to read or write any
particular byte are independent of whereabouts in the memory that byte is,
and currently is approximately 50 nanoseconds (a thousand millionth of
a second). This is broadly comparable with the speed at which the CPU will
need to access data. Main memory is expensive compared to external memory so
it has limited capacity. Ř The capacity available for a given price
is increasing all the time. For example many home Personal Computers now have a capacity of 16 megabytes (million
bytes), while 64 megabytes is commonplace on commercial workstations. Ř The CPU will normally transfer data to
and from the main memory in groups of two, four or eight bytes, even if the
operation it is undertaking only requires a single byte. Ř Random-access memory (RAM /rćm/) is a form of computer data storage. A random-access memory
device allows data items to be read and
written in roughly the same amount of time regardless of the order in which
data items are accessed. In contrast, with other direct-access data storage
media such as hard disks, CD-RWs, DVD-RWs and the older drum memory, the time required to read and
write data items varies significantly depending on their physical locations
on the recording medium, due to mechanical limitations such as media rotation
speeds and arm movement delays. Ř Today, random-access
memory takes the form of integrated circuits. RAM is normally
associated with volatile types of memory (such as DRAM memory modules), where stored information is lost
if power is removed, although many efforts have been made to develop
non-volatile RAM chip. Other types of non-volatile memory exist that allow
random access for read operations, but either do not allow write operations
or have limitations on them. These include most types of ROM and a type of flash memory called NOR-Flash. Ř Random-access
memory (RAM) comes in two varieties— static and dynamic.
Static RAM (SRAM) is faster and significantly more expensive than Dynamic
RAM (DRAM). SRAM is used for cache memories, both on and off the CPU
chip. DRAM is used for the main memory plus the frame buffer of a graphics
system. Typically, a desktop system will have no more than a few megabytes of
SRAM, but hundreds or thousands of megabytes of DRAM. Static
RAM Ř SRAM stores
each bit in a bistable memory cell. Each cell is implemented with a
six-transistor circuit. This circuit has the property that it can stay
indefinitely in eith er of two different voltage configurations, or states.
Any other state will be unstable—starting from there, the circuit will
quickly move toward one of the stable states. Dynamic RAM DRAM stores each
bit as charge on a capacitor. This capacitor is very small—typically around
30 femto-farads, that is, 30 × 10−15 farads. Recall,
however, that a farad is a very large unit of measure. DRAM storage can be
made very dense—each cell consists of a capaci tor and a single
access-transistor. Unlike SRAM, however, a DRAM memory cell is very sensitive
to any disturbance. When the capacitor voltage is disturbed, it will never
recover. Exposure to light rays will cause the capacitor voltages to change.
In fact, the sensors in digital cameras and camcorders are essentially arrays
of DRAM cells. Various sources of
leakage current cause a DRAM cell to lose its charge within a time period of
around 10 to 100 milliseconds. Fortunately, for computers operating with
clock cycles times measured in nanoseconds, this retention time is quite
long. The memory system must periodically refresh every bit of memory by
reading it out and then rewriting it. Some systems also use error-correcting
codes, where the computer words are encoded a few more bits (e.g., a 32-bit
word might be encoded using 38 bits), such that circuitry can detect and correct
any single erroneous bit within a word. Auxiliary memory
Ř
Auxiliary memory,
also known as auxiliary storage, secondary storage, secondary
memory or external memory, is a non-volatile
memory (does not lose stored data when the device
is powered down) that is not directly accessible by the CPU, because it is
not accessed via the input/output channels (it is an external device). In RAM
devices (as flash memory) data can be directly deleted or changed. Ř
It is used to store a
large amount of data at lesser cost per byte than primary
memory; secondary storage is two orders of
magnitude less expensive than primary storage. Ř Forms
of Auxiliary Memory The most common form of auxiliary memory devices used
in consumer systems is flash memory,
optical discs,
and magnetic disks.
The latest addition to the auxiliary memory family is flash memory. This form
is much faster as compared to predecessors, as this form of auxiliary memory
does not involve any moving parts. In some laptops, such as Apple's MacBook
Air line and MacBook Pro with Retina Display line, solid state drives (SSDs)
made from flash memory have replaced magnetic disk based hard disk drives
(HDDs) that are found in most laptops. Flash storage chips tend to be
significantly more expensive at modestly large capacities compared to HDDs. ·
Flash memory:
An electronic non-volatile computer storage device that can be electrically
erased and reprogrammed, and works without any moving parts. Examples of this
are flash drives,
memory cards
and solid
state drives. A version of this is
implemented in many Apple notebooks. ·
Optical disc:
A storage medium from which data is read and written by lasers. Optical disks
can store much more data — up to 6 gigabytes more than most portable magnetic
media, such as floppies.
There are three basic types of optical disks: CD-ROM (read-only), WORM
(write-once read-many) & EO (erasable optical disks). ·
Magnetic Disk:
A magnetic disk is a circular plate constructed of metal or plastic coated
with magnetized material. Both sides of the disk are used and several disks
may be stacked on one spindle with read/write heads available on each
surface. Bits are stored in magnetized surface in spots along concentric
circles called tracks. Tracks are commonly divided into sections called
sectors. Disk that are permanently attached and cannot be removed by the
occasional user are called hard disks. A disk drive with removable disks is
called a floppy disk drive. ·
Magnetic tapes:
A magnetic tape transport consists of electric, mechanical and electronic
components to provide the parts and control mechanism for a magnetic tape
unit. The tape itself is a strip of plastic coated with a magnetic recording
medium. Bits are recorded as magnetic spots on tape along several tracks.
Seven or Nine bits are recorded to form a character together with a parity
bit. R/W heads are mounted in each track so that data can be recorded and
read as a sequence of characters.
|
|
Unit-03/Lecture-3 |
||||||||
|
Cache Memory:
–
Associative
mapping –
Direct
mapping –
Set-associative
mapping
Fig: Cache and Main memory
Fig: Cache/Main
Memory Structure Cache operation – overview •
CPU requests contents of memory location •
Check cache for this data •
If present, get from cache (fast) •
If not present, read required block from main memory
to cache •
Then deliver from cache to CPU •
Cache includes tags to identify which block of main
memory is in each cache slot Cache Read Operation – Flowchart
· Overlay the Least Recently Used cache block Writes are a concern: Inconsistency: When cache != memory Write-Through: Each write updates both the cache and
memory, ensuring consistency But this slows writes down to memory’s time durations Write Buffer: Holds data when a write is occurring to
memory. Allows for processor to continue processing even when a write is occurring Write buffer is cleared when memory returns successful status Larger write buffers prevent stalls due to write buffer full If memory store time exceeds the average write generate time, buffering cannot help Write-Back: Update memory only when cache is to be
replaced. Solves the short write time problem Sets Dirty Bit=1 when write is required Often used in combination with Write Buffer Example: Intrinsity
FastMATH Processor Embedded MIPS processor Has an instruction cache and data cache · Can simultaneously access an instruction and data word every cycle Cache size = 4K words with 16-word blocks Has write-through and write-back and 1-entry write buffer Multilevel Caching: Two levels of cache: Primary or L1 Cache: Small, expensive, very fast cache: 1 cycle access time Secondary or L2 Cache: Large, cheaper, slower cache: · Often < 10 processor cycles; · Often 10 times size of L1 Cache
|
|
Unit-03/Lecture-4 |
||||||||
|
Typical Cache Organization
Fig: Cache
Organization ·
Current main memory chips have access
times on the order of 60ns to 70ns. When one adds the time it takes for a
memory request to pass from the processor through the system bus and then the
memory controllers and decode logic, the memory access time can increase to
100ns or more. ·
A processor that runs with a 100MHz clock
has a cycle time of 10ns. If we assume that an addition can be executed in a
single processor cycle, then an ADD instruction that takes one of its
operands from main memory might spend 100ns waiting for that operand and only
10ns doing the addition. The overall time required to complete a program
would then be determined almost entirely by the memory access time;
increasing the processor speed would have very little effect. ·
Caches are introduced
into a system to buffer the mismatch between main memory and processor
speeds. A cache is a relatively small, fast memory placed between the
processor and the main memory. The cache is designed so that its access time
matches the processor cycle time. ·
Thus, if the processor is running with a
100MHz clock the cache should be able to respond to a memory request in
approximately 10ns. In the high-performance single-chip processors being
built today, the cache memory is actually built on the processor chip and
separated into distinct instruction and data caches. The typical size of
these caches is 8kb, for a total of 16kb of cache on the processor chip. Many
system designs also include an off-chip cache, which is called the
second-level cache or the L2 cache:
Fig: Caches in a Typical System The L2 cache can
be anywhere from 128kb to 4Mb in size. The on-chip cache is called the
first-level or primary cache. While the first-level cache must match the
processor speed, the second-level cache can be somewhat slower (but not as
slow as the main memory!) When the
processor makes a memory request, the request first passes to the primary
cache. If the data item is found in this cache, we have a cache hit.
If the data item is not found in the primary cache, we have a cache miss
and the memory request is forwarded to the L2 cache. If the data item is
found in this cache, we have an L2 cache hit and the data is passed back to
the primary cache. If the data is not found in the L2 cache, the request is
finally forwarded to the main memory. When the main memory responds to the
memory request, the data item is passed back to the L2 cache and then the
primary cache. Caches work well
because the memory request can usually be serviced by the primary cache. In
fact, measurements show
that 90% of the time the instruction cache will contain the requested
instruction and 85% of the time the data cache will be able to respond to the
data request. Thus, the L2 and main memory are rarely accessed. The reason that
so many memory requests can be handled by the primary cache has to do with
two aspects of program behavior: Temporal Locality If a memory
location is referenced, it is very likely that the memory location will be
referenced again in the near future. Spatial Locality If a memory
location is referenced, it is very likely that a nearby memory location will
also be referenced in the near future. Consider a
program that spends much of its time executing loops of some type, or the
inner portions of loop nests. These loops usually contain only a few hundred
bytes of code. So, although the machine may have many megabytes of main
memory, a very small portion of that memory is actually accessed during a
given period of time. Furthermore that small portion of memory is accessed
repeatedly. Now consider the
data references that might be made in these program loops. There will
probably be some references to local variables or loop control variables. As
with the instructions of a loop, these variables are repeatedly accessed as
the loop is being executed. The data items that vary with each iteration of a
loop are often elements of arrays that are processed serially. While each
element may not be referenced many times, a reference to one element
guarantees that adjacent elements will be referenced. It makes sense to
bring a data item into the cache because temporal locality implies that it
will be referenced again soon. On the first reference, a delay will be
experienced because the data item must be gotten from the main memory. Once
in the cache, subsequent references will result in a faster response. Because
of spatial locality, when a data item must be brought into the cache, it
makes sense to not only get that item from memory, but to also get data from
nearby memory locations. Spatial locality
is embodied in a cache design by grouping sequential bytes of memory into a
single cache line:
Fig. Cache and
Memory Information
transfer between the cache and the memory is in terms of complete cache
lines, rather than individual bytes. Thus if the program needs a particular
byte, the entire cache line containing that byte is obtained from the memory.
For example, suppose that the cache of Figure 2 was being used and the
program fetches the word (two bytes) at location 0004736. If none of the
cache lines contain the 16 bytes stored in addresses 0004730 through 000473F,
then these 16 bytes are transferred from the memory to one of the cache
lines. Because of the spatial locality of the program, we expect that other
values in the cache line thus loaded will be referenced in the near future. Figure shows that
the memory is considered to consist of 16-byte blocks, each beginning at an
address divisible by 16. Any one of these blocks could be loaded into any one
of the 512 lines of the cache. Thus, in order to handle memory requests
correctly, the system needs to know which block is loaded into each cache
line at each instant of time. Moreover, this information needs to be made
available in hardware, because the cache is controlled entirely by hardware.
|
|
Unit-03/Lecture-5 |
||||||||
|
Cache Memory Mappings • Again cache
memory is a small and fast memory between CPU and main memory • A block of
words have to be brought in and out of the cache memory continuously • Performance of
the cache memory mapping function is key to the speed • There are a
number of mapping techniques – Direct mapping – Associative
mapping – Set associative
– mapping Direct mapping
·
Associative
memories are expensive compared to random-access memories because of the
added logic associated with each cell. The possibility of using a
random-access memory for the cache is investigated. The CPU address of 15
bits is divided into two fields. ·
The
nine least significant bits constitute the index field and the
remaining six bits form the tag field. The figure shows that main
memory needs an address that includes both the tag and the index bits. ·
The
number of bits in the index field is equal to the number of address bits
required to access the cache memory. ·
In the
general case, there are 2k words in cache memory and 2n words in main memory. ·
The n-bit
memory address is divided into two fields: k bits for the index field
and n – k bits for the tag field. ·
The
direct mapping cache organization uses the n-bit address to access the
main memory and the k-bit index to access the cache. Each word in
cache consists of the data word and its associated tag. ·
When a
new word is first brought into the cache, the tag bits are stored alongside
the data bits. ·
When
the CPU generates a memory request, the index field is used for the address
to access the cache. ·
The
tag field of the CPU address is compared with the tag in the word read
from the cache. ·
If the
two tags match, there is a hit and the desired data word is in cache. ·
If
there is no match, there is a miss and the required word is read from main
memory. ·
It is
then stored in the cache together with the new tag, replacing the previous
value. ·
The
disadvantage of direct mapping is that the hit ratio can drop considerably if
two or more words whose addresses have the same index but different tags are
accessed repeatedly. Associative Mapping
Fig: Associative Mapping ·
The
fastest and most flexible cache organization uses an associative memory. ·
This
organization is illustrated. ·
The
associative memory stores both the address and content (data) of the memory
word. ·
This
permits any location in cache to store any word from main memory. ·
The
diagram shows three words presently stored in the cache. ·
The
address value of 15 bits is shown as a five-digit octal ·
Associative
mapping cache (all numbers in octal) number and its corresponding 12-bit word
is shown as a four-digit octal number. ·
A CPU
address of 15 bits is placed in the argument register and the associative
memory is searched for a matching address. ·
If the
address is found, the corresponding 12-bit data is read and sent to the CPU. ·
If no
match occurs, the main memory is accessed for the word. ·
The
address-data pair is then transferred to the associative cache memory. ·
If the
cache is full, an address-data pair must be displaced to make room for a pair
that is needed and not presently in the cache. The decision as to what pair
is replaced is determined from the replacement algorithm that the designer
chooses for the cache. ·
A
simple procedure is to replace cells of the cache in round-robin order
whenever a new word is requested from main memory. This constitutes a
first-in first-out (FIFO) replacement policy. 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. ·
A
third type of cache organization, called set-associative mapping, is an
improvement over the direct-mapping organization in that each word of cache
can store two or more words of memory under the same index address. ·
Each
data word is stored together with its tag and the number of tag-data items in
one word of cache is said to form a set. ·
An
example of a set-associative cache organization for a set size of two is
shown. ·
Each
index address refers to two data words and their associated tags. ·
Each
tag requires six bits and each data words has 12 bits, so the word length is
2(6+12) = 36 bits. ·
An
index address of nine bits can accommodate 512 words. ·
Thus
the size of cache memory is 512 x 36. ·
It can
accommodate 1024 words of main memory since each word of cache contains two
data words. In general, a set-associative cache of set size K will
accommodate k words of main memory in each word of cache. ·
When a
miss occurs in a set-associative cache and the set is full, it is necessary
to replace one of the tag-data items with new value. ·
The most
common replacement algorithms used are: FIFO and LRU. The FIFO procedure
selects for replacement the item that has been in the set the longest. The
LRU algorithm selects for replacement the items that have been least recently
used by the CPU. Both FIFO and LRU can be implemented by adding a few extra
bits in each word of cache.
Fig: Set-Associative mapping
|
|
Unit-03/Lecture-6 |
||||||||
|
Associative
Memory ·
Accessed by the content of the data rather than by an address. ·
Also called Content Addressable
Memory (CAM). ·
When word is written to CAM, no
address is needed; next available unused
storage location is located. ·
When word is read from CAM, the content of word or part of it is
specified, the memory locates all words which give match and marks them for
reading. ·
Associative memories are expensive and used for application where time
search is critical.
Fig:
Block diagram of Associative memory Block Diagram
consists:- ·
Content-addressed or associative memory refers to a memory
organization in which the memory is accessed by its content (as opposed to an
explicit address). Thus, reference clues are "associated" with
actual memory contents until a desirable match (or set of matches) is found. Production
systems
are obvious examples of systems that employ such a memory. ·
Associative memory stands as the most likely model for cognitive
memories, as well. Humans retrieve information best when it can be linked to
other related information. This linking is fast, direct and labyrinthian in
the sense that the memory map is many-to-many and homomorphic. ·
Unlike standard computer memory (random access memory or RAM) in which the user supplies a
memory address and the RAM returns the data word stored at that address, a
CAM is designed such that the user supplies a data word and the CAM searches
its entire memory to see if that data word is stored anywhere in it. If the
data word is found, the CAM returns a list of one or more storage addresses
where the word was found (and in some architectures, it also returns the data
word,
or other associated pieces of data). Thus, a CAM is the hardware embodiment
of what in software terms would be called an associative array. The data word recognition unit was
proposed by Dudley Allen Buck in 1955. A major interface definition for CAMs and other network
search engines (NSEs) was specified in
an interoperability agreement called the Look-Aside
Interface (LA-1 and LA-1B)
developed by the Network
Processing Forum, which later merged with
the Optical Internetworking Forum
(OIF). Numerous devices have been produced by Integrated Device Technology,
Cypress
Semiconductor, IBM,
Broadcom
and others to the LA interface agreement. On December 11, 2007, the OIF
published the serial lookaside (SLA) interface agreement. Semiconductor
implementations Because a CAM is designed to search its entire memory
in a single operation, it is much faster than RAM in virtually all search
applications. There are cost disadvantages to CAM however. Unlike a RAM chip,
which has simple storage cells, each individual memory bit
in a fully parallel CAM must have its own associated comparison circuit to
detect a match between the stored bit and the input bit. Additionally, match
outputs from each cell in the data word must be combined to yield a complete
data word match signal. The additional circuitry increases the physical size
of the CAM chip which increases manufacturing cost. The extra circuitry also
increases power dissipation since every comparison circuit is active on every
clock cycle. Consequently, CAM is only used in specialized applications where
searching speed cannot be accomplished using a less costly method. One successful
early implementation was a General Purpose Associative Processor IC and
System.[4] Alternative
implementations To achieve a different balance between speed, memory
size and cost, some implementations emulate the function of CAM by using
standard tree search or hashing designs in hardware, using hardware tricks
like replication or pipelining to speed up effective performance. These
designs are often used in routers. An alternative approach to implementation is based on
Superimposed Code Words or Field Encoded Words which are used for more
efficient database operations, information retrieval and logic programming,
with hardware implementations based on both RAM and head-monitoring disk
technology.[5][6] Ternary CAMs Binary
CAM is the simplest type of CAM which uses
data search words consisting entirely of 1s and 0s. Ternary
CAM (TCAM) allows a third matching state of
"X" or "don't care" for one or more bits in the stored
dataword, thus adding flexibility to the search. For example, a ternary CAM might
have a stored word of "10XX0" which will match any of the four
search words "10000", "10010", "10100", or
"10110". The added search flexibility comes at an additional cost
over binary CAM as the internal memory cell must now encode three possible
states instead of the two of binary CAM. This additional state is typically
implemented by adding a mask bit ("care" or "don't care"
bit) to every memory cell. Holographic associative memory
provides a mathematical model for "don't care" integrated
associative recollection using complex valued representation. Example applications Content-addressable memory is often used in computer
networking devices. For example, when a network switch
receives a data frame
from one of its ports, it updates an internal table with the frame's source MAC address
and the port it was received on. It then looks up the destination MAC address
in the table to determine what port the frame needs to be forwarded to, and
sends it out on that port. The MAC address table is usually implemented with
a binary CAM so the destination port can be found very quickly, reducing the
switch's latency. Ternary CAMs are often used in network routers,
where each address has two parts: the network address, which can vary in size
depending on the subnet
configuration, and the host address, which occupies the remaining bits. Each
subnet has a network mask that specifies which bits of the address are the
network address and which bits are the host address. Routing
is done by consulting a routing table maintained by the router which contains
each known destination network address, the associated network mask, and the
information needed to route packets to that destination. Without CAM, the
router compares the destination address of the packet to be routed with each
entry in the routing table, performing a logical
AND with the network mask and comparing it
with the network address. If they are equal, the corresponding routing
information is used to forward the packet. Using a ternary CAM for the routing
table makes the lookup process very efficient. The addresses are stored using
"don't care" for the host part of the address, so looking up the
destination address in the CAM immediately retrieves the correct routing
entry; both the masking and comparison are done by the CAM hardware. Other CAM applications include: ·
CPU fully associative cache controllers
and translation lookaside buffers ·
Database
engines ·
Data compression
hardware
|
||||||||
|
Unit-03/Lecture-7 |
||||||||
|
Virtual memory ·
Virtual memory is a memory management technique that is
implemented using both hardware and software. It maps memory addresses used by a program, called virtual addresses, into physical
addresses in computer memory. ·
Main storage as seen by a process or
task appears as a contiguous address space or collection of contiguous segments. ·
The operating system manages virtual address spaces and
the assignment of real memory to virtual memory. Address translation hardware
in the CPU, often referred to as a memory management unit or MMU,
automatically translates virtual addresses to physical addresses. ·
Software within the operating system may extend these
capabilities to provide a virtual address space that can exceed the capacity
of real memory and thus reference more memory than is physically present in
the computer. ·
The primary benefits of virtual memory include freeing
applications from having to manage a shared memory space, increased security
due to memory isolation, and being able to conceptually use more memory than
might be physically available, using the technique of paging. ·
Virtual memory makes application programming easier by
hiding fragmentation of physical memory; by
delegating to the kernel the burden of managing the memory hierarchy (eliminating the need
for the program to handle overlays explicitly); and, when
each process is run in its own dedicated address space, by obviating the need
to relocate program code or to
access memory with relative addressing. ·
Memory virtualization can be considered a generalization
of the concept of virtual memory.
Fig: Virtual Memory •
Virtual memory – permit the user to construct programs as though large
memory space were available, equal to the totality of the auxiliary memory •
An address used by a programmer is Virtual address •
Set of virtual addresses are called address space •
An address in main memory is called a location or physical address •
Set of physical addresses constitute memory space •
Address space > memory space if virtual memory is available. •
Mapping a virtual address –
Virtual address register – stores virtual address – Memory mapping table – to map a virtual
address to a physical address – Main memory address register – stores
physical address –
Address mapping can also be done using pages ·
Mapping table for mapping Virtual address
Address mapping using pages •
Blocks – physical memory is broken down into groups of equal size •
Page – groups of address space of the same size •
Page frame is sometimes used to denote a block •
Memory page table consists of 8 words one for each page •
Address in the page table denotes the page number •
Content of the word gives the block number where that page is stored
in main memory •
Presence bit – indicates whether the page has been transferred from
auxiliary memory into main memory •
3 high order bits of the virtual address specify a page number and an
address for the memory page table.
|
||||||||
|
Unit-03/Lecture-8 |
||||||||
|
Memory
Management Hardware • Basic components include: – Facility for
dynamic storage relocation that maps logical memory references into physical
memory addresses – Provision for
storing common programs stored in memory by different users. – Security against
unauthorized access between users and preventing users from changing OS
functions • Segment – set of logically related instructions or data
elements associated with a given name (address generated by a segmented
program is logical address) • Translation lookaside buffer (TLB) – fast associative
memory used to hold the most recently referenced table entries • Examples of logical and physical addresses
–
Consists of memory array of
m words each of n bits, argument register A and key register K each of n
bits.
|
||||||||
|
Unit-03/Lecture-9 |
||||||||
Positioning
code and addressing memory
We want to have multiple programs loaded in memory at the same time and have the operating system periodically switch the processor's execution state from one process to another. This means that each program will be loaded into different areas of system memory. Since programs use memory addresses for jump instructions and memory references, they need to make sure that the proper address is used no matter where the program is positioned in memory. The most basic approach is that of absolute code, where all addresses are hard-coded into the program and the program knows its starting memory location. For example, the CP/M operating system loaded all programs at the starting address of 0x0100. If we want to place multiple programs in memory at the same time, this becomes problematic since we are not likely to know a priori where the program will be loaded into memory. Another approach is to have the compiler generate position independent code. In this
model, all references to memory that the program uses are relative to either
the current location or to the stack pointer. Any attempt to use absolute
addresses to reference the program's data or instructions must be avoided
since it will yield unpredictable results because, as with absolute code, the
program does not know where it will be loaded into memory. With the gcc compiler, the A compiler can generate code that does not fill in memory references. Instead, it generates a relocation table. In the simplest case, this is a table of byte offsets into the program that represent locations where absolute memory references exist. The program is compiled (or assembled) to assume a base address of 0. When the operating system loads the program, the table is traversed and each memory reference within the program gets the base address of the program added to it. This is known as dynamically relocatable code. Logical Addressing
Fig:Address translation A radically different approach to positioning code in memory is to introduce support into the computer's hardware that will translate any address reference made by the process (the logical address) into its actual location in physical memory (the physical address, or real address). This translation is done as the program executes. A memory management unit, or MMU, is responsible for performing this real-time, on-demand translation between logical and physical addresses. Relocatable
addressing
Fig: Base & limit addressing A direct approach to a hardware solution is to offset each memory reference by a base address — a constant value that represents the starting memory location into which the program was loaded. Now a program can assume that it starts at location 0 (or some other known location). When the operating system loads it into some other region of memory, say location 20000, the operating system would load the base register of the memory management unit with the value 0f 20000. When the program references location 1533, the memory management unit will add the base register to the reference, resulting in a reference to a real memory address of 21533 (20000+1533). To ensure that the program does not access memory outside its range, a test for a limit can be added. This is the total amount of memory that is allocated to the process. If the logical address exceeds this limit, then the memory management unit will generate a trap. Multiple
fixed partitions
Fig:. Multiple Fixed Partitions Getting back to the issue of loading multiple processes into memory at the same time, we can divide memory into multiple fixed partitions (segments). The partitions could be of varying sizes and they would be defined by the system administrator when the system starts up. This was the approach used in IBM System/360's OS/MFT. A new program gets placed on a queue for the smallest partition that can hold it. Any unused space within a partition remains unused. This is internal fragmentation. If any partitions have no programs to run then the memory in that partition is always wasted. This is called external fragmentation. External fragmentation refers to areas of storage that are not allocated and are therefore unused. A modification of the multiple queue approach is to use a single queue. All incoming jobs go on this queue. When a partition is free, the memory manager searches the entire queue for the biggest job for that available partition. If there isn't enough room in the partition, then the operating system will have to move the memory contents into a larger partition (if available) or, if no partition is available, then save the partition contents and processor register state onto some temporary storage on the disk and queue the process until a larger partition becomes available. Variable
Partition Multiprogramming
Given that memory is a highly desirable resource, multiple fixed partitions isn't a desirable approach due to internal fragmentation (programs are rarely a perfect match for the partitions they go into, leading to wasted memory) and due to the problem of deciding what partition sizes to create (lots of small partitions? A few small and a few medium sized ones? A couple of big partitions?). An improvement over multiple fixed partitions is variable partition multiprogramming, where partitions are created dynamically as they are needed and to the size needed.
Figure 5. Variable partition multiprogramming
Figure 6. Holes in variable partition multiprogramming Consider the example in figure 5. As new processes get created, the operating system allocates each process into available memory and is given the exact amount of memory required by the process. As processes exit (figure 6), they create holes: regions of free memory. When new processes get created, the operating system tries to fit a process into an available hole. If a fit is found, it is unlikely that the new process will be the exact same size as the previous one (and it cannot be bigger), so a smaller hole will be left. We can combine the holes (unused memory) by relocating processes down (move process 2 to the top of process 0 and then move process 4 to the top of the relocated process 2). This is known as memory compaction and is usually not done because it takes up too much CPU time. Segmentation
Fig:. Segmentation hardware A variation on variable partition multiprogramming is to allocate each of the components of a process separately (e.g., code, data, heap, stack). This is known as segmentation. By taking this approach, we break up a process into smaller chunks and increase our chances of finding free memory. Certain regions, such as code and static data, will not grow in size and will never have to be reallocated. It's unlikely that the entire process will have to be moved to a larger whole but rather just the heap or stack segments. The offsets are different depending on which segment of the process is being addressed. The memory management unit that handles segmentation has to take this into account. Each process will have a number of segment registers associated with it, one for each region of the process (e.g., code, data, stack). The processor's hardware will need to be designed to select the appropriate register for each type of memory reference. An example of processors that support a segmentation model is the family of Intel processors starting from the 8086 and 8088 and continuing through today's 64-bit systems. Allocation algorithms
If more than one region of memory is able to accommodate a segment (or process), the operating system needs to make a decision on how to pick the best segment. Several approaches are possible. First fit Scan segments of memory until you
find a hole that fits. Break the hole into one segment for the process and
another segment that will be a hole containing the leftover memory. This
algorithm has the advantage of a small search. Next fit This algorithm is just like First
Fit except that it searches from where it left off the previous time (and
then wraps around). In practice it exhibits worse performance than First Fit.
Best fit The Best Fit technique searches the
list for the hole that best fits the process. It’s slower than First Fit
since the entire list must be searched. It also produces tiny holes that are
often useless. Worst fit Since best fit doesn’t perform
well, you would think its inverse would. The Worst
Fit algorithm searches for the largest hole on the assumption
that the hole remaining after allocation will be big enough to be useful. It
also doesn’t yield good performance. Quick fit The Quick Fit algorithm maintains
separate lists for common sizes (e.g. 4K holes, 12K holes, ...). It's fast
but has the drawback that finding neighbors for merging is difficult. Paging is a memory management technique that: ·
does
not let the amount of physical memory limit the size of our process. ·
allows
the process feels like it owns the entire address space of the processor. ·
allows
memory allocation to be non-contiguous and has no external fragmentation
problems, simplifying memory management and obviating any need for
compaction. ·
lets
us keep more processes in memory than the sum of their memory needs so that
we can keep the CPU utilization as high as possible. ·
lets
us us keep just the parts of a process that we're using in memory and the
rest on the disk. If the blocks that we divide memory into are all of equal size, then we have a paging system. If the blocks are of different sizes, then we have a segmentation system. In this section, we will examine how paging works. Implementing this requires a more sophisticated memory management unit architecture in the processor. With paging, we divide physical memory into equal-sized blocks. These are called page frames. A logical address space is also divided into blocks of the same size, called pages. Every memory access is translated from a page to a page frame by the memory management unit. A page may be placed in any available page frame. The memory management unit maps a page to the page frame in which that page resides. The size of each page is constant and is a power of two. Therefore, a fixed number of high bits in the memory reference (virtual address) identifies the page number and a fixed number of lower bits in the address identifies the displacement, or offset.
Fig: Virtual address decomposition For instance, if the page size is 4K bytes, the offset in the page will be 12 bits (log24096 = 12). This means that if we have a 32-bit virtual address, the page field will be 20 bits (32-12), corresponding to 1M pages. An address of 0x00002c37 will correspond to page 2, offset 0xc37. If this isn’t obvious, convert the address to binary. Grab the top 20 bits as the the page number and the bottom 10 as the offset (figure 8). When a process references a virtual address (v=(p,d)), the paging system (the MMU) looks up p in a page table using the page number as the index into this table. The page table is an array of page table entries (PTEs). A page table entry (PTE) for page p in the table contains a page residence bit that indicates whether the page is currently mapped onto a page frame. If it is, a field in the PTE provides the page frame f. The pseudocode for this operation is: f = page_table[p].page
Fig: Page table lookup
Figure 10. Page mapping The physical location of the data in memory is therefore at offset d in page frame f: the address that is the concatenation of f and d (figure 9). If the page is not mapped to a page frame in memory, a page fault occurs (this is a trap to the operating system) and the OS is responsible for either killing the process (in the case of an invalid memory reference), allocating the page or loading the needed page into an empty page frame and then restarting the faulting instruction. Because any page can be mapped into any page frame, there is no need to allocate memory contiguously. Any available page frame can be used for any page and the page table keeps the mapping, providing the illusion of one contiguous block of memory . Within the memory management hardware, associative memory is used to construct the translation lookaside buffer, or TLB. Each entry in the TLB contains the information that would be found in a page table as well as the page number (which is used as the query key). Every entry in the TLB is compared with the key (the page number that we are looking up) simultaneously. This approach is known as associative mapping. The hope with the TLB is that a large percentage of the pages we seek will be found in the TLB. The percent of references that can be satisfied with a TLB lookup is called the hit ratio. A hit ratio close to 100% means that almost every memory reference is translated by associative memory. Ideally, the TLB will be designed to be fast enough to allow the CPU to do the logical-to-physical memory translation as well as the corresponding real memory read/write operation in one memory access so that the MMU does not create a performance penalty. Unlike normal cache memory, the TLB is built into the MMU and caches individual table entries rather than a set of arbitrary memory locations. If a page is not in the TLB, then the MMU detects a cache miss and performs an ordinary page lookup (referencing the memory-resident page table). In doing so, one entry is removed from the TLB and replaced by the entry that was just looked up so that the next reference to that same page will result in a TLB hit. Memory protection and statistics
In addition to managing logical-to-physical memory page translations, each page table entry can contain fields for additional information, allowing the management unit to enforce memory access permissions and track memory access. Some common elements in a page table include: ·
valid/invalid:
(residence bit) is there a page frame mapped to this region of memory? ·
read-only:
is the process allowed to write to this page? ·
execute:
is the process allowed to execute code from this page? ·
dirty:
has the page been modified since the bit was cleared? ·
accessed:
has the page been accessed since the bit was cleared? This can help us decide
if a page is still being actively referenced. Multilevel page tables
Fig: Per-process memory map Virtual memory allows each process to have its own private address space. The page table for the process maps memory references from this virtual private address space onto page frames in real memory. Because a process can conceivably access any memory location in its address space, the page table has to be big enough to cover every page within that space, whether that page is actually mapped to real memory or not. As we saw earlier, a 32-but system with 4 KB pages means that we have 20-bit pages and, therefore, a 20-bit index into the page table. This means that the page table needs to have 1,048,576 (220) entries. Even if we skimp on extra flags and assume that each entry is only 24 bits, the page table now consumes 3 MB per process (with a 64-bit address space, each page table will consume approximately 28,672 TB!).
Fig: Multilevel page table The vast bulk of processes use only a very small part of their address space, although the regions that are used may be scattered. For example, the stack may be at a different end of memory than the text and heap. It's a waste to maintain an entire page table since large regions of it will be unused and empty. To optimize memory use for a sparse page table, we can arrange the page table in a hierarchy (figure 13). The virtual address is divided into three parts (figure 13). The high-order bits index into a top-level page table (index table). This table contains the base address of a partial page table: the pages that contain those high-order bits. The middle-bits are an offset into this partial page table. This partial page table contains page table entries. If a large-enough region of memory is not used, then the partial page tables for those regions don't need to be created and the corresponding entries in the index table can indicate that there is no valid mapping. Inverted page tables
The hierarchical approach helps to deal with large address spaces. The hierarchy can be extended to additional layers (e.g., a three-level or even a four-level page table) at the cost of an extra memory read per table lookup. A four-level page table will require four memory reads just to find the page translation and then one more memory access for the actual read/write operation. This effectively makes memory access five times slower whenever there's a cache miss. With a large address space, the potential number of pages is huge with a larger address space (e.g., 64 bit). The number of page frames, however, is more manageable since it is limited by the physical memory on a system. We can design a paging system that is indexed by page frames such that the ith entry into an inverted page table contains information on the contents of page frame i. The number of entries in such a table will always be equal to the number of page frames on the system and will be independent of the virtual address space or the number of processes. The problem is that it is expensive to search through such a table since there is no direct index onto the desired entry; we only know the page number but the table is indexed by page frames. By using a hash table, we can achieve an access time that is much better than linear search through the table. Moreover, we can couple this inverted page table with a TLB as we did with with page tables to gain the benefits of cached entries for frequently accessed pages. Inverted page tables are not used on today's x86-64, Intel 32-bit, or ARM architectures but have been used on systems such as the IBM System/38, PowerPC, Intel Itanium, and UltraSPARC. Logical and physical addressing
modes
Most processors support operation in two modes: virtual addressing mode, which uses address translation through the memory management unit, and physical addressing mode, which bypasses the MMU. In this latter mode, every memory reference is a reference to the actual physical memory location in the memory system. Upon power-on, a CPU will start up in physical addressing mode since page tables have not been set up yet. The system will usually remain in physical addressing mode while the operating system is loaded and run to initialize the page table. The operating system will then switch the processor to virtual addressing mode. The
Buddy System
The buddy system is a memory allocation and management algorithm that manages memory in power of two increments. This brief discussion presents only the basic buddy algorithm; there are a number of variations on it. lists of blocks of free chunks of memory. A memory manager (e.g., the Linux page allocator) using the Buddy System keeps lists of free blocks that are sizes of powers of two (2, 4, 8, 16, 32, …). Initially, when all of memory is free, all lists are empty except for the largest power of two that is less than or equal to the size of allocatable memory. When a block of size n is needed, the algorithm checks the list for the nearest power of two that is greater than or equal to n. If there is one, all is well and the block can be marked as used. If there is no free block, the algorithm gets a block from the next level, splits it into two buddies (which get recorded in the previous level of the list), and uses one of those for allocation. When that block is freed again, the buddies can be combined and brought back up to the next level in the list. If the next level in the list does not have an available block, the process is repeated with successively bigger-sized blocks in the list. For example, suppose we're using a buddy-based page allocator and need a block of 53 contiguous pages. The closest bigger power of two is 64, so we request a 64-page chuck. Suppose that all we have is one free 512-page segment. We have an array of pointers to lists: a 512-page list, a 256-page list, etc., down to a 1-page list. The algorithm starts off by looking looks for a 64-page segment. That list is empty, so it then attempts to get a 128-page segment that it can split into two 64-page buddies. That doesn't exist either, so we then look for a 256-page segment. We don't have it, so we then look for a 512-page segment. We have one of those and split it into two 256-page buddies. Now we back up and look for the 256-page segment that we couldn't find earlier. Now we have two of those. We grab one and split it into two 128-page buddies. We back up further and look for that 128-page segment. We have two of those now and split one into two 64-page segments. We back up further to our initial search for a 64-page segment and, lo and behold, we have one we can allocate. When a segment is freed, the algorithm checks to see whether the segment's buddy is free as well. If it is, then the two buddies are combined into a single free segment. The process is repeated for progressively bigger segments until there are no more buddies to consolidate. This algorithm is fast and makes merging very easy. Unfortunately, because it requires all allocation units to be powers of two, it is wasteful of memory since it can lead to internal fragmentation. Recall that unused memory within an allocation unit is known as internal fragmentation and unused memory between allocation units is known as external fragmentation.
|
