bluuebunny/crossref_metadata_2025 huggingface dataset:
Understory patch dynamics and ungulate herbivory in old-growth forests of Olympic National Park, Washington
Authors: Schreiner Edward G. , Krueger Kirsten A. , Houston Douglas B. , Happe Patricia J.
Published: June 2008

The relationship between native ungulates (mainly Roosevelt elk, Cervuselaphus L.) and the occurrence of three patch types in an old-growth (220- to 260-year-old) Sitka spruce (Piceasitchensis (Bong.) Carrière)–western hemlock (Tsugaheterophylla (Raf.) Sarg.) temperate coniferous rain forest was investigated on the South Fork Hoh River in Olympic National Park. The distribution, frequency, and size of two understory patches (grass, moss) and patches where shrubs had escaped herbivory (refugia) were sampled along transects. Vegetation standing crop, percent cover, species richness, and equitability along transects were compared with conditions in two 8-year-old 0.5-ha ungulate exclosures. Ungulate herbivory profoundly affected the distribution and abundance of understory patch types. Grass-dominated patches disappeared following 8 years of protection from ungulate herbivory. Ungulates maintained a reduced standing crop, increased forb species richness, and determined the distribution, morphology, and reproductive performance of several shrub species. There is clearly a dynamic relationship between patch type, tree fall, and ungulate herbivory in these old-growth forests. Our results show that ungulate herbivory is a driving force shaping vegetation patterns in coastal coniferous forests.
Seed release from black spruce cones in logging slash
Authors: Fleming R.L. , Mossa D.S.
Published: June 2008

Seed release from black spruce (Piceamariana (Mill.) BSP) cones on two clearcut sites in northwestern Ontario was evaluated over a 5-year period. Newly ripened cones were set out at seven locations on or above upland raw humus, upland mineral soil, and lowland raw humus substrates, and periodically sampled to determine the number of seeds remaining, and their germinability. Cones elevated above the substrates released 45–55% of their seeds within 1 year, and 65–75% of their seeds within 2 years. Seed release was largely confined to the growing season. Filled seeds were released more rapidly than empty seeds, and germination percent of the remaining filled seeds declined with time. Cones lying on or just above the substrates released about 25% of their seeds within 2 years, but the proportion of seeds remaining that were filled, and their germination percent, declined more rapidly with time than for elevated cones. Seed release occurred most rapidly from cones associated with upland raw humus substrates. Estimated viable seed release from cones elevated above the substrates was two to three times greater than that from cones lying on the substrates. Depending on cone location, 65–90% of all viable seed released was released within the first year after harvesting. This seed source should be considered when designing silvicultural regeneration systems for black spruce.
Influence of crown class on survival and development of Betulalenta in Connecticut, U.S.A.
Authors: Ward Jeffrey S. , Stephens George R.
Published: June 2008

Crown class, diameter, and sprout rank of 2219 black birch (Betulalenta L.) >1.5 cm have been monitored at 10-year intervals since 1927. Survival and development of black birch in 25- to 85-year-old stands was influenced by antecedent crown class, sprout rank, and disturbance. Mortality was typically higher for trees in the lower than upper crown classes. Black birch demonstrated high flux among crown classes. Persistence in the upper canopy was 70 years for dominant trees and only 20 years for codominant trees. Trees in lower crown classes generally ascended into higher crown classes at a faster rate than did trees in higher crown classes. Survival in stands from ages 25 through 55 years was higher for the largest stem in a sprout clump than for lesser sprouts and trees that had never been part of a sprout clump. Survival was independent of diameter class when crown-class effects were removed. Immediate response of black birch to a period of upper canopy disturbance caused by drought and severe defoliation included temporary decreases of crown-class regression and mortality rates, and a concomitant temporary increase of crown-class persistence rates. Crown-class ascension rates increased after a 10-year lag for codominant and intermediate trees, and a 20-year lag for suppressed trees. Black birch ingrowth also responded positively to upper canopy disturbance. The increased use of partial cutting, i.e., anthropogenic upper canopy disturbance, in the northeastern United States is creating conditions advantageous for black birch development.
Age structure and response to fine-scale disturbances of Abiessachalinensis, Piceajezoensis, Piceaglehnii, and Betulaermanii growing under the influence of a dwarf bamboo understory in northern Japan
Authors: Hiura Tsutom , Sano Junji , Konno Yasuo
Published: June 2008

We studied regeneration patterns of the four canopy dominants, Abiessachalinensis (Fr. Schm.) Masters, Piceajezoensis (Sieb. et Zucc.) Cam, Piceaglehnii (Fr. Schm.) Masters, and Betulaermanii Cham., of an old-growth (>400 years) boreal coniferous forest in northern Japan. Age and size structure, height growth, and diameter growth of tree populations in a 40 × 40 m plot were analyzed. Seedling establishment was restricted to nurse logs and mounds (98%), where the influence of dwarf bamboo (Sasasenanensis (Franch. et Sav.) Rehd.) was limited. Abiessachalinensis had a high density (10 263/ha) but a high mortality (8.4%/year for saplings, 1.7%/year for canopy trees) and a short canopy residence time. It also showed a more rapid tree-ring width increase after disturbances. Piceaglehnii had a low density (1450/ha) but a low mortality (6.9%/year for saplings, 0.1%/year for canopy trees) and a longer residence time in the canopy. Piceajezoensis had an intermediate density (8206/ha) and its mortality rate for canopy trees (0.9%/year) was lower than that of A. sachalinensis, although its sapling mortality rate (8.1%/year) was similar to that of A. sachalinensis. Betulaermanii had a higher mortality (14.1%/year for saplings, 2.4%/year for canopy trees) than the conifers. On the other hand, B. ermanii had the highest height growth and P. glehnii had the lowest. The mortality and average height growth of saplings showed a trade-off relationship. The trade-off relation in life history strategy may contribute to the coexistence of these species. The proportion of the gap area created in the forest was 1.2–2.4%/year, and a forest turnover time calculated from aboveground volumes was 87–99 years. These values were similar to a weighted mean of the estimated life times of the constituent species, 71 years for A. sachalinensis, 123 years for P. jezoensis, and 49 years for B. ermanii.
Using spatial and temporal patterns of Armillaria root disease to formulate management recommendations for Ontario's black spruce (Piceamariana) seed orchards
Authors: Bruhn J.N. , Mihail J.D. , Meyer T.R.
Published: June 2008

Between 1982 and 1989, 22 black spruce (Piceamariana (Mill.) BSP) seed orchards were established on cleared jack pine (Pinusbanksiana Lamb.) forest land in northwest Ontario. These orchards were located on stressful sites for black spruce to hasten seed production. Mortality caused by Armillariaostoyae (Romagn.) Herink was observed in most of these orchards within 3 years of establishment. This study was initiated to quantitatively describe the temporal progress and spatial patterns of Armillaria root disease mortality in five representative orchards, to determine future operational management implications. In the four orchards where epidemics developed, temporal disease progress was nonlinear and was better described by the monomolecular function than by the Gompertz or logistic functions. Monomolecular rates of disease increase were 0.0062–0.0346. Applying these rates, we estimated that cumulative Armillaria root disease mortality will be 9–41% and 25–79%, at 20 and 50 years after planting, respectively. Armillaria root disease mortality was spatially aggregated in all four orchards. Trees adjacent to Armillaria-killed trees had an increased probability of mortality from Armillaria root disease. Successive epidemics may develop in these orchards; their timing and severity will be affected by orchard management practices. Measures of spruce family performance in these orchards are compromised by the aggregated distributions of different A. ostoyae genets and the root disease they cause.
The effects of overstory shading on white pine weevil damage to white spruce and its effects on spruce growth rates
Authors: Taylor S.P. , Delong C. , Alfaro R.I. , Rankin L.
Published: June 2008

A retrospective study was conducted in 1993 that quantified the effects of overstory shading on both spruce weevil (Pissodesstrobi (Peck)) and leader growth on white spruce (Piceaglauca (Moench) Voss × Piceaengelmannii Parry ex Engelm.). The study was undertaken in the interior of British Columbia, where the weevil is causing extensive damage to plantations of white spruce. Shading on the spruce trees was measured by calculating the light interception index and percent overstory cover on individual white spruce trees at the centre of a 2.52 m radius plot. Current weevil attacks decreased significantly with increasing overstory cover, and the rate of decrease was greater in heavily versus lightly attacked stands. Shading also decreased leader growth. These results indicate that the optimum level of overstory removal may be a compromise between volume loss due to overstory competition and volume gain due to decreased weevil attacks.
Effect of understory competition on distribution and recovery of 15N applied to a western red cedar–western hemlock clear-cut site
Authors: Chang Scott X. , Weetman Gordon F. , Preston Caroline M. , McCullough Kevin , Barker John
Published: June 2008

Fertilizer labeled with 15N was used to study the fate of N in forest soil–plant systems with (control) and without competition (treated) from an ericaceous evergreen shrub, salal (Gaultheriashallon Pursh), on a western red cedar (Thujaplicata Donn ex D. Don)–western hemlock (Tsugaheterophylla (Raf.) Sarg.) clear-cut site on northern Vancouver Island. Fertilizer was applied in April 1991 at 200 kg N•ha−1 as (NH4)2SO4 (3.38044% 15N enrichment) to single-tree plots of 1 m radius. Four-year-old western red cedar, western hemlock, and Sitka spruce (Piceasitchensis (Bong.) Carrière) were used and the plots were destructively sampled after two growing seasons (October 1992). The distribution of 15N within trees was virtually unaffected by the treatment but displayed differences among species. The majority of the 15N in a tree was found in the current-year needles. Because of the dilution effect, 15N abundances in the above ground tree components were not different between treatments but 15N contents were significantly increased by salal removal. The pattern of and treatment effect on total N distribution were similar to those of 15N. Total recovery by trees of applied 15N was 7.7, 17.8, and 10.3% in the treated plots planted with cedar, hemlock, and spruce, respectively. The corresponding values for the control plots were 4.1, 2.0, and 4.9%. Understory in the control plots immobilized 14.8, 24.6, and 13.5% of the applied N for plots planted with the respective species. Total recoveries in soil and vegetation ranged from 57 to 87%, of which 59 to 82% was recovered in the soil compartments. Results clearly showed that trees competed poorly with the understory vegetation for the applied fertilizer N.
Effects of Phellinusweirii gaps on early successional vegetation following timber harvest
Authors: Ingersoll C.A. , Wilson M.V. , Thies W.G.
Published: June 2008

A 65-year-old stand in northwestern Washington dominated by Pseudotsugamenziesii (Mirb.) Franco was harvested by clear-cutting in 1987. Before harvest, canopy gaps caused by the root-disease fungus Phellinusweirii (Murr.) Gilbn. covered about 22% of stand area. Five years after harvest, overall plant species composition of former gaps differed significantly from adjacent areas of previously intact forest. Forbs and trees were more abundant, and ferns less abundant, in areas of previously intact forest than in former gaps. In contrast, total cover, species diversity, and the abundance of plant species groups (defined by distributional and life history characteristics) did not differ significantly between areas of previously intact forest and former gaps. Plant species responded individualistically to timber harvesting in gaps and intact forest. These results show that development of root-disease gaps may influence understory patterns during early succession following harvest.
An individual-tree basal area growth model for loblolly pine stands
Authors: Murphy Paul A. , Shelton Michael G.
Published: June 2008

Tree basal area growth has been modeled as a combination of a potential growth function and a modifier function, in which the potential function is fitted separately from open-grown tree data or a subset of the data and the modifier function includes stand and site variables. We propose a modification of this by simultaneously fitting both a growth component and a modifier component. The growth component can be any function that approximates tree growth patterns, and the logistic function is chosen as the modifier component. This approach can be adapted to a variety of stand conditions, and its application is demonstrated using data from an uneven-aged loblolly pine (Pinustaeda L.) study located in Arkansas and Louisiana.
COLLAPSING FLUID WITH SELF-SIMILARITY OF THE SECOND KIND IN 2 + 1 GRAVITY
Authors: MARTINS M. R. , DA SILVA M. F. A. , WU YUMEI
Published: June 2008

Anisotropic fluid with self-similarity of the second kind in (2 + 1)-dimensional space–times with circular symmetry is studied. By imposing the condition that the radial pressure vanishes, we show that the only allowed solutions are the ones that represent dust fluid. All such solutions to the Einstein field equations are found and their local and global properties are studied in detail. It is found that some can be interpreted as representing gravitational collapse, in which both naked singularities and black holes can be formed.
COSMIC EVOLUTION WITH EARLY AND LATE ACCELERATION INSPIRED BY THE DUAL NATURE OF THE RICCI SCALAR CURVATURE
Authors: SRIVASTAVA S. K.
Published: June 2008

In the present paper, a cosmological scenario is proposed in which dark energy emerges spontaneously from modified gravity. In this scenario, the universe inflates for ~10-37s in the beginning and the late universe accelerates after 8.58 Gyrs. During the long intermediate period, the universe decelerates driven by radiation and subsequently by matter. The gravitational dark energy that emerges in this model mimics quintessence and its density falls by 115 orders from 2.18 × 1068GeV4initially to its current value 2.19 × 10-47GeV4.
THE GRAVITY OF QUANTUM PRESSURE — A NEW TEST OF GENERAL RELATIVITY
Authors: UNNIKRISHNAN C. S. , GILLIES G. T.
Published: June 2008

Matter confined to a small volume generates quantum pressure and this pressure acts as a source of gravity according to general relativity, in which mass, energy, stress and pressure are all sources of gravity. Quantum Fermi pressure in nuclei and degeneracy pressure in stars should measureably alter space–time, and thus provide a new test of classical general relativity in which relativistic quantum effects on matter manifest as a modification of the Newtonian gravitational field of a source mass. But the situation is subtle owing to the gravity with opposite sign from the surface tension at boundaries confining such quantum matter. We discuss the general scenario, the first quantitative empirical investigation and a successful high precision test of the equality of the active and passive gravitational masses corresponding to the quantum pressure.
LOW-ENERGY SECTOR OF EIGHT-DIMENSIONAL GENERAL RELATIVITY: ELECTROWEAK MODEL AND NEUTRINO MASS
Authors: CIANFRANI FRANCESCO , MONTANI GIOVANNI
Published: June 2008

We demonstrate that in a Kaluza–Klein space–time V4 ⊗ S1 ⊗ S3, the dimensional reduction of spinors provides a 4-field, whose associated SU(2) gauge connections are geometrized. However, additional and gauge-violating terms arise, but they are highly suppressed by a factor β, which fixes the amount of the spinor dependence on extra-coordinates. The application of this framework to the Electroweak Model is performed, thus giving a lower bound for β due to electric charge conservation. We emphasize that the Higgs sector can be reproduced also, but neutrino masses are predicted and the fine-tuning on the Higgs parameters can additionally be explained.
ACCRETION ONTO COMPACT OBJECTS VIEWED AS A FLOW IN CONVERGING-DIVERGING DUCTS
Authors: CHAKRABARTI K. , MAJUMDAR M. M. , CHAKRABARTI SANDIP K.
Published: June 2008

Black hole accretion is necessarily transonic and the number of physical sonic points depends on the angular momentum of the flow. We study the properties of such a flow by recasting this idea into an engineering problem in which a flow has a subsonic to supersonic transition when it passes through a de Laval nozzle, i.e. a converging and diverging duct in a flat geometry in the presence of sufficient end pressure difference. Particularly interesting is the case of the centrifugal pressure supported standing shock formation inside an accretion flow, because the flow passes through at least two saddle type sonic points, one before and one after the shock. In this case, the duct itself has two minima and a maximum. We study the properties of such a duct as a function of the inflow parameters and classify all possible types of the flow through this composite nozzle.
PERSPECTIVES ON MEASURING THE PPN PARAMETERS β AND γ IN EARTH'S GRAVITATIONAL FIELD TO HIGH ACCURACY WITH CHAMP/GRACE MODELS
Authors: IORIO LORENZO
Published: June 2008

The current bounds on the PPN parameters β and γ are on the order of 10-4–10-5. Many missions aimed at improving such limits by several orders of magnitude have been proposed, including LATOR, ASTROD, BepiColombo and GAIA. They involve the use of various spacecraft, to be launched along interplanetary trajectories, for measuring the post-Newtonian effects induced by solar gravity on the propagation of electromagnetic waves. In this paper, we investigate the requirements needed to measure the combination ν = (2 + 2γ - β)/3 entering the post-Newtonian Einstein pericenter precession [Formula: see text] of a test particle to an accuracy on the order of ~10-5 with a pair of drag-free spacecraft in Earth's gravitational field. It turns out that the latest gravity models from the dedicated CHAMP and GRACE missions would allow the reduction of the systematic errors of gravitational origin to just this demanding level of accuracy. With regard to the non-gravitational errors, the spectral noise density of the required drag-free sensors amounts to 10-8–10-9 cm s-2 Hz-½ over very low frequencies. Although not yet attainable with present technologies, such a level of compensation is much less demanding than those required for LISA, for instance. As a by-product, an independent measurement of the post-Newtonian gravitomagnetic Lense–Thirring effect with a ~1% accuracy will be possible as well. The forthcoming Earth gravity models from CHAMP and GRACE will further reduce the systematic bias of gravitational origin in both such tests.
A NEW VIEW OF THE SUN FROM THE HINODE SPACE MISSION
Authors: HARRA LOUISE K.
Published: June 2008

The Japanese/US/UK space mission, Hinode, was launched successfully in September 2006. Now, more than a year after the commissioning of the spacecraft and instruments, Hinode is unveiling a new view of the Sun. Hinode's goal is to help us to understand solar activity, and to link activity on (and below) the surface to the outer corona. This review will describe how the initial results are overturning our understanding of the Sun and will look to the future to anticipate what further discoveries might be made. In particular I will describe the areas of basic magnetohydrodynamic (MHD) processes such as magnetic reconnection and Alfvén waves, the formation of both the fast and slow solar winds and the triggering of flares and coronal mass ejections.
HYBRID STARS WITH DELTA MATTER AND COLOR–FLAVOR LOCKED QUARK PHASE
Authors: RODRIGUES H. , OLIVEIRA J. C. T. , DUARTE S. B.
Published: June 2008

The color–flavor locked (CFL) phase is believed to be the fundamental state of strange quark matter (SQM) at high densities. The CFL phase is a color superconductor composed of pairs of u, d and s quarks, with no electrons, forming a Bose condensate. In this work, we analyze a possible phase transition of hadronic matter made of nucleons, Δ–resonances, hyperons and leptons, to CFL superconducting quark matter. An equation of state taking into account this phase transition is employed to determine the characteristics of a hybrid star. The role of the color superconducting gap on the hybrid stars properties is also discussed.
Bigtable
Authors: Chang Fay , Dean Jeffrey , Ghemawat Sanjay , Hsieh Wilson C. , Wallach Deborah A. , Burrows Mike , Chandra Tushar , Fikes Andrew , Gruber Robert E.
Published: June 2008

Bigtable is a distributed storage system for managing structured data that is designed to scale to a very large size: petabytes of data across thousands of commodity servers. Many projects at Google store data in Bigtable, including web indexing, Google Earth, and Google Finance. These applications place very different demands on Bigtable, both in terms of data size (from URLs to web pages to satellite imagery) and latency requirements (from backend bulk processing to real-time data serving). Despite these varied demands, Bigtable has successfully provided a flexible, high-performance solution for all of these Google products. In this article, we describe the simple data model provided by Bigtable, which gives clients dynamic control over data layout and format, and we describe the design and implementation of Bigtable.
RaWMS - Random Walk Based Lightweight Membership Service for Wireless Ad Hoc Networks
Authors: Bar-Yossef Ziv , Friedman Roy , Kliot Gabriel
Published: June 2008

This article presents RaWMS, a novel lightweight random membership service for ad hoc networks. The service provides each node with a partial uniformly chosen view of network nodes. Such a membership service is useful, for example, in data dissemination algorithms, lookup and discovery services, peer sampling services, and complete membership construction. The design of RaWMS is based on a novel reverse random walk (RW) sampling technique. The article includes a formal analysis of both the reverse RW sampling technique and RaWMS and verifies it through a detailed simulation study. In addition, RaWMS is compared both analytically and by simulations with a number of other known methods such as flooding and gossip-based techniques.
Checking race freedom via linear programming
Authors: Terauchi Tachio
Published: June 2008

We present a new static analysis for race freedom and race detection. The analysis checks race freedom by reducing the problem to (rational) linear programming. Unlike conventional static analyses for race freedom or race detection, our analysis avoids explicit computation of locksets and lock linearity/must-aliasness. Our analysis can handle a variety of synchronization idioms that more conventional approaches often have difficulties with, such as thread joining, semaphores, and signals. We achieve efficiency by utilizing modern linear programming solvers that can quickly solve large linear programming instances. This paper reports on the formal properties of the analysis and the experience with applying an implementation to real world C programs.
Race directed random testing of concurrent programs
Authors: Sen Koushik
Published: June 2008

Bugs in multi-threaded programs often arise due to data races. Numerous static and dynamic program analysis techniques have been proposed to detect data races. We propose a novel randomized dynamic analysis technique that utilizes potential data race information obtained from an existing analysis tool to separate real races from false races without any need for manual inspection. Specifically, we use potential data race information obtained from an existing dynamic analysis technique to control a random scheduler of threads so that real race conditions get created with very high probability and those races get resolved randomly at runtime. Our approach has several advantages over existing dynamic analysis tools. First, we can create a real race condition and resolve the race randomly to see if an error can occur due to the race. Second, we can replay a race revealing execution efficiently by simply using the same seed for random number generation--we do not need to record the execution. Third, our approach has very low overhead compared to other precise dynamic race detection techniques because we only track all synchronization operations and a single pair of memory access statements that are reported to be in a potential race by an existing analysis. We have implemented the technique in a prototype tool for Java and have experimented on a number of large multi-threaded Java programs. We report a number of previously known and unknown bugs and real races in these Java programs.
A study of concurrent real-time garbage collectors
Authors: Pizlo Filip , Petrank Erez , Steensgaard Bjarne
Published: June 2008

Concurrent garbage collection is highly attractive for real-time systems, because offloading the collection effort from the executing threads allows faster response, allowing for extremely short deadlines at the microseconds level. Concurrent collectors also offer much better scalability over incremental collectors. The main problem with concurrent real-time collectors is their complexity. The first concurrent real-time garbage collector that can support fine synchronization, STOPLESS, has recently been presented by Pizlo et al. In this paper, we propose two additional (and different) algorithms for concurrent real-time garbage collection: CLOVER and CHICKEN. Both collectors obtain reduced complexity over the first collector STOPLESS, but need to trade a benefit for it. We study the algorithmic strengths and weaknesses of CLOVER and CHICKEN and compare them to STOPLESS. Finally, we have implemented all three collectors on the Bartok compiler and runtime for C# and we present measurements to compare their efficiency and responsiveness.
Conditional correlation analysis for safe region-based memory management
Authors: Wang Xi , Xu Zhilei , Liu Xuezheng , Guo Zhenyu , Wang Xiaoge , Zhang Zheng
Published: June 2008

Region-based memory management is a popular scheme in systems software for better organization and performance. In the scheme, a developer constructs a hierarchy of regions of different lifetimes and allocates objects in regions. When the developer deletes a region, the runtime will recursively delete all its subregions and simultaneously reclaim objects in the regions. The developer must construct a
consistent
placement of objects in regions; otherwise, if a region that contains pointers to other regions is not always deleted
before
pointees, an inconsistency will surface and cause dangling pointers, which may lead to either crashes or leaks.

This paper presents a static analysis tool RegionWiz that can find such lifetime inconsistencies in large C programs using regions. The tool is based on an analysis framework that generalizes the relations and constraints over regions and objects as conditional correlations. This framework allows a succinct formalization of consistency rules for region lifetimes, preserving memory safety and avoiding dangling pointers. RegionWiz uses these consistency rules to implement an efficient static analysis to compute the conditional correlation and reason about region lifetime consistency; the analysis is based on a context-sensitive, field-sensitive pointer analysis with heap cloning.

Experiments with applying RegionWiz to six real-world software packages (including the RC compiler, Apache web server, and Subversion version control system) with two different region-based memory management interfaces show that RegionWiz can reason about region lifetime consistency in large C programs. The experiments also show that RegionWiz can find several previously unknown inconsistency bugs in these packages.
Automatic volume management for programmable microfluidics
Authors: Amin Ahmed M. , Thottethodi Mithuna , Vijaykumar T. N. , Wereley Steven , Jacobson Stephen C.
Published: June 2008

Microfluidics has enabled lab-on-a-chip technology to miniaturize and integrate biological and chemical analyses to a single chip comprising channels, valves, mixers, heaters, separators, and sensors. Recent papers have proposed programmable labs-on-a-chip as an alternative to traditional application-specific chips to reduce design effort, time, and cost. While these previous papers provide the basic support for programmability, this paper identifies and addresses a practical issue, namely, fluid volume management. Volume management addresses the problem that the use of a fluid depletes it and unless the given volume of a fluid is distributed carefully among all its uses, execution may run out of the fluid before all its uses are complete. Additionally, fluid volumes should not overflow (i.e., exceed hardware capacity) or underflow (i.e., fall below hardware resolution). We show that the problem can be formulated as a linear programming problem (LP). Because LP's complexity and slow execution times in practice may be a concern, we propose another approach, called DAGSolve, which over-constrains the problem to achieve linear complexity while maintaining good solution quality. We also propose two optimizations, called cascading and static replication, to handle cases involving extreme mix ratios and numerous fluid uses which may defeat both LP and DAGSolve. Using some real-world assays, we show that our techniques produce good solutions while being faster than LP.
Foundations of the C++ concurrency memory model
Authors: Boehm Hans-J. , Adve Sarita V.
Published: June 2008

Currently multi-threaded C or C++ programs combine a single-threaded programming language with a separate threads library. This is not entirely sound [7].

We describe an effort, currently nearing completion, to address these issues by explicitly providing semantics for threads in the next revision of the C++ standard. Our approach is similar to that recently followed by Java [25], in that, at least for a well-defined and interesting subset of the language, we give sequentially consistent semantics to programs that do not contain data races. Nonetheless, a number of our decisions are often surprising even to those familiar with the Java effort:

We (mostly) insist on sequential consistency for race-free programs, in spite of implementation issues that came to light after the Java work.

We give no semantics to programs with data races. There are no benign C++ data races.

We use weaker semantics for trylock than existing languages or libraries, allowing us to promise sequential consistency with an intuitive race definition, even for programs with trylock.

This paper describes the simple model we would like to be able to provide for C++ threads programmers, and explain how this, together with some practical, but often under-appreciated implementation constraints, drives us towards the above decisions.
Expressive and safe static reflection with MorphJ
Authors: Huang Shan Shan , Smaragdakis Yannis
Published: June 2008

Recently, language extensions have been proposed for Java and C# to support
pattern-based reflective declaration
. These extensions introduce a disciplined form of meta-programming and aspect-oriented programming to mainstream languages: They allow members of a class (i.e., fields and methods) to be declared by statically iterating over and pattern-matching on members of other classes. Such techniques, however, have been unable to safely express simple, but common, idioms such as declaring getter and setter methods for fields.

In this paper, we present a mechanism that addresses the lack of expressiveness in past work without sacrificing safety. Our technique is based on the idea of nested patterns that elaborate the outer-most pattern with blocking or enabling conditions. We implemented this mechanism in a language, MorphJ. We demonstrate the expressiveness of MorphJ with real-world applications. In particular, the MorphJ reimplementation of DSTM2, a software transactional memory library, reduces 1,107 lines of Java reflection and bytecode engineering library calls to just 374 lines of MorphJ code. At the same time, the MorphJ solution is both high level and safer, as MorphJ can separately type check generic classes and catch errors early. We present and formalize the MorphJ type system, and offer a type-checking algorithm.
Iterative optimization in the polyhedral model
Authors: Pouchet Louis-Noël , Bastoul Cédric , Cohen Albert , Cavazos John
Published: June 2008

High-level loop optimizations are necessary to achieve good performance over a wide variety of processors. Their performance impact can be significant because they involve in-depth program transformations that aim to sustain a balanced workload over the computational, storage, and communication resources of the target architecture. Therefore, it is mandatory that the compiler accurately models the target architecture as well as the effects of complex code restructuring.

However, because optimizing compilers (1) use simplistic performance models that abstract away many of the complexities of modern architectures, (2) rely on inaccurate dependence analysis, and (3) lack frameworks to express complex interactions of transformation sequences, they typically uncover only a fraction of the peak performance available on many applications. We propose a complete iterative framework to address these issues. We rely on the polyhedral model to construct and traverse a large and expressive search space. This space encompasses only legal, distinct versions resulting from the restructuring of any static control loop nest. We first propose a feedback-driven iterative heuristic tailored to the search space properties of the polyhedral model. Though, it quickly converges to good solutions for small kernels, larger benchmarks containing higher dimensional spaces are more challenging and our heuristic misses opportunities for significant performance improvement. Thus, we introduce the use of a genetic algorithm with specialized operators that leverage the polyhedral representation of program dependences. We provide experimental evidence that the genetic algorithm effectively traverses huge optimization spaces, achieving good performance improvements on large loop nests.
A practical automatic polyhedral parallelizer and locality optimizer
Authors: Bondhugula Uday , Hartono Albert , Ramanujam J. , Sadayappan P.
Published: June 2008

We present the design and implementation of an automatic polyhedral source-to-source transformation framework that can optimize regular programs (sequences of possibly imperfectly nested loops) for parallelism and locality simultaneously. Through this work, we show the practicality of analytical model-driven automatic transformation in the polyhedral model -- far beyond what is possible by current production compilers. Unlike previous works, our approach is an end-to-end fully automatic one driven by an integer linear optimization framework that takes an explicit view of finding good ways of tiling for parallelism and locality using affine transformations. The framework has been implemented into a tool to automatically generate OpenMP parallel code from C program sections. Experimental results from the tool show very high speedups for local and parallel execution on multi-cores over state-of-the-art compiler frameworks from the research community as well as the best native production compilers. The system also enables the easy use of powerful empirical/iterative optimization for general arbitrarily nested loop sequences.
Orchestrating the execution of stream programs on multicore platforms
Authors: Kudlur Manjunath , Mahlke Scott
Published: June 2008

While multicore hardware has become ubiquitous, explicitly parallel programming models and compiler techniques for exploiting parallelism on these systems have noticeably lagged behind. Stream programming is one model that has wide applicability in the multimedia, graphics, and signal processing domains. Streaming models execute as a set of independent actors that explicitly communicate data through channels. This paper presents a compiler technique for planning and orchestrating the execution of streaming applications on multicore platforms. An integrated unfolding and partitioning step based on integer linear programming is presented that unfolds data parallel actors as needed and maximally packs actors onto cores. Next, the actors are assigned to pipeline stages in such a way that all communication is maximally overlapped with computation on the cores. To facilitate experimentation, a generalized code generation template for mapping the software pipeline onto the Cell architecture is presented. For a range of streaming applications, a geometric mean speedup of 14.7x is achieved on a 16-core Cell platform compared to a single core.
Deriving linearizable fine-grained concurrent objects
Authors: Vechev Martin , Yahav Eran
Published: June 2008

Practical and efficient algorithms for concurrent data structures are difficult to construct and modify. Algorithms in the literature are often optimized for a specific setting, making it hard to separate the algorithmic insights from implementation details. The goal of this work is to systematically construct algorithms for a concurrent data structure starting from its sequential implementation. Towards that goal, we follow a construction process that combines manual steps corresponding to high-level insights with automatic exploration of implementation details. To assist us in this process, we built a new tool called Paraglider. The tool quickly explores large spaces of algorithms and uses bounded model checking to check linearizability of algorithms.

Starting from a sequential implementation and assisted by the tool, we present the steps that we used to derive various highly-concurrent algorithms. Among these algorithms is a new fine-grained set data structure that provides a wait-free contains operation, and uses only the compare-and-swap (CAS) primitive for synchronization.
Sketching concurrent data structures
Authors: Solar-Lezama Armando , Jones Christopher Grant , Bodik Rastislav
Published: June 2008

We describe PSketch, a program synthesizer that helps programmers implement concurrent data structures. The system is based on the concept of sketching, a form of synthesis that allows programmers to express their insight about an implementation as a partial program: a sketch. The synthesizer automatically completes the sketch to produce an implementation that matches a given correctness criteria.

PSketch is based on a new counterexample-guided inductive synthesis algorithm (CEGIS) that generalizes the original sketch synthesis algorithm from Solar-Lezama et.al. to cope efficiently with concurrent programs. The new algorithm produces a correct implementation by iteratively generating candidate implementations, running them through a verifier, and if they fail, learning from the counterexample traces to produce a better candidate; converging to a solution in a handful of iterations.

PSketch also extends Sketch with higher-level sketching constructs that allow the programmer to express her insight as a "soup" of ingredients from which complicated code fragments must be assembled. Such sketches can be viewed as syntactic descriptions of huge spaces of candidate programs (over 10
8
candidates for some sketches we resolved).

We have used the PSketch system to implement several classes of concurrent data structures, including lock-free queues and concurrent sets with fine-grained locking. We have also sketched some other concurrent objects including a sense-reversing barrier and a protocol for the dining philosophers problem; all these sketches resolved in under an hour.
SharC
Authors: Anderson Zachary , Gay David , Ennals Rob , Brewer Eric
Published: June 2008

Unintended or unmediated data sharing is a frequent cause of insidious bugs in multithreaded programs. We present a tool called SharC (short for
Sharing Checker
) that allows a user to write lightweight annotations to declare how they believe objects are being shared between threads in their program. SharC uses a combination of static and dynamic analyses to check that the program conforms to this specification.

SharC allows any type to have one of five "sharing modes" -- private to the current thread, read-only, shared under the control of a specified lock, intentionally racy, or checked dynamically. The dynamic mode uses run-time checking to verify that objects are either read-only, or only accessed by one thread. This allows us to check programs that would be difficult to check with a purely static system. If the user does not give a type an explicit annotation, then SharC uses a static type-qualifier analysis to infer that it is either private or should be checked dynamically.

SharC allows objects to move between different sharing modes at runtime by using reference counting to check that there are no other references to the objects when they change mode.

SharC's baseline dynamic analysis can check any C program, but is slow, and will generate false warnings about intentional data sharing. As the user adds more annotations, false warnings are reduced, and performance improves.We have found in practice that very few annotations are needed to describe all sharing and give reasonable performance. We ran SharC on 6 legacy C programs, summing to over 600k lines of code, and found that a total of only 60 simple annotations were needed to remove all false positives and to reduce performance overhead to only 2-14%.
Liquid types
Authors: Rondon Patrick M. , Kawaguci Ming , Jhala Ranjit
Published: June 2008

We present
Logically Qualified Data Types
, abbreviated to
Liquid Types
, a system that combines
Hindley-Milner
type inference with
Predicate Abstraction
to automatically infer dependent types precise enough to prove a variety of safety properties. Liquid types allow programmers to reap many of the benefits of dependent types, namely static verification of critical properties and the elimination of expensive run-time checks, without the heavy price of manual annotation. We have implemented liquid type inference in DSOLVE, which takes as input an OCAML program and a set of logical qualifiers and infers dependent types for the expressions in the OCAML program. To demonstrate the utility of our approach, we describe experiments using DSOLVE to statically verify the safety of array accesses on a set of OCAML benchmarks that were previously annotated with dependent types as part of the DML project. We show that when used in conjunction with a fixed set of array bounds checking qualifiers, DSOLVE reduces the amount of manual annotation required for proving safety from 31% of program text to under 1%.
Certifying low-level programs with hardware interrupts and preemptive threads
Authors: Feng Xinyu , Shao Zhong , Dong Yuan , Guo Yu
Published: June 2008

Hardware interrupts are widely used in the world's critical software systems to support preemptive threads, device drivers, operating system kernels, and hypervisors. Handling interrupts properly is an essential component of low-level system programming. Unfortunately, interrupts are also extremely hard to reason about: they dramatically alter the program control flow and complicate the invariants in low-level concurrent code (e.g., implementation of synchronization primitives). Existing formal verification techniques---including Hoare logic, typed assembly language, concurrent separation logic, and the assume-guarantee method---have consistently ignored the issues of interrupts; this severely limits the applicability and power of today's program verification systems.

In this paper we present a novel Hoare-logic-like framework for certifying low-level system programs involving both hardware interrupts and preemptive threads. We show that enabling and disabling interrupts can be formalized precisely using simple ownership-transfer semantics, and the same technique also extends to the concurrent setting. By carefully reasoning about the interaction among interrupt handlers, context switching, and synchronization libraries, we are able to---for the first time---successfully certify a preemptive thread implementation and a large number of common synchronization primitives. Our work provides a foundation for reasoning about interrupt-based kernel programs and makes an important advance toward building fully certified operating system kernels and hypervisors.
Type-preserving compilation for large-scale optimizing object-oriented compilers
Authors: Chen Juan , Hawblitzel Chris , Perry Frances , Emmi Mike , Condit Jeremy , Coetzee Derrick , Pratikaki Polyvios
Published: June 2008

Type-preserving compilers translate well-typed source code, such as Java or C#, into verifiable target code, such as typed assembly language or proof-carrying code. This paper presents the implementation of type-preserving compilation in a complex, large-scale optimizing compiler. Compared to prior work, this implementation supports extensive optimizations, and it verifies a large portion of the interface between the compiler and the runtime system. This paper demonstrates the practicality of type-preserving compilation in complex optimizing compilers: the generated typed assembly language is only 2.3% slower than the base compiler's generated untyped assembly language, and the type-preserving compiler is 82.8% slower than the base compiler.
Quantitative information flow as network flow capacity
Authors: McCamant Stephen , Ernst Michael D.
Published: June 2008

We present a new technique for determining how much information about a program's secret inputs is revealed by its public outputs. In contrast to previous techniques based on reachability from secret inputs (tainting), it achieves a more precise quantitative result by computing a maximum flow of information between the inputs and outputs. The technique uses static control-flow regions to soundly account for implicit flows via branches and pointer operations, but operates dynamically by observing one or more program executions and giving numeric flow bounds specific to them (e.g., "17 bits"). The maximum flow in a network also gives a minimum cut (a set of edges that separate the secret input from the output), which can be used to efficiently check that the same policy is satisfied on future executions. We performed case studies on 5 real C, C++, and Objective C programs, 3 of which had more than 250K lines of code. The tool checked multiple security policies, including one that was violated by a previously unknown bug.