這篇論文是有關於如何在一SIMD CREWPRAM 的平行計算模組上,用有限的處理器,解 一疏散三角線性方程組,並且使得所需的時間(以總乘法及總加法運算次數做計時單 位)心可能短。 高斯消去法是被廣泛地使用在解線性方程組,在以往的研究中曾將高斯消去法解一線 性方程組的過程以一task graph來描述。由於在此盡考慮解疏散三角線性方程組,因 此對於解疏散三角線性方程組的過程我們將另以associated directed graph 來描述 ,並在這個圖形上設計排程演算法。相對於在task graph對頂點做排程在associated directed graph將對邊做排程,在排程過程中後者比前者有較大的選擇彈性,也就是 會得到較好的排程結果。 在此我們提出兩個排程演算法,皆能突破Wing與Huang 在task graph做排程的瓶頸。 第一個排程演算法是將一些在task graph上不能同時執行的運算,結合成一大運算並 用足夠的處理器執行,以降低執行乘法運算的時間(也就是對於m 個獨立乘法運算, 若以循序執行,則需m 次乘法運算的執行時間,若有足夠的處理器並且能以平行方式 執行則僅需要1次乘法運算的時間)。第二個排程演算法則結合了第一個排程演算法 的方法及有限制的使用前置換法,也就是允許適當的fill-in 產生,在處理器較多時 可得到比第一個排程演算法更好的結果。
|