William Stallings Computer Organization Dr. George Lazik .
Edited byDr. George LazikWilliam StallingsComputer Organizationand Architecture10th Edition 2016 Pearson Education, Inc., Hoboken,NJ. All rights reserved.
Chapter 4Cache Memory 2016 Pearson Education, Inc., Hoboken, NJ. All rights reserved.
LocationInternal (e.g. processor registers, cache,main memory)External (e.g. optical disks, magnetic disks,tapes)CapacityNumber of wordsNumber of bytesUnit of TransferWordBlockAccess Access timeCycle timeTransfer ratePhysical sical sableOrganizationMemory modulesTable 4.1Key Characteristics of Computer Memory Systems 2016 Pearson Education, Inc., Hoboken, NJ. All rights reserved.
Characteristics of MemorySystemsLocationRefers to whether memory is internal and external to the computerInternal memory is often equated with main memoryProcessor requires its own local memory, in the form of registersCache is another form of internal memoryExternal memory consists of peripheral storage devices that areaccessible to the processor via I/O controllersCapacityMemory is typically expressed in terms of bytesUnit of transferFor internal memory the unit of transfer is equal to the number ofelectrical lines into and out of the memory module 2016 Pearson Education, Inc., Hoboken, NJ. All rights reserved.
Method of Accessing Units of ativeMemory is organized intounits of data calledrecordsInvolves a shared readwrite mechanismEach addressablelocation in memory has aunique, physically wiredin addressing mechanismA word is retrievedbased on a portion of itscontents rather than itsaddressAccess must be made ina specific linearsequenceIndividual blocks orrecords have a uniqueaddress based onphysical locationThe time to access agiven location isindependent of thesequence of prioraccesses and is constantEach location has its ownaddressing mechanismand retrieval time isconstant independent oflocation or prior accesspatternsAccess time is variableAny location can beselected at random anddirectly addressed andaccessedCache memories mayemploy associativeaccessAccess time is variableMain memory and somecache systems arerandom access 2016 Pearson Education, Inc., Hoboken, NJ. All rights reserved.
Capacity and Performance:The two most important characteristics ofmemoryThree performance parameters are used:Access time (latency) For random-access memory it is thetime it takes to perform a read orwrite operation For non-random-access memory itis the time it takes to position theread-write mechanism at thedesired locationMemory cycle time Access time plus any additionaltime required before secondaccess can commence Additional time may be requiredfor transients to die out on signallines or to regenerate data if theyare read destructively Concerned with the system bus,not the processor 2016 Pearson Education, Inc., Hoboken, NJ. All rights reserved.Transfer rate The rate at which data can betransferred into or out of a memoryunit For random-access memory it isequal to 1/(cycle time)
MemoryThe most common forms are:Semiconductor memoryMagnetic surface memoryOpticalMagneto-opticalSeveral physical characteristics of data storage are important:Volatile memoryInformation decays naturally or is lost when electrical power is switched offNonvolatile memoryOnce recorded, information remains without deterioration until deliberately changedNo electrical power is needed to retain informationMagnetic-surface memoriesAre nonvolatileSemiconductor memoryMay be either volatile or nonvolatileNonerasable memoryCannot be altered, except by destroying the storage unitSemiconductor memory of this type is known as read-only memory (ROM)For random-access memory the organization is a key design issueOrganization refers to the physical arrangement of bits to form words 2016 Pearson Education, Inc., Hoboken, NJ. All rights reserved.
Memory HierarchyDesign constraints on a computer’s memory can be summedup by three questions:How much, how fast, how expensiveThere is a trade-off among capacity, access time, and costFaster access time, greater cost per bitGreater capacity, smaller cost per bitGreater capacity, slower access timeThe way out of the memory dilemma is not to rely on a singlememory component or technology, but to employ a memoryhierarchy 2016 Pearson Education, Inc., Hoboken, NJ. All rights reserved.
gRe r sei stIn bme oardmoryOutsto boarrag deOffsto -lineragechCaeinMa orymmeiskcditegn OMM a D- R WC D- R WRCMDDV D- R A yaDV lu-RBctet ingMaeapFigure 4.1 The Memory Hierarchy 2016 Pearson Education, Inc., Hoboken, NJ. All rights reserved.
T1 T2Average access timeT2T101Fraction of accesses involving only Level 1 (Hit ratio)Figure 4.2 Performance of a Simple Two-Level Memory 2016 Pearson Education, Inc., Hoboken, NJ. All rights reserved.
MemoryThe use of three levels exploits the fact that semiconductormemory comes in a variety of types which differ in speedand costData are stored more permanently on external mass storagedevicesExternal, nonvolatile memory is also referred to assecondary memory or auxiliary memoryDisk cacheA portion of main memory can be used as a buffer to hold datatemporarily that is to be read out to diskA few large transfers of data can be used instead of many smalltransfers of dataData can be retrieved rapidly from the software cache rather thanslowly from the disk 2016 Pearson Education, Inc., Hoboken, NJ. All rights reserved.
Block TransferWord TransferMain MemoryCacheCPUFastSlow(a) Single cacheLevel 2(L2) cacheLevel 1(L1) cacheCPUFastestFastLevel 3(L3) cacheLessfast(b) Three-level cache organizationFigure 4.3 Cache and Main Memory 2016 Pearson Education, Inc., Hoboken, NJ. All rights reserved.MainMemorySlow
LineNumber Tag012BlockMemoryaddress0123Block 0(K words)C–1Block Length(K Words)(a) CacheBlock M – 12n – 1WordLength(b) Main memoryFigure 4.4 Cache/Main-Memory Structure 2016 Pearson Education, Inc., Hoboken, NJ. All rights reserved.
STARTReceive addressRA from CPUIs blockcontaining RAin cache?Access mainmemory for blockcontaining RANoYesAllocate cacheline for mainmemory blockFetch RA wordand deliverto CPULoad mainmemory blockinto cache lineDeliver RA wordto CPUDONEFigure 4.5 Cache Read Operation 2016 Pearson Education, Inc., Hoboken, NJ. All rights reserved.
igure 4.6 Typical Cache Organization 2016 Pearson Education, Inc., Hoboken, NJ. All rights reserved.System BusAddressbuffer
Cache AddressesLogicalPhysicalCache SizeMapping FunctionDirectAssociativeSet AssociativeReplacement AlgorithmLeast recently used (LRU)First in first out (FIFO)Least frequently used (LFU)RandomWrite PolicyWrite throughWrite backLine SizeNumber of cachesSingle or two levelUnified or splitTable 4.2Elements of Cache Design 2016 Pearson Education, Inc., Hoboken, NJ. All rights reserved.
Cache AddressesVirtual MemoryVirtual memoryFacility that allows programs to address memory from a logicalpoint of view, without regard to the amount of main memoryphysically availableWhen used, the address fields of machine instructions containvirtual addressesFor reads to and writes from main memory, a hardware memorymanagement unit (MMU) translates each virtual address into aphysical address in main memory 2016 Pearson Education, Inc., Hoboken, NJ. All rights reserved.
Logical addressMMUPhysical addressProcessorMainmemoryCacheData(a) Logical CacheLogical addressMMUPhysical addressProcessorCacheData(b) Physical CacheFigure 4.7 Logical and Physical Caches 2016 Pearson Education, Inc., Hoboken, NJ. All rights reserved.Mainmemory
Year 199919992000L1 CacheaL2 cacheL3 Cache16 to 32 kB1 kB16 kB64 kB128 to 256 kB8 kB8 kB/8 kB32 kB32 kB/32 kB32 kB/32 kB256 kB8 kB/8 kB——————256 to 512 KB——256 KB to 1 MB8 MB256 KB—————————2 MB——200064 kB/32 kB8 MB—2000200120028 kB16 kB/16 kB32 kB2 MB96 KB256 KB—4 MB6 MB200364 kB1.9 MB36 MB200464 kB/64 kB1MB—PC/server200764 kB/64 kB4 MB32 MBMainframeWorkstaton/server200864 kB/128 kB3 MB24-48 MB20116 32 kB/32 kB1.5 MB12 MB201124 64 kB/128 kB24 1.5 MB24 MB L3192 MBL4ProcessorTypeIBM 360/85PDP-11/70VAX 11/780IBM 3033IBM 3090Intel 80486PentiumPowerPC 601PowerPC 620PowerPC G4IBM S/390 G6Pentium -endserverSupercomputerIBM SPCRAY MTAbItaniumItanium 2IBMPOWER5CRAY XD-1IBMPOWER6IBM z10Intel Core i7EE 990IBMzEnterprise196Table 4.3Cache Sizes ofSomeProcessorsaMainframe/ServerTwo values separated bya slash refer to instructionand data caches.b 2016 Pearson Education, Inc., Hoboken, NJ. All rights reserved.Both caches areinstruction only; no datacaches.(Table can be found onpage 134 in the textbook.)
Mapping FunctionBecause there are fewer cache lines than main memoryblocks, an algorithm is needed for mapping main memoryblocks into cache linesThree techniques can be used:Direct The simplest technique Maps each block of mainmemory into only onepossible cache lineAssociative Permits each mainmemory block to beloaded into any line of thecache The cache control logicinterprets a memoryaddress simply as a Tagand a Word field To determine whether ablock is in the cache, thecache control logic mustsimultaneously examineevery line’s Tag for amatch 2016 Pearson Education, Inc., Hoboken, NJ. All rights reserved.Set Associative A compromise thatexhibits the strengths ofboth the direct andassociative approacheswhile reducing theirdisadvantages
tbbL0m linesB0Bm–1Lm–1First m blocks ofmain memory(equal to size of cache)cache memoryb length of block in bitst length of tag in bits(a) Direct mappingtbL0bone block ofmain memoryLm–1cache memory(b) Associative mappingFigure 4.8 Mapping From Main Memory to Cache:Direct and Associative 2016 Pearson Education, Inc., Hoboken, NJ. All rights reserved.
Simple Direct Mapping CacheMemory Address ock 0Word 0Word 1Block 112Block 234Block 356Block 47Block 5Block 6Block 1101128011100290111013001111031011111Block 8Block 9SIMPLE EXAMPLEDESIGN PARAMETERSWord: 1 bitLine 3 bitsTag: 2 bitsBlock 10Block 11Block 12Block Size: 21 or 2 wordsNumber of Blocks: 16Block 13Block 14Block 15 2016 Pearson Education, Inc., Hoboken, NJ. All rights reserved.Number of Lines: 23 or 8
s wCacheTagMemory AddressWordLines–rrTagMain MemoryDataL0wWOW1W2W3B0W4jW(4j 1)W(4j 2)W(4j 3)Bjs–rswCompare1 if match0 if no matchLi(hit in cache)Lm–10 if match1 if no match(miss in cache)Figure 4.9 Direct-Mapping Cache Organization 2016 Pearson Education, Inc., Hoboken, NJ. All rights reserved.w
2016 Pearson Education, Inc., Hoboken, NJ. All rights reserved.
Main memory address (binary)Tag(hex)TagLine 11111100Data13579246LineDataNumber13579246 000011235813 10012345678FF1611223344123456783FFE3FFF8 bits32 1111110016-Kline cache1122334424682468Note: Memory address values arein binary representation;other values are in hexadecimal32 bits16-MByte main memoryTagLine8 bits14 bitsWordMain memory address Figure 4.10 Direct Mapping Example 2016 Pearson Education, Inc., Hoboken, NJ. All rights reserved.2 bits
2016 Pearson Education, Inc., Hoboken, NJ. All rights reserved.
Direct Mapping SummaryAddress length (s w) bits determines memory address spaceNumber of addressable units 2s w words or bytes memory sizeBlock size line size 2w words or bytes specified by designerNumber of blocks in main memory 2s w/2w 2sNumber of lines in cache m 2r “m” is specified by designerSize of tag (s – r) bits 2016 Pearson Education, Inc., Hoboken, NJ. All rights reserved.
Victim CacheOriginally proposed as an approach to reduce the conflictmisses of direct mapped caches without affecting its fastaccess timeFully associative cacheTypical size is 4 to 16 cache linesResiding between direct mapped L1 cache and the next levelof memory 2016 Pearson Education, Inc., Hoboken, NJ. All rights reserved.
s wCacheMemory AddressWordTagTagMain MemoryDataL0sW0W1W2W3B0W4jW(4j 1)W(4j 2)W(4j 3)BjwwLjswCompare1 if match0 if no match0 if match1 if no match(hit in cache)sLm–1(miss in cache)Figure 4.11 Fully Associative Cache Organization 2016 Pearson Education, Inc., Hoboken, NJ. All rights reserved.
2016 Pearson Education, Inc., Hoboken, NJ. All rights reserved.
Main memory address (binary)TagWordTag (hex)000000 000000000000000000000000000001 ata3FFFFE 11223344 0000058CE7 FEDCBA98 0001058CE6 000101100011001110011000058CE7 000101100011001110011100058CE8 000101100011001110100000FEDCBA98FEDCBA983FFFFD 33333333000000 135792463FFFFF 2468246822 bits3FFD3FFE3FFF32 bits16 Kline Cache3FFFFD 1111111111111111111101003FFFFE 1111111111111111111110003FFFFF te: Memory address values arein binary representation;other values are in hexadecimal32 bits16 MByte Main MemoryTagWordMain Memory Address 22 bitsFigure 4.12 Associative Mapping Example 2016 Pearson Education, Inc., Hoboken, NJ. All rights reserved.2 bits
Associative Mapping SummaryAddress length (s w) bits determines memory address spaceNumber of addressable units 2s w words or bytes memory sizeBlock size line size 2w words or bytes specified by designerNumber of blocks in main memory 2s w/2w 2sNumber of lines in cache undetermined specified by designerSize of tag s bits 2016 Pearson Education, Inc., Hoboken, NJ. All rights reserved.
Set Associative MappingCompromise that exhibits the strengths of both the direct andassociative approaches while reducing their disadvantagesCache consists of a number of setsEach set contains a number of linesA given block maps to any line in a given sete.g. 2 lines per set2 way associative mappingA given block can be in one of 2 lines in only one set 2016 Pearson Education, Inc., Hoboken, NJ. All rights reserved.
L0k linesB0Lk–1Cache memory - set 0Bv–1First v blocks ofmain memory(equal to number of sets)Cache memory - set v–1(a) v associative-mapped cachesB0L0v linesonesetBv–1First v blocks ofmain memory(equal to number of sets)Cache memory - way 1Cache memory - way k(b) k direct-mapped cachesFigure 4.13 Mapping From Main Memory to Cache:k-way Set Associative 2016 Pearson Education, Inc., Hoboken, NJ. All rights reserved.Lv–1
Set Associative Mapping SummaryAddress length (s w) bitsNumber of addressable units 2s w words or bytesBlock size line size 2w words or bytesNumber of blocks in main memory 2s w/2w 2sNumber of lines in set kk is determined by designerNumber of sets v 2dd is determined by designerNumber of lines in cache m kv k * 2dSize of cache k * 2d w words or bytesSize of tag (s – d) bits 2016 Pearson Education, Inc., Hoboken, NJ. All rights reserved.
Simple Set Associative CacheMemory Address 0010101100101112001100BlockBlock 0Block 1Block 2Block 3Block 4Block 1100126011010K 1Word 0Block 6Block 7Block 8Block 9SetWord 1K 2Word 0Word 101234567SIMPLE EXAMPLEDESIGN PARAMETERSWord: 1 bitSet: 3 bitsTag: 2 bitsKeys: 2 with 2 words/lineBlock 10Block 11Block Size: 21 or 2 wordsBlock 12Number of Blocks: 16Block 132701101128011100290111013001111031011111 2016 Pearson Education, Inc., Hoboken, NJ. All rights reserved.Block 14Block 15Number of Sets: 23 or 8
Simple Set Associative Cache WorksheetMemory Address 00001701000118010010Key 1Key 2SetBlockvdTagWord 0Word 1vdTagWord 0Word ckDATA WORDS NOTATIONW0-AW1-ABlockWHERE "A" IS THE MEMORY 3001111031011111BlockBlockBlockBlockBlockBlock 2016 Pearson Education, Inc., Hoboken, NJ. All rights reserved.
s wCacheTagMemory AddressWordSets–ddTagMain MemoryDataB0F0B1wF1Set 0s–dFk–1Fks wBjCompareFk i(hit in cache)1 if match0 if no match0 if match1 if no matchSet 1F2k–1(miss in cache)Figure 4.14 k-Way Set Associative Cache Organization 2016 Pearson Education, Inc., Hoboken, NJ. All rights reserved.
2016 Pearson Education, Inc., Hoboken, NJ. All rights reserved.
2016 Pearson Education, Inc., Hoboken, NJ. All rights reserved.
2016 Pearson Education, Inc., Hoboken, NJ. All rights reserved.
Tag(hex)Main memory address (binary)TagMain Memory Address Set Word000 000000000000000000000000000 000000000000000000000100Data13579246TagSet9 bitsWord13 bits2 bits000 000000001111111111111000000 00000000111111111111110002C 00010110000000000000000002C DataNumber Tag000 13579246 0000 02C 7777777702C 11235813 000102C 000101100011001110011100FEDCBA9802C FEDCBA980CE702C 000101100111111111111100123456781FF 1122334402C 123456781FFE1FFF9 bits1FF 1111111110000000000000001FF 1111111110000000000001001FF 1111111111111111111110001FF 11111111111111111111110032 bits1FF 246824689 bits32 bits16 Kline Cache112233442468246832 bits16 MByte Main MemoryNote: Memory address values arein binary representation;other values are in hexadecimalFigure 4.15 Two-Way Set Associative Mapping Example 2016 Pearson Education, Inc., Hoboken, NJ. All rights reserved.
2016 Pearson Education, Inc., Hoboken, NJ. All rights reserved.
Figure 4.15 shows our example using set-associativemapping with two lines in each set, referred to as twoway set-associative. The 13-bit set number identifies a unique set of twolines within the cache. It also gives the number of theblock in main memory, modulo 213. This determinesthe mapping of blocks into lines. Thus, blocks 000000, 008000, , FF8000 of mainmemory map into cache set 0. 2016 Pearson Education, Inc., Hoboken, NJ. All rights reserved.
Any of those blocks can be loaded into either of thetwo lines in the set. Note that no two blocks thatmap into the same cache set have the same tagnumber. For a read operation, the 13-bit set number is usedto determine which set of two lines is to beexamined. Both lines in the set are examined for a match withthe tag number of the address to be accessed. Inthe extreme case of v m , k 1, the setassociative technique reduces to direct mapping,and forv 1, k m , it reduces toassociative mapping. 2016 Pearson Education, Inc., Hoboken, NJ. All rights reserved.
The use of two lines per set (v m /2, k 2) is themost common set-associative organization. Itsignificantly improves the hit ratio over directmapping. Four- way set associative (v m /4, k 4) makes amodest additional improvement for a relatively smalladditional cost [MAYB84, HILL89]. Furtherincreases in the number of lines per set have littleeffect. 2016 Pearson Education, Inc., Hoboken, NJ. All rights reserved.
1.00.90.8Hit 256k512kCac
Design constraints on a computer’s memory can be summed up by three questions: How much, how fast, how expensive There is a trade-off among capacity, access time, and cost Faster access time, greater cost per bit Greater capacity, smaller cost per bit Greater capacity, slower access time
COMPUTER ORGANIZATION (3-1-0 ) . Computer System Architecture, Morris Mano, PHI Reference Books: 1. Computer Architecture & Organization, William Stallings, Pearson Prerequisite 1. Knowledge of digital circuit 2. Functionality of various gates . Computer Architecture and Organization, by - John P. Hayes, 3rd Edition, Mc Graw Hill .
Nov 06, 2012 · William Stallings Computer Organization and Architecture 7th Edition Chapter 6 External Memory Types of External Memory Magnetic Disk —RAID —Removable Optical —CD-ROM —CD-Recorda
Larry Stallings Paso Robles 2 Iva Wilcox San Luis Obispo 3 02 - Cut Flowers ············· 3 records Larry Stallings Paso Robles 1 Rick Hicks Templeton 2 Joe Sabol San Luis Obispo 3 03 - Potted Plants ············· 3 records Larry Stallings Paso Robles 1
CRYPTOGRAPHY AND NETWORK SECURITY, SIXTH EDITION A tutorial and survey on network security technology. Each of the basic building blocks of network security, . THE WILLIAM STALLINGS BOOKS ON COMPUTER AND DATA COMMUNICATIONS TECHNOLOGY. Foundations of Modern Networking SDN, NFV, QoE, IoT, and Cloud William Stallings With contributions by:
Dr. Mohammed Arafah William Stallings “Data and Computer Communications” 19 Asynchronous Transmission – Example 1 Construct the transmitted frame using asynchronous transmission mode which contains the following data: GO. Assume that the number of bits per character is 8, the number
Chapter 1 - William Stallings, Data and Computer Communications, 8/e Author: Dr Lawrie Brown Subje
William Stallings Book: Chapter 5 OS – has processes and threads Multiprogramming: The management of multiple processes within in a uniprocessor system Distributed processing: The management of multiple processes executing on multiple distributed computer systems. Fundamental to OS is
David A. Patterson and John L. Hennessey, “Computer organization and design‟, . and Safat G. Zaky, “Computer Organisation“, VI th edition, Mc Graw-Hill Inc, 2012. 2. William Stallings “Computer Organization and Architecture” , Seventh Edition , Pearson . John P. Hayes, “Computer Architecture and Organization”, Third Edition .
