Computer Organization and Architecture 4-26

Nhemoy
A "Mapping
Usually, the cache hemory can store Areasonable number of memory blocks at any given time, but this
number is small compared Lto the total number of blocks in the main memory. The correspondene between the
mapping function.
main memory, blocks and those in the cache is specified by a
"The mapping techniques are classified as
1. Direct-mapping technique
2 Associative-mapping technique
.Fully-a8s0ciative
Set-associative techniques
" To discuss these techniques of cache mapping we consider a cache consists of 128 blocks of 16 worde each,
atotal of 2048 (2 K) main memory has 64 K words. This
64 K for
words and assume that the words of main
memory is addressable by a16-bit address and it can be viewed as 4 K blocks of 16 words each. The
T28 blocks of 16 words each in main [Link]
memory form a page
Z6.1 Direct-Mapping
It is the simplest
mapping technique.
In this technique, each block from the main memory has only one
In this example, the block i of
possible location in the cache organization
the main memory maps onto block j(i = i modulo 128) of the cache, as
Fig- 4.10.6. Therefore, whenever one of the main memory blocks 0, 128, shown in
256, ... is loaded in the cache, it is
Stored in cache block 0. Blocks 1, 129, 257...are stored in cache
block 1 and so on.
In general the mapping
expression is
j =imodulo m
where
i = Main memory block number
j= Cache block (ine) number
m = Number of
blocks (lines) in the cache Main memory
" To implement such cache system, the Block 0
divided into three fields, as shown in [Link]
is Block 1
4.7.6. Page 0
" The lOwer order 4-bits select one of the 16
words Cache Tag 0
in a block. This field is known as 5bits
word field. j=0 Tag
memory
" The Block o Biock 127
second field known as block field is used to j1 ag Block 128
distinguish a block from other blocks. Its length is Block Block 129
7-bits since 2 = 128. Page 1
Tag 1
" When anew block enters the j= 127 Tag
cache, the 7-bit cache Block 127
block ield determines the cache position in which Biock 2K5

this block must be stored.

. The third field is a tag field. It is used to store the
high-order 5-bits of memory address of the block. Block 3968
These 5-bit (tag bits) are used to identify which of Block 3989
the 32 blocks (pages) that are mapped into the Tag Block Word Page 31
Tag 31
cache. 41
Main memory address
. When memory is accessed the 7-bit cache bleek Block 4095

Held of each address generated by CPU points to a Flg. 4.7.6

TECHNICAL PUBLICATIONS - An up thrust for
Direct-mapped cache
knowledge
 and Architecture 4-27 Memory
Organization
er
block location in the cache. The high-order 5bits of the address are cornpared with the tag bits
particular
cache. If there is
assOciated that cache location. If they match, then the desired word is in that block of the
with
and loaded
match. then the block containing the required word must first be read from the main memory
no
intothe cache.

means
that to determine whether requested word is in the cache, only tag field is necessary to be
This
, compared. This needs only one comparison.
from
maindrawback of direct mapped cache is that if processor needs to access sarne mernory locations Since
different pages of the main memory frequently, the controller has to access main mernory frequentiy
" The
two access nemory
of these locations can be in the cache at a time. For example, if processor want to
only one 2 of the main
location 100 Hfrom page 0 and then from page 2, the cache controller has to access page
memory. Therefore, we can say that direct-mapped cache
is easy to inplernent, however, it is not very flexible

Associtive-MMapping. (Fully-Associative Mapping)

2 shows the associative-mapping technique.
The Fig. 4.7.7
this techrnique, a main memory block can be placed Main TernOry

cache block position. As there is no fix block, Block

into any
address has only two fields : word and tag.
the menföry fully-associative 12 bts Cache
This techniques is also referred to as mermor

Tag Biock O
cache,
Biock
block Tag
. The 12-tag bits are required to identify a memory
Biock 1

12bits
when it is resident in the cache. The high-Order
CPU are compared to
of an address received from the Tag Biock 127
see if the
the tag bits of each block of the cache to
Biock i

desired block is present

Tag Word
is
"Once the desired block is present, the 4-bit word 12 4
from the cache. Biock 409s
used to identify the necessary word
Main memory address

Fhis technique gives complete freedom in choosing the

cache location in which to place the memory block. Fig. 4.7.7 Associative-mapped cache
tused mere
Thus, the memory space in the eaehe ean be
efficiently.
replace (remove) an existing block only if the cache is
"A new block that has to be loaded into the cache has to
full.
possible replacement algorithm to select the block to be
in such situations, it is necessarý to use one of the
replaced. higher-order bits of address of the
SDisadvantage : In associative-mapped cache, it is necessary to compare the
determine whether a given block is in the cache.
main mermory with all 128 tag corresponding to each block to
Ihis is the main disadvantage of associative-mapped cache. X2X2XLY

Set-Associative Mapping
he set-associative mapping is a combination of both direct and associative mapping.
parallel.
contains several groups of direct-mapped blocks that operate as several direct-mapped caches in
*A Hock of data from any page in the main memory can go into a particular block location a any
cache. Hence the contention problenm of the direct-mapped technique is eased by hayihg a few
dírect-mapped
Choices for block placement.
TECHNICAL PUBLICATIONS - An up thust for knowiedoe
 Comt(vpant atik ad
Ahiechue
required Addrese Main emory
narisns dewend on the
number
lock 0
toc
Caches in the diret mayet
Cahe system et

Theee omyarisons Ate

less than the always
mparisN Block 63
fu axsNiative mapping
the Alork 6A
he eory Cache enory
ig 478 Set 0 Tag 4 Alock 0
shows wYINaY ock 0
Page
set-assiañvr he Eah Set 1 Tag Hlock 1 Tg 1
a in the main
menmory is Block 127
Ogánizd
the
in such a way
that
size ot each page is Set 62g |Tag Block 82
as the size of same
one dinectly Set 6 Block 63
Tac
Block 83
mapr cache. is called RIock 4032
two-wav set-assOciative cache Tag Set Word
Qlock 4033
because cach bock fro min Block belongs Page 83
Tag 63
memory has twe choic for to set 6)

blockplacement
(" In this
Block 4095

technique, block 0, 64, Fig. 4.7.8 Two-way

set-assoclative cache
125,..4032 of main menmory can map into any of the two (block 0)
main mnemory can map into blocks of set 0, block 1, 65, 129,.,
any of the two (block 1) 4033 of
" As there are two blocks of set 1and so on.
choices, necessary to compare
it is
block locations of
particular set. Thus for two-wayaddress memory with the tag bits of
of
determine whetht agiven block is in the set-associative
cache, we require two corresponding
two
ebince there are two cache. comparisons to
cache at a time. This direct-mapped caches, any two bytes having same
offset from different pages
" yo
improves the hit rate ef the
cache system. can be in the
implement set-associative cache system, the
" The4-bit word field selects one of address 0s divided into three fields, as
the 16 words in a
block. shown in Fig. 4.7.8.
,The set feld needs 6-bits to
determine the desired block from 64 sets.
dentity a block belongs to a particular page from 64 However, there are now 64 pages. To
mD Cons1der acache consisting of 256 blocks of pages, six tag bits are required.
main memory is l6 words each, for a
addressable by a l6-bit addressd it consists total of 4096 (4 K) words
and assume
BLOCKISET and word fields for
different mapping techniques ?
of 4 K blocks. How
many bits are there in each of that te
Solution: We know that memory address is the TAy
field in different mapping divided into three fields. We will now find
techniques. the exact bits
required for eacit
a) Direct-mapping
Word bits : We know that each
block consists of 16
16) four bit reserved for it. words. Therefore, to
identify each word we must have (2*-
Block blts : The cache memory
consists of 256
blocks and
memory maps onto block k modulo 256 of
for each block. To address 256 the cache. It has oneusing direct-mapped technique, block k of the mait
to one
block we require (2° =256) eight bits. correspondence
and requires unique address

TECHNICAL PUBLICATIONS- An up thrust for

knowledge
Computer Organization and Architecture 4-28 14

Whe
Memory
required address Main nemory
comparisons depend on the Block O
number Block
caches in the
direct-mapped Rlock belongs
cache system. to set 0
Page 0
These oomparisOns are always Tag 0
less than the Omparisons Block 63
requied in the Block 64

futv-associatire
Fig 4.7.8
mapping Set 0 Tag
Cache memory
Tag
Cache mernory
Biock 65

shows two Way Block 0 Biock 0 Page

set-associative cache. Each Set 1 Tag Biock 1 | Tag Block 1 Tag
age in the main
memory is Biock 127
Organized in such a way that
the size of each page is Set 62 Tag Tag
as the size of
same Block 62
one directiy Set 63 Tag Tag
Block 63 Block 63
mapped cache Bock 4032
It is called
Block 4033
two-way set-associative cache Tag Set Word
6 4
because each bleck from main Block belongs Page 83
Tag 63
to set 63
memory has twe chotces for
biock placement. Block 4095
. I this techrique,
block 0, 64, Fig. 4.7.8 Two-way
128,....4032of main memory can
map into any of the two (block 0)
set-associative cache
main memory can map into any of blocks of set 0, block 1, 65, 129... 4033
the two (block 1) blockS of of
" As there are two set1 and so on.
choices, it is necessary to compare
bËock locations of address of memory with the
particular set. Thus twO-way tag bits of
determine whetha a given block is in the forcache. set-associative cache, we require twocorresponding twoto
Since there are two comparisons
Cache at a time. This direct-mapped caches, any two bytes
iproves the hit rate ef the cache having same offset from different pages can be n
. To
implement set-associative cache systemn, the system. e
. The 4-bit word
field selects one of the 16 address is-divided into three fields, as
The set field needs 6-bits to
words in a block. shown in Fig. 4.7.8.
identify a block belongs to a determinepage the desired block
from 64 sets.
particular
ExampleAConsider a cache consisting of 256 trom 64 pages, six tag bits areHowever,
required.
there are now 6 Pages. To
main emory is addressable by a of blocks l6 words each, for a
16-bit total of
addressd consists of 4 K blocks.
BLOCKSET and uword fields for d1fferent mupping it 4096 (4 K) words arnd ASSUme that the
How many bits are
Solution: We know that memory address is
techniques? there in e2c gf the TAG
field in different mapping divided into three fields. We
techniques. will now find the required for ea
a) Direct-mapping exact bits
Word bits We know that each block
16) four bit reserved for it. consists of 16
words. Therefore, to identify each word we
must
have (2s

Block bits : The cache memory consists

of 256
memory maps onto block k modulo 256 of the and using blocks the mau
for each block. To cache.
address 256 block we require (2 It has one to one
-256) eight bits.
directcorrespondence
-mapped technique,
and
block k of
unique
address
requires
TECHNICAL PUBLICATIONS - An up thrust for
krnowBedge
 Onganizatonand Architecture 4-29 Mernory

of the main
iAlhe remaining 4 (16- 4 - 8) address bits are tag bits which stores the higher address
TAgbitg
memory.

main memory address for directmapping technique is divided as shown below:

The

TAG ALOCK wORO

Main nnemory ddress

Fig. 4.7.9 (a)

b)Associative-mapping
Word bits: The
word length will remain same i.e. 4 bits.
tag bits and an address
the associative-mapping techique, each block in the main memory is identified by the desired block is
the CPUis compared with the tag bits of each block of the cache to see if the
In
rveived from
(except word bits) are
present. Therefore, this type of technique does not have block bits, but all remaining bits
bits.
reserved as tag
Block bits :

there are 12
address each block in the main memory (212= 4096) 12 bits are required and therefore,
Tag bits: To
tag bits.
technique is divided as shoWn below:
The main memory address for direct mapping

TAG WORD

Main memory address 12

Fig. 4.7.9 (b)

c) Set-associative mapping blocks per

mnapping. Here, cache memory is mapped with two
Let us assume that there is a 2-way set-associative the desired block.
determines which set of the cache might contain
set. The set field of the address
bits.
Word bits : The word length will remain same i.e. 4
(2= 128) seven bits are required.
Set bits: There are 128 sets (256/2). To identify each set
the tag bits which stores higher address of the main
Tag bits: The remaining 5 (16 - 4 - 7) address bits are
memory. mapping technique is divided as shown below:
Ihe main memory address for 2-way set associative
TAG SET WORD

Main memory address

Fig. 4.7.10

Consider a cache consisting of 128 blocks of 16

words each, for a tottal of 2048 (2k) wends and aSSUMe that the main
memor
Hou ymany addressable
is by a 16 bit address and it consists
bits are there in each of the TAG,
of 48 blocks.
SET and WORD fields for dierent mapyping techniques ie.
)
Direct i) Associative iii) 2-way set associative.
TECHNICAL PUBLICATIONS- An up thnust for krnowecdge
Computer Oryenization and
Architecture 4-30
Mernory
Solution : i) Direct mapping
Word bits
Each blok consists of 16 words
To identify each reserved for it.
wond we must have (2 - 16) four bit
The cache consists of 128 blocks and using direct mapped technique, block Kof main memory map
Block bits :
onto blok K modulo 128 of the cache It has one to one correspondence and requires unique address for each block.

To address 128 blocks we reuire (2- 128)

seven bits.
higher address ot
Tag bits: The 7) address bits are tag bits which stores the the main
remaining 5 (16 - 4 -
memor. The main memory address for direct -mapping technique is divided as shown
below :

TACG BLOCK WORD

Main memory address 7

i) Associative mapping

Word bits: The word length will remain same i.e. 4

bits.
n he assoxiative-mapping technique, each block in the main memory is identified by the tag bits and an addres
recerved from the CPUis compared with the tag bits of each block of the cache to see if the desired block is
present Therefore, this type of technigue does not have block bits, but all remaining bits (except
word bits) are
reserved as tag bits.
Biock bits : 0
Tag bits: To address each block in the main
tag bits.
memory (2 = 2048) 11 bits are required and therefore there are 11
The main memory address for direct
mapping technique is divided as shown below:

TAG
WORD
Main memory address = 11 4

iiiy Set associative Mapping

et us
assume that there is a 2-way
set. The set field of the address set-associative mapping. Here, cache memory is mapped with two
determines which set of the cache might contain blocks per
Word bits : The word length will remain same i.e. 4 the desired block.
bits.
Set bits: There are 64 sets (128/2). To
identify each set (2 = 64) six bits
are required.
Tag bits: The remaining 6 (16 - 4 -
6) address bits are the tag bits
memory. which stores higher address of the man
The main memory address for
2-way set associative mapping
technique is divided as shown below :
TAG
SET WORD
Main memory address

TECHNICAL PUBLICATIONS An up thrust for

knowledge
 Onganizatlonand Architecture
4- 31

Ahlock
set-assoCiatre cache consists of 64 Memory
blocks divided into 4 block sets. The main
of 128 words of 16 bits length : memory contains 4096 blocks,
mamybits are
there in main
How
memory
?
J in each of the TAG, SET
bits are there and WORD fields ?
solution: i) Number of bits in main memory :

= Number of blocks x Number of words per block x Number of bits per word
= 4096 x 128 x 16

= 8388608 bits

) Number of bits in word field:

There are 128 words in each block. Therefore, to identify each word (2 = 128) 7 bits are required.
i) Number of T bits in set field : There are 64 blocks and each set consists of4 blocks.
Therefore, there are 16 (64/4) sets. To identify each set (2 = 16) four bits are required.
k) Number of bits in tag field : The total words in the memory are :
4096 ×128 = 524288

To address these words we require (2 = 524288) 19 address lines. Therefore, tag bits are eight (19 -7-4).
memory of 1 K words. The cache uses direct
omote 5 A digital computer has a memory unit of 64 K x 16 and a cache
block and word field of the address format ?
ming with a block size of four words. How many bits there in the tag indes,
Solution : Word bits : Number of word bits = log, 4 = log, 2 = 2-bits

Block bits : Number of block =

Cache size
Words in each block 1k-
4 256

2° = 8 bits
.:. Number of block bits = log, 256 = log,
main memory
Tag bits : Number of bits to address
Block Word
Tag
2
Main memory address =

log, 2° = 16 bits
= log, 64 K =
= 16 - 8 2 =6 bits a total of 20.48
.i. Number of Tag bits block of four words. The cache can accommodate
memory uses
set associative cache
mple 4.16 A two wav
main memory size 1s
wUras from main nemory. The
?
128 Kx 32. of address format
index, block and word field AKTU 20121, Marks 5
i) How bits are there in the tag
îny log 2 = 17 bits
) What is size of cache memory = log, 128 K =
memory address 2048
Solution :Number of bits in main 512 Blocks
cache memory= 4
Number of blocks in the 5i2 = 256 sets
the cache memory =
Number of sets in = 8 bits
set field= log, 256 = log, 2"
Number of bitsin 2 bits
word field = log, 4 = log, 2* =
Number of bits in -8- 2 =7 bits
tag field = 17
Number of bits in
knowiedge
- An up thrust for
TECHNCAL PUBLICATIONS
 Computer Organization and Architecture 4-32

Tag
Set Word Mernoy
2
Main memory address
17bits

Bxanple 7A direct the follouwing parameters : cache size = 1K

mapped cache has words, Block size = 120
memorv size is 64 K words. Specify the
mumber of bits in TAG, BLOCK and
WORD in main memory address. 100rds and main
Solution: Wor bits = log: 128 = 7-bits
Cache size 1K
Number of blocks = 8
Wordsin each block 128

. Number of block bits = log, 8 = 3-bits

Number of address bits to address main memory
= log, 64K = log, 26 = 16 - bits
Tag bits = 16 - 3 -7=6-bits

TAG BLOCK WORD

Maii memory address = 7

16 - bits

Expiain various cache mapping

aSSOcatiDe manner with 4 blocks per set, 64 wordstechniques. A computer system has a 4K
pe block. The main
_word cache organized in block
each of the TAG, SET and memors contain 65536 blocks How many bits are
WORD fields ? there i
Solution: AKTU201581
Word bits : Each block contains 64
reserved for it. words. Therefore, to identify each word we
must have (2° -64) six bits
Set bits: Total number of hlock - lotal words in cache 4096
Words per block 64
= 64

Total number of sets = Number of blocks 64

blocks per set 4 16
To
identify each set (2* =16)four bits are
Tag bits : Total number
required.
words in main memory
65536 x 64 = 4194304 = 222
Main memory address is 22 bits wide.
Tag bits = 22 - set bits -
word bits = 22 - 4 -6= 12

Tag Set Word

Main memory address 12 4 6

410 An eight-way set-associative cache is used in a

is 16hutes, and there are 2 lines per set. computer in which the real
Calculate the cache size and tao lenoth memory size is 2 bytes. The line size
Solution: Number of blocks per set = 2" = 1024
Number of bytes per block = 16

TECHNICAL PUBLICATIONS- An up thrust for

knowledoe
 nanizationand Architecture
4- 33 Mornory

Total number of sets = g

Total size of cache memory = 1024 x8 x16

128 K

Tag length = 32 - 10 - 4 = 18

Comparison between Mapping Techniques

S.
No.
Direct-mapping Associative-mapping Vsetassociative-mapping
main main tnemory can
Each block from the possible
A block of data from main memory A block of data from location of
1
memory has only one can be placed into any cache block go into a particular block
cache. any direct-mapped cache.
location in the position.
equal to
comparison. Needs comparison with all tag bits. Needs number of comparisons
Needs only one number of blocks per set.
2
in cache hit ratio
decreases if Cache hit ratio has no effect if The effect of reduction
access to the two
Cache hit ratio same processor needs to access same in case of frequent memory is
3
Drocessor needs to access
two location from two different differernt pages of the main
from memory
memory location pages of the main memory reduced.
different pages of the main
memory frequently. frequently.
address is divided into
address is divided into Main memory SET and WORD.
address is Main nemory three fields : TAG,
Main memory two fieids : TAG and WORD.
divided into three fields:TAG,
BLOCK and WORD. with number
Searching time increases
less. Searching time is more. of blocks per set.
5 Searching time is
between mapping techniques
Table 4.7.1 Comparison
memory may
477 Cache Coherency cache memory and another in main
same data, one in
CPU systemn, two copies of coherence problem.
"Ina single inconsistency is called as cache operations.
data
become different. This main memory caused by cache write
in the
updating systems eliminates data inconsistency system bus. This bus
master could
"Cache control of the
another bus master can take over another processor. When this
multiprocessor systems, held in the cache of
"In
main memory blocks which are already memory creating
inconsistency.
data into a held in main
write
cache no longer match those cache coherency :
happens, the datain the data inconsistency, that is to protect
approaches to prevent
four different
"The 80386 supports 2. Hardware trarnsparency
1. Bus watching (snooping) 4. Cache flushing. master writes to a
3. Non-cacheable memory invalidates the cache entry, if another
cache controller shows bus watching.
"Bus watching : In bus
watching,
resides in the cache memory. Fig. 4.7.11
which also main memory are routed
location in shared memory accesses of all devices to the that
hardware
transparency,
the main memory and to all other caches
" Hardware transparency : In all cache writes both
to
by copying system.
through the same cache or 4.7.12 shows hardware transparent
share the samememory. Fig.

knowledge
- An up thrust for
TECHNICAL PUBLICATIONS
 4-34
Duter Oryenization and Architecture Col

Otherbu Other bus Cache Main

master master
memory

80306 Cache
Shared
80386 82385
memory

transparoncy
Flg. 4.7.12 Hardwaro
Flg. 4.7.11 Bus watching
" Non-cacheable memory : The 80386DX can partition its main memory into a cacheable and non-cacheab,
coherency can be
as non-cacheable memory cache maintained, sine
memory. By designing shared memory
shared memory is never copied into cache.

Other bus
master

Non-cacheable

80386 Decode
Main
memory Cacheable
Decode

Fig. 4.7.13 Memory

"Cache ffushing : To avoid data inconsistency, a cache flush writes any altered data to the main memory and
caches in the system are flushed before a device writes to shared memory.

478 Cache Updating Policies

"In a cache system, two copies of same data can exist at a time, one in cache and
one in main memory. If on
copy is altered and other is not, two different sets of data become associated
with the same address. 10
prevent this, the cache system has updating systems such as : write through system,
system and write-back system.
buffered write through

4.79.1 Write through System

" The cache
controller copies data to the main memory immediately after it is written to
main memory always contains a valid data and thus any the cache. Due to u
block in the cache can be overwritten immediat
without data loss.
" The write through is asimple approach.
.This approach requires time to write
data in main memory with increase in bus traffic.
" This in effect reduces the system performance.

18.2 Buffered Wrte through System

" In buffered write through system, the processor can start a new cycle before the write cycle to the mait
memory is completed. 1his means that the write accesses to the
main memorv are buffered.
" In such systems, read access which is a "cache hit" can be performed simultaneously When main memory
updated.
TECHNICAL PUBLICATIONS- An up thrust for knowledge
 Organzationand Architecture
4- 35
Memory
" However,two consecutive write operations to the main memory or read operation with cache "miss" require
wait.
processor to
the
-Back System
In a write-back system, the alter (update) bit in the tag field is used to keep information of the new data. If it
isset,the controller copies the block to main memory before loading new data into the cache.
e Due toO one time write operation, number of write cycles are reduced in write-back system. But this system has
following disadvantages.
Write-back cache controller logic is
more complex.
is necessary that, all altered blocks must be written to the main memory before another device can
access
these blocks in main memory.
In case of power failure, the data in the cache memory is lost, so there is no way to tell which locations of
the main memory contain old data. Therefore, the main memory as well as cache must be considered
volatile and provisions must be made to save the data in the cache.
8 Replacement Algorithms
. When a new block is brought into the cache, one of the existing blocks must be replaced, by a new block.
.In case of direct-mapping cache, we know that each block from the main mnemory has only one possible
location in the cache, hence there is no choice. The previous data is replaced by the data from the same
memory location from new page of the main memory.
.For associative and set-associative techniques, there is a choice of replacing existing biock. The choice of
replacement of the existing block should be such that the probability of accessing same block must be very less.
The replacement algorithms do the task of selecting the existing block which must be replaced.
" There are four most common replacemernt algorithms
. Least-Recently-Used (LRU)
First-In-First-Out (FIFO)
Least-Frequently-Used (LFU)
Random
"Least-Recently-Used : In this technique, the block in the set which has been in the cache longest with no
reference to it, is selected for the replacemernt. Since we assume that more-recentBy used memory locations ae
more likely to be referenced again. This techrnique can be easily implemented in the two-way set-asociative
cache organization.
"First-In-First-Out : This technique uses same concept that stack implementation uses in the microprocessors. In
this technique, the block which is first loaded in the cache amongst the present blocks in the cache is selected
for the replacement.
"Least-Fregquently- Used : In this technique, the block in the set which has the fewest references is selected for
the replacement.
"Random : Here. there is no specific criteria for replacement of any block. The existing blocks are replaced
randomly. Simulation studies have proved that random replacement algorithm provides only slightBy inferior
performance to algorithms just discussed.
Performance Issues
" The overall goal in memory-hierarchy desigrn should be to achieve a performance close to that of the fastest
device M, and a cost per bit close to that of the cheapest device M.

TECHNICAL PUBLICATIONS- An up thrust for krowieke