王慶江　桂小林　鄭守淇

摘要：為了縮短網(wǎng)格中數(shù)據(jù)并行流水線在吞吐率受限下的延遲，提出了一種優(yōu)化任務指派的算法．在一個流水線中，每個任務都可以是一個數(shù)據(jù)并行程序．當多個任務被指派到同一個并行系統(tǒng)時，假設(shè)每個任務排他地使用一組處理機．根據(jù)優(yōu)化目的，優(yōu)化過程可分成連續(xù)的兩個階段，即提高吞吐率和縮短吞吐率受限下的延遲．對不同的優(yōu)化階段，用不同的啟發(fā)式算法確定一個并行系統(tǒng)中每個任務的處理機數(shù)．改派任一任務都會使流水線的性能發(fā)生變化，性能提高的幅度被稱為任務優(yōu)先級．通過重復改派優(yōu)先級最高的任務，流水線的性能可迅速提高，這在仿真實驗中已得到了證實．

關(guān)鍵詞：網(wǎng)格；流水線；數(shù)據(jù)并行流水線；吞吐率；延遲；任務指派

中圖分類號：TP393文獻標識碼：A文章編號：0253—987X(2004)08—0771—04