NDLI: Using SIMD registers and instructions to enable instruction-level parallelism in sorting algorithms

Please wait, while we are loading the content...

Universal augmentation schemes for network navigability: overcoming the √n-barrier

Approximation algorithms for multiprocessor scheduling under uncertainty

Feasibility study of MPI implementation on the heterogeneous multi-core cell BE™ architecture

Optimal sparse matrix dense vector multiplication in the I/O-model

Scheduling threads for constructive cache sharing on CMPs

Tight bounds for distributed selection

Packing to angles and sectors

Weakening the online adversary just enough to get optimal conflict-free colorings for intervals

The notion of a timed register and its application to indulgent synchronization

Online frequency allocation in cellular networks

Maximizing total upload in latency-sensitive P2P applications

Cilk provides the "best overall productivity" for high performance computing: (and won the HPC challenge award to prove it)

Rate vs. buffer size: greedy information gathering on the line

Sparse parallel Delaunay mesh refinement

On triangulation of simple networks

Scheduling DAGs on asynchronous processors

Evaluating synchronization techniques for light-weight multithreaded/multicore architectures

The cache-oblivious gaussian elimination paradigm: theoretical framework, parallelization and experimental evaluation

Supermatrix out-of-order scheduling of matrix operations for SMP and multi-core architectures

Local MST computation with short advice

Conflict-free coloring for rectangle ranges using $O(n^{.382})$ colors

On the truthfulness and the approximation for scheduling selfish tasks

Nonblocking transactions without indirection using alert-on-update

Energy efficient randomised communication in unknown AdHoc networks

Bi-objective scheduling algorithms for optimizing makespan and reliability on heterogeneous systems

PRAM-on-chip: first commitment to silicon

Online collaborative filtering with nearly optimal dynamic regret

Using SIMD registers and instructions to enable instruction-level parallelism in sorting algorithms

Strong-diameter decompositions of minor free graphs

Scheduling to minimize gaps and power consumption

Towards soft optimization techniques for parallel cognitive applications

Cache-oblivious streaming B-trees

Proximity-aware directory-based coherence for multi-core processor architectures

Distributed approximation of capacitated dominating sets

Balanced allocations with heterogenous bins

Optimal bit-reversal using vector permutations

Time-based transactional memory with scalable time bases

Local strategies for maintaining a chain of relay stations between an explorer and a base station

Speed scaling on parallel processors

Transactional memory and the birthday paradox

Truthful unsplittable flow for large capacity networks

A tight bound on online buffer management for two-port shared-memory switches

An experimental comparison of cache-oblivious and cache-conscious programs

A parallel dynamic programming algorithm on a multi-core architecture

Deadlock-free scheduling of X10 computations with bounded resources

On the convergence of multicast games in directed networks

Using SIMD registers and instructions to enable instruction-level parallelism in sorting algorithms

Content Provider	ACM Digital Library
Author	Amaral, José Nelson Furtak, Timothy Niewiadomski, Robert
Abstract	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 the number of elements to be sorted reaches a set threshold, data is loaded into the vector registers, manipulated in-register, and the result stored back to memory. Three implementations of sorting with two different SIMD machineries - x86-64's SSE2 and G5's AltiVec - demonstrate that this idea delivers significant speed improvements. The improvements provided are orthogonal to the gains obtained through empirical search for a suitable sorting algorithm [11]. When integrated with the Dynamically Tuned Sorting Library (DTSL) this new code generation strategy reduces the time spent by DTSL up to 22% for moderately-sized arrays, with greater relative reductions for small arrays. Wall-clock performance of d-heaps is improved by up to 39% using a similar technique.
Starting Page	348
Ending Page	357
Page Count	10
File Format	PDF
ISBN	9781595936677
DOI	10.1145/1248377.1248436
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2007-06-09
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Instruction-level parallelism Quicksort Sorting networks Simd Vectorization Sorting
Content Type	Text
Resource Type	Article

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

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

Using SIMD Registers and Instructions to Enable Instruction-Level Parallelism in Sorting Algorithms (2007)

Using SIMD registers and instructions to enable instruction-level parallelism in sorting algorithms

Retargetable code optimization with SIMD instructions

Automatic generation of custom SIMD instructions for Superword Level Parallelism

Optimizing sorting algorithms by using sorting networks

Methods to utilize SIMT and SIMD instruction level parallelism in tridiagonal solvers

Energy aware compilation for DSPs with SIMD instructions

Retargetable code optimization with SIMD instructions

Using SIMD registers and instructions to enable instruction-level parallelism in sorting algorithms

Similar Documents

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

Using SIMD Registers and Instructions to Enable Instruction-Level Parallelism in Sorting Algorithms (2007)

Using SIMD registers and instructions to enable instruction-level parallelism in sorting algorithms

Retargetable code optimization with SIMD instructions

Automatic generation of custom SIMD instructions for Superword Level Parallelism

Optimizing sorting algorithms by using sorting networks

Methods to utilize SIMT and SIMD instruction level parallelism in tridiagonal solvers

Energy aware compilation for DSPs with SIMD instructions

Retargetable code optimization with SIMD instructions

Using SIMD registers and instructions to enable instruction-level parallelism in sorting algorithms