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

Singularity structure and chaotic behavior of the homopolar disk dynamo

We study in great detail a system of three first-order ordinary differential equations describing a homopolar disk dynamo (HDD). This system displays a large variety of behaviors, both regular and chaotic. Existence of periodic solutions is proved for certain ranges of parameters. Stability criteria for periodic solutions are given. The nonintegrability aspects of the HDD system are studied by investigating analytically the singularity structure of the system in the complex domain. Coexisting attractors (including period-doubling sequence) and coexisting strange attractors appear in some parametric regimes. The gluing of strange attractors and the ungluing of a strange attractor are also shown to occur. A period of bifurcation leading to chaos, not observed for other chaotic systems, is shown to characterize the chaotic behavior in some parametric ranges. The limiting case of the Lorenz system is also studied and is related to HDD.

On the integrability and chaotic behavior of an ecological model

A three-species food chain model is studied analytically as well as numerically. Integrability of the model is studied using Painleve analysis while chaotic behavior is studied using numerical techniques, such as calculation of Lyapunov exponents, plotting the bifurcation diagram and phase plots. We correct and critically comment on the wrong results reported recently on this ecological model, in a paper by Rai [1995].

Predictive uncertainty of chaotic daily streamflow using ensemble wavelet networks approach

Perfect or even mediocre weather predictions over a long period are almost impossible because of the ultimate growth of a small initial error into a significant one. Even though the sensitivity of initial conditions limits the predictability in chaotic systems, an ensemble of prediction from different possible initial conditions and also a prediction algorithm capable of resolving the fine structure of the chaotic attractor can reduce the prediction uncertainty to some extent. All of the traditional chaotic prediction methods in hydrology are based on single optimum initial condition local models which can model the sudden divergence of the trajectories with different local functions. Conceptually, global models are ineffective in modeling the highly unstable structure of the chaotic attractor. This paper focuses on an ensemble prediction approach by reconstructing the phase space using different combinations of chaotic parameters, i.e., embedding dimension and delay time to quantify the uncertainty in initial conditions. The ensemble approach is implemented through a local learning wavelet network model with a global feed-forward neural network structure for the phase space prediction of chaotic streamflow series. Quantification of uncertainties in future predictions are done by creating an ensemble of predictions with wavelet network using a range of plausible embedding dimensions and delay times. The ensemble approach is proved to be 50% more efficient than the single prediction for both local approximation and wavelet network approaches. The wavelet network approach has proved to be 30%-50% more superior to the local approximation approach. Compared to the traditional local approximation approach with single initial condition, the total predictive uncertainty in the streamflow is reduced when modeled with ensemble wavelet networks for different lead times. Localization property of wavelets, utilizing different dilation and translation parameters, helps in capturing most of the statistical properties of the observed data. The need for taking into account all plausible initial conditions and also bringing together the characteristics of both local and global approaches to model the unstable yet ordered chaotic attractor of a hydrologic series is clearly demonstrated.

Nonlinear dynamics and chaotic motions in feedback-controlled two- and three-degree-of-freedom robots

The dynamics of a feedback-controlled rigid robot is most commonly described by a set of nonlinear ordinary differential equations. In this paper we analyze these equations, representing the feedback-controlled motion of two- and three-degrees-of-freedom rigid robots with revolute (R) and prismatic (P) joints in the absence of compliance, friction, and potential energy, for the possibility of chaotic motions. We first study the unforced or inertial motions of the robots, and show that when the Gaussian or Riemannian curvature of the configuration space of a robot is negative, the robot equations can exhibit chaos. If the curvature is zero or positive, then the robot equations cannot exhibit chaos. We show that among the two-degrees-of-freedom robots, the PP and the PR robot have zero Gaussian curvature while the RP and RR robots have negative Gaussian curvatures. For the three-degrees-of-freedom robots, we analyze the two well-known RRP and RRR configurations of the Stanford arm and the PUMA manipulator respectively, and derive the conditions for negative curvature and possible chaotic motions. The criteria of negative curvature cannot be used for the forced or feedback-controlled motions. For the forced motion, we resort to the well-known numerical techniques and compute chaos maps, Poincare maps, and bifurcation diagrams. Numerical results are presented for the two-degrees-of-freedom RP and RR robots, and we show that these robot equations can exhibit chaos for low controller gains and for large underestimated models. From the bifurcation diagrams, the route to chaos appears to be through period doubling.