OpenRaiser/Intern-Atlas huggingface dataset:
Routability in 3D IC Design: Monolithic 3D vs. Skybridge 3D CMOS
Venue: arXiv cs.ET 2016
Year: 2016

Conventional 2D CMOS technology is reaching fundamental scaling limits, and interconnect bottleneck is dominating integrated circuit (IC) power and performance. While 3D IC technologies using Through Silicon Via or Monolithic Inter-layer Via alleviate some of these challenges, they follow a similar layout and routing mindset as 2D CMOS. This is insufficient to address routing requirements in high-density 3D ICs and even causes severe routing congestion at large-scale designs, limiting their benefits and scalability. Skybridge is a recently proposed fine-grained 3D IC fabric relying on vertical nanowires that presents a paradigm shift for scaling, while addressing associated 3D connectivity and manufacturability challenges. Skybridge's core fabric components enable a new 3D IC design approach with vertically-composed logic gates, and provide a greater degree of routing flexibility compared to conventional 2D and 3D ICs leading to much larger benefits and future scalability. In this paper, we present a methodology using relevant metrics to evaluate and quantify the benefits of Skybridge vs. state-of-the-art transistor-level monolithic 3D IC (T-MI) and 2D in terms of routability and its impact on large-scale circuits. This is enabled by a new device-to-system design flow with commercial CAD tools that we developed for large-scale Skybridge IC designs in 16nm node. Evaluation for standard benchmark circuits shows that Skybridge yields up to 1.6x lower routing demand against T-MI with no routing congestion (routing demand to resource ratio < 1) at all metal layers. This 3D routability in conjunction with compact vertical gate design in Skybridge translate into benefits of up to 3x lower power and 11x higher density over 2D CMOS, while TLM-3DIC approach only has up to 22% power saving and 2x density improvement over 2D CMOS.
Usage of Cloud Computing Simulators and Future Systems For Computational Research
Venue: arXiv cs.DC 2016
Year: 2016

Cloud Computing is an Internet based computing, whereby shared resources, software and information, are provided to computers and devices on demand, like the electricity grid. Currently, IaaS (Infrastructure as a Service), PaaS (Platform as a Service) and SaaS (Software as a Service) are used as a business model for Cloud Computing. Nowadays, the adoption and deployment of Cloud Computing is increasing in various domains, forcing researchers to conduct research in the area of Cloud Computing globally. Setting up the research environment is critical for the researchers in the developing countries to evaluate the research outputs. Currently, modeling, simulation technology and access of resources from various university data centers has become a useful and powerful tool in cloud computing research. Several cloud simulators have been specifically developed by various universities to carry out Cloud Computing research, including CloudSim, SPECI, Green Cloud and Future Systems (the Indiana University machines India, Bravo, Delta, Echo and Foxtrot) supports leading edge data science research and a broad range of computing-enabled education as well as integration of ideas from cloud and HPC systems. In this paper, the features, suitability, adaptability and the learning curve of the existing Cloud Computing simulators and Future Systems are reviewed and analyzed.
Exploiting Social Tie Structure for Cooperative Wireless Networking: A Social Group Utility Maximization Framework
Venue: arXiv cs.NI 2016
Year: 2016

In this paper, we develop a social group utility maximization (SGUM) framework for cooperative wireless networking that takes into account both social relationships and physical coupling among users. We show that this framework provides rich modeling flexibility and spans the continuum between non-cooperative game and network utility maximization (NUM) -- two traditionally disjoint paradigms for network optimization. Based on this framework, we study three important applications of SGUM, in database assisted spectrum access, power control, and random access control, respectively. For the case of database assisted spectrum access, we show that the SGUM game is a potential game and always admits a socially-aware Nash equilibrium (SNE). We develop a randomized distributed spectrum access algorithm that can asymptotically converge to the optimal SNE, derive upper bounds on the convergence time, and also quantify the trade-off between the performance and convergence time of the algorithm. We further show that the performance gap of SNE by the algorithm from the NUM solution decreases as the strength of social ties among users increases and the performance gap is zero when the strengths of social ties among users reach the maximum values. For the cases of power control and random access control, we show that there exists a unique SNE. Furthermore, as the strength of social ties increases from the minimum to the maximum, a player's SNE strategy migrates from the Nash equilibrium strategy in a standard non-cooperative game to the socially-optimal strategy in network utility maximization. Furthermore, we show that the SGUM framework can be generalized to take into account both positive and negative social ties among users and can be a useful tool for studying network security problems.
Comparative Analysis of Initial Access Techniques in 5G mmWave Cellular Networks
Venue: arXiv cs.NI 2016
Year: 2016

The millimeter wave frequencies (roughly above 10 GHz) offer the availability of massive bandwidth to greatly increase the capacity of fifth generation (5G) cellular wireless systems. However, to overcome the high isotropic pathloss at these frequencies, highly directional transmissions will be required at both the base station (BS) and the mobile user equipment (UE) to establish sufficient link budget in wide area networks. This reliance on directionality has important implications for control layer procedures. Initial access in particular can be significantly delayed due to the need for the BS and the UE to find the initial directions of transmission. This paper provides a survey of several recently proposed techniques. Detection probability and delay analysis is performed to compare various techniques including exhaustive and iterative search. We show that the optimal strategy depends on the target SNR regime.
An analysis of visitors' length of stay through noninvasive Bluetooth monitoring in the Louvre Museum
Venue: arXiv cs.CY 2016
Year: 2016

Art Museums traditionally employ observations and surveys to enhance their knowledge of visitors' behavior and experience. However, these approaches often produce spatially and temporally limited empirical evidence and measurements. Only recently has the ubiquity of digital technologies revolutionized the ability to collect data on human behavior. Consequently, the greater availability of large-scale datasets based on quantifying visitors' behavior provides new opportunities to apply computational and comparative analytical techniques. In this paper, we attempt to analyze visitors' behavior in the Louvre Museum from anonymized longitudinal datasets collected from noninvasive Bluetooth sensors. We examine visitors' length of stay in the museum and consider this relationship with occupation density around artwork. This data analysis increases the knowledge and understanding of museum professionals related to the experience of visitors.
Improving practical sensitivity of energy optimized wake-up receivers: proof of concept in 65nm CMOS
Venue: arXiv cs.IT 2016
Year: 2016

We present a high performance low-power digital base-band architecture, specially designed for an energy optimized duty-cycled wake-up receiver scheme. Based on a careful wake-up beacon design, a structured wake-up beacon detection technique leads to an architecture that compensates for the implementation loss of a low-power wake-up receiver front-end at low energy and area costs. Design parameters are selected by energy optimization and the architecture is easily scalable to support various network sizes. Fabricated in 65nm CMOS, the digital base-band consumes 0.9uW (V_DD=0.37V) in sub-threshold operation at 250kbps, with appropriate 97% wake-up beacon detection and 0.04% false alarm probabilities. The circuit is fully functional at a minimum V_DD of 0.23V at f_max=5kHz and 0.018uW power consumption. Based on these results we show that our digital base-band can be used as a companion to compensate for front-end implementation losses resulting from the limited wake-up receiver power budget at a negligible cost. This implies an improvement of the practical sensitivity of the wake-up receiver, compared to what is traditionally reported.
Automatic Parameter Derivations in k2U Framework
Venue: arXiv cs.DS 2016
Year: 2016

We have recently developed a general schedulability test framework, called k2U, which can be applied to deal with a large variety of task models that have been widely studied in real-time embedded systems. The k2U framework provides several means for the users to convert arbitrary schedulability tests (regardless of platforms and task models) into polynomial-time tests with closed mathematical expressions. However, the applicability (as well as the performance) of the k2U framework relies on the users to index the tasks properly and define certain constant parameters. This report describes how to automatically index the tasks properly and derive those parameters. We will cover several typical schedulability tests in real-time systems to explain how to systematically and automatically derive those parameters required by the k2U framework. This automation significantly empowers the k2U framework to handle a wide range of classes of real-time execution platforms and task models, including uniprocessor scheduling, multiprocessor scheduling, self-suspending task systems, real-time tasks with arrival jitter, services and virtualizations with bounded delays, etc.
Networks of Complements
Venue: arXiv cs.GT 2016
Year: 2016

We consider a network of sellers, each selling a single product, where the graph structure represents pair-wise complementarities between products. We study how the network structure affects revenue and social welfare of equilibria of the pricing game between the sellers. We prove positive and negative results, both of "Price of Anarchy" and of "Price of Stability" type, for special families of graphs (paths, cycles) as well as more general ones (trees, graphs). We describe best-reply dynamics that converge to non-trivial equilibrium in several families of graphs, and we use these dynamics to prove the existence of approximately-efficient equilibria.
Differentially Private Bayesian Programming
Venue: arXiv cs.PL 2016
Year: 2016

We present PrivInfer, an expressive framework for writing and verifying differentially private Bayesian machine learning algorithms. Programs in PrivInfer are written in a rich functional probabilistic programming language with constructs for performing Bayesian inference. Then, differential privacy of programs is established using a relational refinement type system, in which refinements on probability types are indexed by a metric on distributions. Our framework leverages recent developments in Bayesian inference, probabilistic programming languages, and in relational refinement types. We demonstrate the expressiveness of PrivInfer by verifying privacy for several examples of private Bayesian inference.
Symbolic-Numeric Tools for Analytic Combinatorics in Several Variables
Venue: arXiv cs.SC 2016
Year: 2016

Analytic combinatorics studies the asymptotic behaviour of sequences through the analytic properties of their generating functions. This article provides effective algorithms required for the study of analytic combinatorics in several variables, together with their complexity analyses. Given a multivariate rational function we show how to compute its smooth isolated critical points, with respect to a polynomial map encoding asymptotic behaviour, in complexity singly exponential in the degree of its denominator. We introduce a numerical Kronecker representation for solutions of polynomial systems with rational coefficients and show that it can be used to decide several properties (0 coordinate, equal coordinates, sign conditions for real solutions, and vanishing of a polynomial) in good bit complexity. Among the critical points, those that are minimal---a property governed by inequalities on the moduli of the coordinates---typically determine the dominant asymptotics of the diagonal coefficient sequence. When the Taylor expansion at the origin has all non-negative coefficients (known as the `combinatorial case') and under regularity conditions, we utilize this Kronecker representation to determine probabilistically the minimal critical points in complexity singly exponential in the degree of the denominator, with good control over the exponent in the bit complexity estimate. Generically in the combinatorial case, this allows one to automatically and rigorously determine asymptotics for the diagonal coefficient sequence. Examples obtained with a preliminary implementation show the wide applicability of this approach.
Token Sliding on Chordal Graphs
Venue: arXiv cs.DM 2016
Year: 2016

Let I be an independent set of a graph G. Imagine that a token is located on any vertex of I. We can now move the tokens of I along the edges of the graph as long as the set of tokens still defines an independent set of G. Given two independent sets I and J, the Token Sliding problem consists in deciding whether there exists a sequence of independent sets which transforms I into J so that every pair of consecutive independent sets of the sequence can be obtained via a token move. This problem is known to be PSPACE-complete even on planar graphs. In 2014, Demaine et al. asked whether the Token Sliding reconfiguration problem is polynomial time solvable on interval graphs and more generally in chordal graphs. Yamada and Uehara showed in 2016 that a polynomial time transformation can be found in proper interval graphs. In this paper, we answer the first question of Demaine et al. and generalize the result of Yamada and Uehara by showing that we can decide in polynomial time whether two independent sets of an interval graph are in the same connected component. Moveover, we answer similar questions by showing that: (i) determining if there exists a token sliding transformation between every pair of k-independent sets in an interval graph can be decided in polynomial time; (ii) deciding this problem becomes co-NP-hard and even co-W[2]-hard (parameterized by the size of the independent set) on split graphs, a sub-class of chordal graphs.
Age-of-Information in the Presence of Error
Venue: arXiv cs.PF 2016
Year: 2016

We consider the peak age-of-information (PAoI) in an M/M/1 queueing system with packet delivery error, i.e., update packets can get lost during transmissions to their destination. We focus on two types of policies, one is to adopt Last-Come-First-Served (LCFS) scheduling, and the other is to utilize retransmissions, i.e., keep transmitting the most recent packet. Both policies can effectively avoid the queueing delay of a busy channel and ensure a small PAoI. Exact PAoI expressions under both policies with different error probabilities are derived, including First-Come-First-Served (FCFS), LCFS with preemptive priority, LCFS with non-preemptive priority, Retransmission with preemptive priority, and Retransmission with non-preemptive priority. Numerical results obtained from analysis and simulation are presented to validate our results.
CAIR: Using Formal Languages to Study Routing, Leaking, and Interception in BGP
Venue: arXiv cs.NI 2016
Year: 2016

The Internet routing protocol BGP expresses topological reachability and policy-based decisions simultaneously in path vectors. A complete view on the Internet backbone routing is given by the collection of all valid routes, which is infeasible to obtain due to information hiding of BGP, the lack of omnipresent collection points, and data complexity. Commonly, graph-based data models are used to represent the Internet topology from a given set of BGP routing tables but fall short of explaining policy contexts. As a consequence, routing anomalies such as route leaks and interception attacks cannot be explained with graphs. In this paper, we use formal languages to represent the global routing system in a rigorous model. Our CAIR framework translates BGP announcements into a finite route language that allows for the incremental construction of minimal route automata. CAIR preserves route diversity, is highly efficient, and well-suited to monitor BGP path changes in real-time. We formally derive implementable search patterns for route leaks and interception attacks. In contrast to the state-of-the-art, we can detect these incidents. In practical experiments, we analyze public BGP data over the last seven years.
A Necessary and Sufficient Condition for Local Maxima of Polynomial Modulus Over Unit Disc
Venue: arXiv cs.NA 2016
Year: 2016

An important quantity associated with a complex polynomial $p(z)$ is $\Vert p \Vert_\infty$, the maximum of its modulus over the unit disc $D$. We prove, $z_* \in D$ is a local maximum of $|p(z)|$ if and only if $a_*$ satisfies, $z_*=p(z_*)|p'(z_*)|/p'(z_*)|p(z_*)|$, i.e. it is proportional to its corresponding Newton direction. This explicit formula gives rise to novel iterative algorithms for computing $\Vert p \Vert_\infty$. We describe two such algorithms, including a Newton-like method and present some visualization of their performance.
The Capacity of Robust Private Information Retrieval with Colluding Databases
Venue: arXiv cs.IT 2016
Year: 2016

Private information retrieval (PIR) is the problem of retrieving as efficiently as possible, one out of $K$ messages from $N$ non-communicating replicated databases (each holds all $K$ messages) while keeping the identity of the desired message index a secret from each individual database. The information theoretic capacity of PIR (equivalently, the reciprocal of minimum download cost) is the maximum number of bits of desired information that can be privately retrieved per bit of downloaded information. $T$-private PIR is a generalization of PIR to include the requirement that even if any $T$ of the $N$ databases collude, the identity of the retrieved message remains completely unknown to them. Robust PIR is another generalization that refers to the scenario where we have $M \geq N$ databases, out of which any $M - N$ may fail to respond. For $K$ messages and $M\geq N$ databases out of which at least some $N$ must respond, we show that the capacity of $T$-private and Robust PIR is $\left(1+T/N+T^2/N^2+\cdots+T^{K-1}/N^{K-1}\right)^{-1}$. The result includes as special cases the capacity of PIR without robustness ($M=N$) or $T$-privacy constraints ($T=1$).
A heuristic algorithm for a single vehicle static bike sharing rebalancing problem
Venue: arXiv cs.AI 2016
Year: 2016

The static bike rebalancing problem (SBRP) concerns the task of repositioning bikes among stations in self-service bike-sharing systems. This problem can be seen as a variant of the one-commodity pickup and delivery vehicle routing problem, where multiple visits are allowed to be performed at each station, i.e., the demand of a station is allowed to be split. Moreover, a vehicle may temporarily drop its load at a station, leaving it in excess or, alternatively, collect more bikes from a station (even all of them), thus leaving it in default. Both cases require further visits in order to meet the actual demands of such station. This paper deals with a particular case of the SBRP, in which only a single vehicle is available and the objective is to find a least-cost route that meets the demand of all stations and does not violate the minimum (zero) and maximum (vehicle capacity) load limits along the tour. Therefore, the number of bikes to be collected or delivered at each station should be appropriately determined in order to respect such constraints. We propose an iterated local search (ILS) based heuristic to solve the problem. The ILS algorithm was tested on 980 benchmark instances from the literature and the results obtained are quite competitive when compared to other existing methods. Moreover, our heuristic was capable of finding most of the known optimal solutions and also of improving the results on a number of open instances.
Block Shelves for Visual Programming Languages
Venue: arXiv cs.HC 2016
Year: 2016

The blocks editor, such as the editor in Scratch, is widely applied for visual programming languages (VPL) nowadays. Despite it's friendly for non-programmers, it exists three main limitations while displaying block codes: (1) the readability, (2) the program structure, and (3) the re-use. To cope with these issues, we introduce a novel formatting tool, block shelves, into the editor for organizing blocks. A user could utilize shelves to constitute a user-defined structure for the VPL projects. Based on the experiment results, block shelves improves the block code navigating and searching significantly. Besides, for achieving code re-use, users could use shelf export/import to share/re-use their block codes between projects in the file format of eXtensible Markup Language (xml.) All functions were demonstrated on MIT App inventor 2, while all modifications were made in Google Blockly.
On the Mathematics of Data Centre Network Topologies
Venue: arXiv cs.DM 2016
Year: 2016

The theory of combinatorial designs has recently been used in order to build switch-centric data centre networks incorporating a large number of servers, in comparison with the popular Fat-Tree data centre network. The construction employed, called the 3-step method, revolves around an appropriately chosen (but relatively small) bipartite graph and a transversal design. In this paper, we clarify and extend these recent results. In particular, we prove the following path diversity results: in a one-to-one context, we prove that in these data centre networks there are pairwise link-disjoint paths joining all the servers adjacent to some switch with all the servers adjacent to any other switch so that we retain control of the path lengths (these results are optimal in terms of the numbers of paths constructed and we prove that we have a wide choice of bipartite graph and transversal design to which we can apply the 3-step method); and in a one-to-many context, we prove that there are pairwise link-disjoint paths from all the servers adjacent to some switch to any identically-sized collection of target servers where these target servers need not be adjacent to the same switch (again, we keep control of the path lengths). Our constructions and analysis are undertaken on bipartite graphs with the applications to data centre networks being easily derived. Our results strengthen the overall competitiveness of data centre networks constructed using the 3-step method, in comparison with Fat-Tree data centre networks, and, more generally, show the potential of results and methodologies from combinatorics to data centre network design.
The Role of communication and network technologies in vehicular applications
Venue: arXiv cs.NI 2016
Year: 2016

Vehicular networks attract a lot of attention in the research world. Novel vehicular applications need a suitable communication channel in order to extend in-vehicle capabilities and, be aware about surrounding events. However, these networks present some proprieties, such as high mobility or specific topologies. These properties affect the performances of applications and more effort should be directed to identify the final necessities of the network. Few works deal with application requirements which should be considered when vehicular services are designed. In this chapter this gap is filled, proposing an analysis of application requirements which considers available technologies for physical/MAC and network layers. This study contains key factors which must be taken into account not only at the designing stage of the vehicular network, but also when applications are evaluated.