Leakage power consumption of logic elements has become a serious problem, especially in the sub-100-nanometer process. In this paper, a novel power gating approach by using the controlling value of logic elements is proposed. In the proposed method, sleep signals of the power-gated blocks are extracted completely from the original circuits without any extra logic element. A basic algorithm and a probability-based heuristic algorithm have been developed to implement the basic idea. The steady maximum delay constraint has also been introduced to handle the delay issues. Experiments on the ISCAS'85 benchmarks show that averagely 15-36% of logic elements could be power gated at a time for random input patterns, and 3-31% of elements could be stopped under the steady maximum delay constraints. We also show a power optimization method for AND/OR tree circuits, in which more than 80% of gates can be power-gated.

The paper describes the folding method of logic functions to reduce the size of memories to keep the functions. The folding is based on the relation of fractions of logic functions. If the logic function includes 2 or 3 same parts, then only one part should be kept and other parts can be omitted. We show that the logic function of 1-bit addition can be reduced to half size using the bit-wise NOT relation and the bit-wise OR relation. The paper also introduces 3-1 LUT's with the folding mechanism. A full adder can be implemented using only one 3-1 LUT with the folding. Multi-bit AND and OR operations can be mapped to our LUT's not using the extra cascading circuit but using the carry circuit for addition. We have also tested the mapping capability of 4 input functions to our 3-1 LUT's with folding and carry propagation mechanisms. We have shown the reduction of the area consumption when using our LUT's compared to the case using 4-1 LUT's on several benchmark circuits.

Given a set P of n points on which facilities can be placed and an integer k, we want to place k facilities on some points so that the minimum distance between facilities is maximized. The problem is called the k-dispersion problem. In this paper, we consider the 3-dispersion problem when P is a set of points on a plane (2-dimensional space). Note that the 2-dispersion problem corresponds to the diameter problem. We give an O(n) time algorithm to solve the 3-dispersion problem in the L∞ metric, and an O(n) time algorithm to solve the 3-dispersion problem in the L1 metric. Also, we give an O(n2 log n) time algorithm to solve the 3-dispersion problem in the L2 metric.

High-level synthesis is a novel method to generate a RT-level hardware description automatically from a high-level language such as C, and is used at recent digital circuit design. Floating-point to fixed-point conversion with bit-length optimization is one of the key issues for the area and speed optimization in high-level synthesis. However, the conversion task is a rather tedious work for designers. This paper introduces automatic bit-length optimization method on floating-point to fixed-point conversion for high-level synthesis. The method estimates computational errors statistically, and formalizes an optimization problem as a non-linear problem. The application of NLP technique improves the balancing between computational accuracy and total hardware cost. Various constraints such as unit sharing, maximum bit-length of function units can be modeled easily, too. Experimental result shows that our method is fast compared with typical one, and reduces the hardware area.

The Hajos calculus is a nondeterministic procedure which generates the class of non-3-colorable graphs. If all non-3-colorable graphs can be constructed in polynomial steps by the calculus, then NP = co-NP holds. Up to date, however, it remains open whether there exists a family of graphs that cannot be generated in polynomial steps. To attack this problem, we propose two graph calculi PHC and PHC* that generate non-3-colorable planar graphs, where intermediate graphs in the calculi are also restricted to be planar. Then we prove that PHC and PHC* are sound and complete. We also show that PHC* can polynomially simulate PHC.

We are given a set S of n points in the Euclidean plane. We assume that S is in general position. A simple polygon P is an empty polygon of S if each vertex of P is a point in S and every point in S is either outside P or a vertex of P. In this paper, we consider the problem of enumerating all the empty polygons of a given point set. To design an efficient enumeration algorithm, we use a reverse search by Avis and Fukuda with child lists. We propose an algorithm that enumerates all the empty polygons of S in O(n2|ε(S)|)-time, where ε(S) is the set of empty polygons of S. Moreover, by applying the same idea to the problem of enumerating surrounding polygons of a given point set S, we propose an enumeration algorithm that enumerates them in O(n2)-delay, while the known algorithm enumerates in O(n2 log n)-delay, where a surroundingpolygon of S is a polygon such that each vertex of the polygon is a point in S and every point in S is either inside the polygon or a vertex of the polygon.

We explore the maximum total number of edge crossings and the maximum geometric thickness of the Euclidean minimum-weight (k, ℓ)-tight graph on a planar point set P. In this paper, we show that (10/7－ε)|P| and (11/6－ε)|P| are lower bounds for the maximum total number of edge crossings for any ε ＞ 0 in cases (k,ℓ)=(2,3) and (2,2), respectively. We also show that the lower bound for the maximum geometric thickness is 3 for both cases. In the proofs, we apply the method of arranging isomorphic units regularly. While the method is developed for the proof in case (k,ℓ)=(2,3), it also works for different ℓ.

We prove NP-completeness of deciding whether a given loop of colored right isosceles triangles, hinged together at edges, can be folded into a specified rectangular three-color pattern. By contrast, the same problem becomes polynomially solvable with one color or when the target shape is a tree-shaped polyomino.

Clock gating is the insertion of control signal for registers to switch off unnecessary clock signals selectively without violating the functional correctness of the original design so as to reduce the dynamic power consumption. Commercial EDA tools usually have a mechanism to generate clock gating logic based on the structural method where the control signals specified by designers are used, and the effectiveness of the clock gating depends on the specified control signals. In the research, we focus on the automatic clock gating logic generation and propose a method based on the candidate extraction and control signal selection. We formalize the control signal selection using linear formulae and devise an optimization method based on BDD. The method is effective for circuits with a lot of shared candidates by different registers. The method is applied to counter circuits to check the co-relation with power simulation results and a set of benchmark circuits. 19.1-71.9% power reduction has been found on counter circuitsafter layout and 2.3-18.0% cost reduction on benchmark circuits.

In the hardware synthesis from a high-level language such as C, the bit length of variables is one of the key issues for the area and speed optimization. Usually, designers are required to optimize the bit-length of each variable manually using the time-consuming simulation on huge-data. In this paper, we propose an optimization method of the fractional bit length in the conversion from floating-point variables to fixed-point variables. The method is based on error propagation and the backward propagation of the accuracy limitation. The method is fully analytical and fast compared to simulation based methods.

This paper studies a variant of the graph partitioning problem, called the evacuation planning problem, which asks us to partition a target area, represented by a graph, into several regions so that each region contains exactly one shelter. Each region must be convex to reduce intersections of evacuation routes, the distance between each point to a shelter must be bounded so that inhabitants can quickly evacuate from a disaster, and the number of inhabitants assigned to each shelter must not exceed the capacity of the shelter. This paper formulates the convexity of connected components as a spanning shortest path forest for general graphs, and proposes a novel algorithm to tackle this multi-objective optimization problem. The algorithm not only obtains a single partition but also enumerates all partitions simultaneously satisfying the above complex constraints, which is difficult to be treated by existing algorithms, using zero-suppressed binary decision diagrams (ZDDs) as a compressed expression. The efficiency of the proposed algorithm is confirmed by the experiments using real-world map data. The results of the experiments show that the proposed algorithm can obtain hundreds of millions of partitions satisfying all the constraints for input graphs with a hundred of edges in a few minutes.

Last year, a new notion of rep-cube was proposed. A rep-cube is a polyomino that is a net of a cube, and it can be divided into some polyominoes such that each of them can be folded into a cube. This notion was inspired by the notions of polyomino and rep-tile, which were introduced by Solomon W. Golomb. It was proved that there are infinitely many distinct rep-cubes. In this paper, we investigate this new notion and show further results.

An Ordered Binary Decision Diagram (OBDD) is a directed acyclic graph representing a Boolean function. The size of OBDDs largely depends on the variable ordering. In this paper, we show the size of the OBDD representing the i-th bit of the output of n-bit/n-bit integer division is Ω ( 2(n-i)/8 ) for any variable ordering. We also show that -OBDDs, -OBDDs and -OBDDs representing integer division has the same lower bounds on the size. We develop new methods for proving lower bounds on the size of -OBDDs, -OBDDs and -OBDDs.

Clock gating is supported by commercial tools as a power optimization feature based on the guard signal described in HDL (structural method). However, the identification of control signals for gated registers is hard and designer-intensive work. Besides, since the clock gating cells also consume power, it is imperative to minimize the number of inserted clock gating cells and their switching activities for power optimization. In this paper, we propose an automatic multi-stage clock gating algorithm with ILP (Integer Linear Programming) formulation, including clock gating control candidate extraction, constraints construction and optimum control signal selection. By multi-stage clock gating, unnecessary clock pulses to clock gating cells can be avoided by other clock gating cells, so that the switching activity of clock gating cells can be reduced. We find that any multi-stage control signals are also single-stage control signals, and any combination of signals can be selected from single-stage candidates. The proposed method can be applied to 3 or more cascaded stages. The multi-stage clock gating optimization problem is formulated as constraints in LP format for the selection of cascaded clock-gating order of multi-stage candidate combinations, and a commercial ILP solver (IBM CPLEX) is applied to obtain the control signals for each register with minimum switching activity. Those signals are used to generate a gate level description with guarded registers from original design, and a commercial synthesis and layout tools are applied to obtain the circuit with multi-stage clock gating. For a set of benchmark circuits and a Low Density Parity Check (LDPC) Decoder (6.6k gates, 212 F.F.s), the proposed method is applied and actual power consumption is estimated using Synopsys NanoSim after layout. On average, 31% actual power reduction has been obtained compared with original designs with structural clock gating, and more than 10% improvement has been achieved for some circuits compared with single-stage optimization method. CPU time for optimum multi-stage control selection is several seconds for up to 25k variables in LP format. By applying the proposed clock gating, area can also be reduced since the multiplexors controlling register inputs are eliminated.