Parallel circuit partitioning on a reduced array architecture

The physical design of a VLSI circuit involves circuit partitioning as a subtask. Typically, it is necessary to partition a large electrical circuit into several smaller circuits such that the total cross-wiring is minimized. This problem is a variant of the more general graph partitioning problem, and it is known that there does not exist a polynomial time algorithm to obtain an optimal partition. The heuristic procedure proposed by Kernighan and Lin1,2 requires O(n2 log2n) time to obtain a near-optimal two-way partition of a circuit with n modules. In the VLSI context, due to the large problem size involved, this computational requirement is unacceptably high. This paper is concerned with the hardware acceleration of the Kernighan-Lin procedure on an SIMD architecture. The proposed parallel partitioning algorithm requires O(n) processors, and has a time complexity of O(n log2n). In the proposed scheme, the reduced array architecture is employed with due considerations towards cost effectiveness and VLSI realizability of the architecture.The authors are not aware of any earlier attempts to parallelize a circuit partitioning algorithm in general or the Kernighan-Lin algorithm in particular. The use of the reduced array architecture is novel and opens up the possibilities of using this computing structure for several other applications in electronic design automation.

Equivalent circuit parameters of the film-covered magnesium/electrolyte interface in Mg/MnO2 dry cells from transient and ac impedance measurements

The electrochemical properties of the film-covered anode/solution interface in the magnesium/ manganese dioxide dry cell have been evaluated. The most plausible electrical equivalent circuit description of the Mg/solution interface with the passive film intact, has been identified. These results are based on the analysis of ac impedance and voltage transient measurements made on the dry cell under conditions which cause no damage to the protective passive film on the anode. The study demonstrates the complementary character of impedance and transient measurements when widely different frequency ranges are sampled in each type of investigation. The values and temperature dependence of the anode-film resistance, film capacitance, double-layer capacitance and charge-transfer resistance of the film-covered magnesium/solution interface have been determined. The magnitude of these values and its implications in understanding the important performance aspects of the magnesium/manganese dioxide dry cell are discussed. The study may be extended, in principle, to Li, Al and Ca batteries.

Equivalent circuit parameters of the film-covered magnesium/electrolyte interface in Mg/MnO2 dry cells from transient and ac impedance measurements

The electrochemical properties of the film-covered anode/solution interface in the magnesium/ manganese dioxide dry cell have been evaluated. The most plausible electrical equivalent circuit description of the Mg/solution interface with the passive film intact, has been identified. These results are based on the analysis of ac impedance and voltage transient measurements made on the dry cell under conditions which cause no damage to the protective passive film on the anode. The study demonstrates the complementary character of impedance and transient measurements when widely different frequency ranges are sampled in each type of investigation. The values and temperature dependence of the anode-film resistance, film capacitance, double-layer capacitance and charge-transfer resistance of the film-covered magnesium/solution interface have been determined. The magnitude of these values and its implications in understanding the important performance aspects of the magnesium/manganese dioxide dry cell are discussed. The study may be extended, in principle, to Li, Al and Ca batteries.

Efficient algorithms for domination and Hamilton circuit problems on permutation graphs

The domination and Hamilton circuit problems are of interest both in algorithm design and complexity theory. The domination problem has applications in facility location and the Hamilton circuit problem has applications in routing problems in communications and operations research.The problem of deciding if G has a dominating set of cardinality at most k, and the problem of determining if G has a Hamilton circuit are NP-Complete. Polynomial time algorithms are, however, available for a large number of restricted classes. A motivation for the study of these algorithms is that they not only give insight into the characterization of these classes but also require a variety of algorithmic techniques and data structures. So the search for efficient algorithms, for these problems in many classes still continues.A class of perfect graphs which is practically important and mathematically interesting is the class of permutation graphs. The domination problem is polynomial time solvable on permutation graphs. Algorithms that are already available are of time complexity O(n2) or more, and space complexity O(n2) on these graphs. The Hamilton circuit problem is open for this class.We present a simple O(n) time and O(n) space algorithm for the domination problem on permutation graphs. Unlike the existing algorithms, we use the concept of geometric representation of permutation graphs. Further, exploiting this geometric notion, we develop an O(n2) time and O(n) space algorithm for the Hamilton circuit problem.

Open-circuit potential—time transients of alkaline porous iron electrodes at various states-of-charge

Open-circuit potential—time transients during the discharge of alkaline porous iron electrodes at various states-of-charge have been studied. From this, it has been possible to arrive at a correlation between the parameters of self-discharge kinetics of the electrode and observed open-circuit potential—recovery time constants. The study provides a method of estimate the state-of-charge of the rechargeable iron electrodes. As a hydrogen evolution reaction inevitably occurs on alkaline iron electrodes, the kinetics of the reaction have also been investigated.

Estimation Of Charge Transport Parameters And Equivalent Circuit For Poly Alkyl Thiophene Field-Effect Transistors

The small signal ac response is measured across the source-drain terminals of organic field-effect transistors (OFET) under dc bias to obtain the equivalent circuit parameters of poly(2,5-bis(3-tetradecylthiophen-2-yl)thieno[3,2-b]thiophene) (PBTTT) and poly(3-hexyl thiophene) (P3HT) based devices. The numerically simulated response based on these parameters is in good agreement with the experimental data for PBTTT-FET except at low frequencies, while the P3HT-FET data show significant deviations. This indicates that the interface with the metal electrode is rather complex for the latter, involving additional circuit elements arising from contact impedance or charge injection processes. Such an investigation can help in identifying the operational bottlenecks and to improve the performance of OFETs.

Circuit layout through an analogy with neural networks

Standard-cell design methodology is an important technique in semicustom-VLSI design. It lends itself to the easy automation of the crucial layout part, and many algorithms have been proposed in recent literature for the efficient placement of standard cells. While many studies have identified the Kerninghan-Lin bipartitioning method as being superior to most others, it must be admitted that the behaviour of the method is erratic, and that it is strongly dependent on the initial partition. This paper proposes a novel algorithm for overcoming some of the deficiencies of the Kernighan-Lin method. The approach is based on an analogy of the placement problem with neural networks, and, by the use of some of the organizing principles of these nets, an attempt is made to improve the behavior of the bipartitioning scheme. The results have been encouraging, and the approach seems to be promising for other NP-complete problems in circuit layout.

A Circuit-Based Proof of Toda′s Theorem

We present a simple proof of Toda′s result (Toda (1989), in "Proceedings, 30th Annual IEEE Symposium on Foundations of Computer Science," pp. 514-519), which states that circled plus P is hard for the Polynomial Hierarchy under randomized reductions. Our approach is circuit-based in the sense that we start with uniform circuit definitions of the Polynomial Hierarchy and apply the Valiant-Vazirani lemma on these circuits (Valiant and Vazirani (1986), Thoeret. Comput. Sci.47, 85-93).

A simple equivalent circuit analysis of rectangular folded-waveguide slow-wave structure

A simple yet accurate equivalent circuit model was developed for the analysis of slow-wave properties (dispersion and interaction impedance characteristics) of a rectangular folded-waveguide slow-wave structure. Present formulation includes the effects of the presence of beam-hole in the circuit, which were ignored in existing approaches. The analysis was benchmarked against measurement as well as with 3D electromagnetic modeling using MAFIA for two typical slow-wave structures operating in Ka- and Q-bands, and close agreements were observed. The analysis was extended for demonstrating the effect of the variation of beam-hole radius on the RF interaction efficiency of the device. (C) 2009 Elsevier GmbH. All rights reserved.

Hierarchies of circuit classes that are closed under complement

We examine three hierarchies of circuit classes and show they are closed under complementation. (1) The class of languages recognized by a family of polynomial size skew circuits with width O(w), are closed under complement. (2) The class of languages recognized by family of polynomial size circuits with width O(w) and polynomial tree-size, are closed under complement. (3) The class of languages recognized by a family of polynomial size, O(log(n)) depth, bounded AND fan-in with OR fan-in f (f⩾log(n)) circuits are closed under complement. These improve upon the results of (i) Immerman (1988) and Szelepcsenyi (1988), who show that 𝒩L𝒪𝒢 is closed under complementation, and (ii) Borodin et al. (1989), who show that L𝒪𝒢𝒞ℱL is closed under complement

Hybrid LCI/VSI Power Circuit-A Universal High-Power Converter Solution for Wound Field Synchronous Motor Drives

Load commutated inverter (LCI)-fed wound field synchronous motor drives are used for medium-voltage high-power drive applications. This drive suffers from drawbacks such as complex starting procedure, sixth harmonic torque pulsations, quasi square wave motor current, notches in the terminal voltages, etc. In this paper, a hybrid converter circuit, consisting of an LCI and a voltage source inverter (VSI), is proposed, which can be a universal high-power converter solution for wound field synchronous motor drives. The proposed circuit, with the addition of a current-controlled VSI, overcomes nearly all of the shortcomings present in the conventional LCI-based system besides providing many additional advantages. In the proposed drive, the motor voltage and current are always sinusoidal even with the LCI switching at the fundamental frequency. The performance of the drive is demonstrated with detailed experimental waveforms from a 15.8-hp salient pole wound field synchronous machine. Finally, a brief description of the control scheme used for the proposed circuit is given.

An Investigation into the Dependence of the Arc Voltage on the Parameters of the Short-Circuit Current and the Design of the Vacuum Interrupter

The vacuum interrupter is extensively employed in the medium voltage switchgear for the interruption of the short-circuit current. The voltage across the arc during current interruption is termed as the arc voltage. The nature and magnitude of this arc voltage is indicative of the performance of the contacts and the vacuum interrupter as a whole. Also, the arc voltage depends on the parameters like the magnitude of short-circuit current, the arcing time, the point of opening of the contacts, the geometry and area of the contacts and the type of magnetic field. This paper investigates the dependency of the arc voltage on some of these parameters. The paper also discusses the usefulness of the arc voltage in diagnosing the performance of the contacts.

Bounds on Defect Level and Fault Coverage in Linear Analog Circuit Testing

Transfer function coefficients (TFC) are widely used to test linear analog circuits for parametric and catastrophic faults. This paper presents closed form expressions for an upper bound on the defect level (DL) and a lower bound on fault coverage (FC) achievable in TFC based test method. The computed bounds have been tested and validated on several benchmark circuits. Further, application of these bounds to scalable RC ladder networks reveal a number of interesting characteristics. The approach adopted here is general and can be extended to find bounds of DL and FC of other parametric test methods for linear and non-linear circuits.

Modeling of the Effects of Process Variations on Circuit Delay at 65nm

A novel methodology for modeling the effects of process variations on circuit delay performance is proposed by relating the variations in process parameters to variations in delay metric of a complex digital circuit. The delay of a 2-input NAND gate with 65nm gate length transistors is extensively characterized by mixed-mode simulations which is then used as a library element. The variation in saturation current Ionat the device level, and the variation in rising/falling edge stage delay for the NAND gate at the circuit level, are taken as performance metrics. A 4-bit x 4-bit Wallace tree multiplier circuit is used as a representative combinational circuit to demonstrate the proposed methodology. The variation in the multiplier delay is characterized, to obtain delay distributions, by an extensive Monte Carlo analysis. An analytical model based on CV/I metric is proposed, to extend this methodology for a generic technology library with a variety of library elements.