In a distributed concurrent system such as a computer communication network, the system components communicate with each other via communication links in order to accomplish a desired distributed application. If the links are dynamically established among the components, the system configuration as well as its behavior becomes complex. In this paper, we give formal specification of such a dynamically reconfigurable system in which the components are modeled by communicating finite state machines executed concurrently with the communication links which are dynamically established and disconnected. We also present an algorithm to validate the safety and link-related properties in the specified behavior. Finally, we design and implement a simulator and a validator that enables execution and validation of the given specification, respectively.

Verification of responsive communication protocols is to determine whether they can recover to a normal state within a predetermined time, even when they enter an abnormal state due to any fault. In this paper, we propose a new verification method for responsive communication protocols using virtual system states, each of which represents several system states. Next, in order to evaluate the effectiveness of the new method, we develop a verification tool based on the proposed method. Then we apply the tool to a broadcasting protocol and measure several metrics on the tool. The experimental results show that (1) the number of system states, (2) the amount of memory used by the tool, and (3) the execution time of the tool, can be drastically reduced.

Handprinted Chinese character recognition (HCCR) can be classified into two major approaches: statistical and structural. While neither of these two approaches can lead to a total and practical solution for HCCR, integrating them to take advantages of both seems to be a promising and obviously feasible approach. But, how to integrate them would be a big issue. In this paper, we propose an integrated HCCR system. The system starts from a statistical phase. This phase uses line-density-distribution-based features extracted after nonlinear normalization to guarantee that different writing variations of the same character have similar feature vectors. It removes accurately and efficiently the impossible candidates and results in a final candidate set. Then follows the structural phase, which inherits the line segments used in the statistical phase and extracts a set of stroke substructures as features. These features are used to discriminate the similar characters in the final candidate set and hence improve the recognition rate. Tested by using a large set of characters in a handprinted Chinese character database, the proposed HCCR system is robust and can achieve 96 percent accuracy for characters in the first 100 variations of the database.

In this paper, Wavelength Division Multiple access (WDM) ring is proposed for interconnection in workstation clusters or parallel machines. This network consists of ring connected routers each of which selectively passes signals addressed in some particular wavelengths. Other wavelengths are once converted to electric signals, and re-transmitted being addressed in different wavelengths. Wavelengths are assigned to divisors of the number of nodes in the system. Using the regular WDM ring with imaginary nodes, the diameter and average distance are reduced even if the number of nodes has few divisors. It provides better diameter and average distance than that of the uni-directional torus. Although the diameter and average distance is worse than that of ShuffleNet, the physical structure of the WDM ring is simple and the available number of nodes is flexible.

A formal necessary and sufficient condition on the general Petri net reachability problem is presented by eliminating all spurious solutions among known nonnegative integer solutions of state equation and unifying all the causes of those spurious solutions into a maximal-strongly-connected and siphon-and-trap subnet Nw. This result is based on the decomposition of a given net (N, Mo) with Md and the concepts of "no immature siphon at the reduced initial marking Mwo" and "no immature trap at the reduced end marking Mwd" on Nw which are both extended from "no token-free siphon at the initial marking Mo" and "no token-free trap at the end marking Md" on N, respectively, which have been both effectively, explicitly or implicitly, used in the well-known fundamental and simple subclasses.

Parallelism on heterogeneous machines brings cost effectiveness, but also raises a new set of complex and challenging problems. This paper addresses the problem of estimating the minimum time taken to execute a program on a fine-grained parallel machine composed of different types of processors. In an earlier publication, we took the first step in this direction by presenting a graph-construction method which partitions a given program into several homogeneous parts and incorporates timing constraints due to heterogeneous parallelism into each part. In this paper, to make the method easier to be applied in a scheduling framework and to demonstrate its practical utility, we present an efficient implementation method and compare the results of its use to the optimal schedule lengths obtained by enumerating all possible solutions. Experimental results for several different machine models indicate that this method can be effectively used to estimate a program's minimum execution time.

We present a method for learning classification functions from pre-classified training examples and hypotheses written roughly by experts. The goal is to produce a classification function that has higher accuracy than either the expert's hypotheses or the classification function inductively learned from the training examples alone. The key idea in our proposed approach is to let the expert's hypotheses influence the process of learning inductively from the training examples. Experimental results are presented demonstrating the power of our approach in a variety of domains.

This paper proposes an analysis method of scaling-factor-quantization error in fractal image coding using a state-space approach with the statistical analysis method. It is shown that the statistical analysis method is appropriate and leads to a simple result, whereas the deterministic analysis method is not appropriate and leads to a complex result for the analysis of fractal image coding. We derive the output error variance matrix for the measure of error and define the output error variance by scalar quantity as the mean of diagonal elements of the output error variance matrix. Examples are given to show that the scaling-factor-quantization error due to iterative computation with finite-wordlength scaling factors degrades the quality of decoded images. A quantitative comparison of experimental scaling-factor-quantization error with analytical result is made for the output error variance. The result shows that our analysis method is valid for the fractal image coding.

Since spontaneously spoken language expressions appear continuously, the transfer stage of a spoken language machine translation system have to work incrementally. In such the system, the high degree of incrementality is also strongly required rather than that of quality. This paper proposes an incremental machine translation system, which translates English spoken words into Japanese in accordance with the order of appearances of them. The system is composed of three modules: incremental parsing, transfer and generation, which work synchronously. The transfer module utilizes some features and phenomena characterizing Japanese spoken language: flexible wordorder, ellipses, repetitions and so forth. This in influenced by the observational facts that such characteristics frequently appear in Japanese uttered by English-Japanese interpreters. Their frequent utilization is the key to success of the exceedingly incremental translation between English and Japanese, which have different word-order. We have implemented a prototype system Sync/Trans, which parses English dialogues incrementally and generates Japanese immediately. To evaluate Sync/Trans we fave made an experiment with the conversations consisting of 27 dialogues and 218 sentences. 190 of the sentences are correct, providing a success rate of 87.2%. This result shows our incremental method to be a promising technique for spoken language translation with acceptable accuracy and high real-time nature.

The present paper gives a new formulation for rough surface scattering in terms of a stochastic integral equation which can be dealt with by means of stochastic functional approach. The random surface is assumed to be infinite and a homogeneous Gaussian random process. The random wave field is represented in the stochastic Floquet form due to the homogeneity of the surface, and in the non-Rayleigh form consisting of both upward and downward going scattered waves, as well as in the extended Voronovich form based on the consideration of the level-shift invariance. The stochastic integral equations of the first and the second kind are derived for the unknown surface source function which is a functional of the derivative or the increment of the surface profile function. It is also shown that the inhomogeneous term of the stochastic integral equation of the second kind automatically gives the solution of the Kirchhoff approximation for infinite surface.

This paper proposes a heuristic algorithm for state minimization of incompletely specified finite state machines (FSMs). The strategy is similar to that in ESPRESSO, a wellknown heuristic algorithm for two-level logic minimization. It consists of generating an initial solution, the set of maximal compatibles, and attempting to apply a series of transformations to the solution. The main transformation is to reduce each compatible in the solution and delete unnecessary compatibles by iterative improvements. Other transformations, such as expansion and merging of compatibles, are also introduced for further reduction. When the number of compatibles is likely to be too large to handle explicitly, they are represented by a Binary Decision Diagram. Experimental results show that the proposed method finds better solutions in shorter CPU times for most of the examples than conventional methods.

Connectionless data from existing network applications compose a large portion of the workload during an early ATM deployment, and are likely to make up an important portion of ATM's workload even in the long term. For providing a connectionless service over the ATM network, we compare two approaches; an indirect and a direct approaches, which are adopted by International Telecommunication Union-Telecommunication (ITU-T) as generic approaches. Our main subject of this paper is to compare network costs of two approaches by taking into account several cost factors such as transmission links, buffers, and connectionless servers in the case of the direct approach. Since the cost of the direct approach heavily depends on the configuration of a virtual connectionless overlay network, we propose a new heuristic algorithm to construct an effective connectionless overlay network topology. The proposed algorithm determines an optimal number of connectionless servers and their locations to minimize the network cost while satisfying QoS requirements such as maximum delay time and packet loss probability. Through numerical examples, we compare the indirect and direct approaches, the latter of which is constructed by means of our proposed algorithm.

This paper introduces an object-based distributed shared memory (DSM) system called Adsmith. The primary goal of Adsmith is to provide a low-cost, portable, and efficient DSM for networks of workstations (NOW). Adsmith achieves this goal by building on top of PVM, a widely supported communication subsystem, as a user-level library and by incorporating many traffic reduction and latency hiding techniques. Issues involved in the design of Adsmith and our solution strategies will be discussed. Preliminary performance evaluation of Adsmith on a network of Pentium computers will be presented. The results show that programs developed with Adsmith can achieve a performance comparable to that developed with PVM.

JUMP-1 is currently under development by seven Japanese universities to establish techniques for building an efficient distributed shared memory on a massively parallel processor. It provides a coherent cache with reduced hierarchical bit-map directory scheme to achieve cost effective and high performance management. Messages for coherent cache are transferred through a fat tree on the RDT (Recursive Diagonal Torus) interconnection network. RDT router supports versatile functions including multicast and acknowledge combining for the reduced hierarchical bit-map directory scheme. By using 0.5µm BiCMOS SOG technology, it can transfer all packets synchronized with a unique CPU clock (50MHz). Long coaxial cables (4m at maximum) are directly driven with the ECL interface of this chip. Using the dual port RAM, packet buffers allow to push and pull a flit of the packet simultaneously.

A novel approach to the cache coherent Multistage Interconnection Network (MIN) called the MINC (MIN with Cache control mechanism) is proposed. In the MINC, the directory is located only on the shared memory using the Reduced Hierarchical Bit-map Directory schemes (RHBDs). In the RHBD, the bit-map directory is reduced and carried in the packet header for quick multicasting without accessing the directory in each hierarchy. In order to reduce unnecessary packets caused by compacting the bit map in the RHBD, a small cache called the pruning cache is introduced in the switching element. The simulation reveals the pruning cache works most effectively when it is provided in every switching element of the first stage, and it reduces the congestion more than 50% with only 4 entries. The MINC cache control chip with 16 inputs/outputs is implemented on the LPGA (Laser Programmable Gate Array), and works with a 66 MHz clock.

In client-server database management systems (DBMSs), inter-transaction caching is an effective technique for improving the performance. However, inter-transaction caching requires a cache consistency maintenance (CCM) protocol to ensure that cached copies at clients are kept mutually consistent. Such a protocol could be complex to implement and expensive to run, since several rounds of message exchange may be required. In this paper, we propose a new CCM scheme based on the primary-copy locking algorithm. In the proposed scheme, a number of lock requests and a data-shipping request are combined into a single message packet to reduce client-server interactions, which are known to be very critical to the performance of clientserver DBMSs. We examine its performance tradeoffs on the basis of a simulation model under a wide range of workloads. The performance results indicate that the proposed scheme improves the overall system throughput significantly over the caching two-phase locking and the optimistic two-phase locking scheme. Its higher performance mainly results from its lower communication overhead and lower degree of transaction blocking ratio.

This paper describes a guiding principle for designing functional single-electron tunneling (SET) circuitsthat is a way to elicit the potential functions of a given SET circuit by using as a guiding tool the SET circuit stability diagram. A stability diagram is a map that depicts the stable regions of a SET circuit based on the circuit's variable coordinates. By scrutinizing the diagram, we can infer all the potential functions that can be obtained from a circuit configuration. As an example, we take up a well-known SET-inverter circuit and uncover its latent functions by studying the circuit configuration, based on its stability diagram. We can produce various functions, e.g., step-inverter, Schmidt-trigger, memory cell, literal, and stochastic-neuron functions. The last function makes good use of the inherent stochastic nature of single-electron tunneling, and can be applied to Boltzmann-machine neural network systems.

In microprocessors, reducing the cache access delay and the number of pipeline stall is critical to improve the system performance. In this paper, we propose a Separated Word-line Decoding (SEWD) cache to overcome the pipeline stall caused by the misaligned multi-words data or instruction prefetches which are placed over two cache lines. SEWD cache makes it possible to perform misaligned prefetch as well as aligned prefetch in one clock cycle. This feature is invaluable because the branch target addresses are very often misaligned (Percentage of misalignment in the cache is 8 to 13% for 16-byte caches). 8Kbyte SEWD cache chip was implemented in 0.8µm DLM CMOS process. It consists of 489,000 transistors on a die size of 0.8530.827cm2.

This paper focuses on recovering from processor transient faults in pipelined multiprocessor systems. A pipelined machine may employ out of order execution and branch prediction techniques to increase performance, thus a precise computation state would not be available. We propose an efficient scheme to maintain the precise computation state in a pipelined machine. The goal of this paper is to implement checkpointing and rollback recovery utilizing the technique of precise interrupt in a pipelined system. Detailed analysis is included to demonstrate the effectiveness of this method.

A 167-MHz 1-Mbit CMOS synchronous cache SRAM was developed using 0.40-µm process technology. The floor plan was designed so that the address registers are located in the center of the chip, and high-speed circuits were developed such as the quasi latch (QL) sense amplifier and the one-shot control (OSC) output register. To maintain suitable setup and hold time margins, an equivalent margin (EM) design method was developed. 167-MHz operation was measured at a supply voltage of 2.5 V and an ambient temperature of 75. The same margins 1.1 ns of the setup time and hold time were measured for the specifications of a setup time of 2.0 ns and a hold time of 0.5 ns.