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. _______________ This work supported in part by NSF Grant CCR-9321424.
By: Ioana Banicescu (Polytechnic Univ.) and Susan Flynn Hummel
Published in: RC19934 in 1995
LIMITED DISTRIBUTION NOTICE:
This Research Report is available. This report has been submitted for publication outside of IBM and will probably be copyrighted if accepted for publication. It has been issued as a Research Report for early dissemination of its contents. In view of the transfer of copyright to the outside publisher, its distribution outside of IBM prior to publication should be limited to peer communications and specific requests. After outside publication, requests should be filled only by reprints or legally obtained copies of the article (e.g., payment of royalties). I have read and understand this notice and am a member of the scientific community outside or inside of IBM seeking a single copy only.
Questions about this service can be mailed to reports@us.ibm.com .