演算法映對到線性陣列的系統方法之研究

Abstract

本論文提出一演算法映對到線性陣列的新方法。首先，我們用有方向的非 循環(Directed Acyclic Graph, DAG)來表示一演算法中每個計算間的 相依關係，在圖中的每一個點(vertex)代表此一演算法的一個陳述(sta- tement)，而連接任何兩個點的邊(Arc)表示資料的流向。我們以圖形排序 法(topological sorting)把此圖形的點分成數個擁有不同點的集合，在 同一集合中的點必須指定到不同的處理單元(processing element)，而 被任一邊連接的兩個點應指定到儘可 能接近的處理單元。在本論文中所 舉用的例子包含了帶狀矩陣與向量相乘(band-matrix and vector multiplica- tion)、迴旋問題(convolution problem)、排序(sorting) 、矩陣相乘(ma- trix multiplication)和動態規劃問題(dynamic programming program)。我們所設計用來解決帶狀矩陣與向量相乘、迴旋 問題與排序的線性陣列所用的處理單元只有Ramakrishnan所用的處理單元 的一半，但是所需要的處理時間是一樣的。若用來解決矩陣相乘的線性陣 列在每個處理單元具有n個記憶體大小，或 是連接相鄰處理單元的管道( channel)中有一管道的時間延遲為n-1時間步驟(time steps)的情況下， 我們所設計出的線性陣列比文獻有較好的結果，即是用較少的處理元或是 需要較短的處理時間。除此之外，用來解決動態規劃問題的線性陣列，其 連皆相鄰處理單元的管道的時間延遲與問題的大小無關，因此我們很容易 以固定大小的線性陣列來解決任意大的問題。 In this thesis, we present a novel to mapping algorithms onto linear arrays. First, we use directed acyclic graphs(DAGs) to represent the computation dependence of algorithms. The vertices in a DAG denote statements of an algorithm and an arc between a pair of vertices denotes the data flow. We partition the vertices of the DAG into a group of sets by topological sorting, and the vertices in each set are assigned to different processing elements(PEs). Two dependence vertices should be assigned to PEs whose distance is as near as possible. Design examples are also described in this thesis including multiplication of band-matrix and vector, convolution problem, sorting, matrix multiplication, and dynamic programming problem. Our linear arrays for sorting, band-matrix and vector multiplication, and convolution problem require only half the number of PEs used by Ramakrishnan's designs, while the computation time is the same. If each PE in the linear array has local memory of size n or has n-1 shift registers in a channel, the linear array designed for matrix multiplication are better than previous results. The time delay of the channels does not depend on the problem size in the linear array designed for the optimal parenthesization problem using dynamic programming approach. As a result, we can solve the dynamic programming problem using fixed size linear array independent of the problem size by partitioning the problem.