Seminarthemen ************************************ @inproceedings{tsigas2003simple, title={A simple, fast parallel implementation of quicksort and its performance evaluation on SUN enterprise 10000}, author={Tsigas, Philippas and Zhang, Yi}, booktitle={Parallel, Distributed and Network-Based Processing, 2003. Proceedings. Eleventh Euromicro Conference on}, pages={372--381}, year={2003}, organization={IEEE} } ----------------------------------------------------------------- @inproceedings{HLHPSKS13, title={Distributed queues in shared memory: multicore performance and scalability through quantitative relaxation}, author={Haas, Andreas and Lippautz, Michael and Henzinger, Thomas A and Payer, Hannes and Sokolova, Ana and Kirsch, Christoph M and Sezgin, Ali}, booktitle={Proceedings of the ACM International Conference on Computing Frontiers}, pages={17}, year={2013}, organization={ACM} } ------------------------------------------------------ @Article{DeoPra92, author = "N. Deo and S. Prasad", title = "Parallel Heap: An Optimal Parallel Priority Queue", journal = "The Journal of Supercomputing", volume = "6", number = "1", pages = "87--98", month = mar, year = "1992", keywords = "parallel data structure, heaps, priority queue, optimal parallel algorithm, parallel random access machine, PRAM,", } @inproceedings{Wimmer:2015:LKR:2688500.2688547, author = {Wimmer, Martin and Gruber, Jakob and Tr\"{a}ff, Jesper Larsson and Tsigas, Philippas}, title = {The Lock-free k-LSM Relaxed Priority Queue}, booktitle = {Proceedings of the 20th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming}, series = {PPoPP 2015}, year = {2015}, isbn = {978-1-4503-3205-7}, location = {San Francisco, CA, USA}, pages = {277--278}, numpages = {2}, url = {http://doi.acm.org/10.1145/2688500.2688547}, doi = {10.1145/2688500.2688547}, acmid = {2688547}, publisher = {ACM}, address = {New York, NY, USA}, keywords = {Task-parallel programming, concurrent data structure relaxation, priority-queue, shared memory}, } ---------------------------------------------------------------------------- http://scholar.google.com/citations?view_op=view_citation&hl=en&user=uXUA1pgAAAAJ&citation_for_view=uXUA1pgAAAAJ:EkHepimYqZsC Title Fast shared-memory algorithms for computing the minimum spanning forest of sparse graphs Authors David A Bader, Guojing Cong Publication date 2006/11/30 Journal name Journal of Parallel and Distributed Computing Volume 66 Issue 11 Pages 1366-1378 Publisher Academic Press Description Minimum spanning tree (MST) is one of the most studied combinatorial problems with practical applications in VLSI layout, wireless communication, and distributed networks, recent problems in biology and medicine such as cancer detection, medical imaging, and proteomics, and national security and bioterrorism such as detecting the spread of toxins through populations in the case of biological/chemical warfare. Most of the previous attempts for improving the speed of MST using parallel computing are too complicated to ... -------------------------------------------------------------------------------------- * Graph500 Challenge Präsentierung und was ist der Stand der Technik http://www.graph500.org/ Traversing Trillions of Edges in Real-time: Graph Exploration on Large-Scale Parallel Machines Fabio Checconi (IBM TJ Watson Research Center, USA); Fabrizio Petrini (IBM TJ Watson Research Center, USA) IPDPS 2014 Scalable Single Source Shortest Path Algorithms for Massively Parallel Systems Venkatesan T. Chakaravarthy∗ , Fabio Checconi† , Fabrizio Petrini† , Yogish Sabharwal∗ IPDPS 2014 ---------------------------------------------------------------------------- @techreport{Satish08, author = {Nadathur Satish and Mark Harris and Michael Garland}, title = {Designing Efficient Sorting Algorithms for Manycore {GPUs}}, month = sep, year = 2008, institution = {NVIDIA Corporation}, type = {NVIDIA Technical Report}, number = {NVR-2008-001}, } -------------------------------------------------------------------------------- @article{DeanG10, author = {Jeffrey Dean and Sanjay Ghemawat}, title = {MapReduce: a flexible data processing tool}, journal = {Commun. ACM}, volume = {53}, number = {1}, year = {2010}, pages = {72--77}, ee = {http://doi.acm.org/10.1145/1629175.1629198}, bibsource = {DBLP, http://dblp.uni-trier.de} } ---------------------------------------------------- @Article{KarZha93, author = "R. M. Karp and Y. Zhang", title = "Parallel Algorithms for Backtrack Search and Branch-and-Bound", journal = jacm, year = 1993, volume = 40, number = 3, pages = "765--789", } @TechReport{Ran90, author = "A. Ranade", title = "A Simpler Analysis of the {K}arp-{Z}hang Parallel Branch-and-Bound Method", institution = "University of California Berkeley", year = 1990, annote = "Analyse von Karp/Zhangs Algorithumus verbessert (Isoeffizienzfunktion n log n) und Beweis braucht nur 3 Seiten. Deley Sequence Argument" } --------------------------------------------------------------------------------- Julian Shun and Guy Blelloch. Phase-Concurrent Hash Tables for Determinism Symposium on Parallelism in Algorithms and Architectures. ACM 2014 ---------------------------------------------------------------------- Julian Shun, Yan Gu, Guy E. Blelloch, Jeremy T. Fineman and Phillip B. Gibbons. Sequential Random Permutation, List Contraction and Tree Contraction are Highly Parallel. SODA 2015. ------------------------------------------------------------- @inproceedings{shun2014simple, title={A simple and practical linear-work parallel algorithm for connectivity}, author={Shun, Julian and Dhulipala, Laxman and Blelloch, Guy}, booktitle={Proceedings of the 26th ACM symposium on Parallelism in algorithms and architectures}, pages={143--153}, year={2014}, organization={ACM} } ------------------------------------------------------------------------------------------ Grey Ballard, James Demmel, Olga Holtz, Oded Schwartz: Communication costs of Strassen's matrix multiplication. Commun. ACM (CACM) 57(2):107-114 (2014)