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.

Modeling the Transport Sector: The Role of Existing Fuel Taxes in Climate Policy

Existing fuel taxes play a major role in determining the welfare effects of exempting the transportation sector from measures to control greenhouse gases. To study this phenomenon we modify the MIT Emissions Prediction and Policy Analysis (EPPA) model to disaggregate the household transportation sector. This improvement requires an extension of the GTAP data set that underlies the model. The revised and extended facility is then used to compare economic costs of cap-and-trade systems differentiated by sector, focusing on two regions: the USA where the fuel taxes are low, and Europe where the fuel taxes are high. We find that the interplay between carbon policies and pre-existing taxes leads to different results in these regions: in the USA exemption of transport from such a system would increase the welfare cost of achieving a national emissions target, while in Europe such exemptions will correct pre-existing distortions and reduce the cost.