韻律陣列上對等轉換之一種代數表示法

Abstract

In this research, we propose an algebraic notation for representing and manipulating systolic designs. In the representation part, we use the notation of generating function to represent the data movement through the systolic array. In the manipulation part, we use the transformation matrix T. Various elements in this transformation matrix represent different transformation factors, such as velocity addition, scaling, skewing, rotation, projection, etc.. When T is applied on a systolic design, different but equivalent systolic designs can be derived. Several primitive transformations are defined so that an equivalent transformation T can be composed easily. By using this algebraic model, we present a unified framework in which equivalent systolic designs are related in a systematic way. Various designs of matrix multiplication, LU decomposition, triangular matrix inversion, matrix-vector multiplication, sorting, and convolution problem are derived to illustrate the use of the generation function and its transformations. The performance issues which will influence the design of systolic arrays are also discussed in this research. 在本研究中，我們提出了一種代數表示法，用以表示某一韻律陣列（Systolic Array） 的設計及表示各韻律陣列間之對等（Equivalent）關係。在表示一個韻律陣 列的設計方面，我們利用產生函數（Generating Function） 來代表資料在韻律陣列 間的移動。而在表示各韻律陣列間的對等關係方面，我們使用了對等轉換矩陣（Equi valent Transformation Matrix）T。 在轉換矩陣中的每一個元素都對應一個不同的 轉換因素，例如：速度相加（Velocity Addition）， 尺度變換（Scaling）， 傾斜 （Skewing）， 旋轉（Rotation），投影（Projection）等等。將轉換矩陣作用到韻 律陣列的產生函數上，我們就可以得到另外一個功能對等的韻律陣列。我們定義了一 些基本的轉換矩陣，因此，一個複雜的轉換矩陣可以很容易的由這一些基本的轉換矩 陣所組成。經由此種代數表示法，我們可以很有系統的了解到各種對等韻律陣列間之 關係。 利用上述產生函數及轉換矩陣，我們以矩陣相乘（Matrix Multiplication） ，下三 角形與上三角形矩陣分解（LU Decomposition），三角形矩陣之反矩陣（Triangular Matrix Inversion） ，矩陣向量相乘（Matrix Vector Multiplication），排序（ Sorting）和旋繞（Convolution）等問題為例，推導出一系列對等的韻律陣列。 最後，在本研究中，我們也討論了一些有關影響韻律陣列效能方面（Performance） 的因素。