This thesis proposes several hardware implementation approaches for the EBCOT (Embedded Block Coding with Optimized Truncation) algorithm, one of the key operations in the emerging JPEG 2000 standard. We also modify the EBCOT algorithm in order to reduce the memory requirement and to improve the speed performance. The modified EBCOT encoder saves 40% memory area with triple speed performance compared to the original design.

Buffer insertion is an essential technique for reducing interconnect delay in submicron circuits. Though it is a well researched area, there is a need for robust and effective algorithms to perform buffer insertion at the circuit level. This thesis proposes a new buffer insertion algorithm for large circuits. The algorithm finds a buffering solution for the entire circuit such that buffer cost is minimized and the timing requirements of the circuit are satisfied. The algorithm iteratively inserts buffers in the circuit improving the circuit delay step by step. At the core of this algorithm are very simple but extremely effective techniques that constructively guide the search for a good buffering solution. A flexibility to adapt to the user's requirements and the ability to reduce the number of buffers are the strengths of this algorithm. Experimental results on ISCAS85 benchmark circuits show that the proposed algorithm, on average, yields 36% reduction in the number of buffers, and runs three times faster than one of the best known previously researched algorithms.

Along the history of Very Large Scale Integration (VLSI), we have successfully scaled down the size of transistors, scaled up the speed of integrated circuits (IC) and the number of transistors in a chip - these are just a few examples of our achievement in VLSI scaling. It is projected to enter the nanometer (timing estimation and buffer planning for global routing and other early stages such as floorplanning. A novel path based buffer insertion scheme is also included, which can overcome the weakness of the net based approaches. Part-2 Circuit clustering techniques with the application in Field-Programmable Gate Array (FPGA) technology mapping The problem of timing driven n-way circuit partitioning with application to FPGA technology mapping is studied and a hierarchical clustering approach is presented for the latest multi-level FPGA architectures. Moreover, a more general delay model is included in order to accurately characterize the delay behavior of the clusters and circuit elements.

As Very Large Scale Integration (VLSI) technology moves to the nanoscale regime, design and manufacturing closure becomes very difficult to achieve due to increasing chip and power density. Imperfections due to process, voltage and temperature variations aggravate the problem. Uncertainty in electrical characteristic of individual device and wire may cause significant performance deviations or even functional failures. These impose tremendous challenges to the continuation of Moore's law as well as the growth of semiconductor industry. Efforts are needed in both deterministic design stage and variation-aware design stage. This research proposes various innovative algorithms to address both stages for obtaining a design with high frequency, low power and high robustness. For deterministic optimizations, new buffer insertion and gate sizing techniques are proposed. For variation-aware optimizations, new lithography-driven and post-silicon tuning-driven design techniques are proposed. For buffer insertion, a new slew buffering formulation is presented and is proved to be NP-hard. Despite this, a highly efficient algorithm which runs > 90x faster than the best alternatives is proposed. The algorithm is also extended to handle continuous buffer locations and blockages. For gate sizing, a new algorithm is proposed to handle discrete gate library in contrast to unrealistic continuous gate library assumed by most existing algorithms. Our approach is a continuous solution guided dynamic programming approach, which integrates the high solution quality of dynamic programming with the short runtime of rounding continuous solution. For lithography-driven optimization, the problem of cell placement considering manufacturability is studied. Three algorithms are proposed to handle cell flipping and relocation. They are based on dynamic programming and graph theoretic approaches, and can provide different tradeoff between variation reduction and wire- length increase. For post-silicon tuning-driven optimization, the problem of unified adaptivity optimization on logical and clock signal tuning is studied, which enables us to significantly save resources. The new algorithm is based on a novel linear programming formulation which is solved by an advanced robust linear programming technique. The continuous solution is then discretized using binary search accelerated dynamic programming, batch based optimization, and Latin Hypercube sampling based fast simulation.

Zugl.: Zürich, Techn. Hochsch., Diss., 2008

Thesis (doctoral)--Universität, Paderborn, 2000.

IDDQ testing has been a very useful test screen for CMOS circuits. However, with each technology node the background leakage of chips is rapidly increasing. As a result it is becoming more difficult to distinguish between faulty and fault-free chips using IDDQ testing. Power supply partitioning has been proposed to increase test resolution by partitioning the power supply network, such that each partition has a relatively small defect-free IDDQ level. However, at present no practical partitioning strategy is available. The contribution of this thesis is to present a practical power supply partitioning strategy. We formulate various versions of the power supply partitioning problem that are likely to be of interest depending on the constraints of the chip design. Solutions to all the variants of the problem are presented. The basic idea behind all solutions is to abstract the power topology of the chip as a flow network. We then use flow techniques to find the min-cut of the transformed network to get solutions to our various problem formulations. Experimental results for benchmark circuits verify the feasibility of our solution methodology. The problem formulations will give complete flexibility to a test engineer to decide which factors cannot be compromised (e.g. area of BICS, test quality, etc) for a particular design and accordingly choose the appropriate problem formulation. The application of this work will be the first step in the placement of Built-In Current Sensors for IDDQ testing.

No description available.

No description available.

No description available.