bluuebunny/crossref_metadata_2025 huggingface dataset:
Dural venous sinus angioplasty and stenting for the treatment of idiopathic intracranial hypertension
Authors: Fields Jeremy D , Javedani Parisa P , Falardeau Julie , Nesbit Gary M , Dogan Aclan , Helseth Erek K , Liu Kenneth C , Barnwell Stanley L , Petersen Bryan D
Published: December 2011

Background

Lumboperitoneal shunt (LPS), ventriculoperitoneal shunt (VPS) and optic nerve sheath fenestration (ONSF) are accepted surgical therapies for medically refractory idiopathic intracranial hypertension (IIH). In the subset of patients with IIH and venous sinus stenosis, dural venous sinus stenting has emerged as an alternative surgical approach.

Methods

All cases of dural stents for IIH at our institution were retrospectively reviewed. Eligibility criteria included medically refractory IIH with documented papilledema and dural venous sinus stenosis of the dominant venous outflow system (gradient ≥10 mm Hg).

Results

Fifteen cases (all women) of mean age 34 years were identified. All had failed medical therapy and six had failed surgical intervention. Technical success was achieved in all patients without major periprocedural complications. The mean preprocedural gradient across the venous stenosis was reduced from 24 mm Hg before the procedure to 4 mm Hg after the procedure. Headache resolved or improved in 10 patients. Papilledema resolved in all patients and visual acuity stabilized or improved in 14 patients. There were no instances of restenosis among the 14 patients with follow-up imaging.

Conclusion

In this small case series, dural sinus stenting for IIH was performed safely with a high degree of technical success and with excellent clinical outcomes. These results suggest that angioplasty and stenting for the treatment of medically refractory IIH in patients with dural sinus stenosis warrants further investigation as an alternative to LPS, VPS and ONSF.
THE IDEMPOTENT PROBLEM FOR AN INVERSE MONOID
Authors: GILBERT N. D. , NOONAN HEALE R.
Published: December 2011

We generalize the word problem for groups, the formal language of all words in the generators that represent the identity, to inverse monoids. In particular, we introduce the idempotent problem, the formal language of all words representing idempotents, and investigate how the properties of an inverse monoid are related to the formal language properties of its idempotent problem. We show that if an inverse monoid is either E-unitary or has a finite set of idempotents, then its idempotent problem is regular if and only if the inverse monoid is finite. We also give examples of inverse monoids with context-free idempotent problems, including all Bruck–Reilly extensions of finite groups.
LEFT ADEQUATE AND LEFT EHRESMANN MONOIDS
Authors: BRANCO MÁRIO J. J. , GOMES GRACINDA M. S. , GOULD VICTORIA
Published: December 2011

This is the first of two articles studying the structure of left adequate and, more generally, of left Ehresmann monoids. Motivated by a careful analysis of normal forms, we introduce here a concept of proper for a left adequate monoid M. In fact, our notion is that of T-proper, where T is a submonoid of M. We show that any left adequate monoid M has an X*-proper cover for some set X, that is, there is a left adequate monoid [Formula: see text] that is X*-proper, and an idempotent separating surjective morphism [Formula: see text] of the appropriate type. Given this result, we may deduce that the free left adequate monoid on any set X is X*-proper. In a subsequent paper, we show how to construct T-proper left adequate monoids from any monoid T acting via order-preserving maps on a semilattice with identity, and prove that the free left adequate monoid is of this form. An alternative description of the free left adequate monoid will appear in a paper of Kambites. We show how to obtain the labeled trees appearing in his result from our structure theorem. Our results apply to the wider class of left Ehresmann monoids, and we give them in full generality. We also indicate how to obtain some of the analogous results in the two-sided case. This paper and its sequel, and the two of Kambites on free (left) adequate semigroups, demonstrate the rich but accessible structure of (left) adequate semigroups and monoids, introduced with startling insight by Fountain some 30 years ago.
ARE TIBIOFEMORAL COMPRESSIVE LOADS TRANSFERRED ONLY VIA CONTACT MECHANISMS?
Authors: HAKKAK FERAS , ROSTAMI MOSTAFA , PARNIANPOUR MOHAMAD
Published: December 2011

The tibiofemoral joint is known to bear compressive loads of several body-weights during daily activities. These forces are known to be transferred through the joint via compression of the tibial and femoral surfaces against one another. The menisci are also known to enhance this process by increasing the contact area and decreasing contact stress. However, calculations presented in this paper suggest that the load-bearing capacity of contact mechanisms is seemingly several times smaller than tibiofemoral joint loads. This suggests that probably one or more non-contact load-bearing mechanism(s) exist, and share the load with the already known contact mechanisms.
IMPACT OF OSTEOCLAST PRECURSORS SUBJECTED TO RANDOM POSITIONING MACHINE ON OSTEOBLASTS
Authors: DI SHENGMENG , MENG RUI , QIAN AIRONG , TIAN ZONGCHENG , LI JINGBAO , ZHANG RONG , SHANG PENG
Published: December 2011

Osteoblast-osteoclast interaction plays an important role in the bone remodeling. During long duration space flight, astronauts undergo serious bone loss mainly due to the disruption of equivalence between bone formation and bone resorption. Osteoclast precursors often operate under the control of osteoblasts. However, here we show that the osteoclast precursors could in turn influence osteoblasts. RAW264.7 cells, the murine osteoclast precursors, were treated in the simulated weightlessness produced by a Random Positioning Machine (RPM). After 72 h, conditioned mediums (CM) by the RAW264.7 cells from RPM (RCM) or static control (CCM) were collected and were used to culture osteoblastic-like MC3T3-E1 cells. The results showed that the RCM culture inhibited cell viability and slightly altered cell cycle, but the morphology of the MC3T3-E1 cells was not changed by RCM compared to that of CCM. Furthermore, the intracellular ALP level, NO release and expression of osteoblastic marker genes were all down-regulated by RCM culture. These results suggest that osteoclast precursors subjected to RPM exert negative regulation on osteoblasts.
VISUALIZING RELATIONS USING THE "OBSERVABLE REPRESENTATION"
Authors: SCHULMAN L. S. , BAGROW J. P. , GAVEAU B.
Published: December 2011

The observable representation provides an embedding of a discrete space in a low dimensional continuous space. Typically, the discrete space is a model of a complex system. This graphical representation is known to highlight significant properties of the original space and can serendipitously reveal unanticipated relationships. We report on the current status of this technique and give examples of its applications and rationale.
WORD-OF-MOUTH VERSUS EXPERTS AND REPUTATION IN THE INDIVIDUAL DYNAMICS OF WINE PURCHASING
Authors: BOUZDINE-CHAMEEVA TATIANA , GALAM SERGE
Published: December 2011

The dynamics of wine purchasing behavior is studied focusing on the respective impacts of the word-to-mouth versus wine expert judgements and reputations. To investigate the problem we apply the Galam model of opinion dynamics to agents who have to select a preference about which type of wine to buy given expert judgements, individual preferences and wine reputations. It could be, for instance, a preference between Bordeaux and Burgundy. The main novelty of the work is not about the building of a new model but indeed the construction of a scheme to confront the Galam model to a specific problem of the real world. Accordingly we design a commercial strategy to hold on to a share of the wine market. It provides a novel understanding on how, given some established reputation, the competitive interplay between social interactions and expert judgments affects the market shares distribution. The financial implications of the practical implementation of these results are discussed. In particular it is found that sample distribution of bottles could be drastically reduced from the usual levels practiced by producers. We hope our results will convince some wine producers to test our predictions.
OPEN INNOVATION AND ITS EFFECTIVENESS TO EMBRACE TURBULENT ENVIRONMENTS
Authors: SCHWEITZER FIONA M. , GASSMANN OLIVER , GAUBINGER KURT
Published: December 2011

The paper focuses on the challenges of integrating external sources in the innovation process and investigates the role of environmental turbulence in this context. Building on the resources-based view and the dynamic capabilities perspective the authors propose that open innovation strategies assist companies in navigating through turbulent times. Empirical testing of this assumption in a sample of 101 manufacturing firms indicates that open innovation activities are more important in turbulent than in non-turbulent markets and that supplier integration is vital when technological turbulence is high, whilst customer integration is critical in environments characterized by high market turbulence. From a practical point of view, these findings highlight the importance of stakeholder integration in the innovation process and provide details on the successful implementation of this strategy under different environmental settings.
An unusual specimen of
Glyptograptus
from Dob's Linn (Southern Uplands, Scotland), and a discussion of graptolite teratomorphies
Authors: Muir Lucy A.
Published: December 2011

A specimen of
Glyptograptus
from the Silurian of Dob's Linn is described that possessed a bifurcating virgula, with a biserial stipe along each virgula. The colony lived for some considerable time with this morphology, showing that at least some graptoloids could survive and grow with major modifications to the rhabdosome. The specimen is left under open nomenclature, but if further material is discovered it may be appropriate to name a new species. Growth abnormalities in graptolites are not common, but many examples of repaired damage, rhabdosome malformations, and abnormal growth of thecae, virgellae and virgulae are known. Growth abnormalities can provide important evidence about graptolite ecology, biology and evolution, and so should be described and illustrated whenever possible.
A critical graptolite correlation into the Lower Ordovician of Gondwana
Authors: Fortey Richard A.
Published: December 2011

The early Ordovician was a time of maximum faunal provinciality. Correlation between strata deposited at low palaeolatitudes and those deposited close to the Ordovician pole in Gondwana is accordingly particularly difficult. The graptolite used to define the base of the internationally accepted Floian Stage,
Tetragraptus approximatus
, is essentially a lower latitude species. The discovery of a closely related and coeval species,
T. akzharensis
, in the early Ordovician of the Montagne Noire is reported. It occurs at the same level as the acme of the trilobite
Taihungshania miqueli
. The new record permits a direct tie with the earliest part of the Floian Stage and the shelly faunas typical of much of western Gondwana.
The Rhuddanian/Aeronian transition in the Rheidol Gorge, mid Wales
Authors: Cullum Alex A. , Loydell David K.
Published: December 2011

Logs are presented through the upper Rhuddanian and lower Aeronian (Llandovery, Silurian) of the internationally important Rheidol Gorge section in Ceredigion, mid Wales. It is hoped that these will be of value to those engaged in future research on the section.
Improved Chinese--English SMT with Chinese “DE” Construction Classification and Reordering
Authors: Du Jinhua , Way Andy
Published: December 2011

Syntactic reordering on the source side has been demonstrated to be helpful and effective for handling different word orders between source and target languages in SMT. In this article, we focus on the Chinese (DE) construction which is flexible and ubiquitous in Chinese and has many different ways to be translated into English so that it is a major source of word order differences in terms of translation quality. This article carries out the Chinese “DE” construction study for Chinese--English SMT in which we propose a new classifier model---discriminative latent variable model (DPLVM)---with new features to improve the classification accuracy and indirectly improve the translation quality compared to a log-linear classifier. The DE classifier is used to recognize DE structures in both training and test sentences of Chinese, and then perform word reordering to make the Chinese sentences better match the word order of English. In order to investigate the impact of the DE classification and reordering in the source side on different types of SMT systems (namely PB-SMT, hierarchical PB-SMT (HPB-SMT) as well as the syntax-based SMT (SAMT)), we conduct a series of experiments on NIST 2005 and 2008 test sets to verify the effectiveness of our proposed model. The experimental results show that the MT systems using the data reordered by our proposed model outperform the baseline systems by 3.01% and 4.03% relative points on the NIST 2005 test set, 4.64% and 4.62% relative points on the NIST 2008 test set in terms of BLEU score for PB-SMT and HPB-SMT respectively. However, the DE classification method does not perform significantly well for SAMT. Additionally, we also conducted some experiments to evaluate our DE classification and reordering approach on the word alignment and phrase table in terms of these three types of SMT systems.
Language Modeling for Syntax-Based Machine Translation Using Tree Substitution Grammars
Authors: Xiao Tong , Zhu Jingbo , Zhu Muhua
Published: December 2011

The poor grammatical output of Machine Translation (MT) systems appeals syntax-based approaches within language modeling. However, previous studies showed that syntax-based language modeling using (Context-Free) Treebank Grammars was not very helpful in improving BLEU scores for Chinese-English machine translation. In this article we further study this issue in the context of Chinese-English syntax-based Statistical Machine Translation (SMT) where Synchronous Tree Substitution Grammars (STSGs) are utilized to model the translation process. In particular, we develop a Tree Substitution Grammar-based language model for syntax-based MT, and present three methods to efficiently integrate the proposed language model into MT decoding. In addition, we design a simple and effective method to adapt syntax-based language models for MT tasks. We demonstrate that the proposed methods are able to benefit a state-of-the-art syntax-based MT system. On the NIST Chinese-English MT evaluation corpora, we finally achieve an improvement of 0.6 BLEU points over the baseline.
Deep Learning Approaches to Semantic Relevance Modeling for Chinese Question-Answer Pairs
Authors: Wang Baoxun , Liu Bingquan , Wang Xiaolong , Sun Chengjie , Zhang Deyuan
Published: December 2011

The human-generated question-answer pairs in the Web social communities are of great value for the research of automatic question-answering technique. Due to the large amount of noise information involved in such corpora, it is still a problem to detect the answers even though the questions are exactly located. Quantifying the semantic relevance between questions and their candidate answers is essential to answer detection in social media corpora. Since both the questions and their answers usually contain a small number of sentences, the relevance modeling methods have to overcome the problem of word feature sparsity. In this article, the deep learning principle is introduced to address the semantic relevance modeling task. Two deep belief networks with different architectures are proposed by us to model the semantic relevance for the question-answer pairs. According to the investigation of the textual similarity between the community-driven question-answering (cQA) dataset and the forum dataset, a learning strategy is adopted to promote our models’ performance on the social community corpora without hand-annotating work. The experimental results show that our method outperforms the traditional approaches on both the cQA and the forum corpora.
Query modeling for entity search based on terms, categories, and examples
Authors: Balog Krisztian , Bron Marc , De Rijke Maarten
Published: December 2011

Users often search for entities instead of documents, and in this setting, are willing to provide extra input, in addition to a series of query terms, such as category information and example entities. We propose a general probabilistic framework for entity search to evaluate and provide insights in the many ways of using these types of input for query modeling. We focus on the use of category information and show the advantage of a category-based representation over a term-based representation, and also demonstrate the effectiveness of category-based expansion using example entities. Our best performing model shows very competitive performance on the INEX-XER entity ranking and list completion tasks.
Redirected walking to explore virtual environments
Authors: Hodgson Eric , Bachmann Eric , Waller David
Published: December 2011

Redirected walking has gained popularity in recent years as a way of enhancing the safety of users immersed in a virtual reality simulation and of extending the amount of space that can be simulated in a virtual environment (VE). Limits imposed by the available physical space and functional tracking area are overcome by inducing immersed users to veer imperceptibly in a way that prevents them from leaving the confines of the tracking space. Redirected walking has been shown to be feasible at levels below noticeable thresholds and to function without increasing the incidence of simulator sickness. The present studies demonstrate that redirected walking can function without negatively impacting memory for spatial locations of landmarks in a VE, despite introducing discrepancies between various spatial senses and distorting the spatial mapping of movement onto the environment. Additionally, the present studies implement what, to our knowledge, is the first generalized redirected walking algorithm that is independent of any task or environment structure, and can adaptively steer users in real time as they engage in spontaneous, unconstrained navigation. The studies also demonstrate that such an algorithm can be implemented successfully in a gymnasium-sized space.
Bimodal task-facilitation in a virtual traffic scenario through spatialized sound rendering
Authors: Bernhard Matthias , Grosse Karl , Wimmer Michael
Published: December 2011

Audio rendering is generally used to increase the realism of virtual environments (VE). In addition, audio rendering may also improve the performance in specific tasks carried out in interactive applications such as games or simulators. In this article we investigate the effect of the quality of sound rendering on task performance in a task which is inherently vision-dominated. The task is a virtual traffic gap-crossing scenario with two elements: first, to discriminate crossable and uncrossable gaps in oncoming traffic, and second, to find the right timing to start crossing the street without an accident. A study was carried out with 48 participants in an immersive virtual environment setup with a large screen and headphones. Participants were grouped into three different scenarios. In the first one, spatialized audio rendering with head-related transfer function (HRTF) filtering was used. The second group was tested with conventional stereo rendering, and the remaining group ran the experiment in a mute condition. Our results give a clear evidence that spatialized audio improves task performance compared to the unimodal mute condition. Since all task-relevant information was in the participants' field-of-view, we conclude that an enhancement of task performance results from a bimodal advantage due to the integration of visual and auditory spatial cues.
Integrating multiple views with virtual mirrors to facilitate scene understanding
Authors: Au Carmen E. , Clark James J.
Published: December 2011

In this article, an image integration technique called Virtual Mirroring (VM) is evaluated. VM is a technique that combines multiple 2D views of a 3D scene into a single composite image by overlaying views onto virtual mirrors. Given multiple views of a scene, one view is augmented with the remaining views by placing virtual mirrors on the first view and overlaying onto them the corresponding remaining views. Unlike a standard array presentation, where 2D views are not integrated and simply placed adjacent to one another, the VM presentation preserves the relative location, orientation, and scale between views. As such, it is our contention that humans will fare better at performing certain visual tasks, such as scene identification, when viewing a 3D scene via a VM presentation than when viewing an array presentation. We performed an experiment on 12 participants, where participants were required to identify 96 scenes both with a VM and an array presentation and we compared their % correctness and response times. Moreover, we studied the effects of adding an auditory attentional load on performance. We found that regardless of load, participants were able to identify scenes using VM presentation with greater accuracy and at greater speeds.
Beat space segmentation and octave scale cepstral feature for sung language recognition in pop music
Authors: Maddage Namunu C. , Li Haizhou
Published: December 2011

Sung language recognition relies on both effective feature extraction and acoustic modeling. In this paper, we study rhythm based music segmentation with the frame size being the duration of the smallest note in the music, as opposed to fixed length segmentation in spoken language recognition. It is found that acoustic features extracted from the rhythm based segmentation scheme outperform those from fixed length segmentation. We also study the effectiveness of a musically motivated acoustic feature.
Octave scale cepstral coefficients
(OSCCs) by comparing with the other acoustic features: Log frequency cepstral coefficients,
Linear prediction coefficients
(LPC) and LPC-derived cepstral coefficients. Finally, we examine the modeling capabilities of Gaussian mixture models and support vector machines in sung language recognition experiments. Experiments conducted on a corpus of 400 popular songs sung in English, Chinese, German, and Indonesian, showed that the OSCC feature outperforms other features. A sung language recognition accuracy of 64.9% was achieved when Gaussian mixture models were trained on shifted-delta-OSCC acoustic features, extracted via rhythm based music segmentation.
Efficient computation of queries on feature streams
Authors: Santini Simone
Published: December 2011

This article introduces the notion of
virtual feature stream
, a feature stream defined from a primary data stream, in which at any time only the features that are needed to compute the queries that are currently running in the system are computed.

Virtual feature streams are, in general, impossible to determine a priori, but the paper introduces an algorithm that stops the computation of features as soon as it can be proved that they are no longer needed thus generating, albeit in a roundabout and more expensive than the ideal way, a feature stream that is less expensive than the complete one to compute and safe: the queries that accept the virtual feature stream are those (and only those) that would accept the original feature stream.
SOS
Authors: Li Du , Srisa-an Witawas , Dwyer Matthew B.
Published: December 2011

Data races are subtle and difficult to detect errors that arise during concurrent program execution. Traditional testing techniques fail to find these errors, but recent research has shown that targeted dynamic analysis techniques can be developed to precisely detect races (i.e., no false race reports are generated) that occur during program execution. Unfortunately, precise race detection is still too expensive to be used in practice. State-of-the-art techniques still slow down program execution by a factor of eight or more. In this paper, we incorporate an optimization technique based on the observation that many thread-shared objects are written early in their lifetimes and then become read-only for the remainder of their lifetimes; these are known as stationary objects. The main contribution of our work is the insight that once a stationary object becomes thread-shared, races cannot occur. Therefore, our proposed approach does not monitor access to these objects. As such, our system only incurs an average overhead of 45% of that of an implementation of FastTrack, a low-overhead dynamic race detector. We then compared the effectiveness of our approach to de- tect races in deployed environments with that of Pacer, a sampling based race detector based on FastTrack. We found that our approach can detect over five times more races than Pacer when we budget 50% for runtime overhead.
Tool-supported refactoring for JavaScript
Authors: Feldthaus Asger , Millstein Todd , Møller Anders , Schäfer Max , Tip Frank
Published: December 2011

Refactoring is a popular technique for improving the structure of existing programs while maintaining their behavior. For statically typed programming languages such as Java, a wide variety of refactorings have been described, and tool support for performing refactorings and ensuring their correctness is widely available in modern IDEs. For the JavaScript programming language, however, existing refactoring tools are less mature and often unable to ensure that program behavior is preserved. Refactoring algorithms that have been developed for statically typed languages are not applicable to JavaScript because of its dynamic nature. We propose a framework for specifying and implementing JavaScript refactorings based on pointer analysis. We describe novel refactorings motivated by best practice recommendations for JavaScript programming, and demonstrate how they can be described concisely in terms of queries provided by our framework. Experiments performed with a prototype implementation on a suite of existing applications show that our approach is well-suited for developing practical refactoring tools for JavaScript.
HAWKEYE
Authors: Tripp Omer , Yorsh Greta , Field John , Sagiv Mooly
Published: December 2011

Parallelization transformations are an important vehicle for improving the performance and scalability of a software system. Utilizing concurrency requires that the developer first identify a suitable parallelization scope: one that poses as a performance bottleneck, and at the same time, exhibits considerable available parallelism. However, having identified a candidate scope, the developer still needs to ensure the correctness of the transformation. This is a difficult undertaking, where a major source of complication lies in tracking down sequential dependencies that inhibit parallelization and addressing them.

We report on Hawkeye, a dynamic dependence-analysis tool that is designed to assist programmers in pinpointing such impediments to parallelization. In contrast with field-based dependence analyses, which track concrete memory conflicts and thus suffer from a high rate of false reports, Hawkeye tracks dependencies induced by the abstract semantics of the data type while ignoring dependencing arising solely from implementation artifacts. This enables a more concise report, where the reported dependencies are more likely to be real as well as intelligible to the programmer.
Immutable specifications for more concise and precise verification
Authors: David Cristina , Chin Wei-Ngan
Published: December 2011

In the current work, we investigate the benefits of immutability guarantees for allowing more flexible handling of aliasing, as well as more precise and concise specifications. Our approach supports finer levels of control that can mark data structures as being immutable through the use of immutability annotations. By using such annotations to encode immutability guarantees, we expect to obtain better specifications that can more accurately describe the intentions, as well as prohibitions, of the method. Ultimately, our goal is improving the precision of the verification process, as well as making the specifications more readable, more precise and as an enforceable program documentation. We have designed and implemented a new entailment procedure to formally and automatically reason about immutability enhanced specifications. We have also formalised the soundness for our new procedure through an operational semantics with mutability assertions on the heap. Lastly, we have carried out a set of experiments to both validate and affirm the utility of our current proposal on immutability enhanced specification mechanism.
Oracle scheduling
Authors: Acar Umut A. , Charguéraud Arthur , Rainey Mike
Published: December 2011

A classic problem in parallel computing is determining whether to execute a task in parallel or sequentially. If small tasks are executed in parallel, the task-creation overheads can be overwhelming. If large tasks are executed sequentially, processors may spin idle. This granularity problem, however well known, is not well understood: broadly applicable solutions remain elusive.

We propose techniques for controlling granularity in implicitly parallel programming languages. Using a cost semantics for a general-purpose language in the style of the lambda calculus with support for parallelism, we show that task-creation overheads can indeed slow down parallel execution by a multiplicative factor. We then propose oracle scheduling, a technique for reducing these overheads, which bases granularity decisions on estimates of task-execution times. We prove that, for a class of computations, oracle scheduling can reduce task creation overheads to a small fraction of the work without adversely affecting available parallelism, thereby leading to efficient parallel executions.

We realize oracle scheduling in practice by a combination of static and dynamic techniques. We require the programmer to provide the asymptotic complexity of every function and use run-time profiling to determine the implicit, architecture-specific constant factors. In our experiments, we were able to reduce overheads of parallelism down to between 3 and 13 percent, while achieving 6- to 10-fold speedups.
Scalable join patterns
Authors: Turon Aaron J. , Russo Claudio V.
Published: December 2011

Coordination can destroy scalability in parallel programming. A comprehensive library of scalable synchronization primitives is therefore an essential tool for exploiting parallelism. Unfortunately, such primitives do not easily combine to yield solutions to more complex problems. We demonstrate that a concurrency library based on Fournet and Gonthier's join calculus can provide declarative and scalable coordination. By declarative, we mean that the programmer needs only to write down the constraints of a coordination problem, and the library will automatically derive a correct solution. By scalable, we mean that the derived solutions deliver robust performance both as the number of processors increases, and as the complexity of the coordination problem grows. We validate our claims empirically on seven coordination problems, comparing our generic solution to specialized algorithms from the literature.
Cedalion
Authors: Lorenz David H. , Rosenan Boaz
Published: December 2011

Language Oriented Programming (LOP) is a paradigm that puts domain specific programming languages (DSLs) at the center of the software development process. Currently, there are three main approaches to LOP: (1) the use of internal DSLs, implemented as libraries in a given host language; (2) the use of external DSLs, implemented as interpreters or compilers in an external language; and (3) the use of language workbenches, which are integrated development environments (IDEs) for defining and using external DSLs. In this paper, we contribute: (4) a novel language-oriented approach to LOP for defining and using internal DSLs. While language workbenches adapt internal DSL features to overcome some of the limitations of external DSLs, our approach adapts language workbench features to overcome some of the limitations of internal DSLs. We introduce Cedalion, an LOP host language for internal DSLs, featuring static validation and projectional editing. To validate our approach we present a case study in which Cedalion was used by biologists in designing a DNA microarray for molecular Biology research.
Variability-aware parsing in the presence of lexical macros and conditional compilation
Authors: Kästner Christian , Giarrusso Paolo G. , Rendel Tillmann , Erdweg Sebastian , Ostermann Klaus , Berger Thorsten
Published: December 2011

In many projects, lexical preprocessors are used to manage different variants of the project (using conditional compilation) and to define compile-time code transformations (using macros). Unfortunately, while being a simple way to implement variability, conditional compilation and lexical macros hinder automatic analysis, even though such analysis is urgently needed to combat variability-induced complexity. To analyze code with its variability, we need to parse it without preprocessing it. However, current parsing solutions use unsound heuristics, support only a subset of the language, or suffer from exponential explosion. As part of the TypeChef project, we contribute a novel variability-aware parser that can parse almost all unpreprocessed code without heuristics in practicable time. Beyond the obvious task of detecting syntax errors, our parser paves the road for further analysis, such as variability-aware type checking. We implement variability-aware parsers for Java and GNU C and demonstrate practicability by parsing the product line MobileMedia and the entire X86 architecture of the Linux kernel with 6065 variable features.
A simple abstraction for complex concurrent indexes
Authors: da Rocha Pinto Pedro , Dinsdale-Young Thomas , Dodds Mike , Gardner Philippa , Wheelhouse Mark
Published: December 2011

Indexes are ubiquitous. Examples include associative arrays, dictionaries, maps and hashes used in applications such as databases, file systems and dynamic languages. Abstractly, a sequential index can be viewed as a partial function from keys to values. Values can be queried by their keys, and the index can be mutated by adding or removing mappings. Whilst appealingly simple, this abstract specification is insufficient for reasoning about indexes accessed concurrently. We present an abstract specification for concurrent indexes. We verify several representative concurrent client applications using our specification, demonstrating that clients can reason abstractly without having to consider specific underlying implementations. Our specification would, however, mean nothing if it were not satisfied by standard implementations of concurrent indexes. We verify that our specification is satisfied by algorithms based on linked lists, hash tables and B-Link trees. The complexity of these algorithms, in particular the B-Link tree algorithm, can be completely hidden from the client's view by our abstract specification.
Composable, nestable, pessimistic atomic statements
Authors: Anderson Zachary , Gay David
Published: December 2011

In this paper we introduce a new method for pessimistically implementing composable, nestable atomic statements. Our mechanism, called shelters, is inspired by the synchronization strategy used in the Jade programming language. Unlike previous lock-based pessimistic approaches, our mechanism does not require a whole-program analysis that computes a global lock order. Further, this mechanism frees us to implement several optimizations, impossible with automatically inserted locks, that are necessary for scaling on recent multi-core systems. Additionally we show how our basic mechanism can be extended to support both open- and closed-nesting of atomic statements, something that, to our knowledge, has not yet been implemented fully-pessimistically in this context. Unlike optimistic, transactional-memory-based approaches, programmers using our mechanism do not have to write compensating actions for open-nesting, or worry about the possibly awkward semantics and performance impact of aborted transactions.

Similar to systems using locks, our implementation requires programmers to annotate the types of objects with the shelters that protect them, and indicate the sections of code to be executed atomically with atomic statements. A static analysis then determines from which shelters protection is needed for the atomic statements to run atomically. We have implemented shelter-based atomic statements for C, and applied our implementation to 12 benchmarks totaling over 200k lines of code including the STAMP benchmark suite, and the sqlite database system. Our implementation's performance is competitive with explicit locking, Autolocker, and a mature software transactional memory implementation.
Virtual values for language extension
Authors: Austin Thomas H. , Disney Tim , Flanagan Cormac
Published: December 2011

This paper focuses on extensibility, the ability of a programmer using a particular language to extend the expressiveness of that language. This paper explores how to provide an interesting notion of extensibility by virtualizing the interface between code and data. A virtual value is a special value that supports behavioral intercession. When a primitive operation is applied to a virtual value, it invokes a trap on that virtual value. A virtual value contains multiple traps, each of which is a user-defined function that describes how that operation should behave on that value. This paper formalizes the semantics of virtual values, and shows how they enable the definition of a variety of language extensions, including additional numeric types; delayed evaluation; taint tracking; contracts; revokable membranes; and units of measure. We report on our experience implementing virtual values for Javascript within an extension for the Firefox browser.
Flexible object layouts
Authors: Verwaest Toon , Bruni Camillo , Lungu Mircea , Nierstrasz Oscar
Published: December 2011

Programming idioms, design patterns and application libraries often introduce cumbersome and repetitive boilerplate code to a software system. Language extensions and external DSLs (domain specific languages) are sometimes introduced to reduce the need for boilerplate code, but they also complicate the system by introducing the need for language dialects and inter-language mediation. To address this, we propose to extend the structural reflective model of the language with object layouts, layout scopes and slots. Based on the new reflective language model we can 1) provide behavioral hooks to object layouts that are triggered when the fields of an object are accessed and 2) simplify the implementation of state-related language extensions such as stateful traits. By doing this we show how many idiomatic use cases that normally require boilerplate code can be more effectively supported.

We present an implementation in Smalltalk, and illustrate its usage through a series of extended examples.
A syntactic type system for recursive modules
Authors: Im Hyeonseung , Nakata Keiko , Garrigue Jacques , Park Sungwoo
Published: December 2011

A practical type system for ML-style recursive modules should address at least two technical challenges. First, it needs to solve the double vision problem, which refers to an inconsistency between external and internal views of recursive modules. Second, it needs to overcome the tension between practical decidability and expressivity which arises from the potential presence of cyclic type definitions caused by recursion between modules. Although type systems in previous proposals solve the double vision problem and are also decidable, they fail to typecheck common patterns of recursive modules, such as functor fixpoints, that are essential to the expressivity of the module system and the modular development of recursive modules. This paper proposes a novel type system for recursive modules that solves the double vision problem and typechecks common patterns of recursive modules including functor fixpoints. First, we design a type system with a type equivalence based on weak bisimilarity, which does not lend itself to practical implementation in general, but accommodates a broad range of cyclic type definitions. Then, we identify a practically implementable fragment using a type equivalence based on type normalization, which is expressive enough to typecheck typical uses of recursive modules. Our approach is purely syntactic and the definition of the type system is ready for use in an actual implementation.
RoleCast
Authors: Son Sooel , McKinley Kathryn S. , Shmatikov Vitaly
Published: December 2011

Web applications written in languages such as PHP and JSP are notoriously vulnerable to accidentally omitted authorization checks and other security bugs. Existing techniques that find missing security checks in library and system code assume that (1) security checks can be recognized syntactically and (2) the same pattern of checks applies universally to all programs. These assumptions do not hold for Web applications. Each Web application uses different variables and logic to check the user's permissions. Even within the application, security logic varies based on the user's role, e.g., regular users versus administrators. This paper describes ROLECAST, the first system capable of statically identifying security logic that mediates security-sensitive events (such as database writes) in Web applications, rather than taking a specification of this logic as input. We observe a consistent software engineering pattern-the code that implements distinct user role functionality and its security logic resides in distinct methods and files-and develop a novel algorithm for discovering this pattern in Web applications. Our algorithm partitions the set of file contexts (a coarsening of calling contexts) on which security-sensitive events are control dependent into roles. Roles are based on common functionality and security logic. ROLECAST identifies security-critical variables and applies rolespecific variable consistency analysis to find missing security checks. ROLECAST discovered 13 previously unreported, remotely exploitable vulnerabilities in 11 substantial PHP and JSP applications, with only 3 false positives.

This paper demonstrates that (1) accurate inference of application- and role-specific security logic improves the security of Web applications without specifications, and (2) static analysis can discover security logic automatically by exploiting distinctive software engineering features.
Memory systems in the many-core era
Authors: Mutlu Onur
Published: December 2011

The memory subsystem is a fundamental performance and energy bottleneck in almost all computing systems. Recent trends towards increasingly more cores on die, consolidation of diverse workloads on a single chip, and difficulty of DRAM scaling impose new requirements and exacerbate old demands on the memory system. In particular, the need for memory bandwidth and capacity is increasing [14], applications' interference in memory system increasingly limits system performance and makes the system hard to control [12], memory energy and power are key design concerns [8], and DRAM technology consumes significant amount of energy and does not scale down easily to smaller technology nodes [7]. Fortunately, some promising solution directions exist.

In this talk, we will examine recent technology, application, and architecture trends motivating a fundamental rethinking of the memory hierarchy. Based on this motivation, we will describe requirements from an ideal memory system suitable for the many-core era. The talk will examine questions one would need to answer in approximating the ideal memory system and possible avenues that seem promising for the research community to explore. In particular, we will focus on the problem of uncontrolled inter-application interference in the memory system and draw upon our experiences in solving it by designing quality-of-service (QoS) aware memory controllers [5, 6, 9, 10, 11, 12], interconnects [1 2 13], and entire memory systems. We will make a case forapplication- and QoS-aware design of memory systems and [3, 4]integrated/cooperative design of cores, interconnects, and memory components to optimize the overall system.
Short-term memory for self-collecting mutators
Authors: Aigner Martin , Haas Andreas , Kirsch Christoph M. , Lippautz Michael , Sokolova Ana , Stroka Stephanie , Unterweger Andreas
Published: December 2011

We propose a new memory model called short-term memory for managing objects on the heap. In contrast to the traditional persistent memory model for heap management, objects in short-term memory expire after a finite amount of time, which makes deallocation unnecessary. Instead, expiration of objects may be extended, if necessary, by refreshing. We have developed a concurrent, incremental, and non-moving implementation of short-term memory for explicit refreshing called self-collecting mutators that is based on programmer-controlled time and integrated into state-of-the-art runtimes of three programming languages: C, Java, and Go. All memory management operations run in constant time without acquiring any locks modulo the underlying allocators. Our implementation does not require any additional heap management threads, hence the name. Expired objects may be collected anywhere between one at a time for maximal incrementality and all at once for maximal throughput and minimal memory consumption. The integrated systems are heap management hybrids with persistent memory as default and short-term memory as option. Our approach is fully backwards compatible. Legacy code runs without any modifications with negligible runtime overhead and constant per-object space overhead. Legacy code can be modified to take advantage of short-term memory by having some but not all objects allocated in short-term memory and managed by explicit refreshing. We study single- and multi-threaded use cases in all three languages macro-benchmarking C and Java and micro-benchmarking Go. Our results show that using short-term memory (1) simplifies heap management in a state-of-the-art H.264 encoder written in C without additional time and minor space overhead, and (2) improves, at the expense of safety, memory management throughput, latency, and space consumption by reducing the number of garbage collection runs, often even to zero, for a number of Java and Go programs.
Garbage collection auto-tuning for Java mapreduce on multi-cores
Authors: Singer Jeremy , Kovoor George , Brown Gavin , Luján Mikel
Published: December 2011

MapReduce has been widely accepted as a simple programming pattern that can form the basis for efficient, large-scale, distributed data processing. The success of the MapReduce pattern has led to a variety of implementations for different computational scenarios. In this paper we present
MRJ
, a MapReduce Java framework for multi-core architectures. We evaluate its scalability on a four-core, hyperthreaded Intel Core i7 processor, using a set of standard MapReduce benchmarks. We investigate the significant impact that Java runtime garbage collection has on the performance and scalability of MRJ. We propose the use of memory management auto-tuning techniques based on machine learning. With our auto-tuning approach, we are able to achieve MRJ performance within 10% of optimal on 75% of our benchmark tests.