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.

The Design of a Mechanical Assembly System

This thesis describes a mechanical assembly system called LAMA (Language for Automatic Mechanical Assembly). The goal of the work was to create a mechanical assembly system that transforms a high-level description of an automatic assembly operation into a program or execution by a computer controlled manipulator. This system allows the initial description of the assembly to be in terms of the desired effects on the parts being assembled. Languages such as WAVE [Bolles & Paul] and MINI [Silver] fail to meet this goal by requiring the assembly operation to be described in terms of manipulator motions. This research concentrates on the spatial complexity of mechanical assembly operations. The assembly problem is seen as the problem of achieving a certain set of geometrical constraints between basic objects while avoiding unwanted collisions. The thesis explores how these two facets, desired constraints and unwanted collisions, affect the primitive operations of the domain.

MicroRNAs Modulate Hematopoietic Lineage Differentiation

MicroRNAs (miRNAs), an abundant class of ~22 nucleotide non-coding RNAs, are thought to play an important regulatory role in animal and plant development at the posttranscriptional level. Many miRNAs cloned from mouse bone marrow cells are differentially regulated in various hematopoietic lineages, suggesting that they might influence hematopoietic lineage differentiation. Some human miRNAs are linked to leukemias: the miR-15a/miR-16 locus is frequently deleted or down-regulated in patients with B-cell chronic lymphocytic leukemia and miR-142 is at a translocation site found in a case of aggressive B-cell leukemia. miR-181, a miRNA upregulated only in the B cell lineage of mouse bone marrow cells, promotes B cell differentiation and inhibits production of CD8⁺ T cells when expressed in hematopoietic stem/progenitor cells. In contrast miR-142s inhibits production of both CD4⁺ and CD8⁺ T cells and does not affect B cells. Collectively, these results indicate that microRNAs are components of the molecular circuitry controlling mouse hematopoiesis and suggest that other microRNAs have similar regulatory roles during other facets of vertebrate development.