Performance analysis and auto-tuning of batch thread schedulers

Abstract

Threads are provided by modern operating systems as a lightweight alternative to processes which are easily manageable at the user level. In the same process, threads share information such as the address space allowing for processes to split work amongst various threads which may be spread across a machines cores in a multi-core environment. E ciency in thread scheduling is vital as the overhead of the scheduler may negate any bene ts gained through utilising threads, even in a multi-core setting. With CPU clock speeds increasing and the overhead of using memory becoming more signi cant, e cient utilisation of the cache is vital with increasing the performance of any high performance application. Therefore, cache a ne thread scheduling is crucial for providing good performance. Reducing the amount of cache misses avoids the need to access slower areas in memory. As such, thread schedulers which promote high levels of thread locality are desirable. Batching is a technique which groups ne grained threads into coarser grained entities termed batches, in order to promote repeated cache use amongst grouped threads whilst still sharing work over all available cores in multi-core machines. Machine learning is commonly used to optimise algorithms and recently work has been done to apply machine learning methods to enhance thread scheduling algorithms. This project discusses the results of implementing a batch based scheduler on modern hardware and proposes a method to utilize optimisation methods in order to auto-tune the batch parameters for any given application.