邱東黎 施晶晶

(江南計(jì)算技術(shù)研究所 江蘇 無錫 214000)

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

邱東黎 施晶晶

(江南計(jì)算技術(shù)研究所 江蘇 無錫 214000)

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

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

0 引 言

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

1 DRAM結(jié)構(gòu)與訪存調(diào)度

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

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

圖1 現(xiàn)代DRAM結(jié)構(gòu)

2 基礎(chǔ)調(diào)度算法

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

算法1 FCFS: 請(qǐng)求優(yōu)先級(jí)

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

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

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

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

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

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

3 多核調(diào)度算法

當(dāng)存儲(chǔ)控制器進(jìn)行的訪存調(diào)度從單核調(diào)度拓展到多核調(diào)度時(shí)，由于片外存儲(chǔ)器是作為多核心的共享資源使用的，多核心訪問除了增加訪存請(qǐng)求數(shù)量外，還帶來兩個(gè)主要問題：

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

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

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

3.1 等待時(shí)間公平算法

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

算法3 STFM: 請(qǐng)求優(yōu)先級(jí)

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

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

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

STFM算法中，不公平性上限α是對(duì)整個(gè)算法影響最大的參數(shù)。若α過大，則該算法退化為FR-FCFS。若α過小，則會(huì)因?yàn)檫^于顧及公平性使系統(tǒng)其它指標(biāo)受損嚴(yán)重。

STFM算法的思路比較簡(jiǎn)明，但缺陷也比較大：

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

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

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

3.2 分批次調(diào)度算法

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

算法4 PAR-BS: 請(qǐng)求優(yōu)先級(jí)

1) 帶標(biāo)記優(yōu)先： 被標(biāo)記的請(qǐng)求優(yōu)先。

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

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

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

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

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

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

? 若某一核心在不同體內(nèi)的少量請(qǐng)求由于到達(dá)時(shí)間原因被分到了兩個(gè)批次，那PAR-BS不僅不能維護(hù)，反而會(huì)進(jìn)一步破壞其體級(jí)并行性。

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

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

算法5 ATLAS: 請(qǐng)求優(yōu)先級(jí)

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

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

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

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

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

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

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

3.4 分組調(diào)度算法

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

算法6 TCM: 請(qǐng)求優(yōu)先級(jí)

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

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

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

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

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

該算法有待改進(jìn)之處如下：

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

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

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

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

算法7 TB-LMI/ATB-LMI: 請(qǐng)求優(yōu)先級(jí)

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

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

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

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

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

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

4 算法總結(jié)

4.1 算法對(duì)比

表1 調(diào)度算法簡(jiǎn)要對(duì)比表

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

4.2 算法框架分析

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

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

(1)

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

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

(2)

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

5 結(jié) 語

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

[1] 趙鵬. 多核環(huán)境下的DRAM內(nèi)存分類調(diào)度算法[J]. 中國(guó)科技論文在線, 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。邱東黎，碩士生，主研領(lǐng)域：計(jì)算機(jī)體系結(jié)構(gòu)。施晶晶，工程師。

TP301

A

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