胡九川，范東睿， 程建聰， 嚴(yán) 龍， 彭 燕， 葉笑春， 李靈枝， 鐘海斌

(1.北京交通大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，北京 100044； 2.中國科學(xué)院計(jì)算技術(shù)研究所 計(jì)算機(jī)體系結(jié)構(gòu)國家重點(diǎn)實(shí)驗(yàn)室，北京 100190)

在計(jì)算機(jī)運(yùn)行過程中，處理器不斷在各個(gè)指令或數(shù)據(jù)之間切換執(zhí)行焦點(diǎn).如果這些被切換的指令或數(shù)據(jù)能夠在一個(gè)相對(duì)的時(shí)間片內(nèi)動(dòng)態(tài)地保留在容量十分有限的處理器片上緩存內(nèi)，那么這些指令或數(shù)據(jù)組成的群組便具有了滿足處理器內(nèi)核訪存需求的局部性的特色，提高了處理器內(nèi)核的訪存效率，消減了處理器內(nèi)核去內(nèi)存訪問指令和數(shù)據(jù)的延遲.由于緩存是臨近處理器內(nèi)核的功能部件，這樣的局部性就具有了及時(shí)的特點(diǎn).在這個(gè)執(zhí)行時(shí)間片內(nèi)，這些被切換的指令或數(shù)據(jù)之間具備了滿足處理器內(nèi)核訪存需求的時(shí)間和空間聯(lián)系[1-5].及時(shí)局部性(In-Time Locality)概括了指令和數(shù)據(jù)之間存在的客觀聯(lián)系，可以將處理器的執(zhí)行過程抽象為執(zhí)行焦點(diǎn)在不同的具有局部性的指令或數(shù)據(jù)族群之間進(jìn)行切換的過程.

這種客觀存在的及時(shí)局部性來源于程序執(zhí)行邏輯的內(nèi)在規(guī)定.指令執(zhí)行順序、數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)與形式的安排是程序這個(gè)邏輯復(fù)合體的基本構(gòu)件，在根本上決定了指令之間、數(shù)據(jù)之間不可割舍的時(shí)空聯(lián)系.這種時(shí)空聯(lián)系自然需要在指令和數(shù)據(jù)從內(nèi)存遷往片上緩存的過程得到保持和維護(hù)，如此才能夠在處理器片上緩存內(nèi)建立有利于處理器訪存的及時(shí)局部性環(huán)境.所以，如何在從內(nèi)存遷往片上緩存中保持和維護(hù)指令或數(shù)據(jù)之間存在的局部性便成為一個(gè)需要深入研究分析的問題.分析研究指令和數(shù)據(jù)在片上緩存和內(nèi)存之間往返遷移的規(guī)律、最大限度保持指令和數(shù)據(jù)之間的時(shí)間和空間聯(lián)系具有重要的現(xiàn)實(shí)意義.

一般地，在指令和數(shù)據(jù)遷移進(jìn)出處理器時(shí)，它們之間存在的局部性聯(lián)系很可能由于它們?cè)趦?nèi)存和片上緩存的存儲(chǔ)位置的改變、共存于緩存中的其他指令或數(shù)據(jù)的占位而發(fā)生變化，使得在處理器原計(jì)劃遵照程序內(nèi)在的邏輯展開運(yùn)算時(shí)，前來向處理器內(nèi)核“報(bào)到”的指令或數(shù)據(jù)可能并不是處理器內(nèi)核所需的，導(dǎo)致這內(nèi)在的程序執(zhí)行邏輯面臨具體展開的困境，形成需求錯(cuò)位的局面.這樣的矛盾局面產(chǎn)生的根源是由于片上緩存容量十分有限，而要進(jìn)入緩存的指令和數(shù)據(jù)量卻是巨大的、乃至邏輯上是無限的，片上緩存中的指令和數(shù)據(jù)需要不斷地從內(nèi)存中遷移更新才能將所有指令和數(shù)據(jù)從內(nèi)存中推到處理器核的面前，方便處理器核的訪問.因此，在處理器內(nèi)核訪問指令或數(shù)據(jù)時(shí)，應(yīng)該將與之存在時(shí)空關(guān)系的其它指令、數(shù)據(jù)一起組合為一個(gè)臨時(shí)的整體遷移到處理器的片上緩存內(nèi)，盡量保持指令或數(shù)據(jù)之間的時(shí)空聯(lián)系，并且將指令之間、數(shù)據(jù)之間的時(shí)空關(guān)系轉(zhuǎn)化為指令、數(shù)據(jù)在片上緩存中的分布形態(tài).控制此分布形態(tài)必然有助于提高處理器內(nèi)核的訪存命中率、減緩訪存延遲，營造出片上及時(shí)局部性環(huán)境.

根據(jù)上面的分析，可以發(fā)現(xiàn)片上及時(shí)局部性環(huán)境的兩個(gè)基本要素：第一、處理器所需要的指令或數(shù)據(jù)可以及時(shí)在片上寄存器或緩存內(nèi)找到；第二、處理器所需要的指令或數(shù)據(jù)可以在片上寄存器或緩存中就近找到.因此，為了提高處理器訪存效率，消減訪存延遲，營造及時(shí)局部性環(huán)境，指令和數(shù)據(jù)不但要遷移到片上緩存內(nèi)，而且要確保指令和數(shù)據(jù)的局部性在一定的時(shí)間內(nèi)不被消解.

如果將指令和數(shù)據(jù)規(guī)約為一個(gè)個(gè)及時(shí)局部組，將指令和數(shù)據(jù)組織在及時(shí)局部組內(nèi)，那么處理器內(nèi)核在各個(gè)指令和數(shù)據(jù)之間切換執(zhí)行焦點(diǎn)的情形可以進(jìn)一步清晰化為執(zhí)行焦點(diǎn)在各個(gè)及時(shí)局部組之間切換，于是營造及時(shí)局部環(huán)境可以以及時(shí)局部組為基本構(gòu)件.實(shí)際上，只有處理器內(nèi)核的執(zhí)行焦點(diǎn)遍歷完一個(gè)程序的所有及時(shí)局部組，程序執(zhí)行的整體效應(yīng)才會(huì)出現(xiàn).如果及時(shí)局部組內(nèi)的指令或數(shù)據(jù)都能夠滿足處理器內(nèi)核的訪存需要，那在整體上程序的執(zhí)行將是一個(gè)理想狀態(tài).在這個(gè)過程中，不但要關(guān)心及時(shí)局部組在遷移過程中產(chǎn)生的變化，而且還要關(guān)注各個(gè)及時(shí)局部組在遷移過程中產(chǎn)生的相互影響.

及時(shí)局部組是一個(gè)以處理器訪存焦點(diǎn)即當(dāng)前被訪問的指令或數(shù)據(jù)為中心、涵蓋一定范圍內(nèi)的指令或數(shù)據(jù)組成的、具有時(shí)空關(guān)聯(lián)關(guān)系的指令或數(shù)據(jù)族群.在本文作者以及時(shí)局部組內(nèi)的指令或數(shù)據(jù)之間的關(guān)聯(lián)關(guān)系在遷移過程中發(fā)生的變化為入手點(diǎn)，研究分析及時(shí)局部環(huán)境內(nèi)在機(jī)制，探索理想狀態(tài)產(chǎn)生的前提條件.運(yùn)用抽象的數(shù)學(xué)方法研究分析指令或數(shù)據(jù)在處理器片上緩存和內(nèi)存之間往返遷移的規(guī)律，尋找遷移過程中保持指令或數(shù)據(jù)及時(shí)局部性的前提條件.為了行文簡便，在本文中指令和數(shù)據(jù)統(tǒng)稱為數(shù)據(jù).

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

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

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

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

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

Dn×Dm={(a1,a2,…,an,d1,d2,…,dm)}

其中

(a1,a2,…,an)∈Dn,(d1,d2,…,dm)∈Dm

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

從定義2可知，基本尋址單位泛指存儲(chǔ)在內(nèi)存中的指令或數(shù)據(jù).兩個(gè)基本尋址單位的距離可以定義為地址之間的距離.

1.2 片上緩存

處理器片上緩存可以視為“漂浮”在內(nèi)存上面的視窗，內(nèi)存中的數(shù)據(jù)只能在視窗“飛臨”其上的條件下才可以出現(xiàn)在視窗里.數(shù)據(jù)在內(nèi)存中存儲(chǔ)的位置與其在緩存中停留的位置之間的呼應(yīng)關(guān)系便是緩存和內(nèi)存的關(guān)聯(lián)關(guān)系，即全相聯(lián)、直接相連和組相聯(lián).這樣的關(guān)聯(lián)關(guān)系影響數(shù)據(jù)從內(nèi)存中遷移來緩存后的在緩存內(nèi)的分布形態(tài).緩存和內(nèi)存全相聯(lián)需要復(fù)雜的邏輯電路，但是數(shù)據(jù)來到緩存里可以自由進(jìn)駐緩存槽，而直接相連和組相聯(lián)的邏輯電路相對(duì)簡單，數(shù)據(jù)來到緩存進(jìn)駐緩存槽需要遵循關(guān)聯(lián)約定.為描述這關(guān)聯(lián)約定，下面給出片上緩存的定義.

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

Q:Dn×Dm→Dp×Dq

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

u=(a1,a2,…,an,d1,d2,…,dm)

存在內(nèi)存Dp×Dq中的基本尋址單位

v=(i1,i2,…,ip,c1,c2,…,cq)

的地址滿足：

a12n-1+a22n-2+…+an=g2p+I

其中g(shù)為自然數(shù)，2p>I，

I=i12p-1+i22p-2+…+ip

則稱內(nèi)存Dp×Dq為內(nèi)存Dn×Dm的常規(guī)緩存，稱I為基本尋址單位在常規(guī)緩存Dp×Dq中的索引號(hào), 映射Q為從Dn×Dm到Dp×Dq為常規(guī)相聯(lián).

將一個(gè)大容量結(jié)構(gòu)內(nèi)的數(shù)據(jù)納入到一個(gè)容量相對(duì)十分小的結(jié)構(gòu)內(nèi)的基本方法是將大容量結(jié)構(gòu)內(nèi)的數(shù)據(jù)分成等價(jià)類，使得等價(jià)類中的數(shù)據(jù)能夠出現(xiàn)在這個(gè)容量相對(duì)小的結(jié)構(gòu)“視窗”之中，如此才能在邏輯意義上將一個(gè)大容量結(jié)構(gòu)置于小容量結(jié)構(gòu)之中.目前，片上緩存與內(nèi)存之間的關(guān)聯(lián)結(jié)構(gòu)主要是通過等價(jià)分類實(shí)現(xiàn)的[3,6].定義3揭示了該等價(jià)類方法的本質(zhì)，其中基本尋址單位在緩存中的索引號(hào)就是通過模運(yùn)算折算出來，模運(yùn)算是對(duì)數(shù)值進(jìn)行等價(jià)分類的常用方法.

圖1是一個(gè)將內(nèi)存的數(shù)據(jù)置于緩存的原理解釋圖.按照定義3中規(guī)定的模運(yùn)算，內(nèi)存中數(shù)據(jù)的地址被予以換算，模運(yùn)算所得的余數(shù)為數(shù)據(jù)被遷移到緩存中的索引號(hào)，該索引號(hào)標(biāo)注了這些數(shù)據(jù)在緩存中所安置的位置，稱為存儲(chǔ)槽索引號(hào).例如，以緩存容量值c=7為模數(shù)，對(duì)數(shù)值為9的地址進(jìn)行模運(yùn)算得到余數(shù)為2，則位于內(nèi)存位置9上的數(shù)據(jù)被遷移到緩存中后，其在緩存中的索引號(hào)為2.圖1顯示了從內(nèi)存地址到片上緩存地址(緩存槽索引號(hào))之間的對(duì)應(yīng)關(guān)系.

圖1 內(nèi)存和緩存關(guān)聯(lián)關(guān)系示意圖Fig.1 Schematic diagram of memory and cache association

不難發(fā)現(xiàn)，內(nèi)存空間Dn×Dm中的基本尋址單位的地址u與另一個(gè)內(nèi)存空間Dp×Dq的容量2p做模運(yùn)算，所得余數(shù)正好為基本尋址單位v在內(nèi)存空間Dp×Dq里的地址，即緩存槽索引號(hào).又根據(jù)拓?fù)鋵W(xué)的知識(shí)[7-8]，模運(yùn)算將內(nèi)存空間中的所有基本尋址單位分成2p個(gè)等價(jià)類.這樣的等價(jià)類可以為確定片上緩存容量提供啟發(fā).

緩存是層次結(jié)構(gòu)意義上的內(nèi)存，且靠近處理器核更近，數(shù)據(jù)局部組的及時(shí)性只有在其進(jìn)駐緩存后才能顯著地呈現(xiàn)出來.本文的討論僅圍繞常規(guī)緩存展開.

1.3 訪存焦點(diǎn)與及時(shí)局部性

處理器當(dāng)前訪存所指向的內(nèi)存位置稱為處理器的訪存焦點(diǎn).與訪存焦點(diǎn)存在局部性聯(lián)系的其他數(shù)據(jù)具有一定程度的焦點(diǎn)色彩.這種焦點(diǎn)關(guān)聯(lián)在實(shí)踐中的表現(xiàn)是，當(dāng)緩存內(nèi)的數(shù)據(jù)被訪問后，該數(shù)據(jù)或被再次訪問，或與該數(shù)據(jù)相鄰的數(shù)據(jù)將被訪問.所以作為焦點(diǎn)和焦點(diǎn)化的數(shù)據(jù)應(yīng)作為一整體遷移到緩存中來，使數(shù)據(jù)的位置相互靠攏匯聚起來，處理器內(nèi)核因此能方便定位到它們.

定義4設(shè)m,n為自然數(shù)，r為非負(fù)整數(shù)，

u=(a1,a2,…,an,d1,d2,…,dm)

為內(nèi)存Dn×Dm中任意一個(gè)基本尋址單位，稱集合

N(u,r)={u′:e(u-u′)

為以基本尋址單位u為中心的鄰域.其中，e(u-u')為兩個(gè)基本可尋址單位u和u′之間的向量距離.

以一個(gè)處理器內(nèi)核的當(dāng)前訪存焦點(diǎn)u為中心，以距離r為半徑，可在內(nèi)存中劃定一個(gè)不超出此半徑的對(duì)稱區(qū)域，區(qū)域內(nèi)匯集了一組按照地址順序排列的基本尋址單位，訪存焦點(diǎn)位于隊(duì)列正中央，該對(duì)稱區(qū)域構(gòu)成一個(gè)以訪存焦點(diǎn)為中心的鄰域N(u,r)，該鄰域是一個(gè)對(duì)稱及時(shí)局部組.

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

以基本尋址單位的鄰域?yàn)槊浇?，可營造處理器內(nèi)核訪問數(shù)據(jù)的及時(shí)局部性環(huán)境，完善片上緩存內(nèi)數(shù)據(jù)遷移的機(jī)制.這意味將改進(jìn)計(jì)算性能的探索不再靜止停留在緩存結(jié)構(gòu)層面，而是上升到動(dòng)態(tài)利用數(shù)據(jù)局部性關(guān)聯(lián)的新層面.局部性跨度是反映局部性狀態(tài)變化的指標(biāo).

定義5設(shè)m,n,p,q為自然數(shù)，r為非負(fù)整數(shù)，

u=(a1,a2,…,an,d1,d2,…,dm)

為內(nèi)存Dn×Dm中任意一個(gè)基本尋址單位,

Q:Dn×Dm→Dp×Dq

為一個(gè)常規(guī)相聯(lián)，稱

Q(u+r)-Q(u-r)

為以基本尋址單位u為中心的局部性跨度.

局部性跨度是一個(gè)刻畫數(shù)據(jù)局部性涉及范圍的尺度，意味那些存在于跨度之外的數(shù)據(jù)不再納入局部性考慮的范圍.在數(shù)據(jù)及時(shí)局部組從內(nèi)存遷往片上緩存的過程中，局部性跨度可能因片上緩存和內(nèi)存的關(guān)聯(lián)關(guān)系而發(fā)生改變.

2 數(shù)據(jù)遷移分析

為營造在片上緩存內(nèi)服務(wù)處理器內(nèi)核訪存的及時(shí)局部性環(huán)境，作為整體遷移的及時(shí)局部組鄰域N(u,r)內(nèi)數(shù)據(jù)之間的局部性關(guān)系應(yīng)該保持穩(wěn)定，即保持鄰域結(jié)構(gòu)的拓?fù)浣Y(jié)構(gòu)[7]穩(wěn)定，不被遷移所改變.故引入如下概念.

定義6設(shè)Dp×Dq,Dn×Dm為內(nèi)存,m,n,p,q為自然數(shù).對(duì)任意的u∈Dn×Dm,如果映射

s:Dn×Dm→Dp×Dq

滿足：對(duì)任意的u′∈N(u,r),有

s(u')∈N(s(u),r)

則稱s為從內(nèi)存Dn×Dm到內(nèi)存Dp×Dq的一個(gè)局部性保持遷移.

在數(shù)據(jù)從內(nèi)存遷移到緩存的過程中，及時(shí)局部組內(nèi)數(shù)據(jù)的局部性關(guān)系可能會(huì)發(fā)生形變，造成及時(shí)局部組鄰域被分拆或折疊，詳見下面的實(shí)例.

例1 圖2顯示了一個(gè)常規(guī)緩存中緩存槽索引號(hào)和內(nèi)存地址的對(duì)應(yīng)關(guān)系.例如索引號(hào)為3的緩存槽可以接納來自內(nèi)存地址為3、11、19、27、…的數(shù)據(jù).以任意一個(gè)內(nèi)存地址為中心，取鄰域半徑為2，可以構(gòu)成一個(gè)以該地址為中心的及時(shí)局部組.

圖2 片上緩存中數(shù)據(jù)分配示意圖Fig.2 Diagram of data allocation in the on-chip cache

在圖2中，以那些分別以索引號(hào)為2、3、4、5關(guān)聯(lián)的地址上的數(shù)據(jù)為中心的及時(shí)局部組可以保持局部性地遷移到緩存內(nèi).例如，以地址20為中心的局部組占據(jù)一個(gè)連續(xù)的地址段18、19、20、21、22，這些內(nèi)存地址上的數(shù)據(jù)之間的關(guān)聯(lián)關(guān)系可以不被分拆地遷移到緩存內(nèi)一組相鄰索引號(hào)2、3、4、5、6所指定的緩存槽內(nèi).然而，以那些只能和索引號(hào)為0、1、6、7的地址上的數(shù)據(jù)為中心的及時(shí)局部組卻不能保持其局部性遷移到緩存內(nèi).例如，以地址15為中心的及時(shí)局部組占據(jù)一個(gè)連續(xù)地址段13、14、15、16、17，該地址段上的數(shù)據(jù)被遷移到緩存內(nèi)一組由不相鄰索引號(hào)5、6、7、0、1所指定的片上緩存槽內(nèi).索引號(hào)為5的緩存槽與索引號(hào)為1的緩存槽之間的距離為3，超過了及時(shí)局部組的鄰域半徑2.

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

例2 在圖2中，選擇及時(shí)局部組鄰域半徑為6，以地址22為中心的及時(shí)局部組占據(jù)一個(gè)連續(xù)地址段16、…、21、22、23、…、28，這些地址上的數(shù)據(jù)被遷移到緩存內(nèi)后，一些緩存槽將同時(shí)被兩個(gè)來自不同內(nèi)存地址的數(shù)據(jù)所占據(jù).例如圖2中索引號(hào)為3的緩存槽被來自內(nèi)存地址為19，27的不同數(shù)據(jù)同時(shí)占據(jù)，這顯然是不合理的.

同一緩存槽被來自不同地址的數(shù)據(jù)所同時(shí)占領(lǐng)的情形稱為及時(shí)局部性折疊.局部性折疊是數(shù)據(jù)過度靠攏的畸形形態(tài)，在數(shù)據(jù)從內(nèi)存遷往緩存的過程中，應(yīng)杜絕局部性折疊.

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

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

r-(c-h)≥h-r

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

r≥c/2

同理，在圖3(b)中，索引號(hào)為h的緩存槽到索引號(hào)為0的緩存槽的距離h小于及時(shí)局部組的鄰域半徑r且

r-h≥c-(h+r)

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

r≥c/2

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

下面證明充分條件.假設(shè)不發(fā)生局部性折疊，則r-(c-h)

r

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

(a)高地址端

(b)低地址端圖3 靠近緩存地址端Fig.3 Close to the cache address end

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

r

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

證明2 由定理1可以推得定理2成立.

根據(jù)定理1和定理2，只要及時(shí)局部組鄰域半徑的數(shù)值不超過緩存容量的一半，局部性折疊就不會(huì)發(fā)生.然而定理3指出局部性分拆必然經(jīng)常發(fā)生.

定理3設(shè)Q為從內(nèi)存Dn×Dm到緩存Dp×Dq的常規(guī)相聯(lián)，m,n,p,q為自然數(shù)，r為及時(shí)局部組鄰域半徑，c為緩存Dp×Dq的容量，c=2p，0

證明3 根據(jù)0，當(dāng)0

當(dāng)r

(a) h

(b) r

(c) c-r

定理4設(shè)Q為從內(nèi)存Dn×Dm到緩存Dp×Dq的常規(guī)相聯(lián)，m,n,p,q為自然數(shù)，r為局部組鄰域半徑，c為緩存Dp×Dq的容量，c=2p，r

證明4 任取基本尋址單位u′∈N(u,r)，設(shè)u′在緩存Dp×Dq中的緩存槽索引號(hào)為h′，u，u′在內(nèi)存中的地址分別是Du,Du′,根據(jù)定義3必然存在正整數(shù)g，g′滿足

Du=gc+h

Du′=g′c+h′

其中，r

Du-Du=(g-g′)c+h-h′

不妨設(shè)g>g′>0,于是

如果g≠g′，那么產(chǎn)生矛盾.因此，g=g′,r>h-h′.Q是局部性保持遷移.

根據(jù)定理4，只要控制內(nèi)存地址的取值范圍和及時(shí)局部組鄰域半徑規(guī)模，常規(guī)相聯(lián)可以使得及時(shí)局部組在從一個(gè)存儲(chǔ)空間遷往另一個(gè)存儲(chǔ)空間的過程中，及時(shí)局部組內(nèi)各個(gè)數(shù)據(jù)之間的局部性關(guān)系不被破壞，也意味當(dāng)前處理器中片上緩存和內(nèi)存之間的相聯(lián)機(jī)制能夠?qū)崿F(xiàn)保持?jǐn)?shù)據(jù)局部性的遷移.

3 及時(shí)局部性環(huán)境分析

3.1 計(jì)算過程與及時(shí)局部組

計(jì)算展開的過程是一個(gè)在計(jì)算機(jī)內(nèi)的能量傳遞改變物質(zhì)載體能量狀態(tài)的控制過程，更是一個(gè)實(shí)踐活動(dòng)邏輯展開的過程；邏輯關(guān)系的銜接決定了這個(gè)過程中產(chǎn)生的中間結(jié)果、最終結(jié)果必須予以保存.所以，寄存器、片上緩存、內(nèi)存的客觀存在是計(jì)算的內(nèi)在規(guī)定.

表達(dá)邏輯過程的基本工具是指令集，指令集決定著處理器內(nèi)部的數(shù)據(jù)通路和流水線的基本形態(tài).內(nèi)存、緩存、數(shù)據(jù)通路中和流水線上散布的數(shù)據(jù)卻只能伴隨計(jì)算過程的展開順勢(shì)而動(dòng).高性能計(jì)算要求來到片上緩存的數(shù)據(jù)能夠滿足處理器內(nèi)核的訪存需要.這實(shí)質(zhì)是要求在高速計(jì)算的條件下，處理器的訪存焦點(diǎn)能夠按照程序的執(zhí)行邏輯在不同的數(shù)據(jù)之間進(jìn)行順暢地切換.如果順暢地切換訪存焦點(diǎn)能夠在片上緩存里實(shí)現(xiàn)，那么處理器內(nèi)核訪存延遲會(huì)大幅度縮短，計(jì)算性能得到提高.為了最大限度地實(shí)現(xiàn)訪存焦點(diǎn)的順暢切換，應(yīng)該改變數(shù)據(jù)在處理器運(yùn)行過程中“順勢(shì)而動(dòng)”的被動(dòng)的局面，使之呈現(xiàn)“迎勢(shì)而行”的主動(dòng)姿態(tài).這就是營造片上緩存中及時(shí)局部性環(huán)境的根本原因.

在存儲(chǔ)容量十分有限的緩存里營造及時(shí)局部性環(huán)境，需要保證有效數(shù)據(jù)持續(xù)地來到片上緩存中.因此，控制數(shù)據(jù)在內(nèi)存和緩存之間往來遷移的方式方法是關(guān)鍵.為了確保遷移數(shù)據(jù)的功效，自然需要將具有局部性關(guān)聯(lián)關(guān)系的數(shù)據(jù)一起遷往緩存.所以，要研究分析數(shù)據(jù)局部性、遷移數(shù)據(jù)的片上環(huán)境.

在前面的工作中分析了數(shù)據(jù)局部性存在的根源，抽象概括了當(dāng)前片上緩存和內(nèi)存的關(guān)聯(lián)結(jié)構(gòu)的本質(zhì)特征，從處理器內(nèi)核的訪存姿態(tài)揭示了數(shù)據(jù)及時(shí)局部性的時(shí)間和空間含義，并以反映數(shù)據(jù)局部性本質(zhì)的抽象概念局部組鄰域?yàn)楣ぞ呙枋隽藬?shù)據(jù)及時(shí)局部性在數(shù)據(jù)遷移過程中發(fā)生變化的基本規(guī)律.

3.2 及時(shí)局部組的分拆

從第3節(jié)中給出的研究結(jié)果可以發(fā)現(xiàn)：數(shù)據(jù)及時(shí)局部性是一個(gè)以處理器內(nèi)核的訪存焦點(diǎn)為原點(diǎn)的時(shí)空視野.由于內(nèi)存中存儲(chǔ)單元是線性排列的，數(shù)據(jù)及時(shí)局部性被抽象為一個(gè)鄰域形式來描述以訪存焦點(diǎn)為中心的覆蓋范圍.這種鄰域覆蓋下的數(shù)據(jù)被遷移到片上緩存里后，鄰域形式要么保持，要么發(fā)生分拆(由于緩存容量遠(yuǎn)遠(yuǎn)小于內(nèi)存，發(fā)生及時(shí)局部組鄰域折疊只是理論上有可能，實(shí)踐上幾乎不可能)，但是，具有局部性關(guān)系的數(shù)據(jù)都以鄰域?yàn)閱挝积R聚到了片上緩存里，來到了處理器內(nèi)核的周邊.不論這些數(shù)據(jù)是否聚集在一起，對(duì)于處理器內(nèi)核來講，構(gòu)成片上緩存的邏輯電路可以讓處理器內(nèi)核瞬間訪問到鄰域中的任何數(shù)據(jù)，所以，能夠及時(shí)訪問這些數(shù)據(jù)，意味局部組內(nèi)聚的及時(shí)性在處理器的片上緩存中可以成為及時(shí)訪問的現(xiàn)實(shí).

這種可及時(shí)地訪問的現(xiàn)實(shí)能否在一段時(shí)間內(nèi)在緩存中存在下去與及時(shí)局部組鄰域分拆與否有關(guān).處理器內(nèi)核對(duì)一個(gè)及時(shí)局部組的訪問是一個(gè)計(jì)算過程里的一個(gè)短暫瞬間，這些對(duì)各個(gè)及時(shí)局部組訪問的短暫瞬間串接起來形成一個(gè)以時(shí)間度量的過程.在這個(gè)過程中，處理器內(nèi)核的訪存過程可以先粗顆粒地劃分為對(duì)及時(shí)局部組的逐個(gè)訪問，然后在對(duì)每個(gè)及時(shí)局部組的訪問中細(xì)顆粒地劃分為對(duì)每個(gè)數(shù)據(jù)的訪問.當(dāng)處理器的訪存焦點(diǎn)不是在一個(gè)及時(shí)局部組內(nèi)的各個(gè)數(shù)據(jù)之間切換,而是在各個(gè)及時(shí)局部組之間切換時(shí)，作為切換目標(biāo)的及時(shí)局部組會(huì)存在兩種不理想的可能:要么該及時(shí)局部組未曾被遷移到緩存中來，要么該及時(shí)局部組曾經(jīng)被遷移到緩存內(nèi)卻被后來遷移到緩存的其他及時(shí)局部組所覆蓋.如果及時(shí)局部組在緩存內(nèi)發(fā)生分拆，那么及時(shí)局部組被覆蓋的可能性降低，于是及時(shí)局部組內(nèi)聚的可及時(shí)訪問的現(xiàn)實(shí)性在緩存內(nèi)存在下去的可能性就會(huì)提高.

3.3 及時(shí)局部組的覆蓋

盡管由于處理器片上緩存容量有限，遷來緩存的數(shù)據(jù)最終是要被后續(xù)到來的數(shù)據(jù)所覆蓋的.但是，控制數(shù)據(jù)在片上緩存內(nèi)的分布，保證數(shù)據(jù)在一段時(shí)間內(nèi)不被覆蓋是可行的.如果片上緩存和內(nèi)存之間的關(guān)聯(lián)關(guān)系是滿足定義3要求的常規(guī)相聯(lián)關(guān)系，那么通過控制及時(shí)局部組鄰域半徑或者及時(shí)局部性跨度，利用及時(shí)局部組的分拆，就可以增加數(shù)據(jù)在緩存中的駐留機(jī)會(huì).因此，當(dāng)內(nèi)存中的數(shù)據(jù)以及時(shí)局部組鄰域?yàn)閱挝贿w來片上緩存后，應(yīng)該化整為零分散隱蔽起來，避免被后續(xù)到來的數(shù)據(jù)所覆蓋，爭取駐留緩存的最大機(jī)會(huì).定理3和定理4指出，在緩存和內(nèi)存之間存在常規(guī)相聯(lián)的條件下，如果一個(gè)及時(shí)局部組鄰域中的任何一個(gè)數(shù)據(jù)在內(nèi)存中的地址的數(shù)值是緩存容量的整數(shù)倍，那么該及時(shí)局部組鄰域前往緩存后必然發(fā)生分拆.所以，利用分拆增加數(shù)據(jù)駐留緩存的機(jī)會(huì)是可行的.

總而言之，為了營造片上及時(shí)局部性環(huán)境不僅要以群組為單位從內(nèi)存往緩存遷移數(shù)據(jù)以提高處理器內(nèi)核的訪存命中率，而且要分拆來到緩存的數(shù)據(jù)群組以保持、提高片上及時(shí)局部性環(huán)境的質(zhì)量，維持命中率處于一個(gè)持續(xù)的理想狀態(tài).這個(gè)結(jié)論說明，當(dāng)把數(shù)據(jù)群組遷往緩存時(shí)，盡量將它們分拆開來.比如，可以在進(jìn)程的虛地址和實(shí)地址的轉(zhuǎn)化過程中變換數(shù)據(jù)地址，使得群組數(shù)據(jù)的地址產(chǎn)生分拆.這樣不僅可以提高內(nèi)存的訪存命中率，而且使得進(jìn)程的執(zhí)行安全可控.

4 結(jié)論

1)隨著數(shù)據(jù)及時(shí)局部組不斷進(jìn)駐片上緩存，及時(shí)局部環(huán)境發(fā)揮了積累效應(yīng).從數(shù)據(jù)在內(nèi)存中的地址排列順序看，內(nèi)存中的及時(shí)局部組所涵蓋的局部性具有顯著的線性特征.這種線性特征是內(nèi)存的線性特質(zhì)所決定的.內(nèi)存的線性特質(zhì)來源于計(jì)算機(jī)體系結(jié)構(gòu)的設(shè)計(jì)選擇.

2)當(dāng)具有局部性關(guān)系的數(shù)據(jù)從內(nèi)存遷往片上緩存的時(shí)候，及時(shí)局部組的分拆使得局部組的線性特征出現(xiàn)淡化.這種分拆導(dǎo)致局部組線性特征的淡化恰恰使得局部組內(nèi)含的局部性沖破了線性的束縛展現(xiàn)了出來.

3)應(yīng)該圍繞數(shù)據(jù)的局部性來從理論和實(shí)踐兩個(gè)方面探索片上緩存的未來體系結(jié)構(gòu)，以及處理器內(nèi)核中緩存數(shù)據(jù)的存儲(chǔ)裝置，以此提升處理器的計(jì)算性能.