MESSAGE
| DATE | 2014-12-02 |
| FROM | Ruben Safir
|
| SUBJECT | Subject: [NYLXS - HANGOUT] Notes on Memory Cache and Internal Memory
|
From owner-hangout-outgoing-at-mrbrklyn.com Tue Dec 2 01:16:57 2014
Return-Path:
X-Original-To: archive-at-mrbrklyn.com
Delivered-To: archive-at-mrbrklyn.com
Received: by mrbrklyn.com (Postfix)
id C8249161273; Tue, 2 Dec 2014 01:16:56 -0500 (EST)
Delivered-To: hangout-outgoing-at-mrbrklyn.com
Received: by mrbrklyn.com (Postfix, from userid 28)
id AF3DF161278; Tue, 2 Dec 2014 01:16:56 -0500 (EST)
Delivered-To: hangout-at-nylxs.com
Received: from mailbackend.panix.com (mailbackend.panix.com [166.84.1.89])
by mrbrklyn.com (Postfix) with ESMTP id A48E2161273
for ; Tue, 2 Dec 2014 01:16:55 -0500 (EST)
Received: from panix2.panix.com (panix2.panix.com [166.84.1.2])
by mailbackend.panix.com (Postfix) with ESMTP id 3186F143D1
for ; Tue, 2 Dec 2014 01:16:54 -0500 (EST)
Received: by panix2.panix.com (Postfix, from userid 20529)
id 166BF33CC5; Tue, 2 Dec 2014 01:16:54 -0500 (EST)
Date: Tue, 2 Dec 2014 01:16:53 -0500
From: Ruben Safir
To: hangout-at-nylxs.com
Subject: [NYLXS - HANGOUT] Notes on Memory Cache and Internal Memory
Message-ID: <20141202061653.GA9247-at-panix.com>
MIME-Version: 1.0
Content-Type: multipart/mixed; boundary="+QahgC5+KEYLbs62"
Content-Disposition: inline
User-Agent: Mutt/1.5.23 (2014-03-12)
Sender: owner-hangout-at-mrbrklyn.com
Precedence: bulk
Reply-To: hangout-at-mrbrklyn.com
--+QahgC5+KEYLbs62
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
http://www.nylxs.com/docs/grad_school/arch/memory_notes.txt.html
This is fairly complete and should benifit anyone interested in a topic
that you deal with all the time
The inteplay between a CPU and system memory
--+QahgC5+KEYLbs62
Content-Type: text/plain; charset=us-ascii
Content-Disposition: attachment; filename="memory_notes.txt"
6.0 Computer Memory
6.01 Location:
6.011 internal
6.0111 Main Memory
6.0112 Registers: Processor Local Memory
6.0113 Control Unit Memory
6.0114 Cache
6.012 external
6.0121 Peripheral Storage Devices
6.01212 Tapes and Disks
6.0122 Availble through I/O controllers
6.02 Capacity:
6.021 Bits
6.022 Bytes
6.023 Words (8,16,32 and 64 bits)
6.03 Units of Tranfer:
6.031 Equal to the number of lines in and out of the memory device
6.032 May be equal to a word or larger (64, 128, 256)
6.033 Main Memory: The Number of bits read/write into
memory at a single time.
6.034 External: Often transfered in units larger than a
word, such as a block.
6.04 Addressable Units: Usually a Word size but some units
allow for Byte Size addressing
6.041 The relationship between length in bits A of an
address and the number of addressable units:
2A = N <==============================What?
6.1 Memory Access:
6.11 Methods:
Sequential
Direct
Random
Associative
6.12 Sequenction Access:
.121 Memory organzed into Record Units
.122 Access is linear
.123 Addressing Information is stored to make
Record Accessing easier
.124 Shared Read/Write Mechanism is used
.125 Access requires moving through records to
find what you want to use for R/W
.126 Example: Backup Tapes
6.13 Direct Access:
.131 Shared Access (R/W) mechanism (similar to
sequntial)
.132 Block or Records have unique Addresses
based on physical location
.133 Direct Acces to the area of the storage and
then sequential counting to find the exact data
location
.134 Variable Access Time
.135 Example: Disk Units
6.14 Random Access:
.141 Each Memory Unit has a specific, unique, wired address
.142 Time to access each location is independent
of previous memory access and access is fairly
constant
.143 Example: Main Memory and certain cache.
6.15 Associative Access:
.151 A type of random access
.152 enables one to make a comparison of desired bit
locations within a word for a specified match
.153 Does this for all Words simulatenously
.154 A word is retrieved based on its content,
rather than its address.
.155 Retrieval Time contastant - Each location
has its own addressing location
.156 Examples: Some Cache memories
6.2 Memory Charactoristics:
6.21 Capacity
6.22 Performance
.221 Access Time: The Time it takes to perform
an individual R/W
.222 Memory Cycle Time: System Bus dependent
time where the a R/W can start after one
completes.
.2221 Most a Random Access Memory Issue
.223 Transfer Rate: The rate in which data can
transfer in and out of a memory unit
6.3 Physical Memory Types:
6.31 Semiconductor
.311 Volatile or NonVolatile
6.32 Magnetic Surface
.321 NonVolatile
6.33 Optical
6.34 Magneto-Optical
6.35 Memory Physical Properties:
6.351 Volatile: Leaks Memory and Disapates when
powered down.
6.352 NonVolatile: Memory remains once stored
until deliberately changed
6.353 Nonerasable: ROM in Semiconductor Material
6.354 Organization Design - Especially for RAM
is essential to its use and description. How
the bits and words are translated in physical
memory.
6.4 Memory Heirachy: Traditional memory design where the
fastest and most expensive form of memory is close to the
processor and less expensive and larger memory resources are
further off the system core.
6.41 Locality of reference: The theory that areas of
memory, over the short period of time, is more intensly
used than outside clusters of memory. This gives
advantage to a system of memory movement where the
system cashes clusters of memory for processing usage.
6.42 Inboard Memory:
6.421 Registers, Cache, Main Memory
6.43 Outboard Storage:
6.431 Magnetic Disk, Optical Disks, etc
6.44 Offline Storage:
6.441 BAckup Tapes
Heirarchy
-----------
Register
Cache
Main Memory
Magnetic Disk
Tape
6.5 Memory Caching Technique
CPU <====> Cache <====> Main Memory
fast slow
CPU <==> L1 <==> L2 <==> L3 <==> Main Memory
Fastest Fast Less Slow
Fast
6.51 Each Cache location would have a numer of memory
words at a single location.
6.511 Processor generates a read address
6.512 Check if the address is in the block
contained in the cache.
.5121 If it is in the cache block,
return the data for the address
.51212 If that address is not in any of
the blocks in the cache, retrieve the
block with the address. The cache then
send the data on to the CPU
.51213 Alternatively, the Data and
Address lines can be connected from the
CPU to the Main Memory and the Cache in
parallel. This gives the advantage that
when you have a cache miss, the cache
can call for the memory and it enters
the cache and the CPU registers
simultaneously.
http://www.nylxs.com/docs/grad_school/arch/cache_memory_parellel.png
.512131 Parallel Control
When a memory address is listed in the
cache in a parallel architecture, then
the cache, which has the control line
between the system bus and the
processor, turns off access to the
system bus, preventing traffic on the
bus.
6.52 Elements of Cache Design:
6.521 Addressing: Logical or Physical
6.5211 Virtual Memory -
Hardware Memory Management
Module translates virtual
addresses for real physical
address.
6.52111 MMU - Memory
Management Unit: Can
sit between cache and
the processor or between
cache and the system
bus.
6.52112 Logical
Addressing: Cache is
between the and the MMU
521121: No MMU access for cache
hits (good)
521122: Addresses not unique
and therefor, the cache must be
flushed clean between
application switches or extra
bits need to be added to the
address to specify the virtual
process running the virtual
memory
6.522 Cache Size
6.523 Mapping Function:
The Memory is larger than the
cache so in order to reach all
memory locations, an algorithm
must be constructed
.5231 Direct - Maps each memory
address to a single possible
cache line in a box of cache.
http://www.nylxs.com/docs/grad_school/arch/direct_cache_model.png
.52311 TIO - Tag, Index, Offset
111: Memory Map of the
memory address which
might be requested by a
CPU an mapped to a Cache.
__________________________________________________________
| TAG | Index |Offset |
|___________________|______________________________|_______|
112: Example:
Consider a machine with a byte addressable main memory of 2^16 bytes
and block size of 8 bytes. Assume that a direct mapped cache consisting
of 32 lines is used with this machine.
Memory is addressed with 16 bits. 16 bits is 2^16 individual possible
addresses.
Since a block is 8 bytes, and a byte is a word, then 3 bits address the
offset (2^3).
Since there are 32 lines in each cache then 2^5 or 5 bits address the
index.
That leaves 8 bits for the tag. Note that this does NOT include the
data at the memory address.
Suppose the byte with address 0001 1010 0001 1010 is stored in the
cache. What are the addresses of the other bytes stored along with
it?
1) The first eight are the tag: 0001 1010 : In any line you can
have ANY tag
2) The next 5 are the INDEX: 00011: All the words/btyes of this index
are in the cache: This includes address of offset 001 -> 111
0001 1010 0001 1000
0001 1010 0001 1001
0001 1010 0001 1010
0001 1010 0001 1011
0001 1010 0001 1100
0001 1010 0001 1101
0001 1010 0001 1110
0001 1010 0001 1111
How many total bytes of memory can be stored in the cache? Why is the tag also stored in the cache?
32 x 8 bytes of **data** 2^8 bytes = 256 btyes. The tag is stored in
order to differential between matching 32 blocks of memory segments.
.5232 Associative -
21 Any Memory
block can be
assigned to any
cache line
22 An address is
interpreted as a TAG and
WORD field
223 Each tag
represents a
block of memory
224 Every tag in
the cache has to
be examined for
a match
.225 Address
Length is s+ w
bits (there is
no index or r)
.226 Number of
Addresses is
2^(s+w)
.227 Block Size
of data
is a cash line
size with is in
our example 2^W
or bytes
.228 Total
Blocks in Main
Memory:
2^(s + w)
--------- =
2^w
2^s which is the
number of tags
23 Every line is looked
for a matching tag as
the currently requested memory
address in order to
determine if it is in
the cache or not
.5233 Set Associative - A little bit of
each of the above in an effort
to reduce their disadvantages.
52331 Cache is a number of
sets
52332 Each set a number of
lines
52333 A given line maps into
any line of a given set
52334 As with associative
mapping, each word maps into
multiple cache lines. For
set-associative mapping, each
word maps into all the cache
lines in a specific set, so
that main memory block B0 maps
into set 0, and so on. Thus,
the set-associative cache can
be physically implemented
as n associative caches. It
is also possible to implement
the set-associative cache as
k direct mapping caches
52334
Where i = the cache set number
j = the main memory block
number
m = the number of lines
in cache
v = number of sets
k = number of lines per
set then:
m = v*k (the number of
sets by the size of each
set)
i = j%v (the cache set
number is the remainder
from the main memory
block number divided by
the number of sets in
cache)
Example:
__________________________j________________________
| |
____________________________________________________________________
| Tag | Set (i) |WordOffset|
|______|________________________________________________|__________|
9bits 13 bits 2 bits
If this is a 2way associative set cache (two lines per set)
In this case there are 2^13 SETS which are numbered 0x0000 => 0x1FFF
Tags are associated with the higher order main memory locations and
assigned to a set with the 32 bits of data. The word is an offest of
the data which (which is a memory block of 4 bytes in this case).
6.524 Replacement Algorithm - For
Associate and Set-Associate caching and
DECISION has to be made on which or
several possible memories need to be
bumped. This is the purpose of
hardware implemented replacement
algorithms.
.5241 Least Recently Used (LRU)
LRU implemention for a fully
associative cache. The cache
mechanism maintains a separate
list of indexes to all the lines
in the cache. When a line is
referenced, it moves to the front
of the list. For replacement,
the line at the back of the list
is used.
.52412
.5242 First in First Out (FIFO)
.5243 Least Frequently Used
(LFU)
.5244 Random
6.525 Write Policy
.5251 Write Through - All
writes to Cache are also
written to main memory (then
what is the point?)
52511 Bus watching with write
through: All cache devices
watch the bus for changes
and all write through to
memory.
.5252 Write Back - updates only
in cache.
.52521 Parts of Main Memory
are then invalid and I/O
modules using DME can be
working on invalid data.
6.526 Line Size - the size of the line
determines that size of the block of
main memory is stored within cache.
Large blocks have more hits but reduce
the number of cache lines and cause more
memory to be swapped in and out,
reducing hit rates. So there is a sweet
spot on line size.
6.527 Victim Cache - On write to the
Cache, a preexisting line is moved to a
small cache between the L1 Direct cache
and the next level.
.5271 Reduces the 'cost' of a
miss in the cache
.5272 Victims Cache needs to be
fully associative: it
can't be direct memory..you
don't know what is being
victimized
.5273 Usually 4-16 lines of
cache
6.528 Multilevel Caches: Modern systems
are far more complex than these simple
modules and leverage SDRAM and Chipside
caching in a multilevel scheme of L1, L2
and even L3 levels of cache.
.5281 Internal Cache is
designated L1 and does not use
the system bus.
.5282 External Cache is
designated L2
6.529 Unified or Split function Cache:
Split is perhaps implemented as 2 L1 caches, one
for Instructions and one for Data.
.5291 - Unified might have more hit
rates.
.5292 - Split cache can allow for more
pipelining and prevents contention at
the FECHEX level
.52921 - Processor can fetch a
block of instructions at one
time and wait for the execution
and decoding cycle to function
at its pace using the separate
data cache for data.
Note - there is a segment on the
specifics of the Pentium 4 and Arm
Processor on caching within the chapter
that might be worth reviewing. As of
2014CE though, much of it is old news.
--+QahgC5+KEYLbs62--
|
|
