Antoine BOSSARD Keiichi KANEKO
Extending the very popular tori interconnection networks[1]-[3], Torus-Connected Cycles (TCC) have been proposed as a novel network topology for massively parallel systems [5]. Here, the set-to-set disjoint paths routing problem in a TCC is solved. In a TCC(k,n), it is proved that paths of lengths at most kn2+2n can be selected in O(kn2) time.
Hirotaka HAYASHI Tomoaki OHTSUKI
Recently, Doppler radars have been used in various applications from the detection and the classification of indoor human activities to the detection of airplanes. To improve both the degrees of freedom (DOF) and the estimation accuracy of the direction-of-arrival (DOA) of targets, multiple-input multiple-output (MIMO) radar has received much attention in recent years. The temporal spatial virtual array based on Doppler shift of a moving target has been one of methods to improve DOA estimation accuracy. However, the DOA estimation accuracy based on the method depends on the velocity and the direction of the target on which we focus. Also, the temporal spatial virtual array should be generated based on the information of the single target. Thus, it is difficult to implement the method if there are multiple targets. In this paper, we propose a new method that provides high accuracy of DOA estimation by using the temporal spatial virtual array without dependence on the velocity, the direction and the number of existing targets. We demonstrate the DOA estimation accuracy and the effectiveness of the proposed method via simulations.
Toshifumi NISHINAGA Masahiro MAMBO
By the deployment of Internet of Things, embedded systems using microcontroller are nowadays under threats through the network and incorporating security measure to the systems is highly required. Unfortunately, microcontrollers are not so powerful enough to execute standard security programs and need light-weight, high-speed and secure cryptographic libraries. In this paper, we port NaCl cryptographic library to ARM Cortex-M0(M0+) Microcontroller, where we put much effort in fast and secure implementation. Through the evaluation we show that the implementation achieves about 3 times faster than AVR NaCl result and reduce half of the code size.
As semiconductor technologies have advanced, the reliability problem caused by soft-errors is becoming one of the serious issues in LSIs. Moreover, multiple component errors due to single soft-errors also have become a serious problem. In this paper, we propose a method to synthesize multiple component soft-error tolerant application-specific datapaths via high-level synthesis. The novel feature of our method is speculative resource sharing between the retry parts and the secondary parts for time overhead mitigation. A scheduling algorithm using a special priority function to maximize speculative resource sharing is also an important feature of this study. Our approach can reduce the latency (schedule length) in many applications without deterioration of reliability and chip area compared with conventional datapaths without speculative resource sharing. We also found that our method is more effective when a computation algorithm possesses higher parallelism and a smaller number of resources is available.
GuangFu LI Hsien-Shun WU Ching-Kuang C. TZUANG
An asymmetric left-handed coupled-line is presented to implement the tight forward coupler. Two left-handed transmission lines are coupled through its shunt inductors. The numerical procedures based on the generalized four-port scattering parameters combined with the periodical boundary conditions are applied to extract the modal characteristics of the asymmetric coupled-line, and theoretically predict that the proposed coupled-line can make a normalized phase constant of c mode 1.57 times larger than π mode for the forward coupler miniaturization. The design curves based on different overlapping length of the shunt inductors are reported for the coupler design. The procedures, so-called the port-reduction-method (PRM), are applied to experimentally characterize the coupler prototype using the two-port instruments. The measured results confirm that prototype uses 0.21 λg at 430 GHz to achieve -4.55 dB forward coupling with 13% 1-dB operating bandwidth.
Yan CHEN Yu ZHANG Guanghui ZHANG Xunwang ZHAO ShaoHua WU Qing ZHANG XiaoPeng YANG
In this paper, a Many Integrated Core Architecture (MIC) accelerated parallel method of moment (MoM) algorithm is proposed to solve electromagnetic problems in practical applications, where MIC means a kind of coprocessor or accelerator in computer systems which is used to accelerate the computation performed by Central Processing Unit (CPU). Three critical points are introduced in this paper in detail. The first one is the design of the parallel framework, which ensures that the algorithm can run on distributed memory platform with multiple nodes. The hybrid Message Passing Interface (MPI) and Open Multi-Processing (OpenMP) programming model is designed to achieve the purposes. The second one is the out-of-core algorithm, which greatly breaks the restriction of MIC memory. The third one is the pipeline algorithm which overlaps the data movement with MIC computation. The pipeline algorithm successfully hides the communication and thus greatly enhances the performance of hybrid MIC/CPU MoM. Numerical result indicates that the proposed algorithm has good parallel efficiency and scalability, and twice faster performance when compared with the corresponding CPU algorithm.
Let G be a probabilistic graph, in which the vertices fail independently with known probabilities. Let K represent a specified subset of vertices. The K-terminal reliability of G is defined as the probability that all vertices in K are connected. When |K|=2, the K-terminal reliability is called the 2-terminal reliability, which is the probability that the source vertex is connected to the destination vertex. The problems of computing K-terminal reliability and 2-terminal reliability have been proven to be #P-complete in general. This work demonstrates that on multi-tolerance graphs, the 2-terminal reliability problem can be solved in polynomial-time and the results can be extended to the K-terminal reliability problem on bounded multi-tolerance graphs.
In this paper, a convolution theorem which is analogous to the theorem for Fourier transform is shown among a certain type of polynomials. We establish a fast method of the multiplication in a special class of quotient rings of multivariate polynomials over q-element finite field GF(q). The polynomial which we treat is one of expressing forms of the multiple-valued logic function from the product of the semigroups in GF(q) to GF(q). Our results can be applied to the speedup of both software and hardware concerning multiple-valued Boolean logic.
Sasinee PRUEKPRASERT Toshimitsu USHIO
This paper considers an optimal stabilization problem of quantitative discrete event systems (DESs) under the influence of disturbances. We model a DES by a deterministic weighted automaton. The control cost is concerned with the sum of the weights along the generated trajectories reaching the target state. The region of weak attraction is the set of states of the system such that all trajectories starting from them can be controlled to reach a specified set of target states and stay there indefinitely. An optimal stabilizing controller is a controller that drives the states in this region to the set of target states with minimum control cost and keeps them there. We consider two control objectives: to minimize the worst-case control cost (1) subject to all enabled trajectories and (2) subject to the enabled trajectories starting by controllable events. Moreover, we consider the disturbances which are uncontrollable events that rarely occur in the real system but may degrade the control performance when they occur. We propose a linearithmic time algorithm for the synthesis of an optimal stabilizing controller which is robust to disturbances.
Yali LI Hongma LIU Shengjin WANG
A brain-computer interface (BCI) translates the brain activity into commands to control external devices. P300 speller based character recognition is an important kind of application system in BCI. In this paper, we propose a framework to integrate channel correlation analysis into P300 detection. This work is distinguished by two key contributions. First, a coefficient matrix is introduced and constructed for multiple channels with the elements indicating channel correlations. Agglomerative clustering is applied to group correlated channels. Second, the statistics of central tendency are used to fuse the information of correlated channels and generate virtual channels. The generated virtual channels can extend the EEG signals and lift up the signal-to-noise ratio. The correlated features from virtual channels are combined with original signals for classification and the outputs of discriminative classifier are used to determine the characters for spelling. Experimental results prove the effectiveness and efficiency of the channel correlation analysis based framework. Compared with the state-of-the-art, the recognition rate was increased by both 6% with 5 and 10 epochs by the proposed framework.
Yoshitaka OTANI Osamu AOKI Tomohiro HIROTA Hiroshi ANDO
The purpose of this study is to make available a fall risk assessment for stroke patients during walking using an accelerometer. We assessed gait parameters, normalized root mean squared acceleration (NRMSA) and berg balance scale (BBS) values. Walking dynamics were better reflected in terms of the risk of falls during walking by NRMSA compared to the BBS.
Jungnam BAE Saichandrateja RADHAPURAM Ikkyun JO Weimin WANG Takao KIHARA Toshimasa MATSUOKA
A low-voltage controller-based all-digital phase-locked loop (ADPLL) utilized in the medical implant communication service (MICS) frequency band was designed in this study. In the proposed design, controller-based loop topology is used to control the phase and frequency to ensure the reliable handling of the ADPLL output signal. A digitally-controlled oscillator with a delta-sigma modulator was employed to achieve high frequency resolution. The phase error was reduced by a phase selector with a 64-phase signal from the phase interpolator. Fabricated using a 130-nm CMOS process, the ADPLL has an active area of 0.64 mm2, consumes 840 µW from a 0.7-V supply voltage, and has a settling time of 80 µs. The phase noise was measured to be -114 dBc/Hz at an offset frequency of 200 kHz.
Carlos PEREZ-LEGUIZAMO P. Josue HERNANDEZ-TORRES J.S. Guadalupe GODINEZ-BORJA Victor TAPIA-TEC
Recently, the Services Oriented Architectures (SOA) have been recognized as the key to the integration and interoperability of different applications and systems that coexist in an organization. However, even though the use of SOA has increased, some applications are unable to use it. That is the case of mission critical information applications, whose requirements such as high reliability, non-stop operation, high flexibility and high performance are not satisfied by conventional SOA infrastructures. In this article we present a novel approach of combining SOA with Autonomous Decentralized Systems (ADS) in order to provide an infrastructure that can satisfy those requirements. We have named this infrastructure Autonomous Decentralized Service Oriented Architecture (ADSOA). We present the concept and architecture of ADSOA, as well as the Loosely Couple Delivery Transaction and Synchronization Technology for assuring the data consistency and high reliability of the application. Moreover, a real implementation and evaluation of the proposal in a mission critical information system, the Uniqueness Verifying Public Key Infrastructure (UV-PKI), is shown in order to prove its effectiveness.
Bumsoon JANG Seokjoo DOO Soojin LEE Hyunsoo YOON
Due to the periodic recovery of virtual machines regardless of whether malicious intrusions exist, proactive recovery-based Intrusion Tolerant Systems (ITSs) are being considered for mission-critical applications. However, the virtual replicas can easily be exposed to attacks during their working period, and additionally, proactive recovery-based ITSs are ineffective in eliminating the vulnerability of exposure time, which is closely related to service availability. To address these problems, we propose a novel hybrid recovery-based ITS in this paper. The proposed method utilizes availability-driven recovery and dynamic cluster resizing. The availability-driven recovery method operates the recovery process by both proactive and reactive ways for the system to gain shorter exposure times and higher success rates. The dynamic cluster resizing method reduces the overhead of the system that occurs from dynamic workload fluctuations. The performance of the proposed ITS with various synthetic and real workloads using CloudSim showed that it guarantees higher availability and reliability of the system, even under malicious intrusions such as DDoS attacks.
Yuya TARUTANI Yuichi OHSITA Masayuki MURATA
Cloud storage has become popular and is being used to hold important data. As a result, availability to become important; cloud storage providers should allow users to upload or download data even if some part of the system has failed. In this paper, we discuss distributed cloud storage that is robust against failures. In distributed cloud storage, multiple replicas of each data chunk are stored in the virtual storage at geographically different locations. Thus, even if one of the virtual storage systems becomes unavailable, users can access the data chunk from another virtual storage system. In distributed cloud storage, the placement of the virtual storage system is important; if the placement of the virtual cloud storage system means that a large number of virtual storages are possible could become unavailable from a failure, a large number of replicas of each data chunk should be prepared to maintain availability. In this paper, we propose a virtual storage placement method that assures availability with a small number of replicas. We evaluated our method by comparing it with three other methods. The evaluation shows that our method can maintain availability while requiring only with 60% of the network costs required by the compared methods.
Yefang CHEN Zhipeng HUANG Pei CAO Ming JIN Chengtou DU Jiangbo QIAN
Some networks, such as wireless sensor networks, vehicle networks, etc., are often disconnected and thus fail to provide an end-to-end route for transmission. As a result, a new kind self-organized wireless network, i.e., Delay Tolerant Network (DTN) is proposed to transmit messages using a store-carry-forward method. To efficiently process aggregation queries, this paper proposes a subscription aggregation query processing method that combines query processing and transfer protocols. The basic idea is reducing the number of redundant copy transmissions, increasing the message delivery rate and reducing the transmission delay by matrix summation. Theoretical and experimental results show that the method can attain a good performance in the delay tolerant networks.
Kimihiro MIZUTANI Takeru INOUE Toru MANO Osamu AKASHI Satoshi MATSUURA Kazutoshi FUJIKAWA
The routing efficiency of structured overlay networks depends on the consistency of pointers between nodes, where a pointer maps a node identifier to the corresponding address. This consistency can, however, break temporarily when some overlay nodes fail, since it takes time to repair the broken pointers in a distributed manner. Conventional solutions utilize “backpointers” to quickly discover any failure among the pointing nodes, which allow them to fix the pointers in a short time. Overlay nodes are, however, required to maintain backpointers for every pointing node, which incurs significant memory and consistency check overhead. This paper proposes a novel light-weight protocol; an overlay node gives a “living will” containing its acquaintances (backpointers) only to its successor, thus other nodes are freed from the need to maintain it. Our carefully-designed protocol guarantees that all acquaintances are registered via the living will, even in the presence of churn, and the successor notifies the acquaintances for the deceased. Even if the successor passes away and the living will is lost, the successor to the successor can identify the acquaintances with a high success ratio. Simulations show that our protocol greatly reduces memory overhead as well as the detection time for node failure with the cost being a slight increase in messaging load.
Kiyotaka YAMAMURA Suguru ISHIGURO Hiroshi TAKI
This paper presents efficient and easily implementable methods for the characteristic analysis and tolerance analysis of nonlinear resistive circuits using integer programming. In these methods, the problem of finding all characteristic curves or all solution sets (regions of possible operating points) is formulated as a mixed integer programming problem, and it is solved by a high-performance integer programming solver such as CPLEX. It is shown that the proposed methods can easily be implemented without making complicated programs, and that all characteristic curves or all solution sets are obtained by solving mixed integer programming problems several times. Numerical examples are given to confirm the effectiveness of the proposed methods.
Dexiu HU Zhen HUANG Xi CHEN Jianhua LU
This paper proposes a moving source localization method that combines TDOA, FDOA and doppler rate measurements. First, the observation equations are linearized by introducing nuisance variables and an initial solution of all the variables is acquired using the weighted least squares method. Then, the Taylor expression and gradient method is applied to eliminate the correlation between the elements in the initial solution and obtain the final estimation of the source position and velocity. The proposed method achieves CRLB derived using TDOA, FDOA and doppler rate and is much more accurate than the conventional TDOA/FDOA based method. In addition, it can avoid the rank-deficiency problem and is more robust than the conventional method. Simulations are conducted to examine the algorithm's performance and compare it with conventional TDOA/FDOA based method.
Cong LIU Jiujun CHENG Yirui WANG Shangce GAO
Time performance optimization and resource conflict resolution are two important challenges in multiple project management contexts. Compared with traditional project management, multi-project management usually suffers limited and insufficient resources, and a tight and urgent deadline to finish all concurrent projects. In this case, time performance optimization of the global project management is badly needed. To our best knowledge, existing work seldom pays attention to the formal modeling and analyzing of multi-project management in an effort to eliminate resource conflicts and optimizing the project execution time. This work proposes such a method based on PRT-Net, which is a Petri net-based formulism tailored for a kind of project constrained by resource and time. The detailed modeling approaches based on PRT-Net are first presented. Then, resource conflict detection method with corresponding algorithm is proposed. Next, the priority criteria including a key-activity priority strategy and a waiting-short priority strategy are presented to resolve resource conflicts. Finally, we show how to construct a conflict-free PRT-Net by designing resource conflict resolution controllers. By experiments, we prove that our proposed priority strategy can ensure the execution time of global multiple projects much shorter than those without using any strategies.