基于時間偏差協議的動態負載平衡技術

摘要：對并行VHDL模擬的特殊性進行分析后，建立了一個并行VHDL模擬的動態負載平衡模型。在此模型中，提出動態調節最佳并行規模的動態負載平衡方法來解決系統資源緊張的問題，采用一種新的模擬中負載的度量方法——模擬推進度。此模型還包括基于標準偏差和最小通信變化量的動態負載平衡算法和一個運行中的負載遷移機制。最后對該模型進行可行性分析。

關鍵詞：并行超高速集成電路硬件描述語言模擬; 負載平衡; 負載分配; 時間偏差協議

中圖分類號：TP391．9文獻標志碼：A

文章編號：1001-3695(2007)12-0118-03

對于并行計算環境而言，由于多用戶的存在和任務分配不均衡等原因，導致各并行進程的相對速度不一致，需要通過負載調整，使系統負載達到平衡，以減少資源的浪費，從而提高模擬性能。在多個節點間通過負載分配和調整來實現負載平衡狀態的過程稱為負載平衡。雖然動態負載平衡技術在并行和分布式計算中得到了廣泛應用，但是對使用時間偏差協議的并行VHDL模擬系統而言，動態負載平衡的性質有所不同。

1）計算密度不同并行VHDL模擬的計算密度相對于傳統的分布式計算來說比較低，模擬中的通信開銷占了總運行時間的很大部分。

2）外部負載造成的影響不同傳統分布式計算中，外部負載只是造成應用程序可用計算資源及其他系統資源變少。并行VHDL模擬中，則造成各個節點的局部虛擬時間不同，從而引起運行中產生大量滯后消息的發送，進而引發大量的回退，使模擬性能急劇下降。

3）遷移的單位不同并行VHDL模擬中，負載遷移的單位是分配到每個模擬進程中的模擬對象。而在傳統的分布式計算中，動態遷移的負載多是以進程為遷移單位。

綜上所述，必須結合并行VHDL模擬自身的特點，開發新的適合并行VHDL模擬中的動態負載平衡算法，并且由于負載的動態性和負載變化的無規律性，使得并行VHDL模擬中的動態負載平衡問題更具挑戰性。

1研究現狀

國內外學者針對網絡負載平衡和高性能計算機的管理中間件等方面對負載平衡作了很多研究。Azzedine等人針對采用保守同步機制的并行離散時間模擬提出了基于CPU隊列長度的動態負載平衡算法。在采用樂觀同步機制的并行模擬中，Fujimoto等人針對動態負載平衡提出了后臺執行的概念。Shanker等人提出了自適應負載平衡算法。國內國防科技大學的一些學者對分布式仿真中的負載平衡進行了研究。這些研究表明，使用動態負載平衡技術，能夠在不同程度上提高并行VHDL模擬的性能，但對并行VHDL模擬中的動態負載平衡技術缺乏深入研究。盡管不同的負載平衡方法針對不同的模擬系統得到的效果是不一樣的，但是動態負載平衡策略研究的主要問題基本類似。主要有三個方面：負載分布判斷、選擇進行負載遷移涉及的對象、執行已經確定的轉移策略。

2動態調動處理機的負載平衡算法

負載即工作量，它直接表明了模擬節點或模擬進程完成自身任務所需要的執行時間。實現動態負載平衡的一種前提是用一種有效的方法來測量模擬系統中各個模擬進程的負載。基于未來信息得到的判斷應該比基于過去事件的判斷更準確。本文用SAP(simulation advance progress，模擬推進度)來度量模擬進程的負載，以LVT（local virtual time，局部虛擬時間）為標準，表示在單位虛擬時間中各個處理節點處理的對象個數。計算公式為

其中：^LVT為該處理節點模擬對象的最小時間戳和最大時間戳的差值；LVT為該處理節點的局部虛擬時間；n為未來^LVT內所模擬的對象個數。

該度量方式既考慮了基于時間偏差協議中的回退問題，又考慮了各個處理節點的模擬進度，所表示的是基于模擬節點上所要處理的事件數，而不是節點上的模擬對象數。并且這些事件是有時間標記的，就是根據其時間標記判斷一個處理器在未來一段時間中要處理的事件數來度量模擬進程的負載。

2．1最佳并行規模的調節

由于筆者的并行VHDL模擬系統是基于時間偏差協議的，允許進程盡可能樂觀地向前推進，收到遲到消息時再回退。這就需要保存大量的過去信息以保證回退的正確性。過多的狀態保存會大大增加系統的負擔，可以考慮當外部還有可用資源時，把它加入到處理機行列來。當系統負載相對較低時，則釋放多余的處理機。這樣不僅可以緩解系統資源緊張的情形，還可以更充分地利用已有的資源更有效地模擬系統。當然，并不是使用處理器越多系統模擬就越好。這其中還要考慮通信對性能的影響，使用益處函數來衡量系統性能，稍后再作介紹。

從圖2可以看出，負載度量方法的選擇對動態負載平衡的效果影響很大。筆者提出以未來推進度作為負載衡量方法雖然不是最好的方法，但也提高了30%的模擬性能。動態負載管理器較好地平衡了各個模擬進程的推進速度，使各個模擬進程之間收發反消息的次數明顯減少。LVT標準和PU標準的通信量高于SAP標準，但PU標準的發送消息個數稍小于LVT標準的個數。這說明進行動態負載遷移后，能夠有效地改善初始分配的不理想狀態。

4結束語

現今在并行VHDL模擬關于動態負載平衡方面的研究還很少，而且大多是基于給定數目的處理機的基礎上進行模擬的，并沒有一個可靠的算法決定應該選擇多少臺處理機。一方面可以考慮在工作繁忙時動態地添加處理機以緩解資源緊張的狀況，在工作較少時釋放部分處理機去處理別的事務，充分利用可用資源，解決了系統資源緊張的瓶頸問題，大大提升了系統的可擴展性；另一方面，在決定進行負載遷移時要選擇通信消耗最少的模擬對象進行遷移，更好地完成負載均衡的目標，提高系統的性能。最后從進行的標準測試電路的并行邏輯模擬的實驗可以得知：動態負載管理器為并行邏輯模擬系統提供了有效的動態負載平衡機制；在存在外部負載的情況下，模擬性能有了明顯提高。

參考文獻：

[1]李思昆.一種啟發式并行—邏輯模擬劃分算法[J].系統工程與電子技術，1999，21(9):68-70.

[2]陳進軍.并行VHDL模擬中動態負載平衡技術的研究與實現[D].上海:上海大學，2005:24-32.

[3]孟小鋒，慕曉強.分布式仿真中的負載平衡技術[J].現代計算機，2001，14(5):14-17.

[4]劉振莫，方濱興，胡鋁營.一個有效的動態負載平衡方法[J].軟件學報，2001，12(4):563-569.

[5]孫秀麗，蘇航.分布式VHDL模擬算法[J].太原理工大學學報，2002，33(1):32-34.

[6]周喜明.時間偏差的并行離散事件模擬研究綜述[J].計算機應用研究，2004，21(11):11-13.

[7]郁志輝.高性能計算并行編程技術——MPI并行程序設計[M].北京:清華大學出版社，2001:2-5.

[8]蔣江.異構集群系統中基于進程遷移機制的負載平衡算法的研究[D].長沙:國防科學技術大學，2002:25-36.

“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”