The problem of embedding two-dimensional grids into hypercube parallel computers is the main subject of this work. Two methods (called dilation 1 and dilation 2 embedding) are used to embed a grid and their performances are evaluated. In dilation 1 (d1) embedding a grid edge connecting 2 points is mapped into one hypercube link, and in dilation 2 (d2) embedding there are cases in which one grid edge is mapped into two hypercube links. Generally, this makes the performance of d2 embedding poorer than that of d1 embedding, as communication between some adjacent grid points have to be forwarded through an intermediate link. However, there are cases where d2 embedding allows a more efficient use of the hypercube, as more processors can be used in the embedding. Thus, it is necessary to find out what kind of embedding achieves the best performance. We assume that the number of grid points is larger than the number of processors, and then propose a method to divide the grid in rectangular parts of arbitrary size called fragments, which are actually embedded into a processor. Using the parameters of a commercial hypercube, the performances of several grids embedded under different conditions are evaluated. As a result, the relation between hypercube size and grid size is found to have a strong influence on the choice of the embedding method.

In this paper, a scheme for recoverability of protocols, which have more than one process and can be modelled by communicating finite state machines, is studied. Normal operating states of a protocol are defined as the set of global states that can be reached by executing state transitions in which error events have not occurred. After some error events have occurred, sequences of state transitions enter abnormal operating states. If the protocol is recoverable, then the sequences revert back to a normal operating state. In real recoverable protocols, the sequences often return to a typical normal operating state, that is, an initial state while retaining consistency in the exchange of messages. This paper proposes a new rollback-recovery scheme for recoverable protocols. In this scheme, the sequences can return not only to an initial state but also to an intermediate state which was reached in the past while retaining consistency in the exchange of messages. In addition, protocols can efficiently return to the intermediate state using a broadcast mechanism. The proposed scheme is therefore effective for recoverability of protocols with more than one process. This paper also presents a recovery sequence generation system which has been developed for designing recoverable protocols and some experiments are carried out to show effectiveness of the proposed scheme.

Some vision systems have been using the same algorithms for many years. These systems usually require high system efficiency at the cost of flexibility for algorithm changes. Various hardware systems dedicated to visual processing applications were developed for high system efficiency. We extended the capabilities of existing binary or gray-level image correlation hardware systems by developing application-specific processor architectures for binary edge correlation. The edge correlation algorithm works well even if the contrast of gray-level image is not good enough for extracting the object with a binary threshold. The binary edge correlation systems require less computational loads compared to typical gray-level image correlation systems. Two types of real-time edge calculation modules have been developed in this project; one for monochrome and the other for color images. The color edge module eliminates edges of shadows by defining discontinuous points of color balances as edges. We developed a different dedicated module for each of correlation, spatial gradient calculation, and edge thinning operations for improving the efficiency of existing general-purpose two dimensional convolution modules. The correlation and image smoothing functions were implemented in application-specific integrated circuit chips. Dedicated boards were developed for the other functions. The binary edge correlation systems (including related modules, such as multi-resolution correlation) have been evaluated in bench tests. The edge calculation portion or the binary edge correlation systems works at frame rates. Bench tests with a slow system clock indicate that the speed of the correlation portion is 1.710² times faster than a typical microprocessor system with the same system clock speed.

This paper describes how to use the amount of information in a sentence interpretation as a measure of interpreting input sentences in a natural language understanding system. In this paper, an interpretation of a sentence is considered to be a proposition, and the amount of information of the interpretation is defined according to a listener's model with a knowledge base composed of a literal set and a logical implication set, both of which are defined within the framework of propositional logic. When a given sentence can be analyzed syntactically and semantically into more than one interpretation, the most informative interpretation is selected. The theory of selecting the most informative interpretation by the proposed measure is reasonable in the sense that communication is an act whereby messages are passed on with the least possible effort. The presented theory for disambiguation is applied to a practical procedure for anaphoric ambiguity resolution, as an example of the disambiguation problem, which forms part of a question-answering system. Furthermore, a conversation experiment was carried out, and it was found that ninety-three percent of referents corresponding to anaphoric expressions could be correctly chosen.