In this paper, a practical clock-scheduling engine is introduced. The minimum feasible clock-period is obtained by using a modified Bellman-Ford shortest path algorithm. Then an optimum cost clock-schedule is obtained by using a bipartite matching algorithm. It also provides useful information to circuit synthesis tools. The experiment to a circuit with about 10000 registers and 100000 signal paths shows that a result is obtained within a few minutes. The computation time is almost linear to the circuit size in practice.

Under the assumption that clock can be inputted to each register at an arbitrary timing, the minimum feasible clock period can be determined if delays between registers are given. This minimum feasible clock period might be reduced if delays between some registers are increased by delay insertion. In this paper, we propose a delay insertion algorithm to reduce the minimum clock period. First, the proposed algorithm determines a clock schedule ignoring some constraints. Second, the algorithm inserts delays to recover ignored constraints according to the delay-slack and delay-demand of the obtained clock schedule. We show that the proposed algorithm achieves the minimum clock period by delay insertion if the delay of each element in the circuit is unique. Experiments show that the amount of inserting delay and computational time are smaller than the conventional algorithm.

We introduce a clock schedule algorithm to obtain a clock schedule that achieves a shorter clock period and that can be realized by a light clock tree. A shorter clock period can be achieved by controlling the clock input timing of each register, but the required wire length and power consumption of a clock tree tends to be large if clock input timings are determined without considering the locations of registers. To overcome the drawback, our algorithm constructs a cluster that consists of registers with the same clock input timing located in a close area. The registers in each cluster are driven by a buffer and a shorter wire length can be achieved. In our algorithm, first registers are partitioned into clusters by their locations, and clusters are modified to improve the clock period while maintaining the radius of each cluster small. In our experiments, the clock period achieved in average is about 13% shorter than that achieved by a zero-skew clock tree, and about 4% longer than the theoretical minimum. The wire length and power consumption of a clock tree according to an obtained clock schedule is comparable to these of a zero skew tree.

A circuit in which the clock is assumed to be distributed periodically to each individual register though not necessarily to all registers simultaneously, called a semi-synchronous circuit, is expected to achieve higher frequency or a smaller clock tree compared with an ordinary synchronous circuit, called a complete-synchronous circuit. In this paper, we propose a circuit design method that realizes a semi-synchronous circuit with higher frequency by modifying the clock tree of a complete-synchronous circuit. We confirm that the proposed method is easy to incorporate with current practical design environment by designing a four stage pipelined processor compatible with MIPS operation code. The obtained processor circuit is the first semi-synchronous circuit designed systematically with theoretical background.

In this paper, we propose a new clock tree synthesis method for semi-synchronous circuits. A clock tree obtained by the proposed method is a multi-level multi-way clock tree such that a clock-input timing of each register is a multiple of a predefined unit delay and the wire length from a clock buffer to an element driven by it is bounded. The clock trees are constructed for several practical circuits. The size of constructed clock tree is comparable to a zero skew clock tree. In order to assure the practical quality of the clock trees, they are examined under the five delay conditions, which cover various environmental and manufacturing conditions. As a result, they are proved stable under each condition and improve the clock speed up to 17.3% against the zero skew clock trees.

A semi-synchronous circuit is a circuit in which the clock is assumed to be distributed periodically to each individual register, though not necessarily to all registers simultaneously. In this paper, we propose an algorithm to achieve the target clock period by modifying a given target clock schedule as small as possible, where the realization cost of the target clock schedule is assumed to be minimum. The proposed algorithm iteratively improves a feasible clock schedule. The algorithm finds a set of registers that can reduce the cost by changing their clock timings with same amount, and changes the clock timing with optimal amount. Experiments show that the algorithm achieves the target clock period with fewer modifications.

It is known that the clock-period can be shorter than the maximum of signal-delays between registers if the clock arrival time to each register is properly scheduled. The algorithm to design an optimal clock-schedule was given. In this paper, we propose a clock-tree routing algorithm that realizes a given clock-schedule using the Elmore-delay model. Following the deferred-merge-embedding (DME) framework, the algorithm generates a topology of the clock-tree and simultaneously determines the locations and sizes of intermediate buffers. The experimental results showed that this method constructs a clock-tree with moderate wire length for a random layout of scheduled registers. Notably, the required wire length for a gentle layout of scheduled registers was shown to be almost equal to that of zero-skew clock-trees.

A semi-synchronous circuit is a circuit in which every register is ticked by a clock periodically, but not necessarily simultaneously. In a semi-synchronous circuit, the minimum delay between registers may be critical with respect to the clock period of the circuit, while it does not affect the clock period of an ordinary synchronous circuit. In this paper, we discuss a delay insertion method which makes such a semi-synchronous circuit faster. The maximum delay-to-register ratio over the cycles in the circuit gives a lower bound of the clock period. We show that this bound is achieved in the semi-synchronous framework by the proposing gate-level delay insertion method.