This paper introduces a novel design automation methodology for charge recovery logic (CRL). The proposed methodology combines a novel logic compression algorithm with automatic schematic generation to automate the design process of CRL, enabling power and performance simulations for a large number and variety of CRL circuits. As a measure of the effectiveness of the proposed design flow, automated implementations of CRL equivalents of the LGSynth’91 combinational benchmark circuits are compared with their CMOS counterparts. The results demonstrate a trade-off in power for area: Automatically generated CRL circuits dissipate 51.3% less power on average compared to CMOS equivalents, occupying 54.9% larger area.

In the optimization of long bit-length adder design, the maintenance of solution space for adder structures and the control of wire length are important keys. This paper focuses on parallel prefix adders, and proposes macro construction rules based on the procedural construction framework for parallel prefix adders, and specification of application sequence using binary tree labeling. In addition, bit-line shuffling is combined in the design optimization for further improvement of delay performance. Proposed co-optimization of logical structure and bit-line placement improves the maximum path delay by 7% compared with the best one among the well-known benchmark parallel prefix adders. The improvement seems not to be significant, but the proposed method can easily be applied to variety of designs with different objectives, different parameter settings, etc.

Adiabatic logic circuit can be considered as one of the most attractive solutions for low power circuits. This paper treats a design optimization of Two-Level Adiabatic Logic (2LAL) circuit which has a relatively simple structure and an excellent low-power performance compared with many other asymptotically adiabatic or quasi-adiabatic logic families, while it needs a large number of timing buffers for "decomputation". We focus on "early decompute" technique for fully pipelined 2LAL, and proposes an ILP approach to the optimization of early decompute for minimizing hardware cost. First we show that our hardware minimization problem can be reduced into "Stable Set" problem, and then we derive its ILP formulation. The superiority of the proposed method is evaluated using ISCAS-85 benchmark circuits.

This paper treats the placement of stacked 3-D modules in a stacked 3-D LSI, and proposes a coding scheme named Triplet-Sequence which is inspired by Sequence Pair, a well-known coding system for 2-D rectangular modules. Triplet-Sequence consists of two sequences of module names which work similarly but a bit differently with Sequence Pair for adopting stacked 3-D placement, and one other sequence of integral numbers which specifies layer assignment of modules directly. Another important contribution is the decoding algorithm for flexible Stacked 3-D modules. The shape of each 3-D module is not limited to a cuboid, but a collection of vertically stacked rectangles which may have individual sizes and relative positions (positional offsets) in (x, y)-coordinate. A flexible module is defined as a stacked 3-D module with variable positional offset, which allows us to arrange relative positions between vertically stacked rectangles in one module for adapting to a vacant space around them. The application of Simulated Annealing Search to the solution space defined with Triplet-Sequence is also demonstrated to show the validity of flexible modules and Triplet-Sequence as one of the possible design models for Stacked 3-D layout.

Parallel prefix adder is a type of adder design which has enough structural flexibility on parallelism of carry propagation, and provides us a wide spread of adder structures. This paper proposes the minimum structural transformation of Parallel Prefix Tree, a core of Parallel Prefix Adder, and its application to the structural optimization of Parallel Prefix Adder based on search methods such as Simulated Annealing Algorithm. When we design a solution space for a search-based optimization, (1) containment of the optimum solution, (2) reachability between solutions, and (3) smoothness of a solution space are keys for the success of search-based optimization. The solution space defined with the proposed minimum structural transformation satisfies (1) and (2), and (3) as well in a certain proper level. The smoothness of the solution space defined by the minimum structural transformation will contribute to easy escape from local optima during a search-based optimization with some hill-climb mechanism, which is verified through experiment.

Procedural construction of parallel prefix adder (PPA) is an approach which aims to configure the prefix tree structure by the sequence of basic structural operations. Among several basic operations, “insertion” has a potential to produce a variety of prefix structures while the hardware cost is kept low. This paper investigates the essential structural variations achieved by insertion operation, and proposes a coding scheme which can represent all these essential variations and be used as a solution space to be explored for structural optimization of PPA. In our approach, we focus on the sequence of insertion operations applied at various positions, and propose to use a binary tree to specify the order of applying insertion operations. Optimization of parallel prefix adder structure relies on the Simulated Annealing search of the binary tree structures. Design examples show us their good delay performance while their hardware costs are kept low. Our discussions in this paper would be an important base for the broader optimization of parallel prefix adder utilizing many other structural operations in the procedural construction framework.

Parallel prefix adder is a type of adder design which emphasizes the parallelism on carry propagation, and it can tradeoff between the circuit size and the logical depth. This paper proposes structural-decomposition and procedural-construction of feasible parallel prefix adder structures. “Join”, “insertion” and “interleaving” are introduced as basic operations for constructing feasible parallel prefix diagram (the core structure of a parallel prefix adder) in this paper, and it is demonstrated that well-known benchmark structures are all successfully decomposed/constructed in this novel framework. Our proposed framework provide us a novel, compact and expandable representation of individual parallel prefix structures, which might be used in search-based design optimizations.

Parallel prefix adder is a type of adder design which emphasizes the parallelism on carry propagations, and can trade-off between the circuit size and the logical depth. This paper proposes a novel approach to the optimization of parallel prefix structure, which is based on Simulated Annealing (SA), a stochastic search of solution space, with respect to parallel prefix structures. A coding scheme named “prefix sequence” for representing the structure of parallel prefix adder and its application to SA-based search are main proposals of this paper. Finally, the advantage of our approach is demonstrated through design experiment.

This paper discusses Dynamically Voltage-Frequency Scaling (DVFS) with a limited number of voltage levels (Multi-Level DVFS (ML-DVFS)), and concurrent optimization of voltage levels and voltage assignment is investigated. Based on Karush-Kuhn-Tucker (KKT) conditions for the optimum solution of our ML-DVFS optimization problem, several properties of the optimum solution of ML-DVFS problem are revealed. The proposed solution algorithm consists of the enumeration of partitioning of a task set and nested two-level bisection search on voltage levels and an auxiliary parameter which corresponds to one of Lagrangian multipliers in KKT conditions. Experimental results verify the performance of ML-DVFS against unlimited DVFS.

A field programmable gate array (FPGA) architecture is developed in this work for implementing multi-valued logics (MVL). The arbitrary function of sixteen-valued logic, which is four-bit equivalent to conventional binary circuitry, can be carried out for approximate computations. The number of devices and interconnections in the proposed FPGA processor are both compacted in contrast to those of the conventional binary FPGAs. To memorize MVL datum statically, a self-refreshing and latch-up analog memory cell with four-bit accuracy is designed in a standard CMOS technology. Eighteen transistors are employed by this memory cell, which is only 37.5% of four sets of static binary memory cells. A 16-to-1 multiplexer is also proposed as the look-up table by using sixteen-valued logic signals for addressing A proof-of-concept FPGA processor is designed with 16 by 16 cell-array, and each cell has a four-bit-equivalent capacity. this manner, the number of transistors in lookup tables for such a scale is reduced to 29% of binary lookup tables. The circuit simulation results are presented for the approximate computations of linearly adding, subtracting, and Gaussian functions.

Temperature is one of the major sources of delay variations which may cause timing violations. In this paper, an approach to temperature aware clock skew scheduling for a general class of sequential circuits is proposed. At first, an alternative interpretation of the affine type (linear model) of temperature dependency is shown, which is not merely a "linearized" model applicable to a limited temperature range, but it can cover a class of nonlinear temperature dependency, and hence its applicability is not limited in temperature range. After that, a graph-theoretic skew scheduling considering the lower and the upper temperature bounds, which can work in a polynomial time complexity with respect to the circuit size, is derived. This framework can be applicable to the variants of temperature aware optimizations, such as maximizing upper temperature bound, maximizing clock frequency under a given temperature range, etc. Experiments using ISCAS'89 benchmark circuits show us that our approach achieves maximum 70% improvement in the upper temperature range (in a linear temperature scale) compared with a conventional skew scheduling which maximizes the minimum timing slack.

As the size of semiconductor devices has decreased, reliability degradation caused by soft-errors has become one of the greatest issues in VLSI circuit design. In this paper, we propose a method to synthesize soft-error tolerant application-specific datapaths via high-level synthesis. Our method is based on a concurrent error detection and a retry mechanism for error detection and error correction. The proposed model makes two novel contributions: (1) speculative resource sharing between retry parts and secondary parts for hardware/time overhead mitigation; (2) selective insertion of comparison-operations which detects soft-errors in order to increase the opportunity for speculative resource sharing. Datapath synthesis experiments found that the combination of speculative resource sharing and the selective insertion of comparison-operations achieves a maximum 32.3% improvement in latency.

The feasibility of quaternary field programmable gate array (FPGA) is investigated in this work by using standard CMOS technology and ordinary dual-rail of power supply lines. For quaternary signal processing, the basic functional circuits, quaternary memory unit, look-up table (LUT), and framework of FPGA addressing are proposed. Employing the Neuron-MOS mechanism, multi-threshold voltage inverters are designed. A quaternary scheme of static random access memory (SRAM) circuit and LUTs is proposed for FPGA applications on the basis of these inverters. In this manner, a quaternary FPGA is realized in standard CMOS technology and dual-rail power supply. From the circuit simulation results, our designed proof-of-concept four-by-four FPGA achieves all the illustrated functions correctly. The scale of this FPGA can be expanded by implementing our proposed two-dimensional quaternary addressing framework with the reduced cost.

The feasibility of designing digitally programmable delay elements (PDEs) employing neuron-MOS mechanism is investigated in this work. By coupling the capacitors on the gate of the MOS transistor, the current flowing through the transistor can be digitally tuned without additional static power consumption. Various switching delays are generated by a clock buffer stage in this manner. Two types of neuron-MOS-based PDEs are suggested in this article. One of them is realized by directly applying capacitor-coupling technology on the transistors of an inverter as a clock buffer. The delay programmability is realized by tuning the charging/discharging current through the neuron-MOS inverter digitally. Since no additional transistor is introduced into the charging/discharging path, the performance fluctuation due to process variations on MOS transistors is reduced. The temperature effect is also partially compensated by the proposed neuron-MOS implementation. Another type of PDE circuit is proposed by employing a reliable reference-current-generator, where the neuron-MOS transistor acts as a linearly tunable resistance. A stable reference current is generated and used for charging/discharging the inverter as a clock buffer. As a result, the switching delay of the inverter is linearly programmed by digital input patterns. In general, both types of suggested PDE circuits achieve improved or fair performances over the robustness, power consumption, and linearity.

Post-Silicon clock-Skew Tuning (PSST) is a promising technology for improving performance-yield of VLSIs under process variations. On the other hand, the resultant circuit after PSST should be also robust for run-time timing variations due to the change of temperature, power supply noise, etc. So, post-silicon skew tuning problem considering timing margin arises. In this work, the timing margin in the context of PSST is defined in terms of control values for programmable delay elements (PDEs), and a novel PDE tuning algorithm considering timing margin is proposed. The key component of our PDE tuning procedure is a timing test considering timing margin, in which we need to use a set of different PDE settings (mu-margin PDE test-settings) from a designed (target) PDE setting. Discussions done in this work are devoted to reducing test cost in terms of the number of timing test as well as PDE setting cost in terms of the number of mu-margin PDE test-settings.

The feasibility of programmable delay elements (PDEs) design based on Neuron-MOS mechanism is investigated in this work. By applying the capacitor coupling technology, the charging/discharging current of a clock buffer can be digitally programmed to generate various switching delay without static power consumption. No any additional transistor is introduced into the charging/discharging path, that reduces the performance fluctuation due to process variations for MOS transistors. From the circuit simulation results, the delay change of proposed PDE is less than one third compared to that of the conventional PDE circuits. In order to reduce the temperature sensitivity, another Neuron-MOS-based PDE circuit is also suggested by employing a temperature insensitive reference-current-generator. This type of PDE circuit achieves a delay change within 0.1% when the temperature fluctuates from 25 to 75 degree. In general, both types of suggested PDE circuits achieve better or fair performances over the robustness, power consumption and delay range.

The combination of triple algorithm redundancy and vote-writeback (TAR/VW) is a promising approach for designing an application specific fault-tolerant datapath circuit. The cone partitioning of an input application algorithm in TAR/VW framework increases the opportunity of resource sharing while keeping the fault tolerance ability. However TAR/VW combined with cone partitioning requires a specialized high level synthesis which can treat the complicated resource sharing conditions for fault tolerance. This paper treats high level synthesis for this purpose, and proposes a novel heuristic approach based on a two-phase binding. The resource binding in the first phase utilizes three reservation tables to assign resources to each cone properly while keeping the resource sharing constraint for fault tolerance. The second phase is the detailed resource binding and scheduling in each cone. Through experiments, our heuristic method is shown to produce comparable solutions to ILP-based exact solutions with much faster than ILP solvers.

Clock skew scheduling is a process of assigning intentional clock skews to registers for improving circuit performance and reliability. Due to the recent large effect of process variations, it becomes more and more difficult to reliably implement a large set of arbitrary clock latencies. Consequently, the optimization potential of clock skew scheduling should be highly limited. This paper points out that there is a chance to achieve further improvement of circuit performance by removing some register-writes while preserving functionality. This paper is the first work of the clock skew-aware high-level synthesis framework considering register write inhibition to minimize the clock period. A network flow-based heuristic algorithm to obtain the minimum clock period is presented and evaluated by experiments, which supports the effectiveness of the approach.

Flip-flop (FF)/latch-based design has advantages on such as area and power compared to single register-type design (only FFs or latches). Considering FF/latch-based design at high-level synthesis is necessary, because resource binding process significantly affects the quality of resulting circuits. A major downside of FF/latch-based design is the increase in resources (functional units and registers) due to the modification of the lifetimes of operations and data. Therefore, as a first step, this paper addresses the datapath design problem in which resource binding and register-type selection are simultaneously optimized for resource optimization. An efficient comprehensive framework is presented, which has flexibility to incorporate other design objectives. Experiments show that the proposed approach can generate resource-efficient FF/latch-based datapaths.

Reversible computing dissipates zero energy in terms of information loss at input and also it can detect error of circuit by keeping unique input-output mapping. In this paper, we have proposed a cost effective design of Reversible Programmable Logic Arrays (RPLAs) which is able to realize multi-output ESOP (Exclusive-OR Sum-Of-Product) functions by using a cost effective 3x3 reversible gate, called MG (MUX Gate). Also a new algorithm has been proposed for the calculation of critical path delay of reversible PLAs. The minimization processes consist of algorithms for ordering of output functions followed by the ordering of products. Five lower bounds on the numbers of gates, garbages and quantum costs of reversible PLAs are also proposed. Finally, we have compared the efficiency of proposed design with the existing one by providing benchmark functions analysis. The experimental results show that the proposed design outperforms the existing one in terms of numbers of gates, garbages, quantum costs and delay.

Post-Silicon Tuning is an emerging technology for improving performance-yield of VLSIs under process variations. This paper focuses especially on the post-silicon timing-skew tuning (PSST) via programmable delay elements (PDEs), and proposes a novel tuning algorithm which utilizes only the result of setup and hold timing tests, not the result of costly delay-time measurements. The basic framework of our PSST consists of the construction of Control-value Constraint Graph from the results of timing-tests, and the computation of longest path lengths on this graph for finding safe PDE setting. Even though the cost for timing test is smaller than a delay-time measurement, the cost of timing-tests is still a dominant part of the PSST cost, and its reduction is a crucial problem. Longest path lengths which we need to compute depends directly on edge weights in the “longest-paths tree”, but for co-tree edges, their exact edge weights are not always necessary. Based on this observation, we propose timing-test scheduling for reducing the timing-test cost for PDE tuning. The experimental simulation results show that our approach reduces the test cost by almost half or more.

Moving into the era of nanoscale devices, reliable clock distribution becomes a challenging problem due to the growing impact of process variations. This paper deals with this difficulty, especially on implementing useful clock skew. One possible robust way is by using programmable delay elements (PDEs) since PDEs can be adjusted after fabrication. However, with this benefit, using PDEs takes large power cost. Based on the fact that the required clock skews are quite different, depending on registers, this paper proposes a register binding approach in high-level synthesis to minimize the number of PDEs for power reduction. A mixed integer linear programming is presented to formally draw up the problem. Experiments achieve 49.4% reduction of PDEs, compared to conventional design.

This paper treats post-silicon skew tuning for improving performance yield under various delay variations, and proposes a novel PDE tuning algorithm which utilizes only the result of setup and hold timing tests, not the result of delay measurements. Our algorithm is based on “trial-and-error” approach, and it has a proper level of robustness against the variation of each PDE characteristics. As far as we know, this is the first systematic tuning algorithm whose termination is guaranteed for all chips including malfunctioning chips that have no feasible PDE setting. Simulation results show us that our tuning algorithm achieves yield improvement by around 50 points in percentage, while the loss (our algorithm fails to find a feasible PDE setting while the circuit has it (proven by ILP exact solution)) is kept up to 15 percent.

This paper proposes a novel high level synthesis for post-silicon skew adjustable datapaths. Our objective in high level synthesis is to maximize the "skew adjustability", i.e. the probability of the success of skew adjustment under delay variations. Skew adjustability is first shown to be reduced to the probability for a skew constraint graph (a weighted directed graph) to have no positive cycle. Since the computation of the skew adjustability is intractable, the original problem is transformed into "selective ordered coloring problem", which tries to minimize hazardous cycles instead of an exact skew adjustability. An ILP approach of the selective ordered coloring approach is then proposed. Experimental results show not only the effectiveness of our approach, but also how much improvement in the skew adjustability is achieved by equipping one or two extra registers to a datapath circuit.

This paper proposes a novel high-level synthesis (HLS) using double-edge-triggered flip-flops (DETFF) as memory elements. The duty-cycle is a key factor in the HLS. To utilize the duty-cycle radically, a variable-duty-cycle (VDC) mechanism is built into the HLS, which is captured by a new HLS task named VDC scheduling. As the first step for DETFF-based HLS, the clock-period minimization problem is formulated, and solved by a graph-based algorithm. The experimental results support the effectiveness of the algorithm.

In current VLSI complexity systems, clock skew scheduling is one of the key approaches to improve circuit performance and reliability. A delay insertion method has been discussed in logic-level to reduce the clock period. This paper extends this idea into high-level synthesis (HLS), and introduces a new HLS task, namely the minimum-path delay assignment. Since register binding plays an important role on the effect of the minimum-path delay assignment, this paper formulates the problem of simultaneously optimizing register binding and the minimum-path delay assignment. An MILP-based approach will be presented, and evaluated by experiment which shows the approach can reduce the clock period with an average of 14.1% compared to conventional clock skew-aware design.

Considering the timing uncertainty/variation of control signals and a clock signal to components, this paper proposes a novel resource sharing model which overcomes the risks of malfunctions caused by the timing problems. control timings, and proposes resource sharing conditions to FU assignment, which guarantee correct timings of control signals to multiplexers and registers under delay uncertainty/variation. This approach is combined with ``ordered clocking'' which is another mechanism to guarantee the correct timing, and the final resource sharing model is devised. There is a major drawback: the increase in latency. As the first step, the latency minimization problem under the proposed resource sharing model is formulated, and a simple List Scheduling-based algorithm is proposed as a solution algorithm. The proposed method is evaluated by experimental results for some benchmark circuits.

The setup and hold timing constraints are two types of timing constraints, which should be kept by each operation, and they may be violated by the timing variation of control signals. In this paper, we show that we can solve such potential timing violations in high-level synthesis without degrading speed performance, but by devising register assignment and clocking scheme. That is, we will combine Backward-Data-Direction (BDD) clocking, Forward-Data-Direction (FDD) clocking, and Structural Robustness against delay Variation (SRV)-based register assignment to solve potential timing violations. First, we formulate the problem as a minimum register assignment problem for datapaths which has a proper ordered clocking. After that, we propose an integer linear programming (ILP) formulation and show the experimental results for some benchmark circuits.

The simultaneous optimization of the control step assignment and the control skew assignment is a powerful technique in improving performance. This paper treats an essential and important problem, the solvability of this simultaneous control step and timing skew assignments. Our first result is to announce that the decision problem whether an input instance has a feasible pair of control step assignment and timing skew assignment or not is NP-complete. The second result is to show the necessary and sufficient condition for an input instance to have feasible solutions for every clock period. The latter result contributes greatly to designing a heuristic algorithm for the simultaneous optimization of control step and timing skew assignments, which has been proven to be NP-hard.

For recent and future nanometer-technology VLSIs, static and dynamic delay variations become a serious problem. In many cases, the hold constraint, as well as the setup constraint, becomes critical for latching a correct signal under delay variations. While the timing violation due to the fail of the setup constraint can be fixed by tuning a clock frequency or using a delayed latch, the timing violation due to the fail of the hold constraint cannot be fixed by those methods in general. Our approach to delay variations (in particular, the hold constraint) proposed in this paper is a novel register assignment strategy in high-level synthesis, which guarantees safe clocking by contra-data-direction (CDD) clocking. After the formulation of this new register assignment problem, we prove NP-hardness of the problem, and then derive an integer linear programming formulation for the problem. The proposed method receives a scheduled data flow graph, and generates a datapath having (1) robustness against delay variations, which is ensured by CDD-based register assignment, and (2) the minimum possible number of registers. Experimental results show the effectiveness of the proposed method for some benchmark circuits.

As well as the schedule affects system performance, the control skew, i.e., the arrival time difference of control signals between registers, can be utilized for improving the system performance, enhancing robustness against delay variations, etc. The simultaneous optimization of the control step assignment and the control skew assignment is more powerful technique in improving performance. By our preliminary study, we have proven that, even if the execution sequence of operations assigned to the same resource is fixed, the simultaneous optimization problem under a fixed clock period is NP-hard. In this paper, we propose a heuristic algorithm for the simultaneous control step and skew optimization under given clock period, and we show how much the simultaneous optimization improves system performance. This paper is the first one that uses the intentional skew to shorten control steps (and hence a real application time) under a specified clock period. The proposed algorithm has the potential to play a central role in various scenarios of skew-aware high level synthesis.

In this paper, we propose an extended model of register-sharing in a dual-rail two-phase asynchronous datapath, which provides us with a larger solution space of resource sharing. We introduce a new type of register which is driven by data to be latched and a control signal. By using this type of register, multiple data can share the same register aggressively in a dual-rail two-phase asynchronous datapath.

This paper proposes an approach to non-robust and functionally sensitizable path delay test generation through stuck- at test generation. In this approach, to generate two-pattern tests for path delay faults in a combinational circuit, checker circuitry is constructed which is composed of logic gates corresponding to the mandatory assignments for detecting the faults. This checker circuitry allows us to use any existing combinational stuck-at test generation tool. Since today’s stuck-at test generation tools reach a mature level, the proposed approach can efficiently solve the path delay test generation problem for combinational circuits. Experimental results show that the approach can speed up path delay test generation and can improve fault efficiency. This paper also discusses how a scan circuit and the issues of over-testing and test power are handled in the proposed test generation framework.

In this paper, we propose an effective asynchronous datapath synthesis system to optimize statistical schedule length using statistical schedule length analysis. The proposed method is a heuristics which simultaneously performs scheduling and resource binding. During the design process, decisions are made based on the statistical schedule length analysis. It is demonstrated that asynchronous datapaths with the reduced mean total computation time are successfully synthesized for some datapath synthesis benchmarks.

As the geometrical design rules of VLSIs become finer into the order of deep sub-micron, the impact of wires to VLSI performance becomes larger relatively to the other components, and their estimation at RT-level description and performance-driven datapath synthesis need explicit connectivity information about RT-level architecture and its floorplan. In this paper, an assignment-driven approach to the datapath synthesis incorporated with one-dimensional floor planning is proposed. In our approach, scheduling and one-dimensional floorplanning, both of which are driven by iteratively generated functional unit and register assignment (binding), are performed fully concurrently. Pseudo-branch-and-bound assignment space exploration is adopted for generating assignments in this pilot system.

In this paper, an assignment based approach to the data-path synthesis is studied, which aims to identify and to manage the connectivity between modules more explicitly throughout the design process. In contrast to conventional approaches, the assignment solution space will be explored concurrently with evaluations of scheduling length and the other criteria relevant to the connectivity. Especially in this paper, a scheduling method suitable for this design strategy is proposed, and is incorporated with the branch-and-bound search of the assignment solution space.

Most of the methods for analyzing and designing algorithm-based fault-tolerant (ABFT) systems assume that redundant computations and checking operations are computed by fault-free processors. However, the redundant computations and the checking operations are usually a part of the ABFT system in practical applications, and are needed to be performed on the system processors so that the system still maintains the desired fault tolerance. To achieve these objectives, we extend the MPDC graph model, which has been used for representing ABFT systems, to handle redundant computations, checking operations and their mapping to processors concurrently with nominal computations. A single-fault locatable FIR filter based on the extended MPDC graph model is synthesized on a systolic array as a practical implementation of the proposed method.

In a typical very large scale integration/printed circuit board (VLSI/PCB) design, some modules are preplaced in advance, and the other modules are requested to be placed without overlap with each other and with these preplaced modules. The presence of such obstacles introduces inconsistency to a coding scheme, called sequence pair, which has been proposed for an obstacle free placement problem. We solve this difficulty by proposing a procedure called "adaptation" which transforms an inconsistent sequence pair to a consistent one with the utmost consideration for minimizing the modification. It is shown that a simulated annealing is well organized so that it tests only feasible placements by the adaptation procedure. As a design example, a Microelectronics Center of North Carolina (MCNC) benchmark data "ami49" is packed with treating ten modules among 49 modules as preplaced ones. Further, a PCB example which includes 32 free modules and four preplaced modules (connectors) is laid out successfully by our method with a conventional wiring estimation followed by a commercial router.

A new method for adaptive autoregressive spectral stimulation based on the least-squares criterion with multi-band decomposition of the linear prediction error and analysis of each band through independent variable forgetting factors is presented. The proposed method localizes the forgetting factor adaptation scheme in the frequency domain and in the time domain, in the sense that variations on the statistics of the input signal are independently evaluated for each band along the time. In this paper, a new forgetting factor adaptation technique depending exclusively on the input signal is introduced and applied to the multi-window analysis of the linear prediction error structure to generate time-varying autoregressive spectral estimates. An improvement on the fidelity of estimates is shown in computer experiments which compare the proposed method with conventional and multi-band least-squares methods with fixed forgetting factors.

Article VLSI/PCB placement with obstacles based on sequence-pair Share on Authors: H. Murata Japan Advanced Institute of Science and Technology, Japan Japan Advanced Institute of Science and Technology, JapanView Profile , K. Fujiyoshi Tokyo University of Agriculture and Technology, Japan Tokyo University of Agriculture and Technology, JapanView Profile , M. Kaneko Japan Advanced Institute of Science and Technology, Japan Japan Advanced Institute of Science and Technology, JapanView Profile Authors Info & Claims ISPD '97: Proceedings of the 1997 international symposium on Physical designApril 1997 Pages 26–31https://doi.org/10.1145/267665.267675Online:01 April 1997Publication History 38citation300DownloadsMetricsTotal Citations38Total Downloads300Last 12 Months7Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

In this paper, a novel method for oscillation fault diagnosis for analog circuits is presented. Our method is based on the test whether there exist or not a solution of unknown parameters (transconductances of transistors) which makes nodal admittance matrix singular. The boundary search method for testing the existence of such a solution has been modified, and a pre-processing for diagnosis has been developed by which candidates for the cause of oscillation fault can be selected from various element value perturbations and stray elements in the circuit under test.>

A new adaptive AR spectrum estimation method is proposed. The cost function is defined by using the discrete-time wavelet transform coefficients of the linear prediction error. Instead of a single window throughout the whole frequency spectrum, a wavelet-like windowing method is used to increase the frequency resolution of the low-frequency components and to improve the time resolution of the high-frequency components. Special properties of the covariance matrix are used to derive an RLS algorithm which requires O(M/sup 2/) operations. Simulation results show that the wavelet based spectrum estimation method gives fine frequency resolution at low frequencies and good time resolution at high frequencies, while with conventional methods it is possible to have only one of these characteristics.>

WSI is considered liable to have several faults at the beginning of the production stage and during its operating lifetime. This paper describes a design of distributed controller for reconfiguration on harvesting linear array system as a degradable system with assumption that not only basic cells but also the connection links are subject to fault condition. An inherently distributed feature of a new class of cellular neural network is used in hierarchical method. The proposed method is a simple heuristic distributed process with cellular (next neighbor) information. It has simple structures that have minimum penalty in WSI area thus minimizing the reliability cost.>