內(nèi)存與片上滲透緩存之間數(shù)據(jù)遷移的理論分析

胡九川，范東睿，程建聰，嚴(yán)龍，葉笑春，李靈枝，萬(wàn)良易，鐘海斌

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

1 引言

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.2 片上緩存

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 及時(shí)局部性的分拆與折疊

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

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

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

及時(shí)局部組遷移后其鄰域半徑被拉長(zhǎng)的情形稱(chēng)為及時(shí)局部性分拆。反過(guò)來(lái)，如果及時(shí)局部組半徑過(guò)大，會(huì)出現(xiàn)一個(gè)緩存槽被來(lái)自?xún)?nèi)存中地址不同的2 個(gè)數(shù)據(jù)同時(shí)占據(jù)的不合理情形。

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

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

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

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

圖4 靠近緩存高地址端

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

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

圖5 靠近緩存低地址端

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

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

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

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

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

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

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

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

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

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

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

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

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

5 仿真實(shí)驗(yàn)

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

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

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

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

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

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

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

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

6 結(jié)束語(yǔ)

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

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