Zagazig University Digital Repository
Home
Thesis & Publications
All Contents
Publications
Thesis
Graduation Projects
Research Area
Research Area Reports
Search by Research Area
Universities Thesis
ACADEMIC Links
ACADEMIC RESEARCH
Zagazig University Authors
Africa Research Statistics
Google Scholar
Research Gate
Researcher ID
CrossRef
A Time-space Efficient Algorithm for Parallel k-way In-place Merging based on Sequence Partitioning and Perfect Shuffle
Faculty
Computer Science
Year:
2020
Type of Publication:
ZU Hosted
Pages:
Authors:
Ahmed Salah Mohamed Mostafa
Staff Zu Site
Abstract In Staff Site
Journal:
ACM Transactions on Parallel Computing ACM
Volume:
Keywords :
, Time-space Efficient Algorithm , Parallel k-way In-place
Abstract:
The huge data volumes, big data, and the emergence of new parallel architectures lead to revisiting classic computer science topics. The motivation of the proposed work for revisiting the parallel k-way in-place merging is primarily related to the unsuitability of the current state-of-the-art parallel algorithms for multicore CPUs with shared memory. These architectures can be profitably employed to solve this problem in parallel. Recently, Intel introduced the parallel Standard Template Library (STL) implementation for multicore CPUs, but it has no in-place merge function with the in-place property. We propose Partition-Shuffle-merge (PS-merge) to address this problem. PS-merge includes combining sequence partitioning with the in-place perfect shuffle effect to address the k-way merge task. At first, each sequence is divided into t equal-sized partitions or ranges. Thus, each partition is spread over at most k sequences. Then, perfect shuffle is utilized as a replacement for the classic block rearrangement. Finally, range subpartitions are merged using a sequential in-place merging algorithm. To evaluate the proposed algorithm, as PS-merge produces the standard merging format, we compare this algorithm against the state-of-the-art methods, bitonic merge, a parallel binary merge tree, and lazy-merge. PS-merge shows a significant improvement in overall execution time.
Author Related Publications
Ahmed Salah Mohamed Mostafa, "Artificial Intelligence and Machine Learning-Driven Decision-Making", Hindawi, 2021
More
Ahmed Salah Mohamed Mostafa, "Usages of Spark Framework with Different Machine Learning Algorithms", Hindawi, 2021
More
Ahmed Salah Mohamed Mostafa, "Efficient index-independent approaches for the collective spatial keyword queries", elsevier, 2021
More
Ahmed Salah Mohamed Mostafa, "A robust UWSN handover prediction system using ensemble learning", MDPI, 2021
More
Ahmed Salah Mohamed Mostafa, "Price Prediction of Seasonal Items Using Machine Learning and Statistical Methods", Tech Science Press, 2021
More
Department Related Publications
Ahmed Salah Mohamed Mostafa, "An Adaptive Jellyfish Search Algorithm for Packing Items with Conflict", MDPI, 2023
More
Wael Said AbdelMageed Mohamed, "IoT Security based on Iris Verification Using Multi-Algorithm Feature Level Fusion Scheme", IEEE, 2019
More
Amr Mohammed Abdel Latif Emam, "An Implementation of a Fast Threaded Nondeterministic LL (*) Parser Generator", International Journal of Computer Applications, 2015
More
Wael Said AbdelMageed Mohamed, "LBTMA: An integrated P4-enabled framework for optimized traffic management in SD-IoT networks", ELSEVIER, 2024
More
Wael Said AbdelMageed Mohamed, "MC-LBTO: secure and resilient state-aware multi-controller framework with adaptive load balancing for SD-IoT performance optimization", Springer Nature, 2025
More
جامعة المنصورة
جامعة الاسكندرية
جامعة القاهرة
جامعة سوهاج
جامعة الفيوم
جامعة بنها
جامعة دمياط
جامعة بورسعيد
جامعة حلوان
جامعة السويس
شراقوة
جامعة المنيا
جامعة دمنهور
جامعة المنوفية
جامعة أسوان
جامعة جنوب الوادى
جامعة قناة السويس
جامعة عين شمس
جامعة أسيوط
جامعة كفر الشيخ
جامعة السادات
جامعة طنطا
جامعة بنى سويف