We present an analytical expression for the evaluation of the short-circuit power dissipation in a CMOS inverter driving a CRC interconnect load. The validity of the model is much improved over previous works that inaccurately model a MOS transistor as a piecewise linear element, inadequately consider short-circuit current, or inappropriately apply the total capacitance approach. Moreover, our method requires less characterization effort while considering short-channel effects and secondary effects such as short-circuit current and coupling capacitance. As a result of this analysis, the results from proposed model are very close to those of SPICE3.

The authors present a new kind of CMOS logic circuit that has a different structure and different operation mechanism compared to the existing logic circuits. Its unique delay propagation characteristic makes it much faster than the conventional CMOS logic gate. Gate outputs are preconditioned to a voltage level between V/sub dd/ and V/sub ss/ using a new clocking scheme and circuit design. They give a buffer design example which is about 6.5 times faster than the conventional buffer. The total energy consumed by the new circuit structure is slightly more than conventional CMOS domino logic; however the energy-delay product is smaller.

Fault tolerant algorithms are presented for broadcasting on the star graph. In our algorithm, fault tolerance is achieved by constructing an isomorphism of the star network, such that the faulty nodes minimally disrupt the message passing sequence. It is shown that, in the presence of r(1/spl les/r/spl les/k-2) faults, at most r extra steps are required by our algorithm to perform a one-to-all broadcasting in the k-star network. Our algorithm has the same time complexity as an optimal broadcasting algorithm, and, since it takes advantage of the hierarchical nature of the star graph network, it can be implemented easily. Our algorithm can also be used to perform all-to-all broadcasting in a faulty star graph.

This paper explores parallel logic simulation on a network of workstations using a parallel virtual machine (PVM). A novel parallel implementation of the centralized-time event-driven logic simulation algorithm is carried out such that no global controlling workstation is needed to synchronize the advance of simulation time. Further advantages of our new approach include a random partitioning of the circuit onto available workstations and a pipelined execution of the different phases of the simulation algorithm. To achieve a better load balance, we employ a semioptimistic scheme for gate evaluations (in conjunction with a centralized-time algorithm) such that no rollback is required. The performance of this implementation has been evaluated using the ISCAS benchmark circuits. Speedups improve with the size of the circuit and the activity level in the circuit. Analyses of the communication overhead show that the techniques developed here will yield even higher gains as newer networking technologies like ATM are employed to connect workstations.

A technique for chaining the transistors in the layouts of static CMOS leaf cells is presented and analyzed. This new method is superior to existing techniques, since it can operate on a more general class of circuits and is very efficient. It is shown that the layout width of a CMOS leaf cell can be significantly reduced (nearly 40% in the average case) by transistor chaining. Moreover, more than half of the switching functions of four variables have optimal CMOS circuit implementations with non-series/parallel topologies. Therefore, the use of non-series/parallel circuits can have a positive global impact on layout area and performance. The transistor chaining technique presented in this paper produces the optimal solution for 82% of the circuits tested, and has linear time complexity.

We present a new design technique for the concurrent error correction of single event upsets in the memory elements of ASICs. The technique uses a single error correction/double error detection (SEC/DED) Hamming code to encode the content of the memory elements. The area and delay overhead and error-correction capability are optimized by partitioning the set of memory elements. Design experiments show our technique is feasible, and it can be applied to any ASIC technology.

A plane multigraph is said to be dual Eulerian if both it and its dual contain an Euler path or circuit and the Euler paths have corresponding edge sequences. In this paper several properties of plane multigraphs are derived, and a necessary and sufficient condition for a plane multigraph to be dual Eulerian is given. Although the necessary and sufficient condition for a multigraph to be Eulerian is somewhat trivial, the necessary and sufficient condition for a plane multigraph to be dual Eulerian is not. Nevertheless, the question of whether or not a plane multigraph is dual Eulerian can be answered in time proportional to a linear function of the number of edges of the graph, and an algorithm that answers this question is presented in this paper. This theory can be applied to the layout synthesis of functional cells for Complementary Metal-Oxide Semiconductor Very Large-Scale Integrated circuits.

In this paper the effects of transistor reordering on the delay of CMOS digital circuits are investigated, and an efficient method which uses transistor reordering for the delay optimization of CMOS circuits is presented. The proposed technique achieves significant reduction in propagation delays with little effect on layout area and power dissipation. The technique can be coupled with transistor sizing to achieve the desired improvement in circuit delay. Experimental results for benchmark circuits are given in 2.0, 1.2, and 0.8 /spl mu/m CMOS technologies. The average improvement in delay for the 20 benchmarks used in this paper is 9.1%.>

In standard cell design, many cell terminals and gates are permutable, and it is important for a channel router to take advantage of this to obtain better results. An efficient hierarchical algorithm is presented to determine the proper positions of permutable gates and cell terminals such that the results of the subsequent channel routing can be significantly improved. Experimental results show that our proposed algorithm considerably reduces the number of tracks and vias, and its time complexity is linear in the number of cell terminals.>

A CAD tool, LILA, that generates layouts of both one-dimensional and two-dimensional iterative logic arrays, described in VHDL or schematic structures, is presented. Such a tool is very important because in current industry, the generation of high density iterative logic arrays (such as data paths in microprocessors) is still mainly performed manually, and is a major bottleneck of the design. In LILA, interconnections between modules (i.e., cells) of the array do not need to be between adjacent modules and functions of modules of the array do not need to be identical. Regularity in module functions and interconnections between modules are automatically extracted by the tool. Based on interconnection wire length between modules, layouts of modules and interconnections are optimized in a single step. The signals in each array module are generated in such a way that signals in adjacent modules are perfectly aligned and connected by module abutments. As no global routing or channel routing between modules are necessary, the total layout area and propagation delay between modules are minimal. The proposed system is especially useful for data path modules, bit-level systolic arrays, storage devices, and many other regular structures, and has been actually implemented in a design environment. Extensive experiments have shown that the system has a very good performance and produces layouts of very high density. The tool takes about 1.6 CPU seconds to generate an eight-by-eight array divider on a SUN SPARCstation II.>

A unified algorithm is presented to solve the problem of estimation and scheduling for performance constrained data path synthesis. The algorithm achieves superior results by first computing a lower bound on the number of functional units required to satisfy the performance constraint T, and then scheduling the operations into the best control steps using the lower bound algorithm. The lower bound not only greatly reduces the size of the solution space, but also provides a means to measure the proximity of the final solution to an optimal one. Our unified algorithm can also be incorporated in a branch-and-bound algorithm to solve the scheduling problem optimally. Experiments indicate that our scheduling algorithm can produce results very close to the lower bound. For all of the test cases the difference between our upper and lower bounds is not greater than one.>

In this paper lower bounds for the performance constrained and resource constrained scheduling of tasks on multiprocessors are presented. The lower bounds derived here are sharper than previously known results and the time complexity of their computation is only slightly greater.>

A method which uses transistor reordering for the performance enhancement of CMOS circuits is presented.The proposed technique achieves significant reduction in propagation delays with little effect on layout area.The technique can be coupled with transistor sizing to achieve unbounded inlprovement in circuit delay, and it can be used to decrease dynamic power dissipation.In particular, excellent results have been achieved when the n~ethod is applied to data path circuits.I

An algorithm is presented to determine two lower bounds in functional pipelined data path synthesis. Given an iteration time constraint and a task initiation latency, the algorithm computes a lower bound on the number of functional units required to execute the data flow graph (DFG) of a loop body, and given a resource constraint and a task initiation latency the algorithm computes a lower bound on the number of time steps required to execute the DFG. The lower bounds not only greatly reduce the size of the solution space, but also provide a means to measure the proximity of the final solution to an optimal one. The bounds are computed in polynomial time; therefore the algorithm is very effective, especially for large DFGs. Experiments indicate that the lower bound is very tight. For all of the test cases the difference between our solution and the optimal solution is not greater than one.>

Many optimization algorithms have been proposed for layout styles which are dual dependent: that is, the optimization for the layout of the n-transistor network of a CMOS complex gate is dependent on, the p-transistor network and vice versa. A two-stage linear-time optimization algorithm for dual independent layout styles is presented. The first stage is based on a tree representation of the complex gate. This tree representation allows complete flexibility in transistor order and takes complete advantage of the concept of delayed binding. The optimization goal is identical to the Euler pathed optimization algorithms metal-metal matrix (M/sup 3/) layout style, and examples of generated layouts are shown. Starting from a switching expression, the proposed algorithm always produces an optimal solution in terms of the number of diffusion breaks, which includes an optimal transistor representation for the switching expression (first stage), and an optimal gate sequence to traverse this transistor circuit (second stage).>