This paper describes a VLSI processor architecture designed for a back-propagation accelerator. Three techniques are used to accelerate the simulation. The first is a multi-processor approach where a neural network simulation is suitable for parallel processing. By constructing a ring network using several processors, the simulation speed is multiplied by the number of the processors. The second technique is internal parallel processing. Each processor contains 4 multipliers and 4 ALUs that all work in parallel. The third technique is pipelining. The connections of eight functional units change according to the current stage of the back-propagation algorithm. Intermediate data is sent from one functional unit to another without being stored in extra registers and data is processed in a pipeline manner. The data is in 24-bit floating point format (18-bit mantissa and 6-bit oxponent). The chip has about 88,000 gates, including microcode ROM for processor control, the processor is designed using 0.8-µm CMOS gate arrays, and the estimated performance at 40 MHz is 20 million connection updates per second (MCUPS). For a ring network with 4 processors, performance can be enhanced up to 90 MCUPS.

This paper proposes a test case generation method for testing concurrent programs as a black box. Typical applications are system testing for switching systems and inter-operability testing for OSI products. We adopt a two-step approach: first generate the control flow graph which represents global behaviors of a given concurrent program, and then apply conventional test case generation methods for the control flow graph. To generate a control flow graph without state space explosion, the black-box equivalence between system behaviors is introduced. The proposed algorithm generates a minimal control flow graph which consists of representatives of equivalence classes. Two practical techniques for the second step are discussed for a case study using a commercial digital PBX. The results show the feasibility of the proposed method.

Air-bridge metal interconnection technology is used for upper level power supply line interconnections in GaAs LSI's to reduce the signal propagation delay time. This technology reduces both parasitic capacitance between the signal line and the power supply line, and propagation delay in the signal line to about 10% and about 50%, respectively, compared to conventional 3-level interconnections without air-bridges. Under standard load conditions (FI=FO=2, length of load line=2 mm), the air-bridge technique leads to gate propagation delays which are about 60% of those in conventional interconnections. We fabricated 2.1-k gate Gate Arrays and 4-kb SRAM's using the air-bridge structure to interconnect power supply lines. For a Gate Array with 0.7 µm gate Buried P-layer Lightly Doped Drain (BPLDD) FET's, the typical gate propagation delay under standard load conditions was about 110 ps with a dissipation power of 1.4 mW/gate. SRAM's with 05 µm gate BPLDD's had typical access time (tacc) of 1.5 ns with a dissipation power of 700 mW/chip.

The subject of the paper is to propose two approximation algorithms FM_SPLA, FM_DPLA for priority-list scheduling in timed Petri nets. Their capability is compared with that of existing algorithms SPLA, DPLA through experimental results, where SPLA and DPLA have previously been proposed by the authors.

This paper describes MENDELS ZONE, a Petri-net-based concurrent programming environment, which is especially suitable for cooperating discrete event systems. MENDELS ZONE adopts MENDEL net, which is a type of high level (hierarchical colored) Petri net. One of the characteristics of the MENDEL nets is a process-oriented hierarchy like CCS, which is different from the subnet-oriented hierarchy in the Jensen's hierarchical colored Petri net. In a process-oriented hierarchy, a hierarchical unit is a process, which is more natural for cooperating and decentralized discrete event control systems. This paper also proposes a design methodology for MENDEL nets. Although many Petri net tools have been proposed, most tools support only drawing, simulation, and analysis of Petri nets; few tools support the design methodology for Petri nets. While Petri nets are good final design documents easy to understand, analyzable, and executable it is often difficult to write Petri nets directly in an earlier design phase when the system structure is obscure. A proposed design methodology makes a designer to construct MENDEL nets systematically using causality matrices and temporal logic. Furthemore, constructed MENDEL nets can be automatically compiled into a concurrent programming language and executed on a parallel computer.

A job shop system typically seen in flexible manufacturing systems (FMS) is a system composed of a set of machines and a various kind of jobs processed with the machines. A production system of semiconductor fabrication is an example of job shop systems, which has main features of repetitive processes of one part and set-up times required for machines processing different types of parts. On the other hand, timed Petri nets are used for modelling and analyzing a wide variety of discrete event systems. There are many applications of timed Petri nets to the scheduling problems of job shop systems. The performance evaluation and steady state behaviors are studied by using the maximum cycle time of timed marked graphs. The aim of this paper is to propose a new model for production systems including repetitive processes and set-up time requirements which enables the quantitative analysis of real time system performance. In job shop systems such as a semiconductor fabrication system, it takes considerable amount of set-up time to prepare different types of chemical reactions and the model should take account of a set-up time for each machine. We focus upon the relationship between facility utilization factor and production cycle time in the steady state. In the proposed model, the minimum total set-up time can be attained. Quantitative relationship between utilization factor and production cycle time is derived by using the proposed model. A utilization factor of a system satisfying a given limit of the cycle time is evaluated, and the improvement of the utilization factor is considered. Conversely, we consider the improvement of the cycle time of a system satisfying a given limit of utilization factor.

Many practical communication protocols provide priority service as well as ordinary service. In such a protocol, the protocol machines can initiate a priority service at most of the states. This characteristic leads an extreme increment of the number of state transitions on the protocol machines and causes state space explosion in verification of safety property of the protocol. This paper describes a method of constructing a communication protocol from composition of a subprotocol for ordinary service and that for priority service. This paper also presents a sufficient condition for a composed protocol to inherit safety property from the subprotocols. By using the composition method and the sufficient condition, the decision problem for safety property of the composed protocol can be reduced to those of the subprotocols. An experimental result of verification of a part of OSI session protocol is also described. The result shows that the method can reduce the computation time for verifying safety property to about 3% against the naive way.

The throughput of a parallel execution of a Digital Signal Processing (DSP) algorithm is limited by the iteration bound, which is the minimum period between the start of consecutive iterations. It is given by T=max (Ti/Di), where Ti and Di are the total time of operations and the number of delays in loop i, respectively. A schedule is said rate-optimal if its iteration period is T. The throughput of a DSP algorithm execution can be increased by reducing the Ti's, which can be done by taking as many operations as possible out of loops without changing the semantic of the calculation. This paper presents an optimization technique, called Loop Shrinking, which reduces the iteration bound this way by using commutativity, associativity and distributivity. Also, this paper presents a scheduling method, called Period-Driven Scheduling, which gives rate-optimal schedules more efficiently than existing approaches. An implementation of both is then presented for a system in development by the authors. The system shows reduction in the iteration bound near or equal to careful hand-tunning, and hardware-optimal designs in most of the cases.

This paper describes a reduction algorithm for SW method which generates test sequences for communication systems. SW method is based upon the Finite State Machine (FSM). SW method uses a set of characterizing sequences and a state transition checking approach. This paper concentrates the characteristics of the SW sequences, and proposes the new derivation algorithm of characterizing sequences. Furthermore, Chinese Postman Tour and Extended Chinese Postman Tour is proposed to reduce redundancy of the SW sequences. This paper also presents an evaluation of this method in terms of an upper bound of the sequence length and generated test sequence length. The evaluation shows that the algorithm dramatically reduces the sequence length of the original method.

This paper presents a method for LSI implementation of a long-tap acoustic echo canceller algorithm using the residue number system (RNS) and the mixed-radix number system (MRS). It also presents a quantitative comparison of echo canceller architectures, one using the RNS and the other using the binary number system (BNS). In the RNS, addition, subtraction, and multiplication are executed quickly but scaling, overflow detection, and division are difficult. For this reason, no echo canceller using the RNS has been implemented. We therefore try to design an echo canceller architecture using the RNS and the NLMS algorithm. It is shown that the echo canceller algorithm can be effectively implemented using the RNS by introducing the MRS. The quantitative comparison of echo canceller architectures shows that a long-tap acoustic echo canceller can be implemented more effectively in terms of chip size and power dissipation by the architecture using the RNS.

This paper surveys modeling techniques for telephone call control based on a Finite State Machine (FSM) concept, and studies model simplification techniques. First, the basic concept and fundamental issues of call control modeling are described. Then, based on the analysis of layered call control configuration, it is clarified that the call control machine decomposition within the two-party service control layer has the effect of reducing the apparent size of each mate's machine. Using this effect, guidelines for call control modeling are derived, by which multiple services can be modeled independently. Finally implementation techniques and a few examples of application will be presented.

This paper presents unique specification environments for LOTOS, which is one of FDTs (Formal Description Techniques) developed in ISO. We first discuss the large gap in terms of syntax and semantics between informal specifications at the early stage of specification design and formal specifications based on FDT such as LOTOS. This large gap has been bridged by human intelligent works thus far. In order to bridge the large gap, we have designed user-friendly specification environments for FDTs. The outlines of SEGL (Specification Environment for G-LOTOS), CBP (Concept-Based Programming environment) and MBP (Model-Based Programming environment) are described. The effectiveness of software development under such an environment is demonstrated using application examples from OSI and non-OSI protocols.

This paper describes a modeling of the cryptography based on a concept of Petri nets. Movement of tokens in the net model shows a dynamic behavior of systems. On the other hand, the cryptography is considered as a bit operation, so that we can point out a common property between the net structure and the cryptography, which provides our idea that movement of tokens of the net model corresponds to a bitoperation of the cryptography. Some effective keys in the net model are considered by means of the net elements, which are based on T-invariant and net structures. It is shown that the keys of the net structured cryptography provide reasonable strength comparing with the data encryption standard (DES).

In order to make the implementation of network components flexible and cost effective, it is required to use widely available technologies as the implementation platform. The distributed operating systems can be adopted as such a platform, because they allow to implement a network component using multiple computers connected through a local area network. In this paper, we focus on the Intelligent Network (IN) whose network components are modelled as Functional Entities (FEs), and describe an implementation method of FEs using distributed operating systems. Our method is summarized as follows: The remote procedure call (RPC) is used for the access transparent inter-process communication. The lightweight process mechanism is used for handling concurrent requests. CCF/SSF (Call Control Function/Service Control Function) and SDF (Service Data Function) are implemented as an SSF server and an SDF server, respectively. SCF (Service Control Function) is composed of a Service Dispatcher and a set of Service Executors. The Service Dispatcher accepts all the requests for IN call processing and dispatches them to appropriate Service Executors. Service Executors are created for the individual IN services and execute the service logics. SDF server and Service Executor may be replicated for load partitioning.This paper has also described the implementation of experimental system supporting "Freephone" service based on our method, and showed the performance evaluation of the experimental system in terms of the real-time and concurrent call processing of IN services. We used Mach and SUN OS as a platform for implementing the servers for FEs. The experimental system using four workstations shows that it can handle up to 170IN calls in one second with the additional response time of less than 200msec, which is small enough compared with the response time for the basic connection control. Those results prove that our method is feasible for implementing practical FEs.

The paper describes the design considerations, fabrication process and performance of the newly developed 1-K ECL gate array implemented with fully self-aligned AlGaAs/GaAs hoterojunction bipolar transistors (HBTs). This gate array consists of 960 three-input OR/NOR ECL basic gates. It contains about 7,600 transistors in a chip area 8.15-mm8.45-mm. The basic (FI=FO=1, wiring length L=0-mm) and loaded (FI=FO=3, L=1-mm) gates exhibit delay times of 33-ps and 82-ps, respectively, with 8.5-mW/gate power dissipation. From the measured values, fan-in, fan-out and wiring delay times of 9-ps/FI, 7-ps/FO and 17-ps/mm are estimated, respectively. These results are in good agreement with the designed results obtained using "SPICE" simulation.

In most of the methods proposed so far to design approximately linear phase IIR digital filters (IIR DFs), the design takes place only in the time or in the frequency domain. However, when both magnitude and phase responses are considered, IIR DFs with better frequency responses can be obtained if their characteristics in both domains are taken into account. This paper proposes a design method for approximately linear phase IIR DFs, which is based on parameter estimation techniques in the time domain followed by a nonlinear optimization algorithm in the frequency domain. Several examples are presented, illustrating the proposed method.

In this paper, the software structure for telecommunication user support are discussed, and it is proposed to apply knowledge processing technology to the software. Capabilities of telecommunications networks are becoming quite complicated, and the number of service items and parameters which have to be selected and memorized will become too large for telecommunications end users to make full use of the network capabilities. As such, more effort should be focused on assisting telecommunications end users to use the network and providing user friendly human interfaces of the network. However, this kind of software has additional type of requirements other than those for protocol handling software and call control software, and the realization of such support software has not yet been fully studied. To realize such support software, this paper stressed the realization of the user-system interface. Especially identified in this paper are meaning-based interpretation of user inputs to permit the handling of synonyms and multivocations, and a method to access the database in the support system without consideration of its data schema. To satisfy these objectives, this paper has proposed that the application data should be represented in both a character string and a meaning representation, and that the thesauruses should have the attribute-value relation. In line with these studies, an experimental system called CAPRIS (CAlling PRocedure Instruction System) was developed. It is used to assist the calling party in a telecommunications network to find an appropriate contact point depending on the purpose of the communication. Implementation of CAPRIS is completed and it was confirmed that all the functions described in this paper were actually realized. Some functional experiments were performed on CAPRIS, and the system was concluded to realize satisfactory user-friendliness.

This paper presents a protocol verification method which verifies that the behaviors of a protocol meet requirements. In this method, a protocol specification is expressed as Extended Finite State Machines (EFSM's) that can handle variables, and requirements are expressed using a branching-time temporal logic for a concise and unambiguous description. Using the acyclic expansion algorithm extended such that it can deal with EFSM's, the verification method first generates a state transition graph consisting of executable transitions for each process. Then a branching-time temporal logic formula representing a requirement is evaluated on one of the generated graphs which is relevant to the requirement. An executable state transition graph for each process is much smaller than a global state transition graph which has been used in the conventional verification techniques to represent the behaviors of the whole protocol system consisting of all processes. The computation for generating the graphs is also reduced to much extent for a large complex protocol. As a result, the presented method achieves efficient verification for requirements regarding a state of a process, transmission and reception of messages by a process, varibales of a process and sequences that interact among processes. The validity of the method is illustrated in the paper by the verification of a path-updating protocol for requirements such as process state reachability or fair termination among processes.

The pursuit of higher availability has resulted in the development of fault tolerant systems for many industries. However, system characteristics that can be perceived by the customer have never been diagnosed quantitatively. This paper considers the application of stochastic Petri nets with general firing times to modeling of a fault tolerant system and the use of discrete-event simulation methods for stochastic Petri nets to study the behavior of the system. The stochastic Petri net model incorporates factors that compose the system as well as those that accompany it, including RAS characteristics of products, personnel arrangements, and system management. By modeling the behavioral aspect of each factor, it is possible to diagnose a fault tolerant system quantitatively on the basis of customer impact.

The subject of the paper is the minimum initial marking problem for scheduling in timed Petri net PN: given a vector X of nonnegative integers, a P-invariant Y of PN and a nonnegative integer π, find an initial marking M minimizing the value YtrM among those initial marking M such that there is a scheduling σ having the total completion time τ(σ)π with respect M , X and PN (a sequence of transitions, with the first transition firable on M , such that every transition t can fire prescribed number X(t) of times). The paper shows NP-hardness of the problem and proposes two approximation algorithms with their experimental evaluation.