bluuebunny/crossref_metadata_2025 huggingface dataset:
Automated verification of practical garbage collectors
Authors: Hawblitzel Chris , Petrank Erez
Published: August 2009

Garbage collectors are notoriously hard to verify, due to their low-level interaction with the underlying system and the general difficulty in reasoning about reachability in graphs. Several papers have presented verified collectors, but either the proofs were hand-written or the collectors were too simplistic to use on practical applications. In this work, we present two mechanically verified garbage collectors, both practical enough to use for real-world C# benchmarks. The collectors and their associated allocators consist of x86 assembly language instructions and macro instructions, annotated with preconditions, postconditions, invariants, and assertions. We used the Boogie verification generator and the Z3 automated theorem prover to verify this assembly language code mechanically. We provide measurements comparing the performance of the verified collector with that of the standard Bartok collectors on off-the-shelf C# benchmarks, demonstrating their competitiveness.
Multi-core demands multi-interfaces
Authors: Patt Yale N.
Published: August 2009

The challenge for the microarchitect has always been (with very few notable domain-specific exceptions) how to translate the continually increasing processing power provided by Moore's Law into increased performance, or more recently into similar performance at lower cost in energy. The mechanisms in the past (almost entirely) kept the interface intact and used the increase in transistor count to improve the performance of the microarchitecture of the uniprocessor. When that became too hard, we went to larger and larger on-chip caches. Both are consistent with the notion that "abstractions are good." At some point, we got overwhelmed with too many transistors; predictably, multi-core was born. As the transistor count continues to skyrocket, we are faced with two questions: what should be on the chip, and how should the software interface to it. If we expect to continue to take advantage of what process technology is providing, I think we need to do several things, starting with rethinking the notion of abstraction and providing multiple interfaces for the programmer.
How to build programmable multi-core chips
Authors: Dennis Jack B.
Published: August 2009

The arrival of multi-core chips has heightened interest in the discipline of parallel programming, a topic that has received much attention for many years. Computer architects have much to learn from sound principles for structuring software and expressing parallel computation. This talk will cover principles for the design of computer systems to support composable parallel software - the idea that any parallel program is usable, without change, as a component of larger parallel programs. By following these principles, a revolution in the ease of building robust and high-performance parallel software can be achieved. The principles suggest interesting directions for computer architecture; the tools to experiment with new architecture concepts are ready and waiting for the savvy and ambitious researcher
How much parallelism is there in irregular applications?
Authors: Kulkarni Milind , Burtscher Martin , Inkulu Rajeshkar , Pingali Keshav , Casçaval Calin
Published: August 2009

Irregular programs are programs organized around pointer-based data structures such as trees and graphs. Recent investigations by the Galois project have shown that many irregular programs have a generalized form of data-parallelism called
amorphous data-parallelism
. However, in many programs, amorphous data-parallelism cannot be uncovered using static techniques, and its exploitation requires runtime strategies such as optimistic parallel execution. This raises a natural question: how much amorphous data-parallelism actually exists in irregular programs?

In this paper, we describe the design and implementation of a tool called ParaMeter that produces
parallelism profiles
for irregular programs. Parallelism profiles are an abstract measure of the amount of amorphous data-parallelism at different points in the execution of an algorithm, independent of implementation-dependent details such as the number of cores, cache sizes, load-balancing, etc. ParaMeter can also generate constrained parallelism profiles for a fixed number of cores. We show parallelism profiles for seven irregular applications, and explain how these profiles provide insight into the behavior of these applications.
An efficient transactional memory algorithm for computing minimum spanning forest of sparse graphs
Authors: Kang Seunghwa , Bader David A.
Published: August 2009

Due to power wall, memory wall, and ILP wall, we are facing the end of ever increasing single-threaded performance. For this reason, multicore and manycore processors are arising as a new paradigm to pursue. However, to fully exploit all the cores in a chip, parallel programming is often required, and the complexity of parallel programming raises a significant concern. Data synchronization is a major source of this programming complexity, and Transactional Memory is proposed to reduce the difficulty caused by data synchronization requirements, while providing high scalability and low performance overhead.

The previous literature on Transactional Memory mostly focuses on architectural designs. Its impact on algorithms and applications has not yet been studied thoroughly. In this paper, we investigate Transactional Memory from the algorithm designer's perspective. This paper presents an algorithmic model to assist in the design of efficient Transactional Memory algorithms and a novel Transactional Memory algorithm for computing a minimum spanning forest of sparse graphs. We emphasize multiple Transactional Memory related design issues in presenting our algorithm. We also provide experimental results on an existing software Transactional Memory system. Our algorithm demonstrates excellent scalability in the experiments, but at the same time, the experimental results reveal the clear limitation of software Transactional Memory due to its high performance overhead. Based on our experience, we highlight the necessity of efficient hardware support for Transactional Memory to realize the potential of the technology.
Atomic quake
Authors: Zyulkyarov Ferad , Gajinov Vladimir , Unsal Osman S. , Cristal Adrián , Ayguadé Eduard , Harris Tim , Valero Mateo
Published: August 2009

Transactional Memory (TM) is being studied widely as a new technique for synchronizing concurrent accesses to shared memory data structures for use in multi-core systems. Much of the initial work on TM has been evaluated using microbenchmarks and application kernels; it is not clear whether conclusions drawn from these workloads will apply to larger systems. In this work we make the first attempt to develop a large, complex, application that uses TM for all of its synchronization. We describe how we have taken an existing parallel implementation of the Quake game server and restructured it to use transactions. In doing so we have encountered examples where transactions simplify the structure of the program. We have also encountered cases where using transactions occludes the structure of the existing code. Compared with existing TM benchmarks, our workload exhibits non-block-structured transactions within which there are I/Ooperations and system call invocations. There are long and short running transactions (200-1.3M cycles) with small and large read and write sets (a few bytes to 1.5MB). There are nested transactions reaching up to 9 levels at runtime. There are examples where error handling and recovery occurs inside transactions. There are also examples where data changes between being accessed transactionally and accessed non-transactionally. However, we did not see examples where the kind of access to one piece of data depended on the value of another.
Application-aware management of parallel simulation collections
Authors: Yau Siu , Karamcheti Vijay , Zorin Denis , Damevski Kostadin , Parker Steven G.
Published: August 2009

This paper presents a system deployed on parallel clusters to manage a collection of parallel simulations that make up a computational study. It explores how such a system can extend traditional parallel job scheduling and resource allocation techniques to incorporate knowledge specific to the study.

Using a UINTAH-based helium gas simulation code (ARCHES) and the SimX system for multi-experiment computational studies, this paper demonstrates that, by using application-specific knowledge in resource allocation and scheduling decisions, one can reduce the run time of a computational study from over 20 hours to under 4.5 hours on a 32-processor cluster, and from almost 11 hours to just over 3.5 hours on a 64-processor cluster.
Idempotent work stealing
Authors: Michael Maged M. , Vechev Martin T. , Saraswat Vijay A.
Published: August 2009

Load balancing is a technique which allows efficient parallelization of irregular workloads, and a key component of many applications and parallelizing runtimes. Work-stealing is a popular technique for implementing load balancing, where each parallel thread maintains its own work set of items and occasionally steals items from the sets of other threads.

The conventional semantics of work stealing guarantee that each inserted task is eventually extracted exactly once. However, correctness of a wide class of applications allows for relaxed semantics, because either: i) the application already explicitly checks that no work is repeated or ii) the application can tolerate repeated work.

In this paper, we introduce
idempotent work tealing
, and present several new algorithms that exploit the relaxed semantics to deliver better performance. The semantics of the new algorithms guarantee that each inserted task is eventually extracted
at least
once-instead of
exactly
once.

On mainstream processors, algorithms for conventional work stealing require special atomic instructions or store-load memory ordering fence instructions in the owner's critical path operations. In general, these instructions are substantially slower than regular memory access instructions. By exploiting the relaxed semantics, our algorithms avoid these instructions in the owner's operations.

We evaluated our algorithms using common graph problems and micro-benchmarks and compared them to well-known conventional work stealing algorithms, the THE Cilk and Chase-Lev algorithms. We found that our best algorithm (with LIFO extraction) outperforms existing algorithms in nearly all cases, and often by significant margins.
Backtracking-based load balancing
Authors: Hiraishi Tasuku , Yasugi Masahiro , Umatani Seiji , Yuasa Taiichi
Published: August 2009

High-productivity languages for parallel computing become more important as parallel environments including multicores become more common. Cilk is such a language. It provides good load balancing for many applications including irregular ones; that is, it keeps all workers busy by creating plenty of "logical" threads and adopting the oldest-first work stealing strategy. This paper proposes a "logical thread"-free framework called
Tascell
, which achieves a higher performance and supports a wider range of parallel environments including clusters without loss of productivity. A Tascell worker spawns a "real" task only when requested by another idle worker. The worker performs the spawning by temporarily "backtracking" and restoring its oldest task-spawnable state. Our approach eliminates the cost of spawning/managing logical threads. It also promotes the reuse of workspaces and improves the locality of reference since it does not need to prepare a workspace for each concurrently runnable logical thread. Furthermore, Tascell enables elegant and highly-efficient backtrack search algorithms with delayed workspace copying. For instance, our 16-queens problem solver is 1.86 times faster than Cilk on a system with two dual-core processors. Our approach also enables a single program to run in both shared and distributed memory environments with reasonable efficiency and scalability.
Mapping parallelism to multi-cores
Authors: Wang Zheng , O'Boyle Michael F.P.
Published: August 2009

The efficient mapping of program parallelism to multi-core processors is highly dependent on the underlying architecture. This paper proposes a portable and automatic compiler-based approach to mapping such parallelism using machine learning. It develops two predictors: a data sensitive and a data insensitive predictor to select the best mapping for parallel programs. They predict the number of threads and the scheduling policy for any given program using a model learnt off-line. By using low-cost profiling runs, they predict the mapping for a new unseen program across multiple input data sets. We evaluate our approach by selecting parallelism mapping configurations for OpenMP programs on two representative but different multi-core platforms (the Intel Xeon and the Cell processors). Performance of our technique is stable across programs and architectures. On average, it delivers above 96% performance of the maximum available on both platforms. It achieve, on average, a 37% (up to 17.5
times
) performance improvement over the OpenMP runtime default scheme on the Cell platform. Compared to two recent prediction models, our predictors achieve better performance with a significant lower profiling cost.
Serialization sets
Authors: Allen Matthew D. , Sridharan Srinath , Sohi Gurindar S.
Published: August 2009

This paper proposes a new parallel execution model where programmers augment a sequential program with pieces of code called
serializers
that dynamically map computational operations into
serialization sets
of dependent operations. A runtime system executes operations in the same serialization set in program order, and may concurrently execute operations in different sets. Because serialization sets establish a logical ordering on all operations, the resulting parallel execution is predictable and deterministic.

We describe the API and design of Prometheus, a C++ library that implements the serialization set abstraction through compile-time template instantiation and a runtime support library. We evaluate a set of parallel programs running on the x86_64 and SPARC-V9 instruction sets and study their performance on multicore, symmetric multiprocessor, and ccNUMA parallel machines. By contrast with conventional parallel execution models, we find that Prometheus programs are significantly easier to write, test, and debug, and their parallel execution achieves comparable performance.
OpenMP to GPGPU
Authors: Lee Seyong , Min Seung-Jai , Eigenmann Rudolf
Published: August 2009

GPGPUs have recently emerged as powerful vehicles for general-purpose high-performance computing. Although a new Compute Unified Device Architecture (CUDA) programming model from NVIDIA offers improved programmability for general computing, programming GPGPUs is still complex and error-prone. This paper presents a compiler framework for automatic source-to-source translation of standard OpenMP applications into CUDA-based GPGPU applications. The goal of this translation is to further improve programmability and make existing OpenMP applications amenable to execution on GPGPUs. In this paper, we have identified several key transformation techniques, which enable efficient GPU global memory access, to achieve high performance. Experimental results from two important kernels (JACOBI and SPMUL) and two NAS OpenMP Parallel Benchmarks (EP and CG) show that the described translator and compile-time optimizations work well on both regular and irregular applications, leading to performance improvements of up to 50X over the unoptimized translation (up to 328X over serial).
Comparability graph coloring for optimizing utilization of stream register files in stream processors
Authors: Yang Xuejun , Wang Li , Xue Jingling , Deng Yu , Zhang Ying
Published: August 2009

A stream processor executes an application that has been decomposed into a sequence of kernels that operate on streams of data elements. During the execution of a kernel, all streams accessed must be communicated through the SRF (Stream Register File), a non-bypassing software-managed on-chip memory. Therefore, optimizing utilization of the SRF is crucial for good performance. The key insight is that the interference graphs formed by the streams in stream applications tend to be comparability graphs or decomposable into a set of multiple comparability graphs. We present a compiler algorithm that can find optimal or near-optimal colorings in stream IGs, thereby improving SRF utilization than the First-Fit

bin-packing algorithm, the best in the literature.
A comparison of programming models for multiprocessors with explicitly managed memory hierarchies
Authors: Schneider Scott , Yeom Jae-Seung , Rose Benjamin , Linford John C. , Sandu Adrian , Nikolopoulos Dimitrios S.
Published: August 2009

On multiprocessors with explicitly managed memory hierarchies (EMM), software has the responsibility of moving data in and out of fast local memories. This task can be complex and error-prone even for expert programmers. Before we can allow compilers to handle this complexity for us, we must identify the abstractions that are general enough to allow us to write applications with reasonable effort, yet specific enough to exploit the vast on-chip memory bandwidth of EMM multi-processors. To this end, we compare two programming models against hand-tuned codes on the STI Cell, paying attention to programmability and performance. The first programming model, Sequoia, abstracts the memory hierarchy as private address spaces, each corresponding to a parallel task. The second, Cellgen, is a new framework which provides OpenMP-like semantics and the abstraction of a shared address space divided into private and shared data. We compare three applications programmed using these models against their hand-optimized counterparts in terms of abstractions, programming complexity, and performance.
Committing conflicting transactions in an STM
Authors: Ramadan Hany E. , Roy Indrajit , Herlihy Maurice , Witchel Emmett
Published: August 2009

Dependence-aware transactional memory (DATM) is a recently proposed model for increasing concurrency of memory transactions without complicating their interface. DATM manages dependences between conflicting, uncommitted transactions so that they commit safely.

The contributions of this paper are twofold. First, we provide a safety proof for the dependence-aware model. This proof also shows that the DATM model accepts all concurrent interleavings that are conflict-serializable.

Second, we describe the first application of dependence tracking to software transactional memory (STM) design and implementation. We compare our implementation with a state of the art STM, TL2 [4]. We use benchmarks from the STAMP [21] suite, quantifying how dependence tracking converts certain types of transactional conflicts into successful commits. On high contention workloads, DATM is able to take advantage of dependences to speed up execution by up to 4.8x.
Detecting and tolerating asymmetric races
Authors: Ratanaworabhan Paruj , Burtscher Martin , Kirovski Darko , Zorn Benjamin , Nagpal Rahul , Pattabiraman Karthik
Published: August 2009

This paper introduces ToleRace, a runtime system that allows programs to detect and even tolerate asymmetric data races. Asymmetric races are race conditions where one thread correctly acquires and releases a lock for a shared variable while another thread improperly accesses the same variable. ToleRace provides approximate isolation in the critical sections of lock-based parallel programs by creating a local copy of each shared variable when entering a critical section, operating on the local copies, and propagating the appropriate copies upon leaving the critical section. We start by characterizing all possible interleavings that can cause races and precisely describe the effect of ToleRace in each case. Then, we study the theoretical aspects of an oracle that knows exactly what type of interleaving has occurred. Finally, we present two software implementations of ToleRace and evaluate them on multithreaded applications from the SPLASH2 and PARSEC suites. Our implementation on top of a dynamic instrumentation tool, which works directly on executables and requires no source code modifications, incurs an overhead of a factor of two on average. Manually adding ToleRace to the source code of these applications results in an average overhead of 6.4 percent.
Transactional memory with strong atomicity using off-the-shelf memory protection hardware
Authors: Abadi Martín , Harris Tim , Mehrara Mojtaba
Published: August 2009

This paper introduces a new way to provide strong atomicity in an implementation of transactional memory. Strong atomicity lets us offer clear semantics to programs, even if they access the same locations inside and outside transactions. It also avoids differences between hardware-implemented transactions and software-implemented ones. Our approach is to use off-the-shelf page-level memory protection hardware to detect conflicts between normal memory accesses and transactional ones. This page-level mechanism ensures correctness but gives poor performance because of the costs of manipulating memory protection settings and receiving notifications of access violations. However, in practice, we show how a combination of careful object placement and dynamic code update allows us to eliminate almost all of the protection changes. Existing implementations of strong atomicity in software rely on detecting conflicts by conservatively treating some non-transactional accesses as short transactions. In contrast, our page-level mechanism lets us be less conservative about how non-transactional accesses are treated; we avoid changes to non-transactional code until a possible conflict is detected dynamically, and we can respond to phase changes where a given instruction sometimes generates conflicts and sometimes does not. We evaluate our implementation with C# versions of many of the STAMP benchmarks, and show how it performs within 25% of an implementation with weak atomicity on all the benchmarks we have studied. It avoids pathological cases in which other implementations of strong atomicity perform poorly.
Industrial perspectives panel
Authors: Ranganathan Parthasarathy
Published: August 2009

This year, we have a different format for HPCA's industrial session. We will have an "industrial perspectives panel" with practitioners from industry presenting their perspectives on interesting future technical challenges and opportunities for research. We have panelists from IBM, Microsoft, NVIDIA, and Sun exploring a spectrum of interesting areas from consumer to enterprise markets including "hot" topics around multicores, graphics accelerators, and solid-state memory.
Compiler-assisted dynamic scheduling for effective parallelization of loop nests on multicore processors
Authors: Baskaran Muthu Manikandan , Vydyanathan Nagavijayalakshmi , Bondhugula Uday Kumar Reddy , Ramanujam J. , Rountev Atanas , Sadayappan P.
Published: August 2009

Recent advances in polyhedral compilation technology have made it feasible to automatically transform affine sequential loop nests for tiled parallel execution on multi-core processors. However, for multi-statement input programs with statements of different dimensionalities, such as Cholesky or LU decomposition, the parallel tiled code generated by existing automatic parallelization approaches may suffer from significant load imbalance, resulting in poor scalability on multi-core systems. In this paper, we develop a completely automatic parallelization approach for transforming input affine sequential codes into efficient parallel codes that can be executed on a multi-core system in a load-balanced manner. In our approach, we employ a compile-time technique that enables dynamic extraction of inter-tile dependences at run-time, and dynamic scheduling of the parallel tiles on the processor cores for improved scalable execution. Our approach obviates the need for programmer intervention and re-writing of existing algorithms for efficient parallel execution on multi-cores. We demonstrate the usefulness of our approach through comparisons using linear algebra computations: LU and Cholesky decomposition.
MPIWiz
Authors: Xue Ruini , Liu Xuezheng , Wu Ming , Guo Zhenyu , Chen Wenguang , Zheng Weimin , Zhang Zheng , Voelker Geoffrey
Published: August 2009

Message Passing Interface (MPI) is a widely used standard for managing coarse-grained concurrency on distributed computers. Debugging parallel MPI applications, however, has always been a particularly challenging task due to their high degree of concurrent execution and non-deterministic behavior. Deterministic replay is a potentially powerful technique for addressing these challenges, with existing MPI replay tools adopting either data-replay or order-replay approaches. Unfortunately, each approach has its tradeoffs. Data-replay generates substantial log sizes by recording every communication message. Order-replay generates small logs, but requires all processes to be replayed together. We believe that these drawbacks are the primary reasons that inhibit the wide adoption of deterministic replay as the critical enabler of cyclic debugging of MPI applications.

This paper describes
subgroup reproducible replay
(SRR), a hybrid deterministic replay method that provides the benefits of both data-replay and order-replay while balancing their trade-offs. SRR divides all processes into disjoint groups. It records the contents of messages crossing group boundaries as in data-replay, but records just message orderings for communication within a group as in order-replay. In this way, SRR can exploit the communication locality of traffic patterns in MPI applications. During replay, developers can then replay each group individually. SRR reduces recording overhead by not recording intra-group communication, and reduces replay overhead by limiting the size of each replay group. Exposing these tradeoffs gives the user the necessary control for making deterministic replay practical for MPI applications.

We have implemented a prototype, MPIWiz, to demonstrate and evaluate SRR. MPIWiz employs a replay framework that allows transparent binary instrumentation of both library and system calls. As a result, MPIWiz replays MPI applications with no source code modification and relinking, and handles non-determinism in both MPI and OS system calls. Our preliminary results show that MPIWiz can reduce recording overhead by over a factor of four relative to data-replay, yet without requiring the entire application to be replayed as in order-replay. Recording increases execution time by 27% while the application can be replayed in just 53% of its base execution time.
Formal verification of practical MPI programs
Authors: Vo Anh , Vakkalanka Sarvani , DeLisi Michael , Gopalakrishnan Ganesh , Kirby Robert M. , Thakur Rajeev
Published: August 2009

This paper considers the problem of formal verification of MPI programs operating under a fixed test harness for safety properties without building verification models. In our approach, we directly model-check the MPI/C source code, executing its interleavings with the help of a verification scheduler. Unfortunately, the total feasible number of interleavings is exponential, and impractical to examine even for our modest goals. Our earlier publications formalized and implemented a partial order reduction approach that avoided exploring equivalent interleavings, and presented a verification tool called ISP. This paper presents algorithmic and engineering innovations to ISP, including the use of OpenMP parallelization, that now enables it to handle practical MPI programs, including:(i)~ParMETIS - a widely used hypergraph partitioner, and (ii)~MADRE - a Memory Aware Data Re-distribution Engine, both developed outside our group. Over these benchmarks, ISP has automatically verified up to 14K lines of MPI/C code, producing error traces of deadlocks and assertion violations within seconds.
Exploiting global optimizations for openmp programs in the openuh compiler
Authors: Huang Lei , Eachempati Deepak , Hervey Marcus W. , Chapman Barbara
Published: August 2009

The advent of new parallel architectures has increased the need for parallel optimizing compilers to assist developers in creating efficient code. OpenUH is a state-of-the-art optimizing compiler, but it only performs a limited set of optimizations for OpenMP programs due to its conservative assumptions of shared memory programming. These limitations may prevent some OpenMP applications from being fully optimized to the extent of its sequential counterpart. This paper describes our design and implementation of a parallel data flow framework, consisting of a Parallel Control Flow Graph (PCFG) and a Parallel SSA (PSSA) representation in OpenUH, to model data flow for OpenMP programs. This framework enables the OpenUH compiler to perform all classical scalar optimizations for OpenMP programs, in addition to conducting OpenMP specific optimizations.
NePalTM
Authors: Volos Haris , Welc Adam , Adl-Tabatabai Ali-Reza , Shpeisman Tatiana , Tian Xinmin , Narayanaswamy Ravi
Published: August 2009

We present the programming model, design and implementation of NePalTM; a transactional memory system where atomic blocks can be used for concurrency control at an arbitrary level of nested parallelism.
Parallelization spectroscopy
Authors: Kejariwal Arun , Casçaval Calin
Published: August 2009

In this paper, we present a method - parallelization spectroscopy - for analyzing the thread-level parallelism available in production High Performance Computing (HPC) codes.We survey a number of techniques that are commonly used for parallelization and classify all the loops in the case study presented using a sensitivity metric: how likely is a particular technique is successful in parallelizing the loop.
Preliminary results on nb-feb, a synchronization primitive for parallel programming
Authors: Ha Phuong Hoai , Tsigas Philippas , Anshus Otto J.
Published: August 2009

We introduce a
non-blocking
full/empty bit primitive, or NB-FEB for short, as a promising synchronization primitive for parallel programming on may-core architectures. We show that the NB-FEB primitive is
universal, scalable
and
feasible
. NB-FEB, together with registers, can solve the consensus problem for an arbitrary number of processes (
universality
). NB-FEB is
combinable
, namely its memory requests to the same memory location can be combined into only one memory request, which consequently mitigates performance degradation due to synchronization "hot spots" (
scalability
). Since NB-FEB is a variant of the original full/empty bit that always returns a value instead of waiting for a conditional flag, it is as feasible as the original full/empty bit, which has been implemented in many computer systems (
feasibility
).
Software transactional distributed shared memory
Authors: Dash Alokika , Demsky Brian
Published: August 2009

We have developed a transaction-based approach to distributed shared memory(DSM) that supports object caching and generates path expression prefetches. A path expression specifies a path through the heap that traverses the objects to be prefetched. To our knowledge, this is the first prefetching approach that can prefetch objects whose addresses have not been computed or predicted. Our DSM uses both prefetching and caching of remote objects to hide network latency while relying on the two-phase transaction commit mechanism to preserve the simple transactional consistency model that we present to the developer. We have evaluated this approach on a matrix multiply benchmark. We have found that our approach enables to effectively utilize multiple machines in a cluster and also benefit from prefetching and caching of objects.
Stack-based parallel recursion on graphics processors
Authors: Yang Ke , He Bingsheng , Luo Qiong , Sander Pedro V. , Shi Jiaoying
Published: August 2009

Recent research has shown promising results on using graphics processing units (GPUs) to accelerate general-purpose computation. However, today's GPUs do not support recursive functions. As a result, for inherently recursive algorithms such as tree traversal, GPU programmers need to explicitly use stacks to emulate the recursion. Parallelizing such stack-based implementation on the GPU increases the programming difficulty; moreover, it is unclear how to improve the efficiency of such parallel implementations. As a first step to address both ease of programming and efficiency issues, we propose three parallel stack implementation alternatives that differ in the granularity of stack sharing. Taking tree traversals as an example, we study the performance tradeoffs between these alternatives and analyze their behaviors in various situations. Our results could be useful to both GPU programmers and GPU compiler writers.
Topology aware task mapping techniques
Authors: Bhatelé Abhinav , Bohm Eric , Kalé Laxmikant V.
Published: August 2009

Optimal network performance is critical to efficient parallel scaling for communication-bound applications on large machines. With wormhole routing,
no-load
latencies do not increase significantly with number of hops traveled. Yet, we, and others have recently shown that in presence of
contention
, message latencies can grow substantially large. Hence task mapping strategies should take the topology of the machine into account on large machines. This poster presents a uniform API which provides topology information on 3D tori like IBM Blue Gene and Cray XT machines. We present techniques to use this API to improve performance. The API can be used by user-level codes to obtain information about allocated partitions at runtime which is essential for mapping.

We motivate why it is important to consider network topology, using a simple 3D Stencil kernel. We then present mapping strategies for a production code, OpenAtom, running on three-dimensional torus and mesh topologies. OpenAtom presents complex communication scenarios of interaction between multiple groups of objects. Results are presented in the context of 3D Stencil and OpenAtom on up to 16,384 processors of Blue Gene/L, 8,192 processors of Blue Gene/P and 2,048 processors of Cray XT3.
Towards concurrency refactoring for x10
Authors: Markstrum Shane A. , Fuhrer Robert M. , Millstein Todd D.
Published: August 2009

In this poster, we present our vision of refactoring support for languages with a partitioned global address space memory model as embodied in the X10 programming language. We examine a novel refactoring, extract concurrent, that introduces additional concurrency within a loop by arranging for some user-selected code in the loop body to run in parallel with other iterations of the loop. We discuss the mechanisms and challenges for implementing this refactoring and how development of this refactoring provides insight for designing future refactorings.
How the Fanconi Anemia Pathway Guards the Genome
Authors: Moldovan George-Lucian , D'Andrea Alan D.
Published: August 2009

Fanconi Anemia (FA) is an inherited genomic instability disorder, caused by mutations in genes regulating replication-dependent removal of interstrand DNA crosslinks. The Fanconi Anemia pathway is thought to coordinate a complex mechanism that enlists elements of three classic DNA repair pathways, namely homologous recombination, nucleotide excision repair, and mutagenic translesion synthesis, in response to genotoxic insults. To this end, the Fanconi Anemia pathway employs a unique nuclear protein complex that ubiquitinates FANCD2 and FANCI, leading to formation of DNA repair structures. Lack of obvious enzymatic activities among most FA members has made it challenging to unravel its precise modus operandi. Here we review the current understanding of how the Fanconi Anemia pathway components participate in DNA repair and discuss the mechanisms that regulate this pathway to ensure timely, efficient, and correct restoration of chromosomal integrity.
Bacterial Quorum-Sensing Network Architectures
Authors: Ng Wai-Leung , Bassler Bonnie L.
Published: August 2009

Quorum sensing is a cell-cell communication process in which bacteria use the production and detection of extracellular chemicals called autoinducers to monitor cell population density. Quorum sensing allows bacteria to synchronize the gene expression of the group, and thus act in unison. Here, we review the mechanisms involved in quorum sensing with a focus on the Vibrio harveyi and Vibrio cholerae quorum-sensing systems. We discuss the differences between these two quorum-sensing systems and the differences between them and other paradigmatic bacterial signal transduction systems. We argue that the Vibrio quorum-sensing systems are optimally designed to precisely translate extracellular autoinducer information into internal changes in gene expression. We describe how studies of the V. harveyi and V. cholerae quorum-sensing systems have revealed some of the fundamental mechanisms underpinning the evolution of collective behaviors.
Gene Amplification and Adaptive Evolution in Bacteria
Authors: Andersson Dan I. , Hughes Diarmaid
Published: August 2009

Gene duplication-amplification (GDA) processes are highly relevant biologically because they generate extensive and reversible genetic variation on which adaptive evolution can act. Whenever cellular growth is restricted, escape from these growth restrictions often occurs by GDA events that resolve the selective problem. In addition, GDA may facilitate subsequent genetic change by allowing a population to grow and increase in number, thereby increasing the probability for subsequent adaptive mutations to occur in the amplified genes or in unrelated genes. Mathematical modeling of the effect of GDA on the rate of adaptive evolution shows that GDA will facilitate adaptation, especially when the supply of mutations in the population is rate-limiting. GDA can form via several mechanisms, both RecA-dependent and RecA-independent, including rolling-circle amplification and nonequal crossing over between sister chromatids. Due to the high intrinsic instability and fitness costs associated with GDAs, they are generally transient in nature, and consequently their evolutionary and medical importance is often underestimated.
Nucleomorph Genomes
Authors: Moore Christa E. , Archibald John M.
Published: August 2009

Nucleomorphs are the remnant nuclei of algal endosymbionts in cryptophytes and chlorarachniophytes, two evolutionarily distinct unicellular eukaryotic lineages that acquired photosynthesis secondarily by the engulfment of red and green algae, respectively. At less than one million base pairs in size, nucleomorph genomes are the most highly reduced nuclear genomes known, with three small linear chromosomes and a gene density similar to that seen in prokaryotes. The independent origin of nucleomorphs in cryptophytes and chlorarachniophytes presents an interesting opportunity to study the reductive evolutionary forces that have led to their remarkable convergence upon similar genome architectures and coding capacities. In this article, we review the current state of knowledge with respect to the structure, function, origin, and evolution of nucleomorph genomes across the known diversity of cryptophyte and chlorarachniophyte algae.
Sufficient Statistics for Welfare Analysis: A Bridge Between Structural and Reduced-Form Methods
Authors: Chetty Raj
Published: August 2009

The debate between structural and reduced-form approaches has generated substantial controversy in applied economics. This article reviews a recent literature in public economics that combines the advantages of reduced-form strategies—transparent and credible identification—with an important advantage of structural models—the ability to make predictions about counterfactual outcomes and welfare. This literature has developed formulas for the welfare consequences of various policies that are functions of reduced-form elasticities rather than structural primitives. I present a general framework that shows how many policy questions can be answered by estimating a small set of sufficient statistics using program-evaluation methods. I use this framework to synthesize the modern literature on taxation, social insurance, and behavioral welfare economics. Finally, I discuss problems in macroeconomics, labor, development, and industrial organization that could be tackled using the sufficient statistic approach.
Power Laws in Economics and Finance
Authors: Gabaix Xavier
Published: August 2009

A power law (PL) is the form taken by a large number of surprising empirical regularities in economics and finance. This review surveys well-documented empirical PLs regarding income and wealth, the size of cities and firms, stock market returns, trading volume, international trade, and executive pay. It reviews detail-independent theoretical motivations that make sharp predictions concerning the existence and coefficients of PLs, without requiring delicate tuning of model parameters. These theoretical mechanisms include random growth, optimization, and the economics of superstars, coupled with extreme value theory. Some empirical regularities currently lack an appropriate explanation. This article highlights these open areas for future research.
Stress Cardiomyopathy
Authors: Akashi Yoshihiro J. , Nef Holger M. , Möllmann Helge , Ueyama Takashi
Published: August 2009

Recently, an increasing number of cases of stress cardiomyopathy, mainly occurring in elderly women, have been documented in many parts of the world. In Japan, this disease is known as takotsubo cardiomyopathy (named after the fishing pot used for trapping octopus). Symptoms of this condition are akin to those of acute myocardial infarction, but no obstructive lesions are found in the coronary arteries, and left ventricular apical ballooning is present. Stress cardiomyopathy is now a well-recognized cause of acute heart failure, lethal ventricular arrhythmias, and ventricular rupture. Although the precise mechanism of onset of this condition is still controversial, two major pathogenic mechanisms have been proposed: catecholamine cardiotoxicity and neurogenic stunned myocardium. We summarize the findings of studies conducted to date on stress cardiomyopathy—from bench to bedside and bedside to bench.
Pharmacogenetics of Warfarin
Authors: Kamali Farhad , Wynne Hilary
Published: August 2009

Warfarin is a drug with a narrow therapeutic index and a wide interindividual variability in dose requirement. Because it is difficult to predict an accurate dose for an individual, patients starting the drug are at risk of thromboembolism or bleeding associated with underdosing or overdosing, respectively. Single nucleotide polymorphisms in the cytochrome P450 2C9 (CYP2C9) and vitamin K epoxide reductase (VKOR) genes have been shown to have a significant effect on warfarin dose requirement. Other genes mediating the action of warfarin make either little or no contribution to dose requirement. Although the polymorphisms in CYP2C9 and VKORC1 explain a significant proportion of the interindividual variability in warfarin dose requirement, currently available evidence based on a few small studies relating to the use of pharmacogenetics-guided dosing in the initiation of warfarin therapy has not shown improved outcomes in either safety or efficacy of therapy. Better clinical evidence of beneficial effects on patient outcome, particularly at the extremes of the dose requirements in geographically and ethnically diverse patient populations, is needed before the role of a pharmacogenomic approach to oral anticoagulation therapy in clinical practice can be established.
Batch Scheduling on Two-Machine Flowshop with Machine-Dependent Setup Times
Authors: Ben-Dati Lika , Mosheiov Gur , Oron Daniel
Published: August 2009

We study a batch scheduling problem on a 2-machine flowshop. We assume unit processing time jobs, batch availability, and machine-dependent setup times. The objective is to find a job allocation to batches of integer size and a batch schedule that minimize makespan. We introduce a very efficient closed form solution for the problem.
Are Soil Pollution Risks Established by Governments the Same as Actual Risks?
Authors: Reijnders L.
Published: August 2009

Though soil pollution policies in North America and the European Union increasingly use risk-based standards, the construction and application of such standards are often deficient in taking account of actual risks. Standards refer to total concentrations of substances and not to the biologically available amount. A number of countries neglect “background” exposure, and assumptions regarding routes of exposure to soil pollution can be very different and at variance with empirical data. Recent dose-effect studies are neglected in a number of cases. The application of standards does not take account of the overall risk of soil pollution but rather leads to the decision whether or not there is violation of at least one standard for a specified (group of) substance(s). Standards for soil pollutants are often based on the assumption that only effect addition can occur, whereas dose addition, antagonism and synergism, and indirect effects may in fact apply. Several remedies for current shortcomings are proposed.
New Spectrophotometric and Fluorimetric Methods for Determination of Fluoxetine in Pharmaceutical Formulations
Authors: Darwish Ibrahim A. , Amer Sawsan M. , Abdine Heba H. , Al-Rayes Lama I.
Published: August 2009

New simple and sensitive spectrophotometric and fluorimetric
methods have been developed and validated for the determination of
fluoxetine hydrochloride (FLX) in its pharmaceutical formulations.
The spectrophotometric method was based on the reaction of FLX
with 1,2‐naphthoquinone‐4‐sulphonate (NQS) in an alkaline medium
(pH 11) to form an orange‐colored product that was measured at 490
nm. The fluorimetric method was based on the reaction of FLX with
4‐chloro‐7‐nitrobenzo‐2‐oxa‐1,3‐diazole (NBD‐Cl) in an alkaline
medium (pH 8) to form a highly fluorescent product that was
measured at 545 nm after excitation at 490 nm. The variables
affecting the reactions of FLX with both NQS and NBD‐Cl were
carefully studied and optimized. The kinetics of the reactions
were investigated, and the reaction mechanisms were presented.
Under the optimum reaction conditions, good linear relationships
were found between the readings and the concentrations of FLX in
the ranges of 0.3–6 and 0.035–0.5 μg mL−1 for the
spectrophotometric and fluorimetric methods, respectively. The
limits of detection were 0.1 and 0.01 μg mL−1 for the
spectrophotometric and fluorimetric methods, respectively. Both
methods were successfully applied to the determination of FLX in
its pharmaceutical formulations.
Recurrent Bacteremia, a Complication of Cyanoacrylate Injection for Variceal Bleeding: Report of Two Cases and Review of the Literature
Authors: Galperine T. , Flateau C. , Venon M. D. , Lescure F. X. , Béraud G. , Said Ibrahim T. , Delisle F. , Durand F. , Faure K. , Pialoux G. , Guery B.
Published: August 2009

We report the first description of recurrent bacteremia in two patients after cyanoacrylate injection for gastric varices bleeding treated with antibiotics alone. Adapted and prolonged antibiotic treatment allowed a complete resolution of the infection with no relapse after more than 6 months. According to recent data, prophylactic antibiotics should be further investigated for patients with bleeding varices undergoing cyanoacrylate injection.