Jonggil LEE Hyunchul KANG Seung-Kuk CHOI
The jitter characteristics of synchronous residual time stamp (SRTS) method used in ATM adaptation layer type 1 (AAL1) are analyzed. In this letter, the root mean square amplitude of filtered SRTS jitter is calculated and the computer simulation has been carried out to show jitter of SRTS method considering also the phase time error of network clocks.
With increased size and issue-width, instruction issue queue becomes one of the most energy consuming units in today's superscalar microprocessors. This paper presents a novel architectural technique to reduce energy dissipation of adaptive issue queue, whose functionality is dynamically adjusted at runtime to match the changing computational demands of instruction stream. In contrast to existing schemes, the technique exploits a new freedom in queue design, namely the voltage per access. Since loading capacitance operated in the adaptive queue varies in time, the clock cycle budget becomes inefficiently exploited. We propose to trade-off the unused cycle time with supply voltage, lowering the voltage level when the queue functionality is reduced and increasing it with the activation of resources in the queue. Experiments show that the approach can save up to 39% of the issue queue energy without large performance and area overhead.
Dingjun CHEN Takafumi AOKI Naofumi HOMMA Tatsuo HIGUCHI
We introduce PC Linux cluster computing techniques to an Evolutionary Graph Generation (EGG) system, and successfully implement the parallel version of the EGG system, called PEGG. Our survey satisfactorily shows that the parallel evolutionary approach meets our expectation that the final solutions obtained from PEGG will be as good as or better than those obtained from EGG, and that PEGG can ultimately improve the speed of evolution.
SungHun NAM IlYoung CHUNG SungHo CHO ChongSun HWANG
The stateless-based cache invalidation schemes for wireless environments can be categorized into either asynchronous or synchronous cache invalidation according to the broadcasting way of invalidation report. However, if the asynchronous cache invalidation scheme attempts to support local processing of read-only transaction, a critical problem may occur; the asynchronous invalidation reports provide no guarantee of waiting time for mobile transactions requesting commit. To solve this problem, the server in our approaches broadcasts two kind of messages, asynchronous invalidation report to reduce transaction latency and periodic guide message to avoid the uncertainty of waiting time for the next invalidation report. This paper presents a simulation-based analysis on the performance of the suggesting algorithms. The simulation experiments show that the local processing algorithms of read-only transaction based on asynchronous cache invalidation scheme get better response time than the algorithm based on synchronous cache invalidation scheme.
Liang ZHAO Hiroshi NAGAMOCHI Toshihide IBARAKI
We consider to design approximation algorithms for the survivable network design problem in hypergraphs (SNDPHG) based on algorithms developed for the survivable network design problem in graphs (SNDP) or the element connectivity problem in graphs (ECP). Given an instance of the SNDPHG, by replacing each hyperedge e={v1,
Caihua WANG Hideki TANAHASHI Hidekazu HIRAYU Yoshinori NIWA Kazuhiko YAMAMOTO
In this paper, we propose a probabilistic approach to derive an approximate polyhedral description from range data. We first compare several least-squares-based methods for estimation of local normal vectors and select the most robust one based on a reasonable noise model of the range data. Second, we extract the stable planar regions from the range data by examining the distributions of the local normal vectors together with their spatial information in the 2D range image. Instead of segmenting the range data completely, we use only the geometries of the extracted stable planar regions to derive a polyhedral description of the range data. The curved surfaces in the range data are approximated by their extracted plane patches. With a probabilistic approach, the proposed method can be expected to be robust against the noise. Experimental results on real range data from different sources show the effectiveness of the proposed method.
Masahiro ISHIKAWA Kazutaka FURUSE Hanxiong CHEN Nobuo OHBO
Clustering is one of the most important topics in the field of knowledge discovery from databases. Especially, hierarchical clustering is useful since it gives a hierarchical view of a whole database and can be used to guide users in browsing a huge database. In many cases, clustering can be modeled as a graph partitioning problem. When an appropriate distance function between database objects is given, a database can be viewed as an edge-weighted complete graph, where vertices are database objects and weights of edges are distances between them. Then a process of MST (Minimal Spanning Tree) construction can be viewed as a process of a single-linkage agglomerative clustering process for database objects. In this paper, we propose an efficient MST construction method for a large complete metric graph, which is derived from a database with a metric distance function defined on it. Our method utilizes a metric index to reduce the number of distance calculations. The basic idea is to exclude those edges less probable to be a part of an MST by using the metric postulate. For this purpose, we introduce a new metric index named MetricMatrix. Experimental results show that our method can drastically reduce the number of distance calculations needed for MST construction in comparison with the classical method.
We give an overview of the computational complexity of linear and mesh-connected cellular and iterative arrays with respect to well known models of sequential and parallel computation. We discuss one-way communication versus two-way communication, serial input versus parallel input, and space-efficient simulations. In particular, we look at the parallel complexity of cellular arrays in terms of the PRAM theory and its implications, e.g., to the parallel complexity of recurrence equations and loops. We also point out some important and fundamental open problems that remain unresolved. Next, we investigate the solvability of some reachability and safety problems concerning machines operating in parallel and cite some possible applications. Finally, we briefly discuss the complexity of the "commutativity analysis" technique that is used in the areas of parallel computing and parallelizing compilers.
Tomotsugu OKADA Manabu KOBAYASHI Shigeichi HIRASAWA
Y. S. Han et al. have proposed an efficient maximum likelihood decoding (MLD) algorithm using A* algorithm which is the graph search method. In this paper, we propose a new MLD algorithm for linear block codes. The MLD algorithm proposed in this paper improves that given by Han et al. utilizing codewords of dual codes. This scheme reduces the number of generated codewords in the MLD algorithm. We show that the complexity of the proposed decoding algorithm is reduced compared to that given by Han et al. without increasing the probability of decoding error.
Yoshiharu FUJISAKU Masatoshi KAGAWA Toshio NAKAMURA Hitoshi MURAI Hiromi T. YAMADA Shigeru TAKASAKI Kozo FUJII
40 Gbit/s optical transceiver using a novel OTDM MUX module has been developed. OTDM (Optical-Time-Division-Multiplexing) MUX module, the core component of the transmitter, consisted of a optical splitter, two electro-absorption (EA) modulators and a combiner in a sealed small package. As the split optical paths run through the "air" in the module, greatly stable optical phase relation between bit-interleaved pulses could be maintained. With the OTDM MUX module, the selection between conventional Return-to-Zero (conventional-RZ) format and carrier-suppressed RZ (CS-RZ) format is performed by slightly changing the wavelength of laser-diode. In a receiver, 40 Gbit/s optical data train is optically demultiplexed to 10 Gbit/s optical train, before detected by the O/E receiver for 10 Gbit/s RZ format. Back-to-back MUX-DEMUX evaluations of the transceiver exhibited good sensitivities of under -30 dBm measured at 40 Gbit/s optical input to achieve the bit-error-rate (BER) of 10-9. Another unique feature of the transceiver system was a spectrum switch capability. The stable RZ and CS-RZ multiplexing operation was confirmed in the experiment. Once we adjust the 40 Gbit/s optical signal to CS-RZ format, the optical spectrum would maintain its CS spectrum shape for a long time to the benefit of the stable long transmission characteristics. In the recirculating loop experiment employing the OTDM MUX transceiver, the larger power margin was successfully observed with CS-RZ format than with conventional-RZ format, indicating that proper encoding of conventional-RZ and CS-RZ was realized with this prototype transceiver. In the case of CS-RZ format, the error free (BER < 10-9) transmission over 720 km was achieved with the long repeater amplifier span of 120 km.
Hiromitsu KIMURA Takahiro HANYU Michitaka KAMEYAMA
A new logic-in-memory circuit is proposed for a fine-grain pipelined VLSI system. Dynamic-storage elements are distributed over a logic-circuit plane. A functional pass gate is a key component, where a linear summation and threshold function are merged compactly using charge-storage and charge-coupling effect with a DRAM-cell-based circuit structure. The use of dynamic logic based on pass-transistor network using functional pass gates makes it possible to realize any logic circuits compactly with small power dissipation. As a typical example, a 54-bit pipelined multiplier is implemented by using the proposed circuit technology. Its power dissipation and chip area are reduced to about 63 percent and 72 percent, respectively, in comparison with those of a corresponding binary CMOS implementation under 0.35-µm CMOS technology.
Sheng-He SUN Xiao-Dan MEI Zhao-Li ZHANG
A novel rough neural network (RNN) structure and its application are proposed in this paper. We principally introduce its architecture and training algorithms: the genetic training algorithm (GA) and the tabu search training algorithm (TSA). We first compare RNN with the conventional NN trained by the BP algorithm in two-dimensional data classification. Then we compare RNN with NN by the same training algorithm (TSA) in functional approximation. Experiment results show that the proposed RNN is more effective than NN, not only in computation time but also in performance.
Hiroshi NAGAHASHI Mohamed IMINE
This paper develops a simple algorithm for calculating a polynomial curve or surface in a parallel way. The number of arithmetic operations and the necessary time for the calculation are evaluated in terms of polynomial degree and resolution of a curve and the number of processors used. We made some comparisons between our method and a conventional method for generating polynomial curves and surfaces, especially in computation time and approximation error due to the reduction of the polynomial degree. It is shown that our method can perform fast calculation within tolerable error.
Hiroyoshi MIWA Kazunori KUMAGAI Shinya NOGAMI Takeo ABE Hisao YAMAMOTO
The explosive growth of World Wide Web usage is causing a number of performance problems, including slow response times, network congestion, and denial of service. Web site that has a huge number of accesses and requires high quality of services, such as a site offering hosting services, or content delivery services, usually uses a cache server to reduce the load on the original server offering the original content. To increase the throughput of the caching process and to improve service availability, multiple cache servers are often positioned in front of the original server. This requires a switch to direct incoming requests to one of the multiple cache servers. In this paper, we propose a routing algorithm for such a switch in front of clustered multiple cache servers and evaluate its performance by simulation. The results show that our routing algorithm is effective when content has request locality and a short period of validity, for example, news, map data, road traffic data, or weather information. We also identify points to consider when the proposed algorithm is applied to a real system.
This paper focuses on the watermarking system using a controlled quantization process. We first present a model of the watermark embedding and extracting processes and carry out their analyses. Then we examine the robustness of the watermarking system against common image processing and clarify the reason why detection errors occur in the watermark extracting process. Based on the result, we improve the watermark extracting process and design robust watermarking systems. The improvement is accomplished using a deconvolution filter and neural network techniques. Numerical experiments using the DCT-based watermarking system show good performance as expected by us.
Katsuya MINAMI Hideki TODE Koso MURAKAMI
Recently, as multimedia and high-speed traffic become more popular on the Internet, the various traffic requiring different qualities of service (QoS) will co-exist. In addition, classified service based on Diff-Serv (Differentiated Service), MPLS (Multi-Protocol Label Switching),etc., have come into wide use. Today's Internet environment requires routers to perform control mechanisms in order to guarantee various QoSs. In this paper, we propose a buffer management scheme for the Internet router that uses class-based priority control. This paper focuses on per-flow queueing, and evaluates the performance of the proposed buffer management scheme. Realization of differentiated services and dissolution of buffer occupation by specific flow is expected by the proposed control.
Hyun-Soo PARK Seihyoung LEE Un-Chul PAEK Youngjoo CHUNG
We will discuss a novel non-contact removal technique of optical fiber coating in continuous and uninterrupted manner with hot air stream. We observed little degradation of the tensile strength of the optical fiber after removing the protective polymer coating and the mean breaking tensile strength of the stripped optical fiber using non-contact removal method was 5.1 GPa.
The vertical-cavity surface-emitting laser (VCSEL) is becoming a key device in high-speed optical local-area networks (LANs) and even wide-area networks (WANs). This device is also enabling ultra parallel data transfer in equipment and computer systems. In this paper, we will review its physics and the progress of technology covering the spectral band from infrared to ultraviolet by featuring materials, fabrication technology, and performances such as threshold, output power, polarization, modulation and reliability. Lastly, we will touch on its future prospects.
Seiji KUMAZAWA Tsuyoshi YAMAMOTO Yoshinori DOBASHI
In functional brain images obtained by analyzing higher human brain functions using functional magnetic resonance imaging (fMRI), one serious problem is that these images depict false activation areas (artifacts) resulting from image-to-image physiological movements of subject during fMRI data acquisition. In order to truly detect functional activation areas, it is necessary to eliminate the effects of physiological movements of subject (i.e., gross head motion, pulsatile blood and cerebrospinal fluid (CSF) flow) from fMRI time series data. In this paper, we propose a method for eliminating artifacts due to not only rigid-body motion such as gross head motion, but also non-rigid-body motion like the deformation caused by the pulsatile blood and CSF flow. The proposed method estimates subject movements by using gradient methods which can detect subpixel optical flow. Our method estimates the subject movements on a "pixel-by-pixel" basis, and achieves the accurate estimation of both rigid-body and non-rigid-body motion. The artifacts are reduced by correction based on the estimated movements. Therefore, brain activation areas are accurately detected in functional brain images. We demonstrate that our method is valid by applying it to real fMRI data and that it can improve the detection of brain activation areas.
OFDM modulation has attracted attention for fourth-generation mobile communication systems and high-speed wireless LANs. However, it has a very serious problem of large peak power. PTS (partial transmit sequences) has been proposed as one solution to this problem. In PTS, the OFDM subcarriers are divided into several clusters, and the phase of each cluster is rotated by a complex weight to minimize the PAPR (peak-to-average power ratio). However, the weight of the phase rotation must be sent to the mobile terminal by using a side information channel. In this paper, we propose two weight estimation methods at the receiver to avoid weight transmission in side information channels. The first method uses pilot signals, while the second is a blind estimation method that changes the weight pattern. We evaluate the performance of these methods by computer simulation.