This paper proposes a new environment for high-level VLSI design specification validation using "Algorithmic Debugging" and evaluates its benefits on three significant examples (a protocol processor, an 8-bit CPU, and a Prolog processor). A design is specified at a high-level using the structured analysis (SA) method, which is useful for analyzing and understanding the functionality to be realized. The specification written in SA is transformed into a logic programming language and is simulated in it. The errors (which terminate with an incorrect output in the simulation) included in the three large examples are efficiently located by answering junt a few queries from the algorithmic debugger. The number of interactions between the designer and the debugger is reduced by a factor of ten to a hundred compared to conventional simulation based validation methodologies. The correct SA specification can be automatically translated into a Register Transfer Level (RTL) specification suitable for logic synthesis. In this environment, a designer is freed from the tedious task of debugging a RTL specification, and can concentrate on the design itself. This environment promises to be an important step towards efficient high-level VLSI design specification validation.

A new approach is described for the datapath scheduling of behavioral descriptions containing nested conditional branches of arbitrary structures. This paper first investigates such a complex scheduling mechanism, and formulates an optimal scheduling problem as a 0-1 integer programming problem such that given a prescribed number of control steps, the total cost of functional units can be minimized. In this formulation, each constraint is expressed in the form of a Boolean function, which is set equal to 1 or 0 according as the constraint is satisfied or not, respectively, and a satisfiability problem is defined by the product of the Boolean functions. A procedure is then described, which intends to seek an optimal solution by means of a branch-and-bound method on a binary decision diagram representing the satisfiability problem. Experimental results are also shown, which demonstrate that our approach is of more practical use than the existing methods.

This paper presents a method, called reduced scan shift, which generates short test sequences for full scan circuits. In this method, scan shift operations can be reduced, i.e., not all but part of flip-flops (FFs) are controlled and observed. This method, unlike partial scan methods, does not decrease fault coverage. In the reduced scan shift, test vectors for the combinational part of a circuit are fistly generated. Since short test sequence will be obtained from the small test vectors set, test compaction techniques are used in the test vector generation. For each test vector in the obtained test set, it is found which FFs should be controlled or observed. And then a scan chain is configured so that FFs more frequently required to be controlled (observed) can be located close to the scan input (output). After the scan chain is configured, the scan shift requirement is examined for the essential faults of each test vector. Essential fault is defined to be a fault which is detected by only one test vector but not other test vectors. The order of test vectors is carefully determined by comparing the scan control requirement of a test vector with the scan observation requirement of another test vector so that unnecessary scan shift operations only for controlling or observing FFs can be reduced. A method of determining the order of test vectors with state transition is additionally described. The effectiveness of the proposed method is shown by the experimental results for benchmark circuits.

This paper discusses pulse responses of multi-conductor transmission lines terminated by linear and nonlinear subnetworks. At first step, the circuit is partitioned into a linear transmission lines and nonlinear subnetworks by the substitution voltage sources. Then, the linear subnetworks are solved by a well-known phasor technique, and the nonlinear subnetworks by a numerical integration technique. The variational value at each iteration is calculated by a frequency domain relaxation method to the associated linearized time-invariant sensitivity circuit. Although the algorithm can be efficiently applied to weakly nonlinear circuits, the convergence ratio for stiff nonlinear circuits becomes very small. Hence, we recommend to introduce a compensation element which plays very important role to weaken the nonlinearity. Thus, our algorithm is very simple and can be efficiently applied to wide classes of nonlinear circuits.

Technology mapping algorithms for LUT (Look Up Table) based FPGAs have been proposed to transfer a Boolean network into logic-blocks. However, since those algorithms take no layout information into account, they do not always lead to excellent results. In this paper, a simultaneous technology mapping, placement and global routing algorithm for FPGAs, Maple, is presented. Maple is an extended version of a simultaneous placement and global routing algorithm for FPGAs, which is based on recursive partition of layout regions and block sets. Maple inherits its basic process and executes the technology mapping simultaneously in each recursive process. Therefore, the mapping can be done with the placement and global routing information. Experimental results for some benchmark circuits demonstrate its efficiency and effectiveness.

The graph bisection problem is to partition a given graph into two subgraphs with equal size with minimizing the cutsize. This problem is NP-hard, and hence several heuristic algorithms have been proposed. Among them, the Kernighan-Lin algorithm and the Fiduccia-Mattheyses algorithm are well known, and widely used in practical applications. Since those algorithms are iterative improvement algorithms, in which the current solution is iteratively improved by interchanging a pair of two nodes belonging to different subgraphs, or moving one node from one subgraph to the other, those algorithms tend to fall into a local optimum. In this paper, we present a heuristic algorithm based on subgraph migration to avoid falling into a local optimum. In this algorithm, an initial solution is given, and it is improved by moving a subgraph, which is effective to reduce the cutsize. The algorithm repeats this operation until no further improvement can be achieved. Finally, the balance of the bisection is restored by moving nodes to get a final solution. Experimental results show that the proposed algorithm gets better solutions than the Kernighan-Lin and Fiduccia-Mattheyses algorithms.

This paper describes a new clustering approach for VLSI placement, which is based on a fractal dimension analysis for the topological structure of modules in a logic diagram. A distinctive feature of this approach is that a measure of the 'fractal dimension' has been introduced into a logic diagram in such a way that the clustering of modules is iterated while the fractal dimension among clustered modules is retained in a prescribed range. A part of experimental results is also shown, which demonstrates that our clustering approach raises the placement performance much higher than the conventional clustering methods.

This paper presents a heuristic floorplanning method that improves the method proposed by Vijayan and Tsay. It is based on tentative insertion of constraints, that intentionally produces redundant constraints to make it possible to search in a wide range of solution space. The proposed method can reduce the total area of blocks with the removal and insertion of constraints on the critical path in both horizontal and vertical constraint graphs. Experimental results for MCNC benchmarks showed that the quality of solutions of the proposed method is better than [7],[8] by about 15% on average, and even for the large number of blocks, the proposed method keeps the high quality of solutions.

A timing-driven global routing algorithm is proposed that directly models the path-based timing constraints. By keeping track of the critical path delay and channel densities, and using novel heuristic criteria, it can select routing paths that minimize area as well as satisfy the timing constraints. Using bipolar-specific features, this router can be used to design LSI chips that handle signals with speeds greater that a gigabit per second. Experimental results shows an average delay improvement of 17.6%.

This paper presents a fast and practical routing algorithm implemented on a supercomputer. In previously reported work, routing has been accelerated by executing the maze algorithm on parallel processing elements. However, although many parallel algorithms and special architectures have been introduced, practical aspects have not been addressed. We therefore present a novel approach that uses a vector processor as a routing accelerator and a wavefront control algorithm in order to avoid the wasteful searches that often occur in industrial routing problems. Experimental results that show the performance of a supercomputer using these algorithms is equivalent to over 1800 VAXMIPS, the fastest yet reported for routing accelerators. Results with industrial data also prove the validity of our approach.

Genetic algorithms have been shown to be very useful in a variety of search and optimization problems. In this paper, we propose a modified genetic channel router. We adopt the compatible crossover operator and newly designed compatible mutation operator in order to search solution space more effectively, where vertical constraints are integrated. By carefully selected fitness function forms and optimized genetic parameters, the current version speeds up benchmarks on average about 5.83 times faster than that of our previous version. Moreover the total convergence to optimal solutions for benchmarks can be always obtained.

We present a new multi-layer over-the-cell channel router for standard cell layout design using simulated annealing. This new approach, STANZA-M consists of two key features. The first key feature of our router is a new scheme for simulated annealing in which we use a cost function to evaluate both the total net-length and the channel heights, and an effective simulated annealing process by a limited range to obtain an optimal chnnel wiring in practical time. The second feature of our router is a basic layer assignment procedure in which we assign all horizontal wiring inside a channel to feasible layers by considering the height of channel including cell region with a one dimensional channel compaction process. We implemented our three-layer cannel router in C language on a Solbourne Series 5 Work Station (22 MIPS). Experimental results for benchmarks such as Deutsch's Difficult Example and MCNC's PRIMARY1 channel routing problems indicate that STANZA-M can achieve superior results compared to the conventional routers, and the process times are very fast despite the use of simulated annealing.

In this paper, chaos synchronization in coupled discrete-time dynamical systems is studied. Computer results display the interesting synchronization behaviors in the mutually coupled systems. As possible applications of chaos synchronization, parameter estimations and secure communications are proposed. Furthermore, a modified OGY method is given, which converts a chaotic motion into a periodic motion.

This paper presents a new sort of multilayer piezoelectric ceramic transformer for switching regulated power supplies. This piezoelectric transformer operates in the second thickness extensional vibration mode. Its resonant frequency is higher than 1 MHz. First, numerical simulation was implemented using a distributed constant electromechanical equivalent circuit method. It was calculated that this piezoelectric transformer, which has higher than 200 mechanical quality factor Q_m, could work with higher than 90% efficiency and in more than 20-W/cm³ high power density. Second, a trially fabricated transformer, which is 15 mm long, 15 mm wide and 2.2 mm thick, was examined. Modified PbTiO₃ family ceramics were used for the piezoelectric transformer material, because of the large anisotropy between electromechanical coupling factors k_t and k_p. Obtained results indicate that the piezoelectric transformer has good resonant characteristics, with little spurious vibration, and exhibits 16-W/cm³ power density with high efficiency at 2 MHz. Moreover, a switching regulated power supply, applying the piezoelectric ceramic transformer, was built and examined.

We introduce a generalized cln grammar (gclng), a generalization of a completely linearly nested context-free grammar (clncfg), of which variables are partitioned linearly and each rule satisfies similar conditions as those of clncfg related to its partition. We show that the class of languages generated by gclng's coincides with the class of quasi-rational languages, and consider the inclusion relations between languages generated by gclng's and those generated by clncfg's.

We numerically show that the learning time t of the back propagation model with the encoder topology obeys a power law described as t M^D (D: constant, 1<D 2), with M being the number of input patterns.

In this letter an SR-latch circuit using Hopfield neural networks is introduced. An energy function suited for a neural SR-latch circuit is defined for which the global convergence is guaranteed. We also demonstrate how to compose master-slave (M/S) SR- and JK-flip flops of novel SR-latch circuits, and further an asynchronous binary counter of M/S JK-flip flops. Computer simulations are included to illustrate how each presented circuit operates.

In this letter a new method for controlling chaos is proposed. Although different several methods based on the OGY- and the OPF-method perturb a value of an accessible system parameter, the proposed method perturbs the only timing of switching three values of a parameter. We apply the proposed method to the well-known Chua's circuit on computer simulations. The chaotic orbits in the Rössler type- and the double scroll type-attractor can be stabilized on several unstable periodic orbits embedded within these attractors.