Clock skew scheduling is a technique that intentionally introduces skews to memory elements to improve the performance of a sequential circuit. It was shown in (Ravindran, 2003) that the full optimization potential of clock skew scheduling can be reliably implemented using a few skew domains. In this paper we present an optimal skew scheduling algorithm for sequential circuits with flip-flops. Given a finite set of prescribed skew domains, the algorithm finds a domain assignment for each flip-flop such that the clock period is minimized with possible delay padding. Experimental results validate the efficiency of our algorithm and show 17% improvement on average in clock period.

In this paper we present a new algorithm for retiming synchronous dataflow (SDF) graphs. The retiming aims at minimizing the cycle length of an SDF. The algorithm is provably optimal and its execution time is improved compared to previous approaches.

Design closure becomes hard to achieve at physical layout stage due to the emergence of long global interconnects. Consequently, interconnect planning needs to be integrated in high level synthesis. Delay relaxation that assigns extra clock latencies to functional resources at RTL (register transfer level) can be leveraged. This paper proposed a general formulation for design closure driven delay relaxation problem. The authors show that the general formulation can be transformed into a convex cost integer dual network flow problem and solved in polynomial time using the convex cost-scaling algorithm in (Ahuja et al., 2003). Experimental results validate the efficiency of the approach

Latches are extensively used in high-performance sequential circuit designs to achieve high frequencies because of their good performance and time-borrowing feature. However, the amount of timing uncertainty due to crosstalk accumulated through latches could be larger than the benefit gained by time borrowing. In this paper, we show that the tradeoff between a latch and a flop can be leveraged in a sequential circuit design with crosstalk, so that the clock period is minimized by selecting a configuration of mixed latches and flops. A circular time representation is proposed to make coupling detection easier and more efficient. Experiments on our heuristic algorithm for finding an optimal configuration of mixed latches and flops showed promising results.

In this paper we present a new efficient algorithm for retiming sequential circuits with edge-triggered registers under both setup and hold constraints. Compared with the previous work [17], which computed the minimum clock period in O(|V|3|E|lg|V|) time, our algorithm solves the same problem in O(|V|2|E|) time. Experimental results validate the efficiency of our algorithm.

With the advent of deep sub-micron (DSM) era, floorplanning has become increasingly important in physical design process. In this paper we clarify a misunderstanding in using Lagrangian relaxation for the minimum area floorplanning problem. We show that the problem is not convex and its optimal solution cannot be obtained by solving its Lagrangian dual problem. We then propose a modified convex formulation and solve it using min-cost flow technique and trust region method. Experimental results under module aspect ratio bound [0.5, 2.0] show that the running time of our floorplanner scales well with the problem size in MCNC benchmark. Compared with the floorplanner in the work of Young et al. (2001), our floorplanner is 9.5times faster for the largest case ami49. It also generates a floorplan with smaller deadspace for almost all test cases. In addition, since the generated floorplan has an aspect ratio closer to 1, it is more friendly to packaging. Our floorplanner is also amicable to including interconnect cost and other physical design metrics

The problem of retiming over a netlist of macroblocks to achieve minimal clock period, where block internal structures may not be changed and flip-flops may not be inserted on some wire segments, is called the optimal wire retiming problem. This paper presents a new algorithm that solves the optimal wire retiming problem with polynomial-time worst case complexity. Since the new algorithm avoids binary search and is essentially incremental, it has the potential of being combined with other optimization techniques. Experimental results show that the new algorithm is very efficient in practice.

Clustering (or partitioning) is a crucial step between logic synthesis and physical design in the layout of a large scale design. A design verified at the logic synthesis level may have timing closure problems at post-layout stages due to the emergence of multiple-clock-period interconnects. Consequently, a tradeoff between clock frequency and throughput may be needed to meet the design requirements. In this paper, we find that the processing rate, defined as the product of frequency and throughput, of a sequential system is upper bounded by the reciprocal of its maximum cycle ratio, which is only dependent on the clustering. We formulate the problem of processing rate optimization as seeking an optimal clustering with the minimal maximum-cycle-ratio in a general graph, and present an iterative algorithm to solve it. Experimental results validate the efficiency of our algorithm

Clustering (or partitioning) is a crucial step between logic synthesis and physical design in the layout of a large scale design. A design verified at the logic synthesis level may have timing closure problems at post-layout stages due to the emergence of multiple-clock-period interconnects. Consequently, a trade-off between clock frequency and throughput may be needed to meet the design requirements. In this paper, we find that the processing rate, defined as the product of frequency and throughput, of a sequential system is upper bounded by the reciprocal of its maximum cycle ratio, which is only dependent on the clustering. We formulate the problem of processing rate optimization as seeking an optimal clustering with the minimal maximum-cycle-ratio in a general graph, and present an iterative algorithm to solve it. Since our algorithm avoids binary search and is essentially incremental, it has the potential of being combined with other optimization techniques. Experimental results validate the efficiency of our algorithm.

Latches are extensively used in high-performance sequential circuit designs to achieve high frequencies because of their good performance and time borrowing feature. However, the amount of timing uncertainty due to crosstalk accumulated through latches could be larger than the benefit gained by time borrowing. In this paper, we show that the trade-off between a latch and a flop can be leveraged in a sequential circuit design with crosstalk, so that the clock period is minimized by selecting a configuration of mixed latches and flops. A circular time representation is proposed to make coupling detection easier and more efficient. Experiments on our heuristic algorithm for finding an optimal configuration of mixed latches and flops showed promising results.

In system-on-chips (SOCs), a nonnegligible part of operation time is spent on global wires with long delays. Retiming-that is moving flip-flops in a circuit without changing its functionality-can be explored to pipeline long interconnect wires in SOC designs. The problem of retiming over a netlist of macro-blocks, where the internal structures may not be changed and flip-flops may not be inserted on some wire segments is called the wire retiming problem. In this paper, we formulate the constraints of the wire retiming problem as a fixpoint computation and use an iterative algorithm to solve it. Experimental results show that this approach is multiple orders more efficient than the previous one.

In the current and future System-On-Chips, a non-negligible part of operation time is spent on multiple-clock period wires. Retiming-that is moving flip-flops in a circuit without changing its functionality-can be explored to pipeline long interconnect wires in SOC designs. The problem of retiming over a netlist of macro-blocks, where the internal structures may not be changed and flip-flops may not be inserted on some wire segments is called the wire retiming problem. In this paper, we formulate the constraints of the wire retiming problem as a fixpoint computation and use an iterative algorithm to solve it. Experimental results show that this approach is multiple orders more efficient than the previous one.

The problem of retiming over a netlist of macro-blocks to achieve the minimal clock period, where the block internal structures may not be changed and flip-flops may not be inserted on some wire segments, is called the optimal wire retiming problem. To the best of our knowledge, there is no polynomial-time approach to solve it and the existence of such an approach is still an open question. We present a brand new algorithm that solves the optimal wire retiming problem with polynomial-time worst case complexity. Since the new algorithm avoids binary search and is essentially incremental, it has the potential of being combined with other optimization techniques. Experimental results show that the new algorithm is very efficient in practice.

At the integration scale of system-on-chips (SOCs), the conflicts between communication and computation will become prominent even on a chip. A big fraction of system time will shift from computation to communication. In synchronous systems, a large amount of communication time is spent on multiple-clock period wires. In this paper, we explore retiming to pipeline long interconnect wires in SOC designs. Behaviorally, it means that both computation and communication are rescheduled for parallelism. The retiming is applied to a netlist of macroblocks, where the internal structures may not be changed and flip-flops may not be able to be inserted on some wire segments. This problem is different from that on a gate-level netlist and is formulated as a wire-retiming problem. Theoretical treatment and a polynomial time algorithm are presented in the paper. Experimental results showed the benefits and effectiveness of our approach.