本論文研究Do─Loop式的循序程式之平行處理。做平行處理時，時空安排法則的考量
要件為：（i）加速處理（speedup），（ii）效率（efficiency），（iii） 局部性
（locality）， 及（iv） 可實行性（practicability）。基於加速處理的考慮，我
們提出極緻並列法（extremely─effective coordinate method）。它在確定的時間
安排下，可以達到最少的計算步驟，在確定的空間安排下，可以使傳送時間趨近最佳
。基於可實行性的考慮，我們針對SIMD及MIMD的鬆連結式機器（loosely coupl ed
machine）， 提出虛處理機（virtual processor） 及二階時間（two level timing
）的觀念，而在虛處理機空間上實現了一般方法“處理機數目無限〞的假設，進而解
除其理論與實際安排之間的不相容性（incompatibility）。 也透過這兩個觀念，我
們在迴圈層次（iteration level） 建立一套平行性實現模式，稱為分批完全疊合實
現模式（batching overlap parallelism realization model），它融合了時間、空
間、記憶體使用等安排及計算、傳送方式而為一體。透過彈性的間及虛處理機安排可
以達到高效率和局部性，而也自然地解決了問題尺度過大（too large sixe of comp
utauional problem）， 高維循迴平行執行（parallel execution of high dimensi
─oonal looplem）等問題。另外，我們建議關鏈代入（critical substitution）的
觀念，只要透過一條指述（statement）的代入就可以解除程式在原安排下的執行瓶
頸。我們把它應用在Ⅱ一群法（ Ⅱ─block method），超平面法（hyperplane metA
─hod）， 超平面法（hyperplane method），和極紋碰列法下而提出突破瓶頸的與定
理。在論文，我們明確地建立Do─Loop 的執行模式，並進行精確的執行時間求算，這
使得以上的結果有很強的理論支持。
|