Improving fine-grained multithreading performance through object-affinity scheduling

Abstract

Object-oriented parallel programming uses a philosophy common to both multithreading and object-oriented programming (OOP). The use of OOP for multithreading can help maintain an abstraction from the concept of a thread, providing concurrent objects whose complex details are encapsulated. Moreover, for thread schedulers developed as libraries for existing languages, OOP's encapsulation and hierarchical model provides mechanisms which can ensure a certain amount of security for the scheduler. Fine-grained multi threading involves scheduling large numbers of frequently communicating threads. This means that in order to maintain performance on par with coarser-grain scheduling, thread management overheads must be kept as low as possible. The design of the scheduler's scheduling strategy can drastically affect performance. One such strategy, locality-based scheduling, involves grouping common threads together so as to improve cache exploitation and decrease contention for shared resources. Used in conjunction with an object-oriented approach, this strategy gives rise to object-affinity advantages. We develop two object-oriented uniprocessor schedulers which aim to take advantage of object-affinity scheduling. The first, adapted from SSRG's smash, employs a circular run queue and is used to gauge the effect of using an object-oriented programming approach. The second, BOOSH, uses objects as the criteria for batching groups of related threads together. A batch is composed of threads representing the object's methods. Object-affinity scheduling advantages arise from the fact that the threads representing member methods will very often be accessing the same data, that is, the object's member data. Also, since the threads of a particular batch are executed for a number of dispatches before the batch yields control to another batch, threads would be able to find a copy of the data they require still in the cache, thereby reducing cache misses. We find that for applications which make good use of its batching facilities, BOOSH is capable of significantly improving performance. At the same time, for applications which do not take full advantage of batching, performance does not degrade drastically. Together with the above two schedulers, we also study possible ways of implementing an object-oriented batch-based scheduler on an SMP system.