心縮陣列與其資料流模型

Abstract

在本論文中，用包含幾束不同波前的資料流的一個表示式來描述規則遞迴計算則。這 種形式是將資料流動塑成指數級數的產生函數，並且聯結到吾人熟知的幾何表示式， 亦即所謂的相依圖形。根據這種觀，在相依圖形上的轉換可視為資料流速的轉移。心 縮計算法則與其陣列之主要特性皆顯露於單一的資料流表示式。它完整地結合原先發 展於相依圖形上的理論與技術，並且非常簡潔。這些優點將在一個結合兩已有心縮陣 列的例子中表現出來，它使結合的條件變得直接。 為了避免在心縮陣列中直接傳送控制信號，吾人沿續上述觀點將標簽粘貼於資料流的 資料上，用以指定處理元的動作。吾人考慮為標簽粘貼所須的位元數目最小化問題， 首先證明這樣一個問題要得到最小解是ＮＰ－Ｃｏｍｐｌｅｔｅ。因而將此問題寫成 如微程式中的控制記憶體最小化問題，在相依圖形上定義類似的最大包容義（ＭＣＣ ），列含蓋表，並縮減它。結果是得到一個適合ＶＬＳＩ，製做的全同的處理元。接 著討論在多維結構下的時間複雜度，吾人給予一個與輸入長度，輸出長度，計算長度 及處理元數目有關的下限。然後提出一個藉由線性運算子的結合性質與交換性質的分 解方法，來對應心縮計算法則到一個較高維的陣列設立上去。這使得單一資料通過陣 列的時間大幅減少，並且不增加處理元的數目。