Theoretical bounds for switching activity analysis in finite-statemachines

The objective of this paper is to provide lower and upper bounds for the switching activity on the state lines in finite state machines (FSMs). Using a Markov chain model for the behavior of the FSM states, we derive theoretical bounds for the average Hamming distance on the state lines which are valid irrespective of the state encoding used in the final implementation. Such lower and upper bounds, in addition to providing a target for any state assignment algorithm, can also be used as parameters in a high-level power model and thus provide an early indication about the performance limits of the target FSM     

Genetic algorithm-based FSM synthesis with area-power trade-offs

Traditionally, state-encoding strategies targeting minimization of area, dynamic power or a combination of them have been utilized in finite state machine (FSM) synthesis. With drastic scaling down of devices at recent technology level, leakage power has also become an important design parameter to be considered during synthesis. A genetic algorithm-based state encoding, targeting area and power minimized FSM, has been proposed in this paper. A unified technique to reduce both static power (leakage) and dynamic power along with area trade-off has been carried out for FSM synthesis, targeting static CMOS NAND-NAND PLA, dynamic CMOS NOR-NOR PLA and pseudo-NMOS NOR-NOR PLA implementations. Suitable weights for area, leakage power and dynamic power to minimize power density have also been explored. Simulation with MCNC benchmarks shows an average improvement of 31%, 26% and 29% in leakage power consumption, dynamic power consumption and area requirement respectively, over NOVA-based state assignment technique in case of dynamic CMOS PLA implementation. Improvements of 30% in leakage power and 15% in area have been obtained for pseudo-NMOS PLA implementation. For the static CMOS case, the improvements are about 29% in leakage power consumption, 14% in dynamic power consumption and 18% in area requirement.     

Power/area/delay aware FSM synthesis and optimization

In this paper, we present novel state minimization and state assignment techniques to synthesize Finite State Machines (FSMs) including novel state minimization and state assignment to optimize power, area, and delay in designing sequential circuits for future low power system application such as cell phones, PDAs, etc. The goal is to reduce the number of gates and literals relevant to power and area, and furthermore to shorten the critical-path delay in FSM simultaneously. In the first step, we try to target the optimal solution for state minimization in efficiency by applying (i) the technique of binary-tree algorithm, heuristic algorithm (or ILP model) to determine the minimized groups covering all state variables where these groups are allocated at different Riversides (here, Shiue's River is introduced for readers to understand easily), (ii) the technique of edge-identification algorithm to determine the edges and impossible edges, which help targeting the solution at lower bound, (iii) Boolean Expression Effects due to alternative ways of minimized states, such that the required number of flip-flops is minimum for completely (or incompletely) specified state tables. Next, our novel state assignment techniques consisting of (i) edge-covering algorithm, (ii) block-reordering algorithm, (iii) cost calculation, (iv) ping-pong gray-codes assignment, and (iv) design space exploration, are developed to target the best state assignment. Espresso is then run to determine the Boolean expressions and choose the best state assignment with the minimal sum-of-product (SOP) terms and literals. Finally, the performance metrics in power, area, and delay are calculated based on the developed cell libraries for those optimal solutions having the same number of terms and literals. Our solutions provide engineers and designers to choose the best state assignment having less power, area, and delay to meet their system specification. Our experiments show that our approach results in quarter reduction (≈25%) in power, area, and delay, respectively, for FSM MCNC benchmarks.     

State assignment in finite state machines for minimal switchingpower consumption

A state assignment algorithm for minimal switching power consumption is proposed. It minimises the switching activity caused by state transitions by assigning codes closer in Hamming distance to the states with higher state transition probabilities. Experimental results show that the switching activity obtained by the proposed algorithm is, on the average, ~45% less than that of NOVA with only a ~3% increase in the number of product terms     

Information-theoretic bounds on average signal transition activity[VLSI systems]

Transitions on high-capacitance buses in very large scale integration systems result in considerable system power dissipation. Therefore, various coding schemes have been proposed in the literature to encode the input signal in order to reduce the number of transitions. In this paper, we derive lower and upper bounds on the average signal transition activity via an information-theoretic approach, in which symbols generated by a process (possibly correlated) with entropy rate H are coded with an average of R bits per symbol. The bounds are asymptotically achievable if the process is stationary and ergodic. We also present a coding algorithm based on the Lempel-Ziv data-compression algorithm to achieve the bounds. Bounds are also obtained on the expected number of ones (or zeros). These results are applied to determine the activity-reducing efficiency of different coding algorithms such as, entropy coding, transition signaling, and bus-invert coding, and determine the lower bound on the power-delay product given H and R. Two examples are provided where transition activity within 4% and 9% of the lower bound is achieved when blocks of eight symbols and 13 symbols, respectively, are coded at a time     

State assignment of finite state machines for low powerapplications

The authors present an algorithm for the state assignment in finite state machines targeted for minimal switching power dissipation. The adjacent states are assigned codes closer in Hamming distance by our algorithm, which modifies the given state transition graph so that it can be embedded in an n-cube. Experimental results show that the switching activity obtained by the proposed method is better than the previous method     

FsmTest: Functional test generation for sequential circuits

This paper presents a new approach to test pattern generation for sequential circuits modeled as finite state machines. This approach is well suited for controller synthesis, because such devices are usually represented as explicit finite state machines. Based on a functional fault model, only a restricted set of transitions of the finite state machine (FSM) is considered for the purpose of testing. A new state discriminating sequence, referred to as EUIO is proposed. Overlapping is accomplished to reduce the test length. In most cases, test length and CPU time requirements are substantially lower compared with gate-level ATPGs. Techniques are also introduced to preserve a high fault coverage. Evaluation on MCNC benchmarks has shown the effectiveness of the test algorithm both at functional and gate levels, while achieving in most cases 100% coverage of single stuck-at faults.     

Power optimization algorithm based on XNOR/OR logic

Based on the investigation of the XNOR/OR logical expression and the propagation algorithm of signal probability, a low power synthesis algorithm based on the XNOR/OR logic is proposed in this paper. The proposed algorithm has been implemented with C language. Fourteen Microelectronics Center North Carolina (MCNC) benchmarks are tested, and the results show that the proposed algorithm not only significantly reduces the average power consumption up to 27% without area and delay compensations, but also makes the runtime shorter.     

Changes in the length of internal state codes with the aim at minimizing the power consumption of finite-state machines

Two heuristic techniques intended to encode the finite-state machine (FSM) internal states with the aim at decreasing the power consumption have been discussed. In the first approach, internal state codes are assumed to have the constant length. The second approach is based on code lengths varying from the minimum value to the level not leading to a decrease in power consumption. It is demonstrated that the second technique has a low computational complexity, making it possible to use FSMs with a large number of states. It has been ascertained experimentally that the FSM consumed power inherent to the NOVA algorithm can be decreased by 39% on the average (or by 68% with the use of certain benchmarks) via the first technique. In several cases, the second approach enables us to diminish the consumed power by 34% in comparison with the first one. Practical recommendations for the use of each technique, as well as the promising directions of further investigations, are presented.     

A Kernel‐Based Partitioning Algorithm for Low‐Power,Low‐Area Overhead Circuit Design Using Don't‐Care Sets

This letter proposes an efficient kernel‐based partitioning algorithm for reducing area and power dissipation in combinational circuit designs using don't‐care sets. The proposed algorithm decreases power dissipation by partitioning a given circuit using a kernel extracted from the logic. The proposed algorithm also reduces the area overhead by minimizing duplicated gates in the partitioned sub‐circuits. The partitioned subcircuits are further optimized utilizing observability don't‐care sets. Experimental results for the MCNC benchmarks show that the proposed algorithm synthesizes circuits that on the average consume 22.5% less power and have 12.7% less area than circuits generated by previous algorithms based on a precomputation scheme.     

Circuit activity based logic synthesis for low power reliableoperations

A system developed to synthesize both finite state machines and combinational logic for low-power applications, called SYCLOP, is described. SYCLOP tries to minimize the transition density at the internal nodes of a circuit to minimize power dissipation during normal operation. As input signal probabilities and transition densities are considered during the synthesis process, a particular circuit can be synthesized in different ways for different applications that require different types of inputs. For the present state inputs to the combinational circuit of a state machine, simulation was used to determine the signal probabilities and transition densities. The algorithm is not limited by the number of bits used for state assignment. The multilevel optimization process extracts kernels so that there is a balance between area and power optimization. Results have been obtained for a wide range of MCNC benchmark examples     

Composition bounds for channel block codes

The performance of Channel block codes for a general channel is studied by examining the relationship between the rate of a code, the joint composition of pairs of codewords, and the probability of decoding error. At fixed rate, lower bounds and upper bounds, both on minimum Bhattacharyya distance between codewords and on minimum equivocation distance between codewords, are derived. These bounds resemble, respectively, the Gilbert and the Elias bounds on the minimum Hamming distance between codewords. For a certain large class of channels, a lower bound on probability of decoding error for low-rate channel codes is derived as a consequence of the upper bound on Bhattacharyya distance. This bound is always asymptotically tight at zero rate. Further, for some channels, it is asymptotically tighter than the straight line bound at low rates. Also studied is the relationship between the bounds on codeword composition for arbitrary alphabets and the expurgated bound for arbitrary channels having zero error capacity equal to zero. In particular, it is shown that the expurgated reliability-rate function for blocks of letters is achieved by a product distribution whenever it is achieved by a block probability distribution with strictly positive components.     

Minimizing the dynamic and sub-threshold leakage power consumption using least leakage vector-assisted technology mapping

Power consumption due to the temperature-dependent leakage current becomes a dominant part of the total power dissipation in systems using nanometer-scale process technology. To obtain the minimum power consumption for different operating conditions, logic synthesis tools are required to take into consideration the leakage power as well as the operating characteristics during the optimization. Conventional logic synthesis flows consider dynamic power only and use an over-simplified cost function in modeling the total power consumption of the logic network. In this paper, we propose a complete model of the total power consumption of the logic network, which includes both the active and standby sub-threshold leakage power, and the operating duty cycle of the applications. We also propose a least leakage vector (LLV) assisted technology mapping algorithm to optimize the total power of the final mapped network. Instead of finding the LLV after the logic network is synthesized and mapped, we use the LLV found in the technology-decomposed network to help in obtaining the lowest total power match during technology mapping. Experimental results on MCNC benchmarks show that on average more than 30% reduction in total power consumption is obtained comparing with the conventional low power technology mapping algorithm.     

Krawtchouk polynomials and universal bounds for codes and designsin Hamming spaces

Universal bounds for the cardinality of codes in the Hamming space F_rⁿ with a given minimum distance d and/or dual distance d' are stated. A self-contained proof of optimality of these bounds in the framework of the linear programming method is given. The necessary and sufficient conditions for attainability of the bounds are found. The parameters of codes satisfying these conditions are presented in a table. A new upper bound for the minimum distance of self-dual codes and a new lower bound for the crosscorrelation of half-linear codes are obtained     

基于近似计算技术的FPRM电路面积优化

近似计算技术通过降低电路输出精度实现电路功耗、面积、速度等方面的优化.本文针对RM（Reed-Muller）逻辑中"异或"运算特点，提出了基于近似计算技术的适合FPRM逻辑的电路面积优化算法，包括基于不相交运算的RM逻辑错误率计算方法，及在错误率约束下，有利于面积优化的近似FPRM函数搜索方法等.优化算法用MCNC（Microelectronics Center of North Carolina）电路进行测试.实验结果表明，提出的算法可以处理输入变量个数为199个的大电路，在平均错误率为5.7%下，平均电路面积减少62.0%，并在实现面积优化的同时有利于实现电路的动态功耗的优化且对电路时延影响不大.     

基于划分的力矢量布局算法

提出了一个全新的基于划分的力矢量布局算法．针对大规模集成电路的布局问题，采用基于并行结群技术的递归划分方法进行分解解决，并结合改进的力矢量算法对划分所得的子电路进行迭代布局优化．通过对MCNC标准单元测试电路的实验，与FengShui布局工具相比，该布局算法在花费稍长一点的时间内获得了平均减少12%布局总线长度的良好效果．     

基于与非锥的新型FPGA逻辑簇互连结构研究

该文针对新型FPGA可编程逻辑单元与非锥(And-Inverter Cone, AIC)的结构特性,提出一系列方案以得到优化的逻辑簇互连结构,包括:移除输出级交叉矩阵,单级反相交叉矩阵,低负载电路优化,将反馈和输出选择功能分开,限制AIC输出级数的基础上移除中间级交叉矩阵,与LUT架构进行混合等。通过大量的实验,得出针对面积延时积最优的AIC簇互连结构,与Altera公司的FPGA芯片Stratix-IV结构相比,该结构逻辑功能簇本身面积减小9.06%, MCNC应用电路集在基于优化的AIC FPGA架构上实现的平均面积延时积减小40.82%, VTR应用电路集平均面积延时积减小17.38%;与原有的AIC结构相比,簇面积减小23.16%, MCNC应用电路集平均面积延时减小27.15%, VTR应用电路集平均面积延时积减小15.26%。     

Gate Level Multiple Supply Voltage Assignment Algorithm for Power Optimization Under Timing Constraint

We propose a multiple supply voltage scaling algorithm for low power designs. The algorithm combines a greedy approach and an iterative improvement optimization approach. In phase I, it simultaneously scales down as many gates as possible to lower supply voltages. In phase II, a multiple way partitioning algorithm is applied to further refine the supply voltage assignment of gates to reduce the total power consumption. During both phases, the timing correctness of the circuit is maintained. Level converters (LCs) are adjusted correctly according to the local connectivity of the different supply voltage driven gates. Experimental results show that the proposed algorithm can effectively convert the unused slack of gates into power savings. We use two of the ISPD2001 benchmarks and all of the ISCAS89 benchmarks as test cases. The 0.13-mum CMOS TSMC library is used. On average, the proposed algorithm improves the power consumption of the original design by 42.5% with a 10.6% overhead in the number of LCs. Our study shows that the key factor in achieving power saving is including the most comfortable supply voltage in the scaling process.     

Bounds on FSM Switching Activity

This paper obtains lower and upper bounds for the switching activity on the state lines of a finite state machine (FSM) that is driven by typical input sequences. More specifically, the paper provides bounds on the average Hamming distance which is in turn proportional to the switching activity and the overall power dissipation in the system. By introducing the concepts of a distance matrix and a weight matrix, and by exploiting the symmetry of the distance matrix, we are able to obtain bounds that are provably tighter than existing bounds and, as demonstrated by our experimental results, they can offer significant improvements in many cases of interest. Since our bounds are independent of the state assignment and the actual implementation, they can be used at an early stage of the FSM design to indicate the largest/smallest possible power consumption.