OpenRaiser/Intern-Atlas huggingface dataset:
Dynamic Warp Resizing in High-Performance SIMT
Venue: arXiv cs.AR 2012
Year: 2012

Modern GPUs synchronize threads grouped in a warp at every instruction. These results in improving SIMD efficiency and makes sharing fetch and decode resources possible. The number of threads included in each warp (or warp size) affects divergence, synchronization overhead and the efficiency of memory access coalescing. Small warps reduce the performance penalty associated with branch and memory divergence at the expense of a reduction in memory coalescing. Large warps enhance memory coalescing significantly but also increase branch and memory divergence. Dynamic workload behavior, including branch/memory divergence and coalescing, is an important factor in determining the warp size returning best performance. Optimal warp size can vary from one workload to another or from one program phase to the next. Based on this observation, we propose Dynamic Warp Resizing (DWR). DWR takes innovative microarchitectural steps to adjust warp size during runtime and according to program characteristics. DWR outperforms static warp size decisions, up to 1.7X to 2.28X, while imposing less than 1% area overhead. We investigate various alternative configurations and show that DWR performs better for narrower SIMD and larger caches.
Analytical Survey of Wearable Sensors
Venue: arXiv cs.SY 2012
Year: 2012

Wearable sensors inWireless Body Area Networks (WBANs) provide health and physical activity monitoring. Modern communication systems have extended this monitoring remotely. In this survey, various types of wearable sensors discussed, their medical applications like ECG, EEG, blood pressure, detection of blood glucose level, pulse rate, respiration rate and non medical applications like daily exercise monitoring and motion detection of different body parts. Different types of noise removing filters also discussed at the end that are helpful in to remove noise from ECG signals. Main purpose of this survey is to provide a platform for researchers in wearable sensors for WBANs.
Performance Analysis of Protograph-based LDPC Codes with Spatial Diversity
Venue: arXiv cs.IT 2012
Year: 2012

In wireless communications, spatial diversity techniques, such as space-time block code (STBC) and single-input multiple-output (SIMO), are employed to strengthen the robustness of the transmitted signal against channel fading. This paper studies the performance of protograph-based low-density parity-check (LDPC) codes with receive antenna diversity. We first propose a modified version of the protograph extrinsic information transfer (PEXIT) algorithm and use it for deriving the threshold of the protograph codes in a single-input multiple-output (SIMO) system. We then calculate the decoding threshold and simulate the bit error rate (BER) of two protograph codes (accumulate-repeat-by-3-accumulate (AR3A) code and accumulate-repeat-by-4-jagged-accumulate (AR4JA) code), a regular (3, 6) LDPC code and two optimized irregular LDPC codes. The results reveal that the irregular codes achieve the best error performance in the low signal-to-noise-ratio (SNR) region and the AR3A code outperforms all other codes in the high-SNR region. Utilizing the theoretical analyses and the simulated results, we further discuss the effect of the diversity order on the performance of the protograph codes. Accordingly, the AR3A code stands out as a good candidate for wireless communication systems with multiple receive antennas.
LU factorization with panel rank revealing pivoting and its communication avoiding version
Venue: arXiv cs.NA 2012
Year: 2012

We present the LU decomposition with panel rank revealing pivoting (LU_PRRP), an LU factorization algorithm based on strong rank revealing QR panel factorization. LU_PRRP is more stable than Gaussian elimination with partial pivoting (GEPP). Our extensive numerical experiments show that the new factorization scheme is as numerically stable as GEPP in practice, but it is more resistant to pathological cases and easily solves the Wilkinson matrix and the Foster matrix. We also present CALU_PRRP, a communication avoiding version of LU_PRRP that minimizes communication. CALU_PRRP is based on tournament pivoting, with the selection of the pivots at each step of the tournament being performed via strong rank revealing QR factorization. CALU_PRRP is more stable than CALU, the communication avoiding version of GEPP. CALU_PRRP is also more stable in practice and is resistant to pathological cases on which GEPP and CALU fail.
Decision Taking for Selling Thread Startup
Venue: arXiv cs.SE 2012
Year: 2012

Decision Taking is discussed in the context of the role it may play for a selling agent in a search market, in particular for agents involved in the sale of valuable and relatively unique items, such as a dwelling, a second hand car, or a second hand recreational vessel. Detailed connections are made between the architecture of decision making processes and a sample of software technology based concepts including instruction sequences, multi-threading, and thread algebra. Ample attention is paid to the initialization or startup of a thread dedicated to achieving a given objective, and to corresponding decision taking. As an application, the selling of an item is taken as an objective to be achieved by running a thread that was designed for that purpose.
Distributed Pareto Optimization via Diffusion Strategies
Venue: arXiv cs.MA 2012
Year: 2012

We consider solving multi-objective optimization problems in a distributed manner by a network of cooperating and learning agents. The problem is equivalent to optimizing a global cost that is the sum of individual components. The optimizers of the individual components do not necessarily coincide and the network therefore needs to seek Pareto optimal solutions. We develop a distributed solution that relies on a general class of adaptive diffusion strategies. We show how the diffusion process can be represented as the cascade composition of three operators: two combination operators and a gradient descent operator. Using the Banach fixed-point theorem, we establish the existence of a unique fixed point for the composite cascade. We then study how close each agent converges towards this fixed point, and also examine how close the Pareto solution is to the fixed point. We perform a detailed mean-square error analysis and establish that all agents are able to converge to the same Pareto optimal solution within a sufficiently small mean-square-error (MSE) bound even for constant step-sizes. We illustrate one application of the theory to collaborative decision making in finance by a network of agents.
The Generic Model of Computation
Venue: arXiv cs.LO 2012
Year: 2012

Over the past two decades, Yuri Gurevich and his colleagues have formulated axiomatic foundations for the notion of algorithm, be it classical, interactive, or parallel, and formalized them in the new generic framework of abstract state machines. This approach has recently been extended to suggest a formalization of the notion of effective computation over arbitrary countable domains. The central notions are summarized herein.
Stable Segmentation of Digital Image
Venue: arXiv cs.CV 2012
Year: 2012

In the paper the optimal image segmentation by means of piecewise constant approximations is considered. The optimality is defined by a minimum value of the total squared error or by equivalent value of standard deviation of the approximation from the image. The optimal approximations are defined independently on the method of their obtaining and might be generated in different algorithms. We investigate the computation of the optimal approximation on the grounds of stability with respect to a given set of modifications. To obtain the optimal approximation the Mumford-Shuh model is generalized and developed, which in the computational part is combined with the Otsu method in multi-thresholding version. The proposed solution is proved analytically and experimentally on the example of the standard image.
Unified Analysis of Transmit Antenna Selection/Space-Time Block Coding with Receive Selection and Combining over Nakagami-m Fading Channels in the Presence of Feedback Errors
Venue: arXiv cs.IT 2012
Year: 2012

Examining the effect of imperfect transmit antenna selection (TAS) caused by the feedback link errors on the performance of hybrid TAS/space-time block coding (STBC) with selection combining (SC) (i.e., joint transmit and receive antenna selection (TRAS)/STBC) and TAS/STBC (with receive maximal-ratio combining (MRC)-like combining structure) over Nakagami-m fading channels is the main objective of this paper. Under ideal channel estimation and delay-free feedback assumptions, statistical expressions and several performance metrics related to the post-processing signal-to-noise ratio (SNR) are derived for a unified system model concerning both joint TRAS/STBC and TAS/STBC schemes. Exact analytical expressions for outage probability and bit/symbol error rates (BER/SER) of binary and M-ary modulations are presented in order to provide an extensive examination on the capacity and error performance of the unified system that experiences feedback errors. Also, the asymptotic diversity order analysis, which shows that the diversity order of the investigated schemes is lower bounded by the diversity order provided by STBC transmission itself, is included in the paper. Moreover, all theoretical results are validated by performing Monte Carlo simulations.
Hide and New in the Pi-Calculus
Venue: arXiv cs.PL 2012
Year: 2012

In this paper, we enrich the pi-calculus with an operator for confidentiality (hide), whose main effect is to restrict the access to the object of the communication, thus representing confidentiality in a natural way. The hide operator is meant for local communication, and it differs from new in that it forbids the extrusion of the name and hence has a static scope. Consequently, a communication channel in the scope of a hide can be implemented as a dedicated channel, and it is more secure than one in the scope of a new. To emphasize the difference, we introduce a spy context that represents a side-channel attack and breaks some of the standard security equations for new. To formally reason on the security guarantees provided by the hide construct, we introduce an observational theory and establish stronger equivalences by relying on a proof technique based on bisimulation semantics.
Two-Way Finite Automata: Old and Recent Results
Venue: arXiv cs.FL 2012
Year: 2012

The notion of two-way automata was introduced at the very beginning of automata theory. In 1959, Rabin and Scott and, independently, Shepherdson, proved that these models, both in the deterministic and in the nondeterministic versions, have the same power of one-way automata, namely, they characterize the class of regular languages. In 1978, Sakoda and Sipser posed the question of the cost, in the number of the states, of the simulation of one-way and two-way nondeterministic automata by two-way deterministic automata. They conjectured that these costs are exponential. In spite of all attempts to solve it, this question is still open. In the last ten years the problem of Sakoda and Sipser was widely reconsidered and many new results related to it have been obtained. In this work we discuss some of them. In particular, we focus on the restriction to the unary case and on the connections with open questions in space complexity.
Local Rules for Computable Planar Tilings
Venue: arXiv cs.FL 2012
Year: 2012

Aperiodic tilings are non-periodic tilings characterized by local constraints. They play a key role in the proof of the undecidability of the domino problem (1964) and naturally model quasicrystals (discovered in 1982). A central question is to characterize, among a class of non-periodic tilings, the aperiodic ones. In this paper, we answer this question for the well-studied class of non-periodic tilings obtained by digitizing irrational vector spaces. Namely, we prove that such tilings are aperiodic if and only if the digitized vector spaces are computable.
Universality of One-Dimensional Reversible and Number-Conserving Cellular Automata
Venue: arXiv cs.FL 2012
Year: 2012

We study one-dimensional reversible and number-conserving cellular automata (RNCCA) that have both properties of reversibility and number-conservation. In the case of 2-neighbor RNCCA, García-Ramos proved that every RNCCA shows trivial behavior in the sense that all the signals in the RNCCA do not interact each other. However, if we increase the neighborhood size, we can find many complex RNCCAs. Here, we show that for any one-dimensional 2-neighbor reversible partitioned CA (RPCA) with s states, we can construct a 4-neighbor RNCCA with 4s states that simulates the former. Since it is known that there is a computationally universal 24-state 2-neighbor RPCA, we obtain a universal 96-state 4-neighbor RNCCA.
A Simple Optimum-Time FSSP Algorithm for Multi-Dimensional Cellular Automata
Venue: arXiv cs.FL 2012
Year: 2012

The firing squad synchronization problem (FSSP) on cellular automata has been studied extensively for more than forty years, and a rich variety of synchronization algorithms have been proposed for not only one-dimensional arrays but two-dimensional arrays. In the present paper, we propose a simple recursive-halving based optimum-time synchronization algorithm that can synchronize any rectangle arrays of size m*n with a general at one corner in m+n+max(m, n)-3 steps. The algorithm is a natural expansion of the well-known FSSP algorithm proposed by Balzer [1967], Gerken [1987], and Waksman [1966] and it can be easily expanded to three-dimensional arrays, even to multi-dimensional arrays with a general at any position of the array.
Phase Space Invertible Asynchronous Cellular Automata
Venue: arXiv cs.FL 2012
Year: 2012

While for synchronous deterministic cellular automata there is an accepted definition of reversibility, the situation is less clear for asynchronous cellular automata. We first discuss a few possibilities and then investigate what we call phase space invertible asynchronous cellular automata in more detail. We will show that for each Turing machine there is such a cellular automaton simulating it, and that it is decidable whether an asynchronous cellular automaton has this property or not, even in higher dimensions.
A Method for Selecting Noun Sense using Co-occurrence Relation in English-Korean Translation
Venue: arXiv cs.CL 2012
Year: 2012

The sense analysis is still critical problem in machine translation system, especially such as English-Korean translation which the syntactical different between source and target languages is very great. We suggest a method for selecting the noun sense using contextual feature in English-Korean Translation.
H-Probe: Estimating Traffic Correlations from Sampling and Active Network Probing
Venue: arXiv cs.NI 2012
Year: 2012

An extensive body of research deals with estimating the correlation and the Hurst parameter of Internet traffic traces. The significance of these statistics is due to their fundamental impact on network performance. The coverage of Internet traffic traces is, however, limited since acquiring such traces is challenging with respect to, e.g., confidentiality, logging speed, and storage capacity. In this work, we investigate how the correlation of Internet traffic can be reliably estimated from random traffic samples. These samples are observed either by passive monitoring within the network, or otherwise by active packet probes at end systems. We analyze random sampling processes with different inter-sample distributions and show how to obtain asymptotically unbiased estimates from these samples. We quantify the inherent limitations that are due to limited observations and explore the influence of various parameters, such as sampling intensity, network utilization, or Hurst parameter on the estimation accuracy. We design an active probing method which enables simple and lightweight traffic sampling without support from the network. We verify our approach in a controlled network environment and present comprehensive Internet measurements. We find that the correlation exhibits properties such as long range dependence as well as periodicities and that it differs significantly across Internet paths and observation times.
Forwarding Without Repeating: Efficient Rumor Spreading in Bounded-Degree Graphs
Venue: arXiv cs.DC 2012
Year: 2012

We study a gossip protocol called forwarding without repeating (FWR). The objective is to spread multiple rumors over a graph as efficiently as possible. FWR accomplishes this by having nodes record which messages they have forwarded to each neighbor, so that each message is forwarded at most once to each neighbor. We prove that FWR spreads a rumor over a strongly connected digraph, with high probability, in time which is within a constant factor of optimal for digraphs with bounded out-degree. Moreover, on digraphs with bounded out-degree and bounded number of rumors, the number of transmissions required by FWR is arbitrarily better than that of existing approaches. Specifically, FWR requires O(n) messages on bounded-degree graphs with n nodes, whereas classical forwarding and an approach based on network coding both require ω(n) messages. Our results are obtained using combinatorial and probabilistic arguments. Notably, they do not depend on expansion properties of the underlying graph, and consequently the message complexity of FWR is arbitrarily better than classical forwarding even on constant-degree expander graphs, as n \rightarrow \infty. In resource-constrained applications, where each transmission consumes battery power and bandwidth, our results suggest that using a small amount of memory at each node leads to a significant savings.
How Agreement and Disagreement Evolve over Random Dynamic Networks
Venue: arXiv cs.SI 2012
Year: 2012

The dynamics of an agreement protocol interacting with a disagreement process over a common random network is considered. The model can represent the spreading of true and false information over a communication network, the propagation of faults in a large-scale control system, or the development of trust and mistrust in a society. At each time instance and with a given probability, a pair of network nodes are selected to interact. At random each of the nodes then updates its state towards the state of the other node (attraction), away from the other node (repulsion), or sticks to its current state (neglect). Agreement convergence and disagreement divergence results are obtained for various strengths of the updates for both symmetric and asymmetric update rules. Impossibility theorems show that a specific level of attraction is required for almost sure asymptotic agreement and a specific level of repulsion is required for almost sure asymptotic disagreement. A series of sufficient and/or necessary conditions are then established for agreement convergence or disagreement divergence. In particular, under symmetric updates, a critical convergence measure in the attraction and repulsion update strength is found, in the sense that the asymptotic property of the network state evolution transits from agreement convergence to disagreement divergence when this measure goes from negative to positive. The result can be interpreted as a tight bound on how much bad action needs to be injected in a dynamic network in order to consistently steer its overall behavior away from consensus.
Comparative Bi-stochastizations and Associated Clusterings/Regionalizations of the 1995-2000 U. S. Intercounty Migration Network
Venue: arXiv cs.SI 2012
Year: 2012

Wang, Li and Konig have recently compared the cluster-theoretic properties of bi-stochasticized symmetric data similarity (e. g. kernel) matrices, produced by minimizing two different forms of Bregman divergences. We extend their investigation to non-symmetric matrices, specifically studying the 1995-2000 U. S. 3,107 x 3,107 intercounty migration matrix. A particular bi-stochastized form of it had been obtained (arXiv:1207.0437), using the well-established Sinkhorn-Knopp (SK) (biproportional) algorithm--which minimizes the Kullback-Leibler form of the divergence. This matrix has but a single entry equal to (the maximal possible value of) 1. Highly contrastingly, the bi-stochastic matrix obtained here, implementing the Wang-Li-Konig-algorithm for the minimum of the alternative, squared-norm form of the divergence, has 2,707 such unit entries. The corresponding 3,107-vertex, 2,707-link directed graph has 2,352 strong components. These consist of 1,659 single/isolated counties, 654 doublets (thirty-one interstate in nature), 22 triplets (one being interstate), 13 quartets (one being interstate), three quintets and one septet. Not manifest in these graph-theoretic results, however, are the five-county states of Hawaii and Rhode Island and the eight-county state of Connecticut. These--among other regional configurations--appealingly emerged as well-defined entities in the SK-based strong-component hierarchical clustering.
A Novel Strategy Selection Method for Multi-Objective Clustering Algorithms Using Game Theory
Venue: arXiv cs.GT 2012
Year: 2012

The most important factors which contribute to the efficiency of game-theoretical algorithms are time and game complexity. In this study, we have offered an elegant method to deal with high complexity of game theoretic multi-objective clustering methods in large-sized data sets. Here, we have developed a method which selects a subset of strategies from strategies profile for each player. In this case, the size of payoff matrices reduces significantly which has a remarkable impact on time complexity. Therefore, practical problems with more data are tractable with less computational complexity. Although strategies set may grow with increasing the number of data points, the presented model of strategy selection reduces the strategy space, considerably, where clusters are subdivided into several sub-clusters in each local game. The remarkable results demonstrate the efficiency of the presented approach in reducing computational complexity of the problem of concern.
Modeling and Verification of Agent based Adaptive Traffic Signal using Symbolic Model Verifier
Venue: arXiv cs.SE 2012
Year: 2012

This paper addresses the issue of modeling and verification of a Multi Agent System (MAS) scenario. We have considered an agent based adaptive traffic signal system. The system monitors the smooth flow of traffic at intersection of two road segment. After describing how the adaptive traffic signal system can efficiently be used and showing its advantages over traffic signals with predetermined periods, we have shown how we can transform this scenario into Finite State Machine (FSM). Once the system is transformed into a FSM, we have verified the specifications specified in Computational Tree Logic(CTL) using NuSMV as a model checking tool. Simulation results obtained from NuSMV showed us whether the system satisfied the specifications or not. It has also showed us the state where the system specification does not hold. Using which we traced back our system to find the source, leading to the specification violation. Finally, we again verified the modified system with NuSMV for its specifications.
Bio Inspired Approach to Secure Routing in MANETs
Venue: arXiv cs.CR 2012
Year: 2012

In this paper, the author explore the challenges with respect to the security aspect in MANETs and propose a new approach which makes use of a bio-inspired methodology. This paper elaborates various attacks which can be perpetrated on MANETs and current solutions to the aforementioned problems, and then it describes a Bio-Inspired Method which could be a possible solution to security issues in MANETs.