ERA

Download the full-sized PDF of Using SIMD Registers and Instructions to Enable Instruction-Level Parallelism in Sorting AlgorithmsDownload the full-sized PDF

Analytics

Share

Permanent link (DOI): https://doi.org/10.7939/R3GB2D

Download

Export to: EndNote  |  Zotero  |  Mendeley

Communities

This file is in the following communities:

Computing Science, Department of

Collections

This file is in the following collections:

Technical Reports (Computing Science)

Using SIMD Registers and Instructions to Enable Instruction-Level Parallelism in Sorting Algorithms Open Access

Descriptions

Author or creator
Furtak, Timothy
Amaral, Nelson
Niewiadomski, Robert
Additional contributors
Subject/Keyword
Sorting networks
Vectorization
Sorting
Instruction-level parallelism
Quicksort
d-Heaps
SIMD
SSE
Type of item
Computing Science Technical Report
Computing science technical report ID
TR07-02
Language
English
Place
Time
Description
Technical report TR07-02. Most contemporary processors offer some version of Single Instruction Multiple Data (SIMD) machinery -- vector registers and instructions to manipulate data stored in such registers. The central idea of this paper is to use these SIMD resources to improve the performance of the tail of recursive sorting algorithms. When a recursive computation reaches a set threshold, data is loaded into the vector registers, manipulated in-register, and the result stored back to memory. Four implementations of sorting with two different SIMD machinery -- x86-64's SSE2 and G5's AltiVec -- demonstrate that this idea delivers significant performance improvement. The improvements provided by the tail optimization of sorting are orthogonal to the gains obtained through empirical search for a suitable sorting algorithm. When integrated with the Dynamically Tuned Sorting Library (DTSL), this new code generation strategy improves the performance of DTSL by up to 18%. Performance of d-heaps is similarly improved by up to 35%.
Date created
2007
DOI
doi:10.7939/R3GB2D
License information
Creative Commons Attribution 3.0 Unported
Rights

Citation for previous publication

Source
Link to related item

File Details

Date Uploaded
Date Modified
2014-04-24T23:50:10.388+00:00
Audit Status
Audits have not yet been run on this file.
Characterization
File format: pdf (Portable Document Format)
Mime type: application/pdf
File size: 161897
Last modified: 2015:10:12 13:34:12-06:00
Filename: TR07-02.pdf
Original checksum: d4b043f803b9c4146a55321a359d8153
Well formed: true
Valid: true
Page count: 20
Activity of users you follow
User Activity Date