韻律演算法的設計方式

Abstract

韻律演算法是一種平行演算法，也是目前的研究課題之一。由於此種演算法讓資料在 處理單元間的輸出輸入很有規律性，而且只允許相鄰的處理單元才能互相傳送信息， 故所得到的設計結果非常適伓超大型積體電路的製作。 設計韻律演算法的三個主要考慮因素可歸納為：處理單元的位置安排，每個處理單元 的功能，以及證明此演算法的正確性。 在此論文中，首先我們提出一個設計程序來設計一個線性陣列上的韻律演算法。此種 設計方式也可以被用來設計某些二唯陣列上的韻律演算法。當一個演算法被提出後， 其正確性將加以詳細的證明。然後我們使用這個設計程序來設計一些問題的韻律演算 法。其中包括了兩個組合產生器（產生由ｎ個元素取出ｍ個元素的所有組合數）與動 態程式問題的韻律演算法。前者的計算模式是線性陣列，後者則為二唯陣列。這三個 演算法所需要的處理單元個數分別為：ｎ，ｎ，和（ｎ＊ｎ＋２＊ｎ－４）／４；所 使用的執行時間單位分別是２＊〔Ｃ（ｎ，ｍ）〕＋（ｍ－１），Ｃ（ｎ，ｍ），和 ２＊ｎ－３。其中Ｃ＊ｎ，ｍ）表示組合數〔ｎ！／（ｍ！＊（ｎ－ｍ）！〕。在數 學歸納法的應用下，這三個韻律演算的正確性得到很嚴格的證明。 這個設計程序的特點有：〔１〕、直接分析問題的特性，從中擷取可以平行處理的部 分來探討。〔２〕、考慮了計算模式中的控制傳輸線與控制信號。〔３〕、設計結果 是正規的韻律演算法，即每個處理單元的功能都是可執行的指令。〔４〕、對問題的 設計程序充分瞭解後，在數學歸納原理的幫助下，演算法正確性的推導就顯得比較自 然些。