#ACHE #OHERENCE 0ROTOCOLS IN .5-! -ULTIPRO CESSORS
.5-!다중 프로세서에서의 캐쉬 일관성 프로토콜
3ANG -AN -OH 모상만 #OMPUTER 3YSTEM $EPARTMENT 하드웨어구조연구팀 선임연구원 7OO *ONG (AHN 한우종 #OMPUTER 3YSTEM $EPARTMENT 하드웨어구조연구팀 책임연구원 팀장 3UK (AN 9OON 윤석한 #OMPUTER 3YSTEM $EPARTMENT 컴퓨터시스템연구부 책임연구원 부장
2ECENTLY SCALABLE MULTIPROCESSOR SYSTEMS ARE ACTIVELY DEVELOPED FOR GENERAL PURPOSE COMPUTING WHICH ARE BASED ON DISTRIBUTED SHARED MEMORY $3- ARCHITECTURE TO BOOST UP BOTH PROGRAMMABILITY AND SCALABILITY )N THIS PAPER WE SURVEY AND ANALYZE CACHE COHERENCE PROTOCOLS IN NON UNIFORM MEMORY ACCESS .5-! MULTIPROCESSOR SYSTEMS
)N PARTICULAR IT HAS BEEN EASILY INFERRED THAT SPECIALIZED HARDWARE SUITABLE FOR .5-! MULTIPROCESSOR SYSTEMS WITH COMMODITY SYMMETRIC MULTIPROCESSORS 3-0S IS HIGHLY REQUIRED 4HE CACHE COHERENCE PROTOCOL COMBINED WITH SPECIALIZED HARDWARE CAN SIGNI`CANTLY IMPROVE THE PERFORMANCE AND SCALABILITY OF .5-! MULTIPROCESSOR SYSTEMS PROVIDING BETTER PROGRAMMABILITY
) )NTRODUCTION
0ARALLEL COMPUTING SYSTEMS WITH MULTI PLE PROCESSORS ARE USUALLY CLASSI`ED INTO TWO LARGE GROUPS NAMELY SHARED MEMORY MULTI PROCESSORS AND MESSAGE PASSING MULTICOMPUT ERS 4HE MAJOR DISTINCTION BETWEEN MULTI PROCESSORS AND MULTICOMPUTERS LIES IN MEMORY SHARING AND THE MECHANISMS USED FOR INTERPRO CESSOR COMMUNICATION ;=
)N A SHARED MEMORY MULTIPROCESSOR SYSTEM A GLOBAL PHYSICAL MEMORY IS EQUALLY ACCESSIBLE TO ALL PROCESSORS !N IMPORTANT ADVANTAGE OF SUCH A SYSTEM IS THE GENERAL AND CONVENIENT PROGRAMMING MODEL THAT ENABLES SIMPLE DATA SHARING THROUGH A UNIFORM MECHANISM OF READ ING AND WRITING SHARED VARIABLES IN THE COM
MON MEMORY )N A MESSAGE PASSING MULTICOM PUTER SYSTEM MULTIPLE INDEPENDENT PROCESSING NODES WITH LOCAL MEMORY MODULES COMMUNI CATE WITH EACH OTHER THROUGH MESSAGE PASS ING -ESSAGE PASSING MULTICOMPUTER SYSTEMS ARE CLAIMED TO BE SCALABLE AND SYSTEMS WITH VERY HIGH COMPUTING POWER ARE POSSIBLE ;=
4HE CONCEPT OF DISTRIBUTED SHARED MEM ORY $3- TRIES TO COMBINE THE ADVANTAGES OF THE TWO APPROACHES ;= ! $3- SYSTEM LOGI CALLY IMPLEMENTS THE SHARED MEMORY MODEL IN A PHYSICALLY DISTRIBUTED MEMORY SYSTEM 4HE EASE OF PROGRAMMING AND THE PORTABILITY OF SHARED MEMORY SYSTEMS ARE PRESERVED )N AD DITION THE SCALABILITY AND COST E_ECTIVENESS OF UNDERLYING MESSAGE PASSING SYSTEMS ARE ALSO
INHERITED 4HE MAIN OBJECTIVE OF RESEARCH IN
$3- SYSTEMS IS THE DEVELOPMENT OF GENERAL APPROACHES THAT MINIMIZE THE AVERAGE ACCESS TIME TO SHARED DATA WHILE MAINTAINING DATA CONSISTENCY
$ESIGNING AND PROGRAMMING MULTIPROCES SOR SYSTEMS CORRECTLY AND EbCIENTLY POSE COM PLEX PROBLEMS 3YNCHRONIZING PROCESSES MAIN TAINING DATA COHERENCE AND ORDERING EVENTS IN A MULTIPROCESSOR ARE ISSUES THAT MUST BE AD DRESSED FROM THE HARDWARE DESIGN LEVEL UP TO THE PROGRAMMING LANGUAGE LEVEL ;= 4HERE ARE ALSO SOME IMPORTANT ISSUES SUCH AS SCHEDULING AND PARTITIONING
&IG ! SHARED MEMORY MULTIPROCESSOR SYSTEM WITH PRI VATE CACHES
#ACHE COHERENCE PROBLEMS EXIST IN MULTI PROCESSORS WITH PRIVATE CACHES AND ARE CAUSED BY THREE FACTORS SHARING OF WRITABLE DATA PRO CESS MIGRATION AND )/ ACTIVITY ;= &IGURE SHOWS A SHARED MEMORY MULTIPROCESSOR SYSTEM WITH PRIVATE CACHES IN WHICH MULTIPLE PRO CESSORS AND SHARED MEMORY MODULES ARE IN TERCONNECTED THROUGH AN INTERCONNECTION NET WORK ! MULTIPROCESSOR SYSTEM WITH MULTIPLE
CACHES FACES THE PROBLEM OF MAKING SURE THAT ALL COPIES OF A GIVEN PIECE OF INFORMATION ARE THE SAME ! MODI`CATION OF ANY ONE OF THESE COPIES SHOULD SOMEHOW BE REaECTED IN ALL OTH ERS ;= 4HIS IS CALLED THE CACHE COHERENCE PROB LEM OR THE CACHE CONSISTENCY PROBLEM ! SYS TEM OF CACHES IS SAID TO BE COHERENT IF EVERY READ BY ANY PROCESSOR `NDS A VALUE PRODUCED BY THE LAST PREVIOUS WRITE NO MATTER WHICH PROCESSOR PERFORMED IT ;= 4HE IMPORTANCE OF THE CACHE COHERENCE PROBLEM IS EMPHASIZED BY THE FACT THAT NOT ONLY IN THE CACHE COHERENCE SOLUTION NECESSARY FOR CORRECT PROGRAM EXECU TION BUT IT CAN HAVE A SIGNI`CANT IMPACT ON SYSTEM PERFORMANCE
)N 3ECTION )) OF THIS PAPER THE CACHE COHER ENCE PROTOCOLS FOR SHARED MEMORY MULTIPROCES SORS ARE DESCRIBED SYSTEMATICALLY 4HE .5-!
MULTIPROCESSOR SYSTEMS AND THE CACHE COHER ENCE MECHANISMS FOR CACHE COHERENT .5-!
SYSTEMS ARE PRESENTED IN 3ECTION ))) )N 3ECTION )6 PAST RELATED WORKS ON .5-! MULTIPRO CESSOR SYSTEMS AND CACHE COHERENCE PROTOCOLS ARE GIVEN AND ANALYZED IN DETAIL WHICH INCLUDE RESEARCH PROTOTYPES AND COMMERCIAL SYSTEMS
!ND SOME RESEARCH ISSUES AND THE CONCLUDING REMARKS OF THIS PAPER ARE COVERED IN 3ECTION 6
)) #ACHE #OHERENCE 0ROTOCOLS
4HERE ARE TWO POLICIES FOR MAINTAINING CACHE COHERENCE WRITE INVALIDATE AND WRITE UPDATE POLICIES ;= &IGURE SHOWS THE CON CEPTUAL BEHAVIOR OF WRITE OPERATIONS BOTH FOR WRITE INVALIDATE POLICY AND FOR WRITE UPDATE
Interconnection network
Memory Memory Memory
Proc.
Cache
Proc.
Cache
Proc.
Cache
&IG 4WO WRITE POLICIES FOR MAINTAINING CACHE COHERENCE
POLICY 4HE WRITE INVALIDATE POLICY MAINTAINS COHERENCE OF MULTIPLE COPIES IN THE FOLLOWING WAY 2EAD REQUESTS ARE CARRIED OUT LOCALLY IF A COPY OF THE BLOCK EXISTS 7HEN A PROCESSOR UP DATES A BLOCK HOWEVER ALL OTHER COPIES ARE IN VALIDATED 4HE WRITE UPDATE POLICY MAINTAINS COHERENCE DI_ERENTLY )NSTEAD OF INVALIDATING ALL COPIES IT UPDATES THEM 7HETHER THE MEM ORY COPY IS UPDATED OR NOT DEPENDS ON HOW THIS PROTOCOL IS IMPLEMENTED
! VARIETY OF MECHANISMS HAVE BEEN PRO POSED FOR SOLVING THE CACHE COHERENCE PROBLEM
4HE OPTIMAL SOLUTION FOR A GIVEN MULTIPROCES SOR SYSTEM DEPENDS ON SEVERAL FACTORS SUCH AS THE SIZE OF THE SYSTEM THE ANTICIPATED USAGE OF THE SYSTEM AND THE DESIRED SYSTEM COST ;=
4HE CACHE COHERENCE MECHANISMS ARE MAINLY CLASSI`ED INTO TWO CLASSES SOFTWARE BASED AND HARDWARE BASED SOLUTIONS
3OFTWARE BASED SOLUTIONS GENERALLY RELY ON THE ACTIONS OF THE PROGRAMMER COMPILER OR OPERATING SYSTEM IN DEALING WITH THE COHER ENCE PROBLEM ;= 4HE SIMPLEST WAY IS TO
DECLARE NON CACHEABLE PAGES OF SHARED DATA
-ORE ADVANCED METHODS ALLOW THE CACHING OF SHARED DATA AND ACCESSING THEM ONLY IN CRITICAL SECTIONS IN MUTUALLY EXCLUSIVE WAY 3OFTWARE SCHEMES ARE GENERALLY LESS EXPENSIVE THAN THEIR HARDWARE COUNTERPARTS 3OME DISADVANTAGES HOWEVER ARE EVIDENT WHERE INEVITABLE INEb CIENCIES ARE INCURRED SINCE THE COMPILER ANAL YSIS IS UNABLE TO PREDICT THE aOW OF PROGRAM EXECUTION ACCURATELY AND CONSERVATIVE ASSUMP TIONS HAVE TO BE MADE
(ARDWARE BASED SOLUTIONS EbCIENTLY SUP PORT THE FULL RANGE FROM SMALL TO LARGE SCALE MULTI PROCESSORS ;= !LTHOUGH THEY REQUIRE AN INCREASED HARDWARE COMPLEXITY THEIR COST IS WELL JUSTI`ED BY THE SIGNI`CANT ADVANTAGES
(ARDWARE SCHEMES DEAL WITH THE COHERENCE PROBLEM BY DYNAMIC RECOGNITION OF INCONSIS TENCY CONDITIONS FOR SHARED DATA ENTIRELY AT RUN TIME "EING TOTALLY TRANSPARENT TO SOFT WARE HARDWARE PROTOCOLS FREE THE PROGRAMMER AND COMPILER FROM ANY RESPONSIBILITY FOR COHER ENCE MAINTENANCE AND IMPOSE NO RESTRICTIONS
Cache
X X′
Cache
X (I)
Cache
X (I)
Data
X (I)
Memory Interconnection network
(I): Invalid state
Cache
X X′
Cache
X X′
Cache X X′
Data
X X′
Memory Interconnection network
(a) Write-invalidate policy (b) Write-update policy
invalidate update
ON ANY LAYER OF SOFTWARE 4ECHNOLOGICAL AD VANCES HAVE MADE THEIR COST QUITE ACCEPTABLE
(ARDWARE CACHE COHERENCE SCHEMES CAN BE PRINCIPALLY DIVIDED INTO TWO LARGE GROUPS
SNOOPY AND DIRECTORY PROTOCOLS ;= )N SNOOPY CACHE COHERENCE PROTOCOLS COHERENCE MAINTE NANCE IS BASED ON THE ACTIONS OF LOCAL CACHE CONTROLLERS AND DISTRIBUTED LOCAL STATE INFORMA TION .EITHER CENTRALIZED CONTROLLER NOR GLOBAL STATE INFORMATION IS EMPLOYED 3O ALL THE AC TIONS FOR THE CURRENTLY SHARED BLOCK MUST BE ANNOUNCED TO ALL OTHER CACHES VIA BROADCAST CAPABILITY ,OCAL CACHE CONTROLLERS ARE ABLE TO SNOOP ON THE NETWORK AND TO RECOGNIZE THE AC TIONS AND CONDITIONS FOR COHERENCE VIOLATION WHICH IMPOSE SOME REACTIONS IN ORDER TO PRE SERVE COHERENCE
3NOOPY PROTOCOLS ARE IDEALLY SUITED FOR MUL TIPROCESSORS THAT USE A SHARED BUS AS A GLOBAL INTERCONNECT SINCE THE SHARED BUS PROVIDES VERY INEXPENSIVE AND FAST BROADCAST ;= 4HEY ARE ALSO KNOWN FOR BEING VERY COST E_ECTIVE AND aEXIBLE SCHEMES (OWEVER COHERENCE ACTIONS ON THE SHARED BUS INCREASE THE BUS TRAbC AND MAKE THE BUS SATURATION MORE ACUTE #ONSE QUENTLY ONLY SYSTEMS WITH A SMALL TO MEDIUM NUMBER OF PROCESSORS CAN BE SUPPORTED BY SNOOPY PROTOCOLS
)N DIRECTORY BASED CACHE COHERENCE PROTO COLS THE GLOBAL SYSTEM WIDE STATE INFORMATION RELEVANT FOR COHERENCE MAINTENANCE IS STORED IN SOME KIND OF A DIRECTORY ;= 4HE RESPONSIBIL ITY OF COHERENCE IS PREDOMINANTLY DELEGATED TO A CENTRALIZED DIRECTORY CONTROLLER THAT IS USU ALLY A PART OF THE MAIN MEMORY CONTROLLER
5PON THE INDIVIDUAL REQUESTS OF THE LOCAL CACHE
CONTROLLERS THE DIRECTORY CONTROLLER CHECKS THE DIRECTORY AND ISSUES NECESSARY COMMANDS FOR DATA TRANSFER BETWEEN MEMORY AND CACHES OR BETWEEN CACHES THEMSELVES )T IS ALSO RESPON SIBLE FOR KEEPING STATE INFORMATION UP TO DATE SO EVERY LOCAL ACTION THAT CAN A_ECT THE GLOBAL STATE OF THE BLOCK MUST BE REPORTED TO THE CEN TRAL DIRECTORY CONTROLLER "ESIDES THE GLOBAL DI RECTORY MAINTAINED BY THE CENTRAL CONTROLLER PRIVATE CACHES STORE SOME LOCAL STATE INFOR MATION ABOUT CACHED BLOCKS $IRECTORY BASED CACHE COHERENCE PROTOCOLS ARE PRIMARILY SUIT ABLE FOR MULTIPROCESSORS WITH GENERAL INTERCON NECTION NETWORKS ;=
!GARWAL ET AL ;= INTRODUCED ONE USE FUL CLASSI`CATION OF DIRECTORY SCHEMES DENOT ING THEM AS $IRI8 WHERE I IS THE NUMBER OF POINTERS AND 8 IS " OR ." FOR BROADCAST AND NON BROADCAST SCHEMES RESPECTIVELY
4HE DI_ERENT aAVORS OF DIRECTORY PROTOCOLS FALL UNDER THREE PRIMARY CATEGORIES FULL MAP DIRECTORIES LIMITED DIRECTORIES AND CHAINED DI RECTORIES ;= &IGURE SHOWS THE THREE TYPES OF DIRECTORY ORGANIZATIONS &ULL MAP DIRECTORIES STORE ENOUGH STATE ASSOCIATED WITH EACH BLOCK IN GLOBAL MEMORY SO THAT EVERY CACHE IN THE SYSTEM CAN SIMULTANEOUSLY STORE A COPY OF ANY BLOCK OF DATA 4HAT IS EACH DIRECTORY ENTRY CONTAINS . POINTERS WHERE . IS THE NUMBER OF PROCESSORS IN THE SYSTEM ,IMITED DIREC TORIES DI_ER FROM FULL MAP DIRECTORIES IN THAT THEY HAVE A `XED NUMBER OF POINTERS PER ENTRY REGARDLESS OF THE NUMBER OF PROCESSORS IN THE SYSTEM ,IMITED DIRECTORY PROTOCOLS ARE DE SIGNED TO SOLVE THE DIRECTORY SIZE PROBLEM 2E STRICTING THE NUMBER OF SIMULTANEOUSLY CACHED
&IG 4HREE TYPES OF DIRECTORY ORGANIZATIONS
COPIES OF ANY PARTICULAR BLOCK OF DATA LIMITS THE GROWTH OF THE DIRECTORY TO A CONSTANT FAC TOR #HAINED DIRECTORIES EMULATE THE FULL MAP SCHEMES BY DISTRIBUTING THE DIRECTORY AMONG THE CACHES #HAINED DIRECTORIES KEEP TRACK OF
SHARED COPIES OF DATA BY MAINTAINING A CHAIN OF DIRECTORY POINTERS AND THEY DO NOT UNTILIZE A BROADCAST MECHANISMS 4HESE SCHEMES REAL IZE THE SCALABILITY OF LIMITED DIRECTORIES WITHOUT RESTRICTING THE NUMBER OF SHARED COPIES OF DATA BLOCKS
))) .5-! 3YSTEMS AND #ACHE #OHER ENCE
-ULTIPROCESSOR SYSTEMS ARE SUITABLE FOR GENERAL PURPOSE MULTIUSER APPLICATIONS WHERE PROGRAMMABILITY IS THE MAJOR CON CERN 3HARED MEMORY MULTIPROCESSORS ARE ROUGHLY CATEGORIZED INTO TWO LARGE MODELS
THE UNIFORM MEMORY ACCESS 5-! MODEL AND NON UNIFORM MEMORY ACCESS .5-!
MODEL ;= )N A 5-! MULTIPROCESSOR MODEL THE PHYSICAL MEMORY IS UNIFORMLY SHARED BY ALL THE PROCESSORS !LL PROCESSORS HAVE EQUAL ACCESS TIME TO ALL MEMORY WORDS WHICH IS WHY IT IS CALLED UNIFORM MEMORY ACCESS
7HEN ALL PROCESSORS HAVE EQUAL ACCESS TO ALL PERIPHERAL DEVICES THE SYSTEM IS CALLED A SYM METRIC MULTIPROCESSOR 3-0 )N THIS CASE ALL THE PROCESSORS ARE USUALLY CAPABLE OF RUNNING THE EXECUTION PROGRAMS SUCH AS THE /3 KERNAL AND )/ SERVICE ROUTINES
! .5-! MULTIPROCESSORS IS A SHARED MEMORY SYSTEM IN WHICH THE ACCESS TIME VARIES WITH THE LOCATION OF THE MEMORY WORD 4HE SHARED MEMORY IS PHYSICALLY DISTRIBUTED TO ALL PROCESSORS CALLED LOCAL MEMORIES 4HE COLLEC TION OF ALL LOCAL MEMORIES FORMS A GLOBAL AD DRESS SPACE ACCESSIBLE BY ALL PROCESSORS )T IS FASTER TO ACCESS A LOCAL MEMORY WITH A LOCAL
Cache X
Memory
Directory
Interconnection network
(a) Full-map directory
Cache X Cache
X
Data X
Cache X
Memory
Directory
Interconnection network
(b) Limited directory
Cache Cache
X
Data X
Cache X
Memory
Directory
Interconnection network
(c) Chained directory
Cache Cache
Data X X
PROCESSOR 4HE ACCESS OF REMOTE MEMORY AT TACHED TO OTHER PROCESSORS TAKES LONGER DUE TO THE ADDED DELAY THROUGH THE INTERCONNECTION NETWORK
!S A VARIATION OF .5-! MODEL FOR MUL TIPROCESSORS A CACHE COHERENT NON UNIFORM MEMORY ACCESS ## .5-! MODEL CAN BE SPECI`ED WITH DISTRIBUTED SHARED MEMORY AND CACHE COHERENCE MECHANISM ;= ! MAJOR CON CERN OF ## .5-! MULTIPROCESSOR SYSTEMS IS THE CACHE COHERENT MEMORY ACCESS TRANSPARENT TO ALL THE PROCESSORS ,ATENCY TOLERANCE FOR RE MOTE MEMORY ACCESS IS ALSO A MAJOR LIMITATION OF ## .5-! SYSTEMS
&IG 4YPICAL EXAMPLE OF AN 3-0 BASED ## .5-! MUL TIPROCESSOR SYSTEM
!S MENTIONED IN THE ABOVE A MAJOR SHORTCOMING OF MULTIPROCESSORS IS THE LACK OF SCALABILITY )T IS RATHER DIbCULT TO BUILD LARGE SCALE MACHINES USING CENTRALIZED SHARED MEMORY MODEL !S A RESULT $3- SYSTEMS HAVE BEEN STUDIED AND DEVELOPED FOR GENERAL PURPOSE COMPUTING 3-0 BASED ## .5-!
SYSTEMS ARE HIERARCHICALLY STRUCTURED MULTI PROCESSOR MACHINES WHICH HAVE TWO LAYERS OF ARCHITECTURE 3-0 AND ## .5-! MOD ELS )N AN 3-0 BASED ## .5-! MULTI PROCESSOR SYSTEM 3-0 NODES ARE INTERCON NECTED VIA THE INTERCONNECTION NETWORK BASED ON THE CACHE COHERENT NON UNIFORM MEMORY ACCESS MODEL !LL PROCESSORS BELONGING TO THE SAME 3-0 NODE ARE ALLOWED TO UNIFORMLY AC CESS THE NODE MEMORY MODULES !LL 3-0 NODES HAVE ACCESS TO ALL PHYSICALLY DISTRIBUTED MEMORIES (OWEVER THE ACCESS TIME TO RE MOTE MEMORIES IS LONGER THAN THAT TO THE LO CAL SHARED MEMORY &IGURE SHOWS A TYPICAL EXAMPLE OF AN 3-0 BASED ## .5-! MULTI PROCESSOR SYSTEM WHERE THE BUS BASED 3-0 NODES ARE INTERCONNECTED THROUGH AN INTER CONNECTION NETWORK 4HE AVAILABILITY OF COST E_ECTIVE COMMODITY 3-0S MAKES THEM AN ATTRACTIVE CHOICE FOR ## .5-! DESIGNERS
)N 3-0 BASED ## .5-! MULTIPROCESSOR SYSTEMS MULTILEVEL CACHE HIERARCHY SEEMS TO BE UNAVOIDABLE ;= ,OWER LEVELS OF SUCH A HI ERARCHY ARE SMALLER BUT FASTER CACHES 4HEIR TASK IS TO REDUCE MISS PENALTY 5PPER LEVEL CACHES ARE SLOWER BUT MUCH LARGER IN ORDER TO ATTAIN HIGHER HIT RATIO AND REDUCE THE TRAbC ON THE INTERCONNECTION NETWORK
4HERE ARE TWO ALTERNATIVES IN IMPLEMENT ING A CACHE COHERENCE CONTROLLER FOR MULTIPRO CESSOR SYSTEMS IN PARTICULAR FOR 3-0 BASED
## .5-! MULTIPROCESSOR SYSTEMS A CUSTOM HARDWARE COHERENCE CONTROLLER AND A COHERENCE CONTROLLER BASED ON COMMODITY PROTOCOL PRO CESSORS ;= #USTOM HARDWARE COHERENCE CON TROLLERS CAN BE EbCIENTLY IMPLEMENTED FOR SPE
Proc.
Memory Bus
Interconnection network Cache
Proc.
Cache
Cache coherence
adapter
Proc.
Memory Bus Cache
Proc.
Cache
Cache coherence
adapter
CI`C TARGET SYSTEMS AND RUN FASTER #OHERENCE CONTROLLERS BASED ON PROTOCOL PROCESSORS ALLOW THE COHERENCE PROTOCOL TO BE TAILORED TO SPE CI`C APPLICATION NEEDS
4HE CACHE COHERENCE SCHEMES THAT COM BINE THE PRINCIPLES AND ADVANTAGES OF BOTH SNOOPY AND DIRECTORY PROTOCOLS ON DI_ERENT LEVELS MAY BE HIGHLY E_ECTIVE FOR LARGE SCALE SHARED MEMORY MULTIPROCESSORS ;= )N MOST OF 3-0 BASED ## .5-! MULTIPROCESSOR SYS TEMS DIRECTORY PROTOCOLS ARE USED FOR INTERN ODE CACHE COHERENCE SINCE THE SYSTEMS HAVE MANY PROCESSORS AND GENERAL INTERCONNECTION NETWORKS
)6 2ELATED 7ORKS
3OME RESEARCH PROTOTYPES AND COMMERCIAL SYSTEMS OF .5-! MULTIPROCESSORS BASED ON 3-0 NODES HAVE BEEN DEVELOPED 4YPICAL EX AMPLES OF SUCH SYSTEMS ARE $!3( ;= ;=
!352! ;= .5-!CHINE ;= AND .5-!
1 ;= .EW MACHINES BASED ON 3-0 BASED
## .5-! MULTIPROCESSORS ARE BEING DEVEL OPED OR SHIPPED BY SOME COMPANIES TODAY
4HESE KINDS OF MULTIPROCESSORS TYPICALLY USE THE LATEST COMMODITY MICROPROCESSORS AVAIL ABLE AT THE TIME THEY ARE SHIPPED -ORE OVER BECAUSE OF COST E_ECTIVENESS AND TIME TO MARKET REQUIREMENTS O_ THE SHELF COMMODITY 3-0S ARE WIDELY USED AS COMPUTING NODES IN DEVELOPING THE CACHE COHERENT .5-! MULTI PROCESSOR SYSTEMS
4HE $!3( PROTOTYPE SYSTEM WAS AN OUTGROWTH OF RESEARCH INTO SCALABLE SHARED MEMORY MULTIPROCESSING AT 3TANFORD 5NIVER
SITY 4HE PRIMARY GOAL OF BUILDING THE MACHINE WAS A BETTER UNDERSTANDING OF THE DESIGN ISSUES AND FEASIBILITY OF THIS CLASS OF MACHINES ;=
;= 4HE SYSTEM IS LIMITED TO A r CON`G URATION WITH NODES DUE TO THE CONSTRAINTS IN MEMORY ADDRESSING OF THE BASE NODE )N THE $!3( PROTOTYPE 3-0 NODES ARE INTERCON NECTED VIA A PAIR OF $ MESH NETWORKS 4HE GLOBAL SHARED MEMORY IS DISTRIBUTED AMONG THE 3-0 NODES CALLED PROCESSING NODES %ACH NODE CONTAINS FOUR 2 PROCESSORS WITH A
+BYTE WRITE BACK CACHE PER PROCESSOR A PORTION OF GLOBAL MEMORY AND LOCAL )/ DE VICES 4HE SIZE OF EACH NODES MEMORY PARTI TION IS ONLY -BYTES 4HE TWO MESH NET WORKS ARE CALLED REQUEST NETWORK AND REPLY NETWORK RESPECTIVELY EACH OF WHICH GUARAN TEES POINT TO POINT DELIVERY OF MESSAGES WITH OUT DEADLOCKS
! BUS BASED SNOOPY SCHEME IS USED TO KEEP CACHES COHERENT WITHIN AN 3-0 NODE WHILE INTERNODE CACHE COHERENCE IS MAIN TAINED USING A DISTRIBUTED DIRECTORY BASED COHERENCE PROTOCOL 4HE $!3( CACHE COHER ENCE PROTOCOL IS AN INVALIDATION BASED OWNER SHIP PROTOCOL ! MEMORY BLOCK CAN BE IN ONE OF THREE STATES AS INDICATED BY THE AS SOCIATED FULL MAP DIRECTORY ENTRY UNCACHED SHARED REMOTE AND DIRTY REMOTE 4HE REMOTE ACCESS CACHE IS DIRECT MAPPED WRITE BACK CACHE WITH BYTE LINES WHICH CONTAINS ONLY
+BYTES OF REMOTE MEMORY DATA 4HE RE MOTE ACCESS CACHE OF +BYTES IS VERY SMALL AND ITS LINE SIZE OF BYTES IS ALSO RELATIVELY SHORT COMPARED TO THE PROCESSOR CACHE LINE SIZE OF BYTES $UE TO THE SMALL SIZE AND SHORT
LINES OF THE REMOTE ACCESS CACHE THE PERFOR MANCE OF THE CACHE COHERENCE PROTOCOL CAN BE DEGRADED 3LOW LOOKUP OF THE $2!- DIREC TORY AGAINST NODE BUS TRANSACTIONS IS ALSO A SHORTCOMING OF THE $!3( IMPLEMENTATION
!352! ;= IS A LARGE 3-0 BASED DISTRIBUTED SHARED MEMORY MULTIPROCESSOR SYSTEM DEVELOPED AT +YOTO 5NIVERSITY AND +UBOTA #ORPORATION )T CONSISTS OF UP TO
NODES INTERCONNECTED THROUGH AN INTERNODE NETWORK 4HE !352! NODE IS CON`GURED AS A BUS BASED 3-0 WITH UP TO EIGHT 2-#
PROCESSORS A -BYTE LOCAL SHARED MEMORY A 'BYTE GLOBAL SHARED MEMORY AND )/
DEVICES %ACH PROCESSOR HAS A -BYTE WRITE BACK CACHE 7HILE THE LOCAL SHARED MEMORY IS SHARED ONLY BY UP TO EIGHT PROCESSORS IN THE NODE THE GLOBAL SHARED MEMORY IS SHARED BY ALL NODES 3EVERAL CANDIDATE TOPOLOGIES FOR THE INTERNODE NETWORK WERE CONSIDERED FROM WHICH VARIOUS CON`GURATIONS FOR THE NETWORK COULD BE CHOSEN TO OBTAIN A TRANSFER RATE OF
-BYTES PER SECOND FOR EACH LINK
7HILE INTRANODE CACHE COHERENCE IS MAIN TAINED BY A SNOOPY PROTOCOL INTERNODE CACHE COHERENCE IS DONE BY A FULL MAP DIRECTORY PRO TOCOL 4HE 3-0 NODE HAS A REMOTE ACCESS CACHE CALLED GLOBAL CACHE WHICH IS A WAY SET ASSOCIATIVE -BYTE WRITE BACK CACHE WITH
BYTE LINES )N THE DIRECTORY BASED INTERN ODE CACHE COHERENCE PROTOCOL A CACHED MEM ORY BLOCK CAN BE IN ONE OF THREE STATES IN VALID CLEAN AND DIRTY 4HE BYTE LINE OF THE REMOTE ACCESS CACHE IS TOO LONG WHICH CAN MAKE FALSE SHARING PROBLEM BECOME MORE SERI OUS 4HE MEMORY OVERHEAD OF THE DIRECTORY IS
A SIGNI`CANT CONSTRAINT SINCE THE SYSTEM CON NECTS UP TO NODES USING THE FULL MAP DI RECTORY SCHEME 3UCH CONSTRAINTS MAY RESTRICT THE SCALABILITY AND DEGRADE THE PERFORMANCE OF THE !352! SYSTEM
.5-!CHINE ;= IS A CACHE COHERENT SHARED MEMORY MULTIPROCESSOR DESIGNED AT 5NIVERSITY OF 4ORONTO )T IS AN 3-0 BASED
## .5-! MACHINE DESIGNED TO CONNECT UP TO NODES VIA A HIERARCHY OF UNIDIRECTIONAL BIT PARALLEL RINGS %ACH BUS BASED 3-0 NODE CONSISTS OF FOUR 2 PROCESSORS A 'BYTE MEMORY AND )/ DEVICES 4HE 2 PROCES SOR INTERNALLY CONTAINS A -BYTE WRITE BACK CACHE 4HE INTERNODE RINGS ARE DIVIDED INTO TWO LEVELS OF HIERARCHY A GLOBAL RING AND LOCAL RINGS
4HE .5-!CHINE CACHE COHERENCE PROTO COL EMPLOYS A WRITE BACK AND WRITE INVALIDATE SCHEME ! SNOOPY COHERENCE PROTOCOL IS USED FOR FOUR PROCESSORS IN EACH 3-0 NODE 4O MAINTAIN INTERNODE CACHE COHERENCE A HIERAR CHICAL TWO LEVEL FULL MAP DIRECTORY EXISTS FOR GLOBAL AND LOCAL RINGS %ACH 3-0 NODE CON TAINS A REMOTE ACCESS CACHE CALLED NETWORK CACHE WHICH IS A WRITE BACK -BYTE CACHE
&OUR BASIC STATES ARE DE`NED FOR A CACHE LINE IN A MEMORY MODULE OR A REMOTE ACCESS CACHE
LOCAL VALID LOCAL INVALID REMOTE VALID AND RE MOTE INVALID 4HE TWO LEVEL FULL MAP DIRECTORY INEVITABLY INCLUDES THE COMPLICATED CONTROL OF THE CACHE COHERENCE PROTOCOL WHICH MAY BE A HURDLE IN MAINTAINING THE CACHE COHERENCE Eb CIENTLY 4HE HIERARCHICAL RING ARCHITECTURE ALSO HAS THE LATENCY PROBLEM SINCE MULTIPLE HOPS ARE SERIALIZED TO HAND OVER DATA
.5-! 1 ;= INITIALLY NAMED 34I.' IS A ## .5-! MULTIPROCESSOR SYSTEM DE SIGNED AND BUILT BY 3EQUENT #OMPUTER 3YS TEMS )NC ! KEY ENABLER OF THE .5-! 1 ARCHITECTURE IS THE O_ THE SHELF WAY 3-0 BUILDING BLOCK )T COMBINES UP TO
PROCESSOR 3-0S CALLED 1UADS USING A SCAL ABLE COHERENT INTERFACE 3#) INTERCONNECT
4HE 3-0 NODES ARE BASED ON THE )NTEL 0EN TIUM 0RO PROCESSOR AND EXTERNAL BUS IT DE
`NES )N ADDITION TO FOUR PROCESSORS EACH NODE MAY CONTAIN 'BYTES OF SYSTEM MEMORY AND )/ DEVICES 4HE 0ENTIUM 0RO PROCESSOR HAS A WAY SET ASSOCIATIVE +BYTE WRITE BACK CACHE WITH BYTE LINES 3#) BASED DUAL RINGS ARE USED FOR THE INTERNODE INTERCONNECTION NET WORK
7ITHIN AN 3-0 NODE CACHE COHERENCE IS MAINTAINED USING A SNOOPY CACHE COHERENCE PROTOCOL CALLED -%3) PROTOCOL %ACH NODE CON TAINS A BRIDGE BOARD CALLED )1 ,INK INITIALLY NAMED ,YNX THAT PLUGS INTO THE LOCAL 3-0 BUS )NCLUDED IN THE BOARD IS A WAY SET ASSOCIATIVE -BYTE WRITE BACK REMOTE AC CESS CACHE WITH BYTE LINES ! CHAINED DI RECTORY IMPLEMENTS A DIRECTORY BASED INTERN ODE CACHE COHERENCE PROTOCOL WHICH CONTAINS FORWARD AND BACKWARD POINTERS 4HAT IS A DOUBLY LINKED LIST DIRECTORY STRUCTURE IS USED TO MAINTAIN THE INTERNODE CACHE COHERENCE OVER THE 3#) BASED DUAL RINGS 4HE DIRECTORY STATE BITS INDICATE WHETHER EACH LINE IS HOME FRESH OR GONE )NHERENTLY THE CHAINED DIRECTORY CAN NOT ALLOW ANY DIRECT ACCESS TO ONE OF CHAINED CACHE DATA -OREOVER SIMULTANEOUS OR OUT OF ORDER INVALIDATIONS ARE ALSO IMPOSSIBLE SINCE
THE ARCHITECTURE DOES NOT HAVE ANY BROADCAST OR MULTICAST CAPABILITY !LTHOUGH THE DOUBLY LINKED LIST DIRECTORY STRUCTURE IMPROVES THE PERFORMANCE LIMITATION SUCH RESTRICTIONS MAY BE DRAWBACKS OF SCALABLE PERFORMANCE
/RIGIN;= ;= IS ALSO A ## .5-! MULTI PROCESSOR SYSTEM DESIGNED AND MANUFACTURED BY 3ILICON 'RAPHICS )NC (OWEVER EVERY NODE IS NOT AN 3-0 ARCHITECTURE IN THE /RIGIN SYS TEM 3O WE SIMPLY LOOK THROUGH KEY FEATURES OF THE SYSTEM .OW THE /RIGIN SYSTEM CONSISTS OF UP TO NODES INTERCONNECTED BY A SCAL ABLE #RAYLINK NETWORK %ACH NODE CONSISTS OF ONE OR TWO 2 PROCESSORS UP TO 'BYTES OF COHERENT MEMORY AND AN )/ SUBSYSTEM
)NTERNODE CACHE COHERENCE IS MAINTAINED BY AN INVALIDATION BASED FULL MAP DIRECTORY PRO TOCOL WHICH IS SIMILAR TO THE $!3( PROTOCOL
6 )SSUES AND #ONCLUDING 2EMARKS
!LTHOUGH SOME WORKS HAVE BEEN CARRIED OUT TO BUILD AND IMPROVE CACHE COHERENCE PROTO COLS IN DESIGNING .5-! MULTIPROCESSOR SYS TEMS THERE ARE STILL MANY RESEARCH ISSUES RE MAINED 4HE ISSUES ARE MAINLY DIVIDED INTO TWO LARGE CATEGORIES CORRECTNESS AND PERFOR MANCE 4HE CORRECTNESS ISSUE INCLUDES THE OR DERING AND CONSISTENCY OF MEMORY ACCESSES DEADLOCK LIVELOCK STARVATION AND THE VERI
`CATION OF CORRECTNESS 4HE PERFORMANCE IS SUE INCLUDES DATA ACCESS LATENCY BANDWIDTH AND PROTOCOL OVERHEAD 4HE LATENCY AND BAND WIDTH OF DATA ACCESSES ARE THE MAJOR CONCERNS
OF CACHE COHERENCE PROTOCOL DESIGN WHICH SIG NI`CANTLY INaUENCE SYSTEM PERFORMANCE 4HE PROTOCOL OVERHEAD IS TIGHTLY RELATED TO BOTH LA TENCY AND BANDWIDTH AND RESTRICTS THE Eb CIENCY OF CACHE COHERENCE PROTOCOLS
7E BELIEVE THERE ARE MANY WAYS TO IMPROVE PERFORMANCE CHARACTERISTICS SUCH AS LATENCY BANDWIDTH AND PROTOCOL OVERHEAD IN DESIGNING A CACHE COHERENCE PROTOCOL FOR .5-! MULTI PROCESSORS )N PARTICULAR MORE AGGRESSIVE AND SPECIALIZED HARDWARE SEEMS TO BE A USEFUL SO LUTION FOR HIGH PERFORMANCE IMPLEMENTATION
2ECENTLY O_ THE SHELF COMMODITY 3-0S LIKE )NTEL STANDARD HIGH VOLUME 3(6 SERVERS
;= ARE MORE POPULAR IN THE COMMERCIAL MAR KETPLACE -OREOVER WELL DEVELOPED SYSTEM AREA INTERCONNECTS BASED ON PACKET SWITCHED INTERCONNECTION NETWORKS PROVIDE HIGHER PER FORMANCE WITH SCALABILITY )N SUCH AN 3-0 BASED ## .5-! MULTIPROCESSOR SYSTEM A CACHE COHERENCE PROTOCOL IS SIGNI`CANTLY IM PORTANT IN THAT THE SCALABILITY OF SYSTEM PERFOR MANCE IS DETERMINED BY THE PERFORMANCE OF THE CACHE COHERENCE PROTOCOL 3PECIALIZED HARD WARE IS HIGHLY REQUIRED TO IMPROVE THE PERFOR MANCE OF THE CACHE COHERENCE PROTOCOL SINCE IT CAN PROVIDE THE CACHE COHERENT INTERCONNEC TION OF 3-0 NODES WITH MINIMAL DEGRADATION OF SCALABILITY !N EbCIENT DESIGN OF SPECIAL IZED HARDWARE ALSO MINIMIZES PROTOCOL OVER HEAD RESULTING IN THE IMPROVEMENT OF INTERNODE LATENCY AND BANDWIDTH
!S WE HAVE DESCRIBED SO FAR SOME RESEARCH AND DEVELOPMENT WORKS ON CACHE COHERENCE PROTOCOLS FOR .5-! MULTIPROCESSOR SYSTEMS HAVE BEEN CARRIED OUT FOR A DECADE (OWEVER
EVEN THOUGH SOME INNOVATIVE WORKS HAVE NOT ONLY TRIGGERED THE RESEARCH AND DEVELOPMENT OF SUCH ARCHITECTURES BUT ALSO ENABLED COMMER CIALLY SUCCESSFUL SYSTEMS THERE STILL EXIST MANY PROBLEMS AND ISSUES TO BE DIGGED AS MENTIONED
)N THIS PAPER WE HAVE PRESENTED CACHE COHERENCE PROTOCOLS IN .5-! MULTIPROCESSOR SYSTEMS )N PARTICULAR IT HAS BEEN EASILY IN FERRED THAT SPECIALIZED HARDWARE SUITABLE FOR
## .5-! MULTIPROCESSOR SYSTEMS WITH O_
THE SHELF COMMODITY 3-0S IS HIGHLY REQUIRED
4HE SPECIALIZED HARDWARE CAN MAKE A CACHE COHERENCE PROTOCOL ENABLE HIGH PERFORMANCE SYSTEM WIDE DATA ACCESSES WITH BETTER PRO GRAMMABILITY
4HERE EXIST MANY RESEARCH TOPICS TO BE DIGGED IN THE FUTURE INCLUDING THE VERI`CATION OF PROTOCOL CORRECTNESS PERFORMANCE EVALUA TION AND COMPARISON THE MINIMIZATION OF PRO TOCOL OVERHEAD DIRECTORY SIZE PROBLEMS AND COST TO PERFORMANCE TRADEO_S
2EFERENCES
;= + (WANG !DVANCED #OMPUTER !RCHITECTURE 0ARALLELISM 3CALABILITY 0ROGRAMMABILITY -C'RAW (ILL )NC .EW 9ORK PP p
;= * 0ROTIC - 4OMASEVIC AND 6 -ILUTINOVIC <!N /VERVIEW OF $ISTRIBUTED 3HARED -EMORY $ISTRIBUTED 3HARED -EMORY #ONCEPTS AND 3YSTEMS * 0ROTIC -
4OMASEVIC AND 6 -ILUTINOVIC %D )%%% #OMPUTER 3O CIETY 0RESS ,OS !LAMITOS #ALIFORNIA PP p
;= &! "RIGGS <3YNCHRONIZATION #OHERENCE AND %VENT /RDERING IN -ULTIPROCESSORS )%%% #OMPUTER 6OL
.O &EB PP p
;= !* 3MITH <#ACHE -EMORIES !#- #OMPUTING 3URVEYS 6OL .O 3EP PP p
;= 0 3TENSTROM <! 3URVEY OF #ACHE #OHERENCE 3CHEMES FOR -ULTIPROCESSORS )%%% #OMPUTER 6OL .O *UNE
PP p
;= $* ,ILJA <#ACHE #OHERENCE IN ,ARGE 3CALE 3HARED -EMORY -ULTIPROCESSORS )SSUES AND #OMPARISONS !#-
#OMPUTING 3URVEYS 6OL .O 3EP PP
p
;= - 4OMASEVIC AND 6 -ILUTINOVIC <(ARDWARE 3OLUTIONS FOR
#ACHE #OHERENCE IN 3HARED -EMORY -ULTIPROCESSOR 3YS TEMS 4HE #ACHE #OHERENCE 0ROBLEM IN 3HARED -EMORY -ULTIPROCESSORS (ARDWARE 3OLUTIONS - 4OMASEVIC AND 6 -ILUTINOVIC %D )%%% #OMPUTER 3OCIETY 0RESS ,OS
!LAMITOS #ALIFORNIA PP p
;= ! !GARWAL 2 3IMONI * (ENNESSY AND - (OROWITZ
<!N %VALUATION OF $IRECTORY 3CHEMES FOR #ACHE #OHER ENCE 0ROC TH )NT 3YMP ON #OMPUTER !RCHITECTURE (ONOLULU (AWAII -AY p*UNE PP p
;= $ #HAIKEN # &IELDS + +URIHARA AND ! !GARWAL
<$IRECTORY "ASED #ACHE #OHERENCE IN ,ARGE 3CALE -ULTI PROCESSORS )%%% #OMPUTER 6OL .O *UNE
PP p
;= -- -ICHAEL !+ .ANDA " ( ,IM AND -, 3COTT
<#OHERENCE #ONTROLLER !RCHITECTURES FOR 3-0 "ASED ##
.5-! -ULTIPROCESSORS 0ROC OF TH )NT 3YMP ON
#OMPUTER !RCHITECTURE $ENVER #OLORADO *UNE
PP p
;= $ ,ENOSKI * ,AUDON + 'HARACHORLOO ! 'UPTA AND
* (ENNESSY <4HE $IRECTORY "ASED #ACHE #OHERENCE 0RO TOCOL FOR THE $!3( -ULTIPROCESSOR 0ROC OF TH )NT
3YMP ON #OMPUTER !RCHITECTURE 3EATTLE 7ASHINGTON -AY PP p
;= $ ,ENOSKI * ,AUDON + 'HARACHORLOO 7 $ 7EBER
! 'UPTA * (ENNESSY - (OROWITZ AND 3 ,AM <4HE 3TANFORD $ASH -ULTIPROCESSOR )%%% #OMPUTER 6OL
.O -AR PP p
;= $ ,ENOSKI AND 7 $ 7EBER 3CALABLE 3HARED -EMORY -ULTIPROCESSING -ORGAN +AUFMANN 0UBLISHERS 3AN &RAN CISCO #ALIFORNIA PP p
;= 3 -ORI ( 3AITO - 'OSHIMA - 9ANAGIHARA 4 4ANAKA
$ &RASER + *OE ( .ITTA AND 3 4OMITA <! $ISTRIBUTED
3HARED MEMORY -ULTIPROCESSOR !352! 0ROC OF )NT
#ONF ON 3UPERCOMPUTING 0ORTLAND /REGON .OV
PP p
;= : 6RANESIC 3 "ROWN - 3TUMM 3 #ARANCI !
'RBIC 2 'RINDLEY - 'USAT / +RIEGER ' ,EMIEUX + ,OVELESS . -ANJIKIAN : :ILIC 4 !BDELRAHMAN
" 'AMSA 0 0EREIRA + 3EVCIK ! %LKATEEB AND 3 3RBLJIC 4HE .5-!CHINE -ULTIPROCESSOR 4ECHNICAL 2E PORT #32) #OMPUTER 3YSTEMS 2ESEARCH )NSTITUTE 5NIVERSITY OF 4ORONTO #ANADA
;= 4 ,OVETT AND 2 #LAPP <34I.' ! ## .5-! #OMPUTER 3YSTEM FOR THE #OMMERCIAL -ARKETPLACE 0ROC OF TH )NT 3YMP ON #OMPUTER !RCHITECTURE 0HILADELPHIA 0ENN SYLVANIA -AY p PP p
;= 4$ ,OVETT 2- #LAPP AND 2* 3AFRANET .5-!
1 !N 3#) "ASED %NTERPRISE 3ERVER 3EQUENT #OMPUTER 3YSTEMS )NC HTTPWWWSEQUENTCOMNEWSPAPERS
QNUMASCI CURRENT -AR
;= * ,AUDON AND $ ,ENOSKI <4HE 3') /RIGIN ! CC.5-!
(IGHLY 3CALABLE 3ERVER 0ROC OF TH )NT 3YMP ON
#OMPUTER !RCHITECTURE $ENVER #OLORADO *UNE p
PP p
;= 3ILICON 'RAPHICS )NC /RIGIN 4ECHNOLOGY HTTPWWW
SGICOMORIGINTECHNOLOGYHTML CURRENT -AR
;= )NTEL #ORPORATION 3TANDARD (IGH 6OLUME 3ERVERS
#HANGING THE 2ULES FOR "USINESS #OMPUTING HTTP
WWWINTELCOMSHVSERVERS CURRENT -AR
