基于EDA仿真軟件的多資源調(diào)度算法*

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

(1 中國(guó)科學(xué)院微電子研究所 三維及納米集成電路設(shè)計(jì)自動(dòng)化技術(shù)北京市重點(diǎn)實(shí)驗(yàn)室，北京 100029；2 中國(guó)科學(xué)院大學(xué)，北京 100049) (2019年12月12日收稿； 2020年1月21日收修改稿)

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

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

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

1 主流公平調(diào)度算法

1.1 DRF調(diào)度算法

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

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

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

(1)

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

1.2 license管理及調(diào)度

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

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

2 LDRF算法

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

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

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

(2)

滿足下列約束：

(3)

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

(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一個(gè)子任務(wù)所需資源向量li=(li1,li2,…,lis) 用戶i一個(gè)子任務(wù)所需license向量xi 用戶i已分配的任務(wù)數(shù)mi用戶i最多分配的任務(wù)數(shù)wi用戶i的權(quán)重步驟:1. 根據(jù)公式(4)計(jì)算每個(gè)用戶i的初始優(yōu)先級(jí)pi0,從大到小 排序并存入隊(duì)列P;2. for pi in P∥依次選擇初始優(yōu)先級(jí)高的用戶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ù)公式計(jì)算(2)計(jì)算每個(gè)用戶的占優(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資源調(diào)度為前提，如果任務(wù)缺乏license則不分配計(jì)算資源，這部分資源可分配給別的任務(wù)，保證資源充分利用。而DRF沒有考慮license調(diào)度，調(diào)度系統(tǒng)可能給任務(wù)分配資源但缺乏license授權(quán)，任務(wù)已分配充足的資源卻不能執(zhí)行，導(dǎo)致資源利用率下降。

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

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

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

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

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

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

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

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

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

3.2 公平性分析

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

4 總結(jié)

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