A Lifetime-based Garbage Collector for LISP Systems on General-Purpose Computers

Garbage collector performance in LISP systems on custom hardware has been substantially improved by the adoption of lifetime-based garbage collection techniques. To date, however, successful lifetime-based garbage collectors have required special-purpose hardware, or at least privileged access to data structures maintained by the virtual memory system. I present here a lifetime-based garbage collector requiring no special-purpose hardware or virtual memory system support, and discuss its performance.

Volume-based garbage collection fees : the Illinois experience /

"Presented at the ASTSWMO 1992 National Solid Waste Forum July 20-22, 1992, Portland, OR."

Sparsely Faceted Arrays: A Mechanism Supporting Parallel Allocation, Communication, and Garbage Collection

Conventional parallel computer architectures do not provide support for non-uniformly distributed objects. In this thesis, I introduce sparsely faceted arrays (SFAs), a new low-level mechanism for naming regions of memory, or facets, on different processors in a distributed, shared memory parallel processing system. Sparsely faceted arrays address the disconnect between the global distributed arrays provided by conventional architectures (e.g. the Cray T3 series), and the requirements of high-level parallel programming methods that wish to use objects that are distributed over only a subset of processing elements. A sparsely faceted array names a virtual globally-distributed array, but actual facets are lazily allocated. By providing simple semantics and making efficient use of memory, SFAs enable efficient implementation of a variety of non-uniformly distributed data structures and related algorithms. I present example applications which use SFAs, and describe and evaluate simple hardware mechanisms for implementing SFAs. Keeping track of which nodes have allocated facets for a particular SFA is an important task that suggests the need for automatic memory management, including garbage collection. To address this need, I first argue that conventional tracing techniques such as mark/sweep and copying GC are inherently unscalable in parallel systems. I then present a parallel memory-management strategy, based on reference-counting, that is capable of garbage collecting sparsely faceted arrays. I also discuss opportunities for hardware support of this garbage collection strategy. I have implemented a high-level hardware/OS simulator featuring hardware support for sparsely faceted arrays and automatic garbage collection. I describe the simulator and outline a few of the numerous details associated with a "real" implementation of SFAs and SFA-aware garbage collection. Simulation results are used throughout this thesis in the evaluation of hardware support mechanisms.

Garbage Collection is Fast, But a Stack is Faster

Prompted by claims that garbage collection can outperform stack allocation when sufficient physical memory is available, we present a careful analysis and set of cross-architecture measurements comparing these two approaches for the implementation of continuation (procedure call) frames. When the frames are allocated on a heap they require additional space, increase the amount of data transferred between memory and registers, and, on current architectures, require more instructions. We find that stack allocation of continuation frames outperforms heap allocation in some cases by almost a factor of three. Thus, stacks remain an important implementation technique for procedure calls, even in the presence of an efficient, compacting garbage collector and large amounts of memory.

Assessing the impact of shore-based shellfish collection on under-boulder communities in Strangford Lough.

Under-boulder communities are listed as a priority habitat as they provide shelter, shade and moisture and play an important role in the life-cycle of many marine algae and animals.

Home-based versus clinic-based specimen collection in the management of Chlamydia trachomatis and Neisseria gonorrhoeae infections

BACKGROUND Chlamydia trachomatis (CT) and Neisseria gonorrhoeae (NG) are the most frequent causes of bacterial sexually transmitted infections (STIs). Management strategies that reduce losses in the clinical pathway from infection to cure might improve STI control and reduce complications resulting from lack of, or inadequate, treatment. OBJECTIVES To assess the effectiveness and safety of home-based specimen collection as part of the management strategy for Chlamydia trachomatis and Neisseria gonorrhoeae infections compared with clinic-based specimen collection in sexually-active people. SEARCH METHODS We searched the Cochrane Sexually Transmitted Infections Group Specialized Register, the Cochrane Central Register of Controlled Trials (CENTRAL), MEDLINE, EMBASE and LILACS on 27 May 2015, together with the World Health Organization International Clinical Trials Registry (ICTRP) and ClinicalTrials.gov. We also handsearched conference proceedings, contacted trial authors and reviewed the reference lists of retrieved studies. SELECTION CRITERIA Randomized controlled trials (RCTs) of home-based compared with clinic-based specimen collection in the management of C. trachomatis and N. gonorrhoeae infections. DATA COLLECTION AND ANALYSIS Three review authors independently assessed trials for inclusion, extracted data and assessed risk of bias. We contacted study authors for additional information. We resolved any disagreements through consensus. We used standard methodological procedures recommended by Cochrane. The primary outcome was index case management, defined as the number of participants tested, diagnosed and treated, if test positive. MAIN RESULTS Ten trials involving 10,479 participants were included. There was inconclusive evidence of an effect on the proportion of participants with index case management (defined as individuals tested, diagnosed and treated for CT or NG, or both) in the group with home-based (45/778, 5.8%) compared with clinic-based (51/788, 6.5%) specimen collection (risk ratio (RR) 0.88, 95% confidence interval (CI) 0.60 to 1.29; 3 trials, I² = 0%, 1566 participants, moderate quality). Harms of home-based specimen collection were not evaluated in any trial. All 10 trials compared the proportions of individuals tested. The results for the proportion of participants completing testing had high heterogeneity (I² = 100%) and were not pooled. We could not combine data from individual studies looking at the number of participants tested because the proportions varied widely across the studies, ranging from 30% to 96% in home group and 6% to 97% in clinic group (low-quality evidence). The number of participants with positive test was lower in the home-based specimen collection group (240/2074, 11.6%) compared with the clinic-based group (179/967, 18.5%) (RR 0.72, 95% CI 0.61 to 0.86; 9 trials, I² = 0%, 3041 participants, moderate quality). AUTHORS' CONCLUSIONS Home-based specimen collection could result in similar levels of index case management for CT or NG infection when compared with clinic-based specimen collection. Increases in the proportion of individuals tested as a result of home-based, compared with clinic-based, specimen collection are offset by a lower proportion of positive results. The harms of home-based specimen collection compared with clinic-based specimen collection have not been evaluated. Future RCTs to assess the effectiveness of home-based specimen collection should be designed to measure biological outcomes of STI case management, such as proportion of participants with negative tests for the relevant STI at follow-up.

Garbage collection optimization for non uniform memory access architectures

Cache-coherent non uniform memory access (ccNUMA) architecture is a standard design pattern for contemporary multicore processors, and future generations of architectures are likely to be NUMA. NUMA architectures create new challenges for managed runtime systems. Memory-intensive applications use the system’s distributed memory banks to allocate data, and the automatic memory manager collects garbage left in these memory banks. The garbage collector may need to access remote memory banks, which entails access latency overhead and potential bandwidth saturation for the interconnection between memory banks. This dissertation makes five significant contributions to garbage collection on NUMA systems, with a case study implementation using the Hotspot Java Virtual Machine. It empirically studies data locality for a Stop-The-World garbage collector when tracing connected objects in NUMA heaps. First, it identifies a locality richness which exists naturally in connected objects that contain a root object and its reachable set— ‘rooted sub-graphs’. Second, this dissertation leverages the locality characteristic of rooted sub-graphs to develop a new NUMA-aware garbage collection mechanism. A garbage collector thread processes a local root and its reachable set, which is likely to have a large number of objects in the same NUMA node. Third, a garbage collector thread steals references from sibling threads that run on the same NUMA node to improve data locality. This research evaluates the new NUMA-aware garbage collector using seven benchmarks of an established real-world DaCapo benchmark suite. In addition, evaluation involves a widely used SPECjbb benchmark and Neo4J graph database Java benchmark, as well as an artificial benchmark. The results of the NUMA-aware garbage collector on a multi-hop NUMA architecture show an average of 15% performance improvement. Furthermore, this performance gain is shown to be as a result of an improved NUMA memory access in a ccNUMA system. Fourth, the existing Hotspot JVM adaptive policy for configuring the number of garbage collection threads is shown to be suboptimal for current NUMA machines. The policy uses outdated assumptions and it generates a constant thread count. In fact, the Hotspot JVM still uses this policy in the production version. This research shows that the optimal number of garbage collection threads is application-specific and configuring the optimal number of garbage collection threads yields better collection throughput than the default policy. Fifth, this dissertation designs and implements a runtime technique, which involves heuristics from dynamic collection behavior to calculate an optimal number of garbage collector threads for each collection cycle. The results show an average of 21% improvements to the garbage collection performance for DaCapo benchmarks.

Identification of logically related heap regions

This paper introduces a novel technique for identifying logically related sections of the heap such as recursive data structures, objects that are part of the same multi-component structure, and related groups of objects stored in the same collection/array. When combined withthe lifetime properties of these structures, this information can be used to drive a range of program optimizations including pool allocation, object co-location, static deallocation, and region-based garbage collection. The technique outlined in this paper also improves the efficiency of the static analysis by providing a normal form for the abstract models (speeding the convergence of the static analysis). We focus on two techniques for grouping parts of the heap. The first is a technique for precisely identifying recursive data structures in object-oriented programs based on the types declared in the program. The second technique is a novel method for grouping objects that make up the same composite structure and that allows us to partition the objects stored in a collection/array into groups based on a similarity relation. We provide a parametric component in the similarity relation in order to support specific analysis applications (such as a numeric analysis which would need to partition the objects based on numeric properties of the fields). Using the Barnes-Hut benchmark from the JOlden suite we show how these grouping methods can be used to identify various types of logical structures allowing the application of many region-based program optimizations.

Integrating a mobile accessible electronic system into dockside monitoring: How can small-scale fisheries data collection programs transition from paper-based to digital data collection?

Thesis (Master's)--University of Washington, 2016-06

Image-based safety assessment : automated spatial safety risk identification of earthmoving and surface mining activities

This paper presents an automated image‐based safety assessment method for earthmoving and surface mining activities. The literature review revealed the possible causes of accidents on earthmoving operations, investigated the spatial risk factors of these types of accident, and identified spatial data needs for automated safety assessment based on current safety regulations. Image‐based data collection devices and algorithms for safety assessment were then evaluated. Analysis methods and rules for monitoring safety violations were also discussed. The experimental results showed that the safety assessment method collected spatial data using stereo vision cameras, applied object identification and tracking algorithms, and finally utilized identified and tracked object information for safety decision making.

Efficient Content-based Routing, Mobility-aware Topologies, and Temporal Subspace Matching

Event-based systems are seen as good candidates for supporting distributed applications in dynamic and ubiquitous environments because they support decoupled and asynchronous many-to-many information dissemination. Event systems are widely used, because asynchronous messaging provides a flexible alternative to RPC (Remote Procedure Call). They are typically implemented using an overlay network of routers. A content-based router forwards event messages based on filters that are installed by subscribers and other routers. The filters are organized into a routing table in order to forward incoming events to proper subscribers and neighbouring routers. This thesis addresses the optimization of content-based routing tables organized using the covering relation and presents novel data structures and configurations for improving local and distributed operation. Data structures are needed for organizing filters into a routing table that supports efficient matching and runtime operation. We present novel results on dynamic filter merging and the integration of filter merging with content-based routing tables. In addition, the thesis examines the cost of client mobility using different protocols and routing topologies. We also present a new matching technique called temporal subspace matching. The technique combines two new features. The first feature, temporal operation, supports notifications, or content profiles, that persist in time. The second feature, subspace matching, allows more expressive semantics, because notifications may contain intervals and be defined as subspaces of the content space. We also present an application of temporal subspace matching pertaining to metadata-based continuous collection and object tracking.

A TDMA-based Energy Aware MAC (TEA-MAC) Protocol for Reliable Multicast in WSNs

Multicast in wireless sensor networks (WSNs) is an efficient way to spread the same data to multiple sensor nodes. It becomes more effective due to the broadcast nature of wireless link, where a message transmitted from one source is inherently received by all one-hop receivers, and therefore, there is no need to transmit the message one by one. Reliable multicast in WSNs is desirable for critical tasks like code updation and query based data collection. The erroneous nature of wireless medium coupled with limited resource of sensor nodes, makes the design of reliable multicast protocol a challenging task. In this work, we propose a time division multiple access (TDMA) based energy aware media access and control (TEA-MAC) protocol for reliable multicast in WSNs. The TDMA eliminates collisions, overhearing and idle listening, which are the main sources of reliability degradation and energy consumption. Furthermore, the proposed protocol is parametric in the sense that it can be used to trade-off reliability with energy and delay as per the requirement of the underlying applications. The performance of TEA-MAC has been evaluated by simulating it using Castalia network simulator. Simulation results show that TEA-MAC is able to considerably improve the performance of multicast communication in WSNs.

Towards Formalizing Java's Weak References

Weak references provide the programmer with limited control over the process of memory management. By using them, a programmer can make decisions based on previous actions that are taken by the garbage collector. Although this is often helpful, the outcome of a program using weak references is less predictable due to the nondeterminism they introduce in program evaluation. It is therefore desirable to have a framework of formal tools to reason about weak references and programs that use them. We present several calculi that formalize various aspects of weak references, inspired by their implementation in Java. We provide a calculus to model multiple levels of non-strong references, where a different garbage collection policy is applied to each level. We consider different collection policies such as eager collection and lazy collection. Similar to the way they are implemented in Java, we give the semantics of eager collection to weak references and the semantics of lazy collection to soft references. Moreover, we condition garbage collection on the availability of time and space resources. While time constraints are used in order to restrict garbage collection, space constraints are used in order to trigger it. Finalizers are a problematic feature in Java, especially when they interact with weak references. We provide a calculus to model finalizer evaluation. Since finalizers have little meaning in a language without side-effect, we introduce a limited form of side effect into the calculus. We discuss determinism and the separate notion of uniqueness of (evaluation) outcome. We show that in our calculus, finalizer evaluation does not affect uniqueness of outcome.

The formal specification of abstract data types and their implementation in Fortran 90: Implementation issues concerning the use of pointers

In this paper we continue our investigation into the development of computational-science software based on the identification and formal specification of Abstract Data Types (ADTs) and their implementation in Fortran 90. In particular, we consider the consequences of using pointers when implementing a formally specified ADT in Fortran 90. Our aim is to highlight the resulting conflict between the goal of information hiding, which is central to the ADT methodology, and the space efficiency of the implementation. We show that the issue of storage recovery cannot be avoided by the ADT user, and present a range of implementations of a simple ADT to illustrate various approaches towards satisfactory storage management. Finally, we propose a set of guidelines for implementing ADTs using pointers in Fortran 90. These guidelines offer a way gracefully to provide disposal operations in Fortran 90. Such an approach is desirable since Fortran 90 does not provide automatic garbage collection which is offered by many object-oriented languages including Eiffel, Java, Smalltalk, and Simula.