bluuebunny/crossref_metadata_2025 huggingface dataset:
Associations between participation in organised physical activity in the school or community outside school hours and neighbourhood play with child physical activity and sedentary time: a cross-sectional analysis of primary school-aged children from the UK
Authors: Jago Russell , Macdonald-Wallis Corrie , Solomon-Moore Emma , Thompson Janice, L. , Lawlor Debbie, A. , Sebire Simon, J.
Published: September 2017

Objectives

To assess the extent to which participation in organised physical activity in the school or community outside school hours and neighbourhood play was associated with children’s physical activity and sedentary time.

Design

Cross-sectional study.

Setting

Children were recruited from 47 state-funded primary schools in South West England.

Participants

1223 children aged 8–9 years old.

Outcome measures

Accelerometer-assessed moderate-to-vigorous-intensity physical activity (MVPA) and sedentary time.

Methods

Children wore an accelerometer, and the mean minutes of MVPA and sedentary time per day were derived. Children reported their attendance at organised physical activity in the school or community outside school hours and neighbourhood play using a piloted questionnaire. Cross-sectional linear and logistic regression were used to examine if attendance frequency at each setting (and all settings combined) was associated with MVPA and sedentary time. Multiple imputation methods were used to account for missing data and increase sample size.

Results

Children who attended clubs at school 3–4 days per week obtained an average of 7.58 (95% CI 2.7 to 12.4) more minutes of MVPA per day than children who never attended. Participation in the three other non-school-based activities was similarly associated with MVPA. Evidence for associations with sedentary time was generally weaker. Associations were similar in girls and boys. When the four different contexts were combined, each additional one to two activities participated in per week increased participants’ odds (OR: 1.18, 95% CI 1.12 to 1.25) of meeting the government recommendations for 60 min of MVPA per day.

Conclusion

Participating in organised physical activity at school and in the community is associated with greater physical activity and reduced sedentary time among both boys and girls. All four types of activity contribute to overall physical activity, which provides parents with a range of settings in which to help their child be active.
Preoperative Staging of Cholangiocarcinoma and Biliary Carcinoma using 18F-Fluorodeoxyglucose Positron Emission Tomography: A Meta-Analysis
Authors: Hu Jing-Hong , Tang Jui-hsiang , Lin Cheng-Hui , Chu Yin-Yi , Liu Nai-Jen
Published: September 2017

This meta-analysis was performed to determine the diagnostic accuracy of 18F-fluorodeoxyglucose positron emission tomography (18F-FDG-PET) in assessing primary cholangiocarcinoma (CCA) and CCA with lymph node and distant metastasis. A literature search for studies reporting the use of 18F-FDG-PET for preoperative work-up/staging in patients with CCA was performed. Diagnostic OR (DOR) was used as an index of diagnostic performance of FDG-PET/CT in predicting primary CCA, lymph node metastases, and distant metastases. The pooled DOR was 9.34 (95% CI 4.27 to 20.42) and the area under the summary receiver operating characteristic (SROC) curve was 0.8643 (SE=0.0362), indicating overall good discriminatory test performance in predicting primary CCA. Subgroup analyses based on the primary tumor site showed better diagnostic performance for intrahepatic CCA (DOR=54.44, 95% CI 13.44 to 220.49), both intrahepatic and extrahepatic CCA (DOR=32.96, 95% CI 1.41 to 768.80) and gallbladder cancer (DOR=12.93, 95% CI 1.97 to 84.80), than for extrahepatic CCA (DOR=2.55, 95% CI 0.71 to 9.20) and hilar CCA (DOR=2.75, 95% CI 0.17 to 43.72). The pooled DOR for the prediction of lymph nodes metastases in 10 studies was 11.34 (95% CI 4.79 to 26.80), with moderate heterogeneity (Cochran Q=15.14, p=0.0872, I2=40.5%). The area under the SROC curve was 0.8584 (SE=0.0729). In conclusion, 18F-FDG-PET and PET/CT were found to be accurate in the evaluation of primary tumors, lymph node metastasis, and distant metastasis in patients with CCA.
Public reason and the limited right to conscientious objection: a response to Magelssen
Authors: Greenblum Jake
Published: September 2017

In a recent article for this journal, Morten Magelssen argues that the right to conscientious objection in healthcare is grounded in the moral integrity of healthcare professionals, a good for both professionals and society. In this paper, I argue that there is no right to conscientious objection in healthcare, at least as Magelssen conceives of it. Magelssen’s conception of the right to conscientious objection is too expansive in nature. Although I will assume that there is a right to conscientious objection, it does not extend to objections that are purely religious in nature.iThus, this right is considerably more restricted than Magelssen thinks. In making my case, I draw on John Rawls’s later work in arguing for the claim that conscientious objection based on purely religious considerations fails to benefit society in the appropriate way.
Remote myocardial injury: the protective role of fluoxetine
Authors: Yaman Onur M. , Erman Hayriye , Guner Ibrahim , Tok Olgu Enis , Pala Mukaddes , Esrefoglu Mukaddes , Gelisgen Remise , Uzun Hafize , Aksu Ugur , Yelmen Nermin , Sahin Gulderen
Published: September 2017

Aortic cross-clamping-induced ischemia–reperfusion (IR) is an important factor in the development of postoperative acute cardiac injury following abdominal aortic surgery. We investigated the possible anti-oxidant/anti-inflammatory effects of fluoxetine (FLX), which is used widely as a preoperative anxiolytic on cardiac injury induced by IR of the infrarenal abdominal aorta. FLX was administered to IR-performed (60 min of ischemia and 120 min of reperfusion) rats for 3 days, once daily at 20 mg/kg i.p. dosage. Results were compared to control and non-FLX-treated IR-performed rats. Serum creatine kinase (CK) and CK-MB levels, lipid hydroperoxide, thiobarbituric acid reactive substances, and pro-oxidant/anti-oxidant balance levels in the IR group were significantly higher whereas superoxide dismutase activity, glutathione, and ferric reducing/anti-oxidant power levels were lower than for the control. IR also increased myeloperoxidase activity, tumor necrosis factor-α, interleukin-1β, and interleukin-6 and decreased interleukin-10 levels. FLX decreased CK, CK-MB, lipid hydroperoxide, thiobarbituric acid reactive substances, and pro-oxidant/anti-oxidant balance levels while increasing superoxide dismutase activity, glutathione, and ferric reducing/anti-oxidant power levels. FLX also decreased myeloperoxidase activity, tumor necrosis factor-α, interleukin-1β, and interleukin-6 levels and increased interleukin-10 levels compared to IR. FLX attenuated the morphological changes associated with cardiac injury. Our study clearly demonstrates that FLX confers protection against aortic IR-induced cardiac injury, tissue leucocyte infiltration, and cellular integrity via its anti-oxidant/anti-inflammatory effects.
Effect of different sound atmospheres on SnO2:Sb thin films prepared by dip coating technique
Authors: Kocyigit Adem , Ozturk Erhan , Ejderha Kadir , Turgut Guven
Published: September 2017

Different sound atmosphere effects were investigated on SnO2:Sb thin films, which were deposited with dip coating technique. Two sound atmospheres were used in this study; one of them was nay sound atmosphere for soft sound, another was metallic sound for hard sound. X-ray diffraction (XRD) graphs have indicated that the films have different orientations and structural parameters in quiet room, metallic and soft sound atmospheres. It could be seen from UV–Vis spectrometer measurements that films have different band gaps and optical transmittances with changing sound atmospheres. Scanning electron microscope (SEM) and AFM images of the films have been pointed out that surfaces of films have been affected with changing sound atmospheres. The electrical measurements have shown that films have different I–V plots and different sheet resistances with changing sound atmospheres. These sound effects may be used to manage atoms in nano dimensions.
Role Models and Entrepreneurial Intention: The Moderating Effects of Experience, Locus of Control and Self-Esteem
Authors: Brunel Olivier , Laviolette Eric Michael , Radu-Lefebvre Miruna
Published: September 2017

This article demonstrates that the impact of role models (RMs) on students’ self-efficacy and entrepreneurial intention is moderated by their entrepreneurial experience and personality variables such as self-esteem and locus of control. 276 students enrolled in an entrepreneurship education programs (EEPs) were exposed to either a positive or a negative sensitisation message by alumni who became entrepreneurs to test its impact on the students’ self-efficacy and entrepreneurial intention. Findings indicate that students with entrepreneurial experience, high self-esteem and internal locus of control are less impacted by entrepreneurial role models. We discuss the relevance and effectiveness of role models in EEPs.
Nil Clean Graphs of Rings
Authors: Basnet Dhiren Kumar , Bhattacharyya Jayanta
Published: September 2017

In this article, we define the nil clean graph of a ring R. The vertex set is the ring R, and two ring elements a and b are adjacent if and only if a + b is nil clean in R. Graph theoretic properties like the girth, dominating sets, diameter, etc., of the nil clean graph are studied for finite commutative rings.
The weight distributions of irreducible cyclic codes of length 2npm
Authors: Sangwan Monika , Kumar Pankaj
Published: September 2017

Let [Formula: see text] be a primitive root modulo [Formula: see text], where [Formula: see text] and [Formula: see text] are distinct odd primes. Let [Formula: see text] be a finite field. For such pair of [Formula: see text] and [Formula: see text], the explicit expressions of minimal and generating polynomials over [Formula: see text] are obtained for all irreducible cyclic codes of length [Formula: see text]. In Sec. 4, it is observed that the weight distributions of all irreducible cyclic codes of length [Formula: see text] over [Formula: see text] can be computed easily with the help of the results obtained in [P. Kumar, M. Sangwan and S. K. Arora, The weight distribution of some irreducible cyclic codes of length [Formula: see text] and [Formula: see text], Adv. Math. Commun. 9 (2015) 277–289]. An explicit formula is also given to compute the weight distributions of irreducible cyclic codes of length [Formula: see text] over [Formula: see text].
Lie nilpotency indices of modular group algebras II
Authors: Sahai Meena , Siwach Reetu , Sharma R. K.
Published: September 2017

Let [Formula: see text] be the modular group algebra of a group [Formula: see text] over a field [Formula: see text] of characteristic [Formula: see text]. The classification of the group algebras [Formula: see text] with upper Lie nilpotency index [Formula: see text] greater than or equal to [Formula: see text] has already been done. In this paper, we determine the group algebras [Formula: see text] such that [Formula: see text], [Formula: see text], [Formula: see text], [Formula: see text], [Formula: see text] or [Formula: see text].
Qualitative Determinacy and Decidability of Stochastic Games with Signals
Authors: Bertrand Nathalie , Genest Blaise , Gimbert Hugo
Published: September 2017

We consider two-person zero-sum stochastic games with signals, a standard model of stochastic games with imperfect information. The only source of information for the players consists of the signals they receive; they cannot directly observe the state of the game, nor the actions played by their opponent, nor their own actions.

We are interested in the existence of almost-surely winning or positively winning strategies, under reachability, safety, Büchi, or co-Büchi winning objectives, and the computation of these strategies when the game has finitely many states and actions. We prove two
qualitative determinacy
results. First, in a reachability game, either player 1 can achieve almost surely the reachability objective, or player 2 can achieve surely the dual safety objective, or both players have positively winning strategies. Second, in a Büchi game, if player 1 cannot achieve almost surely the Büchi objective, then player 2 can ensure positively the dual co-Büchi objective. We prove that players only need strategies with
finite memory
. The number of memory states needed to win with finite-memory strategies ranges from one (corresponding to memoryless strategies) to doubly exponential, with matching upper and lower bounds. Together with the qualitative determinacy results, we also provide fix-point algorithms for deciding which player has an almost-surely winning or a positively winning strategy and for computing an associated finite-memory strategy. Complexity ranges from EXPTIME to 2EXPTIME, with matching lower bounds. Our fix-point algorithms also enjoy a better complexity in the cases where one of the players is better informed than their opponent.

Our results hold even when players do not necessarily observe their own actions. The adequate class of strategies, in this case, is mixed or general strategies (they are equivalent). Behavioral strategies are too restrictive to guarantee determinacy: it may happen that one of the players has a winning general strategy but none of them has a winning behavioral strategy. On the other hand, if a player can observe their actions, then general, mixed, and behavioral strategies are equivalent. Finite-memory strategies are sufficient for determinacy to hold, provided that randomized memory updates are allowed.
Predictor-Estimator
Authors: Kim Hyun , Jung Hun-Young , Kwon Hongseok , Lee Jong-Hyeok , Na Seung-Hoon
Published: September 2017

Recently, quality estimation has been attracting increasing interest from machine translation researchers, aiming at finding a good estimator for the “quality” of machine translation output. The common approach for quality estimation is to treat the problem as a supervised regression/classification task using a quality-annotated noisy parallel corpus, called
quality estimation data
, as training data. However, the available size of quality estimation data remains small, due to the too-expensive cost of creating such data. In addition, most conventional quality estimation approaches rely on manually designed features to model nonlinear relationships between feature vectors and corresponding quality labels. To overcome these problems, this article proposes a novel neural network architecture for quality estimation task—called the
predictor-estimator
—that considers word prediction as an additional pre-task. The major component of the proposed neural architecture is a
word prediction model
based on a modified neural machine translation model—a probabilistic model for predicting a target word conditioned on all the other source and target contexts. The underlying assumption is that the word prediction model is highly related to quality estimation models and is therefore able to transfer useful knowledge to quality estimation tasks. Our proposed quality estimation method sequentially trains the following two types of neural models: (1)
Predictor
:
a neural word prediction model
trained from parallel corpora and (2)
Estimator
:
a neural quality estimation model
trained from quality estimation data. To transfer word a prediction task to a quality estimation task, we generate
quality estimation feature vectors
from the word prediction model and feed them into the quality estimation model. The experimental results on WMT15 and 16 quality estimation datasets show that our proposed method has great potential in the various sub-challenges.
Differential privacy as a tool for truthfulness in games
Authors: Cummings Rachel
Published: September 2017

Differential privacy guarantees the input data from a single individual has a very small impact on the output of a computation. Tools from privacy can also be used in game theory and economics to incentivize people to truthfully reveal their data.
Incentivizing exploration via information asymmetry
Authors: Slivkins Aleksandrs
Published: September 2017

As self-interested individuals make decisions over time, they utilize information revealed by others in the past and produce information that may help others in the future. So how can we incentivize exploration for the sake of the common good?
Mimebot—Investigating the Expressibility of Non-Verbal Communication Across Agent Embodiments
Authors: Alexanderson Simon , O’sullivan Carol , Neff Michael , Beskow Jonas
Published: September 2017

Unlike their human counterparts, artificial agents such as robots and game characters may be deployed with a large variety of face and body configurations. Some have articulated bodies but lack facial features, and others may be talking heads ending at the neck. Generally, they have many fewer degrees of freedom than humans through which they must express themselves, and there will inevitably be a filtering effect when mapping human motion onto the agent. In this article, we investigate filtering effects on three types of embodiments: (a) an agent with a body but no facial features, (b) an agent with a head only, and (c) an agent with a body and a face. We performed a full performance capture of a mime actor enacting short interactions varying the non-verbal expression along five dimensions (e.g., level of frustration and level of certainty) for each of the three embodiments. We performed a crowd-sourced evaluation experiment comparing the video of the actor to the video of an animated robot for the different embodiments and dimensions. Our findings suggest that the face is especially important to pinpoint emotional reactions but is also most volatile to filtering effects. The body motion, on the other hand, had more diverse interpretations but tended to preserve the interpretation after mapping and thus proved to be more resilient to filtering.
Urdu Named Entity Recognition and Classification System Using Artificial Neural Network
Authors: Malik Muhammad Kamran
Published: September 2017

Named Entity Recognition and Classification (NERC) is a process of identifying words and classifying them into person names, location names, organization names, and so on. In this article, we discuss the development of an Urdu Named Entity (NE) corpus, called the Kamran-PU-NE (KPU-NE) corpus, for three entity types, that is, Person, Organization, and Location, and marking the remaining tokens as Others (O). We use two supervised learning algorithms, Hidden Markov Model (HMM) and Artificial Neural Network (ANN), for the development of the Urdu NERC system. We annotate the 652852-token corpus taken from 15 different genres with a total of 44480 NEs. The inter-annotator agreement between the two annotators in terms of Kappa k statistic is 73.41%. With HMM, the highest recorded precision, recall, and f-measure values are 55.98%, 83.11%, and 66.90%, respectively, and with ANN, they are 81.05%, 87.54%, and 84.17%, respectively.
Integrated IoT programming with selective abstraction
Authors: Lee Gyeongmin , Heo Seonyeong , Kim Bongjun , Kim Jong , Kim Hanjun
Published: September 2017

The explosion of networked devices has driven a new computing environment called the Internet of Things (IoT), enabling various services such as home automation and health monitoring. Despite the promising applicability of the IoT, developing an IoT service is challenging for programmers, because the programmers should integrate multiple programmable devices and heterogeneous third-party devices. Recent works have proposed integrated programming platforms, but they either require device-specific implementation for third-party devices without any device abstraction, or abstract all the devices to the standard interfaces requiring unnecessary abstraction of programmable devices. To integrate IoT devices with selective abstraction, this work revisits the object oriented programming (OOP) model, and proposes a new language extension and its compiler-runtime framework, called Esperanto. With three annotations that map each object to its corresponding IoT device, the Esperanto language allows programmers to integrate multiple programmable devices into one OOP program and to abstract similar third-party devices into their common ancestor classes. Given the annotations, the Esperanto compiler automatically partitions the integrated program into multiple sub-programs for each programmable IoT device, and inserts communication and synchronization code. Moreover, for the ancestor classes, the Esperanto runtime dynamically identifies connected third-party devices, and links their corresponding descendent objects. Compared to an existing approach on the integrated IoT programming, Esperanto requires 33.3% fewer lines of code to implement 5 IoT services, and reduces their response time by 44.8% on average.
Towards SMT-based LTL model checking of clock constraint specification language for real-time and embedded systems
Authors: Zhang Min , Ying Yunhui
Published: September 2017

The Clock Constraint Specification Language (CCSL) is a formal language companion to MARTE (shorthand for Modeling and Analysis of Real-Time and Embedded systems), a UML profile used to facilitate the design and analysis of real-time and embedded systems. CCSL is proposed to specify constraints on the occurrences of events in systems. However, the language lacks efficient verification support to formally analyze temporal properties, which are important properties to real-time and embedded systems. In this paper, we propose an SMT-based approach to model checking of the temporal properties specified in Linear Temporal Logic (LTL) for CCSL by transforming CCSL constraints and LTL formulas into SMT formulas. We implement a prototype tool for the proposed approach and use the state-of-the-art tool Z3 as its underlying SMT solver. We model two practical real-time and embedded systems, i.e., a traffic light controller and a power window system in CCSL , and model check LTL properties of them using the proposed approach. Experimental results demonstrate the effectiveness and efficiency of our approach.
Adaptive optimization for OpenCL programs on embedded heterogeneous systems
Authors: Taylor Ben , Marco Vicent Sanz , Wang Zheng
Published: September 2017

Heterogeneous multi-core architectures consisting of CPUs and GPUs are commonplace in today’s embedded systems. These architectures offer potential for energy efficient computing if the application task is mapped to the right core. Realizing such potential is challenging due to the complex and evolving nature of hardware and applications. This paper presents an automatic approach to map OpenCL kernels onto heterogeneous multi-cores for a given optimization criterion – whether it is faster runtime, lower energy consumption or a trade-off between them. This is achieved by developing a machine learning based approach to predict which processor to use to run the OpenCL kernel and the host program, and at what frequency the processor should operate. Instead of hand-tuning a model for each optimization metric, we use machine learning to develop a unified framework that first automatically learns the optimization heuristic for each metric off-line, then uses the learned knowledge to schedule OpenCL kernels at runtime based on code and runtime information of the program. We apply our approach to a set of representative OpenCL benchmarks and evaluate it on an ARM big.LITTLE mobile platform. Our approach achieves over 93% of the performance delivered by a perfect predictor.We obtain, on average, 1.2x, 1.6x, and 1.8x improvement respectively for runtime, energy consumption and the energy delay product when compared to a comparative heterogeneous-aware OpenCL task mapping scheme.
BARRACUDA: binary-level analysis of runtime RAces in CUDA programs
Authors: Eizenberg Ariel , Peng Yuanfeng , Pigli Toma , Mansky William , Devietti Joseph
Published: September 2017

GPU programming models enable and encourage massively parallel programming with over a million threads, requiring extreme parallelism to achieve good performance. Massive parallelism brings significant correctness challenges by increasing the possibility for bugs as the number of thread interleavings balloons. Conventional dynamic safety analyses struggle to run at this scale.

We present BARRACUDA, a concurrency bug detector for GPU programs written in Nvidia’s CUDA language. BARRACUDA handles a wider range of parallelism constructs than previous work, including branch operations, low-level atomics and memory fences, which allows BARRACUDA to detect new classes of concurrency bugs. BARRACUDA operates at the binary level for increased compatibility with existing code, leveraging a new binary instrumentation framework that is extensible to other dynamic analyses. BARRACUDA incorporates a number of novel optimizations that are crucial for scaling concurrency bug detection to over a million threads.
Instruction punning: lightweight instrumentation for x86-64
Authors: Chamith Buddhika , Svensson Bo Joel , Dalessandro Luke , Newton Ryan R.
Published: September 2017

Existing techniques for injecting probes into running applications are limited;

they either fail to support probing arbitrary locations, or to support scalable,

rapid toggling of probes. We introduce a new technique on x86-64, called

instruction punning, which allows scalable probes at any instruction. The key

idea is that when we inject a jump instruction, the relative address of the jump

serves simultaneously as data and as an instruction sequence. We show that this

approach achieves probe invocation overheads of only a few dozen cycles, and

probe activation/deactivation costs that are cheaper than a system call, even

when all threads in the system are both invoking probes and toggling them.
FunTAL: reasonably mixing a functional language with assembly
Authors: Patterson Daniel , Perconti Jamie , Dimoulas Christos , Ahmed Amal
Published: September 2017

We present FunTAL, the first multi-language system to formalize safe interoperability between a high-level functional language and low-level assembly code while supporting compositional reasoning about the mix. A central challenge in developing such a multi-language is bridging the gap between assembly, which is staged into jumps to continuations, and high-level code, where subterms return a result. We present a
compositional
stack-based typed assembly language that supports
components
, comprised of one or more basic blocks, that may be embedded in high-level contexts. We also present a logical relation for FunTAL that supports reasoning about equivalence of high-level components and their assembly replacements, mixed-language programs with callbacks between languages, and assembly components comprised of different numbers of basic blocks.
HoTTSQL: proving query rewrites with univalent SQL semantics
Authors: Chu Shumo , Weitz Konstantin , Cheung Alvin , Suciu Dan
Published: September 2017

Every database system contains a query optimizer that performs query rewrites. Unfortunately, developing query optimizers remains a highly challenging task. Part of the challenges comes from the intricacies and rich features of query languages, which makes reasoning about rewrite rules difficult. In this paper, we propose a machine-checkable denotational semantics for SQL, the de facto language for relational database, for rigorously validating rewrite rules. Unlike previously proposed semantics that are either non-mechanized or only cover a small amount of SQL language features, our semantics covers all major features of SQL, including bags, correlated subqueries, aggregation, and indexes. Our mechanized semantics, called HoTT SQL, is based on K-Relations and homotopy type theory, where we denote relations as mathematical functions from tuples to univalent types. We have implemented HoTTSQL in Coq, which takes only fewer than 300 lines of code and have proved a wide range of SQL rewrite rules, including those from database research literature (e.g., magic set rewrites) and real-world query optimizers (e.g., subquery elimination). Several of these rewrite rules have never been previously proven correct. In addition, while query equivalence is generally undecidable, we have implemented an automated decision procedure using HoTTSQL for conjunctive queries: a well studied decidable fragment of SQL that encompasses many real-world queries.
A formally verified compiler for Lustre
Authors: Bourke Timothy , Brun Lélio , Dagand Pierre-Évariste , Leroy Xavier , Pouzet Marc , Rieg Lionel
Published: September 2017

The correct compilation of block diagram languages like Lustre, Scade, and a discrete subset of Simulink is important since they are used to program critical embedded control software. We describe the specification and verification in an Interactive Theorem Prover of a compilation chain that treats the key aspects of Lustre: sampling, nodes, and delays. Building on CompCert, we show that repeated execution of the generated assembly code faithfully implements the dataflow semantics of source programs.

We resolve two key technical challenges. The first is the change from a synchronous dataflow semantics, where programs manipulate streams of values, to an imperative one, where computations manipulate memory sequentially. The second is the verified compilation of an imperative language with encapsulated state to C code where the state is realized by nested records. We also treat a standard control optimization that eliminates unnecessary conditional statements.
Fusing effectful comprehensions
Authors: Saarikivi Olli , Veanes Margus , Mytkowicz Todd , Musuvathi Madan
Published: September 2017

List comprehensions provide a powerful abstraction mechanism for expressing computations over ordered collections of data declaratively without having to use explicit iteration constructs. This paper puts forth
effectful comprehensions
as an elegant way to describe list comprehensions that incorporate loop-carried state. This is motivated by operations such as compression/decompression and serialization/deserialization that are common in log/data processing pipelines and require loop-carried state when processing an input stream of data.

We build on the underlying theory of
symbolic transducers
to fuse pipelines of effectful comprehensions into a single representation, from which efficient code can be generated. Using background theory reasoning with an SMT solver, our fusion and subsequent reachability based branch elimination algorithms can significantly reduce the complexity of the fused pipelines. Our implementation shows significant speedups over reasonable hand-written code (3.4×, on average) and traditionally fused version of the pipeline (2.6×, on average) for a variety of examples, including scenarios for extracting fields with regular expressions, processing XML with XPath, and running queries over encoded data.
Low-synchronization, mostly lock-free, elastic scheduling for streaming runtimes
Authors: Schneider Scott , Wu Kun-Lung
Published: September 2017

We present the scalable, elastic operator scheduler in IBM Streams 4.2. Streams is a distributed stream processing system used in production at many companies in a wide range of industries. The programming language for Streams, SPL, presents operators, tuples and streams as the primary abstractions. A fundamental SPL optimization is operator fusion, where multiple operators execute in the same process. Streams 4.2 introduces automatic submission-time fusion to simplify application development and deployment. However, potentially thousands of operators could then execute in the same process, with no user guidance for thread placement. We needed a way to automatically figure out how many threads to use, with arbitrarily sized applications on a wide variety of hardware, and without any input from programmers. Our solution has two components. The first is a scalable operator scheduler that minimizes synchronization, locks and global data, while allowing threads to execute any operator and dynamically come and go. The second is an elastic algorithm to dynamically adjust the number of threads to optimize performance, using the principles of trusted measurements to establish trends. We demonstrate our scheduler's ability to scale to over a hundred threads, and our elasticity algorithm's ability to adapt to different workloads on an Intel Xeon system with 176 logical cores, and an IBM Power8 system with 184 logical cores.
Responsive parallel computation: bridging competitive and cooperative threading
Authors: Muller Stefan K. , Acar Umut A. , Harper Robert
Published: September 2017

Competitive and cooperative threading are widely used abstractions in computing. In competitive threading, threads are scheduled preemptively with the goal of minimizing response time, usually of interactive applications. In cooperative threading, threads are scheduled non-preemptively with the goal of maximizing throughput or minimizing the completion time, usually in compute-intensive applications, e.g. scientific computing, machine learning and AI.

Although both of these forms of threading rely on the same abstraction of a thread, they have, to date, remained largely separate forms of computing. Motivated by the recent increase in the mainstream use of multicore computers, we propose a threading model that aims to unify competitive and cooperative threading. To this end, we extend the classic graph-based cost model for cooperative threading to allow for competitive threading, and describe how such a cost model may be used in a programming language by presenting a language and a corresponding cost semantics. Finally, we show that the cost model and the semantics are realizable by presenting an operational semantics for the language that specifies the behavior of an implementation, as well as an implementation and a small empirical evaluation.
Low overhead dynamic binary translation on ARM
Authors: D'Antras Amanieu , Gorgovan Cosmin , Garside Jim , Luján Mikel
Published: September 2017

The ARMv8 architecture introduced AArch64, a 64-bit execution mode with a new instruction set, while retaining binary compatibility with previous versions of the ARM architecture through AArch32, a 32-bit execution mode. Most hardware implementations of ARMv8 processors support both AArch32 and AArch64, which comes at a cost in hardware complexity.

We present MAMBO-X64, a dynamic binary translator for Linux which executes 32-bit ARM binaries using only the AArch64 instruction set. We have evaluated the performance of MAMBO-X64 on three existing ARMv8 processors which support both AArch32 and AArch64 instruction sets. The performance was measured by comparing the running time of 32-bit benchmarks running under MAMBO-X64 with the same benchmark running natively. On SPEC CPU2006, we achieve a geometric mean overhead of less than 7.5% on in-order Cortex-A53 processors and a performance improvement of 1% on out-of-order X-Gene 1 processors.

MAMBO-X64 achieves such low overhead by novel optimizations to map AArch32 floating-point registers to AArch64 registers dynamically, handle overflowing address calculations efficiently, generate traces that harness hardware return address prediction, and handle operating system signals accurately.
Dynamic race prediction in linear time
Authors: Kini Dileep , Mathur Umang , Viswanathan Mahesh
Published: September 2017

Writing reliable concurrent software remains a huge challenge for today's programmers. Programmers rarely reason about their code by explicitly considering different possible inter-leavings of its execution. We consider the problem of detecting data races from individual executions in a sound manner. The classical approach to solving this problem has been to use Lamport's happens-before (HB) relation. Until now HB remains the only approach that runs in linear time. Previous efforts in improving over HB such as causally-precedes (CP) and maximal causal models fall short due to the fact that they are not implementable efficiently and hence have to compromise on their race detecting ability by limiting their techniques to bounded sized fragments of the execution. We present a new relation weak-causally-precedes (WCP) that is provably better than CP in terms of being able to detect more races, while still remaining sound. Moreover, it admits a linear time algorithm which works on the entire execution without having to fragment it.
Compiling Markov chain Monte Carlo algorithms for probabilistic modeling
Authors: Huang Daniel , Tristan Jean-Baptiste , Morrisett Greg
Published: September 2017

The problem of probabilistic modeling and inference, at a high-level, can be viewed as constructing a (
model
,
query
,
inference
) tuple, where an
inference
algorithm implements a
query
on a
model
. Notably, the derivation of inference algorithms can be a difficult and error-prone task. Hence, researchers have explored how ideas from
probabilistic programming
can be applied. In the context of constructing these tuples, probabilistic programming can be seen as taking a language-based approach to probabilistic modeling and inference. For instance, by using (1) appropriate languages for expressing models and queries and (2) devising inference techniques that operate on encodings of models (and queries) as program expressions, the task of inference can be automated.

In this paper, we describe a compiler that transforms a probabilistic model written in a restricted modeling language and a query for posterior samples given observed data into a Markov Chain Monte Carlo (MCMC) inference algorithm that implements the query. The compiler uses a sequence of intermediate languages (ILs) that guide it in gradually and successively refining a declarative specification of a probabilistic model and the query into an executable MCMC inference algorithm. The compilation strategy produces composable MCMC algorithms for execution on a CPU or GPU.
Simple, fast, and safe manual memory management
Authors: Kedia Piyus , Costa Manuel , Parkinson Matthew , Vaswani Kapil , Vytiniotis Dimitrios , Blankstein Aaron
Published: September 2017

Safe programming languages are readily available, but many applications continue to be written in unsafe languages because of efficiency. As a consequence, many applications continue to have exploitable memory safety bugs. Since garbage collection is a major source of inefficiency in the implementation of safe languages, replacing it with safe manual memory management would be an important step towards solving this problem.

Previous approaches to safe manual memory management use programming models based on regions, unique pointers, borrowing of references, and ownership types. We propose a much simpler programming model that does not require any of these concepts. Starting from the design of an imperative type safe language (like Java or C#), we just add a delete operator to free memory explicitly and an exception which is thrown if the program dereferences a pointer to freed memory. We propose an efficient implementation of this programming model that guarantees type safety. Experimental results from our implementation based on the C# native compiler show that this design achieves up to 3x reduction in peak working set and run time.
Generalizations of the theory and deployment of triangular inequality for compiler-based strength reduction
Authors: Ding Yufei , Ning Lin , Guan Hui , Shen Xipeng
Published: September 2017

Triangular Inequality (TI) has been used in many manual algorithm designs to achieve good efficiency in solving some distance calculation-based problems. This paper presents our generalization of the idea into a compiler optimization technique, named TI-based strength reduction. The generalization consists of three parts. The first is the establishment of the theoretic foundation of this new optimization via the development of a new form of TI named Angular Triangular Inequality, along with several fundamental theorems. The second is the revealing of the properties of the new forms of TI and the proposal of guided TI adaptation, a systematic method to address the difficulties in effective deployments of TI optimizations. The third is an integration of the new optimization technique in an open-source compiler. Experiments on a set of data mining and machine learning algorithms show that the new technique can speed up the standard implementations by as much as 134X and 46X on average for distance-related problems, outperforming previous TI-based optimizations by 2.35X on average. It also extends the applicability of TI-based optimizations to vector related problems, producing tens of times of speedup.
Practical partial evaluation for high-performance dynamic language runtimes
Authors: Würthinger Thomas , Wimmer Christian , Humer Christian , Wöß Andreas , Stadler Lukas , Seaton Chris , Duboscq Gilles , Simon Doug , Grimmer Matthias
Published: September 2017

Most high-performance dynamic language virtual machines duplicate language semantics in the interpreter, compiler, and runtime system. This violates the principle to not repeat yourself. In contrast, we define languages solely by writing an interpreter. The interpreter performs specializations, e.g., augments the interpreted program with type information and profiling information. Compiled code is derived automatically using partial evaluation while incorporating these specializations. This makes partial evaluation practical in the context of dynamic languages: It reduces the size of the compiled code while still compiling all parts of an operation that are relevant for a particular program. When a speculation fails, execution transfers back to the interpreter, the program re-specializes in the interpreter, and later partial evaluation again transforms the new state of the interpreter to compiled code. We evaluate our approach by comparing our implementations of JavaScript, Ruby, and R with best-in-class specialized production implementations. Our general-purpose compilation system is competitive with production systems even when they have been heavily optimized for the one language they support. For our set of benchmarks, our speedup relative to the V8 JavaScript VM is 0.83x, relative to JRuby is 3.8x, and relative to GNU R is 5x.
Gradual synthesis for static parallelization of single-pass array-processing programs
Authors: Fedyukovich Grigory , Ahmad Maaz Bin Safeer , Bodik Rastislav
Published: September 2017

Parallelizing of software improves its effectiveness and productivity. To guarantee correctness, the parallel and serial versions of the same code must be formally verified to be equivalent. We present a novel approach, called GRASSP, that automatically synthesizes parallel single-pass array-processing programs by treating the given serial versions as specifications. Given arbitrary segmentation of the input array, GRASSP synthesizes a code to determine a new segmentation of the array that allows computing partial results for each segment and merging them. In contrast to other parallelizers, GRASSP gradually considers several parallelization scenarios and certifies the results using constrained Horn solving. For several classes of programs, we show that such parallelization can be performed efficiently. The C++ translations of the GRASSP solutions sped performance by up to 5X relative to serial code on an 8-thread machine and Hadoop translations by up to 10X on a 10-node Amazon EMR cluster.
Flatten and conquer: a framework for efficient analysis of string constraints
Authors: Abdulla Parosh Aziz , Atig Mohamed Faouzi , Chen Yu-Fang , Diep Bui Phi , Holík Lukáš , Rezine Ahmed , Rümmer Philipp
Published: September 2017

We describe a uniform and efficient framework for checking the satisfiability of a large class of string constraints. The framework is based on the observation that both satisfiability and unsatisfiability of common constraints can be demonstrated through witnesses with simple patterns. These patterns are captured using
flat
automata each of which consists of a sequence of simple loops. We build a Counter-Example Guided Abstraction Refinement (CEGAR) framework which contains both an under- and an over-approximation module. The flow of information between the modules allows to increase the precision in an automatic manner. We have implemented the framework as a tool and performed extensive experimentation that demonstrates both the generality and efficiency of our method.
Cache locality optimization for recursive programs
Authors: Lifflander Jonathan , Krishnamoorthy Sriram
Published: September 2017

We present an approach to optimize the cache locality for recursive programs by dynamically splicing---recursively interleaving---the execution of distinct function invocations. By utilizing data effect annotations, we identify concurrency and data reuse opportunities across function invocations and interleave them to reduce reuse distance. We present algorithms that efficiently track effects in recursive programs, detect interference and dependencies, and interleave execution of function invocations using user-level (non-kernel) lightweight threads. To enable multi-core execution, a program is parallelized using a nested fork/join programming model. Our cache optimization strategy is designed to work in the context of a random work stealing scheduler. We present an implementation using the MIT Cilk framework that demonstrates significant improvements in sequential and parallel performance, competitive with a state-of-the-art compile-time optimizer for loop programs and a domain-specific optimizer for stencil programs.
DemoMatch: API discovery from demonstrations
Authors: Yessenov Kuat , Kuraj Ivan , Solar-Lezama Armando
Published: September 2017

We introduce DemoMatch, a tool for API discovery that allows the user to discover how to implement functionality using a software framework by demonstrating the functionality in existing applications built with the same framework. DemoMatch matches the demonstrations against a database of execution traces called Semeru and generates code snippets explaining how to use the functionality. We evaluated DemoMatch on several case studies involving Java Swing and Eclipse RCP.
Dancing with Wolves
Authors: Deng Liang , Liu Peng , Xu Jun , Chen Ping , Zeng Qingkai
Published: September 2017

This paper presents a novel framework that enables practical event-driven monitoring for untrusted virtual machine monitors (VMMs) in cloud computing. Unlike previous approaches for VMM monitoring, our framework neither relies on a higher privilege level nor requires any special hardware support. Instead, we place the trusted monitor at the same privilege level and in the same address space with the untrusted VMM to achieve superior efficiency, while proposing a unique mutual-protection mechanism to ensure the integrity of the monitor. Our security analysis demonstrates that our framework can provide high-assurance for event-driven VMM monitoring, even if the highest-privilege VMM is fully compromised. The experimental results show that our framework only incurs trivial performance overhead for enforcing event-driven monitoring policies, exhibiting tremendous performance improvement on previous approaches.