摘要:

AbstractThis paper proposed a new approach to create a very high performance real‐time operating system (OS) using VLSI technology. In this method, a quick and steady response can be guaranteed by implementing basic operations of a real‐time OS as a peripheral chip (Silicon TRON) to be connected to general purpose microprocessors. To confirm the effectiveness of this method, most basic system calls of μITRON have been designed using an HDL. Synthesis results using a 0.8 μm CMOS technology show that the most important part of the system calls can be realized as a VLSI chip. According to the evaluation results based on an FPGA implementation, the hardware portion of these functionalities can be executed within 250 ns and task scheduling can be performed with 750 ns simultaneously, both of which are approximately 6 to 50 times faster than software implementation. Accordingly, very high performance real‐time systems can be created by the proposed

ISSN:0882-1666    

DOI:10.1002/scj.4690270601

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

年代:1996

数据来源: WILEY

摘要:

AbstractLetkandnbe integers with 1 ≤k≤n; F(k, n) is the worst‐case relative error generated in approximating the size of a finite system ofnsets when the sizes of the intersections of all subsystems of at mostksubsets are given. Linial et al. proposed a strategy to estimateF(k, n) and suggested that the strategy is applicable for the problem of counting the number of truth assignments for a DNF formula and the problem of calculating the permanent of a 0/1 matrix, both of which belong to the class of #P‐complete problems. Although the time complexity increases askincreases,F(k, n) decreases their strategy.This paper gives elementary formulas that describe upper and lower bounds onF(k, n) for anykandn.The upper bound is better than the previous one when 2 ≤n ‐ k ≤ n/(8/logen). Furthermore,F(k, n) = 1 + ⊖(nn‐k‐1/2n) is defined for anykandnsuch thatn ‐ k

ISSN:0882-1666    

DOI:10.1002/scj.4690270602

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

年代:1996

数据来源: WILEY

摘要:

AbstractA high‐speed one‐to‐all broadcasting algorithm is proposed whose performance does not deteriorate much when the number of processors is increased in a massively parallel computer. For the network topology, 3D torus networks are considered. Two methods are discussed for a system which broadcasts by repeating one‐to‐one communications. One uses paths having a smaller maximum transfer number to reduce the number of transfers, and the other presets the hardware to reduce the overhead of individual one‐to‐one communications. These methods are evaluated using a double loop model which consists of an inner loop for local processing and an outer loop for global communications. When these methods are used, the scalability increases and for a 32K processor system a 4.2 times speedup in program execution ca

ISSN:0882-1666    

DOI:10.1002/scj.4690270603

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

年代:1996

数据来源: WILEY

摘要:

AbstractThe Knuth‐Bendix completion procedure results in one of the following, when the reduction ordering and the set of equations are given: (1) the procedure succeeds by generating a complete term‐rewriting system; (2) the procedure fails by not giving the orientation to an equation by the reduction ordering; and (3) the procedure diverges without being terminated. The success or failure of the completion procedure depends greatly on the reduction ordering.This paper proposes a completion procedure with multiple reduction orderings to reduce the burden of the user in determining the reduction ordering and to prevent the procedure from diverging due to the inadequate reduction ordering. To improve the efficiency, the data called node are used, based on the data structure of ATMS, which is an architecture proposed in the artificial intelligence. The parallel execution of the ordinary completion procedure is simulated under each reduction ordering.The property of ATMS to handle the multiple context is utilized, and the duplication of the inference is avoided by sharing the result of inference among the reduction orderi

ISSN:0882-1666    

DOI:10.1002/scj.4690270604

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

年代:1996

数据来源: WILEY

摘要:

AbstractIn solving combinatorial optimization problems by Hopfield neural networks, mappings of the problems to the networks are not made so carefully. Although many mappings of, for example, the traveling salesman problems (TSP) have been proposed, their theoretical comparisons are not yet made.In this paper, taking two typical mappings of TSP as examples, their theoretical comparisons are made to prove the superiority of one over the other by the asymptotical stability and unstability theory of the solutions shown by Matsuda [8, 9]. This theoretical comparison method could be applicable to mappings of many other combinatorial optimization problems.

ISSN:0882-1666    

DOI:10.1002/scj.4690270605

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

年代:1996

数据来源: WILEY

摘要:

AbstractMultidimensional data structures have been proposed for management of spatial data including points, lines, and regions. Concomitantly, more research on temporal databases as a way to handle temporal information is needed. Although the management of spatiotemporal data becomes increasingly important in geographic information systems and computer‐aided design, these data structures cannot manage spatiotemporal data efficiently. In this paper, the MP‐tree (multidimensional persistent tree) is proposed for handling multidimensional data with insertion/deletion version without the loss of efficiency of a spatial search. The MP‐tree is developed by extending conventional spatial data structure using techniques of Persistent Search Tree. The advantages and disadvantages of conventional methods with respect to both search and memory efficiency are discussed. Finally, using computer simulations, the MP‐tree is shown to have better performances for both range search and spatiotemporal

ISSN:0882-1666    

DOI:10.1002/scj.4690270606

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

年代:1996

数据来源: WILEY

摘要:

AbstractTo reconstruct the shape of an object from its image, the conventional photometric stereo method requires a preprocessing (e.g., region segmentation based on gray levels) unless the reflectance of its surface is uniform and known; and the method is applicable only to a part of the surface illuminated by more than three light sources.This paper proposes a method based on the photometric stereo method, but with the newly introduced restriction conditions so that the method can be applied without preprocessing to an object with surface texture including regions illuminated by fewer than three light sources. The method has been applied successfully to two spherical objects: the mean square error in the reconstruction of an object where surface texture is 0.01723, and that without texture is 0.002063.

ISSN:0882-1666    

DOI:10.1002/scj.4690270607

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

年代:1996

数据来源: WILEY

摘要:

AbstractThis paper describes a mathematical model of dust particles having complex shapes, and an algorithm to identify them, aiming mainly at categorizing types of dust on an LSI wafer surface. Fractal dimension is used to represent the dust features. A conventional fractal dimension applied to specimens as a whole, however, does not sufficiently represent the shapes of dust in each category of the model.This paper introduces a local fractal dimension into a global fractal dimension so that the feature of a mathematical model can be represented. Also proposed is a method based on Mahalanobis' distance using a fractal characteristic valuable to categorize the data. The proposed method has been tested successively by using real data.

ISSN:0882-1666    

DOI:10.1002/scj.4690270608

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

年代:1996

数据来源: WILEY

摘要:

AbstractThis paper discusses a method for solving an LSI module placement problem using the Kohonen network. First, it is clarified how the neighborhood relations affect the solution called feature map. Specifically, each synapse weight vector is located at the gravitational center of the neighboring synapse weight vectors. Then, it is shown how to set the neighborhood relations to locate the synapse weight vectors at the lattice points, which is necessary in solving the placement problem. Finally, it is shown by computer simulations that performance of the modified Kohonen network is between those of the simulated annealing and the Min‐cut method

ISSN:0882-1666    

DOI:10.1002/scj.4690270609

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

年代:1996

数据来源: WILEY