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.

In this paper, we present the condition for the effective wire addition in Look-Up-Table-based (LUT-based) field programmable gate array (FPGA) circuits, and an optimization procedure utilizing the effective wire addition. Each wire has different characteristics, such as delay and power dissipation. Therefore, the replacement of one critical wire for the circuit performance with many non-critical ones, i.e., many-addition-for-one-removal (m-for-1) is sufficiently useful. However, the conventional logic optimization methods based on sets of pairs of functions to be distinguished (SPFDs) for LUT-based FPGA circuits do not make use of the m-for-1 manipulation, and perform only simple replacement and removal, i.e., the one-addition-for-one-removal (1-for-1) manipulation and the no-addition-for-one-removal (0-for-1) manipulation, respectively. Since each LUT can realize an arbitrary internal function with respect to a specified number of input variables, there is no sufficient condition at the logic design level for simple wire addition. Moreover, in general, simple addition of a wire has no effects for removal of another wire, and it is important to derive the condition for non-simple and effective wire addition. We found the SPFD-based condition that wire addition is likely to make another wire redundant or replaceable, and developed an optimization procedure utilizing this effective wire addition. According to the experimental results, when we focused on the delay reduction of LUT-based FPGA circuits, our method reduced the delay by 24.2% from the initial circuits, while the conventional SPFD-based logic optimization and the enhanced global rewiring reduced it by 14.2% and 18.0%, respectively. Thus, our method presented in this paper is sufficiently practical, and is expected to improve the circuit performance.

FPGA-based hardware emulators are often used for the verification of LSI functions. They generally have dedicated external memories, such as SDRAMs, to compensate for the lack of memory capacity in FPGAs. In such a case, access between the FPGAs and the dedicated external memory may represent a major bottleneck with respect to emulation speed since the dedicated external memory may have to emulate a large number of memory blocks. In this paper, we propose three methods, "Dynamic Clock Control (DCC)," "Memory Mapping Optimization (MMO)," and "Efficient Access Scheduling (EAS)," to avoid this bottleneck. DCC controls an emulation clock dynamically in accord with the number of memory accesses within one emulation clock cycle. EAS optimizes the ordering of memory access to the dedicated external memory, and MMO optimizes the arrangement of the dedicated external memory addresses to which respective memories will be emulated. With them, emulation speed can be made 29.0 times faster, as evaluated in actual LSI emulations.