平行字首計算及其在卜松數產生之應用

Abstract

本論文目的在於研究平行字首計算及其應用。從西元 1980 年以來，平行 字首計算受到學術界人士廣泛地研究討論。在本博士論文中，研究焦點是 在討論一些陣列處理機，如：完全圖、超方塊、樹與2-MCCMB 等架構上之 平行字首計算問題。首先，我們研究歸納傳統結合性字首計算的演算法。 然後，我們提出一個新模組：非結合性平行字首計算。二元運算的結合性 具有許多應用，倘若沒有結合性，這些應用將會變成不可能實現。所以， 我們提出一個轉換二元運算式為具有結合性的二元運算式的方法，然後藉 由使用結合性字首計算的演算法，以計算出所有的非結合性的字首。在本 論文中，並提出兩個非結合性字首計算的應用範例，即為：線性遞迴關係 式與進位前瞻加法。除了非結合性字首計算之外，本論文中還提出一些產 生卜松數亂數的平行演算法。卜松亂數產生器的設計是基於卜松過程與字 首計算的理論。我們所設計出來的平行卜松數產生器的時間複雜度為 O( [k/N]*T) ，此處 k 為卜松數的產生過程中所需之均勻亂數的個數，N 是 陣列處理機的處理機總數，T 是平行字首計算的演算法時間複雜度，以及 [x] 則代表大於或等於x 的最小整數。比較我們設計的平行卜松數產生器 演算法與傳統循序卜松產生器演算法，可以發現平行卜松數產生器的時間 複雜度遠低於循序卜松產生器。這樣將會大為加速卜松數產生的效益。 In this dissertation, we study parallel prefix computation and its applications. Parallel prefix computation has been widely discussed since 1980. Here, we focus on prefix computation on some array processors such as complete graphs, hypercubes, trees, and 2-MCCMB's. First, we propose a new model: non- associative prefix computation. Associativity of a binary operation allows many applications that are not possible with a non-associative binary operation. So we propose a method to transform a binary expression into an associative one, then compute prefixes by using associative prefix computation. Two applications about non-associative prefix computation are also presented: linear recurrences and carry-lookahead addition. Besides non-associative prefix computation, we also propose parallel algorithms to generate Poisson random numbers. The design of Poisson generators are based on the theory of Poisson process and prefix computation. The time complexity of each generator is O([k/N]*T), where k is the number of uniform random numbers used during the generation of the required Poisson numbers, N is the number of processors, T is the time complexity of parallel prefix computation, and [x] represents the minimal integer >= x.