Title: Dynamic tiling for effective use of shared caches on multithreaded processors

Authors: Dimitrios S. Nikolopoulos

Addresses: Department of Computer Science, College of William and Mary, Williamsburg, VA, USA

Abstract: Simultaneous multithreaded (SMT) processors use data caches which are dynamically shared between threads. Depending on the processor workload, sharing the data cache may harm performance due to excessive cache conflicts. A way to overcome this problem is to physically partition the cache between threads. Unfortunately, partitioning the cache requires additional hardware and may lead to lower utilisation of the cache in certain workloads. It is therefore important to consider software mechanisms to implicitly partition the cache between threads by controlling the locations in the cache in which each thread can load data. This paper proposes standard program transformations for partitioning the shared data caches of SMT processors, if and only if there are conflicts between threads in the shared cache at runtime. We propose transformations based on dynamic tiling. The key idea is to use two tile sizes in the program, one for single-threaded execution mode and one suitable for multithreaded execution mode and switch between tile sizes at runtime. Our transformations combine dynamic tiling with either copying or storing arrays in block layout. The paper presents an implementation of these transformations along with runtime mechanisms for detecting cache contention between threads and react to it on-the-fly. Our experimental results show that for regular, perfect loop nests, these transformations provide substantial performance improvements.

Keywords: simultaneous multithreading; SMT processors; shared caches; compilers; memory hierarchies; runtime systems; operating systems; data cache conflicts; data cache partitioning; dynamic tiling; high performance computing; multiple threads.

DOI: 10.1504/IJHPCN.2004.009265

International Journal of High Performance Computing and Networking, 2004 Vol.2 No.1, pp.22 - 35

Published online: 14 Mar 2006 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article