張建民 黎鐵軍 李思昆

（國(guó)防科學(xué)技術(shù)大學(xué)計(jì)算機(jī)學(xué)院 長(zhǎng)沙 410073）（jmzhang＠nudt．edu．cn）

一種并行計(jì)算機(jī)互連網(wǎng)絡(luò)中的地址轉(zhuǎn)換Cache

張建民 黎鐵軍 李思昆

（國(guó)防科學(xué)技術(shù)大學(xué)計(jì)算機(jī)學(xué)院 長(zhǎng)沙 410073）（jmzhang＠nudt．edu．cn）

當(dāng)前在大規(guī)模并行計(jì)算機(jī)中，多數(shù)并行程序的用戶習(xí)慣于使用虛擬地址進(jìn)行編程．因此，虛擬地址與物理地址之間的轉(zhuǎn)換效率直接影響了并行程序的執(zhí)行性能，而cache能夠有效地提高虛實(shí)地址轉(zhuǎn)換的效率并降低延遲．提出了一種在大規(guī)模并行計(jì)算機(jī)互連網(wǎng)絡(luò)中的地址轉(zhuǎn)換cache．它采用了嵌入式DRAM（embedded dynamic random access memory，eDRAM）存儲(chǔ)器，容納更多的地址轉(zhuǎn)換表項(xiàng)，從而提高命中率．并設(shè)計(jì)一種eDRAM刷新機(jī)制，隱藏了刷新操作，避免刷新導(dǎo)致的性能損失．ATC（address translation cache）中實(shí)現(xiàn)了諸如糾錯(cuò)碼與旁路機(jī)制等多種可靠性設(shè)計(jì)．在32個(gè)計(jì)算結(jié)點(diǎn)上運(yùn)行業(yè)界公認(rèn)的NPB測(cè)試程序，結(jié)果顯示32個(gè)結(jié)點(diǎn)中ATC的平均命中率達(dá)到了95．3%，表明ATC設(shè)計(jì)的正確性與高性能．并且通過與3種傳統(tǒng)SRAM（static random access memory）實(shí)現(xiàn)的cache進(jìn)行對(duì)比實(shí)驗(yàn)，說明了cache容量是提高命中率的關(guān)鍵因素．

并行計(jì)算機(jī)；互連網(wǎng)絡(luò)；虛擬地址；物理地址；地址轉(zhuǎn)換cache

當(dāng)前高性能大規(guī)模并行計(jì)算機(jī)通常包含成千上萬(wàn)個(gè)計(jì)算結(jié)點(diǎn)［1］．結(jié)點(diǎn)數(shù)目眾多以及大規(guī)模并行性的需求，使得互連網(wǎng)絡(luò)的設(shè)計(jì)變得十分困難．對(duì)于多數(shù)并行程序來說，要求互連網(wǎng)絡(luò)必須具備高帶寬與低延遲的特性［2－3］．因此，在大規(guī)模并行計(jì)算機(jī)中，設(shè)計(jì)實(shí)現(xiàn)了網(wǎng)絡(luò)接口芯片（network interface chip，NIC）［4］，以滿足互連網(wǎng)絡(luò)高帶寬、低延遲的特點(diǎn)．而在并行應(yīng)用程序中，大多數(shù)用戶習(xí)慣于使用虛擬地址編程，因?yàn)槭褂锰摂M地址編程既簡(jiǎn)單高效又易于保證程序的正確性．那么，在互連網(wǎng)絡(luò)中傳輸?shù)膱?bào)文幾乎都要進(jìn)行虛擬地址到物理地址的轉(zhuǎn)換，使得在程序運(yùn)行過程中，存在大量的虛實(shí)地址轉(zhuǎn)換操作，因此虛實(shí)地址轉(zhuǎn)換的效率直接影響了互連網(wǎng)絡(luò)的通信帶寬與程序的執(zhí)行性能［5－6］．

有學(xué)者在CASES2013會(huì)議上提出了一種優(yōu)化DRAM（dynamic random access memory）cache的命中延遲和失效率的方法［7］，它通過一種全新的組映射策略，同時(shí)兼顧減小命中延遲和失效率．在16核的微處理器中，與經(jīng)典映射策略相比，該方法能夠降低29．3%的命中延遲，并且減少12．1%的失效率．而針對(duì)DRAM cache的訪問帶寬與訪問沖突的問題，學(xué)者們?cè)贑ODES＋I(xiàn)SSS2013會(huì)議上提出了一種自適應(yīng)存儲(chǔ)體映射策略［8］，以應(yīng)對(duì)不同類型應(yīng)用的各種cache訪問模式．通過實(shí)驗(yàn)表明，與傳統(tǒng)的存儲(chǔ)體映射策略相比，本文的方法能夠增加平均19．3%的吞吐率，最大可達(dá)到71%．當(dāng)前多核處理器中存在SRAM（static random access memory）與DRAM cache混合使用的體系結(jié)構(gòu)，其中私有L1與L2cache使用SRAM存儲(chǔ)器，而共享L3和L4 cache采用DRAM存儲(chǔ)器，學(xué)者們?cè)贒AC2014會(huì)議上針對(duì)大容量DRAM cache普遍存在的Tag查找的高延遲問題，提出了一種SRAM?DRAM混合Tag cache的結(jié)構(gòu)［9］，用于判別是否命中L3?L4cache．在一個(gè)16核處理器中，與經(jīng)典結(jié)構(gòu)相比，每周期的平均指令吞吐率能夠提高13．3%．但是，當(dāng)前業(yè)界絕大多數(shù)DRAM cache都是應(yīng)用于多核微處理器中的共享L3和L4cache中，還沒有人將其應(yīng)用于并行計(jì)算機(jī)的互聯(lián)?接口芯片中；另外，SRAM? DRAM混合結(jié)構(gòu)的cache也存在設(shè)計(jì)復(fù)雜、實(shí)現(xiàn)代價(jià)較高的問題．

基于上述原因，在NIC芯片中設(shè)計(jì)實(shí)現(xiàn)了一種大容量、高性能的地址轉(zhuǎn)換cache（address translation cache，ATC）．ATC用于保存地址轉(zhuǎn)換表（address translation table，ATT）項(xiàng)，并根據(jù)虛擬地址訪問ATC得到相應(yīng)的物理地址．為了盡量避免訪問外存，從而減小訪問延遲，就必須提高命中率，因此ATC共計(jì)可容納100萬(wàn)項(xiàng)地址轉(zhuǎn)換表．但由于容量巨大，如果使用SRAM實(shí)現(xiàn)存儲(chǔ)體，那么芯片的設(shè)計(jì)實(shí)現(xiàn)將會(huì)變得極其困難．所以，ATC采用了嵌入式DRAM（embedded dynamic random access memory，eDRAM）存儲(chǔ)器，eDRAM具有面積小、功耗低以及錯(cuò)誤率低的特性．但eDRAM需要定期刷新，會(huì)影響讀寫的效率，因此在ATC中設(shè)計(jì)了一種eDRAM刷新機(jī)制，在讀寫操作的空閑周期進(jìn)行刷新操作，從而達(dá)到將刷新操作隱藏的目的．同時(shí)為了提高訪問帶寬，在ATC中實(shí)現(xiàn)了非阻塞的深度流水線．另外，在ATC中還實(shí)現(xiàn)了多種可靠性設(shè)計(jì)，包括關(guān)鍵存儲(chǔ)器的糾錯(cuò)碼保護(hù)與旁路機(jī)制等．為了驗(yàn)證ATC的性能，構(gòu)建了一個(gè)由32個(gè)計(jì)算結(jié)點(diǎn)組成的并行計(jì)算實(shí)驗(yàn)機(jī)架．通過運(yùn)行業(yè)界公認(rèn)且具有代表性的NPB測(cè)試程序，得到了32個(gè)結(jié)點(diǎn)中NIC芯片的命中率．結(jié)果顯示，32個(gè)結(jié)點(diǎn)中ATC的平均命中率高達(dá)95．3%，表明了ATC設(shè)計(jì)的正確性以及高性能．并且設(shè)計(jì)實(shí)現(xiàn)了3種傳統(tǒng)cache［10－11］并與本文提出的設(shè)計(jì)進(jìn)行對(duì)比實(shí)驗(yàn)；由于傳統(tǒng)cache采用SRAM實(shí)現(xiàn)，受限于面積無(wú)法實(shí)現(xiàn)更大的容量，因此本文ATC的平均命中率大大高于傳統(tǒng)cache．

1 地址轉(zhuǎn)換Cache的體系結(jié)構(gòu)

地址轉(zhuǎn)換cache的主要功能是保存地址轉(zhuǎn)換表，并完成地址轉(zhuǎn)換表的讀寫訪問控制．所謂地址轉(zhuǎn)換表就是指物理地址．由于互連網(wǎng)絡(luò)接口芯片中每個(gè)發(fā)送或接收的報(bào)文都需要根據(jù)虛地址獲取物理地址，因此需要頻繁地訪問遠(yuǎn)端存儲(chǔ)器，其延遲非常大．為了減小系統(tǒng)處理報(bào)文的停頓以及地址轉(zhuǎn)換表訪問的延遲，NIC內(nèi)設(shè)計(jì)實(shí)現(xiàn)了了ATT cache．ATT cache用于保存最近經(jīng)常使用的ATT項(xiàng)，容量達(dá)到39Mb．由于ATT cache的容量小于遠(yuǎn)端存儲(chǔ)器的容量，不可能保存所有的ATT項(xiàng)；因此，當(dāng)報(bào)文需要的ATT項(xiàng)在ATT cache中沒有命中時(shí)，則需要訪問外部存儲(chǔ)器以獲得地址轉(zhuǎn)換表．

ATC的容量為39Mb，映射方式為8路組相聯(lián)．每個(gè)cache行包含8個(gè)ATT項(xiàng)，而每個(gè)ATT項(xiàng)包括32b的物理地址及其7b糾錯(cuò)碼（error correcting code，ECC），那么每個(gè)cache行共計(jì)312b．ATC的每路共計(jì)16 384行，由于ATC的容量很大，因此采用了嵌入式DRAM存儲(chǔ)器實(shí)現(xiàn)ATC的存儲(chǔ)體．通常來講，同樣容量的eDRAM的面積僅是SRAM面積的1?3～1?2，功耗為后者的1?10～1?2．ATC的替換算法采用最近最少使用（least recently used，LRU）算法，以滿足芯片提高性能的需求．ATC的設(shè)計(jì)采用非阻塞的工作方式，即前一個(gè)未完成的訪問操作不會(huì)阻塞后續(xù)訪問的執(zhí)行．為了支持非阻塞訪問，ATC設(shè)置了失效緩沖器，用于記錄失效的報(bào)文地址．圖1給出了ATC的體系結(jié)構(gòu)和外部接口：

Fig．1 Architecture and interface of ATC．圖1 ATC的體系結(jié)構(gòu)與接口

如圖1所示，ATT cache包含10個(gè)主要的模塊．其中輸入隊(duì)列接收來自外部的請(qǐng)求報(bào)文，加入請(qǐng)求源信息，存入對(duì)應(yīng)的FIFO；多個(gè)請(qǐng)求之間采用Round－robin仲裁策略，而后從獲得授權(quán)的FIFO頂端中讀出請(qǐng)求，發(fā)往仲裁器模塊；以流水的方式操作，每個(gè)周期都可以同時(shí)接收所有請(qǐng)求源發(fā)送1個(gè)訪問請(qǐng)求．而輸出隊(duì)列接收從數(shù)據(jù)陣列中讀出的1個(gè)39b的項(xiàng)，而后進(jìn)行ECC校驗(yàn)，得到32bATT項(xiàng)連同是否含ECC不可糾錯(cuò)信號(hào)，根據(jù)請(qǐng)求源信息，返回對(duì)應(yīng)的請(qǐng)求源．優(yōu)先級(jí)仲裁器的請(qǐng)求源共有4個(gè)，分別為失效引擎、輸入隊(duì)列、失效緩沖器和Fill緩沖器，采用優(yōu)先級(jí)仲裁方式，發(fā)往Tag陣列模塊．ATC Tag陣列中包含8個(gè)深度為16 384、寬度為14b的Tag陣列存儲(chǔ)器，由SRAM實(shí)現(xiàn)，保存Tag信息，其中包含有效位、Tag及其ECC糾錯(cuò)碼，該模塊還包含最近最少使用LRU替換策略和相應(yīng)的Tag控制邏輯．

ATC數(shù)據(jù)陣列用于存儲(chǔ)ATC中的ATT數(shù)據(jù)，由cache體數(shù)據(jù)陣列存儲(chǔ)器及其相應(yīng)的控制模塊和接口模塊構(gòu)成，存儲(chǔ)體由8個(gè)深度為16 384、寬度為312b的eDRAM存儲(chǔ)器構(gòu)成．失效緩沖器包含一個(gè)SRAM實(shí)現(xiàn)的緩沖器，用于保存沒有在Tag陣列命中的訪問報(bào)文；待所需的ATT數(shù)據(jù)通過訪存接口返回時(shí)，再將這些失效報(bào)文重新發(fā)射．Fill緩沖器用于保存從外部讀入的ATT數(shù)據(jù)，訪存的粒度為256b，每次讀操作都會(huì)載入8個(gè)32b的ATT項(xiàng)，將其進(jìn)行ECC校驗(yàn)，保存在一個(gè)SRAM實(shí)現(xiàn)的FIFO中，而后發(fā)往數(shù)據(jù)陣列，同時(shí)向仲裁器發(fā)出請(qǐng)求報(bào)文．寫回緩沖器主要是完成ATC訪存請(qǐng)求的緩沖與轉(zhuǎn)換，由一個(gè)SRAM存儲(chǔ)器實(shí)現(xiàn)的FIFO以及相應(yīng)的控制模塊與接口模塊構(gòu)成．訪存接口模塊完成與遠(yuǎn)端存儲(chǔ)器之間的數(shù)據(jù)交換，主要進(jìn)行組包與拆包的工作，同時(shí)發(fā)出相應(yīng)的控制信號(hào)．控制與狀態(tài)寄存器設(shè)置了一組寄存器，用于保存發(fā)送到ATC的控制信息以及來自ATC的狀態(tài)信息．在該模塊內(nèi)還實(shí)現(xiàn)了一個(gè)失效引擎，用于控制ATC中失效ATT項(xiàng)的操作．

2 Tag與數(shù)據(jù)陣列的實(shí)現(xiàn)

Tag與數(shù)據(jù)陣列模塊是ATC中最重要的2個(gè)部件．下面詳細(xì)介紹Tag陣列與數(shù)據(jù)陣列模塊．所謂Tag是指地址位域的一部分．由于ATC采用了8路組相聯(lián)的映像策略，因此Tag存儲(chǔ)陣列由8個(gè)深度為16 384、寬度為14b的SRAM存儲(chǔ)器構(gòu)成，其中14b的Tag項(xiàng)包括8b的Tag及其5b的ECC校驗(yàn)位以及1b的有效位．每組中的每路均有1個(gè)有效位，標(biāo)識(shí)當(dāng)前的cache行是否有效．

ATT cache中采用最近最少使用LRU替換策略，選擇8路中的某一路被替換出去．在ATT cache中有每組有28個(gè)Used位，分別表示8路之間任意2路之間的相互關(guān)系．這些信息保存在64個(gè)深度為256、寬度為28b的Used陣列中．當(dāng)有訪問ATC的操作命中cache的時(shí)候，修改該路與其他7路之間的相互關(guān)系，即修改對(duì)應(yīng)行的Used位．

下面給出Tag陣列與數(shù)據(jù)陣列之間的邏輯結(jié)構(gòu)，以及與ATT地址之間的對(duì)應(yīng)關(guān)系，如圖2所示．

Fig．2 Structure of tag array and data array．圖2 Tag和數(shù)據(jù)陣列的邏輯結(jié)構(gòu)

根據(jù)圖2，Tag陣列控制器的工作流程如下：

1）當(dāng)接收到來自輸入隊(duì)列模塊的請(qǐng)求報(bào)文時(shí)，包括讀ID、訪問地址等位域，從中解析出25b的地址，其中?16：3?位為索引（index），用于Tag陣列的尋址．

2）根據(jù)index，分別從8個(gè)SRAM存儲(chǔ)器中讀出8個(gè)Tag數(shù)據(jù)，按照有效位的標(biāo)識(shí)，8個(gè)Tag數(shù)據(jù)中有效位為1的、同時(shí)與請(qǐng)求地址中的?24：17?位，即Tag，進(jìn)行判等比較．

3）如果存在匹配項(xiàng)，表明當(dāng)前請(qǐng)求報(bào)文命中Tag陣列，那么ATT數(shù)據(jù)陣列中存在該請(qǐng)求要讀寫的ATT，發(fā)送地址、命中路編號(hào)、讀ID等信號(hào)到數(shù)據(jù)陣列模塊；此時(shí)，若當(dāng)前是失效操作，需要清除被命中Tag項(xiàng)的有效位，若是讀操作，則需要將對(duì)應(yīng)的有效位置1．

4）如果不存在匹配項(xiàng)，表明當(dāng)前請(qǐng)求報(bào)文失效，那么數(shù)據(jù)陣列中沒有要訪問的ATT，需要從遠(yuǎn)端主存中載入，于是向訪存接口模塊發(fā)出讀請(qǐng)求，同時(shí)將失效報(bào)文發(fā)送至失效緩沖器中保存．當(dāng)Tag失效時(shí)，需要寫入新的Tag，這時(shí)存在2種情況：①8路的有效位不全為1，那么就將請(qǐng)求報(bào)文的8bTag及其狀態(tài)位寫入有效位為0的路；②8路的有效位全為1，這時(shí)需要將其中1路替換，根據(jù)LRU算法，查詢Used位陣列，得到最近最少使用的一路，而后將Tag寫入該路，將其覆蓋．

ATT數(shù)據(jù)陣列是保存ATT內(nèi)容的存儲(chǔ)陣列，以cache行作為單位進(jìn)行組織，即每個(gè)存儲(chǔ)單元就是1個(gè)cache行．每次讀操作的粒度都固定為256b，也就是1個(gè)cache行，為8個(gè)32b的ATT項(xiàng)．而每個(gè)32b的ATT項(xiàng)都采用7b的糾一檢二ECC校驗(yàn)碼保護(hù)，那么每個(gè)cache行實(shí)際上有8×（32＋7）＝312b．由于數(shù)據(jù)陣列中保存100萬(wàn)個(gè)ATT項(xiàng)，因此總?cè)萘繛?9Mb．而如此大容量的存儲(chǔ)器如果采用SRAM實(shí)現(xiàn)，耗費(fèi)大量的面積與功耗，成本也會(huì)顯著增加，所以在實(shí)現(xiàn)時(shí)使用eDRAM存儲(chǔ)器．但eDRAM存儲(chǔ)器的缺點(diǎn)是需要定期刷新存儲(chǔ)單元，并且刷新可能會(huì)降低讀寫效率．因此設(shè)計(jì)了一種刷新機(jī)制，能夠盡量在讀寫的空閑周期進(jìn)行刷新操作，從而隱藏刷新操作．由于ATC是8路組相聯(lián)，因此ATT數(shù)據(jù)陣列是由8個(gè)存儲(chǔ)器構(gòu)成，那么每個(gè)eDRAM存儲(chǔ)器的容量為4．875Mb，其深度為16 384，寬度為312b，如圖2所示．

ATT數(shù)據(jù)陣列處理2類請(qǐng)求：來自Tag陣列的讀命中請(qǐng)求與來自Fill緩沖器的寫請(qǐng)求．當(dāng)接收到來自Tag陣列的讀ATT請(qǐng)求時(shí)，且讀請(qǐng)求命中Tag，那么就根據(jù)接收的地址與命中路，即請(qǐng)求報(bào)文所匹配的Tag陣列中的同一深度、同一路，從數(shù)據(jù)陣列中讀出對(duì)應(yīng)的cache行，而后根據(jù)訪問ATT地址的?2：0?位，即Offset，從312b的cache行中取出相應(yīng)的39bATT，其中包含了ECC信息，連同接收到的讀ID信息，發(fā)送到輸出緩沖區(qū)．當(dāng)接收到來自Fill緩沖器的寫ATT請(qǐng)求時(shí)，根據(jù)Fill緩沖器發(fā)出的地址，以及Tag控制器指示的空閑路，將312b的cache行寫入ATT數(shù)據(jù)陣列的對(duì)應(yīng)位置．

3 ATT Cache的可靠性設(shè)計(jì)

通常來講，由高能粒子轟擊和噪聲干擾引發(fā)的晶體管瞬時(shí)充放電，改變電路的內(nèi)部狀態(tài)而導(dǎo)致的錯(cuò)誤，稱為軟錯(cuò)誤（soft error rate，SER）．隨著集成電路制造工藝的不斷進(jìn)步，VLSI芯片對(duì)高能粒子和噪聲干擾的敏感性不斷提高，這將使芯片面臨越來越嚴(yán)重的軟錯(cuò)誤威脅，對(duì)集成電路的容錯(cuò)性和可靠性設(shè)計(jì)提出了更高的要求．當(dāng)前在VLSI芯片中，各種存儲(chǔ)單元尤其是cache占據(jù)了芯片面積的40%～70%，是芯片中對(duì)高能粒子最為敏感的部分．芯片發(fā)生的各種軟錯(cuò)誤故障，絕大部分來自于各種存儲(chǔ)單元，尤其是cache．因此目前高可靠集成電路芯片大多都要針對(duì)cache進(jìn)行專門保護(hù)．地址轉(zhuǎn)換cache實(shí)現(xiàn)了3種可靠性設(shè)計(jì)：1）采用軟錯(cuò)誤率更低的eDRAM存儲(chǔ)器；2）在Tag和數(shù)據(jù)等大容量存儲(chǔ)體中加入了糾錯(cuò)編碼ECC；3）設(shè)計(jì)實(shí)現(xiàn)了一種高效的ATT訪問旁路模塊．

一般來講，eDRAM的SER率遠(yuǎn)遠(yuǎn)低于SRAM存儲(chǔ)器，約為后者的1?250，因此在ATC中采用eDRAM實(shí)現(xiàn)數(shù)據(jù)陣列模塊的存儲(chǔ)體．ECC是一種常見的糾錯(cuò)編碼，Tag和數(shù)據(jù)陣列中都采用的是經(jīng)典ECC算法，實(shí)現(xiàn)了糾一檢二功能．所謂糾一檢二是指：如果在原始數(shù)據(jù)與校驗(yàn)碼中有1b發(fā)生錯(cuò)誤，那么該算法能自動(dòng)糾正這1b錯(cuò)；如果在原始數(shù)據(jù)與校驗(yàn)碼中存在2b錯(cuò)，那么該算法能100%檢測(cè)出該錯(cuò)誤．Tag陣列中是由8b原始數(shù)據(jù)產(chǎn)生5bECC校驗(yàn)碼，而數(shù)據(jù)陣列中是由32b原始數(shù)據(jù)生成7b ECC校驗(yàn)碼．

為了提高系統(tǒng)的魯棒性和容錯(cuò)性，還設(shè)計(jì)實(shí)現(xiàn)了一個(gè)ATT訪問旁路模塊（ATT bypass path，ABP）．如果Tag陣列或數(shù)據(jù)存儲(chǔ)體都由于電磁輻射等原因出現(xiàn)不可恢復(fù)的錯(cuò)誤，導(dǎo)致Tag或數(shù)據(jù)陣列無(wú)法正常工作，就通過旁路模塊進(jìn)行訪問ATT的操作．由于ABP實(shí)現(xiàn)簡(jiǎn)單，邏輯較少，并且不包含存儲(chǔ)器，因此不易受到電磁輻射的干擾，可靠性較高．ABP采用阻塞的方式處理請(qǐng)求報(bào)文，主要通過1個(gè)有限狀態(tài)機(jī)來處理請(qǐng)求報(bào)文．該狀態(tài)機(jī)包括5個(gè)狀態(tài)：IDLE，READ0，READ1，WRITE0，WRITE1，如圖3所示．

ABP狀態(tài)機(jī)的各狀態(tài)之間的轉(zhuǎn)換過程為：

1）IDLE．初始狀態(tài)為IDLE，如果檢測(cè)到有請(qǐng)求報(bào)文到達(dá)時(shí)，轉(zhuǎn)換為訪存接口信號(hào)，向外部的存儲(chǔ)控制器發(fā)出讀請(qǐng)求，下一狀態(tài)轉(zhuǎn)換到READ0；否則繼續(xù)在當(dāng)前IDLE狀態(tài)循環(huán)．

2）READ0．如果存儲(chǔ)控制器沒有返回?cái)?shù)據(jù)，則在READ0狀態(tài)循環(huán)，直至接收到讀返回報(bào)文；根據(jù)請(qǐng)求報(bào)文的訪問類型，判斷當(dāng)前是讀操作還是寫操作，若為讀操作，下一狀態(tài)到達(dá)READ1，若為寫操作，轉(zhuǎn)換到WRITE0．

3）READ1．根據(jù)讀請(qǐng)求報(bào)文中地址域的最低3b，從返回報(bào)文中的256bATT數(shù)據(jù)（1個(gè)cache行）中，選擇相應(yīng)的32bATT項(xiàng)，構(gòu)成讀返回報(bào)文，發(fā)送到對(duì)應(yīng)的請(qǐng)求源，轉(zhuǎn)IDLE狀態(tài)．

4）WRITE0．根據(jù)寫請(qǐng)求報(bào)文中地址域的最低3b，將待寫入的32bATT項(xiàng)覆蓋讀返回報(bào)文的256b數(shù)據(jù)中的相應(yīng)ATT項(xiàng)，重新構(gòu)成1個(gè)cache行數(shù)據(jù)，下一狀態(tài)到達(dá)WRITE1．

Fig．3 FSM states transition of ABP．圖3 ABP的狀態(tài)轉(zhuǎn)換圖

Fig．4 Topology of 32Compute nodes．圖4 32個(gè)計(jì)算結(jié)點(diǎn)的拓?fù)浣Y(jié)構(gòu)

5）WRITE1．將新組成的cache行數(shù)據(jù)，構(gòu)成訪存報(bào)文，轉(zhuǎn)換為訪存接口信號(hào)，寫入到外部主存中，而后下一狀態(tài)返回到IDLE．

4 實(shí)驗(yàn)結(jié)果與分析

為了評(píng)估高性能并行計(jì)算機(jī)互聯(lián)網(wǎng)絡(luò)中地址轉(zhuǎn)換cache的性能，構(gòu)建了一個(gè)由32個(gè)計(jì)算結(jié)點(diǎn)構(gòu)成的并行計(jì)算實(shí)驗(yàn)機(jī)架，其拓?fù)浣Y(jié)構(gòu)如圖4所示．每個(gè)計(jì)算結(jié)點(diǎn)包含2個(gè)高性能多核微處理器、1個(gè)硬盤、1個(gè)NIC芯片與DDR3主存．其中NIC芯片通過FPGA芯片實(shí)現(xiàn)，采用了Xilinx Virtex－7系列的XC7V2000T器件，便于進(jìn)行仿真驗(yàn)證與性能對(duì)比評(píng)測(cè)．2個(gè)結(jié)點(diǎn)之間通過全交叉互連的光纖網(wǎng)絡(luò)連接，也就是任意2個(gè)結(jié)點(diǎn)之間都有直接的物理通路進(jìn)行通信．

NPB（NAS parallel benchmarks）［12－13］是廣泛使用的并行計(jì)算機(jī)的測(cè)試基準(zhǔn)程序．與Linkpack程序主要測(cè)試浮點(diǎn)計(jì)算性能不同，NPB的目的在于測(cè)試用戶在并行計(jì)算機(jī)上運(yùn)行實(shí)際應(yīng)用程序的性能，綜合評(píng)估計(jì)算與通信的性能．NPB測(cè)試程序所采用的算法在很多領(lǐng)域得到應(yīng)用，能夠很好地代表一般應(yīng)用程序的實(shí)際性能．NPB根據(jù)測(cè)試程序規(guī)模可以分為A，B，C，D共4級(jí)．其中D級(jí)測(cè)試程序規(guī)模最大，通常運(yùn)行時(shí)間也最長(zhǎng)，能夠更加客觀地反映程序運(yùn)行的實(shí)際性能．因此我們將NPB的D級(jí)題在32個(gè)全互連的計(jì)算結(jié)點(diǎn)上運(yùn)行，評(píng)測(cè)地址轉(zhuǎn)換cache的性能．通常對(duì)于cache來說，命中率是其最重要的性能指標(biāo)，當(dāng)前出現(xiàn)的大部分cache優(yōu)化技術(shù)都是以提高命中率為目標(biāo)的．表1給出了NPB的D級(jí)題運(yùn)行結(jié)束后32個(gè)結(jié)點(diǎn)的NIC芯片中地址轉(zhuǎn)換cache cache的命中率．表1中的第1列給出了結(jié)點(diǎn)編號(hào)；第2列表示在ATC中命中的報(bào)文個(gè)數(shù)；第3列表示各請(qǐng)求源發(fā)送到ATC中請(qǐng)求報(bào)文的總數(shù)；最后1列為命中率＝命中數(shù)?請(qǐng)求數(shù)×100%．

從表1可以看出，對(duì)于所有32個(gè)計(jì)算結(jié)點(diǎn)，本文的地址轉(zhuǎn)換cache的命中率都很高，為94．8%～96．1%．32個(gè)結(jié)點(diǎn)的平均命中率為95．3%．從NPB測(cè)試程序的代表性來看，對(duì)于大多數(shù)程序，無(wú)論是側(cè)重于計(jì)算，還是側(cè)重于通信，或者是計(jì)算與通信的平衡，ATC都能達(dá)到較高的命中率．這主要得益于2點(diǎn)：1）ATC的容量很大，達(dá)到39Mb，能容納高達(dá)100萬(wàn)項(xiàng)地址轉(zhuǎn)換表，并且采用eDRAM存儲(chǔ)器，大大減小了所占用的面積，避免了SRAM實(shí)現(xiàn)導(dǎo)致的空間爆炸問題，使得芯片的實(shí)現(xiàn)成為可能．2）采用了非阻塞的深度流水線，大大提高了處理請(qǐng)求的吞吐率，并且針對(duì)eDRAM的刷新操作可能降低讀寫效率的問題，設(shè)計(jì)了一種刷新機(jī)制，盡量在讀寫操作的空閑周期進(jìn)行刷新操作，從而隱藏刷新操作，顯著降低了刷新操作帶來的負(fù)面作用．

為了驗(yàn)證本文cache的效率，設(shè)計(jì)實(shí)現(xiàn)了3種容量不同的傳統(tǒng)cache設(shè)計(jì)［10－11］，進(jìn)行對(duì)比實(shí)驗(yàn)．其中3種cache的容量分別為4．875Mb，9．75Mb，19．5Mb，采用了傳統(tǒng)的SRAM實(shí)現(xiàn)cache存儲(chǔ)體，每行的寬度都相同，為312b，僅是深度分別變?yōu)?048，4096，8192；同樣采用8路組相聯(lián)與LRU替換策略．由于32結(jié)點(diǎn)并行計(jì)算實(shí)驗(yàn)機(jī)架中，NIC芯片采用FPGA芯片實(shí)現(xiàn)，可以下載不同的設(shè)計(jì)，因此，將3種傳統(tǒng)cache設(shè)計(jì)分別集成在NIC芯片中，進(jìn)行性能對(duì)比與評(píng)測(cè)．表2給出了運(yùn)行NPB程序D級(jí)題結(jié)束后32個(gè)結(jié)點(diǎn)中4種地址轉(zhuǎn)換cache的命中率．其中第2列給出了容量為4．875Mb cache的命中率，其平均命中率為67．0%；第3列是容量為9．75Mb cache的命中率，平均命中率為72．9%；第4列代表了容量為19．5Mb cache的命中率，其平均命中率達(dá)到了81．1%；而最后1列是本文設(shè)計(jì)的39Mb cache的命中率，其平均命中率為95．3%．

由于同樣容量的eDRAM的面積僅是SRAM面積的1?3～1?2，因此在同樣的芯片面積下，使用SRAM實(shí)現(xiàn)cache最多只能達(dá)到19．5Mb，而采用eDRAM可以很容易實(shí)現(xiàn)39Mb甚至更大容量的cache．但是SRAM的讀寫訪問邏輯簡(jiǎn)單、易實(shí)現(xiàn)，也不用考慮刷新的問題，因此讀寫效率比eDRAM略高．但本文設(shè)計(jì)的cache，提出了一種高效的刷新機(jī)制，在讀寫訪問的空閑周期進(jìn)行刷新操作，盡量隱藏額外的刷新操作帶來的帶寬損耗；再加上同樣芯片面積下，eDRAM能夠?qū)崿F(xiàn)容量為39Mb的cache，因此本文設(shè)計(jì)的cache的平均命中率達(dá)到95．3%，大大高于其他3種傳統(tǒng)cache設(shè)計(jì)的命中率．而其他3種cache設(shè)計(jì)中，主要由于容量的因素，19．5Mb＞9．75Mb＞4．875Mb，因此平均命中率也是81．1%＞72．9%＞67．0%．綜上所述，對(duì)于cache的命中率來說，其容量是至關(guān)重要的因素，因此cache設(shè)計(jì)趨勢(shì)是在同樣的芯片面積下盡可能增加容量．

Table 2 Hit Ratio of 4Types of Cache after Running Benchmark表2 4種Cache運(yùn)行測(cè)試程序的命中率%

5 結(jié) 論

提出了一種在并行計(jì)算機(jī)互連網(wǎng)絡(luò)中的地址轉(zhuǎn)換cache．ATC采用了eDRAM存儲(chǔ)器，以容納更多的地址轉(zhuǎn)換表項(xiàng)，從而提高命中率；并設(shè)計(jì)一種eDRAM刷新機(jī)制，隱藏了刷新操作；實(shí)現(xiàn)了非阻塞的深度流水線，提高訪問帶寬．ATC中還實(shí)現(xiàn)了諸如糾錯(cuò)碼與旁路機(jī)制等多種可靠性設(shè)計(jì)．通過在32個(gè)計(jì)算結(jié)點(diǎn)上運(yùn)行NPB測(cè)試程序，結(jié)果表明32個(gè)結(jié)點(diǎn)中ATC的平均命中率達(dá)到了95．3%．并且通過與3種傳統(tǒng)SRAM實(shí)現(xiàn)的cache進(jìn)行對(duì)比實(shí)驗(yàn)，說明了cache容量是提高命中率的關(guān)鍵因素．下一步工作主要是在更多的并行測(cè)試程序上驗(yàn)證ATC的性能．

［1］TOP500Supercomputer Organization．TOP500supercomputers lists［EB?OL］．［2014－06－30］．http：??www．top500．org?lists? 2014?06

［2］Pritchard H，Gorodetsky I，Buntinas D．A uGNI－based MPICH2nemesis network module for the cray XE［G］?? LNCS 6960：Proc of the 18th European MPI Users＇Group Conf on Recent Advances in the Message Passing Interface．Berlin：Springer，2011：110 119

［3］Xie Min，Lu Yutong，Liu Lu，et al．Implementation and evaluation of network interface and message passing services for TianHe－1Asupercomputer［C］??Proc of the 19th IEEE Annual Symp on High Performance Interconnects．Piscataway，NJ：IEEE，2011：78 86

［4］Pang Zhengbin，Xie Min，Zhang Jun，et al．The TH Express high performance interconnect networks［J］．Frontires of Computer Science，2014，8（3）：357 366

［5］Chun Brent N，Mainwaring Alan M，Culler Darid E．Virtual network transport protocols for Myrinet［J］．IEEE Micro，1998，18（1）：53 63

［6］Bhoedjang R A，Ruhl T，Bal H E．User－level network interface protocols［J］．Computer，1998，31（11）：53 60

［7］Hameed F，Bauer L，Henkel J．Simultaneously optimizing DRAM cache hit latency and miss rate via novel set mapping policies［C］??Proc of 2013Int Conf on Compilers，Architecture and Synthesis for Embedded Systems．Piscataway，NJ：IEEE，2013：1 10

［8］Hameed F，Bauer L，Henkel J．Reducing inter－core cache contention with an adaptive bank mapping policy in DRAM cache［C］??Proc of 2013Int Conf on Hardware?Software Codesign and System Synthesis．Piscataway，NJ：IEEE，2013：1 8

［9］Hameed F，Bauer L，Henkel J．Reducing latency in an SRAM?DRAM cache hierarchy via a novel tag－cache architecture［C］??Proc of the 51st Design Automation Conf．New York：ACM，2014：1 6

［10］Corrigan M J，Godtland P，Hinojosa J．Selectively invalidating entries in an address translation cache：USA，United States Patent 7822042［P］．2010－10－26

［11］Carlos F，F(xiàn)ang Z，Ravi R I，et al．Buffer－integrated－cache：A cost－effective SRAM architecture for handheld and embedded platforms［C］??Proc of the 48th Design Automation Conf．New York：ACM，2011：966 971

［12］NASA Advanced Supercomputing Division．NAS Parallel Benchmarks［EB?OL］．［2014－03－02］．http：??www．nas．nasa．gov?publications?npb．html

［13］Yuan Wei，Zhang Yunquan，Sun Jiachang，et al．Performance analysis of NPB benchmark on domestic terascale cluster systems［J］．Journal of Computer Research and Development，2005，42（6）：1079 1084（in Chinese）（袁偉，張?jiān)迫瑢O家昶，等．國(guó)產(chǎn)萬(wàn)億次機(jī)群系統(tǒng)NPB性能測(cè)試分析［J］．計(jì)算機(jī)研究與發(fā)展，2005，42（6）：1079 1084）

Zhang Jianmin，born in 1979．PhD and assistant professor in the National University of Defense Technology．His main research interests include computer architecture，VLSI chip design and verification．

Li Tiejun，born in 1977．PhD and associate professor in the National University of Defense Technology．His main research interests include high performance computer architecture（tjli＠nudt．edu．cn）．

Li Sikun，born in 1941．Professor and PhD supervisor in the National University of Defense Technology．Senior member of China Computer Federation．His main research interests include electronic CAD，chip design methodologies，and virtual reality（lisikun＠263．net．cn）．

An Address Cache of Interconnect Network in Parallel Computers

Zhang Jianmin，Li Tiejun，and Li Sikun
（College of Computer，National University of Defense Technology，Changsha410073）

Most of users are accustomed to utilize the virtual address in their parallel programs running at the scalable parallel computer systems．Therefore the virtual and physical address translation directly affects the performance of the parallel programs．Cache can strongly improve the efficiency of address translation and reduce the latency of translation．In this paper，a new address translation cache（ATC）is proposed for the interconnect network of scalable parallel computer systems．To improve the hit ratio，ATC adopts embedded dynamic random access memory（eDRAM）to store more address translation table items．A new eDRAM refresh mechanism is proposed to hide the refresh operation and avoid the performance loss introduced by refresh．In ATC，there are many reliability techniques，including error correcting code and a novel bypass module．The well－known NPB benchmarks have been run at the 32compute nodes including ATC．The results show that the ATC has high hit ratio which the average value of 32nodes is 95．3%．It is indicated that ATC is well designed and has high performance．It also has been compared with three types of typical cache implemented by different capacities SRAM（static random access memory），and the conclusion is the capacity of cache is key factor to improve the hit ratio．

parallel computer；interconnect network；virtual address；physical address；address translation cache

TP333

2014－09－19；

2015－06－24

國(guó)家自然科學(xué)基金項(xiàng)目（61103083，61133007）；國(guó)家“八六三”高技術(shù)研究發(fā)展計(jì)劃基金項(xiàng)目（2012AA01A301）；國(guó)家“九七三”重點(diǎn)基礎(chǔ)研究發(fā)展計(jì)劃基金項(xiàng)目（2011CB309705）

This work was supported by the National Natural Science Foundation of China（61103083，61133007），the National High Technology Research and Development Program of China（863Program）（2012AA01A301），and the National Basic Research Program of China（973Program）（2011CB309705）．