Balancing Processor Loads and Exploiting Data Locality in Irregular Computations

Fractiling is a scheduling scheme that simultaneously balances processor loads and exploits locality. Because it is based on a probabilistic analysis, fractiling accommodates load imbalances caused by both predictable phenomena, such as irregular data and conditional statements, and also unpredictable phenomena, such as data access latency and operating system interference. Fractiling exploits both temporal locality, which is often profitable for computations on regular data, and spatial locality, which is often profitable for computations on irregular data. Here, we report on a case study involving the application of fractiling to computations on irregular data, namely N-body simulations. In experiments on a KSR1, performance was improved by as much as 43% by fractiling. Performance improvements were obtained on nonuniform and uniform distributions of bodies, underscoring the need for a scheduling scheme that accommodates application as well as system induced execution time variance. ..