面向系統(tǒng)吞吐量與公平性的存控調度算法綜述

邱東黎 施晶晶

(江南計算技術研究所 江蘇 無錫 214000)

面向系統(tǒng)吞吐量與公平性的存控調度算法綜述

邱東黎 施晶晶

(江南計算技術研究所 江蘇 無錫 214000)

現(xiàn)代處理器多使用片外存儲器動態(tài)隨機存儲器DRAM(Dynamic Random Access Memory)，但受到工藝限制，對片外存儲器的存儲速度一直是制約處理器性能的瓶頸。存儲控制器作為處理器芯片與片外存儲器的接口，使用的調度算法會對訪存性能產生直接且關鍵的影響。針對現(xiàn)代DRAM的結構，以及幾種典型的面向系統(tǒng)吞吐量與公平性的存控調度算法，對這些算法各自的優(yōu)勢與劣勢作了簡要分析，提出有待改進的地方。通過對面向系統(tǒng)吞吐量與公平性的存控調度算法的設計框架作一般化分析，得出新算法的設計與優(yōu)化的方向。

Dram 存儲控制器 多核調度算法 系統(tǒng)吞吐量 公平性

0 引 言

現(xiàn)代處理器多使用片外存儲器動態(tài)隨機存儲器DRAM。而現(xiàn)代處理器的計算速度提升與訪存速度提升之間的“剪刀差”，使得片外存儲器訪問往往成為現(xiàn)代處理器性能發(fā)揮瓶頸。近十年來，為了追求更高的計算速度，處理器芯片上集成的核心數(shù)越來越多，這些核心一般共享片外存儲資源[1]。多個核對同一個片外存儲器的同時訪問還會造成競爭，降低單個核心的性能。訪存調度算法作為一種通過亂序調度訪存請求的方法，可以通過合理安排訪存隊列的調度順序，降低核心之間的競爭，是提升核心服務質量，提升存儲系統(tǒng)性能的有效途徑之一。對于多核或眾核處理器來說，其訪存系統(tǒng)有兩個重要的因素會直接影響整體性能：系統(tǒng)吞吐量與公平性。系統(tǒng)吞吐量表示系統(tǒng)總的工作量，是系統(tǒng)性能的直接體現(xiàn)。而公平性表示的是多個核訪問存儲系統(tǒng)的機會是否相等，一個公平的訪存系統(tǒng)不應當使任何一個核心訪問存儲系統(tǒng)時相比于別的核心減速過多甚至是餓死。

1 DRAM結構與訪存調度

現(xiàn)代DRAM采用由BANK(體)、ROW(行)、COLUMN(列)構成的三維地址結構[2]，如圖1所示。新型的存儲結構高帶寬存儲器HBM(High Bandwidth Memory)、混合存儲立方體HMC(Hybrid Memory Cube)也是由DRAM顆粒堆疊而成的，因此本文討論的調度算法同樣適用于這些存儲器結構。在DRAM中，一方面，對不同體的訪問可以并行進行，即該結構具有固有的并行性，開發(fā)體級并行性是隱藏訪存延遲、提高存控工作效率的重要手段。另一方面，體內部是行列的二維存儲陣列，對存儲陣列訪問時實際是對一個頁，即行緩沖(ROW BUFFER)，進行操作：當需要讀出存儲陣列中的某一行時，首先需要將整行寫入到頁中，即行激活；當需要將內容寫入存儲陣列中時，需要對頁操作完畢后整行寫回，即預充電。對頁中內容直接操作稱為列訪問，其延時遠小于行激活或者預充電。當訪存序列流具有較好數(shù)據(jù)局部性時，可以采用頁打開的策略，即只有當下一個待處理的請求所在行與頁沖突時，才執(zhí)行預充電指令，這樣對同一行中不同列連續(xù)操作時，只執(zhí)行一次行激活與預充電指令，而中間是連續(xù)的列訪問指令。頁命中時，除第一條訪存請求外，后面的請求延遲很小，可有效降低總訪存時間、提升工作效率。

存儲控制器是處理器與片外存儲器之間的接口，面向提升系統(tǒng)吞吐率、保證公平性的調度是存儲控制器的主要功能之一。存儲控制器將核心發(fā)出的讀寫請求經過一定的調度后，轉換成對存儲器器進行操作的命令。打亂請求隊列的執(zhí)行次序會改變存儲器命令的個數(shù)以及次序，影響存儲系統(tǒng)的系能，進而影響整體性能。因此對請求隊列次序的優(yōu)化是提升性能的有效途徑之一。本文研究的訪存調度算法便是通過利用現(xiàn)代DRAM的結構與訪存序列流中的數(shù)據(jù)局部性，對請求隊列進行調度，在保證多核公平性的前提下盡量縮短訪存序列流的延遲，從而提升系統(tǒng)的性能。

圖1 現(xiàn)代DRAM結構

2 基礎調度算法

處理訪存請求最為原始的方法是FCFS(First Come First Service，先到達先服務)方法，即順序執(zhí)行，其請求優(yōu)先級規(guī)則如算法1所示。該方法硬件實現(xiàn)代價最小，只需要一個FIFO(First In First Out/先入先出)隊列即可。但是這種方法的問題也十分明顯：該方法可能會破壞訪存請求的數(shù)據(jù)局部性以及體級并行性，使得片外存儲帶寬利用率極低。

算法1 FCFS: 請求優(yōu)先級

1) 老請求優(yōu)先： 年齡最大的請求優(yōu)先。

對于FCFS算法一個簡單但有效的改進是FR-FCFS(First Ready-First Come First Service，先就緒、先到達先服務)調度算法[3]，其請求優(yōu)先級規(guī)則如算法2所示。其中Ready(就緒)的含義是，訪存請求的目標存儲位置所在行已經位于頁中，并且該請求不違反任何約束條件。已經就緒的訪存請求可以立即執(zhí)行，且一定能頁命中。這種算法考慮了DRAM內部結構特征，優(yōu)先處理頁命中的請求，通過對請求序列流中數(shù)據(jù)局部性的進一步挖掘，連續(xù)處理同一主存行的請求，能夠有效縮短訪存請求時間，增大片外存儲帶寬的利用率。

算法2 FR-FCFS: 請求優(yōu)先級(由上到下優(yōu)先級遞減，下同)

1) 頁命中優(yōu)先： 行緩沖命中的請求優(yōu)先。

2) 老請求優(yōu)先： 年齡最大的請求優(yōu)先。

當多核共享片外存儲時，F(xiàn)R-FCFS會有問題：該算法不區(qū)分請求來源，會使數(shù)據(jù)局部性好的核心優(yōu)先級高于局部性差的，也使訪存密集型核心優(yōu)先級高于計算密集型。因此雖然片外帶寬利用率較高，但會造成嚴重的不公平，甚至餓死，使系統(tǒng)公平性與整體吞吐率較低。

3 多核調度算法

當存儲控制器進行的訪存調度從單核調度拓展到多核調度時，由于片外存儲器是作為多核心的共享資源使用的，多核心訪問除了增加訪存請求數(shù)量外，還帶來兩個主要問題：

? 對于單個核心來說，其他核心對片外存儲帶寬的使用會加大自己原本的訪存延遲，降低自身性能。

? 對于多個核心來說，要保證公平性，即外部沒有事先設置不同優(yōu)先級時，多個核心應當具有相同的訪存機會，不應當有任何一個核心相比于其他核心減速過大。

對某個核心來說，假設其單獨使用片外存儲器時，訪存延遲為Talone，當多核心共享片外存儲器時，訪存延遲為Tshared，則定義其減速比S=Tshared/Talone[4]。對于有n個核心的系統(tǒng)，其公平性反比于最大減速比Smax=max{Si|1≤i≤n}。由于多個核心相互干擾，有可能會降低系統(tǒng)總吞吐量或者造成不公平。下面按照其提出的時間順序介紹幾種多核調度算法。

3.1 等待時間公平算法

針對FR-FCFS的問題，Mutlu等人提出了等待時間公平訪存調度STFM(Stall-Time Fair Memory Scheduler)算法[4]。該算法設置一個公平閾值α，當最大減速比與最小減速比的比值Smax/Smin>α時，表示公平性遭到了超過設定程度的破壞，此時對調度過程進行強制調解，使具有最大減速比的核心Tmax具有最高優(yōu)先級。該算法的優(yōu)先級規(guī)則如算法3所示。

算法3 STFM: 請求優(yōu)先級

1) 不公平時Tmax優(yōu)先: 如果Smax/Smin>α，Tmax的請求優(yōu)先。

2) 頁命中優(yōu)先： 行緩沖命中的請求優(yōu)先。

3) 老請求優(yōu)先： 年齡最大的請求優(yōu)先。

STFM算法中，不公平性上限α是對整個算法影響最大的參數(shù)。若α過大，則該算法退化為FR-FCFS。若α過小，則會因為過于顧及公平性使系統(tǒng)其它指標受損嚴重。

STFM算法的思路比較簡明，但缺陷也比較大：

?Smax/Smin沒有考慮核心的相互影響，作為公平性閾值標準還有優(yōu)化空間。

? 該算法不考慮產生不公平性的原因，只當嚴重不公平現(xiàn)象產生時才處理。這種維護公平性的方法有局限性，還有優(yōu)化空間。

? 該算法沒有考慮強制加速一個核心對系統(tǒng)吞吐量的影響，因此這種維護公平性的方式可能會對系統(tǒng)吞吐量產生較大影響。

3.2 分批次調度算法

Mutlu等人提出了并行性敏感的分批次調度PAR-BS(Parallelism-Aware Batch Scheduling)算法[5]。該算法的核心思想有兩條：(1)訪存請求分批次調度；(2)維護請求的體級并行性。在程序執(zhí)行過程中，通過對請求標記的方式，被標記的請求屬于批次內，未被標記的請求在當前批次處理完畢后按規(guī)則劃分新的批次。組建新批次時，通過Marking-Cap參數(shù)限定同一核心在同一體內的最大請求數(shù)。批次內部，體內最大請求數(shù)越小的核心次序越靠前。若體內最大請求數(shù)相同，則總請求數(shù)越小的核心次序越靠前。請求數(shù)小的核心單獨訪問時的延遲小，長訪問延遲對請求數(shù)越小的核心影響越大。維護體級并行性是降低訪存延遲的有效方式，通過本算法的核心次序可以使各個體內核心執(zhí)行順序大致相同，有效維護請求數(shù)小的核心的體級并行性，并降低其延遲。其優(yōu)先級規(guī)則參見算法4。

算法4 PAR-BS: 請求優(yōu)先級

1) 帶標記優(yōu)先： 被標記的請求優(yōu)先。

2) 頁命中優(yōu)先： 行緩沖命中的請求優(yōu)先。

3) 高次序優(yōu)先： 擁有高次序的核心的請求優(yōu)先。

4) 老請求優(yōu)先： 年齡最大的請求優(yōu)先。

該算法通過分批次確定當前階段需要處理的有限個請求。Marking-Cap參數(shù)可以有效控制同一個核心對同一個體占用的時間，維護公平性。通過使各個核心在各個體內的優(yōu)先級相同，可以使訪存量越小的核心在不同體內的請求越能同時執(zhí)行，維護其體級并行性。對于行局部性很差，但是體級并行性很好的核心而言，該算法在對其他核心影響較小的前提下，有效地降低其等待時間，提升了系統(tǒng)吞吐量與公平性。

PAR-BS算法的不足在于其分批次的方式。當批次劃分完畢后，再到達的請求只能等待批次處理結束，進入下一個批次。因此，該算法有兩個導致系統(tǒng)吞吐量降低的問題:

? 某個體在請求處理完畢后需等待時間最長的體，若批次內請求集中于某個體，而其余體的請求在批次劃分完畢后才到來，會產生該體忙碌而其余體空閑的低效狀態(tài)。

? 若某一核心在不同體內的少量請求由于到達時間原因被分到了兩個批次，那PAR-BS不僅不能維護，反而會進一步破壞其體級并行性。

3.3 最少被服務優(yōu)先算法

Kim等人提出了自適應性最少被服務核心優(yōu)先訪存調度ATLAS(Adaptive per-Thread Least-Attained-Service memory scheduling)算法[6]，目的是針對多存控，使存控間不需大量協(xié)調就可獲得較大系統(tǒng)吞吐量。該算法借鑒排隊論中“最少獲得服務優(yōu)先”的思想，在不改變對片外存儲帶寬的使用情況下，減小多個核心總延遲，提高系統(tǒng)吞吐量。每經過某個設定的時長T，各存控協(xié)同統(tǒng)計每個核心在該時段內對片外存儲器的總訪問量，為各個核心設定下一個時段內的優(yōu)先級。其請求優(yōu)先級規(guī)則見算法5。

算法5 ATLAS: 請求優(yōu)先級

1) 超時優(yōu)先： 等待時間超過T的請求優(yōu)先。

2) 最少被服務優(yōu)先：最少獲得服務的核心的請求優(yōu)先。

3) 頁命中優(yōu)先： 行緩沖命中的請求優(yōu)先。

4) 老請求優(yōu)先： 年齡最大的請求優(yōu)先。

該算法與PAR-BS都蘊含著“訪存量小的核心優(yōu)先”的思想，不同的是：(1)PAR-BS分批處理，ATLAS可以處理所有請求。(2)PAR-BS根據(jù)批次內訪存量排序，ATLAS是歷史訪存量。(3)PAR-BS通過強制分批維護公平性，ATLAS只通過超時優(yōu)先防餓死。相比于PAR-BS，ATLAS算法一般情況下系統(tǒng)吞吐量上升而公平性下降。

該算法另一個目標是減少存控間協(xié)調量。多存控時，PAR-BS需要在每個新的批次建立時都協(xié)調一次，而且要確定每個核心在各個體內的最大請求數(shù)，協(xié)調量過大。ATLAS通過較長時間片，以及僅協(xié)調每個核心的總訪問量，減小協(xié)調信息量，提升可擴展性。

該算法不足在于不維護公平性。超時優(yōu)先是防餓死的有效手段，但是餓死是極端不公平現(xiàn)象，即該算法對公平性的維護程度很低。而且由于最少被服務核心優(yōu)先原則，訪存量大的核心會被始終減速，訪存量小的核心則始終加速，即該算法具有固有的不公平性。

3.4 分組調度算法

針對PAR-BS與ATLAS的問題，Kim等人提出了兼顧公平性和吞吐量的核心分組存儲調度TCM(Thread Cluster Memory Scheduling)算法[7]。該算法在其執(zhí)行過程中，將核心根據(jù)對片外存儲帶寬的使用量排序，從最小的依次累加，當達到一定閾值時，將已經累加的分為延遲敏感組(非訪存密集型)，剩下的分為帶寬敏感組(訪存密集型)。TCM算法的核心思想為：(1) 使延遲敏感組優(yōu)先于帶寬敏感組，以提升系統(tǒng)吞吐量；(2) 引入“友好度”評價標準來衡量一個核心干擾其他核心的傾向；(3) 通過“友好度”標準在帶寬敏感組中階段性地對核心優(yōu)先級進行混洗，以減少核心間干擾，保證公平性。當核心行局部性好而體級并行性差時，更容易干擾其他核心，破壞公平性。因此根據(jù)核心i在所有核心中的體級并行性次序bi與行局部性次序ri，定義其“友好度”標準Nicenessi≡bi-ri?；煜捶绞讲捎貌迦牖煜?，使具有高“友好度”核心獲得高優(yōu)先級的幾率更大。請求優(yōu)先級規(guī)則如算法6所示。

算法6 TCM: 請求優(yōu)先級

1) 分組優(yōu)先： 延遲敏感組優(yōu)先。

2) 最少被服務/混洗優(yōu)先：延遲敏感組內最少被服務優(yōu)先，帶寬敏感組內按混洗排定優(yōu)先級。

3) 頁命中優(yōu)先： 行緩沖命中的請求優(yōu)先。

4) 老請求優(yōu)先： 年齡最大的請求優(yōu)先。

訪存密度小的核心更需要低訪存延遲，快速完成訪存可以有效減少計算資源的浪費，提升系統(tǒng)吞吐量；訪存密度大的核心更需要高訪存帶寬，且更容易通過占用片外存儲帶寬與其他核心產生干擾。TCM算法考慮不同的核心的需求，希望獲得整體較優(yōu)的吞吐率和公平性。

該算法有待改進之處如下：

? 當訪存密集型核心與訪存非密集型核心的比例發(fā)生大幅度變化，例如大量核心都是訪存密集型時，該算法的分組方式會導致一定程度的固有不公平。

? 延遲敏感組中最高優(yōu)先級是最小獲得服務，但對多個訪存量小的核心，該原則的效果會降低。延遲敏感組對低延遲需求更高，因此應提高頁命中優(yōu)先級，以降低延遲。

3.5 分時段優(yōu)先級算法

Elhelw等人提出了基于時間的最小訪存密度優(yōu)先調度TB-LMI(Time-Based Least Memory Intensive scheduling)算法[8]，以及改進版本自適應基于時間的最小訪存密度優(yōu)先調度ATB-LMI(Adaptive Time-Based Least Memory Intensive scheduling)[9]。其請求優(yōu)先級規(guī)則見算法7。

算法7 TB-LMI/ATB-LMI: 請求優(yōu)先級

1) 有限次頁命中優(yōu)先： 行緩沖命中的請求優(yōu)先直到該行緩沖達到一定訪問次數(shù)。

2) 最少被服務優(yōu)先：最少獲得服務的核心的請求優(yōu)先。

3) 老請求優(yōu)先： 年齡最大的請求優(yōu)先。

從系統(tǒng)吞吐量來說，頁命中優(yōu)先本身可以降低訪存延遲。從公平性上來說，一方面，相比于公平性遭到嚴重破壞時才維護的方式，有限次數(shù)頁命中杜絕了單核心對頁的長時間占用，對公平性維護效果更好。另一方面，有限次頁命中優(yōu)先級最優(yōu)高，避免了最少被服務優(yōu)先帶來的固有不公平性。

ATB-LMI是TB-LMI的自適應性版本，其請求優(yōu)先級也如算法7所示。不同之處在于ATB-LMI統(tǒng)計訪存量的時長是變化的。在ATB-LMI中，若核心優(yōu)先級經過一個時段沒有發(fā)生變化，則將時段加長，否則減短。若在一個時段內，核心優(yōu)先級沒有變化，則表示該時段內核心的相對訪存量變化不大，核心行為相對穩(wěn)定。加大時段可以減少存控協(xié)調信息量，提升存控效率。若核心優(yōu)先級有變化，則表示至少有一個核心行為有較大變化，此時應當加大協(xié)調量，跟蹤核心行為變化，制定更合適的優(yōu)先級順序。TB-LMI與ATLAS一樣，都是通過歷史預測未來，當訪存行為變化較大時性能會降低。ATB-LMI對訪存行為變化敏感的特點能夠較為有效地彌補TB-LMI的不足。

TB-LMI與ATB-LMI的關鍵之處在于頁命中的上限次數(shù)。上限次數(shù)過高時，算法會趨近于FR-FCFS。上限次數(shù)過低時，算法會嚴重降低系統(tǒng)吞吐量。上限次數(shù)作為經驗型的固定值，需要反復試驗確定。相比于TCM算法，TB-LMI以及ATB-LMI對核心訪存行為特征的關注度相對較低，對不同特征核心訪存行為的可控程度較低，尚有可提升空間。

4 算法總結

4.1 算法對比

表1 調度算法簡要對比表

對上文涉及到的調度算法的簡要總結對比見表1所示?？梢钥闯?，所有亂序調度的算法都使用了頁命中優(yōu)先與老請求優(yōu)先的規(guī)則，這兩條是將FR-FCFS算法的規(guī)則作為亂序調度算法基礎的原因：由于DRAM的行緩沖機制，頁命中是掩蓋連續(xù)請求訪存延遲的最有效方式之一，相比于維護體級并行性也更容易實現(xiàn)。而年齡是所有請求都不相同的，因此在其他優(yōu)先級都相同時可用作調度的參考。

4.2 算法框架分析

訪存請求的調度順序與其自身的三個因素相關：來源、去向與時間，對應到調度算法中也就是：所在核心、頁命中情況與請求年齡。制定算法的過程實際上也就是對三個因素所帶來的影響進行考慮，并通過對這些因素的控制來達到預期的效果的過程。其中，關于請求年齡多使用老請求優(yōu)先(先到先服務)的原則，也可以附加考慮超時的影響；頁命中情況可以直接通過查看存儲器行緩沖狀態(tài)確定，多使用頁命中優(yōu)先的原則；所在核心雖然是請求的固有屬性，但如何合理制定核心優(yōu)先級是個難點，也是提升系統(tǒng)吞吐量與公平性的重點。假設系統(tǒng)中有k個核心，訪存請求隊列中有n個請求，則n個請求的執(zhí)行次序如公式1所示。其中x為請求在隊列中的位置，s為核心號，r為執(zhí)行次序，c為核心的優(yōu)先級，h為頁命中情況，t為年齡，f為調度算法。一般情況下，只關心當前r值最小的x，執(zhí)行該請求；t通常直接取x值，因為請求的位置就代表了其到達次序。

r(x)=f(c(s),h(x),t(x)) (0

(1)

核心優(yōu)先級與其自身的行局部性、體級并行性、訪問延遲和帶寬使用四個因素相關。前兩者是核心請求分布的自身屬性，后兩者是核心訪存的歷史情況。算法使用前兩個因素時，需要通過當前請求序列的特征制定策略；使用后兩個因素時，則是通過歷史預判未來的情況。就單個核心來說，好的行局部性與體級并行性都是降低訪存延遲、提升訪存效率的有效方式。但是考慮到多核心共享存儲時，如果某個核心行局部性很好，但是體級并行性差，則會長期占用某一個體，可能會破壞公平性，以及其他核心的體級并行性，降低系統(tǒng)吞吐量。因此，通常體級并行性好核心優(yōu)先級高，行局部性好的核心優(yōu)先級低。訪問延遲與帶寬使用是訪存的兩個基本性能指標，帶寬使用量小的核心往往更需要低的延遲，帶寬使用量大的核心往往更需要高的帶寬，而帶寬使用量小的核心對于提升系統(tǒng)吞吐量作用更明顯[6-7]。因此，一方面需要關注核心的訪存延遲，防止減速過大乃至餓死；另一方面需要提高帶寬使用量小的核心的優(yōu)先級，以此提升系統(tǒng)吞吐量。綜上所述，核心的優(yōu)先級如公式2所示。其中，c即是式(1)中的核心優(yōu)先級，r表示行局部性，b表示體級并行性，l表示延遲，w表示帶寬使用量，g為核心優(yōu)先級規(guī)則。一般情況下，四個自變量不會同時使用，可根據(jù)算法的目標與思路選取特定的特征進行評價即可。

c(s)=g(r(s),b(s),l(s),w(s)) (0

(2)

通過上述分析，面向系統(tǒng)吞吐量與公平性的訪存調度算法有兩個主要部分：(1)確定核心優(yōu)先級；(2)確定訪存請求調度順序。兩部分的各個因素以及相應的調度方法如上所述，但是其具體方法、參數(shù)以及相互次序需要試驗具體確定，以取得最好效果。

5 結 語

在多核、眾核時代，由于“存儲墻”問題對系統(tǒng)性能的限制，以及核心競爭對公平性、系統(tǒng)吞吐量帶來的嚴峻挑戰(zhàn)，存儲控制器的訪存調度技術成為影響現(xiàn)代處理器性能的關鍵技術之一。本文研究了現(xiàn)有的面向系統(tǒng)吞吐量與公平性的訪存調度算法，并對這些算法進行了分析，抽象出了存儲調度算法的設計框架，為對新算法的設計以及優(yōu)化提供了參考建議。由于現(xiàn)代處理器中存儲系統(tǒng)性能問題依然嚴峻，如何進一步提升訪存調度算法的效率，并且在一些本文涉及的算法中未重點提及的方面，諸如能耗、硬件復雜度等方面，進一步提高調度算法的可用性，依然是研究者應當認真研究的課題。

[1] 趙鵬. 多核環(huán)境下的DRAM內存分類調度算法[J]. 中國科技論文在線, 2011, 6(1): 6-9.

[2] Davis B T. Modern DRAM architectures[D]. Dearborn, MI, USA: University of Michigan, 2001.

[3] Rixner S, Dally W J, Kapasi U J, et al. Memory access scheduling[N]. ACM SIGARCH Computer Architecture News, 2000, 28(2):128-138.

[4] Mutlu O, Moscibroda T. Stall-time fair memory access scheduling for chip multiprocessors[C]//Proceedings of the 40thAnnual IEEE/ACM International Symposium on Microarchitecture. IEEE Computer Society, 2007: 146-160.

[5] Mutlu O, Moscibroda T. Parallelism-aware batch scheduling: enhancing both performance and fairness of shared DRAM systems[N]. ACM SIGARCH Computer Architecture News, 2008, 36(3): 63-74.

[6] Kim Y, Han D, Mutlu O, et al. ATLAS: a scalable and high-performance scheduling algorithm for multiple memory controllers[C]//High Performance Computer Architecture (HPCA), 2010 IEEE 16thInternational Symposium on. IEEE, 2010: 1-12.

[7] Kim Y, Papamichael M, Mutlu O, et al. Thread cluster memory scheduling: exploiting differences in memory access behavior[C]//Microarchitecture (MICRO), 2010 43rd Annual IEEE/ACM International Symposium on. IEEE, 2010: 65-76.

[8] Elhelw A S, El-Moursy A, Fahmy H A H. Time-based least memory intensive scheduling[C]//Embedded Multicore/Manycore Systems-on-Chip (MCSoc), 2014 IEEE 8th International Symposium on. IEEE, 2014: 311-318.

[9] Elhelw A S, El-Moursy A, Fahmy H A H. Adaptive time-based least memory intensive scheduling[C]//Embedded Multicore/Manycore Systems-on-Chip (MCSoC), 2015 IEEE 9thInternational Symposium on. IEEE, 2015:167-174.

SUMMARIZE OF STORAGE CONTROLLER SCHEDULING ALGORITHM FOR THROUGHPUT AND FAIRNESS

Qiu Dongli Shi Jingjing

(JiangnanInstituteofComputerTechnology,Wuxi214000,Jiangsu,China)

Modern processors use off-chip memory DRAM, but by the process limitations, off-chip memory storage speed has been the bottleneck of processor performance constraints. As the interface between the processor chip and its off-chip memory, the storage controller uses the scheduling algorithm to have a direct and critical impact on the access performance. Aiming at the structure of modern DRAM and several typical storage controller scheduling algorithms for system throughput and fairness, the advantages and disadvantages of these algorithms are briefly analyzed, and some improvements are proposed. Through the general analysis of the design framework of the storage controller scheduling algorithm for the throughput and fairness of the system, the direction of the design and optimization of the new algorithm is obtained.

DRAM Storage controller Multi-core scheduling algorithm System throughput Fairness

2016-04-25。邱東黎，碩士生，主研領域：計算機體系結構。施晶晶，工程師。

TP301

A

10.3969/j.issn.1000-386x.2017.05.047