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

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

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

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

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

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

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

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

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

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

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

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

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

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

其中

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

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

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

1.2 片上緩存

處理器片上緩存可以視為“漂浮”在內(nèi)存上面的視窗，內(nèi)存中的數(shù)據(jù)只能在視窗“飛臨”其上的條件下才可以出現(xiàn)在視窗里.數(shù)據(jù)在內(nèi)存中存儲的位置與其在緩存中停留的位置之間的呼應(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ù)來到緩存里可以自由進駐緩存槽，而直接相連和組相聯(lián)的邏輯電路相對簡單，數(shù)據(jù)來到緩存進駐緩存槽需要遵循關(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

使得對內(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中的索引號, 映射Q為從Dn×Dm到Dp×Dq為常規(guī)相聯(lián).

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

圖1是一個將內(nèi)存的數(shù)據(jù)置于緩存的原理解釋圖.按照定義3中規(guī)定的模運算，內(nèi)存中數(shù)據(jù)的地址被予以換算，模運算所得的余數(shù)為數(shù)據(jù)被遷移到緩存中的索引號，該索引號標注了這些數(shù)據(jù)在緩存中所安置的位置，稱為存儲槽索引號.例如，以緩存容量值c=7為模數(shù)，對數(shù)值為9的地址進行模運算得到余數(shù)為2，則位于內(nèi)存位置9上的數(shù)據(jù)被遷移到緩存中后，其在緩存中的索引號為2.圖1顯示了從內(nèi)存地址到片上緩存地址(緩存槽索引號)之間的對應(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與另一個內(nèi)存空間Dp×Dq的容量2p做模運算，所得余數(shù)正好為基本尋址單位v在內(nèi)存空間Dp×Dq里的地址，即緩存槽索引號.又根據(jù)拓撲學(xué)的知識[7-8]，模運算將內(nèi)存空間中的所有基本尋址單位分成2p個等價類.這樣的等價類可以為確定片上緩存容量提供啟發(fā).

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

1.3 訪存焦點與及時局部性

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

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

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

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

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

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

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

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

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

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

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

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

Q:Dn×Dm→Dp×Dq

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

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

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

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

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

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

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

s:Dn×Dm→Dp×Dq

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

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

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

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

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

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

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

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

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

同一緩存槽被來自不同地址的數(shù)據(jù)所同時占領(lǐng)的情形稱為及時局部性折疊.局部性折疊是數(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為對稱及時局部組的半徑，則發(fā)生局部性折疊的充分必要條件是r≥c/2.其中，c為緩存Dp×Dq容量，c=2p.

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

r-(c-h)≥h-r

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

r≥c/2

同理，在圖3(b)中，索引號為h的緩存槽到索引號為0的緩存槽的距離h小于及時局部組的鄰域半徑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為對稱及時局部組的半徑，則不發(fā)生局部性折疊的充分必要條件是

r

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

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

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

定理3設(shè)Q為從內(nèi)存Dn×Dm到緩存Dp×Dq的常規(guī)相聯(lián)，m,n,p,q為自然數(shù)，r為及時局部組鄰域半徑，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′，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)存地址的取值范圍和及時局部組鄰域半徑規(guī)模，常規(guī)相聯(lián)可以使得及時局部組在從一個存儲空間遷往另一個存儲空間的過程中，及時局部組內(nèi)各個數(shù)據(jù)之間的局部性關(guān)系不被破壞，也意味當(dāng)前處理器中片上緩存和內(nèi)存之間的相聯(lián)機制能夠?qū)崿F(xiàn)保持數(shù)據(jù)局部性的遷移.

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

3.1 計算過程與及時局部組

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

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

在存儲容量十分有限的緩存里營造及時局部性環(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ù)據(jù)局部性本質(zhì)的抽象概念局部組鄰域為工具描述了數(shù)據(jù)及時局部性在數(shù)據(jù)遷移過程中發(fā)生變化的基本規(guī)律.

3.2 及時局部組的分拆

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

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

3.3 及時局部組的覆蓋

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

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

4 結(jié)論

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

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

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