Exploiting Hierarchical Locality for Extreme Scale Architectures
Open AccessParallel computer architectures are evolving with deeper memory subsystems and multi-level interconnection networks, in extreme scale systems. With the advent of the multi- andmany-core processors, we started to experience deeper cache hierarchy with high NUMA/NUCA effects, even within thesame node. At the same time, many of the widely used interconnect topologies are also hierarchical in nature, such as fat-tree and dragonfly topologies. Thus, due to these resulting deep hierarchy architectural characteristics, in order to efficiently leverage the maximum capability of the underlying hardware, exploiting hierarchical locality is inevitable. From a parallel application point of view, establishing the affinity between a piece of data and a thread, is what we consider to be the first-order of locality.Higher orders of locality can be attained by grouping threads hierarchically, at different levels, to reach the lowest possible data movement overhead.Pure shared memory programming models exposes no notion oflocality, and thus establishing the first-order of locality becomes impossible. Moreover, since programmers cannot express and control any form of locality, exploiting the hierarchical locality becomes an almost unattainable task.However, when supported by locality-aware programming models, such asmessage passing and Partitioned Global Address Space (PGAS), programmers are able to control locality at one level through establishing affinity between the data and executing activities. This, however, does not provide any localityexploitation at other levels. Therefore, we must conceive an efficientabstraction of hierarchical locality and develop techniques to exploit it.Nevertheless, techniques that are applied directly by programmers, beyond the first level, not only can burden the programmers and hinder their productivity, but may not also guarantee performance portability across different systems.This research seeks to address the above challenges by proposing a design philosophy and techniques, based on which productive runtime systems can be built. The two principles of this design philosophy are:- Trust the programmers or the domain scientists to have full control over the data affinity to the parallel threads (``first-order locality"); - Do not burden the programmers with handling the higher order locality in a hierarchical architecture, as this would be a great hindrance to their productivity. Instead, realizing higher-order of locality should be the task of the parallel runtime system, that can be easily built on top of the first-order.Following this philosophy, we introduced two models with techniques for exploiting hierarchical locality:- A static model: Parallel Hierarchical Locality Abstraction Model for Execution (PHLAME).PHLAME is an execution model to abstract and exploit machine hierarchicalproperties through locality-aware programming and a runtime that takes intoaccount machine characteristics; as well as data sharing and communicationprofile of the underlying application. Our experiments show that these techniques scale up and achieve performance gains of up to 88%.- A dynamic model: Locality-aware Automatic Migration of Processes system (LAMP). LAMP utilizes multi-resolution decentralized monitoring mechanisms, in order to guide thread migration to achieve higher-orders of locality in parallel applications. Our experiments show that we can achieveperformance gains of up to 8% when threads are allowed to migratewithin the nodes. We also presented a model that predictsthe gain when process migration is permitted at any level. Using this model, we show that the expected gain can be up to 30% if process migration is allowed between nodes.
- All rights reserved
Notice to Authors
If you are the author of this work and you have any questions about the information on this page, please use the Contact form to get in touch with us.