傳統的計算機系統都是循序的（sequential）。這類的系統最基礎的架構就是泛紐曼
架構（Von Neuman Architecture） 。一個循序的泛紐曼架構有一些物理上的限制，
目前的計算機技術已經快要達到這個極限，所以很難再提升計算機的處理能力。另一
方面，由於積體電路製造技術的進步及硬體價格的急遽下降，使得平行處理（parall
ell processing）成為目前及未來最主要的發展趨勢。
平行處理在硬體上的發展已日漸成熟。因此，軟體上平行計算方法的設計也日漸重要
。雖然目前在文獻上已有許多平行計算方法可用以解決許多問題，但大多數是根據問
題的特性來設計這些平行計算方法。因此，每一個平行計算方法，只能用來解決一種
問題。另外有些學者專家，提出了一些有系統的平行計算方法設計步驟。根據這些步
驟，可以很輕易地設計出許多問題的平行計算方法。
在許多有系統的平行計算方法設計步驟中，我們有興趣的是以圖形理論為主的設計步
驟。這類的設計步驟，道先針對給定的問題尋找一個解法。在解法的過程中，會產生
一些中繼值。而這些中繼值彼此之間有先後相關的關係，根據這些關係，可以畫出資
料相關圖。中繼值構成資料相關圖的結構（vertex），而它們的相關關係構成了資料
相關圖的有向連結線（directed link）。 最後，將資料相關圖對映到平行架構（
parallel architecture） 上。
本論文討論兩種資料相關圖，分別是規則圖（regular graph） 和半規則圖（semi-
regular graph） 。在規則圖方面，以往的文獻所提的方法只能解決三個變數以下的
問題，對於三個變數以上的問題，雖然也可以解決，但是，是對映到一個無法製造出
來的平行架構上。這是不實際的。本論文將提出一種方法能夠解決有多個變數的問題
，設計出的平行計算方法，可以對映到實際的平行，較以往的設計方法所設計的更有
效率。
|