摘要:

AbstractLocal parallel processing is effective for such fields as image processing where problems are essentially two‐dimensional. Here, we propose the two‐dimensional Omega network as an interconnection network suitable for SIMD multiprocessor systems used in such fields. The two‐dimensional Omega network is an interconnection network devised to apply two‐dimensional permutation to local data obtained in parallel from a two‐dimensional array. The structure of inputs and outputs is anN × Ntwo‐dimensional array, and the number of levels is log2N.Here, we will define two‐dimensional permutation as one‐to‐one mapping on the set whose elements are pairs of indices of a two‐dimensional array. Among possible two‐dimensional permutations, are two‐dimensional shift and rotation. We will show the conditions for admissible permutations on the two‐dimensional Omega network. As for hardware, the complexity isN2/4 m log2Nand the delay time is log2N; of the same order as conventional Omega networks. Furthermore, we will discuss the case where the two‐dimensional Omega network has computing capability. We show that sum, maximum, and minimum of elements in two‐dimensional arrays, and two‐dimensional Fourier transforma

ISSN:0882-1666    

DOI:10.1002/scj.4690171101

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1986

数据来源: WILEY

摘要:

AbstractThe communication sequential processes (CSP) system proposed by Hoare is a model for parallel computation which has no shared variables and performs information exchange and synchronization among processes by means of communication commands. In this paper we first consider a set of states for the given CSP program. Using a binary relation on the set, we introduce a semantics representing only the input‐output relations of the CSP program. Based on this semantics, we propose an axiom system which serves to verify the partial correctness of CSP. We prove the soundness of this axiom system. The axiom system proposed in this paper differs from the previously proposed systems in the following aspects. In our system, the inferences proceed simultaneously over all processes. On the other hand, conventional methods adopt a procedure wherein a given property is first proved independently for each process and it is then shown that a certain condition holds among the processes. Our method of proof is a more direct representation of the actual execution of proces

ISSN:0882-1666    

DOI:10.1002/scj.4690171102

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1986

数据来源: WILEY

摘要:

AbstractA data link with multiple lines can be implemented by using the standard protocol of a multilink procedure. The multilink procedure achieves performance flexibility and reliability improvement. This paper proposes line scheduling methods at a sending station, which is an important factor for implementing multilink procedures, and evaluates their performance. A line scheduling for a multilink procedure selects a line to which a multilink frame, which is the transfer data unit, is assigned. The speed of the lines may be equal or different. The following methods are studied: (1) rotational scheduling, (2) stochastic scheduling and (3) adaptive scheduling. The adaptive scheduling method is shown to have the best performance. For easy implementation it is shown that the rotational scheduling method can be applied to lines with equal speeds and that the stochastic scheduling method can be applied to the lines with equal or different speeds.

ISSN:0882-1666    

DOI:10.1002/scj.4690171103

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1986

数据来源: WILEY

摘要:

AbstractThis paper proposes a square root hardware algorithm using the redundant binary representation in the internal computation. A discussion is made for the realization of a combinational square‐rooter based on the algorithm. This paper considers the computation of the mantissa in square‐rooting for the binary normalized floating‐point representation. The proposed algorithm is a kind of subtract‐and‐shift square‐root method. Partial remainders are represented by the redundant binary representation, where each digit is an element of {‐1, 0, 1}. Then each digit of the square root is determined from {‐1, 0, 1}, by examining the upper three digits of the partial remainder. The computation for the partial remainder is affected in the redundant binary number system. Finally, the square root determined in the redundant binary representation is converted into the ordinary binary representation. In the redundant binary representation, the addition of two numbers can be effected without carry propagation. Consequently, by using the combinational circuit, each digit of the square root can be determined in a constant time, independently of the number of digits of the operand. The computation time for then‐bit square rooter (number of stages) is proportional ton.The number of logic elements in the circuit is proportional ton2. The hardware structure is a regular cellular array, which is suited for VLSI implementation. When the circuit is implemented on a VLSI chip, the chip is proportional ton2. The proposed square rooter has nearly the same circuit structure and the hardware complexity, compared with the conventional subtract‐and‐shift square rooter using ripple carry adder. The computation time is approximately one‐fifth for 32‐bit and one‐tenth for 64‐bit, c

ISSN:0882-1666    

DOI:10.1002/scj.4690171104

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1986

数据来源: WILEY

摘要:

AbstractThe detection of deadlock is one of the important problems in the database system. This paper proposes an efficient algorithm for detecting the deadlock in the concentrated database system, and demonstrates its correctness. The algorithm works as follows. When a process makes an access to a resource which is locked by another process, the process must wait for the resource. The algorithm detects the deadlock by tracing the edges of the resource graph, starting from the waiting process. By attaching the level number to each node, the number of edge tracings can be reduced, which helps to reduce the overhead for deadlock detection. To evaluate the efficiency of the proposed algorithm, an experiment was performed by computer simulation. The cases of the algorithm with and without the proposed level number are compared, indicating the effectiveness of the proposed method.

ISSN:0882-1666    

DOI:10.1002/scj.4690171105

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1986

数据来源: WILEY

摘要:

AbstractIn the automatic generation of the compiler, the area requiring further study is the automatic generation of a semantic analyzer. Several methods have been proposed to define the semantics, but a large‐scale description is required. From such a viewpoint, this paper aims at the construction of a compiler‐compiler which can describe the semantics efficiently. A self multiplicating compiler‐compiler (SMCC) was developed by the bootstrap technique used in the development of a new language. SMCC utilizes LL(1) grammar for the syntax analysis and attribute grammar for the semantic analysis. Not only the compiler, but also the SMCC itself can be described. Consequently, the SMCC can successively be extended and an efficient and complex compiler‐compiler can be generated much simpler than by the manual procedure. SMCC is described entirely by C language, and translates the definitions for the compiler or compiler‐compiler into C language. This paper describes the compiler‐compiler SMCC1 which is constructed manually and serves as the initial kernel, and SMCC2 and SMCC3, which are the result of extensions by SMCC1, together with their

ISSN:0882-1666    

DOI:10.1002/scj.4690171106

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1986

数据来源: WILEY

摘要:

AbstractThis paper describes the development of the syntax‐directed editor generator system (GED). The earlier syntax‐directed editors have some unsatisfactory points from the viewpoint of the user interface. The editor constructed by GED should realize the following three functions in order to improve the user interface: (1) top‐down programming is possible using the command template; (2) the delete, insert and replace of character strings can be made as the text editor; (3) the command defined by the user can easily be used. Giving the inputs such as syntax rules of the object programming language, the editor of that language is produced. For editing as texts, the incremental parser must be constructed in the generation of the editor. For this purpose, the incremental look‐ahead LR(1) (ILALR(1)) is proposed and applied which is an extension of the early

ISSN:0882-1666    

DOI:10.1002/scj.4690171107

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1986

数据来源: WILEY

摘要:

AbstractA high‐speed processing method of rotating two‐dimensional digital images by arbitrary angles is proposed. This method rotates images by combining two skew transformations of raster scanning alongXandYaxes. It makes possible group access to horizontally or vertically adjacent pixels in the memory, and shortens memory read/write time per pixel. Each skew transformation includes scale change of images in which the scale factor is approximated by a rational number. The resultant periodicity in transformation is used for high‐speed processing by simple table look‐up operation. The estimated rotation time of images is 250 ‐ 375 ns per pixel with a two‐dimensional memory of transfer speed 1 m̈s/word (1 word = 16 bits) and the pixel shift clock time 125 ns (8 MHz). The scaling error due to rational number approximation depends on the transformation table capacity. The table capacity being 32 or 16 digits, the error is approximately 0.3 or 0.8 percent, respectively. In applying to document image editing, the table of 16 to 32 digits is practically sufficient, implemented by a small number of IC's (about 100). The effectiveness of this method is justified with th

ISSN:0882-1666    

DOI:10.1002/scj.4690171108

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1986

数据来源: WILEY

摘要:

AbstractThis paper discusses a distortion model for handwritten characters and its ability of representation. The following three assumptions are made in constructing the distortion model: (1) a standard figure is pre‐set in correspondence to each character category; (2) the handwriting process is a sequential system with the standard figure as the input and the figure with distortion as the output; (3) the whole distortion is a combination of the deterministic and the stochastic distortions. The distortion model for the handwritten characters is constructed under the above assumptions. The feedback by the visual system during the handwriting process is regarded as a resorting force which affects a control on the stochastic distortion. The standard figure is considered as a combination of several elements, and the elements are estimated for each individual from handwritten character data. The distorted figure which is generated from the estimated standard figure, is considered to represent the handwritten character of the individual. Finally, the distance between figures is defined, and using it as the measure, the representation ability of the proposed distortion model is evaluated, indicating the usefulness of the mode

ISSN:0882-1666    

DOI:10.1002/scj.4690171109

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1986

数据来源: WILEY

摘要:

AbstractThe paper proposes a memory organization aiming at reduction of memory conflict produced by the multiple access. The proposed memory organization has the effect of suppressing not only the memory conflicts but also the write memory conflicts. The conflict of read access is suppressed by using more than one memory module of the same content, and the conflict of write access is suppressed by restricting the write area and using the distributed communication mechanism. It is shown by the performance evaluation simulation that the memory conflict is sufficiently small compared with the number of multiple read memory and approaches a constant with the increase of the number of processorsn.The hardware complexity is relatively large. The physical memory isntimes compared with the logical address space and the number of memory control circuits isn2. There is one connection between the memory control circuit and the connection network. By specifying the area of applications and simplifying the connection configuration, the hardware complexity can be reduced.

ISSN:0882-1666    

DOI:10.1002/scj.4690171110

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1986

数据来源: WILEY