5.3并行主存儲器

所謂并行主存儲器，是指在一個主存周期內可以并行讀取多個數據字的主存儲器。通常采用單體多字和交叉存取方式。尋址方式有單體多字尋址方式、多體存儲器的尋址方式和多體交叉尋址方式。下一頁上一頁5.3并行主存儲器所謂并行主存儲器，是指在一個

當并行的存儲器共用一套地址寄存器和地址譯碼電路時稱為單體方式，其結構原理圖如下。下一頁上一頁⒈單體多字尋址方式當并行的存儲器共用一套地址寄存器和地址譯碼電路時

多個并行存儲器與同一地址寄存器連接，所以同時被一個單元地址驅動，一次訪問讀出的是沿n個存儲器順序排列的n個字，故也稱單體多字方式。與單體單字結構的存儲器相比，單體多字尋址方式在存取速度方面有明顯的優點，因為，單體單字存儲器的每一個主存周期只能讀出一條指令或一個數據，在取指和讀取數據的周期內，CPU處于等待狀態，因此工作效率低。在本例所示的單體4字的尋址方式中，一次能讀出4個字長為w位的數據或指令，然后再以單字長的形式送給CPU執行。當然，若處理的數據不是連續地存放在主存中，或者在程序中經常使用轉移指令，單體多字尋址方式的效果就不顯著了。下一頁上一頁多個并行存儲器與同一地址寄存器連接，所以同時被一個單元地下一頁上一頁⒉多體存儲器的尋址方式下圖是多體存儲器原理圖下一頁上一頁⒉多體存儲器的尋址方式下圖是多體存儲器原理圖下一頁上一頁

計算機系統中的大容量主存是由多個存儲體組成的，每個存儲體都有自己的讀寫線路、地址寄存器和數據寄存器，能以同等的方式與CPU交換信息，每個存儲體容量相等，它們既能同時工作又獨立編址。圖中MAR為模塊地址寄存器，MDR為模塊數據寄存器，主存地址寄存器的高位表示模塊號，低位表示塊內地址。這種結構的尋址方式有利于并行處理，能夠實現多個分體的并行操作，一次訪問并行處理的n個字，不像單體方式那樣一定是沿存儲器順序排列的存儲單元內容，而是分別由各分體的地址寄存器指示的存儲單元的內容。因為各分體工作獨立，因此，只要進行合理的調度，就能實現并行處理，兩個存儲體可以同時進行不同的操作。例如一個存儲體被CPU訪問時，另一個存儲體可用來與外部設備進行直接存儲器存?。―MA）操作。下一頁上一頁計算機系統中的大容量主存是由多個存儲

多體交叉是多體存儲器的另一種組織形式，下面以一個四體交叉存儲器的組織形式為例，來說明多體交叉存儲器的工作原理。下圖是四體交叉原理圖。下一頁上一頁⒊多體交叉尋址方式多體交叉是多體存儲器的另一種組織形式，下面以一個四體

多體交叉尋址方式與多體存儲器尋址方式不同，多體存儲器是以高位地址作為模塊號，低位地址作為體內地址，每個模塊體內地址是連續的；多體交叉尋址方式是以低位地址作為模塊號，高位地址作為體內地址，各模塊間地址編號采用交叉方式。上圖所示的4個模塊M0、M1、M2、M3的編址如下表所示?？騼刃蛱柋硎敬鎯卧牡刂肪幪朖=0，1，2…。下一頁上一頁多體交叉尋址方式與多體存儲器尋址方式不同，多體存儲器是以

⑴地址連續的兩個單元分布在相鄰的兩個模塊中，地址按模塊號方向順序編號。⑵同一模塊內相鄰的兩個單元地址之差等于n。例如在四體交叉存儲器結構方式下，兩個單元地址之差等于4。⑶任何一個存儲單元的二進制地址編號的末2位正好指示該單元所屬模塊的編號，訪問主存時只要判斷這幾位就能決定訪問的是那個存儲模塊。在四體交叉存儲器結構方式下，M0模塊的每個單元地址的二進制編碼最后兩位都是00，M1模塊的每個單元地址最后兩位都是01，M2模塊的每個單元地址最后兩位都是02，M3模塊的每個單元地址最后兩位都是03。

⑷同一模塊內每個單元地址除去模塊號后的高位地址正好是模塊內單元的順序號，由此就可決定訪問單元在模塊中的位置。下一頁上一頁n體交叉尋址方式的規則滿足以下4點⑴地址連續的兩個單元分布在相鄰的兩個模塊中，地址按模塊號5.5Cache存儲器5.5.1多級存儲體系結構5.5.2Cache工作原理5.5.3主存與Cache的地址映射和地址變換5.5.4Cache的替換策略及寫操作策略5.5Cache存儲器5.5.2Cache工作原理中央處理器主存外存cacheCPUM1M2M3輔助硬件輔助軟硬件5.5.1多級存儲體系結構為解決存儲容量、存取速度和價格之間的矛盾,通常將各種不同存儲容量、不同存取速度的存儲器,按一定的體系結構組織起來,形成一個統一整體.典型的三級存儲系統:圖5.25三級存儲系統示意圖中央處理器主存外存cacheCPUM1M2M3輔助輔助5.5

Cache-主存層次

Cache一般由SRAM構成,容量小,存取速度快，依據程序局部性原理,存放的是主存中當前最需要執行的信息副本.

目的：主存容量不足的問題.

利用輔助硬件和操作系統中的存儲管理軟件,將主存和輔存構成一個整體.目的：解決CPU和主存速度不匹配的問題.

主存-輔存層次

總體效果：存取速度接近Cache,而存儲容量接近于輔存,整體價格也較合理.Cache-主存層次Cache一般由SRAM5.5Cache存儲器5.5.1多級存儲體系結構5.5.2Cache工作原理5.5.3主存與Cache的地址映射和地址變換5.5.4Cache的替換策略及寫操作策略5.5Cache存儲器5.5.2Cache工作原理1.問題的提出避免CPU“空等”現象CPU和主存（DRAM）的速度差異緩存CPU主存容量小速度高容量大速度低字塊1.問題的提出避免CPU“空等”現象CPU和主存（主存塊

調入

緩存主存塊與緩存塊建立

了對應關系標記記錄與某緩存塊建立了對應關系的主存塊號命中未命中主存塊與緩存塊未建立對應關系主存塊

未調入

緩存2.

Cache的命中率主存塊調入緩存主存塊與緩存塊建立了對應關系標記記錄命中率CPU欲訪問的信息在Cache中的比率命中率

與Cache的容量

與

塊長

有關

命中率CPU欲訪問的信息在Cache中的比率命中率命中率CPU欲訪問的信息在Cache中的比率命中率

與Cache的容量

與

塊長

有關

命中率CPU欲訪問的信息在Cache中的比率命中率Cache–主存系統的效率效率e

與命中率有關

設Cache命中率為h，訪問Cache

的時間為tc

，

訪問主存的時間為tm

則

e=×100%tc

h

×tc+(1－h)×tm

訪問Cache的時間

平均訪問時間

e=×100%Cache–主存系統的效率效率e與命中率有關3.Cache的讀操作

訪問Cache取出信息送CPU

訪問主存取出信息送CPU將新的主存塊調入Cache中執行替換算法騰出空位

結束命中？Cache滿？CPU發出訪問地址

開始是否是否3.Cache的讀操作訪問Cache訪問主存4.Cache的基本結構Cache替換機構Cache存儲體主存Cache地址映像變換機構由CPU完成4.Cache的基本結構Cache主存Cache由CPU

5.5.2Cache工作原理Cache的工作機制

Cache工作是以程序訪問的局部性原理為基礎的,即,一個程序的指令大都順序存放、順序執行,與程序相關的數據在存儲器中也相對集中.所以程序運行時,尤其有循環程序段和子程序段時,在較短時間區間內,常會對局部范圍的存儲器頻繁訪問,而此范圍之外的地址訪問甚少.這種現象稱為程序訪問的局部性.把局部范圍的主存內容從主存放到一個高速小容量存儲器中,使CPU在這一段時間內直接訪問它,以減少或不去訪問慢速的主存,程序運行速度將明顯提高.5.5.2Cache工作原理Cache的工作機制C

2.Cache工作原理例:某機主存容量為1MB,Cache容量為8KB,若以字節編址,每512B為一塊,則主存有2048塊,Cache有16塊.塊000000H00001H…..001FFH…塊2047FFE00HFFE01H…FFFFFH主存塊00000H0001H…..01FFH…塊151E00H1E01H…1FFFH

Cache塊的概念一般將主存和Cache的存儲空間分塊,每塊大小相同,包括相同數量的存儲單元.2.Cache工作原理例:某機主存容量為1MB,CaCache構成及工作過程CPU主存主存地址寄存器MAR主存—Cache地址變換機構(塊表)Cache存儲器Cache地址寄存器替換控制部件ABDB單字寬多字寬不命中命中(塊)

Cache包括Cache存儲器及相應控制部件,全部由硬件組成,速度快,對所有程序員均透明.CARCache構成及工作過程CPU主主存主存—CacheCa

Cache命中率

設Nc為Cache完成存取的總次數,Nm為主存完成存取的總次數,h為命中率,則有:

設r=tm/tc表示主存慢于Cache的倍率,e表示訪問效率,則有:

高速緩存命中率:CPU訪存時,信息恰巧在Cache中的概率.h=Nc/(Nc+Nm)

若tc表示命中時的Cache訪問時間,tm表示未命中時的主存訪問時間,1-h表示未命中率,則Cache/主存系統的平均訪問時間ta為:ta=htc+(1-h)tm

e=tc/ta=tc/[htc+(1-h)tm]=1/[h+(1-h)r]=1/[r+(1-r)h]Cache命中率設Nc為Cache例：CPU執行一段程序時,Cache完成存取的次數1900次,主存完成存取的次數為100次,已知Cache的存取周期為1ns,主存存取周期為5ns,求Cache/主存系統的效率和平均訪問時間.解：h=Nc/(Nc+Nm)=1900/(1900+100)=0.95

r=tm/tc=5ns/1ns=5e=1/[r+(1-r)h]=1/[5+(1-5)X0.95]=83.3%ta=tc/e=1ns/0.833=1.2ns例:某計算機的存儲系統由Cache和主存組成,某程序執行過程中訪存1000次,其中訪問Cache缺失(未命中)50次,則Cache的命中率是().A.5%B.9.5%C.50%D.95%例：CPU執行一段程序時,Cache完成存取的次數1900次

影響

Cache命中率的因素☆Cache的大小容量相對較大的Cache,命中率也相應提高,但容量太大,成本會變得不合理.

☆程序的特點遵循局部性原理的程序在運行時Cache的命中率也會很高,相反,在程序中頻繁且無規則地使用Call或JMP命令,將嚴重影響基于Cache的系統性能.

☆Cache的組織結構

Cache組織結構的好壞,對命中率也會產生較大影響.Cache的組織結構有三種類型:全相聯映射、直接映射和組相聯映射.

影響Cache命中率的因素5.5Cache存儲器5.5.1多級存儲體系結構5.5.2Cache工作原理5.5.3主存與Cache的地址映射和地址變換5.5.4Cache的替換策略及寫操作策略5.5Cache存儲器5.5.2Cache工作原理

5.5.3主存與Cache的地址映射和地址變換1.全相聯映射:允許主存中的每一個塊可以映射到Cache的任何一塊位置上.映射過程如下圖所示:

一.全相聯映射及其地址變換

二者密切相關--地址變換由地址映射方式決定.主存--Cache地址變換:程序運行時,根據地址映射把主存地址變換成Cache地址.

主存--Cache地址映射(mapping):把存放在主存中的程序按某種規則裝入Cache中,并依此建立主存地址與Cache地址的對應關系,即塊表.

●塊表—存放數據或指令在內存中所在單元地址的存儲器,用于判斷Cache命中以及實現地址映射,其字數等于Cache的塊數.5.5.3主存與Cache的地址映射和地址變換1……塊0

塊1塊15塊0塊1塊2047Cache主存…全相聯映射

2.全相聯映射方式下的地址變換主存塊號塊內地址

(1)主存地址格式:

(標志字段)圖5.26全相聯映射示意圖……塊0塊1塊15塊0塊1塊2047Cache主存…全相聯例:某機主存容量為1MB,Cache容量為8KB，若以字節編址，每512B為一塊,則主存有2048塊,Cache有16塊。主存地址格式：

0000000000000000000000000000000111111111…塊號(0塊)塊內存儲單元(0-511)…塊號(1塊)

塊內存儲單元(0-511)0000000000100000000000000000001111111111…塊號(2047塊)塊內存儲單元(0-511)1111111111100000000011111111111111111111……例:某機主存容量為1MB,Cache容量為8KB，若以字節Cache塊號塊內地址

主存塊號轉換為Cache塊號,塊內地址不變(3)地址變換(將主存地址轉換為Cache地址):

(2)Cache地址格式:…塊號(0塊)塊內存儲單元(0-511)…塊號(1塊)

塊內存儲單元(0-511)00010000000000001111111111…塊號(15塊)塊內存儲單元(0-511)11110000000001111111111111……0000000000000

0000111111111Cache塊號塊內地址主存塊號轉換為Cache塊號,塊內地主存塊號B(標志字段)塊內地址WCache塊號b塊內地址w主存塊號BCache塊號bBb??????比較命中MARCAR

圖5.27全相聯映射的地址變換塊表(塊表容量的計算：字數等于高緩塊數，字長由主存塊數和高緩塊數決定)不命中則訪問主存注意:在全相聯映射中,主存塊號作為識別是否命中的標志,標志位的長度由主存塊數決定.主存塊號B(標志字段)塊內地址WCache塊號b塊內地址w主字塊0字塊1字塊2C-1…標記標記標記設Cache有2C-1塊,主存有2m-1塊,即Cache塊地址有c位,主存塊地址有m位.字塊0字塊1字塊2C-1……字塊2m-1主存地址格式：主存字塊標記塊內地址m位圖5.28全相聯映射的另一種常見圖解字塊0字塊1字塊2C-1…標記標記標記設Cache有2C-

3.全相聯映射的優缺點

i=jmodm(m為Cache中總塊數)

映射規則:主存中任何一組的第i塊只能放入Cache的第i塊.

主存第j塊(大排塊數)和Cache第i塊有如下函數關系:1.直接映射:首先,主存在分塊的基礎上分組,每組大小與Cache的大小相同。二.直接映射及其地址變換

(2)缺點:塊表的查找時間長,速度慢.(1)優點:塊沖突概率最低,只有當Cache中全部裝滿后,才有可能出現塊沖突,塊分配靈活；其中,商為主存第j塊所在主存的組數,余數為在該組的塊數.3.全相聯映射的優缺點i=jmodm塊0塊1塊15Cache....…..0組1組127組塊0

塊1

塊15

塊16塊17

塊31

塊2047…主存塊2032塊2033圖5.29直接映射示意圖2.直接聯映射方式下的地址變換

Cache塊號

組號塊內地址Cache塊號塊內地址組內塊號

(2)Cache地址格式:(1)主存地址格式:塊0Cache....…..0組1組127組塊0塊…塊號(0塊)塊內存儲單元(0-511)…塊號(1塊)

塊內存儲單元(0-511)00000000001

00000000000000000001

111111111…塊號(2047塊)塊內存儲單元(0-511)11111111111

00000000011111111111

111111111……主存地址格式：00000000

000

00000000000000000

000

111111111組號(0-127)組內塊號(0-15)…塊號塊內存儲單元…塊號塊內存儲單元000000000(3)地址變換(將主存地址轉換為Cache地址):Cache塊號b組號G(標志字段)MARCache塊號b塊內地址wCAR命中不命中訪問主存塊內地址W比較組號GCache地址根據CAR的內容訪問Cache

主存地址中的“組內塊號(Cache塊號)+塊內地址”=Cache地址注意：在直接映射中,主存組號作為識別是否命中的標志，標志位的長度由主存組數決定.(3)地址變換(將主存地址轉換為Cache地址):Cach3.直接映射的優缺點：塊內地址(9位)

組內塊號(4位)組號(7位)

Cache地址格式塊內地址(9位)

塊號(4位)解:(1)主存地址格式

(1)分別寫出主存地址格式和Cache地址格式;(2)畫出直接映射及地址變換圖;(3)主存地址為0022AH的單元在Cache中什么位置?例題:某機主存容量為1MB,Cache容量為8KB，每塊512B,如果采用直接映射,請回答:(2)缺點:Cache的空間利用率低,塊沖突較多,命中率也低.(1)優點:硬件實現簡單,成本低.3.直接映射的優缺點：塊內地址(9位)組內塊號(4位)組塊0塊1塊15Cache....…..0組1組塊0

塊1

塊15

塊16塊17

塊31

塊2047…塊2032塊2033127組主存7位4位9位組號G組內塊號b塊內地址主存地址比較組號不命中,訪問主存Cache地址01…b……15(2)直接映射及地址變換示意圖命中,MARCAR4位9位則根據CAR的內容訪問Cache地址映射地址變換塊0Cache....…..0組1組塊0塊1塊1(3)主存地址為0022AH的單元在Cache中什么位置組(0組)組內塊號(1塊)塊內地址(42字)另外一種求法:

0022AH=(0000

0000001000101010)2因為主存第j塊和Cache第i塊有如下函數關系:i=jmodm(m為Cache中總塊數)這里,j=1,m=16,所以i=1mod16=1(3)主存地址為0022AH的單元在Cache中什么例:設一個Cache中有8個塊,訪問主存進行讀操作的塊地址序列為22、26、22、26、16、4、16、18,求每次訪問后Cache中的內容.解：地址命中與否地址轉換關系

不命中22MOD8=6

不命中26MOD8=2

22命中22MOD8=6

命中26MOD8=216不命中16MOD8=04不命中4MOD8=416命中16MOD8=018不命中18MOD8=2直接映象下Cache訪問情況例:設一個Cache中有8個塊,訪問主存進行讀操作的塊地址序

直接映象的塊分配情況訪問順序12345678地址222622261641618塊分配情況22操作狀態調進2226調進2226命中2226命中222616調進2241626調進2216264命中2216184替換直接映象的塊分配情況訪問順序123練習1.設有一個Cache的容量為2K字,每塊16字,在直接映象方式下,求:(1)該Cache可容納多少個塊?(2)如果主存的容量為256K字,則有多少個塊?(3)主存的地址格式?Cache的地址格式?(4)主存中的第032AB單元映象到Cache中哪一塊?練習2.設計算機的存儲器為64K×16位,直接地址映射的Cache容量為1K字,每塊4字,問:(1)主存中地址的標志字段、塊號和塊內地址字段分別有多少位？（2）Cache中可裝入多少塊數據？練習1.設有一個Cache的容量為2K字,每塊16字,在直三.組相聯映射及其地址變換n路組相聯:每組中有n塊.有全相聯映射:主存第g組第i塊可映射到Cache第i組中任一塊的位置.

有直接映射:主存第g組第i塊只能映射到Cache第i組.

1.組相聯映射:Cache分成大小相等的組,各組再分成大小相等的塊.

主存在分塊的基礎上分組,每組塊數等于Cache組數.

映射規則:Cahe分為m組,每組有n塊,則有以下關系:i=jmodm

其中,i為Cache組號,j為主存塊號(大排).商為主存第j塊所在組數,余數為該組所在塊數.

三.組相聯映射及其地址變換n路組相聯:每組中有n塊.有全相塊0塊1塊2塊3…塊14塊150組1組7組Cache主存塊0塊1塊2塊3…塊7塊8塊15塊16塊17…塊2047…圖5.30組相聯映射示意圖同上例,采用2路組相聯…

塊90組1組…塊0塊1塊2塊3…塊14塊150組1組7組Cache主存塊

2.組相聯映射方式下的地址變換塊內地址

(Cache組號)(1)主存地址格式:(主存字塊標記)

(2)Cache地址格式:塊內地址組號組內塊號

組號組內塊號2.組相聯映射方式下的地址變換塊內地址(Cache組(3)地址變換(將主存地址轉換為Cache地址):塊內地址組號組內塊號塊內地址

(Cache組號)(主存字塊標記)

組號組內塊號(3)地址變換(將主存地址轉換為Cache地址):塊內地址主存字塊標記組號G塊內地址WMAR組號g組內塊號b塊內地址wCAR比較不命中訪問主存命中主存字塊標記Cache組內塊號b┇┇┇┇●●訪問Cache圖5.31組相聯映射的地址變換示意圖塊表主存字塊標記組號G塊內地址WMAR組號g組內塊號b塊內地址w

例:某計算機的Cache共有16塊,采用2路組相聯(即每組2塊).每個主存塊大小為32字節,按字節編址.主存129號單元所在主存應裝入到得Cache組號是().A.0B.2C.4D.6

例:在下列因素中,與Cache的命中率無關的是().A.Cache塊的大小

B.Cache的容量

C.主存的存取時間例:某計算機的Cache共有16塊,采用2路組相聯(即每組

例：假設主存容量為512K×16位,Cache容量為4096×16位,塊長為4個16位的字,訪存地址為字地址.(1)在直接映射方式下,設計主存地址格式.(2)在全相聯映射方式下,設計主存地址格式.(3)在2路組相聯映射方式下,設計主存地址格式.

解:(1)在直接映射方式下,Cache分4096/4=210塊,主存分219/4=217塊,主存分219/212=27組.

故主存地址格式:主存組數(7位)組內塊數(10位)塊內地址(2位)例：假設主存容量為512K×16位,Cache容量為409(2)在全相聯方式下,Cache分4096/4=210塊,主存分219/4=217塊.故主存地址格式:主存塊數(17位)塊內地址(2位)

(3)在組相聯映射方式下,Cache分4096/4=210塊,2塊一組,Cache分210/2=29組;主存分219/4=217塊,每組分29塊,主存分217/29=28組.故主存地址格式:塊內地址

(Cache組號)(主存字塊標記)組號(8位)組內塊號(9位)(2位)(2)在全相聯方式下,Cache分4096/4=210塊,主練習1.設有一個Cache的容量為2K字,每塊16字,在直接映象方式下,求:(1)該Cache可容納多少個塊?(2)如果主存的容量為256K字,則有多少個塊?(3)主存的地址格式?Cache的地址格式?(4)主存中的第032ABH單元映象到Cache中哪一塊?

解:(1)

Cache可容納的塊數為:2K/16=27=128(塊)(2)主存的可容納的塊數為:256K/16=214(塊)

(3)主存地址格式為:塊內地址(4位)

組內塊號(7位)組號(7位)

Cache地址格式為:塊內地址(4位)

組內塊號(7位)練習1.設有一個Cache的容量為2K字,每塊16字,在直(4)主存中的032ABH單元:032ABH=(00000011001010101011)2

6組42塊11字另外一種求法:因為主存第j塊和Cache第i塊有如下函數關系:i=jmodm(m為Cache中總塊數)這里,j=29+28+25+23+21=810,m=128,所以i=1modm=810mod128=42

(4)主存中的032ABH單元:6組42塊115.5Cache存儲器5.5.1多級存儲體系結構5.5.2Cache工作原理5.5.3主存與Cache的地址映射和地址變換5.5.4Cache的替換策略及寫操作策略5.5Cache存儲器5.5.2Cache工作原理5.5.4Cache的替換策略及寫操作策略LRU----LeastRecentlyUsedFIFO----FirstInFirstOutRAND

常用替換算法:

注意:只有全相聯和組相聯的高速緩存中有替換策略問題.

替換策略(replacementpolicy):Cache地址變換中一旦發生不命中,需將主存中一個新塊調入Cache,如果此時發生塊沖突,決定從Cache中選擇哪一個數據塊,并將其從Cache中移去,將新的數據塊寫入的方法.

一.Cache的替換策略5.5.4Cache的替換策略及寫操作策略LRU----

1.RAND算法

特點:符合局部性原理,命中率較高.

方法:根據局部性原理選擇近期用的最少的數據塊作為替換的塊.具體做法:為每一塊設置一個計數器,當某一塊命中時,其計數器清0,其它各塊的計數器增1,當需要替換時,將計數值大的塊替換出.3.LRU算法

特點:較簡單,但沒有體現程序局部性規律,不能提高Cache命中率.方法:選擇最早調入Cache的塊進行替換.

2.FIFO算法

方法:隨機地確定替換塊.特點:容易實現,執行速度快,但沒有體現程序局部性規律,不能提高Cache命中率.1.RAND算法特點:符合局部性原理,命中二、Cache的寫操作策略

Cache內容是主存部分內容的副本,在命中的情況下,如果CPU對Cache寫入,改變了Cache(dirtyblock)的內容,如何保證主存內容與Cache內容一致.

缺點:當CPU向主存寫操作時,Cache無高速緩沖功能,降低了Cache的功效.

優點:寫主存與寫Cache同步.

1.直達法(writethrough