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

Abstract

在本研究中，我們提出了一種代數表示法，用以表示某一韻律陣列(Systolic Array) 的設計及表示各韻律陣列間之對等(Equivalent)關係。在表示一個韻律陣列的設計方 面，我們利用產生函數(Generating Function) 來代表資料在韻律陣列間的移動。而 在表示各韻律陣列間的對等關係方面，我們使用了對等轉換矩陣(Equivalent Trans- formation Matrix) T 。在轉換矩陣中的每一個元素都對應一個不同的轉換因素，例 如：速度相加 (Velocity Addition), 尺度變換 (Scaling), 傾斜 (Skewing), 旋轉 (Rotation), 投影 (Projection) 等等。將轉換矩陣作用到韻律陣列的產生函數上， 我們就可以得到另外一個功能對等的韻律陣列。我們定義了一些基本的轉換矩陣，因 此，一個複雜的轉換矩陣可以很容易的由這一些基本的轉換矩陣所組成。經由此種代 數表示法，我們可以很有系統的了解到各種對等韻律陣列間之關係。 利用上述產生函數及轉換矩陣，我們以矩陣相乘(Matrix Multiplication) ，下三角 形與上三角形矩陣分解(LU Decomposition), 三角形矩陣之反矩陣 (Triangular Ma- trix lnversion)， 矩陣向量相乘(Matrix Vector Multiplication)，排序(sorting )(Convolution)和旋繞(Convolution) 等問題為例，推導出一系列對等的韻律陣列。 最後，在本研究中，我們也討論了一些有關影響韻律陣列效能方面(Performance )的 因素。