臺灣博碩士論文加值系統

一個高維均勻相依演算法可由其計算定義域及有限個數資料相依向量所
表示，而且其計算定義域之凸形殼為此高維空間中非退化凸形有限體。在
由均勻相依演算法合成規律陣列的過程中，有兩個主要問題必須解決，即
時間排程問題及處理機分配問題。在本論文中，我們針對具有任意凸形計
算定義域的均勻相依演算法的最佳線性排程問題及空間最佳化線性陣列問
題提出一個一致性方法。我們發現此兩問題等於求符合問題限制之最小長
度的向量，而向量的長度之計算為定義在一個對稱凸形集合上，此對稱凸
形集合可由計算定義域之凸形殼推導出。均勻相依演算法的最佳線性排程
問題定義為尋找一個線性排程向量，使得在此線性排程之下，此均勻相依
演算法之執行時間為最短。我們發現線性排程的時間等於此線性排程向量
之長度。針對此問題，我們提出一個線性規劃方法以求得此最小長度之向
量。此方法之平均計算複雜度經驗值比目前其他方法都要好。均勻相依演
算法的空間最佳化線性陣列問題定義為尋找一個處理機分配向量，使得在
此處理機分配向量之下，所得之線性陣列的處理機個數為最少。我們發現
處理機個數等於此處理機分配向量之長度。由於將演算法正確映射至線性
陣列上的檢查無法表成數學公式，而需要複雜計算程序，因此我們使用列
舉方法以找出此最小長度之向量。此列舉方法是假設在一合法線性排程之
下，求得此空間最佳化線性陣列。基於此列舉方法，我們發展出一個設計
軟體，稱之為 SODTLA ，此設計軟體可由演算法之計算定義域，及其有限
個數資料相依向量，與合法線性排程向量為輸入，自動找出空間最佳化線
性陣列設計，其尋找過程無須使用者之任何協助。由於將高維均勻相依演
算法正確映射至較低維度的處理機陣列 (線性陣列為一維之處理機陣列)
的過程中，必須檢查有無通道相衝問題，所謂通道相衝問題定義為兩相異
資料同時共用處理機間的連接通道。針對此問題，我們也提出一個新方法
以檢查有無通道相衝問題。此方法之計算複雜度比目前其他方法都要好。
此方法已整合在列舉方法中。

A uniform dependence algorithm can be represented by an index
set of index points and a finite set of data dependence vectors.
Usually, the convex hull of the index set is a nondegenerated
convex polytope in n-dimensional real vector space . And, we
call such an algorithm an n-dimensional uniform dependence
algorithm. To synthesize a regular array from the uniform
dependence algorithm, there are two main issues, namely, the
time schedule problem and the processor assignment problem. In
this dissertation, a unified approach is proposed for the
problems to find an optimal linear schedule and a space-optimal
linear array for a uniform dependence algorithm with an
arbitrary bounded convex index set. Both problems are reduced to
the problem of finding a vector of smallest norm (length)
satisfying the constraints of the problems, where the vector
norm is defined on a symmetric convex set (which is derived from
the convex hull of the index set). The optimal linear schedule
problem of a uniform dependence algorithm is to find a linear
schedule vector such that the total execution time of the
algorithm is minimized. It is found that the total execution
time of a linear schedule is related to the norm of the linear
schedule vector. For this problem, a linear programming problem
is derived for finding a vector with smallest norm. Time
complexity analysis shows that the empirical average time
complexity of our method is better than those of the existing
methods. The space-optimal linear array problem of a uniform
dependence algorithm is to find a PE (Processing Element)
allocation vector such that the number of PEs used in the linear
array is minimized. It is founded that the number of PEs used is
related to the norm of the PE allocation vector. Since the
design constraints of the space-optimal linear array problem
usually do not have a closed and linear form, we proposed an
enumeration procedure to find a vector with the smallest norm.
The enumeration procedure finds a space-optimal PE allocation
vector, assuming that a valid linear schedule has been given a
prior. A tool called SODTLA (Space-Optimal Design Tool for
Linear Array) was developed to find a space-optimal PE
allocation vector without the user''s intervention. To be used in
the enumeration procedure, a method is also proposed to check
the link conflicts in the mapping of n-dimensional uniform
dependence algorithms into lower dimensional processor arrays,
i.e., a k-dimensional processor arrays with 0 < k < n-1. Time
complexity estimation shows that our method to check link
conflicts has better performance than previous methods. 1

Cover
Abstract (in Chinese)
Abstract (in English)
Acknowledgments
Contents
List of Tables
List of Figures
List of Symbols
1 Introduction
1.1 Space-time Mapping
1.2 Optimization Criteria for Arbitrary Bounded Convex Index Sets
1.3 Our Approach
1.4 Organization of the Dissertation
2 Preliminaries
2.1 Uniform Dependence Algorithms
2.2 Norm and Distance Frnction
3 Optimal Linear Schedule for Arbitrary Bounded Convex Index Set
3.1 Introduction
3.2 Formulation for the Optimal Linear Schedule Problem
3.3 Distance Function and Optimal Linear Schedule
3.4 Finding an Optimal Linear Schedule
3.5 Time Complexity Analysis
4 Checking Link Conflicts
4.1 Introduction
4.2 Algorithm Model and Array Model
4.3 Formulation of the Link Conflict Checking Problem
4.4 Checking Link Conflicts
4.5 Time Complexity Estimation
5 Space-Optimal Linear Array for Arbitrary Bornded Convex Indes Set
5.1 introduction
5.2 Formulation of the Space-Optimal Linear Array Problem
5.3 Distance Function and PE Allocation Vector
5.4 Finding an Optimal Allocation Vector
6 Conclusion and Future Research Directions
Bibliography
Appendix A
Vita