Multiplication-accumulation is the basic computation required for image filtering operations. For real-time image filtering, very high throughput computation is essential. This work proposes a hardware algorithm for an application-specific VLSI architecture which realizes an area-efficient high throughput multiplier-accumulator. The proposed algorithm utilizes a priori knowledge of filter mask coefficients and optimizes number of basic hardware components (e.g., full adders, pipeline latches, etc.). This results in the minimum area VLSI architecture under certain input/output constraints.

Space-time tradeoff is a very fundamental issue to design a fault-tolerant real-time (called responsive) system. Routing a message in large computer networks is efficient when each node knows the full topology of the whole network. However, in the hierarchical routing schemes, no node knows the full topology. In this paper, a tradeoff between an optimality of path length (message delay: time) and the amount of topology information (routing table size: space) in each node is presented. The schemes to be analyzed include K-scheme (by Kamoun and Kleinrock), G-scheme (by Garcia and Shacham), and I-scheme (by authors). The analysis is performed by simulation experiments. The results show that, with respect to average path length, I-scheme is superior to both K-scheme and G-scheme, and that K-scheme is better than G-scheme. Additionally, an average path length in I-scheme is about 20% longer than the optimal path length. On the other hand, for the routing table size, three schemes are ranked in reverse direction. However, with respect to the order of size of routing table, the schemes have the same complexity O (log n) where n is the number of nodes in a network.

For each two positive integers r, s, let [1DCM(r)-Time(ns)] ([1NCM(r)-Time(ns)]) and [1DCM(r)-Space(ns)] ([1NCM(r)-Space(ns)]) be the classes of languages accepted in time ns and in space ns, respectively, by one-way deterministic (nondeterministic) r-counter machines. We show that for each X{D, N}, [1XCM(r)-Time(ns)][1XCM(r+1)-Time(ns)] and [1XCM(r)-Space(ns)][1XCM(r+1)-Space(ns)]. We also investigate the relationships between one-way multicounter machines and cooperating systems of one-way finite automata. In particular, it is shown that one-way (one-) counter machines and cooperating systems of two one-way finite automata are equivalent in accepting power.

A fast and efficient heuristic hierarchical global router for Sea-of-Gates(SOG) with embedded macro-blocks is described. The key point in the method is carry out a new optimal domain decomposition scheduling at every hierarchical level. This scheduling is intended to avoid macro-block-through wirings and to reduce wiring congestion near macro-blocks which may occur at lower levels. The new global router yielded superior results compared with previous hierarchical routers and a non-hierarchical maze router by evaluating with several actual SOG circuits including a 300K gate master chip and benchmark data supplied from MCNC. Overflows were reduced to one-half or one-quarter for macro-block embedded data compared with previous hierarchical routers. Concerning the running time, the router remarkably outperformed the non-hierarchical maze router, which took more than 390 times longer time for the tested large data.

A modern architect can not design high performance computer architecture without thinking all factors of performance from hardware level (logic/layout design) to system level (application programs, operating systems, and compilers). For computer architecture design, there are few practical CAD tools, which support design activities of the architect. In this paper, we propose a CAD tool, called COACH, for computer architecture design. COACH supports architecture design from hardware level to system level. To make a high-performance general purpose computer system, the architect evaluates system performance as well as hardware level performance. To evaluate hardware level performance accurately, logic/layout synthesis tools and simulator are used for evaluation. Logic/layout synthesis tools translate the architecture design into logic circuits and layout pattern and simulator is used to get accurate information on hardware level performance which consists of clock frequency, the number of transistors, power consumption, and so on. To evaluate system level performance, a compiler generator is introducd. The compiler generator generates a compiler of a programming language from the desripition of architecture design. The designed architecture is simulated in the behavior level with programs compiled by the compiler, and the architect can get information on system level performance which consists of program execution steps, etc. From both hardware level performance and system level performance, the architect can evaluate and revise his/her architecture, considering the architecture from hardware level to system level. In this paper, we propose a new design methodology which uses () logic/layout synthesis tools and simulators as tools for architecture design and () a compiler generator for system level evaluation. COACH, a CAD system based on the methodology, is discussed and a prototype of COACH is implemented. Using the design methodology, two processors are designed. The result of the designs shows that the proposed design methodology are effective in architecture design.

Fiber-optic passive double star (PDS) network is described as an access network for microcellular radio communication systems. The intrinsic characteristics of the PDS network, reduction in the optical fiber count and flexible access capability, are examined. A unit cell structure is introduced which enables the PDS network to be effectively incorporated into the access portion of microcellular radio communication systems. The reduced total fiber length in the unit cell structure based on the PDS network is discussed in comparison with the conventional architecture. Calculations show that there is an optimum splitting ratio that minimizes the total fiber length. When the microcell radius and service area radius are 100m and 10km, respectively, the total fiber length of the PDS network is reduced to only about 9% of that of the conventional single star (SS) network for a splitting ratio of 34. Resource sharing and handover between microcells in a unit cell are performed by using the dynamic channel allocation function of the PDS system. Substantial performance improvement for loaded traffic can be obtained by resource sharing. When the splitting ratio is 32, the available traffic of a base station (BS) increases from 0.9 [erl/BS] to 3.4 [erl/BS] by adopting dynamic channel allocation for the lost call probability of 0.01.

High speed multiplication of two n-bit numbers plays an important role in many digital signal processing applications. Traditional array and Wallace multipliers are the most widely used multipliers implemented in VLSI. The area and time (=latency) of these two multipliers depend on operand bit-size, n. For a particular bit-size, they occupy fixed positions in some graph which has area and time along the x and y-axes respectively. However, many applications require a multiplier which has an 'intermediate' area-time characteristics with the above two traditional multipliers occupying two extreme ends of above mentioned area-time curve. In this paper, we propose such an intermediate multiplier which trades off area for time. It has higher speed (i.e., less latendy) but more area than a traditional array multiplier. Whereas when compared with a traditional Wallace multiplier, it has lower speed and area. The attractive point of our multiplier is that, it resembles an array multiplier in terms of regularity in placement and inter-connection of unit computation cells. And its interesting feature is that, in contrast to a traditional array multiplier, it computes by introducing multiple computation wave fronts among its computation cells. In this paper, we investigate on the area-time complexity of our proposed multiplier and discuss on its characteristics while comparing with some contemporary multiplers in terms of latency, area and wiring complexity.

Since semiconductor memory chip has been growing rapidly in its capacity, memory testing has become a crucial problem in RAMs. This paper proposes a new RAM test algorithm, called generalized marching test (GMT), which detects static and dynamic pattern sensitive faults (PSF) in RAM chips. The memory array with N cells is partitioned into B sets in which every two cells has a cell-distance of at least d. The proposed GMT performs the ordinary marching test in each set and finally detects PSF having cell-distance d. By changing the number of partitions B, the GMT includes the ordinary marching test for B1 and the walking test for BN. This paper demonstrates the practical GMT with B2, capable of detecting PSF, as well as other faults, such as cell stuck-at faults, coupling faults, and decoder faults with a short testing time.

We propose a continuous speech recognition algorithm utilizing island-driven A* search. Conventional left-to-right A* search is probable to lose the optimal solution from a finite stack if some obscurities appear at the start of an input speech. Proposed island-driven A* search proceeds searching forward and backward from the clearest part of an input speech, and thus can avoid to lose the optimal solution from a finite stack.

The recent non von Neumann chip architectures are mainly classified into the AI architecture and the neural architecture. We focus on these two categories, and introduce the representatives each with a brief history. The AI chip architecture is difficult to escape essentially from the von Neumann architecture as far as it is language-oriented. The neural architecture, however, may yield an essentially new computer architecture, when the new device technologies will support it. In particular, the optoelectronics and the quantum electronics will provide a lot of powerful technologies.

This paper proposes a multi-layer cellular network in which a self-organizing method is implemented. The network is developed for the purpose of data clustering and recognition. A multi-layer structure is presented to realize the sophisticated combination of several sub-spaces which are spanned by given input characteristic data. A self-organizing method is useful for evaluating the set of clusters for input data without a supervisor. Thus, using these techniques this network can provide good clustering ability as an example for image/pattern data which have complicated and structured characteristics. In addition to the development of this algorithm, this paper also presents a parallel VLSI architecture for realizing the mechanism with high efficiency. Since the locality can be kept among all processing elements on every layer, the system is easily designed without large global data communication.

A new transfer mode and a switching architecture which can support loss free and no delay jitter service class with shorter switching delay compared with "stop and go queueing scheme" is proposed. This scheme combines ATM scheme with hierarchical STM framing concept.

Current status and critical issues of the material and device technology towards constructing new architecture LSIs based on quantum-mechanical principles are reviewed in an attempt to draw attention of systems workers to the field. Limitations of the present-day LSI architecture are discussed from the viewpoints of material science and device physics. New quantum mechanical phenomena in the quantum structures are reviewed. Then, key material and processing issues for fabrication of desired quantum structures are briefly discussed. Finally, the basic operation principles the quantum devices and possible architectures of quantum LSIs are discussed.

The hierarchies of multihead finite automata over a one-letter alphabet are investigated. Let SeH(k) [NSeH(k) ] denote the class of languages over a one-letter alphabet accepted by deterministic [nondeterministic] sensing two-way k-head finite automata. Let H (k)s[NH(k)s] denote the class of sets of square tapes over a one-letter alphabet accepted by two-dimensional four-way deterministic [nondeterministic] k-head finite automata. Let SeH(k)s[NSeH(k)s] denote the class of sets of square tapes over a one-letter alphabet accepted by two-dimensional four-way sensing deterministic [nondeterministic] k-head finite automata. This paper shows that SeH(k) SeH(k1) and NSeH(k) NSeH(k1) hold for all k3. It is also shown that H(k)s[NH(k)s] H(k1)s[NH (k1)s] and SeH (k)s[NSeH(k)s] SeH(k1)s[NSeH(k1)s] hold for all k1.

The performance of processing elements can be improved by the progress of VLSI circuit technology, while the communication overhead can not be negligible in parallel processing system. This paper presents a unified scheduling that allocates tasks having different task processing times in multiple processing elements. The objective function is formulated to measure communication time between processing elements. By employing constraint conditions, the scheduling efficiently generates an optimal solution using an integer programming so that minimum communication time can be achieved. We also propose a VLSI processor for robotics whose latency is very small. In the VLSI processor, the data transfer between two processing elements can be done very quickly, so that the communication cycle time is greatly reduced.

The main result of this paper is an almost-everywhere hierarchy theorem for nondeterministic space that is as tight as the well-known infinitely-often hierarchy theorems for deterministic and nondeterministic space. In addition, we show that the complexity-theoretic notion of almost-everywhere complex functions is identical to the recursion-theoretic notion of bi-immune sets in the nondeterministic space domain. Finally, we investigate bi-immunity in nondeterministic and alternating time complexity classes and derive a similar hierarchy result for alternating time.

This paper introduces the new application specific architecture RHINE (Reconfigurable Hierarchical Image Neo-multiprocessor Engine) that is a multiprocessor system for moving picture CODEC. The array processor is known to be originally suited for data parallel processing such as image signal processing which requires vast amount of computations and has the identical instruction sequences on data. However, the moving picture CODEC algorithm suffers from the large load imbalance in the processings on multi-processors with the separated sub-images. Some load balancing techniques are indispensable in such applications for the highest speed-up. RHINE gives one of the optimal solutions for such a load balancing due to its feature of the self reconfigurable architecture. RHINE consists of Block Processing Units (BPU) hierarchically, in each of which has a common bus architecture of multiprocessors with a block memory. Processors in a BPU move to the other BPU according to the load imbalance between BPUs by switching the bus connection between BPUs. The advantage of RHINE architecture is demonstrated by showing performance simulations for real moving pictures.

In this letter, we propose an algorithm to estimate the optical flow fields based on a hierarchical structure composed of spatio-temporal image pyramids obtained from repetitive application of the Gaussian filtering and decimation in both the spatial and temporal domain. In our approach, an inter-level motion smoothness constraint between adjacent pyramid levels is introduced to estimate a unique optical flow field. We show that the pyramid structure allows us to employ the multigrid algorithm, which is known to accelerate the convergence rate. The multigrid algorithm provides a scheme for efficient combination of local and global information to estimate the optical flow field. The experimental results reveal that the combination of local and global information yields a fast convergence behavior and accurate motion estimation results.

Formal verification has become an increasing prominent technique towards establishing the correctness of hardware designs. We present a framework to specifying and verifying the design of systolic architectures. Our approach allows users to represent systolic arrays in Z specification language and to justify the design semi-automatically using the verifier. Z is a notation based on typed set theory and enriched by a schema calculus. We describe how a systolic array for matrix-vector multiplication can be specified and justified with respect to its algorithm.

This paper proposes an off-line text-independent writer identification method applicable to Japanese and Korean sentences. It is assumed that the writer of a writing in question exists in a certain group of people and that reference writings written by each person in the group can be used for identification. In the proposed method, relative frequencies of some model patterns are counted on the binary pattern of each writing and are used as the feature to measure the distance between two writings. Based on a modified Mahalanobis' distance for this feature, the person whose reference writing is nearest to the writing in question is judged as the writer. The effectiveness of the proposed method is examined through an experiment using Japanese and Korean writings. Error rates in the experiment were different depending on conditions such as volume of reference writings, dimension of adopted features, and number of people to be identified. In some cases, error rates as low as 0% were observed. Error rates tend to be lower in Korean writings probably because Hangul is composed of a smaller number of letters compared to Kanji and Hiragana in Japanese writing.