bluuebunny/crossref_metadata_2025 huggingface dataset:
Dural sinus stenting for idiopathic intracranial hypertension: factors associated with hemodynamic failure and management with extended stenting
Authors: Kumpe David A , Seinfeld Joshua , Huang Xianchen , Mei Quelin , Case David E , Roark Christopher D , Subramanian Prem S , Lind Kimberly E , Pelak Victoria S , Bennett Jeffrey L
Published: November 2016

Background

Some patients undergoing dural sinus stenting for idiopathic intracranial hypertension (IIH) develop clinical and hemodynamic failure (recurrence of the pressure gradient) owing to stent-adjacent stenosis.

Objective

To characterize factors associated with hemodynamic failure, and to describe outcomes of patients after repeat stenting.

Materials and methods

We reviewed the initial and follow-up clinical, venographic, and hemodynamic data in 39 patients with IIH treated over 17 years with stenting. Thirty-two had follow-up angiographic and hemodynamic data at 1–99 months (mean 27.6, median 19.5 months). Eight patients were treated with 12 repeat stenting procedures, including extended stenting into the superior sagittal sinus (SSS).

Results

All patients had an initial successful hemodynamic result with the pressure gradient reduced from 10–43 to 0–7 mm Hg. 10/32 patients (31.3%), all women, developed new stenoses in the transverse sinus or posterior SSS above the stent with a recurrent pressure gradient. 7/9 patients with pure extrinsic stenosis of the transverse-sigmoid junction pre-stenting developed new stenoses and hemodynamic failure. All patients with hemodynamic failure who were restented had early and mid-term documented hemodynamic success at 1.7–50 months. They were free from papilledema at 3.8–50 months after the last restenting, and 11.5–99.5 months after initial stent placement (mean 45.3, median 38.5 months).

Conclusions

Pure extrinsic compression of the transverse-sigmoid junction and female gender were strongly associated with hemodynamic failure. Eight patients with hemodynamic failure who were restented had successful control of papilledema, including 4/4 who had extended stenting into the SSS.
Testing unmanned aircraft systems for salmon spawning surveys
Authors: Groves Phillip A. , Alcorn Brad , Wiest Michelle M. , Maselko Jacek M. , Connor William P.
Published: November 2016

Unmanned aircraft systems (UASs) were tested for counting Chinook salmon ( Oncorhynchus tshawytscha) redds as a more accurate, safer alternative to manned helicopter flights. Counting redds from the helicopter was less expensive and time consuming, but of the total redds counted at selected sites with a UAS, an average (± SD) of only 77% ± 14% was counted from the helicopter. A river-wide census of redds was not possible with a UAS because the study area was too large for the single field crew to survey. Simulation analyses were used to compare stratified random sampling (STRS) and sampling proportional to size (PPS) for estimating annual total redd counts from data collected with a UAS. The STRS estimates were more accurate and precise, whereas the PPS estimates, though biased, had 95% CIs that included the observed redd count more frequently. We strongly recommend that researchers conduct simulation analyses to evaluate alternative survey sampling methods if they are considering replacing census counts made from manned aircraft with counts estimated from data collected with a UAS. We conclude that UAS application reduces the risk inherent to manned aircraft flights, but the reduction in risk can come at the cost of estimates of population parameters that can sometimes be inaccurate and lack 95% CI coverage.
Effective models for the multidimensional wave equation in heterogeneous media over long time and numerical homogenization
Authors: Abdulle Assyr , Pouchon Timothée
Published: November 2016

A family of effective equations that capture the long time dispersive effects of wave propagation in heterogeneous media in an arbitrary large periodic spatial domain [Formula: see text] is proposed and analyzed. For a wave equation with highly oscillatory periodic spatial tensors of characteristic length [Formula: see text], we prove that the solution of any member of our family of effective equations is [Formula: see text]-close to the true oscillatory wave over a time interval of length [Formula: see text] in a norm equivalent to the [Formula: see text] norm. We show that the previously derived effective equation in [T. Dohnal, A. Lamacz and B. Schweizer, Bloch-wave homogenization on large time scales and dispersive effective wave equations, Multiscale Model. Simulat. 12 (2014) 488–513] belongs to our family of effective equations. Moreover, while Bloch wave techniques were previously used, we show that asymptotic expansion techniques give an alternative way to derive such effective equations. An algorithm to compute the tensors involved in the dispersive equation and allowing for efficient numerical homogenization methods over long time is proposed.
On flocks influenced by closest neighbors
Authors: Cucker Felipe , Dong Jiu-Gang
Published: November 2016

We prove, both for continuous time and discrete time, results establishing convergence to flocking in a model in which each agent is influenced by only a few closest neighbors. We show unconditional convergence to flocking when this number of closest neighbors is at least half of the population and, otherwise, conditional convergence. That is, convergence to flocking provided the initial positions and velocities satisfy an explicit constraint. We also show that the proportion of neighbors necessary for unconditional convergence, one-half, is sharp. Nothing less will do.
From kinetic theory of multicellular systems to hyperbolic tissue equations: Asymptotic limits and computing
Authors: Outada Nisrine , Vauchelet Nicolas , Akrid Thami , Khaladi Mohamed
Published: November 2016

This paper deals with the analysis of the asymptotic limit toward the derivation of macroscopic equations for a class of equations modeling complex multicellular systems by methods of the kinetic theory. After having chosen an appropriate scaling of time and space, a Chapman–Enskog expansion is combined with a closed, by minimization, technique to derive hyperbolic models at the macroscopic level. The resulting macroscopic equations show how the macroscopic tissue behavior can be described by hyperbolic systems which seem the most natural in this context. We propose also an asymptotic-preserving well-balanced scheme for the one-dimensional hyperbolic model, in the two-dimensional case, we consider a time-splitting method between the conservative part and the source term where the conservative equation is approximated by the Lax–Friedrichs scheme.
Age estimation for the genus Cymbidium (Orchidaceae: Epidendroideae) with implementation of fossil data calibration using molecular markers (ITS2 & matK) and phylogeographic inference from ancestral area reconstruction
Authors: Konhar Ruchishree , Debnath Manish , Marbaniang Jean Valrie , Biswal Devendra Kumar , Tandon Pramod
Published: November 2016

Intercontinental dislocations between tropical regions harboring two-thirds of the flowering plants have always drawn attention from taxonomists and biogeographers. One such family belonging to angiosperms is Orchidaceae with an herbaceous habit and high species diversity in the tropics. Here, we investigate the evolutionary and biogeographical history of the genus Cymbidium, which represents a monophyletic subfamily (Epidendroideae) of the orchids and comprises 50 odd species that are distinctly distributed in tropical to temperate regions. Much is not known about correlations among the level of CAM activity (one of the photosynthetic pathways often regarded as an adaptation to water stress in land plants), habitat, life forms, and phylogenetic relationships of orchids from an evolutionary perspective. A relatively well-resolved and highly supported phylogeny for Cymbidium orchids is reconstructed based on sequence analysis of ITS2 and matK regions from the chloroplast DNA available in public repositories viz. GenBank at NCBI. This study examines a genus level analysis by integrating different molecular matrices to existing fossil data on orchids in a molecular Bayesian relaxed clock employed in BEAST and assessed divergence times for the genus Cymbidium with a focus on evolutionary history of photosynthetic characters. Our study has enabled age estimations (45Ma) as well as ancestral area reconstruction for the genus Cymbidium using BEAST by addition of previously analyzed two internal calibration points.
A Mathematical Model on the Feedback Between Wall Shear Stress and Intimal Hyperplasia
Authors: Goodman Martin E. , Luo X. Y. , Hill N. A.
Published: November 2016

In this paper, we present a mathematical model linking blood flow, shear-dependent endothelium permeability and intimal thickening (hyperplasia) of the arterial wall, which is an initial stage in the development of atherosclerosis. The key concepts are that the intimal layer swells in response to the presence of excess oxidised LDL (OxLDL) in foam cells. The hyperplasia disturbs blood flow, affecting endothelial permeability via the wall shear stress (WSS). These changes produce a feedback mechanism. LDL is transported through the arterial wall by advection and diffusion, and the concentration of LDL at each time step is assumed to be quasi-steady since it equilibrates on a fast time scale. The process is controlled by the slow timescale of the increase in concentration of OxLDL. We consider a section of uniform axisymmetric artery, and impose an initial local injury or ‘hotspot’ of relatively high permeability that enhances the influx of LDL, triggering the development of a bump-shaped lesion. In the absence of further inflammatory processes, the lesion eventually decays back to the homeostatic state. The model is used to explore how the shape of the lesion changes over time, its effect on WSS, influx rates of LDL and the sensitivity of these processes to oxidation parameters. The lesion is shown to propagate downstream driven by regions of high and low WSS on either side of the bump, and it persists for some time after the hotspot has vanished, leaving ample time for further pro-atherogenic processes to develop.
On sums of Fourier coefficients of Maass cusp forms
Authors: Jiang Yujiao , Lü Guangshi
Published: November 2016

Let [Formula: see text] be a Hecke–Maass cusp form, and [Formula: see text] be its [Formula: see text]th Fourier coefficient at the cusp infinity. In this paper, we are interested in the estimation on sums [Formula: see text] for [Formula: see text] We are able to improve previous results by introducing some inequalities concerning Fourier coefficients and other techniques.
Normalizers of congruence groups in SL2(ℝ) and automorphisms of lattices
Authors: Zemel Shaul
Published: November 2016

We determine the normalizer in SL2(ℝ) of several families of congruence subgroups of SL2(ℤ). In addition, we show how these tools can be used to evaluate the groups of automorphisms and the discriminant kernels of a large family of isotropic lattices of signature (2,1).
MoS2-Graphene-Mycosporine-Like Amino Acid Nanocomposite as Photocatalyst
Authors: Kim Hyeong-U , Ha Soohyun , Amalnerkar Dinesh , Kim Sun-Young , Ahn Chisung , Lim Yong Taik , Lee Min-Ho , Moon Byung Joon , Bae Sukang , Moh Sang Hyun , Kulkarni Atul , Kim Taesung
Published: November 2016

In the quest of extending isostructural hybridization approach to organic–inorganic nanocomposite-based photocatalytic systems, a unique strategy of replacing the traditional inorganic semiconductors with naturally produced mycosporine-like amino acids (MAA) is proposed. The main motivation of incorporating MAA in symbiotically configured nanocomposites is with regard to MAA green, nontoxic nature, UV absorption and photostability. Our facile one-pot solvothermal method is to facilitate the amalgamation of MAA and molybdenum disulfide-graphene (MG) composite at the molecular/nanoscale level to endow better photocatalytic functionality. It is observed that the rate of photocatalytic dye degradation of Rhodamine 6G (R6G) becomes consistently enhanced with an incremental increase in the concentration of MAA in MG. The combination of MG-MAA leads up to 81.2% quenching of the PL emission, as compared with MG. Noticeable decrease in PL lifetime from 280 ps (MG) to 77[Formula: see text]ps (MG-MAA) explicitly implies fast charge extraction and transport of the charge carriers.
Bogdanov–Takens bifurcation with codimension three of a predator–prey system suffering the additive Allee effect
Authors: Liu Yanwei , Liu Zengrong , Wang Ruiqi
Published: November 2016

In the present work, research efforts have focused on investigating codimension two and three Bogdanov–Takens bifurcations of a predator–prey system with additive Allee effect. According to the existence conditions of Bogdanov–Takens bifurcation, we give the associated generic unfolding, and derive the dynamical classification in the perturbation parameter plane using some smooth parameter-dependent transformations of coordinate. Moreover, some numerical examples and simulations are performed to complete and illustrate our results.
A Study on the Ventilation Efficiency Improved by Airflow Characteristics of the Axial Fan Installed in Parallel at the Side Wall of the Narrow Exhaust Tower
Authors: Kwon Yong-Il
Published: November 2016

A numerical study has been conducted to simulate airflow and ventilation characteristics in the exhaust tower installed to ventilation of the multi-story underground parking lot. It is the objective of the present study to identify ventilation problems and to suggest the flow direction modifications of the ventilation system with the axial fan to improve ventilation efficiency in the low-rise section of the exhaust tower. Numerical results on SVE4 (scale of ventilation efficiency NO.4) and local mean age of exhaust ports are presented along with the location of axial fan on the direction of swirl flow and the dimension of exhaust tower. Ventilation system modifications on the direction of swirl flow have been suggested from the numerical results in order to prevent the flow interference by airflow discharged from the adjacent stories. The overall ventilation efficiency according to the rotational condition of the axial fans are compared quantitatively using the concept of SVE4 calculated by means of tracer gas pulse method to investigate distribution characteristics of the air discharged from each story among the exhausted air to the two exhaust ports in the narrow exhaust tower.
Two-Dimensional Thermal Shock Problem of Generalized Magneto-Thermoelasticity with a Time-Fractional Heat Conduction Law
Authors: Bachher M. , Sarkar N.
Published: November 2016

An electromagneto-thermoelastic coupled problem for a homogeneous, isotropic, thermally and electrically conducting half-space solid whose surface is subjected to a thermal shock is considered in two-dimensional space. The equations of the theory of generalized electromagneto-thermoelasticity with fractional derivative heat transfer allowing the second sound effects are considered. An initial magnetic field acts parallel to the plane boundary of the half-space. The normal mode analysis and the eigenvalue approach techniques are used to solve the resulting nondimensional coupled field equations for the three theories. Numerical results for the temperature, displacements and thermal stresses distributions are presented graphically and discussed. A comparison is made with the results obtained in the presence and absence of the magnetic field.
Deterministic parallelism via liquid effects
Authors: Kawaguchi Ming , Rondon Patrick , Bakst Alexander , Jhala Ranjit
Published: November 2016

Shared memory multithreading is a popular approach to parallel programming, but also fiendishly hard to get right. We present
Liquid Effects
, a type-and-effect system based on refinement types which allows for fine-grained, low-level, shared memory multi-threading while statically guaranteeing that a program is deterministic. Liquid Effects records the effect of an expression as a for- mula in first-order logic, making our type-and-effect system highly expressive. Further, effects like Read and Write are recorded in Liquid Effects as ordinary uninterpreted predicates, leaving the effect system open to extension by the user. By building our system as an extension to an existing dependent refinement type system, our system gains precise value- and branch-sensitive reasoning about effects. Finally, our system exploits the Liquid Types refinement type inference technique to automatically infer refinement types and effects. We have implemented our type-and-effect checking techniques in CSOLVE, a refinement type inference system for C programs. We demonstrate how CSOLVE uses Liquid Effects to prove the determinism of a variety of benchmarks.
Algorithmic profiling
Authors: Zaparanuks Dmitrijs , Hauswirth Matthias
Published: November 2016

Traditional profilers identify where a program spends most of its resources. They do not provide information about why the program spends those resources or about how resource consumption
would change
for different program inputs. In this paper we introduce the idea of
algorithmic profiling
. While a traditional profiler determines a set of measured cost
values
, an algorithmic profiler determines a cost
function
. It does that by automatically determining the "inputs" of a program, by measuring the program's "cost" for any given input, and by inferring an empirical cost function.
Synthesising graphics card programs from DSLs
Authors: Cartey Luke , Lyngsø Rune , de Moor Oege
Published: November 2016

Over the last five years, graphics cards have become a tempting target for scientific computing, thanks to unrivaled peak performance, often producing a runtime speed-up of x10 to x25 over comparable CPU solutions.

However, this increase can be difficult to achieve, and doing so often requires a fundamental rethink. This is especially problematic in scientific computing, where experts do not want to learn yet another architecture.

In this paper we develop a method for automatically parallelising recursive functions of the sort found in scientific papers. Using a static analysis of the function dependencies we identify sets - partitions - of independent elements, which we use to synthesise an efficient GPU implementation using polyhedral code generation techniques. We then augment our language with DSL extensions to support a wider variety of applications, and demonstrate the effectiveness of this with three case studies, showing significant performance improvement over equivalent CPU methods, and similar efficiency to hand-tuned GPU implementations.
Reagents
Authors: Turon Aaron
Published: November 2016

Efficient communication and synchronization is crucial for fine grained parallelism. Libraries providing such features, while indispensable, are difficult to write, and often cannot be tailored or composed to meet the needs of specific users. We introduce
reagents
, a set of combinators for concisely expressing concurrency algorithms. Reagents scale as well as their hand-coded counterparts, while providing the composability existing libraries lack.
Type-directed completion of partial expressions
Authors: Perelman Daniel , Gulwani Sumit , Ball Thomas , Grossman Dan
Published: November 2016

Modern programming frameworks provide enormous libraries arranged in complex structures, so much so that a large part of modern programming is searching for APIs that surely exist" somewhere in an unfamiliar part of the framework. We present a novel way of phrasing a search for an unknown API: the programmer simply writes an expression leaving holes for the parts they do not know. We call these expressions
partial expressions
. We present an efficient algorithm that produces likely completions ordered by a ranking scheme based primarily on the similarity of the types of the APIs suggested to the types of the known expressions. This gives a powerful language for both API discovery and code completion with a small impedance mismatch from writing code. In an automated experiment on mature C# projects, we show our algorithm can place the intended expression in the top 10 choices over 80% of the time.
Type-directed automatic incrementalization
Authors: Chen Yan , Dunfield Jana , Acar Umut A.
Published: November 2016

Application data often changes slowly or incrementally over time. Since incremental changes to input often result in only small changes in output, it is often feasible to respond to such changes asymptotically more efficiently than by re-running the whole computation. Traditionally, realizing such asymptotic efficiency improvements requires designing problem-specific algorithms known as dynamic or incremental algorithms, which are often significantly more complicated than conventional algorithms to design, analyze, implement, and use. A long-standing open problem is to develop techniques that automatically transform conventional programs so that they correctly and efficiently respond to incremental changes.

In this paper, we describe a significant step towards solving the problem of automatic incrementalization: a programming language and a compiler that can, given a few type annotations describing what can change over time, compile a conventional program that assumes its data to be static (unchanging over time) to an incremental program. Based on recent advances in self-adjusting computation, including a theoretical proposal for translating purely functional programs to self-adjusting programs, we develop techniques for translating conventional Standard ML programs to self-adjusting programs. By extending the Standard ML language, we design a fully featured programming language with higher-order features, a module system, and a powerful type system, and implement a compiler for this language. The resulting programming language, LML, enables translating conventional programs decorated with simple type annotations into incremental programs that can respond to changes in their data correctly and efficiently.

We evaluate the effectiveness of our approach by considering a range of benchmarks involving lists, vectors, and matrices, as well as a ray tracer. For these benchmarks, our compiler incrementalizes existing code with only trivial amounts of annotation. The resulting programs are often asymptotically more efficient, leading to orders of magnitude speedups in practice.
Synchronising C/C++ and POWER
Authors: Sarkar Susmit , Memarian Kayvan , Owens Scott , Batty Mark , Sewell Peter , Maranget Luc , Alglave Jade , Williams Derek
Published: November 2016

Shared memory concurrency relies on synchronisation primitives: compare-and-swap, load-reserve/store-conditional (aka LL/SC), language-level mutexes, and so on. In a sequentially consistent setting, or even in the TSO setting of x86 and Sparc, these have well-understood semantics. But in the very relaxed settings of IBM®, POWER®, ARM, or C/C++, it remains surprisingly unclear exactly what the programmer can depend on.

This paper studies relaxed-memory synchronisation. On the hardware side, we give a clear semantic characterisation of the load-reserve/store-conditional primitives as provided by POWER multiprocessors, for the first time since they were introduced 20 years ago; we cover their interaction with relaxed loads, stores, barriers, and dependencies. Our model, while not officially sanctioned by the vendor, is validated by extensive testing, comparing actual implementation behaviour against an oracle generated from the model, and by detailed discussion with IBM staff. We believe the ARM semantics to be similar.

On the software side, we prove sound a proposed compilation scheme of the C/C++ synchronisation constructs to POWER, including C/C++ spinlock mutexes, fences, and read-modify-write operations, together with the simpler atomic operations for which soundness is already known from our previous work; this is a first step in verifying concurrent algorithms that use load-reserve/store-conditional with respect to a realistic semantics. We also build confidence in the C/C++ model in its own terms, fixing some omissions and contributing to the C standards committee adoption of the C++11 concurrency model.
Dynamic trace-based analysis of vectorization potential of applications
Authors: Holewinski Justin , Ramamurthi Ragavendar , Ravishankar Mahesh , Fauzia Naznin , Pouchet Louis-Noël , Rountev Atanas , Sadayappan P.
Published: November 2016

Recent hardware trends with GPUs and the increasing vector lengths of SSE-like ISA extensions for multicore CPUs imply that effective exploitation of SIMD parallelism is critical for achieving high performance on emerging and future architectures. A vast majority of existing applications were developed without any attention by their developers towards effective vectorizability of the codes. While developers of production compilers such as GNU gcc, Intel icc, PGI pgcc, and IBM xlc have invested considerable effort and made significant advances in enhancing automatic vectorization capabilities, these compilers still cannot effectively vectorize many existing scientific and engineering codes. It is therefore of considerable interest to analyze existing applications to assess the inherent latent potential for SIMD parallelism, exploitable through further compiler advances and/or via manual code changes.

In this paper we develop an approach to infer a program's SIMD parallelization potential by analyzing the dynamic data-dependence graph derived from a sequential execution trace. By considering only the observed run-time data dependences for the trace, and by relaxing the execution order of operations to allow any dependence-preserving reordering, we can detect potential SIMD parallelism that may otherwise be missed by more conservative compile-time analyses. We show that for several benchmarks our tool discovers regions of code within computationally-intensive loops that exhibit high potential for SIMD parallelism but are not vectorized by state-of-the-art compilers. We present several case studies of the use of the tool, both in identifying opportunities to enhance the transformation capabilities of vectorizing compilers, as well as in pointing to code regions to manually modify in order to enable auto-vectorization and performance improvement by existing compilers.
Concurrent data representation synthesis
Authors: Hawkins Peter , Aiken Alex , Fisher Kathleen , Rinard Martin , Sagiv Mooly
Published: November 2016

We describe an approach for synthesizing data representations for concurrent programs. Our compiler takes as input a program written using
concurrent relations
and synthesizes a representation of the relations as sets of cooperating data structures as well as the placement and acquisition of locks to synchronize concurrent access to those data structures. The resulting code is correct by construction: individual relational operations are implemented correctly and the aggregate set of operations is serializable and deadlock free. The relational specification also permits a high-level optimizer to choose the best performing of many possible legal data representations and locking strategies, which we demonstrate with an experiment autotuning a graph benchmark.
Automated synthesis of symbolic instruction encodings from I/O samples
Authors: Godefroid Patrice , Taly Ankur
Published: November 2016

Symbolic execution is a key component of precise binary program analysis tools. We discuss how to automatically boot-strap the construction of a symbolic execution engine for a processor instruction set such as x86, x64 or ARM. We show how to automatically synthesize symbolic representations of individual processor instructions from input/output examples and express them as bit-vector constraints. We present and compare various synthesis algorithms and instruction sampling strategies. We introduce a new synthesis algorithm based on
smart sampling
which we show is one to two orders of magnitude faster than previous synthesis algorithms in our context. With this new algorithm, we can automatically synthesize bit-vector circuits for over 500 x86 instructions (8/16/32-bits, outputs, EFLAGS) using only 6 synthesis templates and in less than two hours using the Z3 SMT solver on a regular machine. During this work, we also discovered several inconsistencies across x86 processors, errors in the x86 Intel spec, and several bugs in previous manually-written x86 instruction handlers.
Chimera
Authors: Lee Dongyoon , Chen Peter M. , Flinn Jason , Narayanasamy Satish
Published: November 2016

Chimera uses a new hybrid program analysis to provide deterministic replay for commodity multiprocessor systems. Chimera leverages the insight that it is easy to provide deterministic multiprocessor replay for data-race-free programs (one can just record non-deterministic inputs and the order of synchronization operations), so if we can somehow transform an arbitrary program to be data-race-free, then we can provide deterministic replay cheaply for that program. To perform this transformation, Chimera uses a sound static data-race detector to find all potential data-races. It then instruments pairs of potentially racing instructions with a weak-lock, which provides sufficient guarantees to allow deterministic replay but does not guarantee mutual exclusion.

Unsurprisingly, a large fraction of data-races found by the static tool are false data-races, and instrumenting them each of them with a weak-lock results in prohibitively high overhead. Chimera drastically reduces this cost from 53x to 1.39x by increasing the granularity of weak-locks without significantly compromising on parallelism. This is achieved by employing a combination of profiling and symbolic analysis techniques that target the sources of imprecision in the static data-race detector. We find that performance overhead for deterministic recording is 2.4% on average for Apache and desktop applications and about 86% for scientific applications.
Polyhedra scanning revisited
Authors: Chen Chun
Published: November 2016

This paper presents a new polyhedra scanning system called CodeGen+ to address the challenge of generating high-performance code for complex iteration spaces resulting from compiler optimization and autotuning systems. The strength of our approach lies in two new algorithms. First, a loop overhead removal algorithm provides precise control of trade-offs between loop overhead and code size based on actual loop nesting depth. Second, an if-statement simplification algorithm further reduces the number of comparisons in the code. These algorithms combined with the expressive power of Presburger arithmetic enable CodeGen+ to support complex optimization strategies expressed in iteration spaces. We compare with the state-of-the-art polyhedra scanning tool CLooG on five loop nest computations, demonstrating that CodeGen+ generates code that is simpler and up to 1.15x faster.
Scalable and precise dynamic datarace detection for structured parallelism
Authors: Raman Raghavan , Zhao Jisheng , Sarkar Vivek , Vechev Martin , Yahav Eran
Published: November 2016

Existing dynamic race detectors suffer from at least one of the following three limitations:

(i)
space
overhead per memory location grows linearly with the number of parallel threads [13], severely limiting the parallelism that the algorithm can handle;

(ii)
sequentialization
: the parallel program must be processed in a sequential order, usually depth-first [12, 24]. This prevents the analysis from scaling with available hardware parallelism, inherently limiting its performance;

(iii)
inefficiency
: even though race detectors with good theoretical complexity exist, they do not admit efficient implem entations and are unsuitable for practical use [4, 18].

We present a new precise dynamic race detector that leverages structured parallelism in order to address these limitations. Our algorithm requires constant space per memory location, works in parallel, and is efficient in practice. We implemented and evaluated our algorithm on a set of 15 benchmarks. Our experimental results indicate an average (geometric mean) slowdown of 2.78x on a 16-core SMP system.
The sequential semantics of producer effect systems
Authors: Tate Ross
Published: November 2016

Effects are fundamental to programming languages. Even the lambda calculus has effects, and consequently the two famous evaluation strategies produce different semantics. As such, much research has been done to improve our understanding of effects. Since Moggi introduced monads for his computational lambda calculus, further generalizations have been designed to formalize increasingly complex computational effects, such as indexed monads followed by layered monads followed by parameterized monads. This succession prompted us to determine the most general formalization possible. In searching for this formalization we came across many surprises, such as the insufficiencies of arrows, as well as many unexpected insights, such as the importance of considering an effect as a small component of a whole system rather than just an isolated feature. In this paper we present our semantic formalization for producer effect systems, which we call a productor, and prove its maximal generality by focusing on only sequential composition of effectful computations, consequently guaranteeing that the existing monadic techniques are specializations of productors.
Abstraction and invariance for algebraically indexed types
Authors: Atkey Robert , Johann Patricia , Kennedy Andrew
Published: November 2016

Reynolds' relational parametricity provides a powerful way to reason about programs in terms of invariance under changes of data representation. A dazzling array of applications of Reynolds' theory exists, exploiting invariance to yield "free theorems", non-inhabitation results, and encodings of algebraic datatypes. Outside computer science, invariance is a common theme running through many areas of mathematics and physics. For example, the area of a triangle is unaltered by rotation or flipping. If we scale a triangle, then we scale its area, maintaining an invariant relationship between the two. The transformations under which properties are invariant are often organised into groups, with the algebraic structure reflecting the composability and invertibility of transformations.

In this paper, we investigate programming languages whose types are indexed by algebraic structures such as groups of geometric transformations. Other examples include types indexed by principals--for information flow security--and types indexed by distances--for analysis of analytic uniform continuity properties. Following Reynolds, we prove a general Abstraction Theorem that covers all these instances. Consequences of our Abstraction Theorem include free theorems expressing invariance properties of programs, type isomorphisms based on invariance properties, and non-definability results indicating when certain algebraically indexed types are uninhabited or only inhabited by trivial programs. We have fully formalised our framework and most examples in Coq.
Static and dynamic semantics of NoSQL languages
Authors: Benzaken Véronique , Castagna Giuseppe , Nguyen Kim , Siméon Jérôme
Published: November 2016

We present a calculus for processing semistructured data that spans differences of application area among several novel query languages, broadly categorized as "NoSQL". This calculus lets users define their own operators, capturing a wider range of data processing capabilities, whilst providing a typing precision so far typical only of primitive hard-coded operators. The type inference algorithm is based on semantic type checking, resulting in type information that is both precise, and flexible enough to handle structured and semistructured data. We illustrate the use of this calculus by encoding a large fragment of Jaql, including operations and iterators over JSON, embedded SQL expressions, and co-grouping, and show how the encoding directly yields a typing discipline for Jaql as it is, namely without the addition of any type definition or type annotation in the code.
High-level separation logic for low-level code
Authors: Jensen Jonas B. , Benton Nick , Kennedy Andrew
Published: November 2016

Separation logic is a powerful tool for reasoning about structured, imperative programs that manipulate pointers. However, its application to unstructured, lower-level languages such as assembly language or machine code remains challenging. In this paper we describe a separation logic tailored for this purpose that we have applied to x86 machine-code programs.

The logic is built from an assertion logic on machine states over which we construct a specification logic that encapsulates uses of frames and step indexing. The traditional notion of Hoare triple is not applicable directly to unstructured machine code, where code and data are mixed together and programs do not in general run to completion, so instead we adopt a continuation-passing style of specification with preconditions alone. Nevertheless, the range of primitives provided by the specification logic, which include a higher-order frame connective, a novel read-only frame connective, and a 'later' modality, support the definition of derived forms to support structured-programming-style reasoning for common cases, in which standard rules for Hoare triples are derived as lemmas. Furthermore, our encoding of scoped assembly-language labels lets us give definitions and proof rules for powerful assembly-language 'macros' such as while loops, conditionals and procedures.

We have applied the framework to a model of sequential x86 machine code built entirely within the Coq proof assistant, including tactic support based on computational reflection.
Towards fully automatic placement of security sanitizers and declassifiers
Authors: Livshits Benjamin , Chong Stephen
Published: November 2016

A great deal of research on sanitizer placement, sanitizer correctness, checking path validity, and policy inference, has been done in the last five to ten years, involving type systems, static analysis and runtime monitoring and enforcement. However, in pretty much all work thus far, the burden of sanitizer placement has fallen on the developer. However, sanitizer placement in large-scale applications is difficult, and developers are likely to make errors, and thus create security vulnerabilities.

This paper advocates a radically different approach: we aim to fully automate the placement of sanitizers by analyzing the ow of tainted data in the program. We argue that developers are better off leaving out sanitizers entirely instead of trying to place them.

This paper proposes a fully automatic technique for sanitizer placement. Placement is static whenever possible, switching to run time when necessary. Run-time taint tracking techniques can be used to track the source of a value, and thus apply appropriate sanitization. However, due to the runtime overhead of run-time taint tracking, our technique avoids it wherever possible.
Checking NFA equivalence with bisimulations up to congruence
Authors: Bonchi Filippo , Pous Damien
Published: November 2016

We introduce bisimulation up to congruence as a technique for proving language equivalence of non-deterministic finite automata. Exploiting this technique, we devise an optimisation of the classical algorithm by Hopcroft and Karp. We compare our approach to the recently introduced antichain algorithms, by analysing and relating the two underlying coinductive proof methods. We give concrete examples where we exponentially improve over antichains; experimental results moreover show non negligible improvements.
Sub-polyhedral scheduling using (unit-)two-variable-per-inequality polyhedra
Authors: Upadrasta Ramakrishna , Cohen Albert
Published: November 2016

Polyhedral compilation has been successful in the design and implementation of complex loop nest optimizers and parallelizing compilers. The algorithmic complexity and scalability limitations remain one important weakness. We address it using sub-polyhedral under-aproximations of the systems of constraints resulting from affine scheduling problems. We propose a sub-polyhedral scheduling technique using (Unit-)Two-Variable-Per-Inequality or (U)TVPI Polyhedra. This technique relies on simple polynomial time algorithms to under-approximate a general polyhedron into (U)TVPI polyhedra. We modify the state-of-the-art PLuTo compiler using our scheduling technique, and show that for a majority of the Polybench (2.0) kernels, the above under-approximations yield polyhedra that are non-empty. Solving the under-approximated system leads to asymptotic gains in complexity, and shows practically significant improvements when compared to a traditional LP solver. We also verify that code generated by our sub-polyhedral parallelization prototype matches the performance of PLuTo-optimized code when the under-approximation preserves feasibility.
The ramifications of sharing in data structures
Authors: Hobor Aquinas , Villard Jules
Published: November 2016

Programs manipulating mutable data structures with intrinsic sharing present a challenge for modular verification. Deep aliasing inside data structures dramatically complicates reasoning in isolation over parts of these objects because changes to one part of the structure (say, the left child of a dag node) can affect other parts (the right child or some of its descendants) that may point into it. The result is that finding intuitive and compositional proofs of correctness is usually a struggle. We propose a compositional proof system that enables local reasoning in the presence of sharing.

While the AI "frame problem" elegantly captures the reasoning required to verify programs without sharing, we contend that natural reasoning about programs with sharing instead requires an answer to a different and more challenging AI problem, the "ramification problem": reasoning about the indirect consequences of actions. Accordingly, we present a RAMIFY proof rule that attacks the ramification problem head-on and show how to reason with it. Our framework is valid in any separation logic and permits sound compositional and local reasoning in the context of both specified and unspecified sharing. We verify the correctness of a number of examples, including programs that manipulate dags, graphs, and overlaid data structures in nontrivial ways.
Toward an Adaptive Screencast Platform
Authors: Hsu Chih-Fan , Fan Ching-Ling , Tsai Tsung-Han , Huang Chun-Ying , Hsu Cheng-Hsin , Chen Kuan-Ta
Published: November 2016

The binding between computing devices and displays is becoming dynamic and adaptive, and screencast technologies enable such binding over wireless networks. In this article, we design and conduct the first detailed measurement study on the performance of the state-of-the-art screencast technologies. Several commercial and one open-source screencast technologies are considered in our detailed analysis, which leads to several insights: (1) there is no single winning screencast technology, indicating room to further enhance the screencast technologies; (2) hardware video encoders significantly reduce the CPU usage at the expense of slightly higher GPU usage and end-to-end delay, and should be adopted in future screencast technologies; (3) comprehensive error resilience tools are needed as wireless communication is vulnerable to packet loss; (4) emerging video codecs designed for screen contents lead to a better Quality of Experience (QoE) of screencast; and (5) rate adaptation mechanisms are critical to avoiding degraded QoE due to network dynamics. As a case study, we propose a nonintrusive yet accurate available bandwidth estimation mechanism. Real experiments demonstrate the practicality and efficiency of our proposed solution. Our measurement methodology, open-source screencast platform, and case study allow researchers and developers to quantitatively evaluate other design considerations, which will lead to optimized screencast technologies.
The Goal Behind the Action
Authors: Papadimitriou Dimitra , Koutrika Georgia , Mylopoulos John , Velegrakis Yannis
Published: November 2016

Human activity is almost always intentional, be it in a physical context or as part of an interaction with a computer system. By understanding why user-generated events are happening and what purposes they serve, a system can offer a significantly improved and more engaging experience. However, goals cannot be easily captured. Analyzing user actions such as clicks and purchases can reveal patterns and behaviors, but understanding the goals behind these actions is a different and challenging issue. Our work presents a unified, multidisciplinary viewpoint for goal management that covers many different cases where goals can be used and techniques with which they can be exploited. Our purpose is to provide a common reference point to the concepts and challenging tasks that need to be formally defined when someone wants to approach a data analysis problem from a goal-oriented point of view. This work also serves as a springboard to discuss several open challenges and opportunities for goal-oriented approaches in data management, analysis, and sharing systems and applications.
Organizing software in a distributed environment
Authors: Lampson Butler W. , Schmidt Eric E.
Published: November 2016

The System Modeller provides automatic support for several different kinds of program development cycle in the Cedar programming system. It handles the daily evolution of a single module or a small group of modules modified by a single person, the assembly of numerous modules into a large system with complex interconnections, and the formal release of a system. The Modeller can also efficiently locate a large number of modules in a big distributed file system, and move them from one machine to another to meet operational requirements or improve performance.
Compiling functional languages for von Neumann machines
Authors: Honschopp U. , Lippe W. M. , Simon F.
Published: November 2016

Functional programming languages based on the lambda calculus provide a powerful programming tool. Much of this power derives from the ability to use higher order functions, that means functions having either functional arguments or a functional result. However, attempts to implement such higher order functions without any restrictions have always been expensive, both in storage and time (e.g. [Bo/We]).

ALGOL-like languages only have functions with functional arguments (e.g. ALGOL 60 or, with some mode restrictions, PASCAL) and a run time stack can be used for managing function and procedure calls. Using Dijkstra's “display-technique” we can obtain a simple and efficient implementation.
Specification and implementation of resilient, atomic data types
Authors: Weihl William , Liskov Barbara
Published: November 2016

A major issue in many applications is how to preserve the consistency of data in the presence of concurrency and hardware failures. We suggest addressing this problem by implementing applications in terms of abstract data types with two properties: Their objects are atomic (they provide serializability and recoverability for activities using them) and resilient (they survive hardware failures with acceptably high probability). We define what it means for abstract data types to be atomic and resilient. We also discuss issues that arise in implementing such types, and describe a particular linguistic mechanism provided in the Argus programming language.
Syntax directed graphical interaction
Authors: Olsen Dan R. , Dempsey Elizabeth P.
Published: November 2016

This paper describes SYNGRAPH (SYNtax) directed GRAPHics) which is a user interface generator for interactive system graphics. This system applies the principles of syntax analysis, parser generation and data abstraction to the development of man-machine interfaces. A great deal of work has been done in the modeling of user interfaces using context-free grammars [Jaco82, Lafu78, Pars79, Reis81, Wass81]. There also has been work done in using parser generation tools for simulating such interactions for prototyping purposes [Hanu80]. The purpose of the system described here is to provide a functional tool for actually implementing graphical user interfaces.