建構於旅行推銷員問題模型上之可重組態單電子電晶體合成技術

Abstract

隨著製程不斷地演進，功率消耗(power dissipation)對於電子電路與系統設計而言是一個重要的問題，而漏洩功率(leakage power)已逐漸成為功率消耗的主要來源。由於可重組態單電子電晶體陣列(reconfigurable single-electron transistor array)的超低功率消耗特性，已經被視為有希望延伸摩爾定律(Moore's Law)的元件之一。近幾年發展出了許多針對可重組態單電子電晶體陣列的自動化映射(automated mapping)方法。然而，現存的這些方法所提出的積項排序(product term ordering)演算法只能做到局部最佳化，可能與全局最佳化的結果有所差距。本篇論文歸納出兩兩積項之間若比鄰映射時,對於可重組態單電子電晶體陣列寬度的影響，並計算映射時所需的寬度成本。此外，本篇論文提出的積項排序演算法可以建構在旅行推銷員問題(Traveling Salesman Problem)的模型上，達到全局最佳化的目的。實驗結果顯示，與現存的方法比較，我們所提出的方法能將陣列寬度進一步減少 14% 至 31%。

Power dissipation has become a crucial issue for most electronic circuit and system designs nowadays since fabrication processes exploit even deeper submicron technology. More specifically, leakage power is now a dominant source of power consumption. The reconfigurable single-electron transistor (SET) array has been presented as an emerging circuit architecture for continuing Moore's Law due to its ultra-low power consumption. In the past few years, several automated synthesis approaches have been developed for the reconfigurable SET array. Nevertheless, all of those existing methods use simple heuristic to determine the ordering of product terms locally, which may potentially lead the outcomes away from the global optimal solutions. In this paper, we first identify the relationship of width cost between two product terms while mapping them side-by-side onto a SET array. We then model the product term reordering for SET array width minimization problem as the traveling salesman problem (TSP). Experimental results show that our new algorithm can achieve an area reduction of up to 14% as compared to current state-of-the-art SET synthesis techniques.