Hybrid Memory Management for Parallel Execution of Prolog on Shared Memory Multiprocessors.

摘要

Shared memory multiprocessors can provide high processing power at relatively low cost. In contrast to message passing systems, shared memory multiprocessors allow for efficient data sharing, and thus are more suitable for execution models that exploit medium grain parallelism. This dissertation investigates the problem of memory management for a globally shared space in a parallel execution environment. An AND/OR parallel execution model of Prolog is chosen for our work due to its medium grain parallelism and its intensive memory usage characteristics. With respect to space, we propose a hybrid heap-stack (called ELPS) which is dynamically allocated for more efficient space sharing and interference-free parallel execution. With respect to time, we present a two-tier memory architecture (called the Aquarius-II) with separate synchronization and high-bandwidth memory spaces. A multiprocessor simulation system has been developed to evaluate the performance of ELPS and the Aquarius-II. ELPS incurs an average of 2% overhead (11% without hardware support), while satisfying the memory requirement to keep up with the speedup potential of the parallel execution model. Compared to the single bus multiprocessor architecture, the Aquarius-II provides higher performance by reducing contention on the synchronization bus and by providing a higher memory bandwidth with a crossbar. A simple broadcast for invalidation scheme is sufficient to keep the crossbar caches consistent while maintaining good cache performance.