Super-Set of Permissible Functions and Its Application to the Transduction Method(Logic Synthesis)(<Special Section>VLSI Design and CAD Algorithms)
スポンサーリンク
概要
- 論文の詳細を見る
The Transduction Method is a powerful way to design logic circuits, utilizing already existing circuits. A set of permissible functions (SPF) plays an essential role in such circuit transformation/reduction, and is computed at each point (connection or gate output). Currently, two types of SPFs have been used: the maximum SPFs (MSPFs) and compatible SPFs (CSPFs). At each point, the MSPF is literally the set of all PF's, and CSPF is a subset of the MSPF. When CSPFs are calculated, priorities are first assigned to all gates in the circuit. Based on the priorities, it is decided which subset is to be selected as the CSPF. The quality of the results depends on the priorities. In this paper, the concept of super-sets of permissible functions (SSPFs) is introduced to reduce the effect of the priorities that CSPFs depend on. In order to loosen the dependency, each SSPF is computed to contain CSPFs which are candidates to be selected. The experimental results show that the SSPF-based Transduction Method has intermediate reduction capability and takes an intermediate computation time between the MSPF-based and CSPF-based ones. The capability and the time are considered as an acceptably good trade-off. In addition, without any transformations, since SSPFs are the maximum super-set, SSPFs are applicable for analyzing the maximum performance of the CSPF-based transformation, for comparison with the MSPF-based one. Theoretically, the number of connectable gate pairs detected by the MSPFs is 100%. According to the experimental results obtained using SSPFs, on average, 99% are detectable by SSPFs and 1% are detectable only by using the MSPFs. The results show that by using CSPFs, 72% of connectable gate pairs are detectable with any priority assignment and 99% (SSPFs capability) are detectable on average even when the best priorities are assigned. According to the experimental results of CSPF calculation with five priorities, 82% to 93% are practically detectable on average. This is the first quantitative analysis realized by SSPFs which compares the CSPF-based and MSPF-based Transduction Methods with respect to the coverage of PF's.
- 社団法人電子情報通信学会の論文
- 2004-12-01
著者
-
Kambayashi Yahiko
Graduate School Of Informatics Kyoto University
-
TANAKA Katsunori
Graduate School of Informatics, Kyoto University
-
Tanaka Katsunori
Graduate School Of Informatics Kyoto University
関連論文
- Super-Set of Permissible Functions and Its Application to the Transduction Method(Logic Synthesis)(VLSI Design and CAD Algorithms)
- SPFD-Based Flexible Transformation of LUT-Based FPGA Circuits(VLSI Design Technology and CAD)