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

Abstract

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