Projects

Power Grid Analysis	Data Mining
When designing large microprocessors, accurate simulation of the power distribution network is necessary. Electrical characteristics such as voltage drop and current density are computed to determine if the chip satisfies manufacturing reliability requirements. The electrical model for the power distribution network reduces to solving millions of equations of the form GV=I. The G matrix is a sparse symmetric positive definite matrix which models the resistance of wires in the power grid. New numercial solvers were developed to solve this large problem and were integrated into the IBM's IMaD and CPAM methodologies. Both programs find electromigration and IR drop problems. CPAM is used by designers before the chips are manufactured, while IMaD is used by chip manufacturing to monitor electrical changes in the chip due to process parameter variations. To efficiently place IO drivers on ASIC chips, a new placement algorithm was developed. The IOs are modeled as current sources on a power grid. By changing the location of the IOs, the voltage drops on the power grid change also. When GV=I is solved on each placement iteration, an optimal IO assignment is achieved which minimizes IR drop. This technique is currently in production use for IBM ASIC chips.	To optimize chip profit, speed sorting chips is critical. That is, being able to predict early in the manufacturing process which chips are slow and which chips are fast. Data mining techinques have been applied to this problem. By choosing the appropriate process parameters, several data mining techinques were implemented: classification trees kohonen neural nets principle components radial basis functions clustering (segmentation) cross validation linear discriminate response surface methodology To visualize the data, Java programs were written that displayed a matrix of scatter plots for the most important process parameters. Chip yield and performance were optimized based on these data mining algorithms and visualizations.

Power Grid Analysis

Data Mining

When designing large microprocessors, accurate simulation of the power distribution network is necessary. Electrical characteristics such as voltage drop and current density are computed to determine if the chip satisfies manufacturing reliability requirements.

The electrical model for the power distribution network reduces to solving millions of equations of the form GV=I. The G matrix is a sparse symmetric positive definite matrix which models the resistance of wires in the power grid. New numercial solvers were developed to solve this large problem and were integrated into the IBM's IMaD and CPAM methodologies. Both programs find electromigration and IR drop problems. CPAM is used by designers before the chips are manufactured, while IMaD is used by chip manufacturing to monitor electrical changes in the chip due to process parameter variations.

To efficiently place IO drivers on ASIC chips, a new placement algorithm was developed. The IOs are modeled as current sources on a power grid. By changing the location of the IOs, the voltage drops on the power grid change also. When GV=I is solved on each placement iteration, an optimal IO assignment is achieved which minimizes IR drop. This technique is currently in production use for IBM ASIC chips.

To optimize chip profit, speed sorting chips is critical. That is, being able to predict early in the manufacturing process which chips are slow and which chips are fast.

Data mining techinques have been applied to this problem. By choosing the appropriate process parameters, several data mining techinques were implemented:

classification trees
kohonen neural nets
principle components
radial basis functions
clustering (segmentation)
cross validation
linear discriminate
response surface methodology

To visualize the data, Java programs were written that displayed a matrix of scatter plots for the most important process parameters. Chip yield and performance were optimized based on these data mining algorithms and visualizations.

Custom Design	Array Logic & Verification
In this project, I developed new CAD algorithms for custom design. By actually doing custom design, I found new logic transforms and verification techniques that are useful enhancements to existing synthesis and verification programs. Several 64-bit adders have been designed including carry select, carry lookahead, Ling, and Brent-Kung. Using multi-bit transformations and pseudo propagates and carries, I optimized the logic to eight logic levels by using pass transistors and complex decode structures. The transistor sizes were tuned automatically using IBM's formal circuit tuning program. For timing to converge, accurate estimates of wire RC from a floorplan were used. New logic transforms were used that mapped complex gates into simpler gates by detecting redundancies in the design. For better diagnosis of a logic failure, I wrote a new Boolean verfication program. When counterexamples are detected, the input vectors are minimized so that isolation of logic errors is improved.	Programmable logic arrays (PLAs) are useful in implementing control logic. Instead of the usual AND-OR structures, logic can be factored into a 3-level AND-GAP-OR structure which is useful in optimizing dynamic PLAs. The Gap cells are small strobed AND-OR arrays which allow logic to be factored more efficiently so that circuit timing and area are improved. By using 2-bit decoders and new folding and partitioning algorithms, PLAs in many cases are faster than gate level designs created by logic synthesis. For fast Boolean verification, I have developed a new multi-valued Boolean verification engine. The algorithms transform binary valued logic into multi-valued array logic and then use this compact representation of Boolean functions to efficiently verify two logic networks. The array logic representation is much different than BDDs, and is efficient in verifying the functionality of combinational circuits. Several dataflow macros including adders, rotators, shifters, and parity trees were verified using these algorithms. A 64-bit adder was successfully verified in 0.5 seconds.

Custom Design

Array Logic & Verification

In this project, I developed new CAD algorithms for custom design. By actually doing custom design, I found new logic transforms and verification techniques that are useful enhancements to existing synthesis and verification programs.

Several 64-bit adders have been designed including carry select, carry lookahead, Ling, and Brent-Kung. Using multi-bit transformations and pseudo propagates and carries, I optimized the logic to eight logic levels by using pass transistors and complex decode structures.

The transistor sizes were tuned automatically using IBM's formal circuit tuning program. For timing to converge, accurate estimates of wire RC from a floorplan were used.

New logic transforms were used that mapped complex gates into simpler gates by detecting redundancies in the design.

For better diagnosis of a logic failure, I wrote a new Boolean verfication program. When counterexamples are detected, the input vectors are minimized so that isolation of logic errors is improved.

Programmable logic arrays (PLAs) are useful in implementing control logic. Instead of the usual AND-OR structures, logic can be factored into a 3-level AND-GAP-OR structure which is useful in optimizing dynamic PLAs. The Gap cells are small strobed AND-OR arrays which allow logic to be factored more efficiently so that circuit timing and area are improved.

By using 2-bit decoders and new folding and partitioning algorithms, PLAs in many cases are faster than gate level designs created by logic synthesis.

For fast Boolean verification, I have developed a new multi-valued Boolean verification engine. The algorithms transform binary valued logic into multi-valued array logic and then use this compact representation of Boolean functions to efficiently verify two logic networks.

The array logic representation is much different than BDDs, and is efficient in verifying the functionality of combinational circuits. Several dataflow macros including adders, rotators, shifters, and parity trees were verified using these algorithms. A 64-bit adder was successfully verified in 0.5 seconds.