Takanori KOMURO Naoto HAYASAKA Haruo KOBAYASHI Hiroshi SAKAYORI
This paper proposes a new approach for analog portion testing, which can meet requirements for high-speed and high-accuracy testing simultaneously with reasonable cost. The key concept of the new method is cooperation of an LSI tester and some circuitry built in a target SoC device. We will explain the operation principle of the proposed method. The proposed method can be one of the methods to overcome today's expensive production test of analog portion on SoC (System on Chip) devices which heavily depends on LSI tester capability and will become harder in near future.
Che-Wun CHIOU Chiou-Yng LEE An-Wen DENG Jim-Min LIN
Because fault-based attacks on cryptosystems have been proven effective, fault diagnosis and tolerance in cryptography have started a new surge of research and development activity in the field of applied cryptography. Without magnitude comparisons, the Montgomery multiplication algorithm is very attractive and popular for Elliptic Curve Cryptosystems. This paper will design a Montgomery multiplier array with a bit-parallel architecture in GF(2m) with concurrent error detection capability to protect it against fault-based attacks. The robust Montgomery multiplier array with concurrent error detection requires only about 0.2% extra space overhead (if m=512 is as an example) and requires four extra clock cycles compared to the original Montgomery multiplier array without concurrent error detection.
Yaya WEI Chuang LIN Xin JIN Raad RAAD Fengyuan REN
The guard channel scheme in wireless mobile networks has attracted and is still drawing research interest owing to easy implementation and flexible control. Dynamic guard channel schemes have already been proposed in the literature to adapt to varying traffic load. This paper presents a novel control-theoretic approach to dynamically reserve guard channels called PI-Guard Channel (PI-GC) controller that maintains the handoff blocking probability (HBP) to a predefined value; while it still improves the channel resource utilization.
An algorithm is described for solving the node-to-set disjoint paths problem in bi-rotator graphs, which are obtained by making each edge of a rotator graph bi-directional. The algorithm is of polynomial order of n for an n-bi-rotator graph. It is based on recursion and divided into three cases according to the distribution of destination nodes in the classes into which the nodes in a bi-rotator graph are categorized. We estimated that it obtains 2n-3 disjoint paths with a time complexity of O(n5), that the sum of the path lengths is O(n3), and that the length of the maximum path is O(n2). Computer experiment showed that the average execution time was O(n3.9) and, the average sum of the path lengths was O(n3.0).
In parallelizing compilers on distributed memory systems, distributions of irregular sized array blocks are provided for load balancing and irregular problems. The irregular data redistribution is different from the regular block-cyclic redistribution. This paper is devoted to scheduling message for irregular data redistribution that attempt to obtain suboptimal solutions while satisfying the minimal communication costs condition and the minimal step condition. Based on the list scheduling, an efficient algorithm is developed and its experimental results are compared with previous algorithms. The improved list algorithm provides more chance for conflict messages in its relocation phase, since it allocates conflict messages through methods used in a divide-and-conquer algorithm and a relocation algorithm proposed previously. The method of selecting the smallest relocation cost guarantees that the improved list algorithm is more efficient than the other two in average.
Makoto ISHIHARA Hiroki HONDA Mitsuhisa SATO
iPat/OMP is an interactive parallelization assistance tool for OpenMP. In the present paper, we describe the design concept of iPat/OMP, the parallelization sequence achieved by the tool and its current implementation status. In addition, we present an evaluation of the performance of the implemented functionalities. The experimental results show that iPat/OMP can detect parallelism and create an appropriate OpenMP directive for several for-loops.
Giscard WEPIWE Plamen L. SIMEONOV
The paper presents HiPeer, a robust resource distribution and discovery algorithm that can be used for fast and fault-tolerant location of resources in P2P network environments. HiPeer defines a concentric multi-ring overlay networking topology, whereon dynamic network management methods are deployed. In terms of performance, HiPeer delivers of number of lowest bounds. We demonstrate that for any De Bruijn digraph of degree d 2 and diameter DDB HiPeer constructs a highly reliable network, where each node maintains a routing table with at most 2d+2 entries independent of the number N of nodes in the system. Further, we show that any existing resource in the network with at most d nodes can be found within at most DHiPeer = log d(N(d-1)+d)-1 overlay hops. This result is as close to the Moore bound [1] as the query path length in other outstanding P2P proposals based on the De Bruijn digraphs. Thus, we argue that HiPeer defines a highly connected network with connectivity d and the lowest yet known lookup bound DHiPeer. Moreover, we show that any node's "join or leave" operation in HiPeer implies a constant expected reorganization cost of the magnitude order of O(d) control messages.
Gabriel RODRIGUEZ María J. MARTIN Patricia GONZALEZ Juan TOURIÑO
This paper presents CPPC (Controller/Precompiler for Portable Checkpointing), a checkpointing tool designed for heterogeneous clusters and Grid infrastructures through the use of portable protocols, portable checkpoint files and portable code. It works at variable level being user-directed, thus generating small checkpoint files. It allows parallel processes to checkpoint independently, without runtime coordination or message-logging. Consistency is achieved at restart time by negotiating the restart point. A directive-based checkpointing precompiler has also been implemented to ease up user's effort. CPPC was designed to work with parallel MPI programs, though it can be used with sequential ones, and easily extended to parallel programs written using different message-passing libraries, due to its highly modular design. Experimental results are shown using CPPC with different test applications.
Paola FLOCCHINI Antonio Mesa ENRIQUES Linda PAGLI Giuseppe PRENCIPE Nicola SANTORO
We consider the problem of computing the optimal swap edges of a shortest-path tree. This problem arises in designing systems that offer point-of-failure shortest-path rerouting service in presence of a single link failure: if the shortest path is not affected by the failed link, then the message will be delivered through that path; otherwise, the system will guarantee that, when the message reaches the node where the failure has occurred, the message will then be re-routed through the shortest detour to its destination. There exist highly efficient serial solutions for the problem, but unfortunately because of the structures they use, there is no known (nor foreseeable) efficient distributed implementation for them. A distributed protocol exists only for finding swap edges, not necessarily optimal ones. We present two simple and efficient distributed algorithms for computing the optimal swap edges of a shortest-path tree. One algorithm uses messages containing a constant amount of information, while the other is tailored for systems that allow long messages. The amount of data transferred by the protocols is the same and depends on the structure of the shortest-path spanning-tree; it is no more, and sometimes significantly less, than the cost of constructing the shortest-path tree.
Ichinoshin MAKI Hideyuki SHIMONISHI Tutomu MURASE Masayuki MURATA
Because of the development of recent broadband access technologies, fair service among users is becoming more important goal. The most promising router mechanisms for providing fair service is per-flow traffic management. However, it is difficult to implement in high-speed core routers because per-flow state management is prohibitively expensive; thus, a large number of flows are aggregated into a small number of queues. This is not an acceptable situation because fairness degrades as the number of flows so aggregated increases. In this paper, we propose a new traffic management scheme called Hierarchically Aggregated Fair Queueing (HAFQ) to provide per-flow fair service. Our scheme can adjust flow aggregation levels according to the queue handling capability of various routers. This means the proposed scheme scales well in high-speed networks. HAFQ improves the fairness among aggregated flows by estimating the number of flows aggregated in a queue and allocating bandwidth to the queue proportionally. In addition, since HAFQ can identify flows having higher arrival rates simultaneously while estimating the number of flows, it enhances the fairness by preferentially dropping their packets. We show that our scheme can provide per-flow fair service through extensive simulation and experiments using a network processor. Since the currently available network processors (Intel IXP1200 in our case) are not high capacity, we also give extensive discussions on the applicability of our scheme to the high-speed core routers.
Hai JIN Xuanhua SHI Weizhong QIANG Deqing ZOU
Grid computing presents a new trend to distributed and Internet computing to coordinate large scale resources sharing and problem solving in dynamic, multi-institutional virtual organizations. Due to the diverse failures and error conditions in the grid environments, developing, deploying, and executing applications over the grid is a challenge, thus dependability is a key factor for grid computing. This paper presents a dependable grid computing framework, called DRIC, to provide an adaptive failure detection service and a policy-based failure handling mechanism. The failure detection service in DRIC is adaptive to users' QoS requirements and system conditions, and the failure-handling mechanism can be set optimized based on decision-making method by a policy engine. The performance evaluation results show that this framework is scalable, high efficiency and low overhead.
Seungjun KIM Hojung KIM Seongeun EOM Nitaigour P. MAHALIK Byungha AHN
Most of the traveller guidance services (TGS) are based on GPS technology and generally concerned with the position data mapping on the simplified 2D electronic map in order to provide macro level service facility such as drive direction notifications. Digital GIS based GPS entails in situ intuitive visualization. The visually enhanced TGS can improve the global and local awareness of unknown areas. In this paper, we propose a reliable new TGS system that provides 3D street as well as pin-pointed destination information in two stages of its interactive services; web-based and AR-based. The web server generates a guiding path on 2D digital map and displays 3D car-driving animation along the path. And, the AR-based service is embedded so that users can interactively obtain the detailed micro-level information of a specific section in the area with their fingertips. The implementation is based on autoformation of on-line GIS data structures from the available priori. For the verification, a 54 road network is selected as a test area. In the service demonstration, we show the effective awareness of street environments and the usefulness of this new TGS system.
Chih-Yuan LIN Jwo-Yuh WU Ta-Sung LEE
Conventional orthogonal frequency division multiplexing (OFDM) system utilizes cyclic prefix (CP) to remove the channel-induced inter-symbol interference (ISI) at the cost of lower spectral efficiency. In this paper, a generalized sidelobe canceller (GSC) based equalizer for ISI suppression is proposed for uplink multi-antenna OFDM systems without CP. Based on the block representation of the CP-free OFDM system, there is a natural formulation of the ISI suppression problem under the GSC framework. By further exploiting the signal and ISI signature matrix structures, a computationally efficient partially adaptive (PA) implementation of the GSC-based equalizer is proposed for complexity reduction. The proposed scheme can be extended for the design of a pre-equalizer, which pre-suppresses the ISI and realizes CP-free downlink transmission to ease the computational burden of the mobile unit (MU). Simulation results show that the proposed GSC-based solutions yield equalization performances almost identical to that obtained by the conventional CP-based OFDM systems and are highly resistant to the increase in channel delay spread.
In this paper, we present the Tangible Media Control System (TMCS), which allows users to manipulate media contents through physical objects in an intuitive way. Currently, most people access digital media contents by exploiting GUI. However, it only provides limited manipulation of the contents. The proposed system, instead of a mouse and a keyboard, adopts two types of tangible objects, i.e. a RFID-enabled object and a tracker-embedded object. The TMCS enables users to easily access and control digital media contents through tangible objects. In addition, it supports an interactive media controller which can be used to synthesize media contents according to users' taste. It also offers personalized contents, which suits users' preferences, by exploiting context such as the users' profile and situational information. Accordingly, the TMCS demonstrates that tangible interfaces with context can provide more effective interfaces to satisfy users' demands. Therefore, the proposed system can be applied to various interactive applications such as multimedia education, entertainment, multimedia editor, etc.
Yung-Fang CHEN Fang-Shuo TSENG
In this paper, we propose an angle of arrival (AOA)-based beamforming structure with strong interference resistant capability for OFDM systems. First, we present novel interference resistant angle of arrival (AOA) estimation schemes for each multipath without training sequences or symbols as the pre-processing of the proposed structure. The generalized sidelobe canceler (GSC) structure is thus applied with the AOA information to avoid calculating the beamforming weight vector individually on a per subcarrier basis, wherein the GSC structure with the reduced-rank multistage Wiener filter (MSWF) is adopted. We also propose a signal transformation scheme to improve performance before the signals are fed into the GSC receiver. The proposed receiver offers better performance than the GSC form of the constrained Wiener filter-based receiver due to the faster convergence property of reduced rank processing and the signal transformation scheme.
In recent years, considerable attention has been devoted to continuously running software systems whose performance characteristics are smoothly degrading in time. Software aging often affects the performance of a software system and eventually causes it to fail. A novel approach to handle transient software failures due to software aging is called software rejuvenation, which can be regarded as a preventive and proactive solution that is particularly useful for counteracting the aging phenomenon. In this paper, we focus on a high assurance software system with fault-tolerance and preventive rejuvenation, and analyze the stochastic behavior of such a highly critical software system. More precisely, we consider a fault-tolerant software system with two-version redundant structure and random rejuvenation schedule, and evaluate quantitatively some dependability measures like the steady-state system availability and MTTF based on the familiar Markovian analysis. In numerical examples, we examine the dependence of two fault tolerant techniques; design and environment diversity techniques, on the system dependability measures.
Masayuki HASHIMOTO Kenji MATSUO Atsushi KOIKE
This paper proposes an effective JPEG 2000 encoding method for reducing tiling artifacts, which cause one of the biggest problems in JPEG 2000 encoders. Symmetric pixel extension is generally thought to be the main factor in causing artifacts. However this paper shows that differences in quantization accuracy between tiles are a more significant reason for tiling artifacts at middle or low bit rates. This paper also proposes an algorithm that predicts whether tiling artifacts will occur at a tile boundary in the rate control process and that locally improves quantization accuracy by the original post quantization control. This paper further proposes a method for reducing processing time which is yet another serious problem in the JPEG 2000 encoder. The method works by predicting truncation points using the entropy of wavelet transform coefficients prior to the arithmetic coding. These encoding methods require no additional processing in the decoder. The experiments confirmed that tiling artifacts were greatly reduced and that the coding process was considerably accelerated.
Chi-Chia SUNG Shanq-Jang RUAN Bo-Yao LIN Mon-Chau SHIE
In recent years, the demand for multimedia mobile battery-operated devices has created a need for low power implementation of video compression. Many compression standards require the discrete cosine transform (DCT) function to perform image/video compression. For this reason, low power DCT design has become more and more important in today's image/video processing. This paper presents a new power-efficient Hybrid DCT architecture which combines Loeffler DCT and binDCT in terms of special property on luminance and chrominance difference. We use Synopsys PrimePower to estimate the power consumption in a TSMC 0.25-µm technology. Besides, we also adopt a novel quality assessment method based on structural distortion measurement to measure the quality instead of peak signal to noise rations (PSNR) and mean squared error (MSE). It is concluded that our Hybrid DCT offers similar quality performance to the Loeffler, and leads to 25% power consumption and 27% chip area savings.
Mitsutoshi YAHARA Kuniaki FUJIMOTO Hirofumi SASAKI
In this paper, we propose a voltage controlled oscillator (VCO) with up mode type Miller-integrator. The controlled voltage of this VCO can continuously change 0 V center in the positive and negative bidirection. Also, the relationship between control voltage and oscillating frequency shows the good linearity, and the calculated and the measured values agree well.
Debatosh DEBNATH Tsutomu SASAO
Fixed polarity Reed-Muller expressions (FPRMs) exhibit several useful properties that make them suitable for many practical applications. This paper presents an exact minimization algorithm for FPRMs for incompletely specified functions. For an n-variable function with α unspecified minterms there are 2n+α distinct FPRMs, and a minimum FPRM is one with the fewest product terms. To find a minimum FPRM the algorithm requires to determine an assignment of the incompletely specified minterms. This is accomplished by using the concept of integer-valued functions in conjunction with an extended truth vector and a weight vector. The vectors help formulate the problem as an assignment of the variables of integer-valued functions, which are then efficiently manipulated by using multi-terminal binary decision diagrams for finding an assignment of the unspecified minterms. The effectiveness of the algorithm is demonstrated through experimental results for code converters, adders, and randomly generated functions.