可程式邏輯陣列中輸入變數配對與輸出相位指定之研究

Abstract

在超大型積體電路系統的設計上面積小、速度快、功率低是電路設計的目標。為了使 可程式邏輯陣列的設計能滿足這些需求，有許多運算法則被用來輔助可程式邏輯陣列 的設計。這些法則包括邏輯化簡、摺疊、函數分割及其它改變電路結構等。本論文的 主題即探討兩種進行可程式邏輯陣列最佳化的方法 - 輸入變數配對與輸出相位指定 。 輸入變數配對的方法是基於解碼式可程式邏輯陣列的結構，在輸入部分使用二個輸入 的四值解碼器作字元解碼。利用這種結構平均可降低百分之五十的陣列面積。而對於 解碼器的輸入而言，不同輸入變數的組合會影響最佳化的程度，因此，必需慎選法則 以進行輸入變數的組配。目前進行輸入變數配對的方法為對n 個輸入變數逐一檢查兩 兩變數間的積項關聯性，同時藉以建立一含n 個節點的輸入變數指定圖，最後利用對 指定圖的分割即可完成輸入變數的配對。為了減少進行輸入變數配對所需的時間，在 論文的研究中，我們利用了兩兩積項間變數差異的檢驗來進行變數指定圖的建立。經 由這項修改可使得產生指定圖的計算複雜度對輸入變數數目的相關性降低一階。就實 際時間而言平均使得進行輸入變數配對的速度增快145 倍，而不影響輸入變數配對的 結果。 除了改變輸入部分之組態外，在輸出部分使用不同的函數輸出相位也可降低可程式邏 輯陣列所需的面積，而為了避免原有進行輸出相位選擇方法中，使用雙相位函數化簡 步驟所引起速度慢、記憶體需求量大的缺點，因此，我們提出一套新的方法來進行輸 出相位的指定。對於一含m 個輸出的函數而言，在這個方法中，針對化簡後的函數正 輸出及函數互補輸出，我們利用了一些規則來檢查函數相位間積項的共用情形。基於 這些檢查結果可形成一個大小為２m ＊２m 的矩陣，這個矩陣我們稱之為輸出相位關 係矩陣。在這個矩陣中包含各個輸出相位所需的積項數，以及各輸出相位間的積項相 關程度。利用這個矩陣可估計出各種相位組合輸出所需的積項數，而輸出相位之指定 即根據這些估計值，選擇最有可能達到最佳化的相位組合，最後再化簡相位選擇後之 混合相位輸出函數即完成輸出相位指定最佳化之步驟。由實際之執行結果顯示，利用 新的法則可比目前最快的方法節省百分之四十六的時間，同時獲得較佳的結果。 綜合以上兩種方法實行可程式邏輯陣列的最佳化，平均而言可節省百分之三十六的面 積，而最多可減少百分之八十一的面積。