5 papers
PACO: A Fully Cache-Oblivious Parallel FFT with One Global Redistribution
Shina Guo, Weiguo Gao, Yuan Tang
Fast Fourier transforms on parallel machines incur two forms of data movement: processor-local transfers through the memory hierarchy and global redistribution between processors.…
Balanced Partitioning of Several Cache-Oblivious Algorithms
Yuan Tang, Weiguo Gao
Frigo et al. proposed an ideal cache model and a recursive technique to design sequential cache-efficient algorithms in a cache-oblivious fashion. Ballard et al. pointed out that i…
Nested Dataflow Algorithms for Dynamic Programming Recurrences with more than O(1) Dependency
Yuan Tang
Dynamic programming problems have wide applications in real world and have been studied extensively in both serial and parallel settings. In 1994, Galil and Park developed work-eff…
Improving the Space-Time Efficiency of Processor-Oblivious Matrix Multiplication Algorithms
Yuan Tang
Classic cache-oblivious parallel matrix multiplication algorithms achieve optimality either in time or space, but not both, which promotes lots of research on the best possible bal…
Extending the Nested Parallel Model to the Nested Dataflow Model with Provably Efficient Schedulers
David Dinh, Harsha Vardhan Simhadri, Yuan Tang
The nested parallel (a.k.a. fork-join) model is widely used for writing parallel programs. However, the two composition constructs, i.e. "" (parallel) and "" (serial)…