NDLI: Parallel Optimization Strategy of Heap Sort Algorithm under Multi-core Environment

Content Provider	IEEE Xplore Digital Library
Author	Wei Zhenhua Liu Zhifeng Li Guoliang
Copyright Year	2015
Description	Author affiliation: Eng. Res. Center of Nucl. Technol. Applic., East China Inst. of Technol., Nanchang, China (Wei Zhenhua; Liu Zhifeng; Li Guoliang)
Abstract	With the popularity of multi-core and many-core platform, multi-core-oriented parallel programming and optimization has become a research hotspot in computer field. However, the vast majority of programmers are still continuing the traditional serial programming habits. Meanwhile, the mainstream algorithms are still in serial. Therefore, how to parallelize the serial programs effectively and write the multi-core programs efficiently is becoming an urgent problem in the field of multi-core programming. In this paper, the optimization of the heap sort algorithm has been achieved adopting the parallel technology based on openMP. Firstly, based on the hypercube model, the heap data to be sorted are divided into n (n is the computer thread amount) blocks called sub-heap which will be sorted respectively. Thus, the scale of the problem is decomposed into 1/n, secondly, the sorted sub-heaps will be merged using merge sort algorithm, finally, the parallel optimized heap sort algorithm is compared to the traditional heap sort algorithm. When the data quantity comes up to ten million bytes, the execution efficiency of the optimized parallel heap sort algorithm of this paper is improved significantly compared with the traditional serial heap sort algorithm on the experimental computer. Furthermore, the efficiency gap between the two algorithms will be intensified prominently with the increasing data quantity.
Sponsorship	Hunan Inst. Ind.
Starting Page	768
Ending Page	771
File Size	750750
Page Count	4
File Format	PDF
e-ISBN	9781467371438
DOI	10.1109/ICMTMA.2015.190
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2015-06-13
Publisher Place	China
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Algorithm design and analysis Computers Computational modeling Instruction sets OpenMP Multi-core Hypercube Model Hypercubes Parallel Optimization Heap Sort Algorithm Optimization 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