Jiahong WANG Jie LI Hisao KAMEDA
Parallel Transaction Processing (TP) systems have great potential to serve the ever-increasing demands for high transaction processing rate. This potential, however, may not be reached due to the data contention and the widely-used two-phase locking (2PL) Concurrency Control (CC) method. In this paper, a distributed locking-based CC policy called LWDC (Local Wait-Depth Control) was proposed for dealing with this problem for the shared-nothing parallel TP system. On the basis of the LWDC policy, an algorithm called LWDCk was designed. Using simulation LWDCk was compared with the 2PL and the base-line Distributed Wait-Depth Limited (DWDL) CC methods. Simulation studies show that the new algorithm offers better system performance than those compared.
Yong-Hyeon PYUN Choung-Shik PARK Sang-Bang CHOI
This paper suggests a novel analytical model to predict average issue rate of both in-order and out-of-order issue policies. Most of previous works have employed only simulation methods to measure the instruction-level parallelism for performance. However these methods cannot disclose the cause of the performance bottle-neck. In this paper, the proposed model takes into account such factors as issue policy, instruction-level parallelism, branch probability, the accuracy of branch prediction, instruction window size, and the number of pipeline units to estimate the issue rate more accurately. To prove the correctness of the model, extensive simulations were performed with Intel 80386/80387 instruction traces. Simulation results showed that the proposed model can estimate the issue rate accurately within 3-10% differences. The analytical model and simulations show that the out-of-order issue can improve the superscalar performance by 70-206% compared to the in-order issue. The model employs parameters to characterize the behavior of programs and the structure of superscalar that cause performance bottle-neck. Thus, it can disclose the cause of the disproportion in performance and reduce the burden of excess simulations that should be performed whenever a new processor is designed.
Toshio ISHIZAKI Koichi OGAWA Hideyuki MIYAKE
Practical design procedure of a four-pole dual-mode cavity filter is explained in the details. Coupling matrix M of an elliptic function filter is derived analytically. The effects of septum thickness is studied experimentally. The dimensions of the aperture have to be modified due to the effects. This attempt had made the filter design very elegant, because no complicated calculation is required. A four-pole filter and a multiplexer are designed and constructed experimentally. They show very excellent performances in the 23 GHz band.
Qi-Wei GE Hidenori YANAGIDA Kenji ONAGA
A data-flow program net is a graph representation of data-flow programs consisting of three types of nodes, AND-node, OR-node and SWITCH-node, which represent arithmetic/logical, data merge and context switch operations respectively. Minimum firing (completion) time T of a program net is an important element in computing parallel degree PARAdeg residing in a data-flow program and is defined as the minimum time when the program net is executed by enough many processors. In this paper, we propose algorithms to efficiently compute T by contracting AND-nodes generally for self-cleaning SWITCH-less program nets with arbitrary node firing time and give the experimental results of the algorithms to show the efficiency.
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.
Takeshi B. NISHIMURA Naotaka IWATA Keiko YAMAGUCHI Masatoshi TOMITA Yasunori BITO Koichi TAKEMURA Yoichi MIYASAKA
This paper describes design approach and power performance of a single 1. 5 V operation two-stage power amplifier MMIC for 2. 4 GHz wireless local area network applications. The MMIC with 0. 760. 96 mm2 area includes SrTiO3 (STO) capacitors with a high capacitance density of 8. 0 fF/µm2 and double-doped AlGaAs/InGaAs/AlGaAs heterojunction FETs with a shallow threshold voltage of -0. 24 V. Utilizing a series STO capacitor and a shunt inductor as an output matching circuit, the total chip size was reduced by 40% as compared with an MMIC utilizing SiNx capacitors. Under single 1.5 V operation, the developed MMIC delivered an output power of 110 mW (20.4 dBm) and a power-added efficiency (PAE) of 36.7% with an associated gain of 20.0 dB at 2.4 GHz. Even operated at a drain bias voltage of 0.8 V, the MMIC exhibited a high PAE of 31.0%.
Arturo CALDERON Shoichi KANAYAMA Shigehide KUHARA
One serious problem affecting the rest and active state images obtained during a functional MRI (fMRI) study is that of involuntary subject movements inside the magnet while the imaging protocol is being carried out. The small signal intensity rise and small activation areas observed in the fMRI results, such as the statistical maps indicating the significance of the observed signal intensity difference between the rest and active states for each pixel, are greatly affected even by head displacements of less than one pixel. Near perfect alignment in the subpixel level of each image with respect to a reference, then, is necessary if the results are to be considered meaningful, specially in a clinical setting. In this paper we report the brain displacements that take place during a fMRI study with an image alignment method based on a refined crosscorrelation function which obtains fast (non-iterative) and precise values for the inplane rotation and X and Y translation correction factors. The performance of the method was tested with phantom experiments and fMRI studies using normal subjects executing a finger-tapping motor task. In all cases, subpixel translations and rotations were detected. The rest and active phases of the time course plots obtained from pixels in the primary motor area were well differentiated after only one pass of the motion correction program, giving enhanced activation zones. Other related areas such as the supplementary motor area became visible only after correction, and the number of pixels showing false activation was reduced.
Kyoichi NAKASHIMA Yutaka NAKAMURA Noboru TAKAGI
This paper presents some fundamental properties of multiple-valued logic functions monotonic in a partial-ordering relation which is introduced in the set of truth values and does not necessarily have the greatest or least element. Two kinds of necessary and sufficient conditions for monotonic p-valued functions are given with the proofs. Their logic formulas using unary operators defined in the partial-ordering relation and a simplification method for those logic formulas are also given. These results include as their special cases our former results for p-valued functions monotonic in the ambiguity relation which is a partial-ordering relation with the greatest element.
In this paper, we apply the Semi-markov Memory and Cache coherence Interference (SMCI) model, which we had proposed for invalidating based cache coherent parallel computers, to an updating based protocol. The model proposed here, the SMCI/Dragon model, can predict performance of cache coherent parallel computers with the Dragon protocol as well as the original SMCI model for the Synapse protocol. Conventional analytic models by stochastic processes to describe parallel computers have the problem of numerical explosion in the number of states necessary as the system size increases. We have already shown that the SMCI model achieved both the small number of states to describe parallel computers with the Synapse protocol and the inexpensive computation cost to predict their performance. In this paper, we demonstrate generality of the SMCI model by applying it to the another cache coherence protocol, Dragon, which has opposite characteristics than Synapse. We show the number of states required by constructing the SMCI/Dragon model is only 21 which is as small as SMCI/Synapse, and the computation cost is also the order of microseconds. Using the SMCI/Dragon model, we investigate several comparative experiments with widely known simulation results. We found that there is only a 5. 4% differences between the simulation and the SMCI/Dragon model.
Norio KOIKE Masato TAKEO Kenichiro TATSUUMA
A simulation methodology to analyze hot-carrier degradation due to bidirectional stressing in a static RAM circuit has been developed. The bidirectional stressing of pass transistors can approximate to unidirectional stressing. The effective stress direction of each NMOSFET can be determined by the higher of the two junction voltages at the peak substrate current generation. Aged SPICE parameter sets extracted in the forward or in the reverse mode are selected for simulating the degradation of each NMOSFET. Furthermore, effects of each NMOSFET degradation on the degraded circuit behavior are simulated. This technique helps detect an NMOSFET having the largest influence on the circuit aging, improving circuit reliability. The methodology was successfully applied to an SRAM device, and was validated by low temperature bias test data.
Masaki HASHIZUME Takeomi TAMESADA Takashi SHIMAMOTO Akio SAKAMOTO
This paper presents two kinds of simplification methods for incompletely specified sequential machines. The strategy of the methods is that as many states in original machines are covered in the simplification processes as possible. The purpose of the methods is to derive a simplified machine having either the largest maximal compatible set or its subset. With the methods, one of the minimal machines can not be always derived, but a near-minimal machine can be obtained more quickly with less memory, since they need not derive all the compatible sets. In this paper, the effectiveness of the methods is checked by applying them to simplification problems of incompletely specified machines generated by using random numbers, and of the MCNC benchmark machines. The experimental results show that our methods can derive a simplified machine quickly, especially for machines having a great number of states or don't care rate.
As open-ended distributed systems and mobile computing systems have spread widely, the need for software which can adapt itself to the dynamic change of runtime environments increases. We call the ability of the software dynamic adaptability. We designed and implemented a language LEAD that provides an architecture for dynamic adaptability. The basic idea is to introduce the mechanism which changes procedure invocation dynamically according to the states of runtime environments. Using LEAD, we can easily realize 1) the highly extensible dynamically adaptable applications, and 2) the introduction of the dynamic adaptability into existing applications.
A function approximation scheme for image restoration is presented to resolve conflicting demands for smoothing within each object and differentiation between objects. Images are defined by probability distributions in the augmented functional space composed of image values and image planes. According to the fuzzy Hough transform, the probability distribution is assumed to take a robust form and its local maxima are extracted to yield restored images. This statistical scheme is implemented by a feedforward neural network composed of radial basis function neurons and a local winner-takes-all subnetwork.
In this paper, a new traffic sign detection algorithm and a symbol recognition algorithm are proposed. For a traffic sign detection, a dominant color transform is introduced, which serves as a tool of highlighting a dominant primary color, while discarding the other two primary colors. For a symbol recognition, the curvilinear shape distribution on a circle centered on the centroid of the symbol, called a circular pattern vector, is used as a spatial feature of the symbol. The circular pattern vector is invariant to scaling, translation, and rotation. As simulation results, the effectiveness of traffic sign detection and recognition algorithms are confirmed.
The following, which is related to the design of the microwave filters, is mainly presented: (1) certain useful approximation which can be obtained by double-resistive- terminated 2-ports consisting of a cascade of two 1-variable 2-ports in different variables, and (2) an approach for filter design from 2-variable viewpoint. Approximations presented provide useful magnitude responses in 2-D domain. Hence it is discussed that how the provided 2-D responses can be used for the design of the microwave filters. Furthermore, properties of the 2-variable transfer functions resulting in such circuits are given.
Kyung-Tae JUNG Hyung-Myung KIM
We propose a Generalized Order Statistic Cell Averaging (GOSCA) CFAR detector. The weighted sums of the order statistics in the leading and lagging reference windows are utilized for the background level estimate. The estimate is obtained by averaging the weighted sums. By changing the weighting values, various CFAR detectors are obtained. The main advantage of the proposed GOSCA CFAR detector over the GOS CFAR detector is to reduce a computational time which is critical factor for the real time operation. We also derive unified formulas of the GOSCA CFAR detector under the noncoherent integration scheme. For Swerling target cases, performances of various CFAR detectors implemented using the GOSCA CFAR detector are derived and compared in homogeneous environment, and in the case of multiple targets and clutter edges situations.
Nozomu TOGAWA Masao YANAGISAWA Tatsuo OHTSUKI
This paper proposes a fast scheduling algorithm based on gradual time-frame reduction for datapath synthesis of digital signal processing hardwares. The objective of the algorithm is to minimize the costs for functional units and registers and to maximize connectivity under given computation time and initiation interval. Incorporating the connectivity in a scheduling stage can reduce multiplexer counts in resource binding. The algorithm maximizes connectivity with maintaining low time complexity and obtains datapath designs with totally small hardware costs in the high-level synthesis environment. The algorithm also resolves inter-iteration data dependencies and thus realizes pipelined datapaths. The experimental results demonstrate that the proposed algorithm reduces the multiplexer counts after resource binding with maintaining low costs for functional units and registers compared with eight conventional schedulers.
In [1], approximate eigenvalues and eigenvectors are defined and algorithms to compute them are described. However, the algorithms require a certain condition: the eigenvalues of M modulo S are all distinct, where M is a given matrix with polynomial entries and S is a maximal ideal generated by the indeterminate in M. In this paper, we deal with the construction of approximate eigenvalues and eigenvectors when the condition is not satisfied. In this case, powers of approximate eigenvalues and eigenvectors become, in general, fractions. In other words, approximate eigenvalues and eigenvectors are expressed in the form of Puiseux series. We focus on a matrix with univariate polynomial entries and give complete algorithms to compute the approximate eigenvalues and eigenvectors of the matrix.
The adaptive associative memory proposed by Ma is used to construct a new model of semantic network, referred to as associative semantic memory (ASM). The main novelty is its computational effectiveness which is an important issue in knowledge representation; the ASM can do inference based on large conceptual hierarchies extremely fast-in time that does not increase with the size of conceptual hierarchies. This performance cannot be realized by any existing systems. In addition, ASM has a simple and easily understandable architecture and is flexible in the sense that modifying knowledge can easily be done using one-shot relearning and the generalization of knowledge is a basic system property. Theoretical analyses are given in general case to guarantee that ASM can flawlessly infer via pattern segmentation and recovery which are the two basic functions that the adaptive associative memory has.
Kenji FUKAZAWA Jiro HIROKAWA Makoto ANDO Naohisa GOTO
The authors propose a novel waveguide two-way power divider, named as τ-junction, in a feed waveguide of a single-layer slotted waveguide array antenna. This junction occupies only a small space and is placed in the middle of a cascade of several power dividers. It suppresses the long line effect and widens the bandwidth of the feed waveguide. The junction has two inductive walls; one is for suppressing the reflection and the other is for controlling the ratio of divided power to the two output ports. Analysis using Galerkin's method of moments is verified by experiments of a 4 GHz-band model. We install the junctions in a 12 GHz-band single-layer slotted waveguide array. The gain reduction at the band-edge is suppressed.