呂 暉，丁亞軍，鄭 方，吳 東，謝向輝

(1.數(shù)學工程與先進計算國家重點實驗室，江蘇 無錫 214125;2.江南計算技術研究所，江蘇 無錫 214000)

支持跨步訪問的嵌入式存儲系統(tǒng)*

呂 暉1，丁亞軍2，鄭 方1，吳 東1，謝向輝1

(1.數(shù)學工程與先進計算國家重點實驗室，江蘇 無錫 214125;2.江南計算技術研究所，江蘇 無錫 214000)

提出了一種新型多素數(shù)嵌入式存儲系統(tǒng)，能夠顯著改善系統(tǒng)跨步訪問的性能。提高跨步訪存的帶寬，對于改善系統(tǒng)的整體性能有著重要的意義。但是，在嵌入式系統(tǒng)中，受片外結(jié)構(gòu)的尺寸限制，直接應用經(jīng)典的素數(shù)存儲系統(tǒng)理論無法顯著改善跨步訪存性能。為此，該新型系統(tǒng)以素數(shù)存儲系統(tǒng)理論為基礎，引入主存訪問調(diào)度策略并結(jié)合嵌入式系統(tǒng)的實際結(jié)構(gòu)特征，構(gòu)造了一種兩層結(jié)構(gòu)的多素數(shù)存儲系統(tǒng)，可以用較少數(shù)量的存儲模塊實現(xiàn)，而且從邏輯地址到物理地址的映像計算簡單，能夠以相對較小的硬件代價實現(xiàn)對嵌入式存儲系統(tǒng)跨步訪問的有效支持。理論分析和實驗結(jié)果均證實了該系統(tǒng)的正確性和有效性。

嵌入式系統(tǒng)；跨步訪問；存儲系統(tǒng)；主存調(diào)度訪問策略

1 引言

數(shù)字信號處理和通信領域中的很多應用，如向量計算、矩陣計算、快速傅里葉變換FFT(Fast Fourier Transform)、Viterbi算法等，都具有大量的跨步訪存行為，提高跨步訪存的帶寬，對于改善其系統(tǒng)的整體性能有著重要的意義。提高跨步訪存帶寬的關鍵在于如何解決體沖突問題[1]。素數(shù)存儲系統(tǒng)是解決訪問沖突，有效利用多體存儲系統(tǒng)的帶寬、提高存儲系統(tǒng)效率的一類重要方法[2]。但是，在嵌入式系統(tǒng)中，由于受片外結(jié)構(gòu)的尺寸限制，可使用的存儲模塊(Memory Module)數(shù)目較少，如果以存儲模塊為單位直接構(gòu)造素數(shù)存儲系統(tǒng)，并不能顯著改善跨步訪存的性能。

使用主存訪問調(diào)度策略，能在不增加數(shù)據(jù)總線寬度的前提下，有效提高存儲模塊中存儲體(Bank)的并行度[3～5]。基于主存訪問調(diào)度策略，本文提出了支持跨步訪問的嵌入式存儲系統(tǒng)。該系統(tǒng)是一種兩層結(jié)構(gòu)的多素數(shù)存儲系統(tǒng)，可以用較少數(shù)量的存儲模塊實現(xiàn)，而且從邏輯地址到物理地址的映像計算簡單，能顯著提高嵌入式系統(tǒng)的跨步訪存性能。

第2節(jié)將簡單介紹現(xiàn)代DRAM體系結(jié)構(gòu)和主存訪問調(diào)度策略；第3節(jié)將對本文提出的嵌入式存儲系統(tǒng)進行形式化描述，并對從邏輯地址到物理地址的映像公式的正確性進行證明；第4節(jié)給出系統(tǒng)的硬件體系結(jié)構(gòu)；第5節(jié)給出實驗和結(jié)果，并證實跨步訪存性能顯著提高；第6節(jié)為結(jié)束語。

2 DRAM體系結(jié)構(gòu)和主存訪問調(diào)度策略

現(xiàn)代DRAM存儲芯片，如DDR3 SDRAM和DDR4 SDRAM，其內(nèi)部都是由多個存儲體組成，每個存儲體內(nèi)的存儲單元以行(Row)、列(Column)二維結(jié)構(gòu)的形式排列[6, 7]。這樣，DRAM存儲芯片具有三維結(jié)構(gòu)特征：存儲體、行、列，如圖1所示。

Figure 1 DRAM architecture圖1 DRAM體系結(jié)構(gòu)

每個芯片中包含若干個存儲體，其數(shù)量一般為2的完全方次。

一般地，對不同存儲體的訪問操作相互獨立。當首次訪問存儲體內(nèi)某一行中的數(shù)據(jù)時，需要對該行進行激活(Activate)操作，即通過敏感放大器(Sense Amplifier)將整個數(shù)據(jù)行讀出，并儲存到行緩沖區(qū)(Row Buffer)中。行緩沖區(qū)相當于一個Cache，能夠減小連續(xù)訪問的延遲。行緩沖區(qū)中的數(shù)據(jù)稱為活動行(Active Row)，可以通過列訪問(Column Accesses)對其進行讀或?qū)?。當訪問另一數(shù)據(jù)行時，需要使用預充電操作(Precharge) 關閉當前的活動行，將行緩沖區(qū)中的數(shù)據(jù)寫回存儲體內(nèi)的存儲單元。預充電操作為下一次行激活操作做好準備。

例如，4 Gb容量的Micron MT41J512M8RA-125芯片[8]是一個典型的DDR3 SDRAM，內(nèi)部包括8個存儲體，每個存儲體由65 536個數(shù)據(jù)行和1 024個數(shù)據(jù)列組成。該芯片的工作頻率為800 MHz，預充電延遲為11個時鐘周期(13.75 ns) ，行激活延遲為11個時鐘周期(13.75 ns)。如果對該芯片中的活動行的列訪問是連續(xù)的，那么每個時鐘周期能完成16 bit的數(shù)據(jù)傳輸，這樣該芯片的峰值傳輸速率可達1 600MB/s。但是，在一般情況下該峰值傳輸速率難以達到。首先，這是因為在某個存儲體進行預充電或者行激活操作期間，不能對該存儲體進行訪問；第二，在列訪問的讀寫操作之間進行切換的時候，數(shù)據(jù)引腳需要一個周期的高阻抗狀態(tài)；第三，所有存儲體共享一套地址線資源和一套數(shù)據(jù)線資源。這樣，在各個主存訪問的操作之間，存在著若干時間約束和資源約束關系，這在一定程度上使訪存帶寬受到了限制。

雖然指向DRAM芯片中同一個存儲體的主存訪問只能順序處理，但是指向不同存儲體的主存訪問可以在一定約束條件下并行處理[3]。這樣，就可以為主存控制器構(gòu)建一個與DRAM時間和資源約束相一致的主存訪問調(diào)度策略，以充分挖掘在某一時刻可并行的存儲體數(shù)量，從而最大限度地提高主存系統(tǒng)帶寬。

主存訪問調(diào)度策略有多種實現(xiàn)方案[3～5]。其中，文獻[3]首次提出使用主存訪問調(diào)度策略提高主存控制器的性能。文獻[4]則提出一種針對異構(gòu)多核片上系統(tǒng)的訪存調(diào)度結(jié)構(gòu)。而文獻[5]給出了一種用于單核處理器的主存訪問調(diào)度技術方案，當主存訪問沒有數(shù)據(jù)一致性問題的時候，該方案可以在滿足同步DRAM資源約束的前提下使各個體盡可能并行執(zhí)行操作；同時，由于該方案以訪問為基本單位面向不同DRAM芯片中的不同體，其硬件實現(xiàn)的復雜程度較文獻[3,4]的方案更低，更適合應用于嵌入式系統(tǒng)。

文獻[5]所提出的主存訪問調(diào)度方案需要N個同步DRAM體控制器和一個端口仲裁模塊。如圖2所示。

Figure 2 Implementation structure of memory access scheduling圖2 主存訪問調(diào)度實現(xiàn)結(jié)構(gòu)

圖2中，N是每個芯片中存儲體的數(shù)量。每個體控制器將處理指向與其相對應的存儲體的所有主存訪問。它采用先來先服務的策略，以保證滿足主存訪問數(shù)據(jù)一致性的要求。全部體控制器向端口仲裁模塊申請所使用的同步DRAM端口資源，仲裁端口將根據(jù)資源約束條件，允許若干個體控制器通過端口將操作命令發(fā)給相應的存儲體，從而達到并行訪問多個存儲體的目的。

3 支持跨步訪問的嵌入式存儲系統(tǒng)描述

該存儲系統(tǒng)需滿足如下的構(gòu)造要求：

構(gòu)造要求1具有p個存儲模塊，編號分別為0，1 ，… ，p-1。

構(gòu)造要求2全部p個存儲模塊中，有p-b個模塊包含n個存儲體，有b個模塊包含n+1個存儲體，令q=n×p+b，則共包含q個存儲體。

構(gòu)造要求3每個存儲體有m個字的存儲容量。

其中，p、q均為大于2的素數(shù)，n≤2k，0

系統(tǒng)中任一個字的物理地址可用一個三維向量(u,v,w)來表示，其中，0≤u≤p-1，0≤v≤n，0≤w≤m-1，特別地，當0≤u≤b-1時，有0≤v≤n，當b≤u≤p-1時，有0≤v≤n-1。其中，u表示所在存儲模塊的編號，v表示所在存儲模塊內(nèi)部體的編號，w表示存儲體中的內(nèi)部地址。一個字的邏輯地址用d表示，其中，0≤d≤q×m-1。

3.1 地址轉(zhuǎn)換公式及正確性證明

在該存儲系統(tǒng)中，從邏輯地址到物理地址的轉(zhuǎn)換公式為：

(1)u=(dmodq) modp;

(2)v=(dmodq) mod 2k;

(3)w=dmodm。

可以證明，存儲系統(tǒng)中的邏輯地址和物理地址滿足以下兩個條件：

(1)每一個邏輯地址d，d∈N,對應于一個且僅對應于一個物理地址(u,v,w), (u,v,w)∈Ω。

(2)每一個物理地址(u,v,w)對應于一個且僅對應于一個邏輯地址d，同樣，d∈N且(u,v,w)∈Ω。其中，N為自然數(shù)的集合，Ω為三維向量的集合。

證明(1) 由轉(zhuǎn)換公式可知，對于任一邏輯地址d，若存在一個有效物理地址與其對應，則該物理地址必定是唯一的。因此，只需證明，對于任一邏輯地址d，都存在一個有效物理地址與其對應，其中，0≤d≤q×m-1。

由u=(dmodq) modp可知，0≤u≤p-1，符合系統(tǒng)的構(gòu)造要求1。

由w=dmodm可知，0≤w≤m-1，符合系統(tǒng)的構(gòu)造要求3。

以下，證明若v=(dmodq) mod 2k，則有0≤v≤n。按照u的取值范圍，可分為兩種情況進行證明：當0≤u≤b-1時，有0≤v≤n；當b≤u≤p-1時，有0≤v≤n-1。

設任意一個邏輯地址d，令x=dmodq。因為，u=xmodp，所以，可記x=k1×p+u。因為對于所有的x的取值，需要滿足條件0≤x

當u的取值范圍為u∈[0,b-1]時，即u的最小取值為0，-k1×p需要小于u的最小取值，且(n-k1)×p+b需要大于u的最大取值b-1，因此推得0≤k1≤n。因此，對于任意確定的u，符合約束條件x的值有n+1個。由此，xmod 2k的值域中的元素數(shù)量不多于n+1，即當0≤u≤b-1時，有0≤v≤n，這符合構(gòu)造要求2。

當u的取值范圍為u∈[b,p-1]時，即u的最小取值為b，-k1×p需要小于u的最小取值，且(n-k1)×p+b需要大于u的最大取值p-1，因此推得0≤k1≤n-1。因此，對于任意確定的u，符合約束條件x的值有n個。由此，xmod 2k的值域中的元素數(shù)量不多于n，即當b≤u≤p-1時，有0≤v≤n-1，符合構(gòu)造要求2。

由此，若v=(dmodq) mod 2k，則有0≤v≤n。

綜上所述，每一個邏輯地址d，d∈N,對應于一個且僅對應于一個物理地址(u,v,w), (u,v,w)∈Ω。

(2)首先給出孫子定理的描述如下：

孫子定理[9]：給定兩組整數(shù){ai|i=1, 2,…,k}和{bi|i=1, 2,…,k}，它們滿足如下條件：{a1,a2, …,ak}中的整數(shù)兩兩互素，且對于1≤i≤k，有bi=xmodai，此處x是一取值為整數(shù)的變量。在滿足上述條件下，x有且僅有一個解。

以下，證明每一個物理地址(u,v,w)對應于一個且僅對應于一個邏輯地址d：

令d′=dmodq,u=d′ modp,v=d′ mod 2k。

由于p是一個素數(shù)，因此p和2k互素，根據(jù)孫子定理，每一對(u,v)對應于一個且僅對應于一個d′。

再考慮d′=dmodq和w=dmodm，因為q是一個素數(shù)，m是2的冪，因此q和m互素，根據(jù)孫子定理，每一對(d′,w)對應于一個且僅對應于一個d。

綜上所述，每一個物理地址(u,v,w)對應于一個且僅對應于一個邏輯地址d。

□

以上證明了地址轉(zhuǎn)換公式的正確性，即該存儲系統(tǒng)中，該地址轉(zhuǎn)換公式能夠保證物理地址和邏輯地址一一對應。

3.2 地址轉(zhuǎn)換公式的有效性

該存儲系統(tǒng)中，w的計算方法為w=dmodm，因為m是2的冪，所以w即為其二進制表示的最右log2m位。這樣，w不需要復雜的計算。

同理，v的計算過程中第二步不需要復雜的計算，只需要在第一步計算中進行模p運算。根據(jù)參考文獻[2]，當p為2k+1或2k-1形式的素數(shù)時，模p運算可以用并行循環(huán)加法器實現(xiàn)，計算復雜度可以接受。

u的計算方法為u=(dmodq) modp，根據(jù)參考文獻[2]，當p和q均為2k+1或2k-1形式的素數(shù)時，模運算可以用并行循環(huán)加法器實現(xiàn)，計算復雜度可以接受。

因此，地址轉(zhuǎn)換公式可以使用硬件有效實現(xiàn)。

4 存儲系統(tǒng)的體系結(jié)構(gòu)

本文提出的嵌入式存儲系統(tǒng)由以下幾部分組成：存儲訪問懸掛緩沖模塊、地址轉(zhuǎn)換模塊、存儲芯片控制器模塊、存儲芯片，如圖3所示。其中，存儲訪問懸掛緩沖模塊用于緩存外界的訪問請求；地址轉(zhuǎn)換模塊負責從邏輯地址到物理地址的映像計算；整個系統(tǒng)中總共包括p個存儲芯片控制器模塊，其作用是，對外界的訪問請求進行譯碼，翻譯成相應的操作序列，并根據(jù)存儲芯片固有的時間約束和資源約束條件，將操作序列發(fā)射給存儲芯片。

Figure 3 Memory system architecture圖3 存儲系統(tǒng)的體系結(jié)構(gòu)

每個存儲芯片控制器模塊都具有一個自動刷新控制模塊、若干個存儲體控制器模塊以及一個仲裁模塊，如圖4所示。

自動刷新模塊每隔固定的周期向存儲芯片發(fā)送刷新(Refresh)操作命令，以保持存儲芯片內(nèi)的信息。整個存儲系統(tǒng)一共有q個存儲體控制器模塊，它的作用是根據(jù)外界的訪問請求生成操作序列，并根據(jù)DRAM芯片的時間約束和資源約束條件向仲裁模塊發(fā)出仲裁請求。由仲裁模塊從多個仲裁請求中選擇一個操作，發(fā)給存儲芯片。

Figure 4 Memory device controller圖4 存儲芯片控制器

5 實驗

本文使用SystemC2.2硬件描述語言在RTL級實現(xiàn)了該存儲系統(tǒng)。其中，存儲芯片模塊根據(jù)Micron公司MT41J512M8RA-125芯片的Verilog行為模型開發(fā)，兩者外部特征完全一致，因此實驗得到的數(shù)據(jù)可以真實地反映設計的實際效果。

實驗所實現(xiàn)的支持跨步的嵌入式存儲系統(tǒng)共包括3個存儲模塊、17個存儲體控制器。每個存儲模塊使用一個MT41J512M8RA-125芯片，每個MT41J512M8RA-125芯片中包含8個存儲體，所以整個存儲系統(tǒng)中共有24個存儲體。由于所實現(xiàn)的存儲系統(tǒng)中只使用了17個存儲體控制器，因此有7個存儲體空閑，為避免空間浪費，可用于存儲那些不需要跨步訪問的數(shù)據(jù)和代碼。

實驗的對比方案也采用3個存儲模塊交叉編址的方式構(gòu)建，但與本文所提方案的不同之處在于存儲模塊內(nèi)部采用順序編址方式。

實驗中的訪存測試數(shù)據(jù)量為32KB，數(shù)據(jù)總線位寬為24bits，分別對上述兩存儲系統(tǒng)中隨機訪存、跨步訪存(跨步為1、2、4、8、16、32)等情況進行測試。表1給出了實驗結(jié)果。

從實驗結(jié)果中可以看出，系統(tǒng)的跨步訪存性能得到了顯著改善。

6 結(jié)束語

本文提出并實現(xiàn)了一種可支持跨步訪問的嵌入式存儲系統(tǒng)。該系統(tǒng)以素數(shù)存儲系統(tǒng)為基礎構(gòu)建，避免了跨步訪問所引起的體沖突問題；同時，通過對主存訪問進行有效調(diào)度，提高存儲模塊中存儲體的并行度，降低系統(tǒng)的實現(xiàn)規(guī)模，滿足嵌入式系統(tǒng)的要求。

Table 1 Experimental results表1 實驗結(jié)果 μs

實驗結(jié)果表明，本文的方法能顯著提高嵌入式系統(tǒng)的跨步訪存性能。

[1] Aho E, Vanne J, Hamalainen T. Parallel memory architecture for arbitrary stride accesses[C]∥Proc of the 9th IEEE Workshop on Design and Diagnostics of Electronic Circuits and Systems, 2006:63-68.

[2] Gao Q S. The Chinese remainder theorem and the prime memory system[C]∥Proc of the 20th Annual International Symposium on Computer Architecture, 1993:337-340.

[3] Rixner S,Dally W J,Kapasi U J,et al. Memory access scheduling[C]∥Proc of the 27th International Symposium on Computer Architecture, 2000:128-138.

[4] Ausavarungnirun R, Chang K K W, Subramanian L, et al. Staged memory scheduling:Achieving high performance and scalability in heterogeneous systems[C]∥Proc of the 39th International Symposium on Computer Architecture, 2012:416-427.

[5] Bai Feng, Cheng Xu. The design of main memory controller for high bandwidth based on memory disambiguation, memory reference scheduling and address remapping[J]. Computer Engineering and Applications, 2003,39(26):125-128.(in Chinese)

[6] JEDEC Solid State Technology Association.JESD79-3E,DD-R3 SDRAM specification[S]. Arlington(VA, USA):JEDEC Solid State Technology Association, 2010.

[7] JEDEC Solid State Technology Association.JESD79-4,DDR4 SDRAM specification[S]. Arlington(VA, USA):JEDEC Solid State Technology Association, 2012.

[8] Micron DDR3 SDRAM MT41J512M8RA-125 Datasheet [EB /OL]. [2010-06-06].http://www.micron.com/～/media/Documents/Products/Data%20Sheet/DRAM/4Gb_DDR3_SDRAM.pdf.

[9] Pan Cheng-dong, Pan Cheng-biao. Elementary number theory[M]. 2nd Ed. Beijing:Peking University Press, 2003. (in Chinese)

附中文參考文獻：

[5] 白鋒, 程旭. 基于主存訪問相關解決等技術的高帶寬主存控

制器設計[J]. 計算機工程與應用, 2003,39(26):125-128.

[9] 潘承洞, 潘承彪. 初等數(shù)論[M]. 第2版. 北京:北京大學出版社, 2003.

LüHui,born in 1978,PhD candidate,assistant researcher,his research interests include high performance computing, and many-core processor architecture.

丁亞軍(1967-),男,浙江衢州人，碩士，高級工程師，研究方向為高性能計算和眾核處理器體系結(jié)構(gòu)。E-mail:dyjdoc@163.com

DINGYa-jun,born in 1967,MS,senior engineer,his research interests include high performance computing, and many-core processor architecture.

鄭方(1984-),男,陜西咸陽人，博士生，助理研究員，CCF會員(E200030852M)，研究方向為高性能計算和眾核處理器體系結(jié)構(gòu)。E-mail:zhengfangwww_2000@163.com

ZHENGFang,born in 1984,PhD candidate,assistant researcher,CCF member(E200030852M)，his research interests include high performance computing, and many-core processor architecture.

吳東(1971-),男,江蘇蘇州人，博士后,副研究員，研究方向為高性能計算與可重構(gòu)計算體系結(jié)構(gòu)。E-mail:wu.dong@meac-skl.cn

WUDong,born in 1971,post doctor,associate research fellow,his research interests include high performance computing, reconfigurable computing architecture.

Anovelembeddedmemorysystemforstrideaccesses

Lü Hui1，DING Ya-jun2，ZHENG Fang1，WU Dong1，XIE Xiang-hui1

(1.State Key Laboratory of Mathematical Engineering and Advanced Computing,Wuxi 214125;2.Jiangnan Institute of Computing Technology,Wuxi 214000,China)

A novel multi-prime embedded memory system is proposed, based on the theory of prime memory system and memory access scheduling. The system can significantly improve the performance of stride memory access at low hardware cost. Theoretical analysis and the experimental results prove the correctness and effectiveness of the system.

embedded system;stride accesses;memory system;memory access scheduling

2013-04-28;

：2013-08-26

國家863計劃資助項目(2013AA010105)

1007-130X(2014)02-0211-05

TP333

：A

10.3969/j.issn.1007-130X.2014.02.004

呂暉(1978-),男,山東高密人，博士生，助理研究員，研究方向為高性能計算與眾核處理器體系結(jié)構(gòu)。E-mail:iamlyuhui@gmail.com

通信地址：214125 江蘇省無錫市濱湖區(qū)楝澤路30號山水城軟件園18號樓Address:Building 18,Shanshuicheng Software Park,30 Lianze Rd,Binhu District,Wuxi 214125,Jiangsu,P.R.China