支持跨步訪問的嵌入式存儲系統*

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

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

支持跨步訪問的嵌入式存儲系統*

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

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

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

嵌入式系統；跨步訪問；存儲系統；主存調度訪問策略

1 引言

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

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

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

2 DRAM體系結構和主存訪問調度策略

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

Figure 1 DRAM architecture圖1 DRAM體系結構

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

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

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

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

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

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

Figure 2 Implementation structure of memory access scheduling圖2 主存訪問調度實現結構

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

3 支持跨步訪問的嵌入式存儲系統描述

該存儲系統需滿足如下的構造要求：

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

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

構造要求3每個存儲體有m個字的存儲容量。

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

系統中任一個字的物理地址可用一個三維向量(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表示所在存儲模塊內部體的編號，w表示存儲體中的內部地址。一個字的邏輯地址用d表示，其中，0≤d≤q×m-1。

3.1 地址轉換公式及正確性證明

在該存儲系統中，從邏輯地址到物理地址的轉換公式為：

(1)u=(dmodq) modp;

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

(3)w=dmodm。

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

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

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

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

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

由w=dmodm可知，0≤w≤m-1，符合系統的構造要求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的值域中的元素數量不多于n+1，即當0≤u≤b-1時，有0≤v≤n，這符合構造要求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的值域中的元素數量不多于n，即當b≤u≤p-1時，有0≤v≤n-1，符合構造要求2。

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

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

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

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

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

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

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

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

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

□

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

3.2 地址轉換公式的有效性

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

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

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

因此，地址轉換公式可以使用硬件有效實現。

4 存儲系統的體系結構

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

Figure 3 Memory system architecture圖3 存儲系統的體系結構

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

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

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

5 實驗

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

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

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

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

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

6 結束語

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

Table 1 Experimental results表1 實驗結果 μs

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

[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] 潘承洞, 潘承彪. 初等數論[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-),男,浙江衢州人，碩士，高級工程師，研究方向為高性能計算和眾核處理器體系結構。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)，研究方向為高性能計算和眾核處理器體系結構。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-),男,江蘇蘇州人，博士后,副研究員，研究方向為高性能計算與可重構計算體系結構。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-),男,山東高密人，博士生，助理研究員，研究方向為高性能計算與眾核處理器體系結構。E-mail:iamlyuhui@gmail.com

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