王靜，陳嵐，張賀，王海永

(1 中國科學院微電子研究所 三維及納米集成電路設計自動化技術北京市重點實驗室，北京 100029；2 中國科學院大學，北京 100049) (2019年12月12日收稿； 2020年1月21日收修改稿)

隨著集成電路的發(fā)展進入到納米級，電子設計自動化(electronic design automation, EDA)工具對CPU和內存等資源的要求越來越高。傳統(tǒng)的單機平臺已不能滿足EDA仿真任務的高復雜性、高密度計算需求[1]。機器學習和大數(shù)據(jù)的發(fā)展也促進開發(fā)人員研究EDA工具并行仿真算法及架構[2-4]，減少集成電路設計周期，改善用戶體驗。需要考慮將EDA并行仿真任務放在高性能集群上，借用集群上的資源快速完成仿真。因此，本文研究適用于EDA并行仿真任務的LDRF(dominant resource fairness allocation algorithm considering license)調度算法。

單一資源調度已研究成熟，比如max-min fairness，核心思想是在多用戶的前提下，最大化每個用戶的最小資源需求，已經(jīng)在很多工程中得到應用，比如網(wǎng)絡隊列中的round-robin算法。而EDA仿真任務對資源需求具有多樣性，可分為CPU密集型、內存密集型及IO密集型等，考慮多種資源公平分配時，占優(yōu)資源公平分配(dominant resource fairness, DRF)[5]是基于“主導份額”的max-min fairness公平調度算法，已經(jīng)得到很多研究及改進。如文獻[6]提出異構環(huán)境下的占優(yōu)資源公平分配(DRF in heterogeneous cloud，DRFH)算法，將DRF運用于異構云系統(tǒng)；文獻[7]提出用戶任務對資源的需求隨時間變化的算法；文獻[8]在DRF思想基礎上提出動態(tài)情況下的分配算法即動態(tài)占優(yōu)資源公平分配機制(dynamic dominant resource fairness mechanism, DDRF)。

綜上所述，多資源調度的研究已經(jīng)取得一定進展[9-13]。由于EDA任務必須獲得license授權才能執(zhí)行，而license比較昂貴且數(shù)量有限，如全流程IC設計所包含的全套EDA工具license一年需要花費上千萬元，針對EDA并行仿真任務，需要將多資源調度和license調度結合，避免任務獲得所需的計算資源、存儲資源等，但卻因未獲得license授權不能運行，導致資源浪費。常用的調度算法沒有考慮license調度，僅適用于map-reduce等計算任務。因此，本文提出將license調度和多資源調度結合的基于EDA并行仿真任務的LDRF調度算法。

1 主流公平調度算法

1.1 DRF調度算法

DRF的核心思想是根據(jù)每個計算任務的資源需求向量和系統(tǒng)總資源向量，得到各個計算任務的主導份額。通過平衡各個計算任務的主導份額，可以確定每個計算任務的子任務數(shù)及最終分配的資源向量。文獻[5]已證明DRF具有4個性質：

1)共享性：不同用戶的任務是通過共享資源而不是獨占資源的形式來提高資源利用率，每個用戶都能均衡占用資源。2)真實性：系統(tǒng)中任何謊報資源的用戶將不會得到更多的資源。3)非搶占性[14]：任何任務都不能在獲得計算資源后，通過已有的資源，去獲得(或交換)另一個任務的資源。4)帕累托效率性[15]：集群中的所有計算任務都不能夠在不減少其他任務資源擁有量的前提下增加自己的資源擁有量。文獻[16-17]證明滿足這4個性質的調度算法具有公平性。該算法的描述如下：

假設系統(tǒng)存在2種資源r1和r2,如CPU、內存。資源總量為R1和R2,系統(tǒng)存在2個用戶i和j,資源需求向量分別為Di=(di,r1,di,r2),Dj=(dj,r1,dj,r2)。如果滿足di,r1/R1>di,r2/R2,dj,r1/R1

(1)

由公式(1)可知，用戶最終分配的子任務數(shù)由占優(yōu)資源決定。

1.2 license管理及調度

常見的EDA工具license[18]大部分基于浮動license進行授權管理，即license不與節(jié)點綁定，用戶只要獲得license授權便可在任意節(jié)點使用。調度系統(tǒng)通過心跳反應與license管理工具交互，確保即將分配資源的任務必須獲得license授權。

license常用調度算法為：先來先服務算法，將任務按照到達時間放入隊列，如果先提交的任務license不能滿足則考慮后面任務；公平分配算法，對于需要相同license的任務平均分配license，如果存在任務license分配超額則可暫時分給別的任務；輪轉調度算法，如果幾個用戶的任務同時需要一種或者幾種license，且license有限，為減少用戶等待時間，可通過時間片輪詢將任務掛起，并將licesne分給別的任務。

2 LDRF算法

LDRF算法使用DRF最大化最小占優(yōu)資源的思想并加以改進，將多資源調度和license調度結合。DRF算法假設用戶分配的子任務數(shù)量是無限的，而幾個任務消耗集群所有資源是不符合實際要求的。EDA并行任務數(shù)是根據(jù)任務種類、規(guī)模及客戶需求等確定的，并且當并行任務數(shù)增加到一定程度時加速比會下降，因此用戶分配的任務數(shù)應該有約束。

由于EDA工具的license分配以核為單位，比如Cadence公司的EDA軟件Calibre DRC、LVS、XRC及DFM等都以CPU核數(shù)為單位分配所需license數(shù)，其license數(shù)目及CPU核數(shù)的節(jié)省比例為1個license支持1核CPU，2個license支持4核CPU，3個license支持8核CPU等。因此，LDRF算法計算資源將以CPU核數(shù)為單位，而不是DRF中的以CPU數(shù)量為單位。其次，真實環(huán)境中，可能存在緊急任務，因此需要根據(jù)重要程度給每個用戶添加權重，確保調度的公平性。LDRF算法具體闡述如下：

集群資源種類數(shù)為m,包括CPU核數(shù)、內存、磁盤及IO等，用戶數(shù)為n,license資源種類數(shù)為s。集群中可分配的資源向量為r=(r1,r2，…，rm),可分配的license向量為L=(L1,L2,…,Ls)。用戶i一個子任務的資源需求向量為di=(di1,di2,…,dim),dij表示用戶i對資源j的需求量。用戶i一個子任務的license需求向量為li=(li1,li2,…,lis)。用戶i已經(jīng)分配的子任務數(shù)為xi，初始值為0。用戶i的權重為wi，最多可分配的任務數(shù)為mi。則考慮權重時，用戶i的占優(yōu)資源份額定義為

(2)

滿足下列約束：

(3)

實際資源分配并不是直接根據(jù)式(2)、式(3)計算最優(yōu)結果，每個用戶的占優(yōu)資源份額不是絕對相等，而是在獲得license授權的條件下趨于平衡。其次，任務執(zhí)行完成后會釋放資源，空閑資源發(fā)生變化，因此實際中是以式(3)為約束條件，通過循環(huán)方式分配給任務資源。每次循環(huán)選擇一個任務分配資源，不存在其他任務競爭。因此，license調度使用的是FIFO(first input first output)算法。因為調度過程中優(yōu)先級是根據(jù)占優(yōu)資源份額來確定的，初始份額均為0，當計算資源充足的情況下，初始任務隨機選擇不影響結果。但是當計算資源有限時，為更加公平地調度，任務應該有初始優(yōu)先級pi0，與任務大小成反比，與用戶權重成正比，如下所示：

(4)

LDRF算法的步驟如算法1所示。

算法1 LDRF算法r=(r1,r2,…,rm) 集群總的資源向量L=(L1,L2,…,Ls) 集群總的license向量c=(c1,c2,…,cm) 集群已經(jīng)使用的資源di=(di1,di2,…,dim)用戶i一個子任務所需資源向量li=(li1,li2,…,lis) 用戶i一個子任務所需license向量xi 用戶i已分配的任務數(shù)mi用戶i最多分配的任務數(shù)wi用戶i的權重步驟:1. 根據(jù)公式(4)計算每個用戶i的初始優(yōu)先級pi0,從大到小 排序并存入隊列P;2. for pi in P∥依次選擇初始優(yōu)先級高的用戶i;3. while rj-dij>cj,j=1,2,…,m4. cj+=dij,j=1,2,…,m;xi++5. end while6. end for7. while rj-cj>0,j=1,2,…,m8. 根據(jù)公式計算(2)計算每個用戶的占優(yōu)資源μi并排序;9. 選擇μi最小的用戶i;10. if rj-cj>dij,j=1,2,…,m and lik

3 LDRF性能分析

3.1 資源利用率分析

1) LDRF和DRF資源利用率比較

LDRF以license資源調度為前提，如果任務缺乏license則不分配計算資源，這部分資源可分配給別的任務，保證資源充分利用。而DRF沒有考慮license調度，調度系統(tǒng)可能給任務分配資源但缺乏license授權，任務已分配充足的資源卻不能執(zhí)行，導致資源利用率下降。

圖1為不同用戶數(shù)條件下，多次隨機產(chǎn)生每個用戶所需資源向量及集群總資源向量時，2種算法CPU資源、內存資源平均占用情況直觀比較圖。其中圖1(a)、1(c)為license數(shù)量有限的情況，圖1(b)、1(d)為license數(shù)量比較充足的情況。由此可知，license有限的條件下，LDRF資源利用率明顯高于DRF資源利用率，CPU核數(shù)平均資源利用率增長60%，內存平均資源利用率增長34%。license比較充足時，CPU核數(shù)平均資源利用率增長28%，內存平均資源利用率增長10%。

圖1 DRF、LDRF算法資源利用率Fig.1 DRF and LDRF algorithm resource utilization

2) LDRF、FIFO、CPU fair算法比較

常用資源調度算法有FIFO和max-min fairness調度算法。FIFO即先到達任務先得資源，依次執(zhí)行，其他任務只能處于等待狀態(tài)。max-min fairness調度算法即最大化每個任務所需最小資源。由于max-min fairness只針對單一資源調度，因此在多資源仿真中以CPU為標準即CPU fair。另外在此基礎上，將2種算法添加license調度以適用于EDA仿真任務。圖2是在不同用戶數(shù)條件下，多次隨機產(chǎn)生所需輸入資源向量及總的空閑資源向量，3種算法平均資源利用率的比較圖。由圖可知，LDRF算法的CPU資源利用率及內存資源利用率明顯優(yōu)于其他算法。

圖2 FIFO、CPU fair和LDRF算法資源利用率Fig.2 FIFO, CPU fair, and LDRF algorithm resource utilization

3) 實測數(shù)據(jù)性能分析

前述分析已經(jīng)展示出LDRF算法資源利用率最高。為使性能對比更具說服力，將2個用戶的并行DFM分析 EDA仿真任務在高性能集群上測試。集群上有8個節(jié)點，每個節(jié)點24個CPU核。圖3為使用LDRF算法和FIFO調度算法時，執(zhí)行任務所對應的平均資源占用情況對比圖。

由圖3可知，使用LDRF算法時，CPU資源利用率及內存資源利用率均最優(yōu)。其次，使用LDRF算法時2個用戶執(zhí)行完任務所需時間約為650 s，使用FIFO算法時任務執(zhí)行時間約為800 s，執(zhí)行效率提升23%。

圖3 FIFO、LDRF實測數(shù)據(jù)資源利用率Fig.3 FIFO and LDRF measured data resource utilization

3.2 公平性分析

LDRF算法借鑒DRF算法最大化最小占優(yōu)資源的思想并加以改進，滿足共享性等4個衡量公平性的指標。從算法過程來看，多重優(yōu)先級的設定如初始優(yōu)先級和占優(yōu)資源份額，以及多輪分配資源的方法保證了每個用戶都能得到資源，滿足共享性。如果用戶謊報資源超額得到分配，下一輪分配會減少用戶資源的分配，最終滿足主導資源均衡性要求，并且由于資源按需計價收費，謊報資源需求會增加花費，滿足真實性及非搶占性。從算法整體來講，每個用戶均共享資源池中的資源，增加一個用戶分配的資源時，必然會減少其他用戶分配的資源，滿足帕累托效率性。其次，LDRF是以license調度為前提的多資源調度算法，可以防止用戶的任務占據(jù)硬件資源但缺乏license無法執(zhí)行，保證了用戶公平性。因此，LDRF算法可以保證公平性資源分配。

4 總結

考慮到EDA工具license昂貴且稀缺、EDA并行任務的子任務數(shù)有限制、每個用戶的權重不同、初始優(yōu)先級以及不同EDA仿真任務可能有不同的占優(yōu)資源，本文研究適用于EDA并行仿真任務的多資源調度LDRF算法，提高了EDA并行任務的執(zhí)行效率和資源利用率，并保證了調度的公平性。由于EDA仿真過程中步驟繁瑣，復雜性高，任務之間可能有依賴性，下一步工作將是基于EDA多任務流算法的研究。保證有依賴關系的任務在license數(shù)量充足的前提下依次執(zhí)行。