NDLI: Analyzing and enhancing the parallel sort operation on multithreaded architectures

Content Provider	Springer Nature Link
Author	Rashid, Layali Hassanein, Wessam M. Hammad, Moustafa A.
Copyright Year	2009
Abstract	The sort operation is a core part of many critical applications (e.g., database management systems). Despite the large efforts to parallelize it, the fact that it suffers from high data-dependencies vastly limits its performance. Multithreaded architectures are emerging as the most demanding technology in leading-edge processors. These architectures include simultaneous multithreading, chip multiprocessors, and machines combining different multithreading technologies. In this paper, we analyze the memory behavior and improve the performance of the most recent parallel radix and quick integer sort algorithms on modern multithreaded architectures. We achieve speedups up to 4.69× for radix sort and up to 4.17× for quicksort on a machine with 4 multithreaded processors compared to single threaded versions, respectively. We find that since radix sort is CPU-intensive, it exhibits better results on chip multiprocessors where multiple CPUs are available. While quicksort is accomplishing speedups on all types of multithreading processers due to its ability to overlap memory miss latencies with other useful processing.
Starting Page	293
Ending Page	312
Page Count	20
File Format	PDF
ISSN	09208542
Journal	The Journal of Supercomputing
Volume Number	53
Issue Number	2
e-ISSN	15730484
Language	English
Publisher	Springer US
Publisher Date	2009-04-28
Publisher Place	Boston
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Multithreading Internal database Simultaneous multithreading Chip multiprocessor Database operations Sorts Quicksort Radix sort Computer Science Processor Architectures Programming Languages, Compilers, Interpreters
Content Type	Text
Resource Type	Article
Subject	Theoretical Computer Science Information Systems Hardware and Architecture Software

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

Performance assessment of multithreaded quicksort algorithm on simultaneous multithreaded architecture

High-performance sorting algorithms for the CRAY T3D parallel computer

A continuation-based noninterruptible multithreading processor architecture

Reliability aware throughput management of chip multi-processor architecture via thread migration

Parallel Partition and Merge QuickSort (PPMQSort) on Multicore CPUs

Parallel Programming and Compilers

Multithreaded computing in evolutionary design and in artificial life simulations

On Exploiting Heterogeneity for Cluster Based Parallel Multithreading Using Task Duplication

SCMP: A Single-Chip Message-Passing Parallel Computer

Analyzing and enhancing the parallel sort operation on multithreaded architectures

Similar Documents

Performance assessment of multithreaded quicksort algorithm on simultaneous multithreaded architecture

High-performance sorting algorithms for the CRAY T3D parallel computer

A continuation-based noninterruptible multithreading processor architecture

Reliability aware throughput management of chip multi-processor architecture via thread migration

Parallel Partition and Merge QuickSort (PPMQSort) on Multicore CPUs

Parallel Programming and Compilers

Multithreaded computing in evolutionary design and in artificial life simulations

On Exploiting Heterogeneity for Cluster Based Parallel Multithreading Using Task Duplication

SCMP: A Single-Chip Message-Passing Parallel Computer

Analyzing and enhancing the parallel sort operation on multithreaded architectures