摘要:

AbstractThe authors have proposed a high‐level parallel processing system representing the data‐drive principle (including history‐sensitive processing by diagrammatical language) and have been investigating its realization. Realization of high‐level processing by the data‐driven principle requires a load and function distribution scheme to secure the smooth data flow corresponding to the input stream into the system. Together with the results of experiment, this paper describes a systematic control scheme for load and function distribution of the data‐driven execution function through the construction of clusters adapted to the hierarchical diagrammatical program structure. In other words, the proposed system realizes the data‐driven execution functions of the hierarchical system by an iterative structure composed of fundamental functions, namely input‐output, function processing, history‐sensitive processing and firing control. This paper first describes the load and function distribution scheme for the fundamental function in the data‐driven execution control. Then, using an experimental system with common‐bus multiprocessor structure, it is shown that the proposed system is useful in realizing high‐level parallel processing. Lastly, based on the geometrical connection structure of the diagrammatical program, a semiquantitative guideline is presented for the distributed assignment of fundamental functions in the hierarc

ISSN:0882-1666    

DOI:10.1002/scj.4690160201

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

年代:1985

数据来源: WILEY

摘要:

AbstractThis paper describes practical optimization/approximation algorithms for scheduling a set of partially ordered computational tasks with different processing times onto a multiprocessor system so that the schedule length is minimized. Since this problem belongs to the class of “strong” NP hard problems, we must eliminate the possibility of constructing not only pseudopolynomial time optimization algorithms, but also fully polynomial time approximation schemes unless P = NP.This paper proposes a heuristic algorithm CP/MISF (Critical Path/Most Immediate Successors First) and an optimization/approximation algorithm DF/IHS (Depth First/ Implicit Heuristic Search). DF/IHS is an excellent scheduling method which can reduce markedly the space complexity and average computation time by combining the branch‐and‐bound method with CP/MISF; it allows us to solve very large‐scale problems with a few hund

ISSN:0882-1666    

DOI:10.1002/scj.4690160202

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

年代:1985

数据来源: WILEY

摘要:

AbstractUntil now, discussions have been made for several models of deterministic parallel computation, concerning such items as the trade‐off between the time and the number of processors and the relations among those models. However, few discussions have been made for the nondeterministic case. This paper discusses the nondeterministic case, using ATM (alternating Turing machine) and NTM (nondeterministic Turing machine). The main results are as follows. (1) WhenR(n)=0(S(n)), andR(n)=ω(log(S(n)),S(n) = ω (n), NRS,(Ro(1)(n) andS0(1)(n)) ATBS(R0(1)(n),S0(1)(n),R0(1)(n))NRSR0(1)(n)),S0(1)(n),S0(1)(n)). (2) S(n) = 0(R(n)) andS(n)=ω (log(R(n)),R(n) = ω(n), where NRSR0(1)(n),S0(1)(n))=ATBSR0(1)(n)),S0(1)(n)), where NRS(R(n),S(n) (ATBS )T(n),B(n), S(n)is the class of languages accepted by(R(n),S(n))reversal‐and‐space bounded NTM[(T(n),B(n)]time‐leaf‐and‐spa

ISSN:0882-1666    

DOI:10.1002/scj.4690160203

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

年代:1985

数据来源: WILEY

摘要:

AbstractAs models to describe concurrent systems, Petri net, shuffle stack automaton (SSA), flow expression, event expression, and shuffle grammar have been proposed. SSA is an automaton which is obtained by adding to the finite automaton a stack with shuffle function. Its descriptive power has already been discussed. This paper discusses the real‐time shuffle stack automaton (RSSA, which is an SSA without λ‐transition in regard to the input), which is a subclass of SSA. It is shown that RSSA has the same descriptive power, independently of the accepting mode (empty‐stack acceptance or final‐state acceptance), and of whether or not a terminating symbol is provided at the end of the input string. It is also shown that the descriptive power of RSSA is incomparable to that of the push‐down automaton, but is properly contained in that of the linear bounded automaton. If a language is bounded and if the set obtained by applying Parikh mapping to that language is semi‐linear, the language is accepted by RSSA. Another property of the language accepted by RSSA is that if it is a bounded context‐free language, it is ac

ISSN:0882-1666    

DOI:10.1002/scj.4690160204

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

年代:1985

数据来源: WILEY

摘要:

AbstractThe CSMA/CD method, one of the communication schemes for bus‐type LANs, has problems with respect to transmission capability and its function. This paper presents an access control method named multichannel CSMA/CD for local area networks. In this method, CSMA/CD combined with a new load distribution mechanism and channel selection function is extended to multichannel organization. This method aims at LANs having high performance and multiple functions. As a result of performance evaluation, multichannel CSMA/CD is shown to be superior to the original CSMA/CD with respect to (1) total transmission capacity, (2) throughput‐delay characteristic performance, (3) channel stability and (4) adaptability to various kinds of user demands in netwo

ISSN:0882-1666    

DOI:10.1002/scj.4690160205

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

年代:1985

数据来源: WILEY

摘要:

AbstractThis paper describes some issues of parallel list processing under data flow control. Also a new type of list‐processing oriented data flow machine is presented which achieves pipelined processing among activated functions. Performance evaluation through software simulation gave the following conclusions.(1) This machine can utilize a high degree of parallelism even for simple programs due to the partial function‐body execution and lenient cons effects.(2) Parallel processing overhead does not affect the processing time.(3) Memory contention is reduced by dividing the structure memory into many banks and by uniformly distributing cons operations in each b

ISSN:0882-1666    

DOI:10.1002/scj.4690160206

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

年代:1985

数据来源: WILEY

摘要:

AbstractThis paper discusses the properties and the algorithms of the fusion operations, which are one of the fundamental techniques of binary image processing. First, a theoretical discussion is made for infinitely spread images, deriving several properties for the fusion operations. Those properties indicate the equivalence among the fusion operations and their iterations and combinations. Since the actual input images are finite, those properties are not satisfied by a simple algorithm due to the effect of the picture frame. This paper presents algorithms not affected by the picture frame for the general‐purpose sequential computers and for the dedicated parallel‐processing hardwares. Those algorithms perform the fusion operation by executing the first operation in the fusion (that is, the expansion or the contraction) together with the distance transformation, and by performing the second operation using the distance information obtained in the first. The proposed algorithms have the feature that most of the properties for infinite images also apply to images of finite size. With this feature, the proposed algorithms are shown to be suited to parallel processing with a small number of process

ISSN:0882-1666    

DOI:10.1002/scj.4690160207

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

年代:1985

数据来源: WILEY

摘要:

AbstractThe X‐ray computed tomography system has found widespread use worldwide in recent years. It is still requested that the system should provide further diagnostic information by providing CT images with higher quality. For this purpose, it is necessary to improve the high‐contrast spatial resolution and the low‐contrast density resolution. It is necessary also to establish a reduction method for various kinds of artifacts which are major causes of image deterioration. This paper examines quantitatively the spatial resolution and artifact, among various factors determining the CT image quality, and discusses their relation to the measured data sampling rate using computer simulation. As a result, it is shown that when other reconstruction parameters are kept constant in the fan‐beam CT system, the spatial resolution is determined largely by the projection data sampling interval rather than the angle sampling interval. The mechanism of artifact generation due to an insufficient angle sampling interval is examined. It is shown that to suppress this kind of artifact below a certain value, a certain condition must be satisfied by the measurement area, angle sampling interval, and projection data sampling interval. It is shown also that the artifact due to the projection sampling interval is proportional to the spatial frequency components of the object above the Nyquist frequency of the projecti

ISSN:0882-1666    

DOI:10.1002/scj.4690160208

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

年代:1985

数据来源: WILEY

摘要:

AbstractA recent tendency in the study of texture is the analysis based on mathematical models rather than the analysis of intuitively clear geometrical features. This type of study is advantageous in that a systematic and theoretical viewpoint can be provided to various kinds of related texture image processings. This paper considers the Gaussian‐Markov random field as a mathematical model for the texture image, and applications of the theory are discussed for texture classification and boundary extraction of texture regions. The determination of parameters for the Markov model is discussed first. Then the distance between textures is defined using the model parameters and a method of texture classification is proposed. The extraction of the boundary between texture regions is formulated as a testing of the parameters of the Markov model, and a method of texture region partition is proposed using the statistical testing variable as the discrimination function for the texture boundary. A classification experiment was performed for texture images with 13 categories, each containing 23 patterns. A 100% rate of classification was obtained, indicating the effectiveness of the proposed classification method. The region partition experiment was performed for the patched texture image. The result of partition was satisfactory, indicating the effectiveness of the proposed boundary extraction metho

ISSN:0882-1666    

DOI:10.1002/scj.4690160209

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

年代:1985

数据来源: WILEY

摘要:

AbstractThis paper describes a method to determine the 3‐D position and orientation of a plane‐like object. The system first extracts edges of the plane‐like object and its shadow cast on a working table by an ideal point light source. Utilizing the shadow informaton effectively, it estimates the 3‐D positions of several boundary points, from which the position and orientation of the plane‐like object are then determined. An application of this method, measurement of the 3‐D position, and orientation of a printed circuit board, is presented. The errors in measuring the position and orientation are about 1% of the size of sight and 4 degrees, respectively. The result is sufficient for a robot hand to manipulate the printed ci

ISSN:0882-1666    

DOI:10.1002/scj.4690160210

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

年代:1985

数据来源: WILEY