Title | ||
---|---|---|
POSTER: STAR (Space-Time Adaptive and Reductive) Algorithms for Real-World Space-Time Optimality. |
Abstract | ||
---|---|---|
It's important to hit a space-time balance for a real-world algorithm to achieve high performance on modern shared-memory multi-core or many-core systems. However, a large class of dynamic programs with more than $O(1)$ dependency achieve optimality either in space or time, but not both. In the literature, the problem is known as the fundamental space-time tradeoff. By exploiting properly on the runtime system, we show that our STAR (Space-Time Adaptive and Reductive) technique can help these dynamic programs to achieve sublinear parallel time bounds while still maintaining work-, space-, and cache-optimality in a processor- and cache-oblivious fashion. |
Year | DOI | Venue |
---|---|---|
2017 | 10.1145/3018743.3019029 | PPOPP |
Keywords | Field | DocType |
space-time balance,cache-oblivious algorithm,dynamic program,shared-memory multicore system | Sublinear function,Space time,Cache-oblivious algorithm,Computer science,Parallel computing,Algorithm,Theoretical computer science,Runtime system,Distributed computing | Conference |
Volume | Issue | ISSN |
52 | 8 | 0362-1340 |
Citations | PageRank | References |
0 | 0.34 | 3 |
Authors | ||
2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Yuan Tang | 1 | 32 | 5.87 |
Ronghui You | 2 | 45 | 4.95 |