Associative memory
What is associative memory in computer organization
and architecture?
·
Is also known as
o
content addressable memory(CAM) or
o
associative storage or
o
associative array
·
is a hardware search engines, a special type of computer memory used in certain
very high searching applications
·
are
composed of conventional semiconductor memory (usually SRAM) with added comparison circuitry that enable a search
operation to complete in a single clock cycle.
·
is
a special type of memory that is optimized for performing searches through data, as opposed to providing a simple
direct access to the data based on an address.
·
The two most common search-intensive tasks that use CAMs are
o packet forwarding and
o
packet classification in Internet routers.
·
A data-storage device in which a location is identified by its
informational content rather than by names, addresses, or relative positions,
and from which the data may be taken
·
Is a content-addressable structure that allows
o
maps a set of input patterns to a set of output patterns stored in
memory.
the process of transferring of data from main memory to cache is referred as
mapping function,
o
the recall of data based on the degree
of similarity between the input patterns stored in memory.
·
There are 2 types of associative memory
o
Auto-associative
o
Hetero-associative
·
Auto-associative memory takes
back(retrieves) a previously stored pattern that most closely resembles the
current pattern.
·
Hetero-associative memory, the retrieved
pattern is in general, different from the input pattern not only in content but
possibly also in type and format.
·
Neutral networks are used to implement
these associative memory models called NAM (Neutral associative memory).
Notes
ü Static
random-access memory (SRAM)
is a type of semiconductor memory
that uses bistable latching circuitry to store each bit.
ü SRAM
exhibits data remanence, but is still volatile in the conventional sense that data is eventually lost
when the memory is not powered.
Example:
Associative Memory
The figure below shows a memory
containing names of several people.
If the given memory is
content-addressable, then using the
erroneous(wrong) string “Crhistine Cullen” as key is sufficient to retrieve the
correct name “Christine Cullen. ”
So this type of memory is robust
and fault-tolerant, because this type of memory exhibits some form of
error-correction capability.
Where is Associative
memory used?
·
We are only using this
associative memory in memory allocation format
and it is widely used in database management systems etc...
Advantages
of Associative Memory
·
This is suitable for parallel searches.
It is also used where search time needs to be short
·
Associative memory is often used to
speed up databases, in neural networks and in the page tables used by the
virtual memory of modern computers.
·
CAM-design challenge is to reduce power
consumption associated with the large amount of parallel active circuitry,
without sacrificing speed or memory density
·
considerably facilitates
the programming and solution of informational-logical problems and accelerates
by hundreds (thousands) of times the speed of retrieval, analysis,
classification, and processing of data.
Disadvantages
of Associative Memory
·
It is expensive than RAM, as each cell
must have storage capability and logical circuits for matching its content with
external argument
Associative
memory Vs Random access memory (RAM)
·
In RAM, the user supplies a memory address and the RAM returns
the data word stored at that address
·
In associative memory, the user supplies a data word and the associative memory searches its
entire memory to see if that data word is stored anywhere in it.
·
If the data
word is found, the associative memory returns a list of one or more storage
addresses where the word was found
·
hardware of associative memory allows
operations to occur in a single-clock cycle, as opposed to the much greater
time required for an algorithmic based search through traditional RAM.
·
is
a special type of memory that is optimized for performing searches through
data, as opposed to providing a simple direct access to the data based on an
address as in RAM.
Relationships between RAM and Associative memory
Associative Memory
in Routers
·
A simple network with three
routers.
·
The use of associative memories
in high-end routers reduces the lookup time by allowing a search to be
performed in a single operation.
·
The search is based on
the destination address, rather than the physical memory address.
·
Access methods for this
memory have been standardized into an interface interoperability agreement by
the Network Processing Forum.
The application of
address lookup in Internet routers
·
Internet routers forward
data packets from an incoming port using an address lookup function
·
The address lookup
function examines the packet's destination address and chooses an output port
associated with that address.
·
The router's list of
destination addresses and their corresponding output ports is called the
routing table.
·
An example of a
simplified routing table is displayed in Table 1.
·
All four entries in the
table 1 are 5-bit words, with the don't care bit, X,
matching both a 0 and a 1 in that position.
·
Because of the X bits,
the first three entries in Table 1 represent a range of input addresses,
i.e. the entry on Line 1 indicates that all addresses in the range of 101002—101112 are
forwarded to port A.
·
The router searches for
the destination address of each incoming packet in the address lookup table to
find the appropriate output port.
·
For example, if the
router receives a packet with the incoming address 01101, the address lookup
matches both Line 2 and Line 3 in the table.
·
Line 2 is selected since it has the most
defined bits, indicating it is the most direct route to the destination.
·
This lookup style is
called longest-prefix matching and is required to implement the most recent
Internet Protocol (IP) networking standard.
·
The CAM contains the
routing table from Table 1 to illustrate how a CAM implements address
lookup.
There are two basic forms of Associative Memory(CAM):
o
Binary
Binary CAMs support storage and searching of
binary bits, zero or one (0,1).
o
Ternary.
o
Ternary CAMs support
storing of zero, one, or don't care bit (0,1,X).
o
Ternary CAMs are
presently the dominant CAM since longest-prefix routing is the Internet
standard.
o
Figure 1 shows a
block diagram of a simplified 4 x 5 bit ternary CAM with a NOR-based
architecture.
o
The CAM core cells are
arranged into four horizontal words, each five bits long.
o
Core cells contain both
storage and comparison circuitry.
o
The search lines run
vertically in the figure and broadcast the search data to the
CAM cells.
o
The matchlines run
horizontally across the array and indicate whether the search data matches the
row's word.
o
An activated matchline
indicates a match and a deactivated matchline indicates a non-match, called amismatch in
the CAM literature.
o
The matchlines are
inputs to an encoder that generates the address corresponding to the match
location.
o
A CAM search operation
begins with precharging all matchlines high, putting them all temporarily in
the match state.
o
Next, the search line
drivers broadcast the search data, 01101 in the figure, onto the search lines.
o
Then each CAM core cell
compares its stored bit against the bit on its corresponding search lines.
o
Cells with matching data
do not affect the matchline but cells with a mismatch pull down the matchline.
o
Cells storing an X operate as
if a match has occurred. The aggregate result is that matchlines are pulled
down for any word that has at least one mismatch.
o
All other matchlines
remain activated (precharged high). In the figure, the two middle matchlines remain
activated, indicating a match, while the other matchlines discharge to ground,
indicating a mismatch.
o
Last, the encoder
generates the search address location of the matching data. In the example, the
encoder selects numerically the smallest numbered matchline of the two
activated matchlines, generating the match address 01.
Associative
Mapping
·
Because no bit field in the address specifies a line number the
cache size is not determined by the address size
·
Associative-mapped memory is also called “content-addressable
memory.”
·
Items are found not by their address but by their content
o
Used extensively in routers and other network devices
o
Corresponds
to associative arrays in Perl and other languages
·
Primary disadvantage is the cost of circuitry
Associative
Mapping
·
Parking lot analogy: there are more permits than spaces
·
Any
student can park in any space
·
Makes full use of parking lot
o
With direct mapping many spaces may be unfilled
·
Note that associative mapping allows flexibility in choice of
replacement blocks when cache is full
Associative
Mapping Summary
·
Address length = (s + w) bits where w = log2(block size)
·
Number of addressable units = 2s+w words or bytes
·
Block size = line size = 2w words or bytes
·
Number of blocks in main memory = 2s+ w/2w = 2s
·
Number of lines in cache = undetermined
·
Size of tag = s bits
Set Associative Mapping
·
A compromise that provides
strengths of both direct and associative approaches
·
Cache is divided into a number of sets of lines
·
Each set contains a fixed number of lines
·
A given block maps to any line in a given set determined by that
block’s address
— e.g. Block B can be in any line of set i
·
e.g. 2 lines per set
— 2-way associative mapping
— A given block can be in one of 2 lines in only one set
Set
Associative Mapping
·
m = v * k
—Where
m = number of lines in cache, v = number of sets and k = lines/set
— Lines in cache = sets * lines per set
·
i = j modulo v
—Where
I = set number and j = main memory block number
— Set
number = block number % number of sets
·
This is referred to as a “k-way” set associative mapping
·
Block Bi can be mapped only into lines of set j.
Set Associative Mapping: Parking Analogy
·
If we have 10,000 parking spaces we can divide them into 1000 sets
of 10 spaces each
·
Still use middle digits of id to find your parking place set: xxx
PPP yyy
·
You have a choice of any place in your set
·
Our parking lots actually work like this, but the sets are fairly
large: Fac/Staff; Commuter; Resident; Visitor
Set
Associative Mapping Example
·
Assume 13 bit set number
·
Block number in main memory is modulo 213 (0010 0000
0000 0000 = 2000h
·
000000, 002000, 004000, … map to same set
Set Associative Mapping Address
Structure
·
Cache control logic sees address as three fields: tag, set and word
·
Use set field to determine cache set to look in
·
Compare tag field to see if we have a hit
·
e.g
—
Address Tag Data Set number
—
1FF 7FFC 1FF 12345678 1FFF
—
001 7FFC 001 11223344 1FFF
·
Tags are much smaller than fully associative memories and
comparators for simultaneous lookup are much less expensive
Set Associative Mapping Summary
·
For a k-way set associative cache with v sets (each
set contains k lines):
— Address length = (t+d+w) bits where w = log2(block size) and d=
log2(v)
— Number of addressable units = 2t+d+w words or bytes
— Size of tag = t bits
— Block size = line size = 2w words or bytes
— Number of blocks in main memory = 2t+d
— Number of lines in set = k
— Number of sets = v = 2d
— Number of lines in cache = kv = k * 2d
·
Tag (t bits) Set (d bits) Word
·
(w bits)
The operation of an associative memory
·
is based on the
representation of all information in the form of a sequence of zones according
to properties and characteristic attributes.
·
In this case the
retrieval of information is reduced to the determination of the zone according
to the preset attributes by means of scanning and comparison of those
attributes with the attributes that are stored in the associative memory.
·
There are 2 basic
methods of realizing the associative memory.
o
The first is the
construction of a memory with storage cells that have the capability of
performing simultaneously the functions of storage, nondestructive reading, and
comparison.
Notes :
ü Such a method of realizing an associative memory
is called network parallel-associative—that is, the required sets of attributes
are preserved in all the memory cells, and the information that possesses a
given set of attributes is searched for simultaneously and independently over
the entire storage capacity.
·
The second method of
realizing an associative memory is the programmed organization (modeling) of
the memory.
o
It consists of the
establishment of associative connections between the information contained in
the memory by means of ordered arrangement of the information in the form of
sequential chains or groups (lists) connected by linkage addresses whose codes
are stored in the same memory cells.
o
This procedure is the
more suitable for practical realization in dealing with large volumes of
information because it provides for the use of conventional accumulators with
address reference.
References
http://www.myreaders.info/04_Associative_Memory.pdf
Written by
LAI WAI KUEN
B031210027
No comments:
Post a Comment