基于繪制時(shí)間的加權(quán)動態(tài)負(fù)載均衡算法

李文強(qiáng)，陸應(yīng)通

（1.四川大學(xué)計(jì)算機(jī)學(xué)院，成都 610065；2.四川大學(xué)視覺合成圖形圖像技術(shù)國防重點(diǎn)學(xué)科實(shí)驗(yàn)室，成都 610065）

基于繪制時(shí)間的加權(quán)動態(tài)負(fù)載均衡算法

李文強(qiáng)1，陸應(yīng)通2

（1.四川大學(xué)計(jì)算機(jī)學(xué)院，成都 610065；2.四川大學(xué)視覺合成圖形圖像技術(shù)國防重點(diǎn)學(xué)科實(shí)驗(yàn)室，成都 610065）

負(fù)載均衡是影響集群并行繪制系統(tǒng)整體性能的關(guān)鍵因素之一。由于場景數(shù)據(jù)的分布不均，在運(yùn)行過程中經(jīng)常出現(xiàn)負(fù)載失衡的現(xiàn)象。針對sort-first型并行繪制系統(tǒng)的特點(diǎn)，綜合考慮每個(gè)繪制節(jié)點(diǎn)的繪制能力，使用權(quán)重因子加權(quán)繪制時(shí)間，提出了一種基于繪制時(shí)間加權(quán)的動態(tài)負(fù)載均衡算法。算法包括負(fù)載預(yù)估、任務(wù)動態(tài)劃分與分配。負(fù)載預(yù)估時(shí)，使用加權(quán)后的時(shí)間估算屏幕中每個(gè)像素點(diǎn)的負(fù)載。任務(wù)分配階段，根據(jù)負(fù)載分布，同時(shí)參考繪制能力，動態(tài)劃分繪制任務(wù)。實(shí)驗(yàn)結(jié)果表明該算法能夠提高系統(tǒng)的幀率，提高系統(tǒng)負(fù)載的穩(wěn)定性。

并行繪制；動態(tài)負(fù)載均衡；自適應(yīng)；歸屬判斷

0 引言

超大規(guī)模場景交互式應(yīng)用中，因其海量的數(shù)據(jù)與繪制實(shí)時(shí)性需求，對系統(tǒng)的處理能力提出了新的挑戰(zhàn)。雖然硬件產(chǎn)品的更新?lián)Q代使得PC的整體性能得到了較大提升，但應(yīng)用的需求與單機(jī)所能提供的繪制能力之間的矛盾卻日益突出。專業(yè)圖形工作站雖能滿足應(yīng)用需求，但昂貴的價(jià)格限制了其應(yīng)用范圍。通過高速網(wǎng)絡(luò)互聯(lián)的PC集群實(shí)現(xiàn)圖形的并行處理，具有較高的擴(kuò)展性與性價(jià)比，能提供與專業(yè)圖形設(shè)備相媲美的處理能力，滿足應(yīng)用需求[1]。在這種集群分布式并行繪制系統(tǒng)中，Molnar等人按照渲染任務(wù)劃分階段與方式[2]，將并行繪制系統(tǒng)的體系結(jié)構(gòu)劃分為sort-first[3]、sort-mid dle[4]、sort-last[5]三種基本類型，奠定了并行繪制體系結(jié)構(gòu)研究的理論基礎(chǔ)。

在三種基本的體系結(jié)構(gòu)中，sort-middle由于需要專有的圖形硬件支持，并沒有運(yùn)用到實(shí)際的系統(tǒng)之中。對sort-last型，圖像合成與網(wǎng)絡(luò)帶寬是系統(tǒng)的性能瓶頸，且限制了集群的規(guī)模。sort-first則最大限度保留了圖形繪制流水線的完整性，非常適合于集群并行繪制系統(tǒng)。但其最大的問題在于容易因場景數(shù)據(jù)分布不均出現(xiàn)負(fù)載失衡，造成資源浪費(fèi)，降低系統(tǒng)性能。因此，如何解決負(fù)載失衡是并行繪制研究的首要問題。

1 相關(guān)工作

負(fù)載均衡是影響集群并行繪制系統(tǒng)整體性能的關(guān)鍵因素之一，開發(fā)高質(zhì)量的負(fù)載均衡算法是提高系統(tǒng)運(yùn)行效率的有效手段。針對sort-first型而言，負(fù)載均衡一般通過對屏幕空間的劃分來實(shí)現(xiàn)，按照劃分方式可將算法分為兩大類：靜態(tài)負(fù)載均衡算法與動態(tài)負(fù)載均衡算法。后者根據(jù)負(fù)載變化，動態(tài)調(diào)整任務(wù)劃分，具有良好的可適應(yīng)性，成為負(fù)載均衡算法的主要研究方向。

動態(tài)負(fù)載均衡算法中，按照系統(tǒng)負(fù)載預(yù)估策略的不同，將其分為兩大類：基于幾何數(shù)據(jù)預(yù)處理的負(fù)載均衡算法與基于繪制歷史的負(fù)載均衡算法。前者以落在屏幕空間中幾何圖元的個(gè)數(shù)作為繪制負(fù)載的量化標(biāo)準(zhǔn)，通過對頂點(diǎn)等幾何數(shù)據(jù)的矩陣變換，確定在屏幕空間的位置，從而完成負(fù)載分布的估計(jì)，如Roble算法[6]、Median-cut算法[7]、Whitman的自頂向下分解算法[8]、MAHD算法[9]等，這類算法需要處理整個(gè)場景數(shù)據(jù)，場景越大，開銷越大，不適合用于超大規(guī)模的實(shí)時(shí)應(yīng)用。

基于繪制歷史的負(fù)載均衡算法（也稱之為時(shí)空轉(zhuǎn)換類算法）的理論基礎(chǔ)是幀間連續(xù)性[10]，即：在交互式系統(tǒng)中，相鄰兩幀間場景數(shù)據(jù)、繪制開銷等變化不大，可用上一幀繪制時(shí)間近似估算下一幀繪制所需時(shí)間。在估計(jì)場景負(fù)載分布時(shí)，使用繪制時(shí)間來度量負(fù)載。金哲凡在其博士論文[11]中首次提出了以時(shí)間作為負(fù)載度量的標(biāo)準(zhǔn)，開啟了這類算法的研究。此后許多類似算法被相繼提出，如：延期著色算法[12]、基于Q-Learning負(fù)載平衡策略[13]、二叉預(yù)測樹算法[14]等。這類算法計(jì)算效率高，能達(dá)到較好的平衡效果。但無法準(zhǔn)確估計(jì)出繪制時(shí)間，容易受軟硬件環(huán)境差異與視點(diǎn)突變等因素的影響，對負(fù)載的評估易產(chǎn)生較大偏差。

結(jié)合上述算法的優(yōu)缺點(diǎn)，本文提出了一種改進(jìn)型的負(fù)載均衡算法：考慮節(jié)點(diǎn)計(jì)算能力對繪制時(shí)間的影響，得到一個(gè)影響因子，用上一幀的繪制時(shí)間與其相乘，用得到的結(jié)果計(jì)算每個(gè)像素的負(fù)載，并用于預(yù)估下一幀的負(fù)載；同時(shí)使用了一個(gè)具有統(tǒng)計(jì)意義的更新閾值來控制更新算法的執(zhí)行。

2 算法概述

幀間連續(xù)性是本算法的理論前提。圖1詳細(xì)描述了算法的執(zhí)行流程。系統(tǒng)在運(yùn)行過程中收集上一幀圖像繪制所用時(shí)間，并進(jìn)行更新閾值計(jì)算，用以判斷是否需要更新當(dāng)前任務(wù)劃分方式。滿足更新條件時(shí)，根據(jù)場景負(fù)載分布特點(diǎn)重新劃分繪制任務(wù)過程中，綜合考慮各繪制節(jié)點(diǎn)圖形處理能力不同、圖像區(qū)域大小互異等因素，計(jì)算得到一個(gè)統(tǒng)一標(biāo)準(zhǔn)下的影響因子，用加權(quán)后的繪制時(shí)間，去評估繪制屏幕空間中每個(gè)像素所需時(shí)間。劃分繪制任務(wù)時(shí)，根據(jù)節(jié)點(diǎn)計(jì)算能力的大小，按照“能者多勞”的原則進(jìn)行分配。

2.1 影響因子計(jì)算

考慮到PC集群中不同繪制節(jié)點(diǎn)的圖形處理能力有所不同，直接采用歷史繪制時(shí)間去評估負(fù)載大小會因度量標(biāo)準(zhǔn)上的差異引入誤差。例如：對于同一繪制任務(wù)而言，高配置機(jī)器繪制所需時(shí)間會小于低配置機(jī)器所需時(shí)間，所以需要引入一個(gè)統(tǒng)一標(biāo)準(zhǔn)來消除因硬件環(huán)境不同而產(chǎn)生的度量上的誤差。

初始運(yùn)行時(shí)讓集群中所有繪制節(jié)點(diǎn)繪制同一場景，分別用時(shí)t1，t2，…，tn，設(shè)集群中繪制這一幀所用最長時(shí)間為tmax。繪制節(jié)點(diǎn)計(jì)算能力影響因子定義為：在同一繪制任務(wù)中，集群中最長繪制時(shí)間除以該節(jié)點(diǎn)繪制所用時(shí)間。公式（1）給出了節(jié)點(diǎn)i計(jì)算能力影響因子計(jì)算過程。后續(xù)處理需要用到繪制時(shí)間時(shí)，直接使用影響因子對繪制時(shí)間做歸一化處理，得到一個(gè)在相同計(jì)算標(biāo)準(zhǔn)下的繪制時(shí)間值。

并非人人都有逃避的自由，亂世中為勢所迫，明哲保身的人不在少數(shù)。五代時(shí)期，士人無論是在朝廷任高官還是在地方做小吏，內(nèi)心有一種朝不保夕的恐懼感。在混世的風(fēng)氣下，他們隨勢可否，不為事先，唯唯諾諾，傳統(tǒng)的人格精神失去了維系世道人心的力量，與盛唐銳意事功、開拓奮進(jìn)的精神面貌相去甚遠(yuǎn)。

圖1 算法處理流程

任務(wù)分配時(shí)，為了最大限度的提高資源利用率，使得繪制節(jié)點(diǎn)在大多數(shù)情況下都處于忙碌狀態(tài)。根據(jù)節(jié)點(diǎn)計(jì)算能力大小按“能者多勞”的原則動態(tài)分配繪制任務(wù)。設(shè)總的繪制任務(wù)量為單位1，所有節(jié)點(diǎn)根據(jù)自己的計(jì)算能力得到一個(gè)所承擔(dān)計(jì)算任務(wù)在總?cè)蝿?wù)中所占的比值，將其定義為節(jié)點(diǎn)計(jì)算任務(wù)比。采用公式（2）計(jì)算，根據(jù)（2）式不難證明所有節(jié)點(diǎn)的計(jì)算任務(wù)比值之和為1，從而保證了集群中的繪制節(jié)點(diǎn)正好無重復(fù)完成所有繪制任務(wù)。

2.2 負(fù)載預(yù)估與任務(wù)劃分

本文采用基于屏幕二維空間的剖分實(shí)現(xiàn)繪制任務(wù)的劃分，每一個(gè)繪制節(jié)點(diǎn)需要保留的數(shù)據(jù)包括：當(dāng)前區(qū)域邊界、歷史繪制時(shí)間CostTime、區(qū)域預(yù)估負(fù)載EstimateTime等。服務(wù)器作為系統(tǒng)中心控制節(jié)點(diǎn)，在系統(tǒng)運(yùn)行過程中收集所有節(jié)點(diǎn)繪制上一幀所用時(shí)間，經(jīng)過（3）歸一化處理后，用其計(jì)算節(jié)點(diǎn)的EstimateTime域。

完成場景負(fù)載分布預(yù)估后，需要選取一種合理有效的屏幕劃分方式，按照各繪制節(jié)點(diǎn)的計(jì)算能力分配負(fù)載。在劃分的過程中，為了避免大量出現(xiàn)細(xì)長條形的劃分方式，本算法總是沿著當(dāng)前區(qū)域中較長邊進(jìn)行劃分。設(shè)當(dāng)前任務(wù)區(qū)域塊Region有w行h列（設(shè)w＜h，記為R（0，h）），區(qū)域總負(fù)載為ER；R（i，j）表示Region中從第i列到第j列像素所組成的子塊；負(fù)責(zé)當(dāng)前任務(wù)區(qū)域的繪制節(jié)點(diǎn)集合為N，將N按照負(fù)載量均分成兩份N1與N2，并盡可能滿足公式（4）。

任務(wù)劃分的目標(biāo)就是根據(jù)繪制節(jié)點(diǎn)集合N1、N2找到一個(gè)k值將當(dāng)前任務(wù)區(qū)域塊Region分成R（0，k）和R（k+1，h），兩個(gè)區(qū)域的負(fù)載分布記為ER（0，k）與ER（k+1，h），k滿足公式（5）所列出的條件。

本算法總是沿著當(dāng)前區(qū)域中較長邊進(jìn)行劃分，即每次在區(qū)域長邊上選取一個(gè)k值，在這個(gè)點(diǎn)上做垂直于該邊的劃分，將當(dāng)前區(qū)域劃分成兩個(gè)相鄰且不重疊的子區(qū)域。

任務(wù)劃分過程可由一棵二叉樹描述，圖2給出了一個(gè)擁有4個(gè)繪制節(jié)點(diǎn)的并行繪制系統(tǒng)屏幕子塊劃分過程，其中不同顏色標(biāo)識了最終的不同繪制任務(wù)。

圖2 屏幕子塊劃分

2.3 任務(wù)更新策略

假設(shè)當(dāng)前集群系統(tǒng)有n個(gè)繪制節(jié)點(diǎn)，設(shè)ti是第i個(gè)繪制節(jié)點(diǎn)繪制上一幀所用時(shí)間，其均值μ與方差σ12可由公式（6）計(jì)算。

為簡化計(jì)算復(fù)雜度，采用文獻(xiàn)[14]給出的調(diào)整方式，即合并小負(fù)載，分割大負(fù)載。設(shè)Ra是開銷最大的繪制節(jié)點(diǎn)，Rb和Rc是tRb*tRc最小的相鄰繪制節(jié)點(diǎn)。將Ra分裂為Ra1與Ra2，合并Rb與Rc為Rbc，其余劃分方式不變，得到新的方差σ22。劃分前與劃分后兩方差相減，整理得到（7）式。

系統(tǒng)運(yùn)行過程中，服務(wù)器收集上一幀繪制所用時(shí)間，經(jīng)歸一化處理之后，更新繪制節(jié)點(diǎn)的EstimateTime的值。在每一幀分發(fā)繪制任務(wù)之前，使用未經(jīng)過歸一化處理的繪制時(shí)間計(jì)算更新控制閾值Threshold。如果Threshold＞0，則認(rèn)為系統(tǒng)處于不均衡狀態(tài)，需要調(diào)整任務(wù)劃分方式；否則，仍然按照上一幀的劃分方式分配任務(wù)。

圖3 相同節(jié)點(diǎn)繪制時(shí)間對比

3 實(shí)驗(yàn)及分析

本文算法的驗(yàn)證在實(shí)驗(yàn)室并行繪制集群的基礎(chǔ)[15]下完成，采用6臺Intel Xeon E3-1230V2 3.30GHz，16G內(nèi)存，4塊NVIDA GeForce GTX980和2塊NVIDA GeForceGTX670圖形加速卡，6塊InfiniBand MCX353A-TCBT網(wǎng)卡，一臺Mellanox IS5022交換機(jī)。對同一場景在相同視點(diǎn)變換條件下分別與靜態(tài)負(fù)載均衡算法和未加權(quán)的動態(tài)負(fù)載均衡算法比較。

負(fù)載均衡實(shí)驗(yàn)所使用的動態(tài)場景包含12個(gè)dragon模型。為準(zhǔn)確評價(jià)本算法性能，我們將其與靜態(tài)負(fù)載均衡算法相對比，兩組試實(shí)驗(yàn)中所使用的測試場景、視點(diǎn)信息、相機(jī)參數(shù)完全一致。圖3給出了靜態(tài)負(fù)載均衡算法與動態(tài)負(fù)載均衡算法運(yùn)行過程中同一繪制節(jié)點(diǎn)在連續(xù)30幀里的繪制開銷對比。

圖3可以看出，同一繪制節(jié)點(diǎn)在相同條件下運(yùn)行場景時(shí)，每幀繪制所需時(shí)間相差較大。這是因?yàn)殪o態(tài)算法運(yùn)行過程中不改變繪制區(qū)域的大小，而落入該區(qū)域的圖元數(shù)目隨視點(diǎn)改變而變化，造成繪制時(shí)間時(shí)高時(shí)低。動態(tài)算法會根據(jù)上一幀負(fù)載調(diào)整下一幀繪制區(qū)域，因此繪制開銷相對平緩。

為定量分析系統(tǒng)負(fù)載性能，使用變量負(fù)載系數(shù)factorLB=tmin/tCost，其中tcost表示集群系統(tǒng)繪制某一幀所用時(shí)間，tmin表示首先完成該幀繪制任務(wù)的繪制節(jié)點(diǎn)所用時(shí)間。factorLB可反映系統(tǒng)繪制負(fù)載分配狀況，factorLB值越接近1表明系統(tǒng)負(fù)載均衡性能越好。圖4給出了連續(xù)15幀里系統(tǒng)使用靜態(tài)算法與動態(tài)算法的factorLB柱狀圖。

從圖4可以看出，動態(tài)算法的factorLB值相對于靜態(tài)算法較大，且更加接近于1。這些特點(diǎn)表明本文的負(fù)載均衡算法提高了系統(tǒng)的負(fù)載性能。

圖4 factorLB柱狀圖

為驗(yàn)證加權(quán)動態(tài)算法的優(yōu)勢，各繪制節(jié)點(diǎn)使用了不同的顯卡（繪制節(jié)點(diǎn)的性能主要由顯卡性能決定）。圖5給出了三種算法在運(yùn)行過程中某段時(shí)間系統(tǒng)幀率對比。

圖5 系統(tǒng)幀率對比

并行繪制系統(tǒng)實(shí)際繪制速度取決于集群中運(yùn)行最慢的繪制節(jié)點(diǎn)。在動態(tài)場景中視點(diǎn)信息不斷發(fā)生改變，落入視域范圍內(nèi)的場景數(shù)據(jù)也隨之改變，場景數(shù)據(jù)在屏幕空間中的分布也不斷變化。靜態(tài)算法在系統(tǒng)運(yùn)行前就確定屏幕劃分方式，運(yùn)行過程中不再改變，而各子區(qū)域的數(shù)據(jù)有時(shí)分布較為均勻，有時(shí)相差較大，導(dǎo)致幀率時(shí)高時(shí)低，波動較大。動態(tài)負(fù)載均衡算法在運(yùn)行過程中，根據(jù)上一幀繪制負(fù)載的分布狀況，通過調(diào)整繪制節(jié)點(diǎn)繪制區(qū)域，確定下一幀各繪制節(jié)點(diǎn)的繪制任務(wù)，能夠適應(yīng)場景負(fù)載的變化，所以繪制幀率較高，曲線也相對平緩。但未加權(quán)的動態(tài)均衡算法與加權(quán)動態(tài)均衡算法相比，由于繪制節(jié)點(diǎn)性能各異，使得前者的幀率明顯低于后者的幀率。圖5也印證了這一現(xiàn)象，實(shí)驗(yàn)結(jié)果顯示，使用加權(quán)動態(tài)算法，系統(tǒng)幀率維持在19～22幀，而相同條件下未加權(quán)動態(tài)算法幀率維持在17～19幀，靜態(tài)算法幀率維持在11～16幀。

產(chǎn)生上述特點(diǎn)的原因有：第一、靜態(tài)負(fù)載均衡算法在運(yùn)行過程中任務(wù)劃分方式不再改變，在某些視點(diǎn)條件下將高負(fù)載分配給高配置機(jī)器，反之亦然，故運(yùn)行時(shí)出現(xiàn)較大的波動性。第二、動態(tài)負(fù)載均衡算法在運(yùn)行過程中動態(tài)根據(jù)負(fù)載調(diào)整任務(wù)劃分，故受視點(diǎn)變化影響較小。第三、未加權(quán)動態(tài)負(fù)載均衡算法雖動態(tài)劃分任務(wù)，但在負(fù)載預(yù)估與任務(wù)分配時(shí)，未考慮機(jī)器硬件繪制能力的差異，從而引入了較大誤差，在某些視點(diǎn)下使得低配置機(jī)器承擔(dān)了較高負(fù)載的繪制任務(wù)。本文提出的算法使用繪制能力對繪制時(shí)間加權(quán)，并應(yīng)用到負(fù)載預(yù)估與任務(wù)分配中，使得各繪制節(jié)點(diǎn)合理的承擔(dān)了繪制任務(wù)，故幀率相對于前者有所提高。第四、兩種動態(tài)負(fù)載均衡算法均出現(xiàn)一定的波動性，其根本原因在于他們都是一種負(fù)載失衡補(bǔ)救策略，當(dāng)幀間連續(xù)性失效時(shí)，負(fù)載預(yù)估將不再準(zhǔn)確，系統(tǒng)需要一定時(shí)間來調(diào)整。

4 結(jié)語

負(fù)載均衡是并行繪制系統(tǒng)中影響性能的最為關(guān)鍵問題，本文提出的基于繪制時(shí)間加權(quán)的動態(tài)負(fù)載均衡算法的處理思路為：考慮繪制節(jié)點(diǎn)的繪制能力，得到一個(gè)因子去歸一化處理繪制時(shí)間；計(jì)算屏幕空間像素點(diǎn)負(fù)載時(shí)，考慮區(qū)域大小的影響，并使用加權(quán)后的時(shí)間去估算；分配繪制任務(wù)時(shí)，根據(jù)繪制能力大小，按比例分配任務(wù)；并采用方差這一更新閾值控制任務(wù)劃分更新算法的執(zhí)行。最后通過對比實(shí)驗(yàn)證明了本文所提算法的正確、有效性，并給出了理論上的分析說明。

在本文基礎(chǔ)上，后續(xù)的一個(gè)潛在可改進(jìn)方向：考慮幀間連續(xù)性失效的情況下，通過學(xué)習(xí)的手段，在對大量歷史運(yùn)行數(shù)據(jù)的研究下，找到各種輸入與負(fù)載之間的關(guān)系，從而在知道視點(diǎn)的情況下，可更加精確地估算系統(tǒng)負(fù)載，以期達(dá)到更好的平衡效果。

[1]劉真,石教英,彭浩宇,等.基于PC集群并行圖形繪制系統(tǒng)綜述[J].系統(tǒng)仿真學(xué)報(bào),2006(z1):70-72.

[2]Steven Molnar,Michael Cox,David Ellsworth,and Henry Fuchs.A Sorting Classification of Parallel Rendering[J].Computer Graphics and Applications,IEEE,14(4):23-32,1994.

[3]E Bethel,Greg Humphreys,Brian Paul,J Dean Brederson.Sort-First,Distributed Memory Parallel Visualization and Rendering[C].In Proceedings of the 2003 IEEE Symposium on Parallel and Large-Data Visualization and Graphics,page 7.IEEE Computer Society, 2003.

[4]Erik Ordentlich,Craig M Wittenbrink.Systems and Methods for Compressing Rasterization Setup Data Within a Sort Middle Graphics Architecture:U.S.Patent,6995769[B2],2006.

[5]Kenneth Moreland,Brian Wylie,Constantine Pavlakos.Sort-Last Parallel Rendering for Viewing Extremely Large Data Sets on Tile Displays[C].In Proceedings of IEEE 2001 Symposium on Parallel and Large-Data Visualization and Graphic,pages 85-92.IEEE Press,2001.

[6]Douglas R Roble.A Load Balanced Parallel Scanline Z-Buffer Algorithm for the Ipsc Hypercube[C].In Proceedings of Pixim,Volume 88,pages 177-192,1988.

[7]Daniel S Whelan.Animac:A Multiprocessor Architecture for Real-Time Computer Animation，1985.

[8]Scott Whitman.Dynamic Load Balancing for Parallel Polygon Rendering[J].Computer Graphics and Applications,IEEE,14(4):41-48, 1994.

[9]Carl Mueller.The Sort-First Rendering Architecture for High-Performance Graphics[C].In Proceedings of the 1995 Symposium on Interactive 3D Graphics,pages 75-ff.ACM,1995.

[10]彭浩宇.基于PC集群機(jī)的并行圖形繪制系統(tǒng)研究[D].杭州:浙江大學(xué)圖書館,2006.

[11]金哲凡.保留模式圖形并行繪制研究[D].杭州：浙江大學(xué)，2003.

[12]常輝,雷小永,戴樹嶺.基于動態(tài)負(fù)載平衡的sort-first繪制集群[J].北京航空航天大學(xué)學(xué)報(bào),2010(4):447-450.

[13]Sina Meraji,Wei Zhang,Carl Tropper.A Multi-State Q-Learning Approach for the Dynamic Load Balancing of Time Warp[C].In Proceedings of the 2010 IEEE Workshop on Principles of Advanced and Distributed Simulation,pages 142-149.IEEE Computer Society,2010.

[14]Biagio Cosenza,Gennaro Cordasco,Rosario De Chiara,et al.Load Balancing in Mesh-Like Computations Using Prediction Binary Trees[C].In Parallel and Distributed Computing,2008.ISPDC'08.International Symposium on,pages 139-146.IEEE,2008.

[15]付訊,葉慶.基于InfiniBand的集群分布式并行繪制系統(tǒng)設(shè)計(jì)[J].四川大學(xué)學(xué)報(bào)，2015,52(1):39-44.

Dynamic Load Balancing for Parallel Rendering System Based on Rendering Time Weighted

LI Wen-Qiang1，LU Ying-Tong2
（1.College of Computer Science，Sichuan University，Chengdu 610065；2.National Key Laboratory of Fundamental Science on Synthetic Vision，Sichuan University，Chengdu 610065）

Load balancing is one of key factors that influences the performance of the parallel rendering system.The existing algorithms usually suffer from high load imbalance during the execution because of the irregular nature of datasets.Proposes an improved load balancing algorithm based on the rendering history for sort-first parallel rendering system,which includes load estimation and render task partition.This algorithm considers the processing ability of each render node,and gets a weight factor.During the load estimation stage,uses this factor to weight the rendering time and compute the render cost of each pixels.Then according to the load distribution and rendering ability, partitioning the render task dynamically.The experimental result shows that this method can improve the frame rate,maintain the stability of the system load.

Parallel Rendering;Dynamic Load Balancing;Self-Adaptive;Belong-Determining

1007-1423（2017）08-0045-06

10.3969/j.issn.1007-1423.2017.08.010

李文強(qiáng)（1990-），男，四川自貢人，碩士研究生，研究方向?yàn)椴⑿袌D形繪制、虛擬現(xiàn)實(shí)陸應(yīng)通（1991-），男，廣東佛山人，碩士研究生，研究方向?yàn)橛?jì)算機(jī)圖形學(xué)

2016-12-22

2017-03-10

國家自然科學(xué)基金（No.61472261）、國家科技支撐計(jì)劃（No.2012BAH62F03）