The Discrete Memory Machine (DMM) is a theoretical parallel computing model that captures the essence of the shared memory access of GPUs. Bank conflicts should be avoided for maximizing the bandwidth of the shared memory access. Offline permutation of an array is a task to copy all elements in array a into array b along a permutation given in advance. The main contribution of this paper is to implement a conflict-free permutation algorithm on the DMM in a GPU. We have also implemented straightforward permutation algorithms on the GPU. The experimental results for 1024 double (64-bit) numbers on NVIDIA GeForce GTX-680 show that the straightforward permutation algorithm takes 247.8 ns for the random permutation and 1684ns for the worst permutation that involves the maximum bank conflicts. Our conflict-free permutation algorithm runs in 167ns for any permutation including the random permutation and the worst permutation, although it performs more memory accesses. It follows that our conflict-free permutation is 1.48 times faster for the random permutation and 10.0 times faster for the worst permutation.

The main contribution of this paper is to show optimal parallel algorithms to compute the sum, the prefix-sums, and the summed area table on two memory machine models, the Discrete Memory Machine (DMM) and the Unified Memory Machine (UMM). The DMM and the UMM are theoretical parallel computing models that capture the essence of the shared memory and the global memory of GPUs. These models have three parameters, the number p of threads, and the width w of the memory, and the memory access latency l. We first show that the sum of n numbers can be computed in $O({nover w}+{nlover p}+llog n)$ time units on the DMM and the UMM. We then go on to show that $Omega({nover w}+{nlover p}+llog n)$ time units are necessary to compute the sum. We also present a parallel algorithm that computes the prefix-sums of n numbers in $O({nover w}+{nlover p}+llog n)$ time units on the DMM and the UMM. Finally, we show that the summed area table of size $sqrt{n} imessqrt{n}$ can be computed in $O({nover w}+{nlover p}+llog n)$ time units on the DMM and the UMM. Since the computation of the prefix-sums and the summed area table is at least as hard as the sum computation, these parallel algorithms are also optimal.

Aiming to alleviate the visual tracking problem of drift which reduces the abilities of almost all online visual trackers, a robust visual tracker (called CCMM tracker) is proposed with a coupled-classifier based on multiple representative appearance models. The coupled-classifier consists of root and head classifiers based on local sparse representation. The two classifiers collaborate to fulfil a tracking task within the Bayesian-based tracking framework, also to update their templates with a novel mechanism which tries to guarantee an update operation along the “right” orientation. Consequently, the tracker is more powerful in anti-interference. Meanwhile the multiple representative appearance models maintain features of the different submanifolds of the target appearance, which the target exhibited previously. The multiple models cooperatively support the coupled-classifier to recognize the target in challenging cases (such as persistent disturbance, vast change of appearance, and recovery from occlusion) with an effective strategy. The novel tracker proposed in this paper, by explicit inference, can reduce drift and handle frequent and drastic appearance variation of the target with cluttered background, which is demonstrated by the extensive experiments.

3D display systems without glasses are preferred because of the inconvenience wearing of special glasses while viewing 3D content. In general, non-glass type 3D displays work by sending left and right views of the content to the corresponding eyes depending on the user position with respect to the display. Since accurate user position estimation has become a very important task for non-glass type 3D displays, most of such systems require additional hardware or suffer from low accuracy. In this paper, an accurate user position estimation method using a single camera for non-glass type 3D display is proposed. As inter-pupillary distance is utilized for the estimation, at first the face is detected and then tracked using an Active Appearance Model. The pose of face is then estimated to compensate the pose variations. To estimate the user position, a simple perspective mapping function is applied which uses the average of the inter-pupillary distance. For accuracy, personal inter-pupillary distance can also be used. Experimental results have shown that the proposed method successfully estimated the user position using a single camera. The average error for position estimation with the proposed method was small enough for viewing 3D contents.

Recently, probabilistic topic models have been applied to various types of data, including text, and their effectiveness has been demonstrated. Latent Dirichlet allocation (LDA) is a well known topic model. Variational Bayesian inference or collapsed Gibbs sampling is often used to estimate parameters in LDA; however, these inference methods incur high computational cost for large-scale data. Therefore, highly efficient technology is needed for this purpose. We use parallel computation technology for efficient collapsed Gibbs sampling inference for LDA. We assume a symmetric multiprocessing (SMP) cluster, which has been widely used in recent years. In prior work on parallel inference for LDA, either MPI or OpenMP has often been used alone. For an SMP cluster, however, it is more suitable to adopt hybrid parallelization that uses message passing for communication between SMP nodes and loop directives for parallelization within each SMP node. We developed an MPI/OpenMP hybrid parallel inference method for LDA, and evaluated the performance of the inference under various settings of an SMP cluster. We further investigated the approximation that controls the inter-node communications, and found out that it achieved noticeable increase in inference speed while maintaining inference accuracy.

A wireless node is called isolated if it has no links to other nodes. The number of isolated nodes in a wireless network is an important connectivity index. However, most previous works on analytically determining the number of isolated nodes were not based on practical channel models. In this work, we study this problem using a generic probabilistic channel model that can capture the behaviors of the most widely used channel models, including the disk graph model, the Bernoulli link model, the Gaussian white noise model, the Rayleigh fading model, and the Nakagami fading model. We derive the expected number of isolated nodes and further prove that their distribution asymptotically follows a Poisson distribution. We also conjecture that the nonexistence of isolated nodes asymptotically implies the connectivity of the network, and that the probability of connectivity follows the Gumbel function.

Reinforcement learning (RL) is a flexible framework for learning a decision rule in an unknown environment. However, a large number of samples are often required for finding a useful decision rule. To mitigate this problem, the concept of transfer learning has been employed to utilize knowledge obtained from similar RL tasks. However, most approaches developed so far are useful only in low-dimensional settings. In this paper, we propose a novel transfer learning idea that targets problems with high-dimensional states. Our idea is to transfer knowledge between state factors (e.g., interacting objects) within a single RL task. This allows the agent to learn the system dynamics of the target RL task with fewer data samples. The effectiveness of the proposed method is demonstrated through experiments.

There exists a considerable number of node placement models and algorithms for simulation of wireless multihop networks. However, the topologies created with the existing algorithms do not have properties of real networks. We have developed NPART (Node Placement Algorithm for Realistic Topologies) in order to resolve this fundamental issue in simulation methodology. We compare topologies generated by NPART with open wireless multihop network in Berlin. The NPART generated topologies have almost identical node degree distribution, number of cut-edges and vertices as the real network. Unlike them, topologies generated with the common node placement models have their own characteristics which are considerably different both from NPART and from reality. NPART algorithm has been developed into a tool. We propose a method and present a tool for integration of NPART with various realistic node mobility algorithms and tools, such as Citymob [1] and MOVE [2]. This integrated tool allows easy and time-efficient generation of highly complex, realistic simulation scenarios. We use the tool to evaluate effects of integration between existing open community wireless multi-hop networks and vehicular ad-hoc networks (VANETs). The evaluation shows that despite partial coverage and peculiar topological properties of open networks, they offer high levels of performance and network availability to the mobile end users, virtually identical to performance and availability of planned, dedicatedly deployed networks. Our results indicate that the integration of these networks may bring considerable benefits to all parties involved.

This paper proposes a new generative model which can deal with rotational data variations by extending Separable Lattice 2-D HMMs (SL2D-HMMs). In image recognition, geometrical variations such as size, location and rotation degrade the performance. Therefore, the appropriate normalization processes for such variations are required. SL2D-HMMs can perform an elastic matching in both horizontal and vertical directions; this makes it possible to model invariance to size and location. To deal with rotational variations, we introduce additional HMM states which represent the shifts of the state alignments among the observation lines in a particular direction. Face recognition experiments show that the proposed method improves the performance significantly for rotational variation data.

The performance of English automatic speech recognition systems decreases when recognizing spontaneous speech mainly due to multiple pronunciation variants in the utterances. Previous approaches address this problem by modeling the alteration of the pronunciation on a phoneme to phoneme level. However, the phonetic transformation effects induced by the pronunciation of the whole sentence have not yet been considered. In this article, the sequence-based pronunciation variation is modeled using a noisy channel approach where the spontaneous phoneme sequence is considered as a “noisy” string and the goal is to recover the “clean” string of the word sequence. Hereby, the whole word sequence and its effect on the alternation of the phonemes will be taken into consideration. Moreover, the system not only learns the phoneme transformation but also the mapping from the phoneme to the word directly. In this study, first the phonemes will be recognized with the present recognition system and afterwards the pronunciation variation model based on the noisy channel approach will map from the phoneme to the word level. Two well-known natural language processing approaches are adopted and derived from the noisy channel model theory: Joint-sequence models and statistical machine translation. Both of them are applied and various experiments are conducted using microphone and telephone of spontaneous speech.

Small-world is a common property existing in many real-life social, technological and biological networks. Small-world networks distinguish themselves from others by their high clustering coefficient and short average path length. In the past dozen years, many probabilistic small-world networks and some deterministic small-world networks have been proposed utilizing various mechanisms. In this Letter, we propose a new deterministic small-world network model by first constructing a binary-tree structure and then adding links between each pair of brother nodes and links between each grandfather node and its four grandson nodes. Furthermore, we give the analytic solutions to several topological characteristics, which shows that the proposed model is a small-world network.

Given a collection of k sets consisting of a total of n points in the plane, the distance from any point in the plane to each of the sets is defined to be the minimum among distances to each point in the set. The farthest-color Voronoi diagram is defined as a generalized Voronoi diagram of the k sets with respect to the distance functions for each of the k sets. The combinatorial complexity of the diagram is known to be Θ(kn) in the worst case. This paper initiates a study on farthest-color Voronoi diagrams having O(n) complexity. We introduce a realistic model, which defines a certain class of the diagrams with desirable geometric properties observed. We finally show that the farthest-color Voronoi diagrams under the model have linear complexity.

Variations in walking speed have a strong impact on gait-based person identification. We propose a method that is robust against walking-speed variations. It is based on a combination of cubic higher-order local auto-correlation (CHLAC), gait silhouette-based principal component analysis (GSP), and a statistical framework using hidden Markov models (HMMs). The CHLAC features capture the within-phase spatio-temporal characteristics of each individual, the GSP features retain more shape/phase information for better gait sequence alignment, and the HMMs classify the ID of each gait even when walking speed changes nonlinearly. We compared the performance of our method with other conventional methods using five different databases, SOTON, USF-NIST, CMU-MoBo, TokyoTech A and TokyoTech B. The proposed method was equal to or better than the others when the speed did not change greatly, and it was significantly better when the speed varied across and within a gait sequence.

This study focused on three simplified models, namely (1) one set of single-phase DC-DC converter, (2) two sets of parallel connection single-phase DC-DC converter, and (3) two sets of series connection single-phase DC-DC converter. The purposes are: (1) to propose the simplification conditions and procedures for the three-phase AC-DC converter; (2) propose a set of new simplification steps for modeling, and present the examples of different three-phase AC-DC circuit topologies, detailed discussion on the simplification steps for modeling of a three-phase AC-DC converter is offered, to help people simplify and analyze the simplified model easily; (3) according to three types of simplified modeling in the three-phase AC-DC converter, this study established a useful reference for the design and analysis of the control systems of the three-phase AC-DC converter simply; (4) to acquire PWM control strategy beforehand based on PFC-Controlled property; (5) to reduce the switching loss for the PWM control strategy of the simplified model; (6) to maintain the original circuit topology and verify that the theory can extensively apply the knowledge of single-phase DC-DC converter to the simplified modeling of three-phase AC-DC converter.

This paper deals with underwater target classification using synthesized active sonar signals. Firstly, we synthesized active sonar returns from a 3D highlight model of underwater targets using the ray tracing algorithm. Then, we applied a multiaspect target classification scheme based on a hidden Markov model to classify them. For feature extraction from the synthesized sonar signals, a matching pursuit algorithm was used. The experimental results depending on the number of observations and signal-to-noise ratios are presented with our discussions.

This paper investigates the relationship between averaged SAR (Specific Absorption Rate) over 10 g mass and temperature elevation in Japanese numerical anatomical models when devices are mounted on the body. Simplifying the radiation source as a half-wavelength dipole, the generated electrical field and SAR are calculated using the FDTD (Finite-Difference Time-Domain) method. Then the bio-heat equation is solved to obtain the temperature elevation due to the SAR derived using the FDTD method as heat source. Frequencies used in the study are 900 MHz and 1950 MHz, which are used for mobile phones. In addition, 3500 MHz is considered because this frequency is reserved for IMT-Advanced (International Mobile Telecommunication-Advanced System). Computational results obtained herein show that the 10 g-average SAR and the temperature elevation are not proportional to frequency. In addition, it is clear that those at 3500 MHz are lower than that at 1950 MHz even though the frequency is higher. It is the point to be stressed here is that good correlation between the 10 g-average SAR and the temperature elevation is observed even for the body-worn device.

Due to the superlinear dependence of leakage power consumption on temperature, and spatial variations in on-chip thermal profiles, methods of leakage power estimation that are known to be accurate require detailed knowledge of thermal profiles. Leakage power depends on the integrated circuit (IC) thermal profile and circuit design style. Here, we show that piecewise linear models can be used to permit accurate leakage estimation over the operating temperature ranges of the ICs. We then show that for typical IC packages and cooling structures, a given amount of heat introduced at any position in the active layer will have a similar impact on the average temperature of the layer. These two observations support the proof that, for wide ranges of design styles and operating temperatures, extremely fast, coarse-grained thermal models, combined with piecewise linear leakage power consumption models, enable the estimation of chip-wide leakage power consumption. These results are further confirmed through comparisons with leakage estimates based on detailed, time-consuming thermal analysis techniques. Experimental results indicate that, when compared with a leakage analysis technique that relies on accurate spatial temperature estimation, the proposed technique yields a 59,259 to 1,790,000 speedup in estimating leakage power consumption, while maintaining accuracy.

The software reliability is the ability of the software to perform its required function under stated conditions for a stated period of time. In this paper, a hybrid methodology that combines both ARIMA and fractal models is proposed to take advantage of unique strength of ARIMA and fractal in linear and nonlinear modeling. Based on the experiments performed on the software reliability data obtained from literatures, it is observed that our method is effective through comparison with other methods and a new idea for the research of the software failure mechanism is presented.

Statistical speech recognition using continuous-density hidden Markov models (CDHMMs) has yielded many practical applications. However, in general, mismatches between the training data and input data significantly degrade recognition accuracy. Various acoustic model adaptation techniques using a few input utterances have been employed to overcome this problem. In this article, we survey these adaptation techniques, including maximum a posteriori (MAP) estimation, maximum likelihood linear regression (MLLR), and eigenvoice. We also present a schematic view called the adaptation pyramid to illustrate how these methods relate to each other.

Correlation power analysis (CPA) is a well-known attack against cryptographic modules with which an attacker evaluates the correlation between the power consumption and the sensitive data candidates calculated from a guessed sub-key and known data such as plaintexts and ciphertexts. This paper enhances CPA to propose a new general power analysis, built-in determined sub-key CPA (BS-CPA), which finds a new sub-key by using the previously determined sub-keys recursively to compute the sensitive data candidates and to increase the signal-to-noise ratio in its analysis. BS-CPA also reuses the power traces in the repetitions of finding sub-keys to decrease the total number of the required traces for determining the all sub-keys. BS-CPA is powerful and effective when the multiple sensitive data blocks such as sbox outputs are processed simultaneously as in the hardware implementation. We apply BS-CPA to the power traces provided at the DPA contest and succeed in finding a DES key using fewer traces than the original CPA does.