緩存—主存地址映射方式解析

朱貴憲　魏勝利

摘要：計(jì)算機(jī)組成原理是計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)的專業(yè)基礎(chǔ)課，其中緩存—主存地址映射方式作為該門課程的一個(gè)重要知識點(diǎn)，理解起來比較困難，該文以一個(gè)初學(xué)者的角度，用固定緩存和主存容量的辦法詳細(xì)解析主存—緩存地址映射方式，為學(xué)習(xí)本課程的學(xué)生提供參考。

關(guān)鍵詞：主存；緩存；地址映射；計(jì)算機(jī)組成原理

中圖分類號：TP311 文獻(xiàn)標(biāo)識碼：A 文章編號：1009-3044（2018）19-0292-03

Abstract： Composition Principle of Computer is a professional basic course for computer science and technology. The Cache - Main Memory address mapping mode as an important knowledge of this course and it is difficult to understand. This article details resolution of this mapping method by fixed cache and main memory capacity from the perspective of a beginner. This provide reference for the learning of this course students.

Key words： Main Memory；Cache；Address Mapping；Composition Principle of Computer

1 主存的相關(guān)概念

計(jì)算機(jī)硬件系統(tǒng)的組成包括5個(gè)部分，分別是：運(yùn)算器，控制器，存儲器，輸入系統(tǒng)和輸出系統(tǒng)。其中存儲器作為記憶部件，用來存放程序以及程序運(yùn)行時(shí)所使用的數(shù)據(jù)。根據(jù)功能的不同，存儲器可分為主存儲器、高速緩沖存儲器和輔助存儲器。主存儲器簡稱主存，有時(shí)也稱內(nèi)存，由半導(dǎo)體存儲器構(gòu)成，用于存放CPU執(zhí)行程序時(shí)所需要的指令和數(shù)據(jù)。存儲容量、存取時(shí)間是衡量主存儲器性能的重要指標(biāo)，存儲容量是指存儲器能存儲二進(jìn)制信息的總數(shù)量。存儲器劃分為多個(gè)存儲單元，每個(gè)單元存放一組二進(jìn)制信息。為了便于讀出或者寫入信息，存儲器所有存儲單元都用二進(jìn)制數(shù)進(jìn)行編號，這些編號稱為“內(nèi)存地址”。計(jì)算機(jī)按照內(nèi)存地址對存儲單元進(jìn)行訪問，存儲單元越多，需要的地址位數(shù)也就越多。如果地址總線是[n]位，則能夠編址[2n]個(gè)存儲單元。如果每個(gè)存儲單元能夠存放一個(gè)字節(jié)的二進(jìn)制數(shù)據(jù)，則該存儲器的容量為[2n]字節(jié)，即[2n]B。存取時(shí)間指的是存儲器完成一次“寫”操作（數(shù)據(jù)存入存儲器）或者完成一次“讀”操作（數(shù)據(jù)從存儲器中取出）所需要的時(shí)間。存取時(shí)間反映了存儲器讀寫數(shù)據(jù)的速度，它的快慢取決于存儲器存儲介質(zhì)的物理特性和存儲器的組織結(jié)構(gòu)。

2 緩存的相關(guān)概念

由于計(jì)算機(jī)的CPU速度不斷提高，主存的速度很難滿足高速CPU的要求，所以通常在CPU與主存之間設(shè)置一級高速緩存（Cache）來解決二者之間的速度不匹配問題。主存、緩存與CPU之間的接方式如圖1所示。由于計(jì)算機(jī)程序中的大部分指令和數(shù)據(jù)在主存中都是連續(xù)存放的，所以只要將CPU近期用到的指令和數(shù)據(jù)提前從主存送到緩存里面，在執(zhí)行程序時(shí)，CPU就可以直接從緩存中讀取信息，從而減少CPU訪問主存的次數(shù)，提高計(jì)算機(jī)執(zhí)行程序的速度。但由于緩存采用高速的半導(dǎo)體芯片制造，價(jià)格高且容量小，因此在程序執(zhí)行過程中就要不斷地將數(shù)據(jù)從主存調(diào)入緩存或者將緩存中的數(shù)據(jù)調(diào)出到主存。主存與緩存之間的數(shù)據(jù)調(diào)入調(diào)出完全是由硬件完成的，如何實(shí)現(xiàn)緩存與主存之間數(shù)據(jù)的高效傳輸，就需要熟知緩存與主存之間的地址映射方式。

3 緩存—主存系統(tǒng)存儲結(jié)構(gòu)

為了便于理解緩存—主存地址映射方式，應(yīng)首先熟悉緩存—主存系統(tǒng)存儲結(jié)構(gòu)，如圖2所示。這里假設(shè)緩存地址總位數(shù)為11位，緩存容量為2KB。把緩存地址分為兩段，高[c]位表示緩存塊號，低[b]位表示塊內(nèi)地址，[2c=C]表示緩存塊數(shù)，這里采用高3位（[c=3]）表示塊號，那么該緩存可以劃分為0～7共8塊；用低八位（[b=8]）表示塊內(nèi)地址，根據(jù)塊內(nèi)字?jǐn)?shù)計(jì)算公式：[2b=B]，則每一塊的塊內(nèi)字?jǐn)?shù)B（也稱塊長）為256字，緩存總?cè)萘繛?×256=2048字。依據(jù)圖2，可以理解為把2KB的緩存劃分成8塊，每一個(gè)緩存塊都內(nèi)含256個(gè)存儲單元，每個(gè)存儲單元能保存一個(gè)字節(jié)（8位二進(jìn)制數(shù)）的信息。

同時(shí)假設(shè)主存地址總位數(shù)為20位，容量為1MB。由于主存與緩存之間以塊為單位進(jìn)行數(shù)據(jù)傳遞，這就要求主存與緩存的塊內(nèi)字?jǐn)?shù)相等（256字），所以仍需要8位表示塊內(nèi)地址，剩余12位表示緩存塊號，即[m=12]，依據(jù)主存的塊數(shù)計(jì)算公式：[2m=M]，可得主存塊數(shù)為4096塊。這樣就可以把容量為1MB的主存劃分為4096塊，每一塊都內(nèi)含為256個(gè)存儲單元，每個(gè)存儲單元同樣都可以保存一個(gè)字節(jié)的信息。

由于現(xiàn)實(shí)中主存的容量遠(yuǎn)遠(yuǎn)大于緩存的容量，所以主存的塊數(shù)也遠(yuǎn)遠(yuǎn)大于緩存的塊數(shù)。

4 緩存與主存的地址映射方式

緩存與主存的地址映射方式指的是緩存與主存地址之間的對應(yīng)關(guān)系，常見的映射方式包括：直接映射，全相聯(lián)映射和組相聯(lián)映射。

4.1 直接映射

直接映射是指每個(gè)主存塊都能按照某一固定的對應(yīng)關(guān)系映射到可用的緩存塊中。

在直接映射方式中，依據(jù)公式[i=jmodC]或者公式[i=jmod2c]，即可建立主存塊與緩存塊之間的對應(yīng)關(guān)系。假設(shè)緩存塊數(shù)是[C]=8，與之對應(yīng)[c=3]，主存中的第4095塊即[j=4095]，按照公式[i=jmod2c]去對應(yīng)，可以計(jì)算出其對應(yīng)緩存中的第7號緩存塊，即[i]=7，依次類推，主存的4094塊對應(yīng)緩存的第6號塊，主存的4093塊對應(yīng)緩存的第5號塊，主存的4088塊對應(yīng)緩存的第0塊。主存與緩存之間映射關(guān)系如圖3所示。

根據(jù)圖3可以看出，直接映射中每個(gè)緩存塊可以對應(yīng)若干個(gè)主存塊，而每個(gè)主存塊固定的對應(yīng)某一個(gè)緩存塊。

直接映射方式中主存地址由高[m]位和低[b]位組成，其中高[m]位又被分成兩個(gè)部分：低[c]位是指緩存字塊的地址，高[t]位是指主存字塊標(biāo)記。這里設(shè)[m]=12，[c]=3，則[t]=12-3=9，這時(shí)主存地址分為3個(gè)部分，[t]=9，[c]=3，[b]=8，主存地址構(gòu)成如圖4所示?？梢岳斫鉃榘阎鞔娴?096個(gè)字塊分成0～511共512組（注意：這里的組和后面組相連的組概念不同），每一組都給予其賦一個(gè)9位的二進(jìn)制編碼，稱為主存字塊標(biāo)記，依據(jù)圖4，第0組的賦值是000000000，第511組的賦值為111111111，這兩個(gè)賦值也是它們各自對應(yīng)的主存字塊標(biāo)記，每一組內(nèi)都含有8個(gè)字塊，且這8個(gè)字塊和緩存中的8個(gè)字塊依次連接，主存共有512×8=4096塊，緩存為8個(gè)字塊，共2048個(gè)字。根據(jù)圖3的分析可知多個(gè)主存塊對應(yīng)某一個(gè)緩存塊，在上述的例子中，對于任一緩存塊，共有4096/8=29=512個(gè)主存塊與之對應(yīng)，主存字塊標(biāo)記就是用來區(qū)分這些對應(yīng)于同一個(gè)緩存塊的不同主存塊的。

CPU發(fā)來的主存地址中，高[m]位地址包含[t]位主存字塊標(biāo)記和[c]位緩存字塊地址，可以根據(jù)中間的[c]位字段得出其對應(yīng)的緩存塊號，如圖4所示，比如主存中的字塊0，其主存地址高[m]位當(dāng)中的低[c]位是000，那么其對應(yīng)的緩存中的第0號緩存塊，假設(shè)主存地址中間的[c]位字段為111，根據(jù)此內(nèi)容可以在緩存中找到對應(yīng)的字塊7，緩存中字塊7的內(nèi)容具體是主存中第0組字塊7的內(nèi)容，還是第N（N≤511）組中字塊7的內(nèi)容，就需要利用緩存的[t]位標(biāo)記與主存地址中的主存字塊標(biāo)記（[t]位）進(jìn)行比較，若相等，如本例緩存的[t]位標(biāo)記為111111111，主存字塊標(biāo)記也是111111111，則說明主存當(dāng)中某一組（這里指第511組）的第7塊的數(shù)據(jù)已經(jīng)被預(yù)先送入到緩存中，即稱之為命中，若不相等，表示主存塊與緩存塊還沒有建立對應(yīng)關(guān)系，即未命中，主存與緩存之間的映射關(guān)系如圖4所示。

直接映射的優(yōu)點(diǎn)在于實(shí)現(xiàn)簡單，缺點(diǎn)是不夠靈活，此外，當(dāng)程序恰好需要重復(fù)訪問對應(yīng)同一個(gè)緩存塊而不同的主存塊時(shí)，就要不停地進(jìn)行替換，從而降低了緩存命中率。

4.2 全相聯(lián)映射

全相連映射方式中，主存的每一字塊可映射到緩存的任一字塊中，只要緩存中有空位，即可將主存映射到該位置，當(dāng)緩存中沒有空位時(shí)，可從緩存中替換出任一字塊。采用全相聯(lián)映射時(shí)，主存地址中主存字塊標(biāo)記為[t+c]位，即[m]位。當(dāng)CPU訪問某主存字時(shí)，需將主存字塊標(biāo)記同緩存中所有標(biāo)記進(jìn)行比較，以確定該主存塊是否已經(jīng)存放在緩存中。比如CPU希望訪問主存的第4095字塊中的某個(gè)存儲單元，就需要先利用主存地址中的高[m]位（111111111111），與緩存中的8個(gè)字塊前面各自對應(yīng)的12位緩存標(biāo)記進(jìn)行比對，如圖5所示，緩存中字塊0的緩存標(biāo)記剛好為111111111111，與主存地址中的高[m]位相同，稱為命中，說明主存的第4095字塊已經(jīng)被預(yù)先存放到緩存的0字塊當(dāng)中。該映射方式所需要的硬件電路復(fù)雜，成本更高，而且有時(shí)需要多次比較，工作效率較低。

4.3 組相聯(lián)映射

組相連映射中，將緩存塊分成了[K]組，每組含[R]塊，每一個(gè)主存塊可以映射到[K]組緩存塊中相應(yīng)組內(nèi)的任一塊，設(shè)[i]為緩存組號，[j]為主存塊號，[i]、[j]、[K]之間的關(guān)系為：[i=jmodK]。本例緩存共有8塊，假設(shè)分成0～3共4組，即[K]=4，每組含2塊（通常將組內(nèi)含有兩個(gè)字塊的組相聯(lián)映射稱為二路組相聯(lián)，此時(shí)[r=1]），即[R=2r=2]塊。主存共有0～4095共有4096塊，主存的第4095塊，代入公式[i=jmodK]后，可計(jì)算出[i]為3，即主存的4095塊對應(yīng)緩存的第3組，依次類推，主存的第4094塊對應(yīng)緩存的第2組，主存的第4093塊對應(yīng)緩存的第1組，主存的4092塊對應(yīng)緩存的第0組，它們之間的地址映射關(guān)系如圖6所示。

二路組相聯(lián)映射（[r=1]）與直接映射相比，緩存字塊地址字段由[c]位（3位）變?yōu)榻M地址字段[q]位（[q=c-r=2]），其中[2c=8]表示緩存的總塊數(shù)，[2q=4]表示緩存的分組個(gè)數(shù)，[2r=2]表示組內(nèi)包含的塊數(shù)，如圖6所示，這樣就實(shí)現(xiàn)了把緩存中的8個(gè)字塊分成4組，每組2塊。對于緩存的分組總結(jié)起來可以理解為：緩存的總塊數(shù)[÷]組內(nèi)塊數(shù)=緩存分組個(gè)數(shù)，即[2c÷2r=2q]，[q=c-r]。

在二路組相連映射中，主存地址分為主存字塊標(biāo)記[s]、組地址[q]和字塊內(nèi)地址[b]共3個(gè)字段。設(shè)主存的塊內(nèi)地址[b=8]位，[c=3]，[r=1]，[q=2]，主存字塊標(biāo)記字段變?yōu)閇s=t+r]等于10位，形成1024個(gè)編碼，組地址[q]為2位，形成4個(gè)編碼，相當(dāng)于把主存分成了1024部分，每部分包含4個(gè)字塊，每個(gè)字塊對應(yīng)緩存中的一個(gè)緩存組。

假如CPU發(fā)來的主存地址的高[m]位為1111111111 11，首先根據(jù)組地址[q]（11），找到其對應(yīng)的緩存組為第3組，再根據(jù)主存字塊標(biāo)記[s]（1111111111），與緩存的字塊6和字塊7前面的標(biāo)記進(jìn)行比對，假設(shè)緩存字塊7前面的標(biāo)記是10個(gè)1，則比對成功，說明主存的第4095字塊已經(jīng)被預(yù)先存放到緩存第3組的字塊7當(dāng)中。

通常將組內(nèi)含有兩個(gè)字塊的組相聯(lián)映射稱為二路組相聯(lián)，同理還有四路組相聯(lián)（[r=2]，[R=4]）等，當(dāng)[r=0]時(shí)，組相聯(lián)映射則變成直接映射，當(dāng)[r=c]時(shí)，則變成了全相聯(lián)映射方式。

5 相關(guān)例題

例題：已知主存容量為1M×8位，緩存容量為2K×8位，塊長為256個(gè)8位的字，按字地址訪存，請分別寫出在直接映射、全相聯(lián)映射和二路組相聯(lián)映射方式下主存的地址格式。若主存的容量變?yōu)?M×16位，緩存容量不變，在四路組相連方式下主存地址的格式又是什么？

解：（1）主存容量為1M字，所以主存地址為20位，緩存的容量為2K字，所以緩存的地址為11位，又因?yàn)閴K長為256個(gè)字，按字地址進(jìn)行訪存，所以塊內(nèi)地址占8位，緩存共有[2048÷256=8]塊，緩存字塊地址[c=3]位，在直接映射方式下，主存的字塊標(biāo)記長度為[20-3-8=9]位。

（2）在全相聯(lián)映射方式中，除8位作為塊內(nèi)地址外，其他為均為主存字塊標(biāo)記，即[20-8=12]位。

（3）二路組相聯(lián)即每組內(nèi)有二個(gè)字塊的組相聯(lián)映射。每塊256個(gè)字，每組2塊，所以緩存共有[2048÷256÷2=4]組，組地址長度[q=2]，主存字塊標(biāo)記長度為[20-2-8=10]位。

（4）若主存容量變?yōu)?M×16位，字長仍然為8位，按字地址尋址，主存容量可看作2M×8位，即主存地址為21位，其中塊內(nèi)地址占8位，由四路組相連可知，緩存內(nèi)共有[2048÷256÷4=2]組，所以組地址為1位，主存的字塊標(biāo)記長度為[21-1-8=12]位。

6 結(jié)束語

該文通過介紹主存、緩存的作用以及與之相關(guān)的概念，引出對緩存—主存地址映射方式的解析。為了便于理解，固定主存容量為1MB，緩存容量為2KB，主存和緩存的塊長皆為256個(gè)8位的字，在此前提下對緩存—主存地址映射方式進(jìn)行具體詳細(xì)的分析，較好的化解了初學(xué)者對這部分內(nèi)容在理解上的困惑。

參考文獻(xiàn)：

[1] 魏勝利. 計(jì)算機(jī)組成原理[M]. 成都： 電子科技大學(xué)出版社， 2016.

[2] 唐朔飛. 計(jì)算機(jī)組成原理[M]. 北京： 高等教育出版社， 2012.

[3] 紀(jì)祿平. 計(jì)算機(jī)組成原理-面向?qū)嵺`能力培養(yǎng)[M]. 北京： 電子工業(yè)出版社， 2017.

[4] 白中英. 計(jì)算機(jī)組成原理[M]. 北京： 科學(xué)出版社， 2013.