OpenRaiser/Intern-Atlas huggingface dataset:
Looking into Hardware-in-the-Loop Coupling of OMNeT++ and RoSeNet
Venue: arXiv cs.NI 2015
Year: 2015

Network emulation using real sensor node hardware is used to increase the accuracy of pure network simulations. Coupling OMNeT++ with network emulation platforms and tools introduces new application possibilities for both sides. This work-in-progress report covers our experiences of using OMNeT++ as a test driver for RoSeNet, a network emulation and test platform for low-power wireless technologies like IEEE 802.15.4. OMNeT++ and RoSeNet were interconnected to enable a co-simulation of real sensor networks with a MAC layer simulation model. Experiences and insights on this Hardware-in-the-Loop (HIL) simulation together with ideas to extend OMNeT++ and to provide a generic interconnection API complete the report.
FPGA Implementation of High Speed Baugh-Wooley Multiplier using Decomposition Logic
Venue: arXiv cs.AR 2015
Year: 2015

The Baugh-Wooley algorithm is a well-known iterative algorithm for performing multiplication in digital signal processing applications. Decomposition logic is used with Baugh-Wooley algorithm to enhance the speed and to reduce the critical path delay. In this paper a high speed multiplier is designed and implemented using decomposition logic and Baugh-Wooley algorithm. The result is compared with booth multiplier. FPGA based architecture is presented and design has been implemented using Xilinx 12.3 device.
Green Energy Aware Avatar Migration Strategy in Green Cloudlet Networks
Venue: arXiv cs.DC 2015
Year: 2015

We propose a Green Cloudlet Network (\emph{GCN}) architecture to provide seamless Mobile Cloud Computing (\emph{MCC}) services to User Equipments (\emph{UE}s) with low latency in which each cloudlet is powered by both green and brown energy. Fully utilizing green energy can significantly reduce the operational cost of cloudlet providers. However, owing to the spatial dynamics of energy demand and green energy generation, the energy gap among different cloudlets in the network is unbalanced, i.e., some cloudlets' energy demands can be fully provided by green energy but others need to utilize on-grid energy (i.e., brown energy) to satisfy their energy demands. We propose a Green-energy awarE Avatar migRation (\emph{GEAR}) strategy to minimize the on-grid energy consumption in GCN by redistributing the energy demands via Avatar migration among cloudlets according to cloudlets' green energy generation. Furthermore, GEAR ensures the Service Level Agreement (\emph{SLA}) in terms of the maximum Avatar propagation delay by avoiding Avatars hosted in the remote cloudlets. We formulate the GEAR strategy as a mixed integer linear programming problem, which is NP-hard, and thus apply the Branch and Bound search to find its sub-optimal solution. Simulation results demonstrate that GEAR can save on-grid energy consumption significantly as compared to the Follow me AvataR (\emph{FAR}) migration strategy, which aims to minimize the propagation delay between an UE and its Avatar.
Refined analysis of sparse MIMO radar
Venue: arXiv cs.IT 2015
Year: 2015

We analyze a multiple-input multiple-output (MIMO) radar model and provide recovery results for a compressed sensing (CS) approach. In MIMO radar different pulses are emitted by several transmitters and the echoes are recorded at several receiver nodes. Under reasonable assumptions the transformation from emitted pulses to the received echoes can approximately be regarded as linear. For the considered model, and many radar tasks in general, sparsity of targets within the considered angle-range-Doppler domain is a natural assumption. Therefore, it is possible to apply methods from CS in order to reconstruct the parameters of the targets. Assuming Gaussian random pulses the resulting measurement matrix becomes a highly structured random matrix. Our first main result provides an estimate for the well-known restricted isometry property (RIP) ensuring stable and robust recovery. We require more measurements than standard results from CS, like for example those for Gaussian random measurements. Nevertheless, we show that due to the special structure of the considered measurement matrix our RIP result is in fact optimal (up to possibly logarithmic factors). Our further two main results on nonuniform recovery (i.e., for a fixed sparse target scene) reveal how the fine structure of the support set affects the (nonuniform) recovery performance. We show that for certain "balanced" support sets reconstruction with essentially the optimal number of measurements is possible. We prove recovery results for both perfect recovery of the support set in case of exactly sparse vectors and an $\ell_2$-norm approximation result for reconstruction under sparsity defect.Our analysis complements earlier work by Strohmer & Friedlander and deepens the understanding of the considered MIMO radar model.
DReAM: Dynamic Re-arrangement of Address Mapping to Improve the Performance of DRAMs
Venue: arXiv cs.AR 2015
Year: 2015

The initial location of data in DRAMs is determined and controlled by the 'address-mapping' and even modern memory controllers use a fixed and run-time-agnostic address mapping. On the other hand, the memory access pattern seen at the memory interface level will dynamically change at run-time. This dynamic nature of memory access pattern and the fixed behavior of address mapping process in DRAM controllers, implied by using a fixed address mapping scheme, means that DRAM performance cannot be exploited efficiently. DReAM is a novel hardware technique that can detect a workload-specific address mapping at run-time based on the application access pattern which improves the performance of DRAMs. The experimental results show that DReAM outperforms the best evaluated address mapping on average by 9%, for mapping-sensitive workloads, by 2% for mapping-insensitive workloads, and up to 28% across all the workloads. DReAM can be seen as an insurance policy capable of detecting which scenarios are not well served by the predefined address mapping.
Output-Polynomial Enumeration on Graphs of Bounded (Local) Linear MIM-Width
Venue: arXiv cs.DS 2015
Year: 2015

The linear induced matching width (LMIM-width) of a graph is a width parameter defined by using the notion of branch-decompositions of a set function on ternary trees. In this paper we study output-polynomial enumeration algorithms on graphs of bounded LMIM-width and graphs of bounded local LMIM-width. In particular, we show that all 1-minimal and all 1-maximal (σ,ρ)-dominating sets, and hence all minimal dominating sets, of graphs of bounded LMIM-width can be enumerated with polynomial (linear) delay using polynomial space. Furthermore, we show that all minimal dominating sets of a unit square graph can be enumerated in incremental polynomial time.
Toward better feature weighting algorithms: a focus on Relief
Venue: arXiv cs.LG 2015
Year: 2015

Feature weighting algorithms try to solve a problem of great importance nowadays in machine learning: The search of a relevance measure for the features of a given domain. This relevance is primarily used for feature selection as feature weighting can be seen as a generalization of it, but it is also useful to better understand a problem's domain or to guide an inductor in its learning process. Relief family of algorithms are proven to be very effective in this task. Some other feature weighting methods are reviewed in order to give some context and then the different existing extensions to the original algorithm are explained. One of Relief's known issues is the performance degradation of its estimates when redundant features are present. A novel theoretical definition of redundancy level is given in order to guide the work towards an extension of the algorithm that is more robust against redundancy. A new extension is presented that aims for improving the algorithms performance. Some experiments were driven to test this new extension against the existing ones with a set of artificial and real datasets and denoted that in certain cases it improves the weight's estimation accuracy.
Automatic Loop Kernel Analysis and Performance Modeling With Kerncraft
Venue: arXiv cs.PF 2015
Year: 2015

Analytic performance models are essential for understanding the performance characteristics of loop kernels, which consume a major part of CPU cycles in computational science. Starting from a validated performance model one can infer the relevant hardware bottlenecks and promising optimization opportunities. Unfortunately, analytic performance modeling is often tedious even for experienced developers since it requires in-depth knowledge about the hardware and how it interacts with the software. We present the "Kerncraft" tool, which eases the construction of analytic performance models for streaming kernels and stencil loop nests. Starting from the loop source code, the problem size, and a description of the underlying hardware, Kerncraft can ideally predict the single-core performance and scaling behavior of loops on multicore processors using the Roofline or the Execution-Cache-Memory (ECM) model. We describe the operating principles of Kerncraft with its capabilities and limitations, and we show how it may be used to quickly gain insights by accelerated analytic modeling.
Failure Mitigation in Linear, Sesquilinear and Bijective Operations On Integer Data Streams Via Numerical Entanglement
Venue: arXiv cs.DC 2015
Year: 2015

A new roll-forward technique is proposed that recovers from any single fail-stop failure in $M$ integer data streams ($M\geq3$) when undergoing linear, sesquilinear or bijective (LSB) operations, such as: scaling, additions/subtractions, inner or outer vector products and permutations. In the proposed approach, the $M$ input integer data streams are linearly superimposed to form $M$ numerically entangled integer data streams that are stored in-place of the original inputs. A series of LSB operations can then be performed directly using these entangled data streams. The output results can be extracted from any $M-1$ entangled output streams by additions and arithmetic shifts, thereby guaranteeing robustness to a fail-stop failure in any single stream computation. Importantly, unlike other methods, the number of operations required for the entanglement, extraction and recovery of the results is linearly related to the number of the inputs and does not depend on the complexity of the performed LSB operations. We have validated our proposal in an Intel processor (Haswell architecture with AVX2 support) via convolution operations. Our analysis and experiments reveal that the proposed approach incurs only $1.8\%$ to $2.8\%$ reduction in processing throughput in comparison to the failure-intolerant approach. This overhead is 9 to 14 times smaller than that of the equivalent checksum-based method. Thus, our proposal can be used in distributed systems and unreliable processor hardware, or safety-critical applications, where robustness against fail-stop failures becomes a necessity.
The USFD Spoken Language Translation System for IWSLT 2014
Venue: arXiv cs.CL 2015
Year: 2015

The University of Sheffield (USFD) participated in the International Workshop for Spoken Language Translation (IWSLT) in 2014. In this paper, we will introduce the USFD SLT system for IWSLT. Automatic speech recognition (ASR) is achieved by two multi-pass deep neural network systems with adaptation and rescoring techniques. Machine translation (MT) is achieved by a phrase-based system. The USFD primary system incorporates state-of-the-art ASR and MT techniques and gives a BLEU score of 23.45 and 14.75 on the English-to-French and English-to-German speech-to-text translation task with the IWSLT 2014 data. The USFD contrastive systems explore the integration of ASR and MT by using a quality estimation system to rescore the ASR outputs, optimising towards better translation. This gives a further 0.54 and 0.26 BLEU improvement respectively on the IWSLT 2012 and 2014 evaluation data.
Approximability of TSP on Power Law Graphs
Venue: arXiv cs.DS 2015
Year: 2015

In this paper we study the special case of Graphic TSP where the underlying graph is a power law graph (PLG). We give a refined analysis of some of the current best approximation algorithms and show that an improved approximation ratio can be achieved for certain ranges of the power law exponent $β$. For the value of power law exponent $β=1.5$ we obtain an approximation ratio of $1.34$ for Graphic TSP. Moreover we study the $(1,2)$-TSP with the underlying graph of $1$-edges being a PLG. We show improved approximation ratios in the case of underlying deterministic PLGs for $β$ greater than $1.666$. For underlying random PLGs we further improve the analysis and show even better expected approximation ratio for the range of $β$ between $1$ and $3.5$. On the other hand we prove the first explicit inapproximability bounds for $(1,2)$-TSP for an underlying power law graph.
MINE GOLD to Deliver Green Cognitive Communications
Venue: arXiv cs.NI 2015
Year: 2015

Geo-location database-assisted TV white space network reduces the need of energy-intensive processes (such as spectrum sensing), hence can achieve green cognitive communication effectively. The success of such a network relies on a proper business model that provides incentives for all parties involved. In this paper, we propose MINE GOLD (a Model of INformation markEt for GeO-Location Database), which enables databases to sell the spectrum information to unlicensed white space devices (WSDs) for profit. Specifically, we focus on an oligopoly information market with multiple databases, and study the interactions among databases and WSDs using a two-stage hierarchical model. In Stage I, databases compete to sell information to WSDs by optimizing their information prices. In Stage II, each WSD decides whether and from which database to purchase the information, to maximize his benefit of using the TV white space. We first characterize how the WSDs' purchasing behaviors dynamically evolve, and what is the equilibrium point under fixed information prices from the databases. We then analyze how the system parameters and the databases' pricing decisions affect the market equilibrium, and what is the equilibrium of the database price competition. Our numerical results show that, perhaps counter-intuitively, the databases' aggregate revenue is not monotonic with the number of databases. Moreover, numerical results show that a large degree of positive network externality would improve the databases' revenues and the system performance.
A Note on the Size-Sensitive Packing Lemma
Venue: arXiv cs.CG 2015
Year: 2015

We show that the size-sensitive packing lemma follows from a simple modification of the standard proof, due to Haussler and simplified by Chazelle, of the packing lemma.
Programs as proofs
Venue: arXiv cs.PL 2015
Year: 2015

The Curry-Howard correspondence is about a relationship between types and programs on the one hand and propositions and proofs on the other. The implications for programming language design and program verification is an active field of research. Transformer-like semantics of internal definitions that combine a defining computation and an application will be presented. By specialisation for a given defining computation one can derive inference rules for applications of defined operations. With semantics of that kind for every operation, each application identifies an axiom in a logic defined by the programming language, so a language can be considered a theory.
Cooperative Cognitive Radio Network with Energy Harvesting: Stability Analysis
Venue: arXiv cs.IT 2015
Year: 2015

This paper investigates the maximum stable throughput of a cooperative cognitive radio system with energy harvesting Primary User and Secondary User. Each PU and SU has a data queue for data storage and a battery for energy storage. These batteries harvest energy from the environment and store it for data transmission in next time slots. The SU is allowed to access the PU channel only when the PU is idle. The SU cooperates with the PU for its data transmission, getting mutual benefits for both users, such that, the PU exploits the SU power to relay a fraction of its undelivered packets, and the SU gets more opportunities to access idle time slots.
i-MARK: A New Subtraction Division Game
Venue: arXiv cs.DM 2015
Year: 2015

Given two finite sets of integers $S\subseteq\NNN\setminus\{0\}$ and $D\subseteq\NNN\setminus\{0,1\}$,the impartial combinatorial game $\IMARK(S,D)$ is played on a heap of tokens. From a heap of $n$ tokens, each player can moveeither to a heap of $n-s$ tokens for some $s\in S$, or to a heap of $n/d$ tokensfor some $d\in D$ if $d$ divides $n$.Such games can be considered as an integral variant of \MARK-type games, introduced by Elwyn Berlekamp and Joe Buhlerand studied by Aviezri Fraenkel and Alan Guo, for which it is allowed to move from a heap of $n$ tokensto a heap of $\lfloor n/d\rfloor$ tokens for any $d\in D$.Under normal convention, it is observed that the Sprague-Grundy sequence of the game $\IMARK(S,D)$ is aperiodic for any sets $S$ and $D$.However, we prove that, in many cases, this sequence is almost periodic and that the set of winning positions is periodic.Moreover, in all these cases, the Sprague-Grundy value of a heap of $n$ tokens can be computed in time $O(\log n)$.We also prove that, under misère convention, the outcome sequence of these games is purely periodic.
A Total Fractional-Order Variation Model for Image Restoration with Non-homogeneous Boundary Conditions and its Numerical Solution
Venue: arXiv cs.CV 2015
Year: 2015

To overcome the weakness of a total variation based model for image restoration, various high order (typically second order) regularization models have been proposed and studied recently. In this paper we analyze and test a fractional-order derivative based total $α$-order variation model, which can outperform the currently popular high order regularization models. There exist several previous works using total $α$-order variations for image restoration; however first no analysis is done yet and second all tested formulations, differing from each other, utilize the zero Dirichlet boundary conditions which are not realistic (while non-zero boundary conditions violate definitions of fractional-order derivatives). This paper first reviews some results of fractional-order derivatives and then analyzes the theoretical properties of the proposed total $α$-order variational model rigorously. It then develops four algorithms for solving the variational problem, one based on the variational Split-Bregman idea and three based on direct solution of the discretise-optimization problem. Numerical experiments show that, in terms of restoration quality and solution efficiency, the proposed model can produce highly competitive results, for smooth images, to two established high order models: the mean curvature and the total generalized variation.
The response of grandstands driven by filtered Gaussian white noise processes
Venue: arXiv cs.CE 2015
Year: 2015

This paper presents a semi-analytical estimate of the response of a grandstand occupied by an active crowd and by a passive crowd. Filtered Gaussian white noise processes are used to approximate the loading terms representing an active crowd. Lumped biodynamic models with a single degree of freedom are included to reflect passive spectators occupying the structure. The response is described in terms of the first two moments, employing the Itô formula and the state augmentation method for the stationary time domain solution. The quality of the approximation is compared on the basis of three examples of varying complexity using Monte Carlo simulation based on a synthetic generator available in the literature. For comparative purposes, there is also a brief review of frequency domain estimates.
Double Relief with progressive weighting function
Venue: arXiv cs.LG 2015
Year: 2015

Feature weighting algorithms try to solve a problem of great importance nowadays in machine learning: The search of a relevance measure for the features of a given domain. This relevance is primarily used for feature selection as feature weighting can be seen as a generalization of it, but it is also useful to better understand a problem's domain or to guide an inductor in its learning process. Relief family of algorithms are proven to be very effective in this task. On previous work, a new extension was proposed that aimed for improving the algorithm's performance and it was shown that in certain cases it improved the weights' estimation accuracy. However, it also seemed to be sensible to some characteristics of the data. An improvement of that previously presented extension is presented in this work that aims to make it more robust to problem specific characteristics. An experimental design is proposed to test its performance. Results of the tests prove that it indeed increase the robustness of the previously proposed extension.
Bounding the Clique-Width of $H$-free Split Graphs
Venue: arXiv cs.DM 2015
Year: 2015

A graph is $H$-free if it has no induced subgraph isomorphic to $H$. We continue a study into the boundedness of clique-width of subclasses of perfect graphs. We identify five new classes of $H$-free split graphs whose clique-width is bounded. Our main result, obtained by combining new and known results, provides a classification of all but two stubborn cases, that is, with two potential exceptions we determine all graphs $H$ for which the class of $H$-free split graphs has bounded clique-width.
Implementing a teleo-reactive programming system
Venue: arXiv cs.PL 2015
Year: 2015

This thesis explores the teleo-reactive programming paradigm for controlling autonomous agents, such as robots. Teleo-reactive programming provides a robust, opportunistic method for goal-directed programming that continuously reacts to the sensed environment. In particular, the TR and TeleoR systems are investigated. They influence the design of a teleo-reactive system programming in Python, for controlling autonomous agents via the Pedro communications architecture. To demonstrate the system, it is used as a controller in a simple game.
Learning without Recall by Random Walks on Directed Graphs
Venue: arXiv cs.SY 2015
Year: 2015

We consider a network of agents that aim to learn some unknown state of the world using private observations and exchange of beliefs. At each time, agents observe private signals generated based on the true unknown state. Each agent might not be able to distinguish the true state based only on her private observations. This occurs when some other states are observationally equivalent to the true state from the agent's perspective. To overcome this shortcoming, agents must communicate with each other to benefit from local observations. We propose a model where each agent selects one of her neighbors randomly at each time. Then, she refines her opinion using her private signal and the prior of that particular neighbor. The proposed rule can be thought of as a Bayesian agent who cannot recall the priors based on which other agents make inferences. This learning without recall approach preserves some aspects of the Bayesian inference while being computationally tractable. By establishing a correspondence with a random walk on the network graph, we prove that under the described protocol, agents learn the truth exponentially fast in the almost sure sense. The asymptotic rate is expressed as the sum of the relative entropies between the signal structures of every agent weighted by the stationary distribution of the random walk.