子計劃一： "可延展性平行演算法的設計策略與分析"

本子計畫今年欲完成之工作有:
(1) 在 ATM/PVM 異質分散計算環境上, 發展一套可延展性平行演算法的設計策略。將包含以下三個工作:
　1. 在 ATM/PVM 平臺上, 設計可延展性平行 SOR 演算法並實作之。
　2. 在 ATM/PVM 平臺上, 設計可延展性平行Matrix Searching 演算 法並實作之。
　3. 在 ATM/PVM 平臺上, 設計可延展性平行 Branch-and-Bound 演算 法並實作之。
(2) 在 ATM/PVM 異質分散計算環境上, 建立可延展性平行演算法的分析模式。 將包括以下三個工作:
　1. 在 ATM/PVM 平臺上, 分析平行SOR 演算法的延展性。
　2. 在 ATM/PVM 平臺上, 分析平行 Matrix searching 演算法的延展性。
　3. 在 ATM/PVM 平臺上,分析平行Branch-and-Bound 演算法的延展性。
(3) 在 ATM/PVM 異質分散計算環境上, 發展一套以 Parallel Branch-and- Bound 演算法為核心的 NP-hard Problem Solver 系統及 Integer Programming Solver 系統。 我們預期對可延展性分析理論有新的發現,可以發表論文於期刊上。參與本計劃的人員, 將經由平行演算法實作的機會,來驗證平行演算法的實用性,並有機會分析實際的異質分散 計算模式,有助益於拉近理論與實作間的差距。這批參加計劃的人員,將對日後工業界發展 異質分散計算環境時貢獻他們的經驗。

子計劃二： "可延展性的數值方法及平行化線路模擬器之應用"

第三年工作項目：
(1) 在異質 PVM 系統上, 各種數值計算方法實作; 其中包括 CG, BCG, BCGSTAB, CGS , QMR, TFQMR, QR, QD, ...等等。
(2) 同步化程式(synchronized program) 的平行計算時間分析,以 QD 為例。
(3) 預條件技術的探討與平行化。
(4) 稀疏矩陣處理。
(5) 可延展性數值計算方法設計與分析。
(6) 建立可延展性分析模式。
(7) 在異質 PVM 系統上, 解一種動力方程式: Boltzmann transport 方程 式。其結果將可用在核反應器中的線性系統部份。

成果及效益:
　　除了預計完成以上所執行的項目外, 我們也希望與發展 PVM 系統的研究團體有著 密切的互動, 並提出 PVM 系統上的一些新的應用取向上的需求以及修改製作 PVM 系統上的相關軟體和撰寫相關論文來分享我們的研究經驗。除此之外, 更重要的 是希望提出一套實際可行的平行演算法分析模式以分析應用在平行計算上。事實 上, 目前我們正嘗試提出另一種分析模式, 而且更積極的希望透過系統組來設計 相關環境以評估所提出的分析方法是否可行。因此, 透過此一計畫的執行,除了相 關人員得以有參與開發系統軟體的經驗外, 而更重要的是此一 計劃成果的經驗 可以直接轉移在學術界發展與工業界的應用上。我們相信, 以Berkeley SPICE 套裝軟體的改進及解 Boltzmann transport 方程式兩個成功實驗, 將會吸引 工業界採用這種異質 PVM 系統。

最後,今年度子計劃目標總結如下:
(1) 根據各種不同的預條件方式來分類一些合適且具有應用價值的矩陣解法。
(2) 修改一些已存在的方法使其達到更穩定與收斂速度更快的效果。
(3) 提出一些 Hybrid 計畫或甚至提出新的方法。
(4) 預條件式的可延展性數值演算法的設計與研究。
(5) 在 PVM 環境下透過 isospeed 及 latency 的可延展性實驗方法來測量 我們設計的各種平行演算法。
(6) 同步化程式的可延展性平行計算時間分析,以 QD 計算為例。
(7) 新的可延展性量度(metric)設計。

預期成果將包括:
(1) 撰寫相關論文以分享我們的研究心得。
(2) 發展出迭代子空間演算法的異質 PVM 版本。
(3)達成訓練研究生或助理研究員有關數值計算的技巧,並且所有的研究工 作將有助完成相關研究生的學位取得之要求。

子計劃三： "可延展性的數值方法及平行化線路模擬器之應用"

我們將以一年的時間完成下列子目標︰
(1)在光線追蹤法方面(ray tracing) •在資料平行化方面：提出動態負載平衡以提高可延展性。
　•在控制平行化方面：將與系統組配合以分散式空間結構模擬"分享記憶"， 討論控制平行化的加速行為。
　•在PVM的工作平台上，製作及測試新方法的加速效果。
(2)在輻射量計算法方面(radiosity)
　•改進過去"主從"的分散式結構而成為"同儕式"(cluster)，以提高系統的 可延展性。
　•研究階層式輻射成像法之平行化。 •探討非完全散射的平行演算法。
　•在PVM上，以實例驗證新方法的加速效果及可行性。
(3)在實體成像法方面(volume rendering)
　•在規則性實體資料上將整合"資料平行"(data parallel)與"影像平行" (image parallel)，以提高可延展性。
　•研究非規則性實體資料之平行化成像法。
　•研究幾合及布林運算之平行演算法。
　•在PVM平台上，以實例驗證平行化之加速績效。

子計劃四： "可延展性程式發展環境"

(1)Compiler
　•做出一個在異質環境下，具有新的平行結構和分散物件的C++語言。
　•用實際的應用程式去測試這個語言環境。
　•發展針對這個語言特性的編譯技巧。
　•建立有效率的C++類別程式庫。
　•評估在即時條件下的效果。
　•編譯器最佳化。
(2)Load-balancing System
　•完成第二年所研發可延展性動態負載平衡策略的實作。
　　a.整合第二年所完成的可延展性動態負載平衡策略雛形之各個模組。
　　b.對所整合的可延展性動態負載平衡系統進行測試工作。
　•整合此一可延展性動態負載平衡策略至可延展性計算環境中。
　　a.由第二年研究在平行計算環境下關於負載平衡的影響所得結果，對可延展 性動態負載平衡系統作適當的修改。
　　b.提供相關的使用介面供可延展性計算環境之其他模組使用。
　　c.撰寫詳細的使用說明文件。
　•評估此系統的效率。
　　a.研究、設計適當的系統評估模式(Evaluation Model)，如負載產生(Load generation)模式等。
　　b.以 A 所發展之評估模式對可延展性動態負載平衡策略進行效能測量。
　　c.評估可延展性動態負載平衡策略的效能表現，並調整系統參數以使其達到最佳之效能。
(3)Library
　　此期計畫中，將預期能夠完成一套架構於PVM上之Heterogeneous Distributed Shared Memory的Library，提供較佳之Programability以撰寫Scalable Applications。同時，針對Communication Overhead，我們將探討幾種較新的策略以增加 Scalability。包括Interrupt Driven 的 Communication，以及 Collective Communication 的Library 製作。
　　工作項目如下：
　•繼續完成Collective Communication Library的發展。
　•評估我們架在PVM上所完成的Heterogeneous Distributed Shared Memory ， Interrupt Driven，和 Collective Communication Libraries 彼此之間的關連性 ，以及對 Scalibility 的影響。
　•研究這樣的Libraries是否能夠對Run_time的其它動作造成什麼正面的效果。
(4)System Kernel 工作項目如下：
　•Task Management的規劃。
　•Task Management的程式撰寫。
　•P4 Interface Design。
　•System Integration。

　　本計畫所要完成的只是一個"麻雀雖小，五臟俱全"的虛擬分散式記憶體 多處理機系統核心。 本計畫所完成的系統除了可作為教學上的應用外，也可以應用在實際多 處理機的問題上。 本計畫乃是針對目前期盼學術界從事系統方面研究的一個直接回應。對 於系統方 面的工程師及研究人員的訓練與培養，將有重大的貢獻。參與計畫 的人員經由計畫中學習到的經驗可用來從事更複雜、更前瞻的計畫。這樣的 經驗對於學術界及工業界而言，均為重要的資源。