應用於可重構式單電子電晶體陣列之合成技術

Abstract

對於奈米層級的電子電路與系統設計而言，功率消散(power dissipation)已經成為一個重要的問題，特別是漏洩功率(leakage power)已經逐漸成為功率消耗的主要來源。近年來各式元件相繼被提出以解決此議題，而單電子電晶體(single-electron transistor)因具有在室溫下之顯著超低功率消耗特性，而成為可望取代傳統電晶體以延續莫爾定律的元件之一。本論文將針對主流單電子電晶體電路架構──可重構式單電子電晶體陣列(reconfigurable single-electron transistor array)上之合成技術做一完整討論。 近來，許多針對可重構單電子電晶體陣列之自動化合成技術陸續被提出，其有幾個主要的考量因素：製程限制、乘積項順序(product term ordering)、控制變數順序(control variable ordering)、乘積項數量及陣列原生瑕疵(defect)的影響。可重構式單電子電晶體陣列的架構類似於二元決策圖(binary decision diagram)，因此其上的合成技術亦多基於此架構發展，藉由調整控制變數順序及乘積項合成順序來最大化共用的機會並降低合成面積。過去被提出的自動化合成演算法皆僅考慮相近乘積項之相互影響，也因此其合成結果常囿於局部最佳解而無法達到全局最佳解。另一方面，由於單電子電晶體的元件尺度較小，在製程中往往無可避免的產生瑕疵而使得合成之電路無法正常運作。然而，絕大多數的自動化合成技術均未考慮此元件瑕疵議題，也因此這些合成演算法難以運用於實際電路。本論文提出一系列的合成技術，藉以解決上述之問題。 本論文第一部分(第二章)，針對可重構式單電子電晶體陣列，提出具製程限制感知的控制變數排序演算法以及動態的乘積項排序演算法來解決電路合成的問題。實驗結果證明，本論文所開發之演算法較現有方法能減少合成的陣列寬度達18%。 論文第二部分(第三章)同樣基於可重構單電子電晶體陣列架構，但討論主軸為發掘乘積項排序演算法的全局最佳解。我們所提出之演算法可將乘積項排序問題轉化成旅行推銷員問題(Traveling Salesman Problem。如此一來便可應用已成熟發展之旅行推銷員問題演算法來達到全局最佳化的目的。實驗結果證明本文所述之演算法與現有之演算法相較能將合成所需的陣列寬度進一步減少14%。 最後，本論文第三部分(第四章)則討論陣列原生瑕疵(defect)對合成演算法的影響。我們所提出的瑕疵感知合成演算法能在合成過程中考量瑕疵的位置及種類，並用以挑選適合的乘積項來合成以使面積最小化。在部份情況下，我們所提出的演算法甚至能巧妙的利用這些原生瑕疵的特性來使得合成面積較無瑕疵的情況下更小。根據實驗結果，本論文提出的演算法較現有瑕疵感知合成演算法能進一步降低15％的合成面積。

Power dissipation has become a crucial issue for most nanoscale electronic circuit and system designs. More specifically, leakage power is now a dominant source of power consumption. Several nano devices have been developed to deal with this issue. Among them, the reconfigurable single-electron transistor (SET) array has been regarded as an emerging circuit architecture for continuing Moore's Law due to its ultra-low power consumption at room temperature. As a result, this dissertation mainly addresses the area minimization synthesis techniques for reconfigurable single-electron transistor array architecture. In the past few years, several automated synthesis approaches have been developed for the reconfigurable SET array. There are three key factors in the synthesis process: product term ordering, control variable ordering, and defects of SET array. A binary decision diagram (BDD) based logic structure has been proposed as a feasible approach for realizing logic functions using SETs. Therefore, most of the existing methods focus on how to reorder variables and product terms during SET mapping to reduce the mapped area. However, 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. Meanwhile, the SET devices suffer from the low yield issue due to the high defect rate of nanowire segments. Nevertheless, very few works consider the effect of faulty devices. Hence, the mapping result expected in synthesis stages may not be correctly mapped onto a faulty SET array. This dissertation presents a series of synthesis technologies for reconfigurable single-electron transistor arrays to tackle these issues. In Part I of this dissertation (Chapter 2), a constraint-aware control variable ordering and dynamic product term ordering algorithm is presented to tackle the synthesis problem on reconfigurable SET array. According to the experimental results, the proposed algorithm can improve the width of circuit up to 18% as compared with previous arts. Part II of this dissertation (Chapter 3) focuses on global area minimization synthesis. We propose a new synthesis algorithm by modeling the product term reordering problem as the traveling salesman problem (TSP). In such way, state-of-the-art TSP solvers can be applied to get a better solution to the original ordering problem. Experimental results show that the proposed method can achieve an area reduction of up to 14% as compared to the current state-of-the-art techniques. Finally, the issue of defects of reconfigurable SET array is addressed in Part III (Chapter 4). The proposed synthesis algorithm is aware of fault types and fault locations. Furthermore, the technique can even take benefit from the faults to further reduce the mapping area. In some cases, the mapping area in a faulty SET array can be smaller than the area in a fault-free array. The experimental results show that our approach can handle moderately large circuits in a reasonable runtime and reduce 15% of width compared to the prior art.