具可延展性的電腦系統（scalable computer system）可以讓使用者依需求 與經費而彈性的擴充其運算資源以期增加其計算能力。目前用以處理大量運算問 題的電腦系統，是以大量平行計算機（mpp）以及工作站群組（workstation cluster)為主流。當這類電腦系統擴充其運算資源時，如何真正的發揮該系統的 最大計算效能，並提供使用者一個容易發展高速計算應用的環境，是目前使用上 的最大瓶頸。
本整合計劃的總體目標，便是建立一個在可延展性電腦上的高速計算應用 之程式發展環境。我們預期經由演算法、系統及應用三方面的整合，提供使用者 一個發揮最大計算效能的程式發展環境。其成果可以直接提昇國內相關單位(如 國家高速電腦中心，氣象局等單位)的計算能量，加速分散式應用軟體的開發速 度，以及協助工作站或個人電腦業界，提高其產品的附加價值與競爭能力。 要建立一個完整的使用者之程式發展環境，勢必要由演算法、系統、及應 用三方面的人互相配合才能竟其工。可延展性演算法的設計策略與常用程式庫， 可做為各領域程式設計師發展其高速計算應用程式的主要參考依據；重要應用領 域，如數值、工程、與圖像等，的可延展性應用程式，可做為該領域使用者解決 問題的重要工具；可延展性的系統程式，如平行程式語言的編譯器（parallel programming language compiler）、負載平衡器（load balancer）等， 則提供一般使用者，在不必熟悉電腦系統架構的前提下，發展其應用程式。 因此，就環境的完整性而言，演算法、系統、及與應用三方面的人，必須互 相密切配合與研討，以便提供不同領域與層次之使用者，在可延展性電腦系 統上，發展其高速計算應用的各種完整途徑。
另外，就建立一個良好有效率的使者環境而言。一個成功的應用系統必須 建立在好的演算法及分析模式上。而發展應用程式與演算法的人更要得到系統的 充分支援，明瞭可能的瓶頸與因應之道，才有實用可行的產品產生。另一方面， 系統的設計也要能充分掌握應用的特性與需求，從而發展出高性能而又容易使用 的系統。在過去兩年的計劃執行中，本研究群已建立了此三類人，在共用實驗設 備（如ncube及cluster），共用研究討論、以及共享研究成果上的經驗交流與良 性互動基礎。
本總體計畫已是第三年，在第三年裡，各子計畫將分別實做出多個雛形系 統的製作，在本總體計劃有下列的整合必要性：
1.我們將使用同一個 atm/pvm 設備環境，互相共享，及提供製作各雛形 系統所需的設備與技術資源。
2. 我們製作完成的各雛形系統，將整合起來成為一個高速網路上高性能計算的整體環境，做一個高速網路應用的重要展示。
玆將本計劃今年各子計劃之子題架構說明如下：
在科學研究和工業應用的領域裡，大量的數值計算扮演著舉足輕重的角色。 例如，在SPICE 的套裝軟體中，大部份的CPU時間都被花費在暫時性的分析上。
為了模擬超過 10,000 個電晶體的大型電路系統，CPU 將會為此花費了大部份的 計算時間。
在本計畫中，我們利用數學公式來描述電路方程式並提供多種數值 方法來分析它。除此之外，我們亦對解 Boltzmann transport 方程式感到濃厚的 興趣，而此方程式主要應用在核子工程領域上。 在本計劃中，我們將著重於根據預條件式的 Krylov 子空間方法去製作能夠解 決一般疏矩陣的線性系統，並且將所研究的成果直接應用在 Berkeley SPICE 的 軟體和 Boltzmann transport 方程式的軟體以擴充其處理能力與彈性。稀疏矩陣 的計算常發生於包括半導體線路設計等許多科學應用上。由於單獨使用直接 法解的大型稀疏矩陣線性系統方程式所花的代價過於昂貴。因此，利用迭代 法的方式求解這類問題已經在科學與工程領域上越來越受到重視。
當一個系統中提供了大量更快速的處理機，大量的記憶體和更快速的傳輸設 備的環境以支援應用程式發展時，可延展性可以用來測量該程式在此環境下
的執行效率。從應用與演算法的展望而言，可延展性告訴了我們一個演算法 或應用程式能否可以完全利用到不同的系統資源的一個重要指標。在於一個 今年將建構完成的異質平行環境
--- PVM 上將上述的數值方法設計成可延展性 的演算法。而這些數值方法在此環境下的可延展性的分析則是我們的最終目 的。的確，一個平行演算法的複雜度取決於兩個參數
: 問題大小(用W表示) 和 在此環境下的處理機數量，系統大小(用P表示) 。根據此一共同的抽象概念， 在最近五年內，已經有許多的測度方式被提出來以測量一個平行演算法的可
延展性。依據這些測度，我們最後將測量我們所提的演算法在此系統下的可 延展性程度。
在計算機圖學中，為求得良好的圖像品質，常需要大量的計算時間，而其中 尤以光線追蹤法(ray tracing)，實體成像法(volume rendering) 與幅射量 計算法(radiosity)等三問題最耗費時間。因此如何使用平行計算，以達到快速 顯像的要求，成為目前極重要的研究課題。本計畫是延續過去二年有關可延展性 高性能運算中，平行顯像法的後續研究，過去我們利用空間分割的技巧提出了 平行化的演算法，亦經實驗測試，確實有加速(speedup)的效果，而且在負載 平衡(load balancing)上也有良好的表現。未來一年將繼續在負載平衡及可延展 性上做更深入的研究。
我們將以一年的時間完成下列子目標 :
(1)在光線追蹤法方面(ray tracing)
•在資料平行化方面:提出動態負載平衡以提高延展性。
•在控制平行化方面:將與系統組配合，以分散式空間結構模擬"分享記憶" 角度，討論控制平行化的加速行為。
•在 PVM 的工作平台上，製作及測試新方法的加速效果，並在高速網路 (如 ATM)上作試，藉以分析系統參數對演算法的影響。
(2)在幅射量計算法方面(radiosity)
•改進過去"主從"的分散式結構而成為"同儕式"(pear-to-pear)結構， 以提高系統的延展性。
•研究階層式幅射成像法之平行化。
•探討非完全散射的平行化。
•在 PVM 上，以實例驗證新方法的加速效果及可行性，並在高速 網路(如 ATM )上作測試，藉以分析系統參數對演算法的影響。
(3)在實體成像方面(volume rendering)
•在規則性實體資料上將整合" 資料平行"(data parallel)與 "影像平行"(image parallel) 以提高可延展性。
•研究非規則性(nonregular)實體資料之平行化成像法。
•研究幾何及布林運算之平行演算法。
•在 PVM 平台上，以實例驗證平行化之加速績效，並在高速網路(如ATM) 上作測試，藉以分析系統參數對演算法的影響。
在 heterogneous distributed 計算環境上的程式規畫比之於 sequential machine 要困難的多。為了鼓勵 user將heterogeneous machines所組成的 machine-clusters 當做parallel machine來使用 ，我們需要更好的系統軟體來減輕使用者在程式規畫上的負擔
。 此研究計劃將建立一系列的系統軟體，提供user 一個parallel programming 環境，並減化parallel程式規化加以programmer的負擔。 我們的工作包括一個由林華君教授所領導的parallel job balancing 系統，李政崑教授領導的一個 parallel C++ compiler (EC++) 計畫， 與金仲達教授在 shared nothing workstation environment 上的 shared memory interface, 黃興燦教授的系統 kernel ，他們提供 了使 parallel programming 更容易的programming tools。
在三年計畫的過去兩年，我們已完成以下的工作。首先 ，我們實作出一個以Ethernet connection 的 8-node DEC workstation Farm 上的shared memory interface. 其次， 我們在nCUBE2 machine與workstation cluster 上發展出 parallel C++ compiler (EC++) 的prototype. 另外，我們也研究 了管理system resources 的dynamically load balancing 系統 。最後，我們也建立PCs 的system kernels 以探討如何將high-end PCs 整合到 high-performance distributed computing environments.
在本計畫中，系統將朝幾個方向加以擴充。首先，以high performance ATM switch 連接的workstation Farm 將做為testbed, 而8-node 的 Dec Farm with ATM switch 的購置用將由本計畫與清華大學共同 支援。我們將應用 ATM switch High-Performance bandwidth 的 technologies 來支援我們需要 high-speed network 的環境。 其次，我們 ATM network 連接下的Dec farm 將與清華大學電通 中心的ATM network連接，這也是國內 NII計畫首要的幾個實驗 性 testbeds 之一。實驗將在ATM switches 連接的workstation clusters 上實驗，理想狀況下，在National Information Highways 上連接的可用workstation clusters 都可在Resource management 的範圍內。初期架構是以ATM switch 連接的Dec Farm 與 SUN cluster，而此兩種clusters 之間亦有ATM connection ，有關將 parallel program partition 到多個workstation clusters環境將是 我們研究的課題。
本年的計畫將包括下列各項。首先，我們將建立一個ATM networks 上的shared memory interface。這將利用 ATM switches 的 communication bandwidth 有效的支援 shared nothing environments 上的shared memory interface。重要的主題也包括有效的支援 ATM switch 上的one-to-one ，one-to-many，以及 many-to-many 的communication libraries。其次，我們將建立一個ATM switch 下 的parallel C++ compiler，這包括利用 ATM switch technology 來支 援languages 與applications 的communication abstractions, 一些 programing style 的refinement，將C++ language extend 到high- performance C++ language 與一些關於multi-ATM clusters 與class- specific 的compiler optimization課題。而當有一個以上的ATM cluster時，我們需要將parallel C++ programs partition 到不同的 clusters。另外，我們將發展出一個在scalable computing environment 上的dynamic load balancing policy 以使system computing resource 得到較佳的利用並改善system performance。而此scalable load balancing policy 是指它能在不相對增加 overhead 下運作一個large-scale系統 。我們也將研究在parallel processing environment上load balancing 的問題。最後，我們將建立high-end PCs 的系統kernels 以將high-ends PCs 整合成high-performance distributed computing environments。 系統kernels 包括communication protocol, task management ，與 P4 interfaces.
我們認為這個發展ATM switch 連接下的heterogeneous computing
environment 之系統軟體的計劃將提供我們關鍵的software components 與computer graphics development
上的實驗性 tested。此外，在三年計畫後，我們將 demo下列工作成果的初期 software environment：
(1)一個workstation環境上的shared memory interface。
(2)一個load-balancing系統。
(3)一個nCUBE2 machine 與workstation cluster 上的實驗性parallel C++ compiler。
(4)在平行 C++ 環境下發展出一個關於three-dimensionally evolving jets 的 parallel vortex methods.此CFD application 使用於 清大動機系，其為N-body問題的一種類型。
(5)一個將PCs整合至high-performance distributed computing environments 上初期 system kernel。