OpenRaiser/Intern-Atlas huggingface dataset:
On Performance Debugging of Unnecessary Lock Contentions on Multicore Processors: A Replay-based Approach
Venue: arXiv cs.PL 2015
Year: 2015

Locks have been widely used as an effective synchronization mechanism among processes and threads. However, we observe that a large number of false inter-thread dependencies (i.e., unnecessary lock contentions) exist during the program execution on multicore processors, thereby incurring significant performance overhead. This paper presents a performance debugging framework, PERFPLAY, to facilitate a comprehensive and in-depth understanding of the performance impact of unnecessary lock contentions. The core technique of our debugging framework is trace replay. Specifically, PERFPLAY records the program execution trace, on the basis of which the unnecessary lock contentions can be identified through trace analysis. We then propose a novel technique of trace transformation to transform these identified unnecessary lock contentions in the original trace into the correct pattern as a new trace free of unnecessary lock contentions. Through replaying both traces, PERFPLAY can quantify the performance impact of unnecessary lock contentions. To demonstrate the effectiveness of our debugging framework, we study five real-world programs and PARSEC benchmarks. Our experimental results demonstrate the significant performance overhead of unnecessary lock contentions, and the effectiveness of PERFPLAY in identifying the performance critical unnecessary lock contentions in real applications.
Fewer runs than word length
Venue: arXiv cs.DM 2015
Year: 2015

The work takes another look at the number of runs that a string might contain and provides an alternative proof for the bound. We also propose another stronger conjecture that states that, for a fixed order on the alphabet, within every factor of a word there are at most as many occurrences of Lyndon roots corresponding to runs in a word as the length of the factor (only first such occurrences for each run are considered).
Spiral Toolpaths for High-Speed Machining of 2D Pockets with or without Islands
Venue: arXiv cs.CG 2015
Year: 2015

We describe new methods for the construction of spiral toolpaths for high-speed machining. In the simplest case, our method takes a polygon as input and a number $δ>0$ and returns a spiral starting at a central point in the polygon, going around towards the boundary while morphing to the shape of the polygon. The spiral consists of linear segments and circular arcs, it is $G^1$ continuous, it has no self-intersections, and the distance from each point on the spiral to each of the neighboring revolutions is at most $δ$. Our method has the advantage over previously described methods that it is easily adjustable to the case where there is an island in the polygon to be avoided by the spiral. In that case, the spiral starts at the island and morphs the island to the outer boundary of the polygon. It is shown how to apply that method to make significantly shorter spirals in polygons with no islands. Finally, we show how to make a spiral in a polygon with multiple islands by connecting the islands into one island.
BER-Based Physical Layer Security with Finite Codelength: Combining Strong Converse and Error Amplification
Venue: arXiv cs.IT 2015
Year: 2015

A bit error rate (BER)-based physical layer security approach is proposed for finite blocklength. For secure communication in the sense of high BER, the information-theoretic strong converse is combined with cryptographic error amplification achieved by substitution permutation networks (SPNs) based on confusion and diffusion. For discrete memoryless channels (DMCs), an analytical framework is provided showing the tradeoffs among finite blocklength, maximum/minimum possible transmission rates, and BER requirements for the legitimate receiver and the eavesdropper. Also, the security gap is analytically studied for Gaussian channels and the concept is extended to other DMCs including binary symmetric channels (BSCs) and binary erasure channels (BECs). For fading channels, the transmit power is optimized to minimize the outage probability of the legitimate receiver subject to a BER threshold for the eavesdropper.
Approximate Bayesian Smoothing with Unknown Process and Measurement Noise Covariances
Venue: arXiv cs.SY 2015
Year: 2015

We present an adaptive smoother for linear state-space models with unknown process and measurement noise covariances. The proposed method utilizes the variational Bayes technique to perform approximate inference. The resulting smoother is computationally efficient, easy to implement, and can be applied to high dimensional linear systems. The performance of the algorithm is illustrated on a target tracking example.
Globally Governed Session Semantics
Venue: arXiv cs.LO 2015
Year: 2015

This paper proposes a bisimulation theory based on multiparty session types where a choreography specification governs the behaviour of session typed processes and their observer. The bisimulation is defined with the observer cooperating with the observed process in order to form complete global session scenarios and usable for proving correctness of optimisations for globally coordinating threads and processes. The induced bisimulation is strictly more fine-grained than the standard session bisimulation. The difference between the governed and standard bisimulations only appears when more than two interleaved multiparty sessions exist. This distinct feature enables to reason real scenarios in the large-scale distributed system where multiple choreographic sessions need to be interleaved. The compositionality of the governed bisimilarity is proved through the soundness and completeness with respect to the governed reduction-based congruence. Finally, its usage is demonstrated by a thread transformation governed under multiple sessions in a real usecase in the large-scale cyberinfrustracture.
Fractional Max-Pooling
Venue: arXiv cs.CV 2015
Year: 2015

Convolutional networks almost always incorporate some form of spatial pooling, and very often it is alpha times alpha max-pooling with alpha=2. Max-pooling act on the hidden layers of the network, reducing their size by an integer multiplicative factor alpha. The amazing by-product of discarding 75% of your data is that you build into the network a degree of invariance with respect to translations and elastic distortions. However, if you simply alternate convolutional layers with max-pooling layers, performance is limited due to the rapid reduction in spatial size, and the disjoint nature of the pooling regions. We have formulated a fractional version of max-pooling where alpha is allowed to take non-integer values. Our version of max-pooling is stochastic as there are lots of different ways of constructing suitable pooling regions. We find that our form of fractional max-pooling reduces overfitting on a variety of datasets: for instance, we improve on the state-of-the art for CIFAR-100 without even using dropout.
Exploiting the Structure of Bipartite Graphs for Algebraic and Spectral Graph Theory Applications
Venue: arXiv cs.DM 2015
Year: 2015

In this article, we extend several algebraic graph analysis methods to bipartite networks. In various areas of science, engineering and commerce, many types of information can be represented as networks, and thus the discipline of network analysis plays an important role in these domains. A powerful and widespread class of network analysis methods is based on algebraic graph theory, i.e., representing graphs as square adjacency matrices. However, many networks are of a very specific form that clashes with that representation: They are bipartite. That is, they consist of two node types, with each edge connecting a node of one type with a node of the other type. Examples of bipartite networks (also called \emph{two-mode networks}) are persons and the social groups they belong to, musical artists and the musical genres they play, and text documents and the words they contain. In fact, any type of feature that can be represented by a categorical variable can be interpreted as a bipartite network. Although bipartite networks are widespread, most literature in the area of network analysis focuses on unipartite networks, i.e., those networks with only a single type of node. The purpose of this article is to extend a selection of important algebraic network analysis methods to bipartite networks, showing that many methods from algebraic graph theory can be applied to bipartite networks with only minor modifications. We show methods for clustering, visualization and link prediction. Additionally, we introduce new algebraic methods for measuring the bipartivity in near-bipartite graphs.
Epidemic Outbreaks in Networks with Equitable or Almost-Equitable Partitions
Venue: arXiv cs.SI 2015
Year: 2015

We study the diffusion of epidemics on networks that are partitioned into local communities. The gross structure of hierarchical networks of this kind can be described by a quotient graph. The rationale of this approach is that individuals infect those belonging to the same community with higher probability than individuals in other communities. In community models the nodal infection probability is thus expected to depend mainly on the interaction of a few, large interconnected clusters. In this work, we describe the epidemic process as a continuous-time individual-based susceptible-infected-susceptible (SIS) model using a first-order mean-field approximation. A key feature of our model is that the spectral radius of this smaller quotient graph (which only captures the macroscopic structure of the community network) is all we need to know in order to decide whether the overall healthy-state defines a globally asymptotically stable or an unstable equilibrium. Indeed, the spectral radius is related to the epidemic threshold of the system. Moreover we prove that, above the threshold, another steady-state exists that can be computed using a lower-dimensional dynamical system associated with the evolution of the process on the quotient graph. Our investigations are based on the graph-theoretical notion of equitable partition and of its recent and rather flexible generalization, that of almost equitable partition.
Micro-Navigation for Urban Bus Passengers: Using the Internet of Things to Improve the Public Transport Experience
Venue: arXiv cs.HC 2015
Year: 2015

Public bus services are widely deployed in cities around the world because they provide cost-effective and economic public transportation. However, from a passenger point of view urban bus systems can be complex and difficult to navigate, especially for disadvantaged users, i.e. tourists, novice users, older people, and people with impaired cognitive or physical abilities. We present Urban Bus Navigator (UBN), a reality-aware urban navigation system for bus passengers with the ability to recognize and track the physical public transport infrastructure such as buses. Unlike traditional location-aware mobile transport applications, UBN acts as a true navigation assistant for public transport users. Insights from a six-month long trial in Madrid indicate that UBN removes barriers for public transport usage and has a positive impact on how people feel about public transport journeys.
Permutohedral Lattice CNNs
Venue: arXiv cs.CV 2015
Year: 2015

This paper presents a convolutional layer that is able to process sparse input features. As an example, for image recognition problems this allows an efficient filtering of signals that do not lie on a dense grid (like pixel position), but of more general features (such as color values). The presented algorithm makes use of the permutohedral lattice data structure. The permutohedral lattice was introduced to efficiently implement a bilateral filter, a commonly used image processing operation. Its use allows for a generalization of the convolution type found in current (spatial) convolutional network architectures.
Deep learning with Elastic Averaging SGD
Venue: arXiv cs.LG 2015
Year: 2015

We study the problem of stochastic optimization for deep learning in the parallel computing environment under communication constraints. A new algorithm is proposed in this setting where the communication and coordination of work among concurrent processes (local workers), is based on an elastic force which links the parameters they compute with a center variable stored by the parameter server (master). The algorithm enables the local workers to perform more exploration, i.e. the algorithm allows the local variables to fluctuate further from the center variable by reducing the amount of communication between local workers and the master. We empirically demonstrate that in the deep learning setting, due to the existence of many local optima, allowing more exploration can lead to the improved performance. We propose synchronous and asynchronous variants of the new algorithm. We provide the stability analysis of the asynchronous variant in the round-robin scheme and compare it with the more common parallelized method ADMM. We show that the stability of EASGD is guaranteed when a simple stability condition is satisfied, which is not the case for ADMM. We additionally propose the momentum-based version of our algorithm that can be applied in both synchronous and asynchronous settings. Asynchronous variant of the algorithm is applied to train convolutional neural networks for image classification on the CIFAR and ImageNet datasets. Experiments demonstrate that the new algorithm accelerates the training of deep architectures compared to DOWNPOUR and other common baseline approaches and furthermore is very communication efficient.
Synthesis Method for the Spherical 4R Mechanism with Minimum Center of Mass Acceleration
Venue: arXiv cs.CE 2015
Year: 2015

In the mechanisms area, minimization of the magnitude of the acceleration of the center of mass (ACoM) implies shaking force balancing. For a mechanism operating in cycles, the case when the ACoM is zero implies that the gravitational potential energy (GPE) is constant. This article shows an efficient and effective optimum synthesis method for minimum acceleration of the center of mass of a spherical 4R mechanism by using dual functions and the counterweights balancing method. Once the dual function for ACoM has been written, one can minimize the shaking forces from a kinematic point of view. We present the synthesis of a spherical 4R mechanism for the case of a path generation task. The synthesis process involves the optimization of two objective functions, this multiobjective problem is solved by using the weighted sum method implemented in the evolutionary algorithm known as Differential Evolution.
Contour Detection Using Cost-Sensitive Convolutional Neural Networks
Venue: arXiv cs.CV 2015
Year: 2015

We address the problem of contour detection via per-pixel classifications of edge point. To facilitate the process, the proposed approach leverages with DenseNet, an efficient implementation of multiscale convolutional neural networks (CNNs), to extract an informative feature vector for each pixel and uses an SVM classifier to accomplish contour detection. The main challenge lies in adapting a pre-trained per-image CNN model for yielding per-pixel image features. We propose to base on the DenseNet architecture to achieve pixelwise fine-tuning and then consider a cost-sensitive strategy to further improve the learning with a small dataset of edge and non-edge image patches. In the experiment of contour detection, we look into the effectiveness of combining per-pixel features from different CNN layers and obtain comparable performances to the state-of-the-art on BSDS500.
Formation Control with Triangulated Laman Graphs
Venue: arXiv cs.SY 2015
Year: 2015

Formation control deals with the design of decentralized control laws that stabilize agents at prescribed distances from each other. We call any configuration that satisfies the inter-agent distance conditions a target configuration. It is well known that when the distance conditions are defined via a rigid graph, there is a finite number of target configurations modulo rotations and translations. We can thus recast the objective of formation control as stabilizing one or many of the target configurations. A major issue is that such control laws will also have equilibria corresponding to configurations which do not meet the desired inter-agent distance conditions; we refer to these as undesired equilibria. The undesired equilibria become problematic if they are also stable. Designing decentralized control laws whose stable equilibria are all target configurations in the case of a general rigid graph is still an open problem. We propose here a partial solution to this problem by exhibiting a class of rigid graphs and control laws for which all stable equilibria are target configurations.
Massive MIMO for Maximal Spectral Efficiency: How Many Users and Pilots Should Be Allocated?
Venue: arXiv cs.IT 2015
Year: 2015

Massive MIMO is a promising technique to increase the spectral efficiency (SE) of cellular networks, by deploying antenna arrays with hundreds or thousands of active elements at the base stations and performing coherent transceiver processing. A common rule-of-thumb is that these systems should have an order of magnitude more antennas, $M$, than scheduled users, $K$, because the users' channels are likely to be near-orthogonal when $M/K > 10$. However, it has not been proved that this rule-of-thumb actually maximizes the SE. In this paper, we analyze how the optimal number of scheduled users, $K^\star$, depends on $M$ and other system parameters. To this end, new SE expressions are derived to enable efficient system-level analysis with power control, arbitrary pilot reuse, and random user locations. The value of $K^\star$ in the large-$M$ regime is derived in closed form, while simulations are used to show what happens at finite $M$, in different interference scenarios, with different pilot reuse factors, and for different processing schemes. Up to half the coherence block should be dedicated to pilots and the optimal $M/K$ is less than 10 in many cases of practical relevance. Interestingly, $K^\star$ depends strongly on the processing scheme and hence it is unfair to compare different schemes using the same $K$.
Reply to the commentary "Be careful when assuming the obvious", by P. Alday
Venue: arXiv cs.CL 2015
Year: 2015

Here we respond to some comments by Alday concerning headedness in linguistic theory and the validity of the assumptions of a mathematical model for word order. For brevity, we focus only on two assumptions: the unit of measurement of dependency length and the monotonicity of the cost of a dependency as a function of its length. We also revise the implicit psychological bias in Alday's comments. Notwithstanding, Alday is indicating the path for linguistic research with his unusual concerns about parsimony from multiple dimensions.
Convolutional Neural Networks for joint object detection and pose estimation: A comparative study
Venue: arXiv cs.CV 2015
Year: 2015

In this paper we study the application of convolutional neural networks for jointly detecting objects depicted in still images and estimating their 3D pose. We identify different feature representations of oriented objects, and energies that lead a network to learn this representations. The choice of the representation is crucial since the pose of an object has a natural, continuous structure while its category is a discrete variable. We evaluate the different approaches on the joint object detection and pose estimation task of the Pascal3D+ benchmark using Average Viewpoint Precision. We show that a classification approach on discretized viewpoints achieves state-of-the-art performance for joint object detection and pose estimation, and significantly outperforms existing baselines on this benchmark.
Learning Deep Temporal Representations for Brain Decoding
Venue: arXiv cs.LG 2015
Year: 2015

Functional magnetic resonance imaging produces high dimensional data, with a less then ideal number of labelled samples for brain decoding tasks (predicting brain states). In this study, we propose a new deep temporal convolutional neural network architecture with spatial pooling for brain decoding which aims to reduce dimensionality of feature space along with improved classification performance. Temporal representations (filters) for each layer of the convolutional model are learned by leveraging unlabelled fMRI data in an unsupervised fashion with regularized autoencoders. Learned temporal representations in multiple levels capture the regularities in the temporal domain and are observed to be a rich bank of activation patterns which also exhibit similarities to the actual hemodynamic responses. Further, spatial pooling layers in the convolutional architecture reduce the dimensionality without losing excessive information. By employing the proposed temporal convolutional architecture with spatial pooling, raw input fMRI data is mapped to a non-linear, highly-expressive and low-dimensional feature space where the final classification is conducted. In addition, we propose a simple heuristic approach for hyper-parameter tuning when no validation data is available. Proposed method is tested on a ten class recognition memory experiment with nine subjects. The results support the efficiency and potential of the proposed model, compared to the baseline multi-voxel pattern analysis techniques.
Balancing Isolation and Sharing of Data for Third-Party Extensible App Ecosystems
Venue: arXiv cs.CR 2015
Year: 2015

In the landscape of application ecosystems, today's cloud users wish to personalize not only their browsers with various extensions or their smartphones with various applications, but also the various extensions and applications themselves. The resulting personalization significantly raises the attractiveness for typical Web 2.0 users, but gives rise to various security risks and privacy concerns, such as unforeseen access to certain critical components, undesired information flow of personal information to untrusted applications, or emerging attack surfaces that were not possible before a personalization has taken place. In this paper, we propose a novel extensibility mechanism which is used for implementing personalization of existing cloud applications towards (possibly untrusted) components in a secure and privacy-friendly manner. Our model provides a clean component abstraction, thereby in particular ruling out undesired component accesses and ensuring that no undesired information flow takes place between application components -- either trusted from the base application or untrusted from various extensions. We then instantiate our model in the SAFE web application framework (WWW 2012), resulting in a novel methodology that is inspired by traditional access control and specifically designed for the newly emerging needs of extensibility in application ecosystems. We illustrate the convenient usage of our techniques by showing how to securely extend an existing social network application.