Name
Abstract | ||
|---|---|---|
Iteration space tiling and scheduling is an important technique for optimizing loops that constitute a large fraction of execution times in computation kernels of both scientific codes and embedded applications. While tiling has been studied extensively in the context of both uniprocessor and multiprocessor platforms, prior research has paid less attention to tile scheduling, especially when targeting multicore machines with deep on-chip cache hierarchies. In this paper, we propose a cache hierarchy-aware tile scheduling algorithm for multicore machines, with the purpose of maximizing both horizontal and vertical data reuses in on-chip caches, and balancing the workloads across different cores. This scheduling algorithm is one of the key components in a source-to-source translation tool that we developed for automatic loop parallelization and multithreaded code generation from sequential codes. To the best of our knowledge, this is the first effort that develops a fully-automated tile scheduling strategy customized for on-chip cache topologies of multicore machines. The experimental results collected by executing twelve application programs on three commercial Intel machines (Nehalem, Dunnington, and Harpertown) reveal that our cache-aware tile scheduling brings about 27.9% reduction in cache misses, and on average, 13.5% improvement in execution times over an alternate method tested. |
Year | DOI | Venue |
|---|---|---|
2011 | 10.1109/CGO.2011.5764684 | CGO |
Keywords | Field | DocType |
on-chip cache hierarchy-aware tile,execution time,processor scheduling,deep on-chip cache hierarchies,workload balancing,vertical data reuses,computation kernels,embedded applications,on-chip cache topology,source-to-source translation tool,tile scheduling,optimizing loops,sequential codes,cache storage,scheduling algorithm,on-chip cache,automatic loop parallelization,multi-threading,on-chip cache hierarchy-aware tile scheduling,resource allocation,multiprocessing systems,cache-aware tile scheduling,deep on-chip cache hierarchy,uniprocessor platforms,multithreaded code generation,fully-automated tile scheduling strategy,cache hierarchy-aware tile scheduling,cache hierarchy-aware tile scheduling algorithm,multicore machines,program control structures,iteration space tiling,embedded systems,horizontal data reuses,on-chip caches,scientific codes,multicore machine,multiprocessor platforms,schedules,multi threading,code generation,multicore processing,system on a chip,shape,optimization,chip | Uniprocessor system,Fair-share scheduling,Cache,Computer science,Scheduling (computing),Parallel computing,Cache algorithms,Real-time computing,Schedule,Dynamic priority scheduling,Multi-core processor | Conference |
ISSN | ISBN | Citations |
2164-2397 | 978-1-61284-358-2 | 11 |
PageRank | References | Authors |
0.55 | 28 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Jun Liu | 1 | 822 | 38.24 |
| Yuanrui Zhang | 2 | 180 | 15.48 |
| Wei Ding | 3 | 130 | 11.67 |
| Mahmut T. Kandemir | 4 | 7371 | 568.54 |