Differences

This shows you the differences between two versions of the page.

--- melange:papers:fall2021 [2021/09/13 20:15]
corentin
+++ melange:papers:fall2021 [2021/10/05 13:05]
corentin add Efficient Execution of Dynamic Programming Algorithms on Apache Spark
@@ Line 43: / Line 43: @@
   booktitle = {Proceedings of the 27th International Conference on Parallel Architectures and Compilation Techniques},
   loc       = {Proceedings of the 27th International Conference on Parallel Architectures and Compilation Techniques},
-  number    = {2018}
+  number    = {2018},
   articleno = {10},
   numpages  = {13},
@@ Line 49: / Line 49: @@
   location  = {Limassol, Cyprus},
   series    = {PACT '18}
+}
+@misc{blleloch2019improved,
+  title         = {Improved Parallel Cache-Oblivious Algorithms for Dynamic Programming and Linear Algebra},
+  author        = {Guy E. Blleloch and Yan Gu},
+  year          = {2019},
+  eprint        = {1809.09330},
+  archivePrefix = {arXiv},
+  primaryClass  = {cs.DS},
+  loc           = {arXiv},
+  number        = {1809.09330},
+  url           = {https://arxiv.org/abs/1809.09330}
+}
+@inproceedings{Henry_2021,
+  title         = {Compilation of Sparse Array Programming Models},
+  author        = {Rawn Henry, Olivia Hsu, Rohan Yadav, Stephen Chou, Kunle Olukotun, Saman Amarasinghe, and Fredrik
+Kjolstad},
+  year          = {2021},
+  articleno     = {128},
+  numpages      = {29},
+  url           = {http://fredrikbk.com/publications/Sparse_Array_Programming.pdf},
+  publisher     = {Association for Computing Machinery},
+  loc           = {Proc. ACM Program. Lang. 5},
+  number        = {},
+  doi           = {10.1145/3485505}
+}
+@InProceedings{10.1007/3-540-17179-7_30,
+  author       = {Rajopadhye, Sanjay V. and Purushothaman, S. and Fujimoto, Richard M.},
+  editor       = {Nori, Kesav V.},
+  title        = {On synthesizing systolic arrays from Recurrence Equations with Linear Dependencies},
+  booktitle    = {Foundations of Software Technology and Theoretical Computer Science},
+  year         = {1986},
+  publisher    = {Springer Berlin Heidelberg},
+  address      = {Berlin, Heidelberg},
+  pages        = {488--503},
+  abstract     = {We present a technique for synthesizing systolic architectures from Recurrence Equations. A class of such equations (Recurrence Equations with Linear Dependencies) is defined and the problem of mapping such equations onto a two dimensional architecture is studied. We show that such a mapping is provided by means of a linear allocation and timing function. An important result is that under such a mapping the dependencies remain linear. After obtaining a two-dimensional architecture by applying such a mapping, a systolic array can be derived if the communication can be spatially and temporally localized. We show that a simple test consisting of finding the zeroes of a matrix is sufficient to determine whether this localization can be achieved by pipelining and give a construction that generates the array when such a pipelining is possible. The technique is illustrated by automatically deriving a well known systolic array for factoring a band matrix into lower and upper triangular factors.},
+  isbn         = {978-3-540-47239-1},
+  loc          = {Foundations of Software Technology and Theoretical Computer Science},
+  number       = {},
+  doi          = {10.1007/3-540-17179-7_30},
+  url          = {https://link.springer.com/chapter/10.1007/3-540-17179-7_30}
+}
+@INPROCEEDINGS{145447,
+  author       = {Mauras, C. and Quinton, P. and Rajopadhye, S. and Saouter, Y.},
+  booktitle    = {[1990] Proceedings of the International Conference on Application Specific Array Processors},
+  title        = {Scheduling affine parameterized recurrences by means of Variable Dependent Timing Functions},
+  year         = {1990},
+  volume       = {},
+  number       = {},
+  pages        = {100-110},
+  abstract     = {The authors present new scheduling techniques for systems of affine recurrence equations. They show that it is possible to extend earlier results on affine scheduling to the case when each variable of the system is scheduled independently of the others by an affine timing-function. This new technique makes it possible to analyze systems of recurrence equations with variables in different index spaces, and multi-step systolic algorithms. This theory applies directly to many problems, such as dynamic programming, LU decomposition, and 2-D convolution, and it avoids in particular preliminary heuristic rewriting of the equations.},
+  keywords     = {},
+  doi          = {10.1109/ASAP.1990.145447},
+  ISSN         = {},
+  month        = {Sep.},
+  loc          = {[1990] Proceedings of the International Conference on Application Specific Array Processors},
+  url          = {https://ieeexplore.ieee.org/document/145447?arnumber=145447}
+}
+@InProceedings{9229617,
+  author       = {Mahdi Javanmard, Mohammad and Ahmad, Zafar and Zola, Jaroslaw and Pouchet, Louis-Noël and Chowdhury, Rezaul and Harrison, Robert},
+  booktitle    = {2020 IEEE International Conference on Cluster Computing (CLUSTER)},
+  title        = {Efficient Execution of Dynamic Programming Algorithms on Apache Spark},
+  year         = {2020},
+  volume       = {},
+  number       = {},
+  pages        = {337-348},
+  doi          = {10.1109/CLUSTER49012.2020.00044},
+  loc          = {[2020] IEEE International Conference on Cluster Computing (CLUSTER)},
+  url          = {https://par.nsf.gov/servlets/purl/10224953}
 }

AlphaZ

User Tools

Site Tools

Differences

Page Tools