Kazutoshi KOBAYASHI Masanao YAMAOKA Yukifumi KOBAYASHI Hidetoshi ONODERA Keikichi TAMARU
We propose a functional memory for addition (FMA), which is a memory-merged logic LSI. It is a memory as well as a SIMD parallel processor. To minimize the area, a precessing element (PE) consists of several DRAM words and a bit-serial ALU. The ALU has a functionality of addition bit by bit. This paper describes two FMA experimental LSIs. One is for general purpose, and the other is for full search block matching of image compression. We estimate that a 0.18 µm process realizes 57,000 PEs in a 50 mm2 die, achieving 205 GOPS under 1.36 W power.
Seunghwan LEE Masanori HARIYAMA Michitaka KAMEYAMA
In designing a field-programmable gate array (FPGA)-based processor for motion stereo, a parallel memory system and a simple interconnection network for parallel data transfer are essential for parallel image processing. This paper, firstly, presents an FPGA-oriented hierarchical memory system. To reduce the bandwidth requirement between an on-chip memory in an FPGA and external memories, we propose an efficient scheduling: Once pixels are transferred to the on-chip memory, operations associated with the data are consecutively performed. Secondly, a rectangular memory allocation is proposed which allocates pixels to be accessed in parallel onto different memory modules of the on-chip memory. Consequently, completely parallel access can be achieved. The memory allocation also minimizes the required capacity of the on-chip memory and thus is suitable for FPGA-based implementation. Finally, a functional unit allocation is proposed to minimize the complexity between memory modules and functional units. An experimental result shows that the performance of the processor becomes 96 times higher than that of a 400 MHz Pentium II.
The mean reflection and transmission coefficients of electromagnetic waves incident onto a two-dimensional slightly random dielectric surface are investigated by means of the stochastic functional approach. We discuss the shift of Brewster's scattering angle using the Wiener kernels and numerical calculations. It is also shown that the phase shift at the reflection into Brewster's angle for a flat surface does not depend on the rms height of the surface, but does on the correlation length of the surface.
Seung-Hyub JEON Min-Hui LIM Chuck YOO
The execution model of mobile code inherits from traditional remote execution model such as telnet that needs two conditions. First, the proper program must exist in advance in the remote system. Second, there should be a process in the remote system waiting for requests. Therefore mobile code also bears the same conditions in order to be executed in a remote system. But these conditions constrain an important aspect of mobile code, which is the dynamic extension of system functionality. In this paper we propose a new approach, named Function Message that enables remote execution without these two conditions. Therefore, Function Message makes it easy and natural for mobile codes to extend system functionality dynamically. This paper describes the design of Function Message and implementation on Linux. We measure the overhead of Function Message and verify its usefulness with experimental results. On the ATM network, Function Message can be about five times faster than the traditional remote execution model based on exec().
The present paper modifies the algorithm to estimate harmful event frequencies and examines the definition of modes of operation in IEC 61508. As far as the continuous mode concerns, the calculated results coincide with those obtained based on the standard. However, for the intermediate region of medium demand frequencies and/or medium demand durations, the standard gives much higher harmful event frequencies than the real values. In order to avoid this difficulty, a new definition of modes of operation and a shortcut method for allocation of SILs are presented.
Takaomi SHIGEHARA Hiroshi MIZOGUCHI Taketoshi MISHIMA Taksu CHEON
We propose a new method to construct a four parameter family of quantum-mechanical point interactions in one dimension, which is known as all possible self-adjoint extensions of the symmetric operator T=-Δ C0(R \{0}). It is achieved in the small distance limit of equally spaced three neighboring Dirac's δ potentials. The strength for each δ is appropriately renormalized according to the distance and it diverges, in general, in the small distance limit. The validity of our method is ensured by numerical calculations. In general cases except for usual δ, the wave function discontinuity appears around the interaction and one can observe such a tendency even at a finite distance level.
Shared buffer ATM switches have been attractive since they can achieve a superior performance in terms of cell loss ratio and throughput with a relatively small buffer size. Shared multi-buffer structures have also been considered by several researchers to enhance the access speed of the cell memory for a large switch. High quality services, however, cannot be provided without reliable operation at each module comprising the ATM switches. In this paper, we present a novel on-line error monitoring technique for shared-buffer ATM switches. The technique detects almost all of the functional errors that could occur in the ATM switches. Moreover, it can detect errors with small hardware overhead and negligible time overhead. An early detection of functional errors in ATM switches could not only reduce the wasted bandwidth due to the transmission of erroneous cells, but greatly enhance the recovery time.
Hiroyuki MICHINISHI Tokumi YOKOHIRA Takuji OKAMOTO Tomoo INOUE Hideo FUJIWARA
The programming circuit of SRAM-based FPGAs consists of two shift registers, a control circuit and a configuration memory (SRAM) cell array. Because the configuration memory cell array can be easily tested by conventional test methods for RAMs, we focus on testing for the shift registers. We first derive test procedures for the shift registers, which can be done by using only the faculties of the programming circuit, without using additional hardware. Next, we show the validness of the test procedures. Finally, we show an application of the test procedures to test Xilinx XC4025.
Kazutoshi KOBAYASHI Kazuhiko TERADA Hidetoshi ONODERA Keikichi TAMARU
We propose a real-time low-rate video compression algorithm using fixed-rate multi-stage hierarchical vector quantization. Vector quantization is suitable for mobile computing, since it demands small computation on decoding. The proposed algorithm enables transmission of 10 QCIF frames per second over a low-rate 29.2 kbps mobile channel. A frame is hierarchically divided by sub-blocks. A frame of images is compressed in a fixed rate at any video activity. For active frames, large sub-blocks for low resolution are mainly transmitted. For inactive frames, smaller sub-blocks for high resolution can be transmitted successively after a motion-compensated frame. We develop a compression system which consists of a host computer and a memory-based processor for the nearest neighbor search on VQ. Our algorithm guarantees real-time decoding on a poor CPU.
Shigeru YAMASHITA Hiroshi SAWADA Akira NAGOYA
This paper presents a new efficient method for finding an "optimal" bi-decomposition form of a logic function. A bi-decomposition form of a logic function is the form: f(X) = α(g1(X1), g2(X2)). We call a bi-decomposition form optimal when the total number of variables in X1 and X2 is the smallest among all bi-decomposition forms of f. This meaning of optimal is adequate especially for the synthesis of LUT (Look-Up Table) networks where the number of function inputs is important for the implementation. In our method, we consider only two bi-decomposition forms; (g1 g2) and (g1 g2). We can easily find all the other types of bi-decomposition forms from the above two decomposition forms. Our method efficiently finds one of the existing optimal bi-decomposition forms based on a branch-and-bound algorithm. Moreover, our method can also decompose incompletely specified functions. Experimental results show that we can construct better networks by using optimal bi-decompositions than by using conventional decompositions.
Takaomi SHIGEHARA Hiroshi MIZOGUCHI Taketoshi MISHIMA Taksu CHEON
In this paper, we show that two-dimensional billiards with point interactions inside exhibit a chaotic nature in the microscopic world, although their classical counterpart is non-chaotic. After deriving the transition matrix of the system by using the self-adjoint extension theory of functional analysis, we deduce the general condition for the appearance of chaos. The prediction is confirmed by numerically examining the statistical properties of energy spectrum of rectangular billiards with multiple point interactions inside. The dependence of the level statistics on the strength as well as the number of the scatterers is displayed.
In this paper, we propose a feature selection method to extract functional structures embedded in multidimensional data. In our approach, we do not approximate functional structures directly. Instead, we focus on the seemingly trivial property that functional structures are geometrically thin in an informative subspace. Using this property, we can exclude irrelevant features to describe functional structures. As a result, we can use conventional identification methods, which use only informative features, to accurately identify functional structures. In this paper, we define Geometrical Thickness (GT) in the Cartesian System Model (CSM), a mathematical model that can manipulate symbolic data. Additionally, we define Total Geometrical Thickness (TGT) which expresses geometrical structures in data. Using TGT, we investigate a new feature selection method and show its capabilities by applying it to two sets of artificial and one set of real data.
This paper deals with an orthogonal functional expansion of a non-linear stochastic functional of a stationary binary sequence taking 1 with unequal probability. Several mathematical formulas, such as multivariate orthogonal polynomials, recurrence formula and generating function, are given in explicit form. A formula of an orthogonal functional expansion for a stochastic functional is presented; the completeness of expansion is discussed in Appendix.
The present paper gives a new formulation for rough surface scattering in terms of a stochastic integral equation which can be dealt with by means of stochastic functional approach. The random surface is assumed to be infinite and a homogeneous Gaussian random process. The random wave field is represented in the stochastic Floquet form due to the homogeneity of the surface, and in the non-Rayleigh form consisting of both upward and downward going scattered waves, as well as in the extended Voronovich form based on the consideration of the level-shift invariance. The stochastic integral equations of the first and the second kind are derived for the unknown surface source function which is a functional of the derivative or the increment of the surface profile function. It is also shown that the inhomogeneous term of the stochastic integral equation of the second kind automatically gives the solution of the Kirchhoff approximation for infinite surface.
Hiroshi SAWADA Takayuki SUYAMA Akira NAGOYA
This paper presents a logic synthesis method for look-up table (LUT) based field programmable gate arrays (FPGAs). We determine functions to be mapped to LUTs by functional decomposition for each of single-output functions. To share LUTs among several functions, we use a new Boolean resubstitution technique. Resubstitution is used to determine whether an existing function is useful to realize another function; thus, we can share common functions among two or more functions. The Boolean resubstitution proposed in this paper is customized for an LUT network synthesis because it is based on support minimization for an incompletely specified function. Experimental results show that our synthesis method produces a small size circuit in a practical amount of time.
Adel CHERIF Masato SUZUKI Takuya KATAYAMA
We present a novel replication technique for parallel applications where instances of the replicated application are active on different group of processors called replicas. The replication technique is based on the FTAG (Fault Tolerant Attribute Grammar) computation model. FTAG is a functional and attribute based model. The developed replication technique implements "active parallel replication," that is, all replicas are active and compute concurrently a different piece of the application parallel code. In our model replicas cooperate not only to detect and mask failures but also to perform parallel computation. The replication mechanisms are supported by FTAG run time system and are fully application-transparent. Different novel mechanisms for checkpointing and recovery are developed. In our model during rollback recovery only that part of the computation that was detected faulty is discarded. The replication technique takes full advantage of parallel computing to reduce overall computation time.
New functional surface tunnel transistors (STTs) with multiple interband-tunnel-junctions in a symmetric source-to-drain structure are proposed to reduce the number of fabrication steps and to increase functionality. These devices have p+/n+ interband tunnel junctions in series between a p+ source and a p+ drain through n+ channels. We successfully fabricated GaAs-based multiple-junction STTs (MJ-STTs) using molecular-beam epitaxy regrowth. This fabrication method eliminates the need for two of the photo-masks in the conventional process for asymmetric planar STTs. In the preliminary experiments using multiple-junction p+/n+ diodes, we found that the peak-voltage increment in negative-differential-resistance (NDR) characteristics due to the reverse-biased tunnel junction in negligible, while the first-peak voltage is roughly proportional to the number of forward-biased tunnel junctions. Moreover, the number of NDR characteristics are completely determined by the number of tunnel junctions. The fabricated STTs with multiple junctions, up to eight junctions, exhibited clear transistor operation with multiple NDR characteristics, which were symmetric with the drain bias. These results indicate that any number of gate-controlled NDR characteristics can be realized in MJ-STTs by using an appropriate number of tunnel junctions in series. In addition, as an example of a functional circuit using MJ-STTs, we implemented a tri-stable circuit with a four-junction STT and a load resistor connected in series. The tri-stable operation was confirmed by applying a combination of a reset pulse and a set pulse for each stable point.
This paper deals with an orthogonal functional expansion of a non-linear stochastic functional of a stationary binary sequence taking 1 with equal probability. Several mathematical formulas, such as multi-variate orthogonal polynomials, recurrence formula and generating function, are given in explicit form. A simple example of orthogonal functional expansion and stationary random seqence generated by the stationary binary sequence are discussed.
Hitoshi IMAGAWA Yasumasa IWASE Etsuo MASUDA
In the proposed architecture, switching system hardware resources are allocated at the equipment level rather than at the component level of LSI chips. Equipment using these resources can thus be shared between independent systems. The efficiency of system development is improved by using structural elements called functional blocks (FBs). The hardware in each FB consists of a shared part (amicroprocessor, its peripheral circuitry, and memory) and a dedicated part that implements the specific functions of the FB. Firmware loaded into the microprocessor consists of a shared part and a dedicated part that corresponds to the hardware parts. Each FB also has its own built-in autonomous testing function to test the reliability of that FB and has its own identification function. By combining these FBs, this approach can flexibly cope with various switching system configurations for plain old telephone service (POTS), integrated services digital network (ISDN), and broad-band ISDN (B-ISDN). Tests using several types of FBs showed that the shared hardware and firmware parts of an FB can be shared between blocks. An architecture based on FBs results in a platform that can handle the hardware for various systems, making it easy to construct new switching systems.
In logic programming or functional programming languages, data objects, such as terms and lists, are immutable. In a basic implementation of such language, updating one element of an aggregate (contiguous data structure, such as an array) involves making a new copy of the whole aggregate. However, such copying can be expensive, and can be avoided by using a destructive update. We introduce the concept of a wrapper which enables destructive operation on an immutable object. Based on this concept, we designed the reversible functor as a solution to the aggregate update problem. We implemented the reversible functor in the existing SB-Prolog system and carried out several benchmarks. These benchmark results show its effectiveness. When using a large functor and updating it many times, the performance is improved dramatically by implementing the reversible functor. It incurs some overhead at runtime, but the amount is small and acceptable.