This paper presents a timing-driven global routing algorithm based on coarse pin assignment, block reshaping, and positioning for VLSI building block layout. As opposed to conventional approaches, we combine pin assignment and global routing problems into one problem. The proposed algorithm determines global routes, coarse pin assignments, and block shapes and positions so as to minimize the chip area and total wire length of nets under the given timing constraints. It is based on an iterative improvement paradigm and performs rip-up and rerouting, block reshaping, and positioning in the manner of simulated evolution taking shapes of soft blocks and routing congestion into consideration until the solution is not further improved. The Elmore delay model is adopted for the interconnection delay model. Experimental results show the effectiveness of the proposed algorithm.

The mapping from a global routing to a feasible detailed routing in a number of 2D array routing structures has been shown to be an NP-complete problem. These routing structures include the Xilinx style routing architecture, as well as architectures with significantly higher switching flexibility. In response to this complexity, a different class of FPGA routing structures called Greedy Routing Architectures (GRAs) have been proposed. On GRAs, optimally routing each switch box, in a specified order, leads to an optimal chip routing. Because routing each switch box takes polynomial time, the mapping problem on GRAs can be solved in polynomial time. In particular, an H-tree GRA with W²+2W switches per switch box (SpSB) and a 2D array GRA with 4W²+2W SpSB have been proposed. In this paper, we improve on these results by introducing an H-tree GRA with W²/2+2W SpSB and a 2D array GRA with 3.5W²+2W SpSB. These new GRAs have the same desirable mapping properties of the previously described GRAs, but use fewer switches.

The importance of technology retargeting for hard IPs is getting increased. However, recent advances in process technologies make layout reuse too complicated to be done by conventional compactors. As an efficient approach, this paper proposes a flexible layout abstraction model and a new layout synthesis algorithm. The synthesis algorithm provides a concurrent procedure of detailed wiring, compaction, and transistor layout generation by using a scan line to get better layout results than conventional compactors. We have applied this method to the technology retargeting of actual cell layouts and have achieved quite good results comparable to hand-crafted designs.

Analysis of frequency-dependent lossy transmission lines is very important for designing the high-speed VLSI, MCM and PCB. The frequency-dependent parameters are always obtained as tabulated data. In this paper, a new curve fitting technique of the tabulated data for the moment matching technique in the interconnect analysis is presented. This method based on Chebyshev interpolation enhances the efficiency of the moment matching technique.

Since most digital phase-locked loops (DPLLs) used in digital data transmission receivers require both fast acquisition of input frequency and phase in the beginning and substantial jitter reduction in the steady-state, the DPLL loop bandwidth is preferred to being adjusted accordingly. In this paper, a bandwidth adjusting (adaptive) algorithm is presented, which allow both fast acquisition and significant jitter reduction for each different noise environment and hardware requirement. This algorithm, based on the recursive least squares (RLS) criterion, suggest an optimal sequence of control parameters for a dual-loop DPLL which achieves the fastest initial acquisition time by trying to minimize the jitter variance in any given time instant. The algorithm can be used for carrier recovery or clock recovery in mobile communications, local area networks and disk drivers that require a short initial preamble period.

This paper introduces a new kind of false path, which is sensitizable but does not affect the decision of the maximum clock frequency. Such false paths exist in multi-clock operations controlled by waiting states, and the delay time of these paths can be greater than the clock period. This paper proposes a method to detect these waiting false paths based on the symbolic state traversal. In this method, the maximum allowable clock cycle of each path is computed using update cycles of each register.

This paper proposes a new flexible hardware model for pipelined design optimization. Using together with an RTL floorplanner, the flexible hardware model makes accurate and fine design space exploration possible. It is quite effective for deep submicron technology since estimation at high level has become a difficult problem and the design tuning at lower level of abstraction makes up the full design optimization task. The experimental results show that our approach reduces the slack time in the pipeline stages then achieves higher performance with a smaller area.

This paper presents a new efficient method for finding an "optimal" bi-decomposition form of a logic function. A bi-decomposition form of a logic function is the form: f(X) = α(g₁(X¹), g₂(X²)). We call a bi-decomposition form optimal when the total number of variables in X¹ and X² is the smallest among all bi-decomposition forms of f. This meaning of optimal is adequate especially for the synthesis of LUT (Look-Up Table) networks where the number of function inputs is important for the implementation. In our method, we consider only two bi-decomposition forms; (g₁ g₂) and (g₁ g₂). We can easily find all the other types of bi-decomposition forms from the above two decomposition forms. Our method efficiently finds one of the existing optimal bi-decomposition forms based on a branch-and-bound algorithm. Moreover, our method can also decompose incompletely specified functions. Experimental results show that we can construct better networks by using optimal bi-decompositions than by using conventional decompositions.

Simple disjunctive decomposition is a special case of logic function decompositions, where variables are divided into two disjoint sets and there is only one newly introduced variable. It offers an optimal structure for a single-output function. This paper presents two techniques that enable us to apply simple disjunctive decompositions with little overhead. Firstly, we propose a method to find symple disjunctive decomposition forms efficiently by limiting decomposition types to be found to two: a decomposition where the bound set is a set of symmetric variables and a decomposition where the output function is a 2-input function. Secondly, we propose an algorithm that constructs a new logic representation for a simple disjunctive decomposition just by assigning constant values to variables in the original representation. The algorithm enables us to apply the decomposition with keeping good structures of the original representation. We performed experiments for decomposing functions and confirmed the efficiency of our method. We also performed experiments for restructuring fanout free cones of multi-level logic circuits, and obtained better results than when not restructuring them.

This paper describes a method to represent m output functions using shared multi-terminal binary decision diagrams (SMTBDDs). The SMTBDD(k) consists of multi-terminal binary decision diagrams (MTBDDs), where each MTBDD represents k output functions. An SMTBDD(k) is the generalization of shared binary decision diagrams (SBDDs) and MTBDDs: for k=1, it is an SBDD, and for k=m, it is an MTBDD. The size of a BDD is the total number of nodes. The features of SMTBDD(k)s are: 1) they are often smaller than SBDDs or MTBDDs; and 2) they evaluate k outputs simultaneously. We also propose an algorithm for grouping output functions to reduce the size of SMTBDD(k)s. Experimental results show the compactness of SMTBDD(k)s. An SMTBDD_min denotes the smaller SMTBDD which is either an SMTBDD(2) or an SMTBDD(3) with fewer nodes. The average relative sizes for SBDDs, MTBDDs, and SMTBDDs are 1. 00, 152. 73, and 0. 80, respectively.

In this paper, we will discuss circuit minimization techniques based on the multiple output capability of FPGA blocks. Since previous methods only consider two independent output functions, we will discuss a more complicated case when the two functions are mutually related. We also discuss a method to maximize flexibility of a specified cell output in the given FPGA block. If a set of possible functions for a cell which will not change the FPGA output function is large, we call that the flexibility of this cell is high. The concept of Sets of Pairs of Functions to be Distinguished (SPFDs) introduced by Yamashita et al. is a powerful tool to minimize a given FPGA circuits. In this paper, an extension of the concept, Priority based SPFDs (PSPFDs) is introduced to maximize the flexibility of output functions realized by such internal cells. By using PSPFDs for our new method, we can utilize the multiple output capability very well. Combination with the previous methods with PSPFDs is also shown to be important. We have implemented these methods and applied them to MCNC benchmarks mapped into 5-variable function blocks. To make a comparison with other methods, we have implemented methods using well-known merging algorithms utilizing the same multiple output capability. Experimental results show that our methods can reduce the number of blocks in the initial circuits by 40% on average. This reduction ratio is 16% higher than that of previous methods.

This paper proposes a high-level synthesis system for datapath design of digital processing hardwares. The system consists of four phases: (1) DFG (data-flow graph) generation, (2) scheduling, (3) resource binding, and (4) HDL (hardware description language) generation. In (1), the system does not generate only one best DFG representing a given behavioral description of a hardware, but more than one good DFGs representing it. In (2) and (3), several synthesis tools can be incorporated into the system depending on the required objectives. Thus we can obtain more than one datapath candidates for a behavioral description with their area and performance evaluation. In (4), the best datapath design is selected among those candidates and its hardware description is generated. The experimental results for applying the system to several benchmarks show the effectiveness and efficiency.

Since manufacturing processes inherently fluctuate, LSI chips which are produced from the same design have different propagation delays. However, the difference in delays caused by the process fluctuation has rarely been considered in most of existing high-level synthesis systems. This paper presents a new approach to module selection in high-level synthesis, which exploits the difference in functional unit delays. First, a module library model which assumes the probabilistic nature of functional unit delays is presented. Then, we propose a module selection problem and an algorithm which minimizes the cost per faultless chip. Experimental results demonstrate that the proposed algorithm finds optimal module selections which would not have been explored without manufacturing information.

Providing various assistances for design modifications on HDL source codes is important for design reuse and quick design cycle in VLSI CAD. Program slicing is a software-engineering technique for analyzing, abstracting, and transforming programs. We show algorithms for extracting/removing behaviors of specified signals in VHDL descriptions. We also describe a VHDL slicing system and show experimental results of efficiently extracting components from VHDL descriptions.

The datapath width of a core processor has a strong effect on cost, power consumption, and performance of an embedded system integrated with memories into a single-chip. However, it is difficult for designers to appropriately determine the datapath width for each application because of the limited reusability of software and the lack of compilation techniques. The purpose of this paper is to clarify supports required from software for the optimal datapath width determination. As a solution, an embedded programming language, called Valen-C, and a retargetable Valen-C compiler are proposed. In this paper, the syntax and semantics of Valen-C along with the mechanism of the Valen-C retargetable compiler and how to preserve the accuracy of computation of programs in relation to various datapath widths are also described. Experiments with practical applications show that the total cost of the system including a core processor, ROM, and RAM is drastically reduced with little performance loss by reducing the datapath width.

Hardware software codesign using various hardware and software implementation possibilities requires a cosimulation environment which has both flexibility and efficiency. In this paper, a hardware software cosimulation environment is developed using the backplane approach and optimized synchronization. To seamlessly integrate a new simulator, this paper defines and implements the backplane protocol for communication and synchronization between client simulators. Automatic interface generation facility is also devised for more effective cosimulation environment. To enhance the performance of cosimulation backplane, a series of optimized hardware software synchronization methods are introduced. Efforts are focused on reducing control packets between simulators as well as concurrent execution of simulators without roll-back. The environment is implemented based on Ptolemy and validated with a QAM example run on different configurations. With optimized synchronization method, we have achieved about 7 times speed-up compared with the lock-step synchronization.

In designing ASIPs (Application Specific Integrated Processors), the papers investigated so far have almost focused on the optimization of the CPU core and did not pay enough attention to the optimization of the RAM and ROM sizes together. This paper overcomes this limitation and proposes an optimization algorithm to define the best ratio between the CPU core, RAM and ROM of an ASIP chip to achieve the highest performance while satisfying design constraints on the chip area. The partitioning problem is formalized as a combinatorial optimization problem that partitions the operations into hardware and software so that the performance of the designed ASIP is maximized under given chip area constraint, where the chip area includes the HW cost of the register file for a given application program with associated input data set. The optimization problem is parameterized so that it can be applied with different technologies to synthesize CPU cores, RAMs or ROMs. The experimental results show that the proposed algorithm is found to be effective and efficient.

In many embedded systems, a significant amount of power is consumed for off-chip driving because off-chip capacitances are much larger than on-chip capacitances. This paper proposes instruction scheduling techniques to reduce power consumed for off-chip driving. The techniques minimize the switching activity of a data bus between an on-chip cache and a main memory when instruction cache misses occur. The scheduling problem is formulated and two scheduling algorithms are presented. Experimental results demonstrate the effectiveness and the efficiency of the proposed algorithms.

This paper presents a new binding algorithm for a retargetable compiler which can deal with diverse architectures of application specific embedded processors. The architectural diversity includes a "non-orthogonal" datapath configuration where all the registers are not equally accessible by all the functional units. Under this assumption, binding becomes a hard task because inadvertent assignment of an operation to a functional unit may rule out possible assignment of other operations due to unreachability among datapath resources. We propose a new BDD-based algorithm to solve this problem. While most of the conventional methods are based on the covering of expression trees obtained by decomposing DFGs, our algorithm works directly on the DFGs so as to avoid infeasible bindings. In the experiments, a feasible binding which satisfies the reachability is found or the deficiency of datapath is detected within a few seconds.

In this paper, we propose a test methodology for core-based system LSIs. Our test methodology aims to decrease testing time for core-based system LSIs. In our method, every core is supplied with several sets of test vectors. Every set of test vectors guarantees sufficient fault coverage. Each set of test vectors consists of two parts. One is based on built-in self-test (BIST) and the other is based on external testing. These sets of test vectors are designed to have different ratio of BIST to external testing each other for every core. We can minimize testing time for core-based system LSIs by selecting from the given sets of test vectors for each core. The main contributions of this paper are summarized as follows. (i) BIST is efficiently combined with external testing to relax the limitation of the external primary inputs and outputs. (ii) External testing for one of cores and BISTs for the others are performed in parallel to reduce the total testing time. (iii) The testing time minimization problem for core-based system LSIs is formulated as a combinatorial optimization problem to select the optimal set of test vectors from given sets of test vectors for each core.

In this paper, we propose a new register transfer level (RT level) testability analysis method. Controllability and observability measures are defined for signal vectors based on the numbers of values they can take. The control part and the datapath part are automatically identified in the given RT level model and distinctive analysis methods are applied. We also describe a DFT point selection method based on our testability measures. In a experiment on a signal processing circuit whose gate count is 7690 including 578 FFs, almost the same fault coverage is achieved with fewer scan FFs than a conventional method based on gate level testability analysis.

We describe a new multiport memory which is called Shared DRAM (SHDRAM) to overcome bus-bottle neck problem in parallel processor system with shared memory. The processors are directly connected to this SHDRAM without conventional common bus. The test chip with 32 kbit memory cells is fabricated using a 1. 5 µm CMOS technology. The basic operation is confirmed by the circuit simulation and experimental results. In addition, it is confirmed by the computer simulation that the system performance with SHDRAM is superior to that with conventional common buses.

This paper proposes a method to reduce the context switching time using a register bank to store contexts of working tasks. Hardware cost and performance were measured by modeling the register bank and controller in VHDL. Following results were obtained: (1) The controller can be implemented with a much smaller amount of hardware cost compared to that of the register bank, which is realized by SRAM module. (2) Context switching time can be reduced to less than 50% compared to that by software implementation. (3) Combination of the proposed architecture with our previous work (RTOS implemented in HW) gives us much higher performance of a hard real-time system.

A method for expanding the channels of data acquisition unit used in distributed microcomputer data measure & control systems and a technique to call assembly routines by C Language are introduced in the paper. The method may increase the number of data acquisition points ten to hundreds times. So it may raise the price performance ratio of all distributed data measure & control system greatly. And the programming method may optimize program performance.

We have developed a Field-Programmable Multi-Chip Module (FPMCM) whose component is the telecommunication-oriented FPGAs, called PROTEUS. The module consists of 3 3 PROTEUS FPGAs and its size is 114 mm square. Each PROTEUS chip is mounted on the MCM substrate using Tape Automated Bonding (TAB) technology so as to minimize the size of the MCM and the production cost. The interconnection topology among the FPGAs is a simple mesh. However, the connection can be changed logically, because PROTEUS itself has a special inter-I/O bypass resource in it. Using this mechanism, the interchip connection delay can be reduced without sacrificing the flexibility, compared to the previous FPMCM implementation using some other interconnection switches which often have a large propagation delay. The interchip connection delay is 200 ps. We have also developed a rapid prototyping system comprising several MCMs, and implemented telecommunication circuits in it.

This paper presents a new routing method that takes into account neighboring-wire-capacitance (inter-layer and intra-layer) constraints. Intermediate routing (IR) assigns each H/V wire segment to the detailed routing (DR) grid using global routing (GR) results, considering the neighboring-wire constraints (NWC) for critical nets. In DR, the results of IR for constrained nets and their neighboring wires are preserved, and violations that occur in IR are corrected. A simple method for setting NWC that satisfy the initial wire capacitance given in a set-wire-load (SWL) file is also presented. The routing method enables more accurate delay evaluation by considering inter-wire capacitance before DR, and avoids long and costly turnaround in deepsubmicron layout design. Experimental results using MCNC benchmark test data shows that the errors between the maximum delay from IR and that from DR for each net were less than 5% for long (long delay) nets.

A double-layer Associative Memory System (AMS) based on the Cerebella Model Articulation Controller (CMAC) (CMAC-AMS), owing to its advantages of simple structures, fast searching procedures and strong mapping capability between multidimensional input/output vectors, has been successfully used in such applications as real-time intelligent control, signal processing and pattern recognition. However, it is still suffering from its requirement for a large memory size and relatively low precision. Furthermore, the hash code used in its addressing mechanism for memory size reduction can cause a data-collision problem. In this paper, a new high-order Associative Memory System based on the Newton's forward interpolation formula (NFI-AMS) is proposed. The NFI-AMS is capable of implementing high-precision approximation to multivariable functions with arbitrarily given sampling data. A learning algorithm and a convergence theorem of the NFI-AMS are proposed. The network structure and the scheme of its learning algorithm reveal that the NFI-AMS has advantages over the conventional CMAC-type AMS in terms of high precision of learning, much less required memory size without the data-collision problem, and also has advantages over the multilayer Back Propagation (BP) neural networks in terms of much less computational effort for learning and fast convergence rate. Numerical simulations verify these advantages. The proposed NFI-AMS, therefore, has potential in many application areas as a new kind of associative memory system.

Consider a random digraph G=(V,A), where |V|=n and an arc (u,v) is present in A with probability p(n) independent of the existence of the other arcs. We discuss the expected number of vertices reachable from a vertex, the expected size of the transitive closure of G and their related topics based on the properties of reachability, where the reachability from a vertex s to t is defined as the probability that s is reachable to t. Let γ_n,p(n) denote the reachability s to t (s) in the above random digraph G. (In case of s=t, it requires another definition. ) We first present a method of computing the exact value of γ_n,p(n) for given n and p(n). Since the computation of γ_n,p(n) by this method requires O(n³) time, we then derive simple upper and lower bounds γ_n,p(n)^U and γ_n,p(n)^L on γ_n,p(n), respectively, and in addition, we give an upper bound _n,p(n) on γ_n,p(n)^U, which is easier to analyze but is still rather accurate. Then, we discuss the asymptotic behavior of _n,p(n) and show that, if p(n)=α/(n-1), lim_nn,p(n) converges to one of the solutions of the equation 1-x-e^{-α x}=0. Furthermore, as for (n) and (n), which are upper bounds on the expected number of reachable vertices and the expected size of the transitive closure of G, resp. , it turns out that lim_n(n) =α/(1-α) if p(n)=α/(n-1) for 0<α<1; otherwise either 0 or , and lim_n(n)=α if p(n)=α/(n-1)² for α0; otherwise either 0 or .

We present an enumerative technique for encoding and decoding binary sequences satisfying a constraint defined by a runlength graph. The presented technique enables to implement encoders and decoders of constrained codes having code rates very close to channel capacity. As a detailed example, we consider enumerative coding of (0,G/I) constrained sequences as often applied in magnetic hard disk recording systems. Using floating-point notation to express the weight coefficients required to perform encoding and decoding, this technique results in moderate complexity. For (0,G/I) constraints of practical interest, the hardware required to implement such a quasi-optimum coding scheme consists mainly of a ROM of at most 2 kByte. As a remarkable example, a (0,6/8) constrained code can be implemented at rate 256/260 or 512/518 using a ROM of about 2 kByte.

This paper proposes two types of acceleration parameters for the Durand-Kerner method and its variant, where the values of parameters are determined at each iteration step. Numerical examples are also shown.

A method of visualization of multimodal images by one monochromatic image is presented on the basis of the projection pursuit approach of the inverse process of the anisotropic diffusion which is a method of image restoration enhancing contrasts at edges. The extension of the projection from a linear one to nonlinear sigmoidal functions enhances the contrast further. The deterministic annealing technique is also incorporated into the optimization process for improving the contrast enhancement ability of the projection. An application of this method to a pair of MRI images of brains reveals its promising performance of superior visualization of tissues.