超大型積體電路陣列的切割方法

Abstract

在很多應用方面（如影像處理，數位訊號處理和科學應用等），尤其是在須要處理大 量資料和講求快速運算的應用方面，超大型積體電路陣列（VLSI Array）是一個最有 效，最經濟的選擇。當我們設計超大型積體電路陣列時，切割（Partition） 是一個 非常重要的工作。有很多學者提出陣列的切割方法，我們將之歸納且分為三類：（１ ）Chip切割法，（２）演算切割法（Algorithm Partition）和（３）陣列切割法（ Array Partition）。第一和第二種方法仍有其缺點。第三種方法又可分成（A）在關 係圖（Dependent Graph）上之切割（B）直接在陣列上之切割。在陣列上之切割方法 尚無一套有系統之切割方法，故我們的研究重點乃在於提出一套有系統的切割方法。 在陣列上作切割基本上有兩種方法：（１）合併法（Coalescent）（２）切疊法（ Cut-and-Pile）。根據合併法的基本觀念，我們提出一套有系統的切割方法，且已經 用C 語言在SUN 工作站上面將此套方法寫成程式。它可將任何演算法之陣列切割成任 何較小之陣列，且可作二次投影（Double Projection） 之功能。在程式中，我們也 對切割後的陣列作模擬（Simulation），並求出此陣列的最大計算時間（Latency） 。 除了提出此套有系統的方法之外，我們也討論了切割的一些副作用，包括：降低計算 速度，硬體複雜性的增加與額外的負擔，處理元件（Processing Element）的控制問 題等。至於怎樣的切割方法才可得到最佳的計算速度？我們也推導出此計算時間（ Latency） 的下限。最後我們也討論了用一個固定大小的陣列來模擬（Emulate） 任 何大小陣列的方法。