PUMA publications for /user/seboettg/kdesems2013https://puma.uni-kassel.de/user/seboettg/kdesems2013PUMA RSS feed for /user/seboettg/kdesems20132024-03-29T10:14:32+01:00The Spreadsort High-performance General-case Sorting Algorithmhttps://puma.uni-kassel.de/bibtex/273dffc3dfca4ab655c7eb58521b97c52/seboettgseboettg2013-07-14T14:45:40+02:00kdesems2013 seminar sorting spreadsort <span class="authorEditorList"><span itemtype="http://schema.org/Person" itemscope="itemscope" itemprop="author"><a title="Steven J. Ross" itemprop="url" href="/author/Steven%20J.%20Ross"><span itemprop="name">S. Ross</span></a></span>. </span><span itemtype="http://schema.org/Book" itemscope="itemscope" itemprop="isPartOf"><em><span itemprop="name">Proceedings of the International Conference on Parallel and Distributed Processing Techniques and Applications - Volume 3</span>, </em></span><em>Seite <span itemprop="pagination">1100--1106</span>. </em><em><span itemprop="publisher">CSREA Press</span>, </em>(<em><span>2002<meta content="2002" itemprop="datePublished"/></span></em>)Sun Jul 14 14:45:40 CEST 2013Proceedings of the International Conference on Parallel and Distributed Processing Techniques and Applications - Volume 31100--1106PDPTA '02The Spreadsort High-performance General-case Sorting Algorithm2002kdesems2013 seminar sorting spreadsort The Spreadsort High-performance General-case Sorting AlgorithmFast parallel GPU-sorting using a hybrid algorithmhttps://puma.uni-kassel.de/bibtex/20b72bee3ea941e13dec3f706c0f4362b/seboettgseboettg2013-07-14T14:32:32+02:00kdesems2013 seminar sorting <span class="authorEditorList"><span itemtype="http://schema.org/Person" itemscope="itemscope" itemprop="author"><a title="Erik Sintorn" itemprop="url" href="/author/Erik%20Sintorn"><span itemprop="name">E. Sintorn</span></a></span>, und <span itemtype="http://schema.org/Person" itemscope="itemscope" itemprop="author"><a title="Ulf Assarsson" itemprop="url" href="/author/Ulf%20Assarsson"><span itemprop="name">U. Assarsson</span></a></span>. </span><span itemtype="http://schema.org/PublicationIssue" itemscope="itemscope" itemprop="isPartOf"><span itemtype="http://schema.org/Periodical" itemscope="itemscope" itemprop="isPartOf"><span itemprop="name"><em>Journal of Parallel and Distributed Computing</em></span></span> <em><span itemtype="http://schema.org/PublicationVolume" itemscope="itemscope" itemprop="isPartOf"><span itemprop="volumeNumber">68 </span></span>(<span itemprop="issueNumber">10</span>):
<span itemprop="pagination">1381 - 1388</span></em> </span>(<em><span>2008<meta content="2008" itemprop="datePublished"/></span></em>)<em>General-Purpose Processing using Graphics Processing Units.</em>Sun Jul 14 14:32:32 CEST 2013Journal of Parallel and Distributed Computing General-Purpose Processing using Graphics Processing Units 101381 - 1388Fast parallel GPU-sorting using a hybrid algorithm 682008kdesems2013 seminar sorting This paper presents an algorithm for fast sorting of large lists using modern GPUs. The method achieves high speed by efficiently utilizing the parallelism of the \{GPU\} throughout the whole algorithm. Initially, GPU-based bucketsort or quicksort splits the list into enough sublists then to be sorted in parallel using merge-sort. The algorithm is of complexity n log n , and for lists of 8 M elements and using a single Geforce 8800 GTS-512, it is 2.5 times as fast as the bitonic sort algorithms, with standard complexity of n ( log n ) 2 , which for a long time was considered to be the fastest for \{GPU\} sorting. It is 6 times faster than single \{CPU\} quicksort, and 10% faster than the recent GPU-based radix sort. Finally, the algorithm is further parallelized to utilize two graphics cards, resulting in yet another 1.8 times speedup. Fast parallel GPU-sorting using a hybrid algorithmVergleich von Sortierverfahrenhttps://puma.uni-kassel.de/bibtex/2c49c9ef4dc754980aa36760133790f69/seboettgseboettg2013-06-17T22:13:17+02:00kdesems2013 mergesort myown quicksort radixsort seminar sortieralgorithmen sortiertverfahren sorting <span class="authorEditorList"><span itemtype="http://schema.org/Person" itemscope="itemscope" itemprop="author"><a title="Sebastian Böttger" itemprop="url" href="/author/Sebastian%20B%c3%b6ttger"><span itemprop="name">S. Böttger</span></a></span>. </span><span itemtype="http://schema.org/PublicationIssue" itemscope="itemscope" itemprop="isPartOf"> </span>(<em><span>2013<meta content="2013" itemprop="datePublished"/></span></em>)Mon Jun 17 22:13:17 CEST 2013Vergleich von Sortierverfahren2013kdesems2013 mergesort myown quicksort radixsort seminar sortieralgorithmen sortiertverfahren sorting Gegenstand dieser Arbeit ist der Vergleich der Sortierverfahren Radixsort, Mergesort und Quicksort. Alle drei Algorithmen werden zunächst ausführlich vorgestellt und ihre Funktionsweise erläutert. Dabei wird die Komplexität und das resultierende Laufzeitverhalten theoretisch betrachtet und die daraus entstehenden Vor- und Nachteile diskutiert. In einem Versuch werden zudem alle drei Algorithmen unter realen Bedingungen auf einem Computer getestet, um die theoretischen Betrachtungen zu untermauern.Von Neumann's First Computer Programhttps://puma.uni-kassel.de/bibtex/26272bbad8db11ff6524cff4572ffca31/seboettgseboettg2013-06-17T17:04:24+02:00kdesems2013 seminar sorting <span class="authorEditorList"><span itemtype="http://schema.org/Person" itemscope="itemscope" itemprop="author"><a title="Donald E. Knuth" itemprop="url" href="/author/Donald%20E.%20Knuth"><span itemprop="name">D. Knuth</span></a></span>. </span><span itemtype="http://schema.org/PublicationIssue" itemscope="itemscope" itemprop="isPartOf"><span itemtype="http://schema.org/Periodical" itemscope="itemscope" itemprop="isPartOf"><span itemprop="name"><em>ACM Comput. Surv.</em></span></span> <em><span itemtype="http://schema.org/PublicationVolume" itemscope="itemscope" itemprop="isPartOf"><span itemprop="volumeNumber">2 </span></span>(<span itemprop="issueNumber">4</span>):
<span itemprop="pagination">247--260</span></em> </span>(<em><span>Dezember 1970<meta content="Dezember 1970" itemprop="datePublished"/></span></em>)Mon Jun 17 17:04:24 CEST 2013New York, NY, USAACM Comput. Surv.dec4247--260Von Neumann's First Computer Program21970kdesems2013 seminar sorting Von Neumann's First Computer ProgramImplementing Quicksort programshttps://puma.uni-kassel.de/bibtex/2afad926399892172416b18c7a996f647/seboettgseboettg2013-06-17T16:58:13+02:00kdesems2013 quicksort seminar sorting <span class="authorEditorList"><span itemtype="http://schema.org/Person" itemscope="itemscope" itemprop="author"><a title="Robert Sedgewick" itemprop="url" href="/author/Robert%20Sedgewick"><span itemprop="name">R. Sedgewick</span></a></span>. </span><span itemtype="http://schema.org/PublicationIssue" itemscope="itemscope" itemprop="isPartOf"><span itemtype="http://schema.org/Periodical" itemscope="itemscope" itemprop="isPartOf"><span itemprop="name"><em>Commun. ACM</em></span></span> <em><span itemtype="http://schema.org/PublicationVolume" itemscope="itemscope" itemprop="isPartOf"><span itemprop="volumeNumber">21 </span></span>(<span itemprop="issueNumber">10</span>):
<span itemprop="pagination">847--857</span></em> </span>(<em><span>Oktober 1978<meta content="Oktober 1978" itemprop="datePublished"/></span></em>)Mon Jun 17 16:58:13 CEST 2013New York, NY, USACommun. ACMoct10847--857Implementing Quicksort programs211978kdesems2013 quicksort seminar sorting This paper is a practical study of how to implement the Quicksort sorting algorithm and its best variants on real computers, including how to apply various code optimization techniques. A detailed implementation combining the most effective improvements to Quicksort is given, along with a discussion of how to implement it in assembly language. Analytic results describing the performance of the programs are summarized. A variety of special situations are considered from a practical standpoint to illustrate Quicksort's wide applicability as an internal sorting method which requires negligible extra storage.Implementing Quicksort programsGPUTeraSort: high performance graphics co-processor sorting for large database managementhttps://puma.uni-kassel.de/bibtex/2f586cfc6ac72dc364dbbeeff585ca05c/seboettgseboettg2013-06-14T21:36:45+02:00databases gpu gpu-terasort graphics_procesor kdesems2013 seminar sorting <span class="authorEditorList"><span itemtype="http://schema.org/Person" itemscope="itemscope" itemprop="author"><a title="Naga Govindaraju" itemprop="url" href="/author/Naga%20Govindaraju"><span itemprop="name">N. Govindaraju</span></a></span>, <span itemtype="http://schema.org/Person" itemscope="itemscope" itemprop="author"><a title="Jim Gray" itemprop="url" href="/author/Jim%20Gray"><span itemprop="name">J. Gray</span></a></span>, <span itemtype="http://schema.org/Person" itemscope="itemscope" itemprop="author"><a title="Ritesh Kumar" itemprop="url" href="/author/Ritesh%20Kumar"><span itemprop="name">R. Kumar</span></a></span>, und <span itemtype="http://schema.org/Person" itemscope="itemscope" itemprop="author"><a title="Dinesh Manocha" itemprop="url" href="/author/Dinesh%20Manocha"><span itemprop="name">D. Manocha</span></a></span>. </span><span itemtype="http://schema.org/Book" itemscope="itemscope" itemprop="isPartOf"><em><span itemprop="name">Proceedings of the 2006 ACM SIGMOD international conference on Management of data</span>, </em></span><em>Seite <span itemprop="pagination">325--336</span>. </em><em>New York, NY, USA, </em><em><span itemprop="publisher">ACM</span>, </em>(<em><span>2006<meta content="2006" itemprop="datePublished"/></span></em>)Fri Jun 14 21:36:45 CEST 2013New York, NY, USAProceedings of the 2006 ACM SIGMOD international conference on Management of data325--336SIGMOD '06GPUTeraSort: high performance graphics co-processor sorting for large database management2006databases gpu gpu-terasort graphics_procesor kdesems2013 seminar sorting We present a novel external sorting algorithm using graphics processors (GPUs) on large databases composed of billions of records and wide keys. Our algorithm uses the data parallelism within a GPU along with task parallelism by scheduling some of the memory-intensive and compute-intensive threads on the GPU. Our new sorting architecture provides multiple memory interfaces on the same PC -- a fast and dedicated memory interface on the GPU along with the main memory interface for CPU computations. As a result, we achieve higher memory bandwidth as compared to CPU-based algorithms running on commodity PCs. Our approach takes into account the limited communication bandwidth between the CPU and the GPU, and reduces the data communication between the two processors. Our algorithm also improves the performance of disk transfers and achieves close to peak I/O performance. We have tested the performance of our algorithm on the SortBenchmark and applied it to large databases composed of a few hundred Gigabytes of data. Our results on a 3 GHz Pentium IV PC with $300 NVIDIA 7800 GT GPU indicate a significant performance improvement over optimized CPU-based algorithms on high-end PCs with 3.6 GHz Dual Xeon processors. Our implementation is able to outperform the current high-end PennySort benchmark and results in a higher performance to price ratio. Overall, our results indicate that using a GPU as a co-processor can significantly improve the performance of sorting algorithms on large databases.GPUTeraSortSorting on Electronic Computer Systemshttps://puma.uni-kassel.de/bibtex/277f952657e1bcc2e08ec71ad9677a4ec/seboettgseboettg2013-06-14T21:08:25+02:00computer electronic kdesems2013 seminar sorting <span class="authorEditorList"><span itemtype="http://schema.org/Person" itemscope="itemscope" itemprop="author"><a title="Edward H. Friend" itemprop="url" href="/author/Edward%20H.%20Friend"><span itemprop="name">E. Friend</span></a></span>. </span><span itemtype="http://schema.org/PublicationIssue" itemscope="itemscope" itemprop="isPartOf"><span itemtype="http://schema.org/Periodical" itemscope="itemscope" itemprop="isPartOf"><span itemprop="name"><em>J. ACM</em></span></span> <em><span itemtype="http://schema.org/PublicationVolume" itemscope="itemscope" itemprop="isPartOf"><span itemprop="volumeNumber">3 </span></span>(<span itemprop="issueNumber">3</span>):
<span itemprop="pagination">134--168</span></em> </span>(<em><span>Juli 1956<meta content="Juli 1956" itemprop="datePublished"/></span></em>)Fri Jun 14 21:08:25 CEST 2013New York, NY, USAJ. ACMjul3134--168Sorting on Electronic Computer Systems31956computer electronic kdesems2013 seminar sorting