Name
Title | ||
|---|---|---|
Cache-conscious scheduling of streaming pipelines on parallel machines with private caches |
Abstract | ||
|---|---|---|
This paper studies the problem of scheduling a streaming pipeline on a multicore machine with private caches to maximize throughput. The theoretical contribution includes lower and upper bounds in the parallel external-memory model. We show that a simple greedy scheduling strategy is asymptotically optimal with a constant-factor memory augmentation. More specifically, we show that if our strategy has a running time of Q cache misses on a machine with size-M caches, then every “static” scheduling policy must have time at least that of Q(Q) cache misses on a machine with size-M/6 caches. Our experimental study considers the question of whether scheduling based on cache effects is more important than scheduling based on only the number of computation steps. Using synthetic pipelines with a range of parameters, we compare our cache-based partitioning against several other static schedulers that load-balance computation. In most cases, the cache-based partitioning indeed beats the other schedulers, but there are some cases that go the other way. We conclude that considering cache effects is a good idea, but other features of the streaming pipeline are also important. |
Year | DOI | Venue |
|---|---|---|
2014 | 10.1109/HiPC.2014.7116893 | International Conference on High Performance Computing |
Field | DocType | ISSN |
Cache-oblivious algorithm,Cache invalidation,Cache pollution,Cache,Computer science,Parallel computing,Cache algorithms,Cache coloring,Bus sniffing,Smart Cache,Distributed computing | Conference | 1094-7256 |
ISBN | Citations | PageRank |
978-1-4799-5975-4 | 1 | 0.35 |
References | Authors | |
19 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Kunal Agrawal | 1 | 687 | 50.08 |
| Jordyn Maglalang | 2 | 3 | 0.72 |
| Jeremy T. Fineman | 3 | 587 | 36.10 |