Parallel Multidimensional Lookahead Sorting Algorithm

作     者：Gebali, Fayez Taher, Mohamed Zaki, Ahmed M. El-Kharashi, M. Watheq Tawfik, Ayman 

作者机构：Univ Victoria Dept Elect & Comp Engn Victoria BC V8W 3P6 Canada Ain Shams Univ Fac Engn Comp & Syst Engn Dept Cairo 11517 Egypt Ajman Univ Elect Engn Dept Ajman U Arab Emirates 

出 版 物：《IEEE ACCESS》 (IEEE Access)

年 卷 期：2019年第7卷

页      面：75446-75463页

核心收录：

主　　题：Lookahead multicore execution parallel algorithms sorting algorithms 

摘      要：This paper presents a new parallel structured lookahead multidimensional sorting algorithm. Our algorithm can be based on any sequential sorting algorithm. The amount of parallelism can be controlled using several parameters such as the number of threads, word size, memory/processor communication overhead, and the dimension of the algorithm. The proposed technique is ideally suited for general purpose graphic processing units and shared-memory massively parallel processor systems. It ensures that data being processed exhibits temporal and spatial locality to maximize the utilization of processor cache. The algorithm achieves a speedup even when a single processor is used. A lookahead algorithm is also proposed to achieve even higher speedup. The performance of the proposed algorithm is verified numerically and experimentally.