Morikazu NAKAMURA Kenji ONAGA Seiki KYAN
We discuss properties of acyclic graph evolution driven by node-firing. The research background and basic concepts of acyclic graph evolution are from the mutual exclusion problem in distributed environments. We proposed in our previous work a mutual exclusion protocol which is based on the notion of evolution trajectories of acyclic graphs. In this paper, we analyze firing concurrency and periodicity of the acyclic graph evolution, from graph theoretical point of views, and investigate topological conditions for assuring the number of firable nodes below a some fixed constant, at any instance of the evolution trajectory. A marked graph, a subclass of Petri nets, is often utilized as a proof tool in analysis.
Masahiro YOSHIZAWA Tetsuma SAKURAI Eisuke ARAI
A novel delivery management system using a new lot sampling scheduling (LSS) method has been developed. The method involves the concepts of "virtual line" and "marker lot," and the system consists of an on-line scheduler executing short-period scheduling for lot-tracking and an off-line scheduler executing long-period scheduling for delivery date simulation. The LSS method can hugely increase the maximum number of lots to simulate the delivery date and also control TAT more effectively compared to conventional dynamic scheduling. Lot progress is controlled by varying the resource allocation ratio for each virtual line. This method is effective for precise delivery date control of lots with various priorities in ASIC production or development lines.
Toshimasa MATSUOKA Shigenari TAGUCHI Kenji TANIGUCHI Chihiro HAMAGUCHI Seizo KAKIMOTO Junkou TAKAGI
Thickness dependence of breakdown properties in control and N2O-Oxynitrided oxides was investigated. Nitrogen atoms piled up at the Si/SiO2 interface increase charge-to-breakdown (QBD) under substrate injection conditions for oxide thickness below 10 nm, while no meaningful improvement is observed above 10 nm. This thickness dependence is explained by the fact that N2O-oxynitridation reduces oxide defects near the Si/SiO2 interface. N2O-oxynitridation of the oxides reduces the number of neutral electron traps due to the chemical reaction of oxide defect with nitrogen atoms. Electron trapping of N2O-oxynitrided oxides is significantly suppressed; the reduction of electron trapping events into neutral electron traps increases QBD under substrate injection. On the other hand, under gate injection, N2O-oxynitrided oxides show low rate of hole trapping during the initial stress period. However, in heavily injected condition, electron trapping is not suppressed, resulting in little improvement of QBD. In addition, the control and N2O-oxynitrided oxides show quite similar dependence of QBD on stress current density, which is related primarily to the carrier transport phenomena (tunneling, traveling, impact ionization and hole injection).
Naomichi OKAMOTO Xue Jun MENG Okihiro SUGIHARA
We analyze all-optical switching property of a nonlinear directional coupler (NLDC) having an MQW coupling layer with both nonlinear and linear losses, and examine the effect of nonlinear losses. We use the Galerkin finite element method accompanied by a prodictor-corrector algorithm. The propagation loss along the strongly-coupled NLDC decreases with increasing nonlinear absorption coefficient due to saturation in absorption. A propagation loss of 8.18 dB or 2.38 dB in the bar state of the cross state is much smaller than the bulk loss of MQW structure which exceeds 50 dB. The nonlinear losses lengthen the coupling length and bring it close to that of a lossfree NLDC, while the linear losses shorten. It is found that the property of the cross state is greatly improved by counting the nonlinear losses: The cross-state output power and the output power ratio of two waveguides increase, and the cross state input power, that is, the switching power decreases.
Hiroki OKA Nobuaki SUGIURA Kei-ichi YASUDA
B-ISDN telecommunication systems will require signal processing speeds up to 600 Mbps or more. We must therefore consider the affects of signal reflection, signal attenuation, time dalay, and so on when designing these systems. The higher the signal speed, the larger the electrical noise induced around the connector, especially in the plated through holes (PTHs) area. This paper presents the results of our investigation focused on connector mounting configurations in the signal transmission line, especially whether or not signals transmit through the PTH in a printed circuit board (PCB). How the signal reflection characteristics depend upon transmission line configurations are discussed and experimental results and simulation analyses for a transmission line system using a small miniature A-type (SMA) connector as an example are performed. It is suggested that designs for future high-speed signal transmission circuits take into account the PTH diameter and/or the PTH pitch conditions, values for which can be determined from simulation analysis.
Robert K. BRAYTON Ellen M. SENTOVICH
Over the last decade, research in the automatic synthesis and optimization of combinational logic has matured significantly; more recently, research has focused on sequential logic. Many of the paradigms for combinational logic have been extended and applied in the sequential domain. In addition, promising new directions for future research are being explored. In this paper, we survey some of the results of combinational synthesis and some recent results for sequential synthesis and then use these to view possible avenues for future sequential synthesis research. In particular we look at two related questions: deriving a set of permissible behaviors and using a minimizer to select the best behavior according to some optimization criteria. We examine these two issues in increasingly complex situations starting with a single-output function, and proceeding to a single multiple-output function, a network of single-output functions, a network of multiple-output functions, and then similar questions where function" is replaced by a finite state machine (FSM). We end with a discussion of a network of finite state machines and the problem of deriving the set of permissible FSM's and choosing a representative minimum one.
The paper describes a new algorithm for Boolean matching, which is based on BDD structure manipulation. Pruning of the search space takes place after partial assignments if certain subgraphs of two BDD's become inequivalent. This pruning is different from existing techniques, so that the search space is further reduced. Another feature of this algorithm is topological filtering. Usually, many functions have no matchings and this is easily found by only counting the number of minterms. To check it quickly, upper and lower bounds of minterm count are calculated from topological information. Using these bounds, functions that have no matchings are discarded without building their BDD's.
Ivan P. RADIVOJEVI Forrest BREWER
This paper describes an exact symbolic formulation of resource-constrained scheduling which allows speculative operation execution in arbitrary forward-branching control/data paths. The technique provides a closed-form solution set in which all satisfying schedules are encapsulated in a compressed OBDD-based representation. An iterative construction method is presented along with benchmark results. The experiments demonstrate the ability of the proposed technique to efficiently extract parallelism not explicitly specified in the input description.
Vasily G. MOSHNYAGA Yutaka MORI Keikichi TAMARU
In order to shorten the time-to-market, Application-Specific Integrated Circuits (ASIC's) are designed from a library of pre-defined layout implementations for register-transfer modules such as multipliers, adders, RAM, ROM, etc. Current approaches to selecting the implementations from the library usually deal with their timing-area estimates and do not consider delay of the intermodule wiring. However, as sub-micron design rules are utilized for IC fabrication, wiring delay becomes comparable to the functional unit delay and can not longer be ignored even in register-transfer synthesis. In this paper we propose an algorithm that combines module selection with Performance-Driven module placement and reduces an impact of wiring on sub-micron ASIC performance. The algorithm not only efficiently exploits multiple module realizations in the design library, but also finds the module placement which minimizes wiring delay. Experimental results on several benchmarks show that considering both module and wiring issues, more than 30% reduction of the total circuit delay can be achieved.
Mitsuteru YUKISHITA Kiyoshi OGURI Tsukasa KAWAOKA
We developed a new test-synthesis that operates method based on data transfer analysis at the language level. Using this method, an efficient scan path is inserted to generate test data for the sequential circuit by using only a test generation tool for the combinatorial circuit. We have applied this method successfully to the behavior, logic, and test design of a 32-bit, RISC-type processor. The size of the synthesized circuit without test synthesis is 23,407 gates; the size with test synthesis is 24,811 gates. This is an increase of only a little over 6%.
Yukihiro FUJIMOTO Hisao OIKAWA
Telecommunication services are expected to be upgraded from POTS to B-ISDN services in the future. This means that the conventional metallic access networks should be upgraded to optical fiber access networks because of providing high bit-rate services. Therefore, it is very important to clarify upgrade strategies in access networks. This paper proposes a dynamic evaluation method that can support decision-making on the upgrade strategy from the viewpoint of economy. This method can determine the most promising future access network and upgrade timing. Moreover, viability of various upgrade strategies can be evaluated by this method.
Sang M. LEE Sung Chan KO Hyung Jin CHOI
In this paper, we propose an efficient method (called DIRIC algorithm) to allocate carrier frequencies so as to minimize intermodulation products in two-level SCPC systems in which Hub station and many Remote stations communicate each other through satellite transponder. We also present a very efficient method to evaluate intermodulation products with substantially reduced CPU time in two-level SCPC systems. We compare and analyze the performance of several frequency allocation methods to extend DELINS-INSDEL algorithm (which is proposed by Okinaka) to two-level SCPC systems. When the proposed algorithm is applied to systems with modulated carrier, it is verified that this algorithm has the same efficiency as the unmodulated carrier. It is also shown heuristically that certain initial assignment algorithms perform better than random assignment.
A key element in the CDMA transmission is DS spreading. Spreading in a DS/SSMA system are provided in two categories-synchronization and data. For synchronization sequences, good auto-correlation and cross-correlation properties are required in order to guarantee fast acquistion with a minimum false alarm probability. On the other hand, the auto-correlation property may not be so important in data spreading since synchronization is obtained by synchronization spreading. In this paper we provide a set of synchronization sequences and a set of data sequences--each a set of binary N-tuples--that have the necessary correlation constraints.
Tadanao TSUBOTA Masahiro KAWAKITA Takahiro WATANABE
The main aim of device-level global routing is to obtain high-performance detailed routing under various layout constraints. This paper deals with global routing for analog function blocks. For analog LSIs, especially for those operating at high frequency, various layout constraints are specified prior to routing. Those constrainsts must be completely satisfied to achieve the required circuit performance. However, they are sometimes too hard to be solved by any heuristic method even if a problem is small in size. Thus, we propose a method based on the branch-and-bound algorithm, which can generate all possible solutions to find the best one. Unfortunately, the method tends to take a large amount of processing time. In order to defeat the drawbacks by accelerating the process, constraints are classified into two groups: constraints on single nets and constraints between two nets. Therefore our method consists of two parts: in the first part only constraints on single nets are processed and in the second part only constraints between two nets are processed. The method is efficient because many possible routes that violate layout constraints are rejected immediately in each part. This makes it possible to construct a smaller search tree and to reduce processing time. Additionally this idea, all nets processed in the second phase are sorted in the proper order to reduce the number of edges in the search tree. This saves much processing time, too. Experimental results show that our method can find a good global route for hard layout constraints in practical processing time, and also show that it is superior to the well-known simulated annealing method both in quality of solutions and in processing time.
Wooi Voon CHANG Toshimitsu USHIO Shigemasa TAKAI Sadatoshi KUMAGAI Shinzo KODAMA
Many typical control problems such as deadlock avoidance problems and mutual exclusion problems can be formulated as forbidden marking problems. This paper studies a forbidden marking problem in controlled complementary-places Petri nets, which are suitable model for sequential control systems. We show a necessary and sufficient condition for the existence of a control law for this problem. We also obtain a maximally permissive control law which allows a maximal number of transitions to fire subject to a condition that forbidden markings will never be reached.
We give an efficient shortest path algorithm on a mesh-connected processor array for nn banded matrices with bandwidth b. We use a b/2b/2 semisystolic processor array. The input data is supplied to the processor array from the host computer. The output from the processor array can be also supplied to itself through the host computer. This algorithm computes all pair shortest distances within the band in 7n4b/21 steps.
We model a road network as a directed graph G(V,E) with a source s and a sink t, where each edge e has a positive length l(e) and each vertex v has a distribution function αv with respect to the traffic entering and leaving v. This paper proposes a polynomial time algorithm for evaluating the importance of each edge e E whicn is defined to be the traffic f(e) passing through e in order to assign the required traffic Fst(0) from s to t along only shortest s-t paths in accordance with the distribution function αv at each vertex v.
In this study we shall put forward a synergetic neural network and investigate the association dynamics. The present neuron model is substantially based on a top down formulation of the dynamic rule of an analog neural network in contrast to the conventional framework. It is proved that a complete association can be assured up to the same number of the embedded patterns as the number of neurons. In practice an association process is carried out for practical images with 256 gray scale levels and 256256 size. In addition, a searching process of the embedded patterns is also realised by means of controlling attraction parameters. Finally a stochastic model for the dynamic process is also proposed as an intermediate model between the association and the searching of the embedded patterns. Finally a stochastic property of the present model is characterized by fractal dimension of the excitation level of a neuron.
This paper presents 1V supply voltage Bi-CMOS current mode circuits. The circuits are consist of current mirrors, current comparators and current sources. The circuits have some advantages such as high accuracy, high speed, high density and low power supply. As an application of the circuits, an analog-to-digital converter (ADC) is given. The ADC operates with small chip area and low power dissipation. The performances of the proposed circuits were confirmed by using SPICE2 simulation.
This paper discusses a CMOS differential-difference amplifier circuit suitable for low voltage operation. A new multiple weighted input transconductor circuit structure is suggested to be use in DDA implementation. The proposed DDA can be employed in several analog/digital systems to improve their parameters. Selected examples of the proposed transconductor/DDA applications are also discussed.