OpenRaiser/Intern-Atlas huggingface dataset:
Generating and evaluating application-specific hardware extensions
Venue: arXiv cs.AR 2014
Year: 2014

Modern platform-based design involves the application-specific extension of embedded processors to fit customer requirements. To accomplish this task, the possibilities offered by recent custom/extensible processors for tuning their instruction set and microarchitecture to the applications of interest have to be exploited. A significant factor often determining the success of this process is the utomation available in application analysis and custom instruction generation. In this paper we present YARDstick, a design automation tool for custom processor development flows that focuses on generating and evaluating application-specific hardware extensions. YARDstick is a building block for ASIP development, integrating application analysis, custom instruction generation and selection with user-defined compiler intermediate representations. In a YARDstick-enabled environment, practical issues in traditional ASIP design are confronted efficiently; the exploration infrastructure is liberated from compiler and simulator idiosyncrasies, since the ASIP designer is empowered with the freedom of specifying the target architectures of choice and adding new implementations of analyses and custom instruction generation/selection methods. To illustrate the capabilities of the YARDstick approach, we present interesting exploration scenarios: quantifying the effect of machine-dependent compiler optimizations and the selection of the target architecture in terms of operation set and memory model on custom instruction generation/selection under different input/output constraints.
Group-Level Graph Visualization Taxonomy
Venue: arXiv cs.HC 2014
Year: 2014

Task taxonomies for graph and network visualizations focus on tasks commonly encountered when analyzing graph connectivity and topology. However, in many application fields such as the social sciences (social networks), biology (protein interaction models), software engineering (program call graphs), connectivity and topology information is intertwined with group, clustering, and hierarchical information. Several recent visualization techniques, such as BubbleSets, LineSets and GMap, make explicit use of grouping and clustering, but evaluating such visualization has been difficult due to the lack of standardized group-level tasks. With this in mind, our goal is to define a new set of tasks that assess group-level comprehension. We propose several types of group-level tasks and provide several examples of each type. Finally, we characterize some of the proposed tasks using the multi-level typology of abstract visualization tasks. We believe that adding group-level tasks to the task taxonomy for graph visualization would make the taxonomy more useful for the recent graph visualization techniques. It would help evaluators define and categorize new tasks, and it would help generalize individual results collected in controlled experiments.
On the Configuration LP for Maximum Budgeted Allocation
Venue: arXiv cs.DS 2014
Year: 2014

We study the Maximum Budgeted Allocation problem, i.e., the problem of selling a set of $m$ indivisible goods to $n$ players, each with a separate budget, such that we maximize the collected revenue. Since the natural assignment LP is known to have an integrality gap of $\frac{3}{4}$, which matches the best known approximation algorithms, our main focus is to improve our understanding of the stronger configuration LP relaxation. In this direction, we prove that the integrality gap of the configuration LP is strictly better than $\frac{3}{4}$, and provide corresponding polynomial time roundings, in the following restrictions of the problem: (i) the Restricted Budgeted Allocation problem, in which all the players have the same budget and every item has the same value for any player it can be sold to, and (ii) the graph MBA problem, in which an item can be assigned to at most 2 players. Finally, we improve the best known upper bound on the integrality gap for the general case from $\frac{5}{6}$ to $2\sqrt{2}-2\approx 0.828$ and also prove hardness of approximation results for both cases.
Opportunistic Spectrum Sharing using Dumb Basis Patterns: The Line-of-Sight Interference Scenario
Venue: arXiv cs.IT 2014
Year: 2014

We investigate a spectrum-sharing system with non-severely faded mutual interference links, where both the secondary-to-primary and primary-to-secondary channels have a Line-of-Sight (LoS) component. Based on a Rician model for the LoS channels, we show, analytically and numerically, that LoS interference hinders the achievable secondary user capacity. This is caused by the poor dynamic range of the interference channels fluctuations when a dominant LoS component exists. In order to improve the capacity of such system, we propose the usage of an Electronically Steerable Parasitic Array Radiator (ESPAR) antenna at the secondary terminals. An ESPAR antenna requires a single RF chain and has a reconfigurable radiation pattern that is controlled by assigning arbitrary weights to M orthonormal basis radiation patterns. By viewing these orthonormal patterns as multiple virtual dumb antennas, we randomly vary their weights over time creating artificial channel fluctuations that can perfectly eliminate the undesired impact of LoS interference. Because the proposed scheme uses a single RF chain, it is well suited for compact and low cost mobile terminals.
MIMO Beamforming in Millimeter-Wave Directional Wi-Fi
Venue: arXiv cs.IT 2014
Year: 2014

Beamforming is indispensable in the operation of 60-GHz millimeter-wave directional multi-gigabit Wi-Fi. Simple power method and its extensions enable the transmitting and receiving antenna arrays to form a beam for single spatial stream. To further improve the spectral efficiency in future 60-GHz directional Wi-Fi, alternating least square (ALS) algorithm can form multiple beams between the transmitter and receiver for multi-input-multi-output (MIMO) operations. For both shared and split MIMO architecture, the ALS beamforming algorithm can be operated in both frequency-flat and frequency-selective channels. In the split architecture, MIMO beamforming approximately maximizes the capacity of the beam-formed MIMO channel.
An Institutional Framework for Heterogeneous Formal Development in UML
Venue: arXiv cs.SE 2014
Year: 2014

We present a framework for formal software development with UML. In contrast to previous approaches that equip UML with a formal semantics, we follow an institution based heterogeneous approach. This can express suitable formal semantics of the different UML diagram types directly, without the need to map everything to one specific formalism (let it be first-order logic or graph grammars). We show how different aspects of the formal development process can be coherently formalised, ranging from requirements over design and Hoare-style conditions on code to the implementation itself. The framework can be used to verify consistency of different UML diagrams both horizontally (e.g., consistency among various requirements) as well as vertically (e.g., correctness of design or implementation w.r.t. the requirements).
The State of Technology for Digital Archiving
Venue: arXiv cs.DL 2014
Year: 2014

The Windsor Study Group on Digital Archiving was commissioned to recommend strategies, policies, and technologies necessary for ensuring the integrity and longevity of electronic publications. The goal of this work is to inform institutions of the challenges and opportunities faced by information stewards in fulfilling their mission of guaranteeing a permanent and authoritative scholarly record in the digital age. This white paper focuses specifically on the technological dimensions of digital archiving. It provides an analysis of the current state of technologies as well as a forecast of how digital archive systems are likely to evolve over the next decade. The thesis of this white paper is that technology does not present a barrier to long term digital archiving, but instead presents an opportunity to harness the current and future power of these technologies to create the architectural underpinnings of a comprehensive digital archiving strategy.
Study and Capacity Evaluation of SISO, MISO and MIMO RF Wireless Communication Systems
Venue: arXiv cs.NI 2014
Year: 2014

The wireless communication systems has gone from different generations from SISO systems to MIMO systems. Bandwidth is one important constraint in wireless communication. In wireless communication, high data transmission rates are essential for the services like tripple play i.e. data, voice and video. At user end the capacity determines the quality of the communication systems. This paper aims to compare the different RF wireless communication systems like SISO, MISO, SIMO and MIMO systems on the capacity basis and explaining the concept as today, the wireless communication has evolved from 2G, 3G to 4G and the companies are fighting to create networks with more and more capacity so that data rates can be increased and customers can be benefitted more. The ultimate goal of wireless communication systems is to create a global personal and multimedia communication without any capacity issues.
Unbiased Black-Box Complexities of Jump Functions
Venue: arXiv cs.NE 2014
Year: 2014

We analyze the unbiased black-box complexity of jump functions with small, medium, and large sizes of the fitness plateau surrounding the optimal solution. Among other results, we show that when the jump size is $(1/2 - \varepsilon)n$, that is, only a small constant fraction of the fitness values is visible, then the unbiased black-box complexities for arities $3$ and higher are of the same order as those for the simple \textsc{OneMax} function. Even for the extreme jump function, in which all but the two fitness values $n/2$ and $n$ are blanked out, polynomial-time mutation-based (i.e., unary unbiased) black-box optimization algorithms exist. This is quite surprising given that for the extreme jump function almost the whole search space (all but a $Θ(n^{-1/2})$ fraction) is a plateau of constant fitness. To prove these results, we introduce new tools for the analysis of unbiased black-box complexities, for example, selecting the new parent individual not by comparing the fitnesses of the competing search points, but also by taking into account the (empirical) expected fitnesses of their offspring.
Adaptive Linear Programming Decoding of Polar Codes
Venue: arXiv cs.IT 2014
Year: 2014

Polar codes are high density parity check codes and hence the sparse factor graph, instead of the parity check matrix, has been used to practically represent an LP polytope for LP decoding. Although LP decoding on this polytope has the ML-certificate property, it performs poorly over a BAWGN channel. In this paper, we propose modifications to adaptive cut generation based LP decoding techniques and apply the modified-adaptive LP decoder to short blocklength polar codes over a BAWGN channel. The proposed decoder provides significant FER performance gain compared to the previously proposed LP decoder and its performance approaches that of ML decoding at high SNRs. We also present an algorithm to obtain a smaller factor graph from the original sparse factor graph of a polar code. This reduced factor graph preserves the small check node degrees needed to represent the LP polytope in practice. We show that the fundamental polytope of the reduced factor graph can be obtained from the projection of the polytope represented by the original sparse factor graph and the frozen bit information. Thus, the LP decoding time complexity is decreased without changing the FER performance by using the reduced factor graph representation.
Using perceptually defined music features in music information retrieval
Venue: arXiv cs.IR 2014
Year: 2014

In this study, the notion of perceptual features is introduced for describing general music properties based on human perception. This is an attempt at rethinking the concept of features, in order to understand the underlying human perception mechanisms. Instead of using concepts from music theory such as tones, pitches, and chords, a set of nine features describing overall properties of the music was selected. They were chosen from qualitative measures used in psychology studies and motivated from an ecological approach. The selected perceptual features were rated in two listening experiments using two different data sets. They were modeled both from symbolic (MIDI) and audio data using different sets of computational features. Ratings of emotional expression were predicted using the perceptual features. The results indicate that (1) at least some of the perceptual features are reliable estimates; (2) emotion ratings could be predicted by a small combination of perceptual features with an explained variance up to 90%; (3) the perceptual features could only to a limited extent be modeled using existing audio features. The results also clearly indicated that a small number of dedicated features were superior to a 'brute force' model using a large number of general audio features.
Relative generalized Hamming weights of one-point algebraic geometric codes
Venue: arXiv cs.IT 2014
Year: 2014

Security of linear ramp secret sharing schemes can be characterized by the relative generalized Hamming weights of the involved codes. In this paper we elaborate on the implication of these parameters and we devise a method to estimate their value for general one-point algebraic geometric codes. As it is demonstrated, for Hermitian codes our bound is often tight. Furthermore, for these codes the relative generalized Hamming weights are often much larger than the corresponding generalized Hamming weights.
A general translation from nested Petri nets into PROMELA
Venue: arXiv cs.LO 2014
Year: 2014

Nested Petri nets have been applied for modeling interaction protocols, mobility, adaptive systems and interorganizational workflows. However, few results have been reported on the use of automated tools for analyzing the behavior of these nets. In this paper we present a general translation from nested Petri nets into PROMELA and explain how some properties of these nets can be studied using SPIN model checker. Besides, we discuss how to deal with the main limitations that may influence SPIN performance when verifying practical examples.
Distributed Collaborative Monitoring in Software Defined Networks
Venue: arXiv cs.NI 2014
Year: 2014

We propose a Distributed and Collaborative Monitoring system, DCM, with the following properties. First, DCM allow switches to collaboratively achieve flow monitoring tasks and balance measurement load. Second, DCM is able to perform per-flow monitoring, by which different groups of flows are monitored using different actions. Third, DCM is a memory-efficient solution for switch data plane and guarantees system scalability. DCM uses a novel two-stage Bloom filters to represent monitoring rules using small memory space. It utilizes the centralized SDN control to install, update, and reconstruct the two-stage Bloom filters in the switch data plane. We study how DCM performs two representative monitoring tasks, namely flow size counting and packet sampling, and evaluate its performance. Experiments using real data center and ISP traffic data on real network topologies show that DCM achieves highest measurement accuracy among existing solutions given the same memory budget of switches.
Keep Your Friends Close and Your Facebook Friends Closer: A Multiplex Network Approach to the Analysis of Offline and Online Social Ties
Venue: arXiv cs.SI 2014
Year: 2014

Social media allow for an unprecedented amount of interaction between people online. A fundamental aspect of human social behavior, however, is the tendency of people to associate themselves with like-minded individuals, forming homogeneous social circles both online and offline. In this work, we apply a new model that allows us to distinguish between social ties of varying strength, and to observe evidence of homophily with regards to politics, music, health, residential sector & year in college, within the online and offline social network of 74 college students. We present a multiplex network approach to social tie strength, here applied to mobile communication data - calls, text messages, and co-location, allowing us to dimensionally identify relationships by considering the number of communication channels utilized between students. We find that strong social ties are characterized by maximal use of communication channels, while weak ties by minimal use. We are able to identify 75% of close friendships, 90% of weaker ties, and 90% of Facebook friendships as compared to reported ground truth. We then show that stronger ties exhibit greater profile similarity than weaker ones. Apart from high homogeneity in social circles with respect to political and health aspects, we observe strong homophily driven by music, residential sector and year in college. Despite Facebook friendship being highly dependent on residence and year, exposure to less homogeneous content can be found in the online rather than the offline social circles of students, most notably in political and music aspects.
Dual-structure Data Center Multicast Using Software Defined Networking
Venue: arXiv cs.NI 2014
Year: 2014

Data center applications use multicast as an effective method to reduce bandwidth cost. However, traditional multicast protocols designed for IP networks are usually bottlenecked by the limited state capacity on switches. In this paper, we propose a scalable multicast solution on fat tree networks based on the observation that data center multicast traffic has strong heterogeneity. We propose to remove the multicast management logic from switches and use the SDN controller to manage multicast groups. The proposed Dual-structure Multicast (DuSM) determines elephant and mice groups according to their traffic amounts and treats them separately. For each elephant group, the controller installs multicast state to maintain multiple shared trees and the group traffic will be balanced evenly among the trees to avoid congestion. For mice groups, the controller applies state-free mutlicast that trades bandwidth capacity for state capacity, such as multicast-to-unicast translation. Our experiments using real multicast traffic data show that the number of groups DuSM supports can be 300% of that of IP multicast. DuSM also achieves traffic balance among links.
Performance of Differential Amplify-and-Forward Relaying in Multi-Node Wireless Communications
Venue: arXiv cs.IT 2014
Year: 2014

This paper is concerned with the performance of differential amplify-and-forward (D-AF) relaying for multi-node wireless communications over time-varying Rayleigh fading channels. A first-order auto-regressive model is utilized to characterize the time-varying nature of the channels. Based on the secondorder statistical properties of the wireless channels, a new set of combining weights is proposed for signal detection at the destination. Expression of pair-wise error probability (PEP) is provided and used to obtain the approximated total average bit error probability (BER). It is shown that the performance of the system is related to the auto-correlation of the direct and cascaded channels and an irreducible error floor exists at high signal-to-noise ratio (SNR). The new weights lead to a better performance when compared to the conventional combining scheme. Computer simulation is carried out in different scenarios to support the analysis.
Short Message Noisy Network Coding with Rate Splitting
Venue: arXiv cs.IT 2014
Year: 2014

Short message noisy network coding with rate splitting (SNNC-RS) encoding strategy is presented. It has been shown by Hou and Kramer that mixed cooperative strategies in which relays in favorable positions perform decode-and-forward (DF) and the rest of the relays perform short message noisy network coding (SNNC) can outperform noisy network coding (NNC). Our proposed strategy further improves the rate performance of such mixed SNNC-DF cooperative strategy. In the proposed scheme, superposition coding is incorporated into the SNNC encoding in order to facilitate partial interference cancellation at DF relays, thereby increasing the overall rate. To demonstrate gains of the proposed SNNC-RS strategy, the achievable rate is analyzed for the discrete memoryless two-relay network with one DF relay and one SNNC-RS relay and compared to the case without rate-splitting. The obtained rate is evaluated in the Gaussian two-relay network and gains over the rate achieved without rate splitting are demonstrated.
On redundancy of memoryless sources over countable alphabets
Venue: arXiv cs.IT 2014
Year: 2014

The minimum average number of bits need to describe a random variable is its entropy, assuming knowledge of the underlying statistics On the other hand, universal compression supposes that the distribution of the random variable, while unknown, belongs to a known set $\cal P$ of distributions. Such universal descriptions for the random variable are agnostic to the identity of the distribution in $\cal P$. But because they are not matched exactly to the underlying distribution of the random variable, the average number of bits they use is higher, and the excess over the entropy used is the "redundancy". This formulation is fundamental to problems not just in compression, but also estimation and prediction and has a wide variety of applications from language modeling to insurance. In this paper, we study the redundancy of universal encodings of strings generated by independent identically distributed (iid) sampling from a set $\cal P$ of distributions over a countable support. We first show that if describing a single sample from $\cal P$ incurs finite redundancy, then $\cal P$ is tight but that the converse does not always hold. If a single sample can be described with finite worst-case-regret (a more stringent formulation than redundancy above), then it is known that length-$n$ iid samples only incurs a diminishing (in $n$) redundancy per symbol as $n$ increases. However, we show it is possible that a collection $\cal P$ incurs finite redundancy, yet description of length-$n$ iid samples incurs a constant redundancy per symbol encoded. We then show a sufficient condition on $\cal P$ such that length-$n$ iid samples will incur diminishing redundancy per symbol encoded.
Algorithm and proof as Ω-invariance and transfer: A new model of computation in nonstandard analysis
Venue: arXiv cs.LO 2014
Year: 2014

We propose a new model of computation based on nonstandard analysis. Intuitively, the role of "algorithm" is played by a new notion of finite procedure, called Omega-invariance and inspired by physics, from nonstandard analysis. Moreover, the role of 'proof' is taken up by the Transfer Principle from nonstandard analysis. We obtain a number of results in Constructive Reverse Mathematics to illustrate the tight correspondence to Errett Bishop's Constructive Analysis and the associated Constructive Reverse Mathematics.
The probability of non-confluent systems
Venue: arXiv cs.LO 2014
Year: 2014

We show how to provide a structure of probability space to the set of execution traces on a non-confluent abstract rewrite system, by defining a variant of a Lebesgue measure on the space of traces. Then, we show how to use this probability space to transform a non-deterministic calculus into a probabilistic one. We use as example Lambda+, a recently introduced calculus defined through type isomorphisms.