bluuebunny/crossref_metadata_2025 huggingface dataset:
Damage of the Bacterial Cell Envelope by Antimicrobial Peptides Gramicidin S and PGLa as Revealed by Transmission and Scanning Electron Microscopy
Authors: Hartmann Mareike , Berditsch Marina , Hawecker Jacques , Ardakani Mohammad Fotouhi , Gerthsen Dagmar , Ulrich Anne S.
Published: June 2010

Scanning electron microscopy (SEM) and transmission electron microscopy (TEM) were used to examine the ultrastructural changes in bacteria induced by antimicrobial peptides (AMPs). Both the β-stranded gramicidin S and the α-helical peptidyl-glycylleucine-carboxyamide (PGLa) are cationic amphiphilic AMPs known to interact with bacterial membranes. One representative Gram-negative strain,Escherichia coliATCC 25922, and one representative Gram-positive strain,Staphylococcus aureusATCC 25923, were exposed to the AMPs at sub-MICs and supra-MICs in salt-free medium. SEM revealed a shortening and swelling of theE. colicells, and multiple blisters and bubbles formed on their surface. TheS. aureuscells seemed to burst upon AMP exposure, showing open holes and deep craters in their envelope. TEM revealed the formation of intracellular membranous structures in both strains, which is attributed to a lateral expansion of the lipid membrane upon peptide insertion. Also, some morphological alterations in the DNA region were detected forS. aureus. AfterE. coliwas incubated with AMPs in medium with low ionic strength, the cells appeared highly turgid compared to untreated controls. This observation suggests that the AMPs enhance osmosis through the inner membrane, before they eventually cause excessive leakage of the cellular contents. The adverse effect on the osmoregulatory capacity of the bacteria is attributed to the membrane-permeabilizing action of the amphiphilic peptides, even at low (sub-MIC) AMP concentrations. Altogether, the results demonstrate that both TEM and SEM, as well as appropriate sample preparation protocols, are needed to obtain detailed mechanistic insights into peptide function.
Evaluation of Biophotonic Imaging To Estimate Bacterial Burden in Mice Infected with Highly Virulent Compared to Less Virulent
Streptococcus pneumoniae
Serotypes
Authors: Henken Stefanie , Bohling Jennifer , Ogunniyi A. David , Paton James C. , Salisbury Vyvyan C. , Welte Tobias , Maus Ulrich A.
Published: June 2010

Bioluminescence imaging is an innovative, noninvasive tool to analyze infectious disease progression under real-life conditions in small laboratory animals. However, the relevance of bioluminescence imaging to monitor invasive compared to noninvasive bacterial infections of the lung has not been examined so far. In the current study, we systematically evaluated the importance of bioluminescence imaging to monitor pneumococcal disease progression by correlating biophotonic signals with lung bacterial loads in two mouse strains (BALB/c, C57BL/6) infected with either self-glowing, bioluminescent serotype 19
Streptococcus pneumoniae
causing focal pneumonia or serotype 2
S. pneumoniae
causing invasive pneumococcal disease. The best correlations between bioluminescence signals and lung CFU counts were observed in BALB/c mice compared to C57BL/6 mice just on day 3 after infection with invasive serotype 2
S. pneumoniae
, while excellent correlations between photon counts and bacterial loads were observed in isolated lungs of BALB/c and C57BL/6 mice, irrespective of the employed pneumococcal serotype. Moreover, good correlations between biophotonic signals and CFU counts were also observed in mice upon infection with serotype 19
S. pneumoniae
causing focal pneumonia in mice, again with best correlation values obtained for BALB/c mice at day 3 postinfection. Collectively, we show that the relevance of biophotonic imaging to monitor
S. pneumoniae
-induced lung infections in mice is largely influenced by the disease model under investigation. The provided data may be important for studies of infectious diseases.
High-grade transformation of adenoid cystic carcinomas: a study of the expression of GLUT1 glucose transporter and of mitochondrial antigen
Authors: Bonfitto V L , Demasi A P , Costa A F , Bonfitto J F , Araujo V C , Altemani A
Published: June 2010

Aims

To broaden understanding of phenomena involved in progression from classical adenoid cystic carcinomas (ACCs) to tumours with high-grade transformation (ACC-HGT)

Methods

Expression of proteins linked to cellular metabolism as well as the microvascular density (MVD) in conventional and transformed areas were analysed. Findings were compared with ordinary ACCs. In seven cases of ACC-HGT and in 18 ACCs the expressions of GLUT1, mitochondrial antigen (MTA), CD34 (for assessing MVD), α-SMA and P63 (for detection of myoepithelial cells) and Ki-67 (for evaluation of proliferation index) were examined.

Results

The transformed component corresponded to adenocarcinomas with frequent (four cases) or scarce/absent (three cases) gland differentiation. In the latter, Ki-67 index was higher, two patients presented lymphatic metastasis and one died of disease. In the former, there was one long-term survivor and one with liver metastasis. Conventional areas of both ACC-HGT and ACC were negative for GLUT1 in most cases (83.3% and 81.3%, respectively) and exhibited low or no expression of MTA (100% and 66.7% of cases, respectively). In contrast, the HGT component presented increased expression of both proteins (GLUT1+ in 50% of cases; MTA+ in 100%). However, the degree of GLUT1 expression did not correlate with clinical outcome. MVD did not differ significantly between conventional and transformed components.

Conclusions

Transformation of classical ACC into ACC-HGT encompasses adenocarcinomas with variable degrees of differentiation and seems to lead to metabolic changes without reflection in tumour vasculature. Despite the tumours' higher GLUT1 expression, this protein has no utility as a prognostic marker.
Tobacco point-of-sale advertising in Guatemala City, Guatemala and Buenos Aires, Argentina
Authors: Barnoya Joaquin , Mejia Raul , Szeinman Debora , Kummerfeldt Carlos E
Published: June 2010

Objectives

To determine tobacco point of sale advertising prevalence in Guatemala City, Guatemala and Buenos Aires, Argentina.

Methods

Convenience stores (120 per city) were chosen from randomly selected blocks in low, middle and high socioeconomic neighbourhoods. To assess tobacco point of sale advertising we used a checklist developed in Canada that was translated into Spanish and validated in both countries studied. Analysis was conducted by neighbourhood and store type.

Results

All stores sold cigarettes and most had tobacco products in close proximity to confectionery. In Guatemala, 60% of stores had cigarette ads. High and middle socioeconomic status neighbourhood stores had more indoor cigarette ads, but these differences were determined by store type: gas stations and supermarkets were more prevalent in high socioeconomic status neighbourhoods and had more indoor cigarette ads. In poorer areas, however, more ads could be seen from outside the stores, more stores were located within 100 metres of schools and fewer stores had ‘No smoking’ or ‘No sales to minors’ signs. In Argentina, 80% of stores had cigarette ads and few differences were observed by neighbourhood socioeconomic status. Compared to Guatemala, ‘No sales to minors’ signs were more prevalent in Argentina.

Conclusions

Tobacco point of sale advertising is highly prevalent in these two cities of Guatemala and Argentina. An advertising ban should also include this type of advertising.
A NOTE ON SCALAR FIELD THEORY IN AdS3/CFT2
Authors: MINCES PABLO
Published: June 2010

We consider a scalar field theory in AdS d+1, and introduce a formalism on surfaces at equal values of the radial coordinate. In particular, we define the corresponding conjugate momentum. We compute the Noether currents for isometries in the bulk, and perform the asymptotic limit on the corresponding charges. We then introduce Poisson brackets at the border, and show that the asymptotic values of the bulk scalar field and the conjugate momentum transform as conformal fields of scaling dimensions Δ- and Δ+, respectively, where Δ± are the standard parameters giving the asymptotic behavior of the scalar field in AdS. Then we consider the case d = 2, where we obtain two copies of the Virasoro algebra, with vanishing central charge at the classical level. An AdS3/CFT2 prescription, giving the commutators of the boundary CFT in terms of the Poisson brackets at the border, arises in a natural way. We find that the boundary CFT is similar to a generalized ghost system. We introduce two different ground states, and then compute the normal ordering constants and quantum central charges, which depend on the mass of the scalar field and the AdS radius. We discuss certain implications of the results.
QUANTUM GRAVITY ASYMPTOTICS FROM THE SU(2) 15j-SYMBOL
Authors: BARRETT JOHN W. , FAIRBAIRN WINSTON J. , HELLMANN FRANK
Published: June 2010

The asymptotics of the SU(2) 15j-symbol are obtained using coherent states for the boundary data. The geometry of all nonsuppressed boundary data is given. For some boundary data, the resulting formula is interpreted in terms of the Regge action of the geometry of a 4-simplex in four-dimensional Euclidean space. This asymptotic formula can be used to derive and extend the asymptotics of the spin foam amplitudes for quantum gravity models. The relation of the SU(2) Ooguri model to these quantum gravity models and their continuum Lagrangians is discussed.
Tuning the capacity of search engines
Authors: Puppin Diego , Silvestri Fabrizio , Perego Raffaele , Baeza-Yates Ricardo
Published: June 2010

This article introduces an architecture for a document-partitioned search engine, based on a novel approach combining collection selection and load balancing, called
load-driven routing
. By exploiting the query-vector document model, and the incremental caching technique, our architecture can compute very high quality results for any query, with only a fraction of the computational load used in a typical document-partitioned architecture. By trading off a small fraction of the results, our technique allows us to strongly reduce the computing pressure to a search engine back-end; we are able to retrieve more than 2/3 of the top-5 results for a given query with only 10% the computing load needed by a configuration where the query is processed by each index partition. Alternatively, we can slightly increase the load up to 25% to improve precision and get more than 80% of the top-5 results. In fact, the flexibility of our system allows a wide range of different configurations, so as to easily respond to different needs in result quality or restrictions in computing power. More important, the system configuration can be adjusted dynamically in order to fit unexpected query peaks or unpredictable failures. This article wraps up some recent works by the authors, showing the results obtained by tests conducted on 6 million documents, 2,800,000 queries and real query cost timing as measured on an actual index.
Exploiting query logs for cross-lingual query suggestions
Authors: Gao Wei , Niu Cheng , Nie Jian-Yun , Zhou Ming , Wong Kam-Fai , Hon Hsiao-Wuen
Published: June 2010

Query suggestion aims to suggest relevant queries for a given query, which helps users better specify their information needs. Previous work on query suggestion has been limited to the same language. In this article, we extend it to cross-lingual query suggestion (CLQS): for a query in one language, we suggest similar or relevant queries in other languages. This is very important to the scenarios of cross-language information retrieval (CLIR) and other related cross-lingual applications. Instead of relying on existing query translation technologies for CLQS, we present an effective means to map the input query of one language to queries of the other language in the query log. Important monolingual and cross-lingual information such as word translation relations and word co-occurrence statistics, and so on, are used to estimate the cross-lingual query similarity with a discriminative model. Benchmarks show that the resulting CLQS system significantly outperforms a baseline system that uses dictionary-based query translation. Besides, we evaluate CLQS with French-English and Chinese-English CLIR tasks on TREC-6 and NTCIR-4 collections, respectively. The CLIR experiments using typical retrieval models demonstrate that the CLQS-based approach has significantly higher effectiveness than several traditional query translation methods. We find that when combined with pseudo-relevance feedback, the effectiveness of CLIR using CLQS is enhanced for different pairs of languages.
Register file partitioning and recompilation for register file power reduction
Authors: Guan Xuan , Fei Yunsi
Published: June 2010

Register files in modern embedded processors contribute a substantial budget in the energy consumption due to their large switching capacitance and long working time. For some embedded processors, on average 25% of registers account for 83% of register file accessing time. This motivates us to partition the register file into hot and cold regions, with the most frequently used registers placed in the hot region, and the rarely accessed ones in the cold region. We employ the bit-line splitting and drowsy register cell techniques to reduce the overall register file accessing power. We propose a novel approach to partition the register in a way that can achieve the largest power saving. We formulate the register file partitioning process into a graph partitioning problem, and apply an effective algorithm to obtain the optimal result. We evaluate our algorithm for MiBench and SPEC2000 applications on the SimpleScalar PISA system, and an average saving of 58.3% and 54.4% over the nonpartitioned register file accessing power is achieved. The area overhead is negligible, and the execution time overhead is acceptable (5.5% for MiBench 2.4% for SPEC2000). Further evaluation for MiBench applications is performed on Alpha and X86 system.
On-chip sensor-driven efficient thermal profile estimation algorithms
Authors: Zhang Yufu , Srivastava Ankur , Zahran Mohamed
Published: June 2010

This article addresses the problem of chip-level thermal profile estimation using runtime temperature sensor readings. We address the challenges of: (a) availability of only a few thermal sensors with constrained locations (sensors cannot be placed just anywhere); (b) random chip power density characteristics due to unpredictable workloads and fabrication variability. Firstly we model the random power density as a probability density function. Given such statistical characteristics and the runtime thermal sensor readings, we exploit the correlation in power dissipation among different chip modules to estimate the expected value of temperature at each chip location. Our methods are optimal if the underlying power density has Gaussian nature. We give a heuristic method to estimate the chip-level thermal profile when the underlying randomness is non-Gaussian. An extension of our method has also been proposed to address the dynamic case. Several speedup strategies are carefully investigated to improve the efficiency of the estimation algorithm. Experimental results indicated that, given only a few thermal sensors, our method can generate highly accurate chip-level thermal profile estimates within a few milliseconds.
An analysis of the dynamic behavior of JavaScript programs
Authors: Richards Gregor , Lebresne Sylvain , Burg Brian , Vitek Jan
Published: June 2010

The JavaScript programming language is widely used for web programming and, increasingly, for general purpose computing. As such, improving the correctness, security and performance of JavaScript applications has been the driving force for research in type systems, static analysis and compiler techniques for this language. Many of these techniques aim to reign in some of the most dynamic features of the language, yet little seems to be known about how programmers actually utilize the language or these features. In this paper we perform an empirical study of the dynamic behavior of a corpus of widely-used JavaScript programs, and analyze how and why the dynamic features are used. We report on the degree of dynamism that is exhibited by these JavaScript programs and compare that with assumptions commonly made in the literature and accepted industry benchmark suites.
Breadcrumbs
Authors: Bond Michael D. , Baker Graham Z. , Guyer Samuel Z.
Published: June 2010

Calling context--the set of active methods on the stack--is critical for understanding the dynamic behavior of large programs. Dynamic program analysis tools, however, are almost exclusively context insensitive because of the prohibitive cost of representing calling contexts at run time. Deployable dynamic analyses, in particular, have been limited to reporting only static program locations.

This paper presents Breadcrumbs, an efficient technique for recording and reporting dynamic calling contexts. It builds on an existing technique for computing a compact (one word) encoding of each calling context that client analyses can use in place of a program location. The key feature of our system is a search algorithm that can reconstruct a calling context from its encoding using only a static call graph and a small amount of dynamic information collected at cold (infrequently executed) callsites. Breadcrumbs requires no offline training or program modifications, and handles all language features, including dynamic class loading.

We use Breadcrumbs to add context sensitivity to two dynamic analyses: a data-race detector and an analysis for diagnosing null pointer exceptions. On average, it adds 10% to 20% runtime overhead, depending on a tunable parameter that controls how much dynamic information is collected. Collecting less information lowers the overhead, but can result in a search space explosion. In some cases this causes reconstruction to fail, but in most cases Breadcrumbs >produces non-trivial calling contexts that have the potential to significantly improve both the precision of the analyses and the quality of the bug reports.
A GPGPU compiler for memory optimization and parallelism management
Authors: Yang Yi , Xiang Ping , Kong Jingfei , Zhou Huiyang
Published: June 2010

This paper presents a novel optimizing compiler for general purpose computation on graphics processing units (GPGPU). It addresses two major challenges of developing high performance GPGPU programs: effective utilization of GPU memory hierarchy and judicious management of parallelism.

The input to our compiler is a naïve GPU kernel function, which is functionally correct but without any consideration for performance optimization. The compiler analyzes the code, identifies its memory access patterns, and generates both the optimized kernel and the kernel invocation parameters. Our optimization process includes vectorization and memory coalescing for memory bandwidth enhancement, tiling and unrolling for data reuse and parallelism management, and thread block remapping or address-offset insertion for partition-camping elimination. The experiments on a set of scientific and media processing algorithms show that our optimized code achieves very high performance, either superior or very close to the highly fine-tuned library, NVIDIA CUBLAS 2.2, and up to 128 times speedups over the naive versions. Another distinguishing feature of our compiler is the understandability of the optimized code, which is useful for performance analysis and algorithm refinement.
2010 Athena lecture
Authors: Eggers Susan
Published: June 2010

Susan Eggers, a Professor of Computer Science and Engineering at the University of Washington, joined her department in 1989. She received a B.A. in 1965 from Connecticut College and a Ph.D. in 1989 from the University of California, Berkeley. Her research interests are in computer architecture and back-end compiler optimization, with an emphasis on experimental performance analysis. With her colleague Hank Levy and their students, she developed the first commercially viable multithreaded architecture, Simultaneous Multithreading, adopted by Intel (as Hyperthreading), IBM, Sun and others. Her current research is in the areas of distributed dataflow machines, FPGAs and chip multiprocessors. In 1989 Professor Eggers was awarded an IBM Faculty Development Award, in 1990 an NSF Presidential Young Investigator Award, in 1994 the Microsoft Professorship in Computer Science and Engineering, and in 2009 the ACM-W Athena Lecturer. She is a Fellow of the ACM and IEEE, a Fellow of the AAAS, and a member of the National Academy of Engineering.
Safe to the last instruction
Authors: Yang Jean , Hawblitzel Chris
Published: June 2010

Typed assembly language (TAL) and Hoare logic can verify the absence of many kinds of errors in low-level code. We use TAL and Hoare logic to achieve highly automated, static verification of the safety of a new operating system called Verve. Our techniques and tools mechanically verify the safety of every assembly language instruction in the operating system, run-time system, drivers, and applications (in fact, every part of the system software except the boot loader). Verve consists of a "Nucleus" that provides primitive access to hardware and memory, a kernel that builds services on top of the Nucleus, and applications that run on top of the kernel. The Nucleus, written in verified assembly language, implements allocation, garbage collection, multiple stacks, interrupt handling, and device access. The kernel, written in C# and compiled to TAL, builds higher-level services, such as preemptive threads, on top of the Nucleus. A TAL checker verifies the safety of the kernel and applications. A Hoare-style verifier with an automated theorem prover verifies both the safety and correctness of the Nucleus. Verve is, to the best of our knowledge, the first operating system mechanically verified to guarantee both type and memory safety. More generally, Verve's approach demonstrates a practical way to mix high-level typed code with low-level untyped code in a verifiably safe manner.
Ur
Authors: Chlipala Adam
Published: June 2010

Dependent types
provide a strong foundation for specifying and verifying rich properties of programs through type-checking. The earliest implementations combined dependency, which allows types to mention program variables; with type-level computation, which facilitates expressive specifications that compute with recursive functions over types. While many recent applications of dependent types omit the latter facility, we argue in this paper that it deserves more attention, even when implemented without dependency.

In particular, the ability to use functional programs as specifications enables
statically-typed metaprogramming
: programs write programs, and static type-checking guarantees that the generating process never produces invalid code. Since our focus is on generic validity properties rather than full correctness verification, it is possible to engineer type inference systems that are very effective in narrow domains. As a demonstration, we present Ur, a programming language designed to facilitate metaprogramming with first-class records and names. On top of Ur, we implement Ur/Web, a special standard library that enables the development of modern Web applications. Ad-hoc code generation is already in wide use in the popular Web application frameworks, and we show how that generation may be tamed using types, without forcing metaprogram authors to write proofs or forcing metaprogram users to write any fancy types.
Parameterized verification of transactional memories
Authors: Emmi Michael , Majumdar Rupak , Manevich Roman
Published: June 2010

We describe an automatic verification method to check whether transactional memories ensure strict serializability a key property assumed of the transactional interface. Our main contribution is a technique for effectively verifying parameterized systems. The technique merges ideas from parameterized hardware and protocol verification--verification by invisible invariants and symmetry reduction--with ideas from software verification--template-based invariant generation and satisfiability checking for quantified formulæ (modulo theories). The combination enables us to precisely model and analyze unbounded systems while taming state explosion.

Our technique enables automated proofs that two-phase locking (TPL), dynamic software transactional memory (DSTM), and transactional locking II (TL2) systems ensure strict serializability. The verification is challenging since the systems are unbounded in several dimensions: the number and length of concurrently executing transactions, and the size of the shared memory they access, have no finite limit. In contrast, state-of-the-art software model checking tools such as BLAST and TVLA are unable to validate either system, due to inherent expressiveness limitations or state explosion.
Schism
Authors: Pizlo Filip , Ziarek Lukasz , Maj Petr , Hosking Antony L. , Blanton Ethan , Vitek Jan
Published: June 2010

Managed languages such as Java and C# are being considered for use in hard real-time systems. A hurdle to their widespread adoption is the lack of garbage collection algorithms that offer predictable space-and-time performance in the face of fragmentation. We introduce SCHISM/CMR, a new concurrent and real-time garbage collector that is fragmentation tolerant and guarantees time-and-space worst-case bounds while providing good throughput. SCHISM/CMR combines mark-region collection of fragmented objects and arrays (arraylets) with separate replication-copying collection of immutable arraylet spines, so as to cope with external fragmentation when running in small heaps. We present an implementation of SCHISM/CMR in the Fiji VM, a high-performance Java virtual machine for mission-critical systems, along with a thorough experimental evaluation on a wide variety of architectures, including server-class and embedded systems. The results show that SCHISM/CMR tolerates fragmentation better than previous schemes, with a much more acceptable throughput penalty.
Green
Authors: Baek Woongki , Chilimbi Trishul M.
Published: June 2010

Energy-efficient computing is important in several systems ranging from embedded devices to large scale data centers. Several application domains offer the opportunity to tradeoff quality of service/solution (QoS) for improvements in performance and reduction in energy consumption. Programmers sometimes take advantage of such opportunities, albeit in an ad-hoc manner and often without providing any QoS guarantees.

We propose a system called Green that provides a simple and flexible framework that allows programmers to take advantage of such approximation opportunities in a systematic manner while providing statistical QoS guarantees. Green enables programmers to approximate expensive functions and loops and operates in two phases. In the calibration phase, it builds a model of the QoS loss produced by the approximation. This model is used in the operational phase to make approximation decisions based on the QoS constraints specified by the programmer. The operational phase also includes an adaptation function that occasionally monitors the runtime behavior and changes the approximation decisions and QoS model to provide strong statistical QoS guarantees.

To evaluate the effectiveness of Green, we implemented our system and language extensions using the Phoenix compiler framework. Our experiments using benchmarks from domains such as graphics, machine learning, signal processing, and finance, and an in-production, real-world web search engine, indicate that Green can produce significant improvements in performance and energy consumption with small and controlled QoS degradation.
Adversarial memory for detecting destructive races
Authors: Flanagan Cormac , Freund Stephen N.
Published: June 2010

Multithreaded programs are notoriously prone to race conditions, a problem exacerbated by the widespread adoption of multi-core processors with complex memory models and cache coherence protocols. Much prior work has focused on static and dynamic analyses for race detection, but these algorithms typically are unable to distinguish destructive races that cause erroneous behavior from benign races that do not. Performing this classification manually is difficult, time consuming, and error prone.

This paper presents a new dynamic analysis technique that uses
adversarial memory
to classify race conditions as destructive or benign on systems with relaxed memory models. Unlike a typical language implementation, which may only infrequently exhibit non-sequentially consistent behavior, our adversarial memory implementation exploits the full freedom of the memory model to return older, unexpected, or stale values for memory reads whenever possible, in an attempt to crash the target program (that is, to force the program to behave erroneously). A crashing execution provides concrete evidence of a destructive bug, and this bug can be strongly correlated with a specific race condition in the target program.

Experimental results with our Jumble prototype for Java demonstrate that adversarial memory is highly effective at identifying destructive race conditions, and in distinguishing them from race conditions that are real but benign. Adversarial memory can also reveal destructive races that would not be detected by traditional testing (even after thousands of runs) or by model checkers that assume sequential consistency.
PACER
Authors: Bond Michael D. , Coons Katherine E. , McKinley Kathryn S.
Published: June 2010

Data races indicate serious concurrency bugs such as order, atomicity, and sequential consistency violations. Races are difficult to find and fix, often manifesting only after deployment. The frequency and unpredictability of these bugs will only increase as software adds parallelism to exploit multicore hardware. Unfortunately, sound and precise race detectors slow programs by factors of eight or more and do not scale to large numbers of threads.

This paper presents a precise, low-overheadsampling-baseddata race detector called Pacer. PACER makes aproportionalityguarantee: it detects any race at a rate equal to the sampling rate, by finding races whose first access occurs during a global sampling period. During sampling, PACER tracks all accesses using the dynamically sound and precise FastTrack algorithm. In nonsampling periods, Pacer discards sampled access information that cannot be part of a reported race,andPacer simplifies tracking of the happens-before relationship, yielding near-constant, instead of linear, overheads. Experimental results confirm our theoretical guarantees. PACER reports races in proportion to the sampling rate. Its time and space overheads scale with the sampling rate, and sampling rates of 1-3% yield overheads low enough to consider in production software. The resulting system provides a "get what you pay for" approach that is suitable for identifying real, hard-to-reproduce races in deployed systems.
Resolving and exploiting the
k
-CFA paradox
Authors: Might Matthew , Smaragdakis Yannis , Van Horn David
Published: June 2010

Low-level program analysis is a fundamental problem, taking the shape of "flow analysis" in functional languages and "points-to" analysis in imperative and object-oriented languages. Despite the similarities, the vocabulary and results in the two communities remain largely distinct, with limited cross-understanding. One of the few links is Shivers's
k
-CFA work, which has advanced the concept of "context-sensitive analysis" and is widely known in both communities.

Recent results indicate that the relationship between the functional and object-oriented incarnations of
k
-CFA is not as well understood as thought. Van Horn and Mairson proved
k
-CFA for
k
≥ 1 to be EXPTIME-complete; hence, no polynomial-time algorithm can exist. Yet, there are several polynomial-time formulations of context-sensitive points-to analyses in object-oriented languages. Thus, it seems that functional
k
-CFA may actually be a profoundly different analysis from object-oriented
k
-CFA. We resolve this paradox by showing that the exact same specification of
k
-CFA is polynomial-time for object-oriented languages yet exponential-time for functional ones: objects and closures are subtly different, in a way that interacts crucially with context-sensitivity and complexity. This illumination leads to an immediate payoff: by projecting the object-oriented treatment of objects onto closures, we derive a polynomial-time hierarchy of context-sensitive CFAs for functional programs.
Line-up
Authors: Burckhardt Sebastian , Dern Chris , Musuvathi Madanlal , Tan Roy
Published: June 2010

Modular development of concurrent applications requires thread-safe components that behave correctly when called concurrently by multiple client threads. This paper focuses on linearizability, a specific formalization of thread safety, where all operations of a concurrent component appear to take effect instantaneously at some point between their call and return. The key insight of this paper is that if a component is intended to be deterministic, then it is possible to build an automatic linearizability checker by systematically enumerating the sequential behaviors of the component and then checking if each its concurrent behavior is equivalent to some sequential behavior.

We develop this insight into a tool called Line-Up, the first complete and automatic checker for
deterministic linearizability
. It is complete, because any reported violation proves that the implementation is not linearizable with respect to
any
sequential deterministic specification. It is automatic, requiring no manual abstraction, no manual specification of semantics or commit points, no manually written test suites, no access to source code.

We evaluate Line-Up by analyzing 13 classes with a total of 90 methods in two versions of the .NET Framework 4.0. The violations of deterministic linearizability reported by Line-Up exposed seven errors in the implementation that were fixed by the development team.
DRFX
Authors: Marino Daniel , Singh Abhayendra , Millstein Todd , Musuvathi Madanlal , Narayanasamy Satish
Published: June 2010

The most intuitive memory model for shared-memory multithreaded programming is
sequential consistency
(SC), but it disallows the use of many compiler and hardware optimizations thereby impacting performance. Data-race-free (DRF) models, such as the proposed C++0x memory model, guarantee SC execution for datarace-free programs. But these models provide no guarantee at all for racy programs, compromising the safety and debuggability of such programs. To address the safety issue, the Java memory model, which is also based on the DRF model, provides a weak semantics for racy executions. However, this semantics is subtle and complex, making it difficult for programmers to reason about their programs and for compiler writers to ensure the correctness of compiler optimizations.

We present the DRFx memory model, which is simple for programmers to understand and use while still supporting many common optimizations. We introduce a
memory model (MM) exception
which can be signaled to halt execution. If a program executes without throwing this exception, then DRFx guarantees that the execution is SC. If a program throws an MM exception during an execution, then DRFx guarantees that the program has a data race. We observe that SC violations can be detected in hardware through a lightweight form of conflict detection. Furthermore, our model safely allows aggressive compiler and hardware optimizations within compiler-designated program regions. We formalize our memory model, prove several properties about this model, describe a compiler and hardware design suitable for DRFx, and evaluate the performance overhead due to our compiler and hardware requirements.
FlumeJava
Authors: Chambers Craig , Raniwala Ashish , Perry Frances , Adams Stephen , Henry Robert R. , Bradshaw Robert , Weizenbaum Nathan
Published: June 2010

MapReduce and similar systems significantly ease the task of writing data-parallel code. However, many real-world computations require a pipeline of MapReduces, and programming and managing such pipelines can be difficult. We present FlumeJava, a Java library that makes it easy to develop, test, and run efficient data-parallel pipelines. At the core of the FlumeJava library are a couple of classes that represent immutable parallel collections, each supporting a modest number of operations for processing them in parallel. Parallel collections and their operations present a simple, high-level, uniform abstraction over different data representations and execution strategies. To enable parallel operations to run efficiently, FlumeJava defers their evaluation, instead internally constructing an execution plan dataflow graph. When the final results of the parallel operations are eventually needed, FlumeJava first optimizes the execution plan, and then executes the optimized operations on appropriate underlying primitives (e.g., MapReduces). The combination of high-level abstractions for parallel data and computation, deferred evaluation and optimization, and efficient parallel primitives yields an easy-to-use system that approaches the efficiency of hand-optimized pipelines. FlumeJava is in active use by hundreds of pipeline developers within Google.
Bamboo
Authors: Zhou Jin , Demsky Brian
Published: June 2010

Traditional data-oriented programming languages such as dataflow languages and stream languages provide a natural abstraction for parallel programming. In these languages, a developer focuses on the flow of data through the computation and these systems free the developer from the complexities of low-level, thread-oriented concurrency primitives. This simplification comes at a cost --- traditional data-oriented approaches restrict the mutation of state and, in practice, the types of data structures a program can effectively use. Bamboo borrows from work in typestate and software transactions to relax the traditional restrictions of data-oriented programming models to support mutation of arbitrary data structures.

We have implemented a compiler for Bamboo which generates code for the TILEPro64 many-core processor. We have evaluated this implementation on six benchmarks: Tracking, a feature tracking algorithm from computer vision; KMeans, a K-means clustering algorithm; MonteCarlo, a Monte Carlo simulation; FilterBank, a multi-channel filter bank; Fractal, a Mandelbrot set computation; and Series, a Fourier series computation. We found that our compiler generated implementations that obtained speedups ranging from 26.2x to 61.6x when executed on 62 cores.
Mint
Authors: Westbrook Edwin , Ricken Mathias , Inoue Jun , Yao Yilong , Abdelatif Tamer , Taha Walid
Published: June 2010

Multi-stage programming (MSP) provides a disciplined approach to run-time code generation. In the purely functional setting, it has been shown how MSP can be used to reduce the overhead of abstractions, allowing clean, maintainable code without paying performance penalties. Unfortunately, MSP is difficult to combine with imperative features, which are prevalent in mainstream languages. The central difficulty is scope extrusion, wherein free variables can inadvertently be moved outside the scopes of their binders. This paper proposes a new approach to combining MSP with imperative features that occupies a "sweet spot" in the design space in terms of how well useful MSP applications can be expressed and how easy it is for programmers to understand. The key insight is that escapes (or "anti-quotes") must be weakly separable from the rest of the code, i.e. the computational effects occurring inside an escape that are visible outside the escape are guaranteed to not contain code. To demonstrate the feasibility of this approach, we formalize a type system based on Lightweight Java which we prove sound, and we also provide an implementation, called Mint, to validate both the expressivity of the type system and the effect of staging on the performance of Java programs.
Software data spreading
Authors: Kamruzzaman Md , Swanson Steven , Tullsen Dean M.
Published: June 2010

Single thread performance remains an important consideration even for multicore, multiprocessor systems. As a result, techniques for improving single thread performance using multiple cores have received considerable attention. This work describes a technique,
software data spreading
, that leverages the cache capacity of extra cores and extra sockets rather than their computational resources. Software data spreading is a software-only technique that uses compiler-directed thread migration to aggregate cache capacity across cores and chips and improve performance. This paper describes an automated scheme that applies data spreading to various types of loops. Experiments with a set of SPEC2000, SPEC2006, NAS, and microbenchmark workloads show that data spreading can provide speedup of over 2, averaging 17% for the SPEC and NAS applications on two systems. In addition, despite using more cores for the same computation, data spreading actually saves power since it reduces access to DRAM.
Z-rays
Authors: Sartor Jennifer B. , Blackburn Stephen M. , Frampton Daniel , Hirzel Martin , McKinley Kathryn S.
Published: June 2010

Arrays are the ubiquitous organization for indexed data. Throughout programming language evolution, implementations have laid out arrays contiguously in memory. This layout is problematic in space and time. It causes heap fragmentation, garbage collection pauses in proportion to array size, and wasted memory for sparse and over-provisioned arrays. Because of array virtualization in managed languages, an array layout that consists of indirection pointers to fixed-size discontiguous memory blocks can mitigate these problems transparently. This design however incurs significant overhead, but is justified when real-time deadlines and space constraints trump performance.

This paper proposes
z-rays
, a discontiguous array design with flexibility and efficiency. A z-ray has a spine with indirection pointers to fixed-size memory blocks called
arraylets
, and uses five optimizations: (1) inlining the first N array bytes into the spine, (2) lazy allocation, (3) zero compression, (4) fast array copy, and (5) arraylet copy-on-write. Whereas discontiguous arrays in prior work improve responsiveness and space efficiency, z-rays combine time efficiency and flexibility. On average, the best z-ray configuration performs within 12.7% of an unmodified Java Virtual Machine on 19 benchmarks, whereas previous designs have
two to three times
higher overheads. Furthermore, language implementers can configure z-ray optimizations for various design goals. This combination of performance and flexibility creates a better building block for past and future array optimization.
A Perl primer for evolutionary algorithm practitioners
Authors: Merelo Juan-Julián
Published: June 2010

It is curious that the Perl language is not widely used within the Evolutionary Algorithms community, since the main virtues of a Perl programmer can also be applied to the general EA practitioner. These virtues are Impatience, Laziness and Hubris [3], and it is evident that we try to evolve something from the initial, random, chaos, appearing then as godlike creatures to our humble chromosomes with high fitness, thus being prone to the most important of the triad, Hubris. And who's not to say that evolutionary algorithms are for lazy slobs? Instead of devising an analytical solution to a problem, or greedily building it piece by painstaking and carefully designed piece, we just cobble together a fitness function and let the evolutionary algorithm have a go at the problem. If anything, we might fiddle a bit with operator rates, but not much more; we do not even care about understanding the problem (we leave that for memetic algorithm practitioners). Just the fitness, ma'am, no need to do any hard work.
Lpin1 in human visceral and subcutaneous adipose tissue: similar levels but different associations with lipogenic and lipolytic genes
Authors: Miranda Merce , Escoté Xavier , Alcaide María J. , Solano Esther , Ceperuelo-Mallafré Victòria , Hernández Pilar , Wabitsch Martin , Vendrell Joan
Published: June 2010

LPIN1 is a gene with important effects on lipidic and metabolic homeostasis. Human subcutaneous LPIN1 expression levels in adipose tissue are related with a better metabolic profile, including insulin sensitivity markers. However, there are few data on the regulation of LPIN1 in visceral adipose tissue (VAT). Our aim was to perform a cross-sectional analysis of VAT compared with subcutaneous (SAT) LPIN1 expression in a well-characterized obese cohort, its relation with the expression of genes involved in lipid metabolism, and the in vitro response to lipogenic and lipolytic stimuli. A downregulation of total LPIN1 mRNA expression in subjects with obesity was found in VAT similarly to that in SAT. Despite similar total LPIN1 mRNA levels in SAT and VAT, a close relationship with clinical parameters and with many lipogenic and lipolytic genes was observed primarily in SAT depot. As shown in the in vitro analysis, the low-grade proinflammatory environment and the insulin resistance associated with obesity may contribute to downregulate LPIN1 in adipose tissue, leading to a worse metabolic profile.
Razumikhin Stability Theorem for Fractional Systems with Delay
Authors: Baleanu D. , Sadati S. J. , Ghaderi R. , Ranjbar A. , Abdeljawad (Maraaba) T. , Jarad F.
Published: June 2010

Fractional calculus techniques and methods started to be applied successfully during the last decades in several fields of science and engineering. In this paper we studied the stability of fractional‐order nonlinear time‐delay systems for Riemann‐Liouville and Caputo derivatives and we extended Razumikhin theorem for the fractional nonlinear time‐delay systems.
Effects of Snail Density on Growth, Reproduction and Survival ofBiomphalaria alexandrinaExposed toSchistosoma mansoni
Authors: Mangal T. D. , Paterson S. , Fenton A.
Published: June 2010

The effects of snail density onBiomphalaria alexandrinaparasitized withSchistosoma mansoniwere investigated. Laboratory experiments were used to quantify the impact of high density on snail growth, fecundity, and survival. Density-dependent birth rates of snails were determined to inform mathematical models, which, until now, have assumed a linear relationship between density and fecundity. The experiments show that the rate of egg-laying followed a negative exponential distribution with increasing density and this was significantly affected by exposure to parasitic infection. High density also affected the weight of snails and survival to a greater degree than exposure to parasitic infection. Although snail growth rates were initially constrained by high density, they retained the potential for growth suggesting a reversible density-dependent mechanism. These experimental data can be used to parameterise models and confirm that snail populations are regulated by nonlinear density-dependent mechanisms.