Ying-Hong WANG Chih-Chieh CHUANG Chih-Feng CHAO
A mobile ad hoc network (MANET) is a self-organizing and adaptive wireless network constructed by the dynamic gathering of mobile nodes (MNs). The communication among MNs in MANETs is carried out without base stations or access points and the transmission of data packets is completed through relays among nodes. Due to the mobility of MNs, the topology of a MANET frequently changes and thus results in the disability of on-the-fly data transmission routes. To cope with the intrinsic properties of MANETs, Dynamic Backup Routes Routing Protocol (DBR2P), a distributed backup routes mechanism for quick reconnection during link failures, is proposed in this paper. DBR2P is an on-demand routing protocol which can set up many backup routes to reach a destination node in a given period of time. The information of backup routes can be saved in a specific on-the-route node and enables backup routes to be found immediately in situation regarding disconnection. When a link fails, routes from the source node to the destination node are analyzed to obtain backup routes and to sustain quick reconnection. As a result, DBR2P could more thoroughly improve the quality of routing than previous routing protocols.
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.
FPGAs (Field-Programmable Gate Arrays) have been widely used as coprocessors to boost the performance of data-intensive applications [1],[2]. However, there are several challenges to further boost FPGA performance: the communication overhead between the host workstation and the FPGAs can be substantial; large-scale applications cannot fit in a single FPGA because of its limited capacity; mapping an application algorithm to FPGAs still remains a daunting job in configurable system design. To circumvent these problems, we propose in this paper the FPGA-based Hierarchical-SIMD (H-SIMD) machine with its codesign of the Pyramidal Instruction Set Architecture (PISA). PISA comprises high-level instructions implemented as FPGA functions of coarse-grain SIMD (Single-Instruction, Multiple-Data) tasks to facilitate ease of program development, code portability across different H-SIMD implementations and high performance. We assume a multi-FPGA board where each FPGA is configured as a separate SIMD machine. Multiple FPGA chips can work in unison at a higher SIMD level, if needed, controlled by the host. Additionally, by using a memory switching scheme and the high-level PISA to partition applications into coarse-grain tasks, host-FPGA communication overheads can be hidden. We enlist the two-dimensional Fast Fourier Transform (2D FFT) to test the effectiveness of H-SIMD. The test results show sustained high performance for this problem. The H-SIMD machine even outperforms a Xeon processor for this problem.
Geometrical properties of the lifting-up technique in support vector machines (SVMs) are discussed here. In many applications, an SVM finds the optimal inhomogeneous separating hyperplane in terms of margins while some of the theoretical analyses on SVMs have treated only homogeneous hyperplanes for simplicity. Although they seem equivalent due to the so-called lifting-up technique, they differ in fact and the solution of the homogeneous SVM with lifting-up strongly depends on the parameter of lifting-up. It is also shown that the solution approaches that of the inhomogeneous SVM in the asymptotic case that the parameter goes to infinity.
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.
Muneo KUSHIMA Motoi INABA Koichi TANNO
In this letter, my proposals for a Floating node voltage-controlled Variable Resistor circuit (FVR) are based upon its advantages as linear and compact. The performance of the proposed circuit was confirmed by PSpice simulation. The simulation results are reported in this letter.
Ning FU Shigetoshi NAKATAKE Yasuhiro TAKASHIMA Yoji KAJITANI
The shape-based routing needs a routing architecture with a geometrical computation framework on it. This paper introduces a novel routing architecture, Oct-Touched Tile (OTT), with a geometrical computation method along the horizontal- and vertical-constraints. The architecture is represented by the tiles spreading over the 2-D plane. Each tile is flexible to satisfy the constraints imposed for non-overlapping and sizing request. In this framework, path finding and shape-based sizing are executed on the same architecture. In experiments, our system demonstrates the performance comparable to a commercial tool. In addition, we show potential of OTT by introducing several ideas of extensions to analog layout constraints.
Hashem Hashemi NAJAF-ABADI Hamid SARBAZI-AZAD
In this paper, routing properties of cube-based optoelectronic OTIS networks are explored. We show emulations of various cubical network topologies on their OTIS augmented variants, including the n-D grid networks, shuffle-exchange, and de Brujin networks. An analytical performance model for OTIS-cube networks is proposed. The model is validated by means of comparison with rigorously obtained simulation results. Using this model, the performance characteristics of the OTIS-hypercube network are evaluated in view of a number of different constraints. Moreover, we compare the performance characteristics of the OTIS-hypercube with that of equivalent fully-electronic networks under various implementation constraints.
Hossein SHAMSI Omid SHOAEI Roghayeh DOOST
In this paper by using an exactly analytic approach the clock jitter in the feedback path of the continuous time Delta Sigma modulators (CT DSM) is modeled as an additive jitter noise, providing a time invariant model for a jittery CT DSM. Then for various DAC waveforms the power spectral density (psd) of the clock jitter at the output of DAC is derived and by using an approximation the in-band power of the clock jitter at the output of the modulator is extracted. The simplicity and generality of the proposed approach are the main advantages of this paper. The MATALB and HSPICE simulation results confirm the validity of the proposed formulas.
Chih-Min YU Shiang-Jiun LIN Chia-Chi HUANG
In this paper, we present Blueweb, a new Bluetooth-based multihop network with an efficient scatternet formation algorithm and a hybrid routing protocol. The Blueweb is designed from the original idea of Bluetree. Blueweb's scatternet formation uses two mechanisms. One is the role exchange mechanism in which only slave nodes serve as the role of relay through the whole scatternet. The other one is the return connection mechanism in which we convert the scatternet from a tree-shaped to a web-shaped topology. Meanwhile, a modified source routing protocol is designed for Blueweb in which we combine the proactive method with the reactive method to discover the optimal path for packet transmission. Furthermore, using computer simulations we compared the system performance of Blueweb and Bluetree with both a static model and a uniform traffic model. With the static model we evaluate the scatternet performance and with the uniform traffic model we evaluate the transmission performance. Our simulation results show that Blueweb achieves superior system performance than Bluetree on both scatternet performance and transmission performance.
Takaaki MANABE Jun Hyun AHN Iwao YAMAGUCHI Mitsugu SOHMA Wakichi KONDO Ken-ichi TSUKADA Kunio KAMIYA Susumu MIZUTA Toshiya KUMAGAI
The 5-cm-diameter double-sided YBa2Cu3O7 (YBCO) films were prepared by metal organic deposition (MOD) using a commercially available metal-naphthenate coating solution. Firstly, YBCO film was prepared by MOD on one side of a double-side-polished 5-cm-diameter LaAlO3 substrate. Secondly, another side was similarly coated with YBCO by MOD. After the latter processing, degradation of average Jc value in the first side was not observed; but the fluctuation of critical current density Jc slightly increased. The double-sided YBCO films showed average Jc values of 0.8-1.0 MA/cm2 at 77 K and microwave surface resistances Rs(12 GHz) of 0.86-1.07 mΩ at 70 K.
Hiroshi YAMAMOTO Kenji KAWAHARA Tetsuya TAKINE Yuji OIE
Recent improvements in the performance of end-computers and networks have made it feasible to construct a grid system over the Internet. A grid environment consists of many computers, each having a set of components and a distinct performance. These computers are shared among many users and managed in a distributed manner. Thus, it is important to focus on a situation in which the computers are used unevenly due to decentralized management by different task schedulers. In this study, which is a preliminary investigation of the performance of task allocation schemes employed in a decentralized environment, the average execution time of a long-lived task is analytically derived using the M/G/1-PS queue. Furthermore, assuming a more realistic condition, we evaluate the performance of some task allocation schemes adopted in the analysis, and clarify which scheme is applicable to a realistic grid environment.
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.
Kazuaki YAMAGUCHI Sumio MASUDA
The 2-terminal shortest path problem is to find a shortest path between two specified vertices in a given graph G. In this paper, we consider this problem in the following situation: G is given before the two vertices are specified so that some preprocessing is allowed to reduce the response time. We present a method for calculating lower bounds of the length of the shortest path for any pair of vertices. Experimental results show that the A* algorithm with our method performs much better than previous methods.
Mobile applications require software reconfiguration to improve resource usage and availability. We propose a power-aware reconfiguration scheme that (1) moves energy-demanding applications to proxy servers, and (2) adjusts the fidelity of mobile applications as resources diminish. We formulate a cooperative reconfiguration plan which determines when, where, and which components should be deployed and have their fidelity controlled, so as to minimize the power consumption of mobile devices and to utilize the system resources of servers efficiently. We then construct a graph-theoretic model of the cost of migrating components to one proxy server or to a cluster of servers. In this model, changes to the residual energy of mobile devices, available server resources, and the wireless network bandwidth can all accelerate or decelerate the migration and fidelity control of applications. We suggest an approximation algorithm that achieves a near-optimal solution in terms of energy consumption. Our proposal will support mobile applications which require large amount of computation and need to maintain their services for an extended time such as video conferencing, multimedia e-mail, and real-time navigation. Simulation-based experiments verify that our scheme is an efficient way to extend the battery life of mobile devices and to improve the response time of mobile applications.
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.
The concept of grid computing emerged with the appearance of high-speed network. Effective grid worker (i.e., computing resource) selection mechanism is important to achieve reliable grid computing system since each worker participate in grid computing is heterogeneous. In this paper, we suggest a credible worker selection mechanism that maximizes grid computing performance by allocating appropriate tasks to each grid worker. Diverse workers can be used efficiently by grid applications through the ranking process of worker's credibility. Initially, the rank of each grid worker's credibility is decided considering static information only such as CPU speed, RAM size, storage capacity and network bandwidth. And then, the rank is refined by using dynamic information such as failure rate, turn around time provided after the task is completed, and correctness of the return value. In the experiments, we find that the proposed mechanism provides improved grid computing performance with high credibility.
Feng HONG Minglu LI Minyou WU Jiadi YU
Routing efficiency is the critical issue when constructing peer-to-peer overlay. However, Chord has often been criticized on its careless of routing locality. A routing efficiency enhancement protocol on top of Chord is illustrated in this paper, which is called PChord. PChord aims to achieve better routing efficiency than Chord by exploiting proximity of the underlying network topology. The simulation shows that PChord has achieved lower RDP per message routing.
Jyh Perng FANG Yang-Shan TONG Sao Jie CHEN
In the floorplan design of System-on-Chip (SOC), Buffer Site Approach (BSA) has been used to relax the buffer congestion problem. However, for a floorplan with dominant wide bus, BSA may instead worsen the congestion. Our proposed Enhanced Buffer Site Approach (EBSA) extends existing BSA in a way that buffers of dominant wide bus can be distributed more evenly while reserving the same fast operation speed as BSA does. Experiments have been performed to integrate our model into an iterative floorplanning algorithm, and the results reveal that buffer congestion in a floorplan with dominant wide bus can be much abated.