Parallel String Sample Sort

详细信息    查看全文

• 作者：Timo Bingmann (18)
  Peter Sanders (18)
  
• 刊名：Lecture Notes in Computer Science
• 出版年：2013
• 出版时间：2013
• 年：2013
• 卷：8125
• 期：1
• 页码：181-192
• 全文大小：220KB
• 参考文献：1. Akiba, T.: Parallel string radix sort in C++ (2011), http://github.com/iwiwi/parallel-string-radix-sort (git repository accessed November 2012)
  2. Bentley, J.L., Sedgewick, R.: Fast algorithms for sorting and searching strings. In: ACM 8th Symposium on Discrete Algorithms, pp. 360鈥?69 (1997)
  3. Bingmann, T., Sanders, P.: Parallel string sample sort. Tech. rep. (May 2013), see ArXiv e-print arXiv:1305.1157
  4. Blelloch, G.E., Leiserson, C.E., Maggs, B.M., Plaxton, C.G., Smith, S.J., Zagha, M.: A comparison of sorting algorithms for the connection machine CM-2. In: 3rd Symposium on Parallel Algorithms and Architectures. pp. 3鈥?6 (1991)
  5. Hagerup, T.: Optimal parallel string algorithms: sorting, merging and computing the minimum. In: Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, STOC 1994, pp. 382鈥?91. ACM, New York (1994) CrossRef
  6. Kn枚pfle, S.D.: String samplesort, bachelor Thesis, Karlsruhe Institute of Technology (November 2012) (in German)
  7. K盲rkk盲inen, J., Rantala, T.: Engineering radix sort for strings. In: Amir, A., Turpin, A., Moffat, A. (eds.) SPIRE 2008. LNCS, vol.聽5280, pp. 3鈥?4. Springer, Heidelberg (2008) CrossRef
  8. McIlroy, P.M., Bostic, K., McIlroy, M.D.: Engineering radix sort. Computing Systems聽6(1), 5鈥?7 (1993)
  9. Mehlhorn, K., Sanders, P.: Scanning multiple sequences via cache memory. Algorithmica聽35(1), 75鈥?3 (2003) CrossRef
  10. Ng, W., Kakehi, K.: Cache efficient radix sort for string sorting. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences E90-A(2), 457鈥?66 (2007)
  11. Ng, W., Kakehi, K.: Merging string sequences by longest common prefixes. IPSJ Digital Courier聽4, 69鈥?8 (2008) CrossRef
  12. Rantala, T.: Library of string sorting algorithms in C++ (2007), http://github.com/rantala/string-sorting (git repository accessed November 2012)
  13. Sanders, P., Winkel, S.: Super scalar sample sort. In: Albers, S., Radzik, T. (eds.) ESA 2004. LNCS, vol.聽3221, pp. 784鈥?96. Springer, Heidelberg (2004) CrossRef
  14. Shamsundar, N.: A fast, stable implementation of mergesort for sorting text files (May 2009), http://code.google.com/p/lcp-merge-string-sort (source downloaded November 2012)
  15. Sinha, R., Wirth, A.: Engineering Burstsort: Toward fast in-place string sorting. J. Exp. Algorithmics聽15(2.5), 1鈥?4 (2010)
  16. Sinha, R., Zobel, J.: Cache-conscious sorting of large sets of strings with dynamic tries. J. Exp. Algorithmics聽9(1.5), 1鈥?1 (2004)
  17. Sinha, R., Zobel, J., Ring, D.: Cache-efficient string sorting using copying. J. Exp. Algorithmics聽11(1.2), 1鈥?2 (2007)
  18. Tsigas, P., Zhang, Y.: A simple, fast parallel implementation of quicksort and its performance evaluation on SUN enterprise 10000. In: PDP, pp. 372鈥?81. IEEE Computer Society (2003)
  19. Wassenberg, J., Sanders, P.: Engineering a multi-core radix sort. In: Jeannot, E., Namyst, R., Roman, J. (eds.) Euro-Par 2011, Part II. LNCS, vol.聽6853, pp. 160鈥?69. Springer, Heidelberg (2011) CrossRef
  
• 作者单位：Timo Bingmann (18)
  Peter Sanders (18)
  
  18. Karlsruhe Institute of Technology, Karlsruhe, Germany
  

文摘

We discuss how string sorting algorithms can be parallelized on modern multi-core shared memory machines. As a synthesis of the best sequential string sorting algorithms and successful parallel sorting algorithms for atomic objects, we propose string sample sort. The algorithm makes effective use of the memory hierarchy, uses additional word level parallelism, and largely avoids branch mispredictions. Additionally, we parallelize variants of multikey quicksort and radix sort that are also useful in certain situations.