A portable runtime interface for multi-level memory hierarchies

The efficient use of a machine's memory system and parallel processing resources has become one of the most important challenges in program optimization. Moreover, efficient use of the memory hierarchy is increasingly important because of the power cost of data transfers through the system. Architecture trends are leading to large scale parallelism using simpler cores and progressively deeper and complex memory hierarchies. These new architecture designs have improved power characteristics and can offer large increases in performance, but traditional programming techniques are inadequate for these architectures.; In this dissertation, we explore a programming language and runtime system for making efficient use of the memory hierarchy and parallel processing resources. This dissertation provides an overview of Sequoia, a programming language we have developed at Stanford to facilitate the development of memory hierarchy aware parallel programs that remain portable across modern machines featuring different memory hierarchy configurations. Sequoia abstractly exposes hierarchical memory in the programming model and provides language mechanisms to describe communication vertically through the machine and to localize computation to particular memory locations within it.; This dissertation presents a platform independent runtime interface for moving data and computation through parallel machines with multi-level memory hierarchies. We show that this interface can be used as a compiler target for the Sequoia language and compiler, and can be implemented easily and efficiently on a variety of platforms. The interface design allows us to compose multiple runtimes, achieving portability across machines with multiple memory levels. We demonstrate portability of Sequoia programs across machines with two memory levels with runtime implementations for multi-core/SMP machines, the STI Cell Broadband Engine, a distributed memory cluster, and disk systems. We also demonstrate portability across machines with multiple memory levels by composing runtimes and running on a cluster of SMP nodes, out-of-core algorithms on a Sony Playstation 3 pulling data from disk, and a cluster of Sony Playstation 3's. All of this is done without any source level modifications to the Sequoia program. With this uniform interface, we achieve good performance for our applications and maximize bandwidth and computational resources on these system configurations.