|
本論文討論平行化編譯程式中的一些重要問題, 主要的研究在於迴圈平行度的抽取和
利用, 並對這些問題提出解決方法。這些問題包含四個主要的課題: 平行度的抽取 (
parallelism extraction) 、程式的分割(program partitioning)、處理機的分配 (
processor assignment) 、和處理機的自我排程(processor self-scheduling)。
對於平行度的抽取, 我們提出一種新的技巧, 能夠根據資料相依圖, 抽取出回圈中隱
含的平行度。所抽取出的平行度比文獻上類似的作法更多。對於程式的分割, 我們並
不採用經驗法則, 而是利用排除且搜尋的技巧和區段分割的技巧, 設計出一個完全多
項式時間的近似方法。這個方法所產生的解的成本可以任意地接近最佳解的成本, 而
且對任意固定的相對誤差, 這個方法所需的計算時間同時是問題大小和相對誤差的倒
數的多項式。
對於處理機的分配, 我們提出兩種非常有效率的演算法, 比目前文獻上的最佳演算法
更快速。此外我們也考慮迴圈轉換對處理機分配的影響, 並且發現適當的迴圈轉換對
處理機分配很有幫助。最後我們提出一種處理機自我排程的方法, 不但能達到最佳負
載平衡, 同時可以避免過多的額外負擔。
我們也進行一些理論推導和實驗以驗證這些方法。由推導出的定理和實驗的結果可以
證實這些方法的確改進平行執行的效能。
|