胡九川，范東睿，程建聰，嚴龍，葉笑春，李靈枝，萬良易，鐘海斌

（1.北京交通大學(xué)計算機科學(xué)與技術(shù)學(xué)院，北京 100044；2.中國科學(xué)院計算技術(shù)研究所，北京 100080）

1 引言

計算機存儲程序原理決定了即將被執(zhí)行的指令或被處理的數(shù)據(jù)必須分批次地調(diào)入處理器，在容量十分有限的處理器片上緩存內(nèi)中轉(zhuǎn)停留，而暫時不能調(diào)入的大量指令和數(shù)據(jù)停留在內(nèi)存乃至硬盤中，等候調(diào)遣進入處理器參與運算實現(xiàn)程序運行；同樣，被執(zhí)行過的指令或處理過的數(shù)據(jù)也很可能在處理器片上緩存內(nèi)中轉(zhuǎn)停留，然后回到內(nèi)存或硬盤。所以，將那些在時間和空間上具有緊密關(guān)聯(lián)關(guān)系的指令與數(shù)據(jù)以群組為單位預(yù)先放置于緊鄰處理器核的片上緩存的頂端，形成及時局部性環(huán)境[1-5]。這樣的環(huán)境有利于縮短處理器內(nèi)核的訪存時延，提高內(nèi)核的訪存命中率。但是，對指令和數(shù)據(jù)在片上緩存與內(nèi)存之間往返遷移的特點和規(guī)律缺乏應(yīng)有的研究和分析。本文將運用數(shù)學(xué)方法研究指令和數(shù)據(jù)在處理器片上的遷移，初步探索其特點和規(guī)律，以最大限度保持指令和數(shù)據(jù)之間的時間和空間聯(lián)系，該方向的研究具有重要的理論和實踐指導(dǎo)意義。

根據(jù)存儲程序原理，指令和數(shù)據(jù)之間的時空關(guān)聯(lián)關(guān)系來源于程序執(zhí)行邏輯的內(nèi)在規(guī)定。抽象地看，以指令執(zhí)行順序、數(shù)據(jù)安置順序為基本構(gòu)件形成的邏輯復(fù)合體構(gòu)成了計算機程序，這個邏輯復(fù)合體隱含著指令之間、數(shù)據(jù)之間不可割舍的時空聯(lián)系。在遷移進出處理器時，指令和數(shù)據(jù)之間的時空聯(lián)系很可能由于它們在內(nèi)存和片上緩存的存儲位置變化而發(fā)生變化，導(dǎo)致在處理器原計劃遵照程序內(nèi)在的邏輯展開運算時，前來向處理器“報到”的指令或數(shù)據(jù)卻打亂了這內(nèi)在的程序執(zhí)行邏輯。這樣需求錯位的矛盾局面產(chǎn)生的根源是內(nèi)存容量和片上緩存容量存在巨大的落差，片上緩存中的指令和數(shù)據(jù)需要不斷地更新才能將所有指令和數(shù)據(jù)從內(nèi)存中推到處理器核的面前，方便處理器核訪問。因此，需求錯位的矛盾是結(jié)構(gòu)性的。

為了緩解需求錯位的矛盾，在處理器內(nèi)核訪問任意指令或數(shù)據(jù)時，應(yīng)該將與之存在時空關(guān)系的其他指令、數(shù)據(jù)組合為一個整體遷移到處理器的片上緩存內(nèi)，盡量保持指令或數(shù)據(jù)之間的時空聯(lián)系，將指令之間、數(shù)據(jù)之間的時空關(guān)系轉(zhuǎn)化為指令、數(shù)據(jù)在片上緩存體系中緊密分布的形態(tài)。由于處理器片上緩存是指令和數(shù)據(jù)進入處理器核的必經(jīng)之路，此分布形態(tài)必然為提高處理器內(nèi)核的訪存命中率，減緩訪存時延、控制指令和數(shù)據(jù)遷移以適應(yīng)處理器運算需要，營造有利的片上及時局部性環(huán)境創(chuàng)造條件。

事實上，及時局部性的特質(zhì)已經(jīng)體現(xiàn)在處理器體系的內(nèi)在結(jié)構(gòu)之中。例如，存儲在片上寄存器里的指令操作元分布在諸如指令解碼器、指令流水線等功能單元可就近方便獲取的地方[6-7]，各級流水線中眾多狀態(tài)寄存器的存在都是及時局部性存在的例證[8-9]。本文可以把片上通用寄存器理解為片上緩存，而片上緩存是通用寄存功能的具體延展。

本質(zhì)上，片上及時局部性環(huán)境可以使處理器所需要的指令或數(shù)據(jù)及時、就近地在片上寄存器或緩存內(nèi)找到[10-13]。因此，掌握指令和數(shù)據(jù)在片上寄存器、緩存和內(nèi)存之間往返遷移的規(guī)律和特點，必將為人們探索在遷移過程中保持指令或數(shù)據(jù)之間的時空聯(lián)系、營造高質(zhì)量的及時局部性環(huán)境奠定基礎(chǔ)。

以指令解碼器為分水嶺，可以把營造及時局部性環(huán)境的工作分為解碼前期和解碼后期2 個階段。在解碼前期，及時局部性環(huán)境主要在片上緩存營造，指令和數(shù)據(jù)在緩存中的分布形態(tài)及其更新是人們關(guān)注的重點；在解碼后期，及時局部性環(huán)境主要通過控制指令和數(shù)據(jù)在處理器片內(nèi)各類寄存器中的分布來實現(xiàn)。

為了更好地緩解需求錯位的矛盾，文獻[1]給出了一個由2 個傳統(tǒng)緩存耦合而成的新型片上緩存，稱之為滲透緩存，并在指令或數(shù)據(jù)的遷移中將具有時空關(guān)聯(lián)關(guān)系的指令和數(shù)據(jù)以及時局部組的整體形式從內(nèi)存遷往滲透緩存，同時控制指令和數(shù)據(jù)在滲透緩存內(nèi)一方面似泉水涌出般地“涌”向滲透緩存的頂端，另一方面似泉水被吸入泉眼般地被“吸”回內(nèi)存，使指令和數(shù)據(jù)在片上緩存內(nèi)流動起來。

圖1 給出了一個滲透緩存結(jié)構(gòu)及數(shù)據(jù)遷入規(guī)則示意，其中地址4 是處理器核的訪存焦點，相鄰地址3 與地址5、地址2 與地址6、地址1 與地址7構(gòu)成內(nèi)存中一個對稱的及時局部組。當(dāng)?shù)刂? 上的指令或數(shù)據(jù)被遷往滲透緩存中的泉吸緩存的頂端時，及時局部組內(nèi)的其他指令或數(shù)據(jù)被分別遷往滲透緩存中的第一級、第二級、第三級泉涌緩存。由于地址4 的及時局部性程度最高，與之鄰近的地址3 和地址5 的及時局部性程度也比較高，因此地址3 和地址5 上的指令或數(shù)據(jù)被遷移到泉涌緩存的第一級。如果處理器內(nèi)核在隨后的訪存中其訪存焦點仍然是地址4，那么該地址的及時局部性仍然保持最高；如果訪存焦點不是地址4 而是地址5，那么它的及時局部性程度變?yōu)樽罡?，地? 的及時局部性降低。此刻，地址4 中指令或數(shù)據(jù)可以停留在原地或被降級遷往滲透緩存中的第二級泉吸緩存，地址5 中的指令或數(shù)據(jù)被升級遷往第一級泉吸緩存，地址6 中的指令或數(shù)據(jù)被升級遷往第一級泉涌緩存，地址7 中的指令或數(shù)據(jù)被升級遷往第二級泉涌緩存，如此，指令或數(shù)據(jù)在滲透緩存中變成流動的趨勢。仿真實驗表明[4]，將處理器片上緩存改進為滲透緩存提高了處理器內(nèi)核訪存的效率和訪存命中率，為縮短訪存時延營造了及時局部性環(huán)境[2-3]。

圖1 滲透緩存結(jié)構(gòu)及數(shù)據(jù)遷入規(guī)則示意

顯然，如果及時局部組內(nèi)的指令或數(shù)據(jù)都能夠滿足處理器內(nèi)核的訪存需要，那將是一個理想狀態(tài)，而滲透緩存是一種逼近這種理想狀態(tài)的手段。本文將探討這種理想狀態(tài)產(chǎn)生的合理性。

及時局部組是一個以處理器訪存焦點即當(dāng)前被訪問的指令或數(shù)據(jù)為中心、一定范圍內(nèi)的指令或數(shù)據(jù)組成的、具有時空關(guān)聯(lián)關(guān)系的指令或數(shù)據(jù)族群。所以，應(yīng)該以族群內(nèi)的指令或數(shù)據(jù)之間的關(guān)聯(lián)關(guān)系在遷移過程中發(fā)生的變化為入手點，去認識及時局部環(huán)境內(nèi)在機制，發(fā)現(xiàn)理想狀態(tài)產(chǎn)生的前提條件。為了從理論上深入認識及時局部環(huán)境的內(nèi)在機制，實現(xiàn)理想的及時局部性狀態(tài)，本文將運用抽象的數(shù)學(xué)方法研究分析指令或數(shù)據(jù)在處理器片上緩存和內(nèi)存之間往返遷移的規(guī)律，尋找遷移過程中保持指令或數(shù)據(jù)及時局部性的前提條件。文獻[1]具體介紹了滲透緩存中的數(shù)據(jù)遷移方式的有效性，本文將以數(shù)學(xué)抽象的方式證明滲透緩存結(jié)構(gòu)的內(nèi)在合理性。

2 內(nèi)存、片上緩存的抽象描述

2.1 內(nèi)存、地址和基本可尋址單位

地址是計算機體系結(jié)構(gòu)中的核心概念，是建立存儲體系的基本工具。地址的組成結(jié)構(gòu)規(guī)定了計算機內(nèi)存和片上緩存的關(guān)聯(lián)法則[4,14]。下面，給出內(nèi)存、地址和基本可尋址單位的抽象定義。由于存儲空間是描述地址結(jié)構(gòu)及其形式的基礎(chǔ)，因此先給出存儲空間的抽象定義。設(shè)m為自然數(shù)，集合D={0,1}，稱集合Dm={(dl,d2,…,dm)|di∈D,i=1,2,3,…,m}為存儲空間，自然數(shù)m為存儲空間維數(shù)。存儲空間維數(shù)m決定存儲空間的容量。由于m維存儲空間中的向量是m位的二進制數(shù)，存儲空間中的所有向量構(gòu)成一個由m位二進制數(shù)組成、按數(shù)值大小關(guān)系排列順序的全序集合[15]，這種序關(guān)系本質(zhì)上就是地址的序關(guān)系。因此從存儲空間演化出地址空間。

定義1設(shè)m為自然數(shù)，Dm為m維的存儲空間，≤為存儲空間中的全序關(guān)系，稱集合{Dm,}≤為地址空間，地址空間中的向量為地址。

定義2設(shè)m,n,p,q,k為自然數(shù)，m=kn，Dn為地址空間，Dm為存儲空間，設(shè)

則稱Dn×Dm為內(nèi)存；Dm中的向量為存儲槽，內(nèi)存空間中的向量為基本可尋址單位。

根據(jù)定義2，基本可尋址單位由地址和存儲槽構(gòu)成，具有唯一的地址，泛指存儲在內(nèi)存中的指令或數(shù)據(jù)。2 個基本可尋址單元在內(nèi)存中的距離可以定義為地址之間的距離。

2.2 片上緩存

在處理器運行過程中，被訪問過或從內(nèi)存取出等待訪問的數(shù)據(jù)被置于一個具有層次結(jié)構(gòu)的片上緩存內(nèi)。片上緩存實質(zhì)是內(nèi)存層次化的自然延伸。片上緩存的結(jié)構(gòu)及其上的數(shù)據(jù)分布策略影響處理器的性能。處理器內(nèi)核應(yīng)該盡可能在緩存層級的高層級內(nèi)訪問到原本需要到內(nèi)存或低緩存層級中才能訪問到的數(shù)據(jù)。所以，必須將加載到內(nèi)存的數(shù)據(jù)遷移到容量相對有限的片上緩存高層級內(nèi)。將一個大容量結(jié)構(gòu)內(nèi)的數(shù)據(jù)納入一個容量相對小的結(jié)構(gòu)內(nèi)的根本方法是將大容量結(jié)構(gòu)內(nèi)的數(shù)據(jù)分成等價類，將等價類的代表放入容量相對小的結(jié)構(gòu)之中。只有這樣才能在邏輯意義上將一個大容量結(jié)構(gòu)置于小容量結(jié)構(gòu)之中。目前，片上緩存與內(nèi)存之間的關(guān)聯(lián)結(jié)構(gòu)主要是通過等價分類實現(xiàn)的[16]。定義3 描述了該等價類方法的本質(zhì)。

定義3設(shè)m,n,p,q為自然數(shù)，Dp×Dq和Dn×Dm為內(nèi)存。如果映射

使對內(nèi)存Dn×Dm中任意的基本可尋址單位

存在內(nèi)存中的基本可尋址單位v=(i1,i2,…,ip,c1,c2,…,cq)的地址滿足

其中，g為自然數(shù)，2p＞I，I=i12p-1+。則稱內(nèi)存Dp×Dq為內(nèi)存Dn×Dm的常規(guī)緩存，I為基本可尋址單位u在緩存Dp×Dq的索引號，映射Q為從Dn×Dm到Dp×Dq為常規(guī)相聯(lián)。

圖2 是一個內(nèi)存和緩存關(guān)聯(lián)關(guān)系示意。內(nèi)存里的數(shù)據(jù)地址按照定義3 中規(guī)定的模運算進行換算，并以模運算的余數(shù)為索引號為該地址上的數(shù)據(jù)在緩存中確定新位置，即存儲槽索引號。例如，圖2 中緩存容量值c為7，以其為模數(shù)，對數(shù)值為8的地址進行模運算得到余數(shù)為1，則位于內(nèi)存位置8 上的數(shù)據(jù)被遷移到緩存中后，其在緩存中的索引號為1。圖2 中的平面坐標(biāo)系內(nèi)給出了從內(nèi)存地址空間U到片上緩存地址空間H（緩存槽索引號）之間的對應(yīng)關(guān)系。

圖2 內(nèi)存和緩存關(guān)聯(lián)關(guān)系示意

一般地，內(nèi)存空間Dn×Dm中的基本可尋址單位u的地址與另一個內(nèi)存空間Dp×Dq的容量2p進行模運算，所得余數(shù)正好為基本可尋址單位v在內(nèi)存空間Dp×Dq里的地址，即緩存槽索引號。根據(jù)拓撲學(xué)的知識[15]，模運算將內(nèi)存空間中的所有基本可尋址單位分成2p個等價類。

定義3 說明了緩存是層次結(jié)構(gòu)意義上的內(nèi)存，只是離處理器核更近。根據(jù)定義3，直接相聯(lián)緩存和集合相聯(lián)緩存是常規(guī)緩存。在大多數(shù)情況下，常規(guī)緩存用來建立一般情況下的片上緩存。但是，全相聯(lián)緩存為非常規(guī)緩存，這是因為Dn×Dm內(nèi)的可尋址單位可以在Dp×Dq內(nèi)任意放置，不用模運算來定位。非常規(guī)緩存用于在特殊的條件下建立片上緩存。除非特別指出，本文的討論圍繞常規(guī)緩存展開。

2.3 訪存焦點與及時局部性

處理器當(dāng)前訪存所指向的內(nèi)存位置稱為處理器的訪存焦點。

定義4設(shè)m,n為自然數(shù)，r為非負整數(shù)，為內(nèi)存Dn×Dm中任意一個基本尋址單位，，稱集合N(u,r)={u′:e(u-u′)＜r}為以基本尋址單位u為中心的鄰域。其中，e(u-u')為2 個基本可尋址單位u和u′之間的距離。

以一個處理器的當(dāng)前訪存焦點u為中心，以距離r為半徑，可在內(nèi)存中劃定一個不超出此半徑的對稱區(qū)域，區(qū)域內(nèi)匯集了一簇按照地址順序排列的基本可尋址單位，訪存焦點位于隊列正中央，形成一個以訪存焦點為中心的鄰域N(u,r)，構(gòu)成一個對稱及時局部組?？刂凄徲虬霃剑纯煽刂凄徲蛞?guī)模；控制鄰域規(guī)模，即可控制遷移數(shù)據(jù)的規(guī)模。

在處理器運行中，訪存焦點u可能被再次訪問，多次成為處理器的執(zhí)行焦點，這種執(zhí)行焦點短暫保持在固定位置的處理器運行態(tài)勢稱為時間局部性。當(dāng)訪存焦點發(fā)生改變時，處理器要訪問鄰域N(u,r)內(nèi)其他的基本尋址單位，且執(zhí)行焦點不超出鄰域范圍的微漂移執(zhí)行態(tài)勢。執(zhí)行焦點在固定位置重復(fù)出現(xiàn)，或相對于固定位置產(chǎn)生微漂移的執(zhí)行態(tài)勢說明了及時局部組內(nèi)數(shù)據(jù)之間具有相對突出的匯聚性，是及時局部性的動態(tài)形式。

因此，以基本尋址單位的鄰域為媒介，可為處理器的運行營造快捷訪問數(shù)據(jù)的及時局部性環(huán)境，進而在片上緩存內(nèi)完善遷移數(shù)據(jù)的機制，將改進計算性能的視野從靜止固定的緩存結(jié)構(gòu)層面，提升到動態(tài)靈活利用數(shù)據(jù)關(guān)聯(lián)特征的高度。

3 及時局部性的分拆與折疊

為了在片上緩存的高端層級營造理想的服務(wù)處理器核的及時局部性環(huán)境，作為整體遷移的及時局部組鄰域N(u,r) 內(nèi)各基本尋址單位之間相互靠攏的位置關(guān)系應(yīng)該盡力保持穩(wěn)定。然而，及時局部組內(nèi)基本可尋址單位相互靠攏的態(tài)勢可能會因內(nèi)存和片上緩存的關(guān)聯(lián)結(jié)構(gòu)限制而在從內(nèi)存遷移到緩存過程中發(fā)生形變，造成及時局部組鄰域被分拆或折疊。

例1圖3 顯示了一個常規(guī)緩存中緩存槽索引號和內(nèi)存地址的對應(yīng)關(guān)系。例如，索引號為2 的緩存槽可以接納來自內(nèi)存地址為2、10、18、26 等的數(shù)據(jù)。以任意一個內(nèi)存地址為中心，取鄰域半徑為2，可以構(gòu)成一個以該地址為中心的及時局部組。從圖3 可以看出，那些以與緩存存儲槽索引號為2、3、4、5 對應(yīng)的地址為中心的及時局部組可以不破壞地址相鄰連續(xù)性關(guān)系地遷移到緩存內(nèi)。例如，以地址19 為中心的及時局部組占據(jù)一個連續(xù)的地址段17、18、19、20、21。這些內(nèi)存地址上數(shù)據(jù)之間的關(guān)聯(lián)關(guān)系可以不被分拆地遷移到緩存內(nèi)一組相鄰索引號1、2、3、4、5 所指定的緩存槽內(nèi)。然而，以那些與索引號0、1、6、7 相對應(yīng)的地址為中心的及時局部組卻只能被分拆后遷移到緩存內(nèi)。例如，以地址23 為中心的及時局部組占據(jù)一個連續(xù)地址段21、22、23、24、25，該地址段上的數(shù)據(jù)被遷移到緩存內(nèi)一組不相鄰的索引號5、6、7、0、1所指定的片上緩存槽內(nèi)。索引號為5 的緩存槽與索引號為1 的緩存槽之間的距離為3，超過了及時局部組的鄰域半徑2。

圖3 片上緩存中數(shù)據(jù)分配示意

及時局部組遷移后其鄰域半徑被拉長的情形稱為及時局部性分拆。反過來，如果及時局部組半徑過大，會出現(xiàn)一個緩存槽被來自內(nèi)存中地址不同的2 個數(shù)據(jù)同時占據(jù)的不合理情形。

例2在圖3 中，選擇及時局部組鄰域半徑為6，以地址14 為中心的及時局部組占據(jù)一個連續(xù)地址段8、…、13、14、15、…、20。這些地址上的數(shù)據(jù)被遷移到緩存內(nèi)后，一些緩存槽同時被2 個來自不同內(nèi)存地址的數(shù)據(jù)所占據(jù)。例如，索引號為3的緩存槽被來自內(nèi)存地址11、19 的不同數(shù)據(jù)同時占據(jù)，這顯然是不合理的。

同一緩存槽被來自不同地址的數(shù)據(jù)同時占據(jù)的情形稱為及時局部性折疊。及時局部性折疊是數(shù)據(jù)過度靠攏的畸形形態(tài)，在基本可尋址單位從內(nèi)存遷往緩存的過程中，應(yīng)杜絕及時局部性折疊。定理1 給出了消除及時局部性折疊的充分必要條件。

定理1設(shè)m,n,p,q為自然數(shù)，內(nèi)存Dp×Dq為內(nèi)存Dn×Dm的常規(guī)緩存，r為對稱及時局部組的半徑，則發(fā)生及時局部性折疊的充分必要條件是r≥c/2。其中，c=2p為緩存Dp×Dq的容量。

證明必要性。任取內(nèi)存Dn×Dm里一個基本可尋址單位，設(shè)其在常規(guī)緩存Dp×Dq內(nèi)的索引號為h。如果出現(xiàn)及時局部組折疊，則只能出現(xiàn)圖4和圖5 這2 種情形中。在圖4 中，索引號為h的緩存槽到索引號為c的緩存槽的距離c-h小于及時局部組的鄰域半徑r，且

圖4 靠近緩存高地址端

于是r-c+h≥h-r，則2r≥c，即

同理，在圖5 中，索引號為h的緩存槽到索引號為0 的緩存槽的距離h小于及時局部組的鄰域半徑r且

圖5 靠近緩存低地址端

于是r-h≥c-h-r，則2r≥c，即

所以，如果發(fā)生及時局部性折疊，則必然有r≥c/2。

充分性。假設(shè)不發(fā)生及時局部性折疊，則r-(c-h)＜h-r而且r-h＜c-(h+r)，于是根據(jù)上述2 個不等式，有

所以，如果r≥c/2，則一定發(fā)生及時局部性折疊。

定理2設(shè)m,n,p,q為自然數(shù)，內(nèi)存Dp×Dq為內(nèi)存Dn×Dm的常規(guī)緩存，r為對稱及時局部組的半徑，則不發(fā)生及時局部性折疊的充要條件是

其中，c=2p為緩存Dp×Dq的容量。

證明根據(jù)定理1，此結(jié)果是顯然的。

定理1 和定理2 指出控制及時局部組的鄰域半徑在一定范圍內(nèi)能杜絕及時局部性發(fā)生折疊。然而，及時局部性發(fā)生撕裂卻是一定的。只要控制內(nèi)存地址的取值范圍和及時局部組鄰域半徑規(guī)模，直接相連和組相連的內(nèi)存與片上緩存的連接關(guān)系能夠使及時局部組在從內(nèi)存遷往片上緩存的過程中，及時局部組內(nèi)各個數(shù)據(jù)之間的相對關(guān)系不被破壞，這意味著當(dāng)前處理器中片上緩存和內(nèi)存之間的相聯(lián)機制能夠?qū)崿F(xiàn)保持數(shù)據(jù)及時局部性的遷移。

4 滲透緩存內(nèi)命中率分析

數(shù)據(jù)遷移到片上緩存的中心地帶可能會產(chǎn)生及時局部性分拆（由于通常的及時局部組鄰域半徑遠小于片上緩存容量的一半，本文在此假設(shè)及時局部性折疊的情況可以忽略）。例如，考慮數(shù)據(jù)從圖6中的內(nèi)存Cs遷移到緩存Ct的情形。如果及時局部組鄰域某個基本可尋址單位的地址值為緩存Ct容量值的整數(shù)倍，那么如圖6 中的陰影區(qū)域所示，這些陰影區(qū)域內(nèi)的數(shù)據(jù)遷入緩存后將被分拆為兩部分，陰影左半部分內(nèi)的數(shù)據(jù)被安置在緩存Ct的右端，陰影右半部分的數(shù)據(jù)被安置在緩存Ct的左端。否則，及時局部組鄰域內(nèi)的數(shù)據(jù)遷入緩存Ct內(nèi)后不發(fā)生分拆，直接安置在緩存Ct內(nèi)連續(xù)的存儲槽號所指定的緩存槽里。

圖6 數(shù)據(jù)從內(nèi)存Cs遷移到緩存Ct

如果在遷移中保持局部性不被分拆，那么數(shù)據(jù)可以在片上緩存內(nèi)接收處理器內(nèi)核的訪問，免除了處理器內(nèi)核“遠涉”內(nèi)存去獲得數(shù)據(jù)；但是，當(dāng)處理器訪存焦點移出該及時局部組時，后續(xù)到來的數(shù)據(jù)及時局部組很可能全面覆蓋之前到來的及時局部組，此刻，若處理器內(nèi)核的訪存焦點移回之前的及時局部組，那么處理器內(nèi)核將不能在片上緩存內(nèi)訪問到之前及時局部組內(nèi)的數(shù)據(jù)，只能“遠涉”內(nèi)存再次遷移數(shù)據(jù)。因此，處理器內(nèi)核訪問片上緩存的命中率會在這種條件下降低，訪存時延會相應(yīng)增加。

如果遷移過程中發(fā)生及時局部性分拆，那么及時局部組內(nèi)的數(shù)據(jù)就會分拆開來，分布在片上緩存的兩端。此時，該及時局部組被后續(xù)到來的及時局部組全面覆蓋的可能性存在降低的可能。如果及時局部組在遷移到片上緩存的過程中，及時局部組內(nèi)的數(shù)據(jù)分布在如圖1 所示的三級緩存內(nèi)，那么，這些局部組內(nèi)的數(shù)據(jù)被隨后到來的新的局部組全部覆蓋的可能性就更低了。這就是本文在第1 節(jié)中介紹的滲透緩存能夠提高處理器訪存命中率、縮短訪存時延的原因。下面的仿真實驗證實了本文的理論分析。

5 仿真實驗

本文利用modelsim 10.1a 仿真平臺對向傳統(tǒng)緩存和滲透緩存實施數(shù)據(jù)遷移的過程進行了模擬，核心工作是模擬處理器load/store 指令的數(shù)據(jù)傳輸過程。為此，本文構(gòu)建了處理器模塊、緩存模塊、內(nèi)存模塊、滲透次數(shù)收集模塊。其中處理器模塊用來解析測試集地址以及產(chǎn)生訪存請求；緩存模塊用來處理數(shù)據(jù)的替換、滲透以及向滲透次數(shù)收集模塊反饋單次滲透完成信號；內(nèi)存模塊用來處理數(shù)據(jù)的替換、滲透遷移以及存儲數(shù)據(jù)；滲透次數(shù)收集模塊用來統(tǒng)計單輪滲透次數(shù)信號，當(dāng)收集到一輪完整的滲透信號之后，向處理器匯報，使處理器開始下一輪工作，各模塊通過數(shù)據(jù)傳輸協(xié)調(diào)工作，如圖7 所示。實驗中傳統(tǒng)緩存和滲透緩存的配置規(guī)格如表1 所示。

圖7 仿真模塊協(xié)調(diào)工作示意

表1 傳統(tǒng)緩存和滲透緩存參數(shù)設(shè)置

實驗結(jié)果表明，在內(nèi)存和片上緩存之間實施滲透數(shù)據(jù)遷移之后，相比傳統(tǒng)的數(shù)據(jù)遷移做法，處理器內(nèi)核訪問片上緩存的命中率總體上得到了有效提高，自然相應(yīng)地縮短了處理器的訪存時延。由于篇幅的限制，本文在此給出部分實驗數(shù)據(jù)，如表2～表4 所示。其中，程序Wordcount、Cholesky 以及LU 是通常測試處理器性能的測試程序，具有典型的代表性，Wordcount 的指令和數(shù)據(jù)的地址存放序列具有突出的時間局部性，LU 具有突出的空間局部性，而Cholesky 兼具時間與空間局部性。以Wordcount 測試集作為處理器訪問內(nèi)存的請求地址，將訪存命中率從傳統(tǒng)緩存的88.036%提升至滲透緩存的92.336%；以Cholesky 測試集作為處理器訪存的請求地址，將訪存命中率從傳統(tǒng)緩存的90.118%提升至99.920%；以LU 測試集作為處理器訪存的請求地址，將訪存命中率從傳統(tǒng)緩存的0.076%提升至92.160%。由于滲透緩存由泉吸緩存與泉涌緩存構(gòu)成，而傳統(tǒng)緩存在結(jié)構(gòu)上相當(dāng)于泉涌緩存容量為零的滲透緩存，且滲透緩存比傳統(tǒng)緩存更加注重空間局部性，對于LU 這種具有極端的空間局部訪存特性的測試集，滲透緩存對訪存命中率的提升幅度更大。從實驗結(jié)果分析，在LU 測試集中，大部分處理器內(nèi)核所需要的數(shù)據(jù)在被遷移滲透訪問的過程中駐留在滲透緩存里，這可以從表4 絕大部分成功訪問發(fā)生在緩存L2-push 中的結(jié)果得到驗證。從整體上看，訪存總的命中率得到提升，在滲透緩存各層級的命中率較傳統(tǒng)緩存中對應(yīng)層級的命中率也得到提升。

表2 傳統(tǒng)緩存和滲透緩存上的命中率（Wordcount）

表3 傳統(tǒng)緩存和滲透緩存上的命中率（LU）

表4 傳統(tǒng)緩存和滲透緩存上的命中率（Cholesky）

在片上緩存容量固定不變的條件下，被遷移的緩存塊大小變化與處理器內(nèi)核訪問緩存的命中率之間的關(guān)系比較復(fù)雜。確定緩存塊的規(guī)模需要以形成片上及時局部性環(huán)境為目標(biāo)，在動態(tài)調(diào)控緩存塊的規(guī)模和遷移過程中盡量使包含在程序中的計算邏輯或業(yè)務(wù)邏輯在片上及時局部性環(huán)境得到保持。為此，本文下一步將進行動態(tài)調(diào)控緩存塊大小規(guī)模方面的探索研究。

6 結(jié)束語

從本文的討論中可以發(fā)現(xiàn)，數(shù)據(jù)遷移到處理器片上緩存中之后，自然不存在處理器內(nèi)核到內(nèi)存里訪問數(shù)據(jù)的時間消耗，縮減了處理器內(nèi)核的訪存時延；如果處理器內(nèi)核在片上緩存內(nèi)的訪存命中率得到提高，那么縮減訪存時延的積累效應(yīng)就更加理想。

所以，構(gòu)成及時局部組的數(shù)據(jù)整體遷移到處理器片上后，處理器訪問內(nèi)存數(shù)據(jù)的時間消耗將進一步減少；如果以及時局部組的形式整體到片上緩存內(nèi)的數(shù)據(jù)能夠化整為零地分布在緩存內(nèi)的各個層級，那么這些數(shù)據(jù)就可能在片上緩存內(nèi)停留更長的時間而不被后續(xù)到來的及時局部組所覆蓋，進而為處理器內(nèi)核的訪存焦點再次轉(zhuǎn)移到這些化整為零的數(shù)據(jù)上創(chuàng)造了更好的命中率，如此迭代積累，必然在片上緩存內(nèi)建立起理想的及時局部性環(huán)境，為改進處理器計算性能挖掘出新的潛力。本文給出的理論分析證明了以及時局部組形態(tài)遷移數(shù)據(jù)從內(nèi)存遷往片上緩存不僅是可行的，而且營造處理器片上緩存內(nèi)及時局部性環(huán)境是合理的。在內(nèi)存和片上緩存之間的數(shù)據(jù)遷移方式蘊含了在微觀層面實施數(shù)據(jù)通信的潛在基礎(chǔ)。