向量計算機多工處理之相依性迴圈切割法則

Abstract

在本篇論文中，我們提出一種應用在向量計算機上多工處理之DO- 迴圈切割法則，其 目的為使得原本迴圈(iterations)間相依性極大的DO- 迴圈可平行地被執行。我們依 據緊密連接部份(strongly connected components) 來切割如此的DO- 迴圈成許多可 在不同中央處理單元(CPUs)上執行的工作(tasks) 。此種DO- 迴圈切割法則能夠充份 利用Cray X-MP/4x上之特性。如經由T 暫存器及B 暫存器來做區塊資料傳遞(block d ata transfer) ，並且有兩個輸出入埠(I/O ports) 可同時存取記憶體。我們也推導 此DO- 迴圈切割法則在時間與空間的複雜性(complexity)，同時解釋此法則運用在多 工處理上並不會造成時間的瓶頸(bottleneck)。 經由進一步地推導效能預測模型來預測兩種不同多工處理方法的效能(performance) ，編譯器可在得知這些預測結果後，選擇較佳的多工處理方法來執行程式。在模擬結 果中，對一些具有相當嚴重相依性的DO- 迴圈而言，我們所提出的DO- 迴圈切割法則 有令人滿意之效能增益(speedup) 。本篇論文也收錄這些模擬結果。