臺灣博碩士論文加值系統

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

CONTENTS
Abstract(in Chinese)
Abstract
Acknowledgements
List of Figures
List of Algorithms
List of Tables
List of Symbols
Chapter 1 Introduction
1.1 Overview of Some design methods
1.2 The proposed approach
1.3 Outline of the thesis
Chapter 2 Systolic Arrays and Systolic Algorithms
2.1 the general method to solve problems
2.2 Programming paralled computers
2.3 Parallel algorithm and parallel processors
2.4 Systolic array
2.5 Systolic algorithm
2.6 Verifications of systolic algorithms
Chapter 3 Computational Model of Systolic arrays
3.1 A computational model of systolic arrays
3.2 Another description of CMSA with message transmission
3.3 A procedure for designing systolic algorithms
3.4 Discussions
Chapter 4 Systolic Algorithms for Representative Problems
4.1 Prefix computation
4.2 the sorter
4.3 Correlation evaluation
4.4 Polynomial division
4.5 Longest common subsequence
4.6 Palindrome recognizer
4.7 Multiplication of polynomials
4.8 First design on generation of combinations
4.9 Second design on generation of combinations
Chapter 5 A Systolic Design for Generating Combinations
5.1 Overview of algorithms for generationg combinations
5.2 design of the systolic array
5.3 The parallel algorith
5.4 The proof of correctness
5.5 Illustrative examples
5.6 Discussions
Chapter 6 Second Systolic Design for Generating Combinations
6.1 The computational model
6.2 Parallel algorithm for generation combinations
6.3 The illustrative examples
6.4 The correctness proof
6.5 Discussions
Chapter 7 A Systolic algorithm for Dynamic Programming
7.1 deriving the systolic algorithm
7.2 The systolic algorithm and an illustrative example
7.3 An illustrative example
7.4 the correctness proof
7.5 discussions
Chapter 8 An Mapping Procedure onto VLSI Array Processors
8.1 An alternative mapping procedure
8.2 The nest-loop problem
8.3 the dynamic programming problem
Chapter 9 Conclusions
9.1 Summary
9.2 Discussions
9.3 Future works
References
Appendix
Biographical Sketch