Narrow Results

The bipartization problem for a graph $G$ asks for finding a subset $S$ of $V(G)$ such that the induced subgraph $G[S]$ is bipartite and $\left|S\right|$ is maximized. This problem has significant applications in the via minimization of VLSI design. The problem has been proved NP-complete and the fixed parameter solvability has been known in the literature. This paper presents several polynomial-time algorithms for special graph families, such as split graphs, co-bipartite graphs, chordal graphs, and permutation graphs.

Modular adders are met in various applications of computer systems. In this paper, we investigate a new architecture for their design that utilizes a carry save adder stage and two binary adders that operate in parallel. Realizations in static CMOS reveal that the introduced architecture leads to modular adder implementations that offer significant savings in delay and power consumption over implementations based on previously proposed architectures. In parallel, the proposed architecture offers significantly smaller implementation area for small operand widths.

An original low-power low-voltage multifunctional structure with improved performances will be further presented, allowing to implement (with minor changes in the design) four important functions: the signal gain with theoretical null distortions, voltage multiplying with very good linearity and simulation of a perfect linear resistor with both positive and negative equivalent resistance. The linearity will be strongly increased by implementing original techniques, while the silicon occupied area per function will be reduced as a result of the circuit multifunctionality. The structure is implemented in 0.35 μm CMOS technology and is supplied at ±3 V. The circuit presents a very good linearity (THD < 0.1% for differential amplifier and active resistors and THD < 0.15% for multiplier), correlated with an extended range of the input voltage (-1.5V < v₁ - v₂ < 1.5 V). The tuning range of the active resistor is about 100kΩ – 1.5MΩ. The second-order effects are also considered, being proposed an original technique based on an anti-parallel connection for compensating the linearity degradation introduced by these effects.

In this paper, multifunction residue number system (RNS) modulo (2ⁿ ± 1) multipliers are proposed. By adopting common circuits for summing up the partial products with extra controls, our proposed multipliers could perform both modulo (2ⁿ + 1) and (2ⁿ - 1) multiplications. The levels for summation of partial products are n + 1, which are same as the conventional modulo multipliers which with only one kind of modulo multiplications. The proposed multifunction modulo (2ⁿ ± 1) multipliers can save at least about 42.5% area under the same delay constraints and above 65.8% Area × Delay Product (ADP) compared with the one composed of modulo (2ⁿ + 1) and modulo (2ⁿ - 1) multiplication operations. Our proposed multipliers could be applied to ease the tremendous computation overload in the real-time processing applications.

Tight time-to-market pressure requires CAD tools to heavily involve component reuse, or intellectual property (IP) reuse, which imposes intense security concerns on IP protection. For the IP providers, it is critical to protect their products against unauthorized reproduction. Thus, circuit layout fingerprinting becomes quite important which helps the IP providers to detect which user distributes the illegal IPs. However, previous works addressing the circuit fingerprinting all have large area and runtime overhead. In this paper, a novel efficient discrete wavelet transform (DWT)-based key sensitive circuit layout fingerprinting technique using chaotic system is proposed. The new circuit layout fingerprinting technique targets to be applied after placement and routing, while before fabrication. Thus, it only slightly impacts the original design and introduces small runtime overhead as well. To further enhance the security, the chaotic system based on Fibonacci transformation is integrated. The experimental results demonstrate that our chaotic DWT-based technique largely outperforms a median-based technique for various attacks. The chaotic DWT-based technique improves the detection error rate by 68.5% for the gate swapping attack, by 65.8% for the random perturbation attack, by 54.8% for the partition-based perturbation attack and by 54.5% for the combined perturbation attack. In addition, the average wirelength overhead is only 0.0149% compared to the original design and the average runtime overhead is only 6.73 s. These demonstrate the effectiveness of our circuit layout fingerprinting technique.

Most recent microprocessors present multiple special functional units to optimize their performance. In this paper, a new functional unit called the calculation and anticipation (C&A) unit is presented for the IEEE 754 standard floating-point adder (FPA) that is the most important and frequently used calculation part for both modern CPUs and GPUs. C&A unit parallelize rounding step and readjustment step, which are known as the time-consuming steps for floating-point addition with significand addition. Therefore it reduces FPA critical path delay enormously, and even more decreases a little FPA area occupation. The synthesis results show that the double-precision FPA with C&A unit takes about 17.17% improvement in the critical path delay, while saves about 8.32% area than the conventional one. It takes 5.90% advantage in area and 19.58% improvement in the worst case delay than the double-precision FPA from the Open Core module "fpu_double" (rev 14 2010-02-13) synthesized in the same 0.13-μm CMOS bulk. Furthermore, comparing with the two-path double-precision FPA synthesized using LSI Logic's gflxp 0.11-μm CMOS library, it takes about 4.30% advantage in the critical path delay, and saves almost one-third area in the number of the individual cells.

Given a point set K of terminals in the plane, the octilinear Steiner tree problem is to find a shortest tree that interconnects all terminals and edges run either in horizontal, vertical, or ±45° diagonal direction. This problem is fundamental for the novel octilinear routing paradigm in VLSI design, the so-called X-architecture.

As the related rectilinear and the Euclidian Steiner tree problem are well-known to be NP-hard, the same was widely believed for the octilinear Steiner tree problem but left open for quite some time. In this paper, we prove the NP-completeness of the decision version of the octilinear Steiner tree problem.

We also show how to reduce the octilinear Steiner tree problem to the Steiner tree problem in graphs of polynomial size with the following approximation guarantee. We construct a planar graph of size which contains a (1 + ε)–approximation of a minimum octilinear Steiner tree for every ε > 0 and n = |K|. Hence, we can apply any α–approximation algorithm for the Steiner tree problem in graphs (for planar graphs, Borradaile et al. very recently presented a polynomial time approximation scheme) and achieve an (α + ε)–approximation bound for the octilinear Steiner tree problem. This approximation guarantee also holds for the more difficult case where the Steiner tree has to avoid blockages (obstacles bounded by octilinear polygons).

Cell placement in VLSI design is an NP-complete problem. In this paper, we have tried to solve the standard cell placement problem using the Hopfield neural network model. Furthermore, a new system of coupled recurrent neural networks, which was designed to eliminate the drawbacks of the Hopfield neural network, is introduced.

The performance of Hopfield networks with discrete and graded neurons is also investigated. The energy function corresponding to the chosen representation is given and the weight matrix and the inputs needed for the network are also computed in this work. Several different combinations of parameters were examined to find the optimum set of parameters which results in better and faster convergence.

To show the effectiveness of our methods, cell placement problems up to 30 cells are considered and the results are compared with the results obtained by a genetic algorithm. Our results show that a system of coupled neural networks could be an efficient way to overcome the limitation of recurrent neural networks which consider only bilinear forms of the energy function.