The number of DRAMs that have adopted hierarchical word-line architecture has increased as developed DRAM memory capacity has increased to more than 64 Mb. Use of the architecture enhances many kinds of DRAM performances, such as access time and fabrication process margin. However, the architecture does cause some problems. This paper describes some kinds of hierarchical word-line circuitries that have been proposed. It also describes a partial subarray activation scheme that is combined with hierarchical word-line and data-line architectures and discusses their potential and required specifications for future multi-giga bit DRAMs.

A new memory cell arrangement for a gigabit-scale NAND DRAM is proposed. Although the conventional NAND DRAM in which memory cells are connected in series realizes the small die size, it faces a crucial array noise problem in the 1 gigabit generation and beyond because of its inherent noise of the open bitline arrangement. By introducing the new cell arrangement to a NAND DRAM, the folded bitline scheme is realized, resulting in good noise immunity. The basic operation of the proposed folded bitline scheme was successfully verified using the 64 kbit test chip. The die size of the proposed NAND DRAM with the folded bitline scheme (F-NAND DRAM) at the 1 Gbit generation is reduced to 63% of that of the conventional 1 Gbit DRAM with the folded bitline scheme, assuming the bitlines and the wordlines are fabricated with the same pitch. The new 4/4 bitline grouping scheme in which cell data are read out to four neighboring bitlines is also introduced to reduce the bitline-to-bitline coupling noise to half of that of the conventional folded bitline scheme. The array noise of the proposed F-NAND DRAM with the 4/4 bitline grouping scheme at 1 Gbit generation is reduced to 10% of the read-out signal, while that of the conventional NAND DRAM with open bitline scheme is 29%, and that of the conventional DRAM with the folded bitline scheme is 22%.

This paper discusses the largest common similar substructure (in short, LCSS) problem for trees. The problem is, for all pairs of "substructure of A and that of B," to find one of them, denoted by A and B', such that A is most similar to B' and the sum of the number of vertices of A and that of B' is largest. An algorithm for the LCSS problem for unrooted and unordered trees (in short, trees) and that for trees embedded in a plane (in short, Co-trees) are proposed. The time complexity of the algorithm for trees is O (max (ma, mb)2 NaNb) and that for CO-trees is O (mambNaNb), where, ma (mb) and Na (Nb) are the largest degree of a vertex of tree Ta (Tb) and the number of vertices of Ta (Tb), respectively. It is easy to modify the algorithms for enumerating all of the LCSSs for trees and CO-trees. The algorithms can be applied to structure-activity studies in chemistry and various structure comparison problems.

Ordered Binary Decision Diagrams (OBDDs) are graph-based representations of Boolean functions which are widely used because of their good properties. In this paper, we introduce nondeterministic OBDDs (NOBDDs) and their restricted forms, and evaluate their expressive power. In some applications of OBDDs, canonicity, which is one of the good properties of OBDDs, is not necessary. In such cases, we can reduce the required amount of storage by using OBDDs in some non-canonical form. A class of NOBDDs can be used as a non-canonical form of OBDDs. In this paper, we focus on two particular methods which can be regarded as using restricted forms of NOBDDs. Our aim is to show how the size of OBDDs can be reduced in such forms from theoretical point of view. Firstly, we consider a method to solve satisfiability problem of combinational circuits using the structure of circuits as a key to reduce the NOBDD size. We show that the NOBDD size is related to the cutwidth of circuits. Secondly, we analyze methods that use OBDDs to represent Boolean functions as sets of product terms. We show that the class of functions treated feasibly in this representation strictly contains that in OBDDs and contained by that in NOBDDs.

The most crucial factor that degrades a high speed VLSI is the signal propagation delay in a routing tree. It is estimated by the sum of the delay caused by the source-to-sink path length and by the total length. To design a routing tree in which these two are both small and balanced, we propose an algorithm to construct such a spanning tree, based on the idea of constructing a tree combining the minimum-spanning-tree and shortest-path-tree algorithms. This idea is extended to finding a rectilinear Steiner tree. Experiments are presented to illustrate how the source-to-sink path length and total length can be ballanced and small.

This paper presents the beam forming characteristics of an optical waveguide-type phased array antenna. Four linearly arranged array antenna was monolithically fabricated on one LiNbO3 substrate containing variable power dividers (VPDs) and optical phase shifters (OPSs). The amplitude and the phase of each antenna element was controlled by applying DC voltage on each VPD and OPS. Open ends of Ti-indiffused waveguides were used as antenna elements. This antenna was designed to operate at 1.3 µm wavelength band. Experimental results confirm the good beam forming capability of optical phased array antennas.

A large scale simulation for polymer chains in good solvent is performed. The implementation technique for efficient parallel execution, optimization, and load-balancing are discussed on this practical application. Finally, a simple performance model is proposed.

We frequently use a polynomial to approximate a complex function. This study shows a method which determines the optimum coefficients and the number of terms of the polynomial, and the error of the polynomial is estimated.

We describe our implementation of the Hypercube variation of the Multiple Polynomial Quadratic Sieve (HMPQS) integer factorization algorithm on a Parsytec GC computer with 128 processors. HMPQS is a variation on the Quadratic Sieve (QS) algorithm which inspects many quadratic polynomials looking for quadratic residues with small prime factors. The polynomials are organized as the nodes of an n-dimensional cube. We report on the performance of our implementations on factoring several large numbers for the Cunningham Project.

We propose an improved orthogonal frequency division multiplexing (OFDM) signal detector which uses the minimum mean-square error (MMSE) noise feedback equalization (NFE). The input bit stream is trellis-coded to form OFDM signal blocks and the maximal ratio combining (MRC) is adopted at the receiver in order to improve the performance of the detector. As a result, we obtain significantly improved detection performance compared with the conventional OFDM receivers as follows. Using the proposed MMSE-NFE in the receiver, we can obtain the performance gain of about 1.5 dB to 2 dB in symbol energy to noise power spectral density (Es/No) for Doppler frequencies of fd=20 and 100 Hz, respectively, over the receiver with the MMSE linear equalization (LE) alone at symbol error rate (SER) of about 10-3. With MRC and trellis coding, the performance gain of about 11 dB in Es/No for fd=20 and 100 Hz at SER of about 10-3 is obtained.

This paper proposes a new test mode circuit which enables the massively parallel test of DRAMs with a standard LSI tester with little chip area penalty. It is useful to enhance the test throughput that can't be improved by the conventional multi-bit test mode. And a new redundancy circuit that detects and repairs the short circuit failures in the memory cell array is also proposed. It greatly improves the yield of super low power 256 Mbit DRAMs.

In this paper, a new method capable of effectively coding arbitrarity-shaped image regions is presented. The image region is spanned into the 8 8 rectangular block and its intermediate luminances are interpolated. After all liminances in the 8 8 block are obtained from pixels in the region, they are transformed by 8 8 DCT. The proposed extension/interpolation (EL) method is compared with conventional ones, such as SA-DCT, mean stuffing, etc., under three aspects: peak signal-to-noise ratio (PSNR), hardware complexity, and the flexibility for improvement of performance. Simulation results show that the performance of the proposed method is superior to that of the conventional ones. In addition, we introduce an improved version by repetitively performing the EL method.

SCI (Scalable Coherent Interface) is pointerbased coherent directory scheme for massively parallel multiprocessors. Large message latency is one of the problems with SCI because of its linked list structure: the searching latency of messages could grow as a linear order of the number of processors. In this paper, we focus on a hierarchical architecture to propose a new schemeEST(Extending SCI-Tree), which may reduce the message traffic and also take the advantages of the topology property. Simulation results show that the EST scheme is effective in reducing message latency and communication cost when compared with other schemes.

This paper presents intelligent memory, a new memory architecture capable of providing efficient lock-free synchronization. In the intelligent memory, a sequence of operations on a shared object associated with that memory module can be processed without any intervention so that an environment for the synchronization can be provided by executing a critical section itself in that memory module. For this, we present a memory architecture for the intelligent memory having minimal instruction set and develop a progtramming model, called Critical Section Procedure (CSP), which consists of shared data structures and operations on them. Intelligent memory is intended to eliminate waste of processing time such as busy waiting in spin lock and the retry due to process contentions in existing lock-free synchronization schemes. Simulation results show that the intelligent memory provides better throughput compared with the spin lock and the existing lock-free synchronization schemes.

We conducted research and development of Distributed Supercomputing Environment (DSE) based on distributed shared memory model to serve as a cluster computing environment to provide parallel processing facilities. Shared memory model and message passing model are well-known typical models of parallel processing. It is desired that hybrid programming environment will make the best use of the prominent features of both models. Consequently, we add a new message passing mechanism to present DSE, and create a prototype called Hybrid DSE as a hybrid model based cluster computing environment. In this paper, we describe the implementation of a message passing mechanism on DSE and performance evaluation of Hybrid DSE.

In high performance compilers to process pointer-handling programs, precise pointer alias analysis is useful for the compilers to generate efficient object code. It is well known that most compiler techniques such as data flow analysis, dependence analysis, side effect analysis and optimizations are related to the alias problem. However, without data structure information, there is a limit on the precision of the alias analysis. Even though the automatic data structure detection problem is complex, when pointer manipulation satisfies some restrictions, some data structures can be detected automatically by compilers with some knowledge of aliases. In this paper, we propose an automatic data structure detection method for Pascal and Fortran 90. Linear list, tree and dag data structures are detected. Detected data structure information can be used not only for raising the precision of alias analysis but also for some optimizing techniques for pointer handling programs directly.

It is known that in a nonblocking packet switch with input queueing, head-of-line (HOL) blocking affects significantly the maximum throughput of the packet switch. To alleviate the HOL blocking effect, a window policy has been proposed in that each input queue can scan up to a fixed number of packets (called the window size) to select for transmission on the outputs. However, the performance of the window policy has never been precisely characterized. In this paper, we use a closed queueing network model to characterize the performance of the packet switch with window policy. We obtain explicit closed-form formulae for the maximum throughput of the packet switch as a function of the window size. Both balanced and imbalanced traffic patterns are discussed. The formulae can easily determine the effectiveness of the window policy.

Geometrically Uniform (GU) codes have been a center of attention because their symmetric properties along with group algebraic structure provide benefits on their design and perfomance evaluation. We have been following a class of GU codes tha we call Strictly Geometrically Uniform (SGU) codes. Our studies had started from devising a way to get SGU trellis codes from Non-SGU (NSGU) constellations. Essentially, SGU multidimensional constellations were derived from an 1- or 2-dimensional NSGU constellations. Some simple good codes were then found, and the novelty is that they rely on symmetries of permutation of channel symbols. Applying the same method to PSK-type constellations, which is SGU, yielded again good codes, along with results regarding their algebraic structure.

This paper proposes a synthesis method to obtain speed-independent asynchronous circuits directly from signal transition graph (STG) specifications with single cycle signals which can be non-persistent and have free-choice operations. The resulting circuits are implemented with basic gates and asynchronous latches, and operate correctly under finite but unbounded gate delays and the zero wire delay assumptions. The proposed method introduces 5 types of lock relations to implement a non-persistent STG. A non-persistent STG can be implemented if every non-persistent signal to a signal t is super-locked with t. The resulting circuits are optimized by extracting of literals, mapping onto asymmetric C-elements, etc. Experimental results show that the proposed synthesis method outperforms the existing synthesis systems such as SYN and SIS.

A fast rip-up and reroute algorithm for very large scale gate arrays is proposed. The automatic routing program for gate arrays usually consists of an initial routing process and rip-up and rerouting process. The rip-up and rerouting process eliminates the unconnects introduced by the initial routing process. There are two main reasons for leaving some unconnects: routing order dependency and local wire congestion. The existing rip-up and reroute algorithms can efficiently resolve unconnects caused by the routing order dependency. However, they cannot do unconnects caused by the local wire congestion. On the other hand, the proposed algorithm combines a `global' and `local' rip-up and reroute process and efficiently resolve unconnects caused by both of them. The `global' process reduces the local wire congestion by ripping up and rerouting global paths. The `local' process eliminates the unconnects, mainly caused by routing order dependency, by ripping up and rerouting local paths. The effectiveness of our method is demonstrated by our experimental results on industrial sea-of-gates (SOG) circuits and a well-known benchmark circuit.