Search-based placement methods have long been used for placing integrated circuits targeting the field programmable gate array (FPGA) and standard cell design styles. Such methods offer the potential for high-quality solutions but often come at the cost of long run-times compared to alternative methods. This dissertation examines strategies for enhancing local search heuristics---and in particular, simulated annealing---through the application of directed moves. These moves help to guide a search-based optimizer by focusing efforts on states which are most likely to yield productive improvement, effectively pruning the size of the search space. The engineering theory and implementation details of directed moves are discussed in the context of both field programmable gate array and standard cell designs. This work explores the ways in which such moves can be used to improve the quality of FPGA placements, improve the robustness of floorplan repair and legalization methods for mixed-size standard cell designs, and enhance the quality of detailed placement for standard cell circuits. The analysis presented herein confirms the validity and efficacy of directed moves, and supports the use of such heuristics within various optimization frameworks.

High performance, energy efficient logic style has always been a popular research topic in the field of very large scale integrated (VLSI) circuits because of the continuous demands of ever increasing circuit operating frequency. The invention of the dynamic logic in the 80s is one of the answers to this request as it allows designers to implement high performance circuit block, i.e., arithmetic logic unit (ALU), at an operating frequency that traditional static and pass transistor CMOS logic styles are difficult to achieve. However, the performance enhancement comes with several costs, including reduced noise margin,charge-sharing noise, and higher power dissipation due to higher data activity. Furthermore, dynamic logic has gradually lost its performance advantage over static logic due to the increased self-loading ratio in deep-submicron technology (65nm and below) because of the additional NMOS CLK footer transistor. Because of dynamic logic's limitations and diminished speed reward, a slowly rising need has emerged in the past decade to explore new logic style that goes beyond dynamic logic. In this thesis a constant delay (CD) logic style is proposed. The constant delay characteristic of this logic style regardless of the logic expression makes it suitable in implementing complicated logic expression such as addition. Moreover, CD logic exhibits a unique characteristic where the output is pre-evaluated before the inputs from the preceding stage is ready. This feature enables performance advantage over static and dynamic logic styles in a single cycle, multi-stage circuit block. Several design considerations including appropriate timing window width adjustment to reduce power consumption and maintain sufficient noise margin to ensure robust operations are discussed and analyzed. Using 65nm general purpose CMOS technology, the proposed logic demonstrates an average speed up of 94% and 56% over static and dynamic logic respectively in five different logic expressions. Post layout simulation results of 8-bit ripple carry adders conclude that CD-based design is 39% and 23% faster than the static and dynamic-based adders respectively. For ultra-high speed applications, CD-based design exhibits improved energy, power-delay product, and energy-delay product efficiency compared to static and dynamic counterparts.

Research presented in this thesis provides a substantial leap from the study of interesting device physics to fully adaptive analog networks and lays a solid foundation for future development of large-scale, compact, low-power adaptive parallel analog computation systems. The investigation described here started with observation of this potential learning capability and led to the first derivation and characterization of the floating-gate pFET correlation learning rule. Starting with two synapses sharing the same error signal, we progressed from phase correlation experiments through correlation experiments involving harmonically related sinusoids, culminating in learning the Fourier series coefficients of a square wave cite{kn:Dugger2000}. Extending these earlier two-input node experiments to the general case of correlated inputs required dealing with weight decay naturally exhibited by the learning rule. We introduced a source-follower floating-gate synapse as an improvement over our earlier source-degenerated floating-gate synapse in terms of relative weight decay cite{kn:Dugger2004}. A larger network of source-follower floating-gate synapses was fabricated and an FPGA-controlled testboard was designed and built. This more sophisticated system provides an excellent framework for exploring applications to multi-input, multi-node adaptive filtering applications. Adaptive channel equalization provided a practical test-case illustrating the use of these adaptive systems in solving real-world problems. The same system could easily be applied to noise and echo cancellation in communication systems and system identification tasks in optimal control problems. We envision the commercialization of these adaptive analog VLSI systems as practical products within a couple of years.

The main objective of this thesis is to develop models for the power distribution network of high performance gigascale chips. The two main concerns in distributing power in a chip are voltage drop and electromigration-induced reliability failures. The voltage drop on the power distribution network is due to IR-drop and simultaneous switching noise. IR-drop is the voltage drop due to current passing through the resistances of the power distribution network. Simultaneous switching noise is due to varying current passing through the inductances of the power distribution network. Compact physical models are derived for the IR-drop and electromigration for different types of packages. These chip-package co-design models enable designers in the early stages of the design to estimate the on-chip interconnect resources, and also to choose type and size of the package required for power distribution. Modeling of the simultaneous switching noise requires the simulation of a large circuit with thousands of inductances. The main obstacle challenging the simulation of a simultaneous switching noise circuit model is the computing resources required to solve the dense inductance matrix. In this work, a new relative inductance matrix is introduced to solve massively coupled RLC interconnects. It is proven that the analysis using this method is accurate for a wide frequency range and all configurations. Using the new inductance matrix makes the circuit simulations significantly faster without losing accuracy.

Home medical equipment becomes increasingly popular as VLSI fabrication technology advances. However, there are two important factors for realizing a miniaturized biochip: low noise [1] and low power. Firstly, physiological signals are very susceptible to interference while the amplitude of the signal is only a few millivolts or less. If the circuit cannot reject noise effectively, it is hard to amplify the signal and obtain the output voltage of the recording system accurately. Secondly, it is not convenient to replace the batteries frequently when using the portable measurement instrument for the patients. This thesis is focused on the measurement of physiological signals, such as electrocardiography (ECG) [2], electroneurogram (ENG) [3] and electromyography (EMG) [4] , and designing an all-in-one recording system to measure the different physiological signals in a chip. For this purpose, a programmable multi-parameter system for recording of the wide range of physiological signals is designed. The system provides two types of input transconductance stages, BiCMOS and CMOS. BiCMOS amplifiers provide high gain , low noise [5] and low offset voltage suitable for the small amplitude of the physiological signal. On the other hand, CMOS amplifiers provide practically infinite input impedance and ultra-low leakage current. The system also provides three selectable amplifier modes: (a) double-differential amplifier, (b) single-differential amplifier in channel 1, (c) single-differential amplifier in channel 2. The double-differential amplifier provides a high common-mode rejection and adjustable gain for each channel to further reduce common-mode interference. The single-differential amplifier (channel 1 or channel 2) in the recording system are also accessible as differential-input and single-ended output channels. Moreover, the system provides an offset compensation structure to prevent the amplifier from exceeding the input range. The offset compensation system can selectively be turned off to reduce the power consumption.

A prototype of a one-time implantable spinal cord stimulation (SCS) system is presented in this thesis. A pair of inductive coils is used to achieve wireless power transmission and bidirectional communication. A rechargeable Li-ion battery is used to extend the lifetime of the implanted SCS device. Therefore, the number of the battery replacement surgery could be reduced such that one-time implantation is feasible. Besides, the proposed system on chip (SOC) controller and many discretes are integrated on a printed circuit board (PCB). The size of the proposed SCS device is competitive compared to the currently commercial products. The proposed SOC controller adopts a dual supply voltage scheme to reduce power consumption. The proposed SCS system employs an amplitude-shift keying (ASK) technique to carry out the data modulation and power transmission. One of the critical factors to affect efficiency of ASK-based wireless power transmission is the oscillating frequency accuracy. A ROM-less direct digital frequency synthesizer (DDFS) is presented in this thesis to fulfill such a high accuracy demand. Since the supply voltages of the discretes are diversified on a system PCB, many level converters are needed to translate different signal output voltage levels. To resolve above problem, the chip, then, must be redesigned to meet the various voltage level requirement, or added level convertors among the SOC and the discretes. Obviously, it will cause a lot of cost. A wide-range I/O buffer, thus, is proposed to resolve the compatibility problem caused by different supply voltages of discretes.

Fault diagnosis plays an important role in improving the circuit design process and the manufacturing yield. With the increasing number of gates in modern circuits, determining the source of failure in a defective circuit is becoming more and more challenging. In this research, we present an efficient effect-cause diagnosis framework for combinational VLSI circuits. The framework consists of three stages to obtain an accurate and reasonably precise diagnosis. First, an improved critical path tracing algorithm is proposed to identify an initial suspect list by backtracing from faulty primary outputs toward primary inputs. Compared to the traditional critical path tracing approach, our algorithm is faster and exact. Second, a novel probabilistic ranking model is applied to rank the suspects so that the most suspicious one will be ranked at or near the top. Several fast filtering methods are used to prune unrelated suspects. Finally, to refine the diagnosis, fault simulation is performed on the top suspect nets using several common fault models. The difference between the observed faulty behavior and the simulated behavior is used to rank each suspect. Experimental results on ISCAS85 benchmark circuits show that this diagnosis approach is efficient both in terms of memory space and CPU time and the diagnosis results are accurate and reasonably precise.

This research addresses some critical challenges in various problems of VLSI design automation, including sophisticated solution search on DAG topology, simultaneous multi-stage design optimization, optimization on multi-scenario and multi-core designs, and GPU-based parallel computing for runtime acceleration. Discrete optimization for VLSI design automation problems is often quite complex, due to the inconsistency and interference between solutions on reconvergent paths in directed acyclic graph (DAG). This research proposes a systematic solution search guided by a global view of the solution space. The key idea of the proposal is joint relaxation and restriction (JRR), which is similar in spirit to mathematical relaxation techniques, such as Lagrangian relaxation. Here, the relaxation and restriction together provides a global view, and iteratively improves the solution. Traditionally, circuit optimization is carried out in a sequence of separate optimization stages. The problem with sequential optimization is that the best solution in one stage may be worse for another. To overcome this difficulty, we take the approach of performing multiple optimization techniques simultaneously. By searching in the combined solution space of multiple optimization techniques, a broader view of the problem leads to the overall better optimization result. This research takes this approach on two problems, namely, simultaneous technology mapping and cell placement, and simultaneous gate sizing and threshold voltage assignment. Modern processors have multiple working modes, which trade off between power consumption and performance, or to maintain certain performance level in a powerefficient way. As a result, the design of a circuit needs to accommodate different scenarios, such as different supply voltage settings. This research deals with this multi-scenario optimization problem with Lagrangian relaxation technique. Multiple scenarios are taken care of simultaneously through the balance by Lagrangian multipliers. Similarly, multiple objective and constraints are simultaneously dealt with by Lagrangian relaxation. This research proposed a new method to calculate the subgradients of the Lagrangian function, and solve the Lagrangian dual problem more effectively. Multi-core architecture also poses new problems and challenges to design automation. For example, multiple cores on the same chip may have identical design in some part, while differ from each other in the rest. In the case of buffer insertion, the identical part have to be carefully optimized for all the cores with different environmental parameters. This problem has much higher complexity compared to buffer insertion on single cores. This research proposes an algorithm that optimizes the buffering solution for multiple cores simultaneously, based on critical component analysis. Under the intensifying time-to-market pressure, circuit optimization not only needs to find high quality solutions, but also has to come up with the result fast. Recent advance in general purpose graphics processing unit (GPGPU) technology provides massive parallel computing power. This research turns the complex computation task of circuit optimization into many subtasks processed by parallel threads. The proposed task partitioning and scheduling methods take advantage of the GPU computing power, achieve significant speedup without sacrifice on the solution quality.

Test power is an important issue in deep submicron semiconductor testing. Too much power supply noise and too much power dissipation can result in excessive temperature rise, both leading to overkill during delay test. Scan-based test has been widely adopted as one of the most commonly used VLSI testing method. The test power during scan testing comprises shift power and capture power. The power consumed in the shift cycle dominates the total power dissipation. It is crucial for IC manufacturing companies to achieve near constant power consumption for a given timing window in order to keep the chip under test (CUT) at a near constant temperature, to make it easy to characterize the circuit behavior and prevent delay test over kill. To achieve constant test power, first, we built a fast and accurate power model, which can estimate the shift power without logic simulation of the circuit. We also proposed an efficient and low power X-bit Filling process, which could potentially reduce both the shift power and capture power. Then, we introduced an efficient test pattern reordering algorithm, which achieves near constant power between groups of patterns. The number of patterns in a group is determined by the thermal constant of the chip. Experimental results show that our proposed power model has very good correlation. Our proposed X-Fill process achieved both minimum shift power and capture power. The algorithm supports multiple scan chains and can achieve constant power within different regions of the chip. The greedy test pattern reordering algorithm can reduce the power variation from 29-126 percent to 8-10 percent or even lower if we reduce the power variance threshold. Excessive noise can significantly affect the timing performance of Deep Sub-Micron (DSM) designs and cause non-trivial additional delay. In delay test generation, test compaction and test fill techniques can produce excessive power supply noise. This can result in delay test overkill. Prior approaches to power supply noise aware delay test compaction are too costly due to many logic simulations, and are limited to static compaction. We proposed a realistic low cost delay test compaction flow that guardbands the delay using a sequence of estimation metrics to keep the circuit under test supply noise more like functional mode. This flow has been implemented in both static compaction and dynamic compaction. We analyzed the relationship between delay and voltage drop, and the relationship between effective weighted switching activity (WSA) and voltage drop. Based on these correlations, we introduce the low cost delay test pattern compaction framework considering power supply noise. Experimental results on ISCAS89 circuits show that our low cost framework is up to ten times faster than the prior high cost framework. Simulation results also verify that the low cost model can correctly guardband every path‟s extra noise-induced delay. We discussed the rules to set different constraints in the levelized framework. The veto process used in the compaction can be also applied to other constraints, such as power and temperature.

In this dissertation, the design and analysis of several fast arithmetic components are presented. Our contributions focus on the fast CORDIC rotation architectures and multipliers. In the CORDIC design, we proposed a fast rotation architecture that can reduce by half the average number of rotations. Furthermore, a new parallel CORDIC rotation algorithm and architecture (called para-CORDIC) is proposed that leads to smaller area and delay compared with the conventional CORDIC algorithm and previous works. In the design of the multiplier generator, a delay-efficient algorithm is used to perform the partial products summation and the final addition during the synthesis of fast parallel multipliers based on standard cell library or other full-custom circuit components. In the field of fixed-width multiplier designs, a lower-error fixed-width carry-free multiplier with low-cost compensation circuits is proposed that has smaller absolute average errors and variances compared with pervious methods.