PARALLEL MERGING - ALGORITHM AND IMPLEMENTATION RESULTS

被引：7

作者：

VARMAN, PJ ^{[1
]}

IYER, BR ^{[1
]}

HADERLE, DJ ^{[1
]}

DUNN, SM ^{[1
]}

机构：

[1] IBM CORP,ALMADEN RES CTR,INST DATABASE TECHNOL,SAN JOSE,CA 95120

来源：

PARALLEL COMPUTING | 1990年 / 15卷 / 1-3期

关键词：

Complexity analysis; Implementation results; Parallel merging; Shared memory multiprocessor; Sorting algorithms;

D O I：

10.1016/0167-8191(90)90040-G

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

An efficient parallel algorithm for merging two sorted lists is presented. The algorithm is based on a novel partitioning algorithm that splits the two lists among the processors, in a way that ensures load balance during the merge. The partitioning algorithm can itself be efficiently parallelized, allowing the solution to scale with increased numbers of processors. A shared memory multiprocessor is assumed. The time complexity for partitioning and merging is O(N/p + log N), where p is the number of processors and N is the total number of elements in the two lists. Implementation results on a twenty node Sequent Symmetry multiprocessor are also presented. © 1990.

引用

页码：165 / 177

页数：13

共 20 条

[11] AN EFFICIENT PARALLEL SORTING ALGORITHM FOR SHARED MEMORY MULTIPROCESSORS
WHEAT, M
EVANS, DJ
PARALLEL COMPUTING, 1992, 18 (01) : 91 - 102
[12] THE IMPLEMENTATION OF THE EXPLICIT BLOCK ITERATIVE METHODS ON THE BALANCE 8000 PARALLEL COMPUTER
EVANS, DJ
YOUSIF, WS
PARALLEL COMPUTING, 1990, 16 (01) : 81 - 97
[13] A PARALLEL ALGORITHM FOR FINDING A MAXIMUM WEIGHT CLIQUE OF AN INTERVAL GRAPH
SHYU, CH
PARALLEL COMPUTING, 1990, 13 (02) : 253 - 256
[14] A PARALLEL ALGORITHM FOR THE KNAPSACK-PROBLEM USING A GENERATION AND SEARCHING TECHNIQUE
CHANG, HKC
CHEN, JJR
SHYU, SJ
PARALLEL COMPUTING, 1994, 20 (02) : 233 - 243
[15] A Parallel Algorithm for Wavelet Transform-Based Color Image Compression
Singh, Piyush Kumar
Singh, Ravi Shankar
Rai, Kabindra Nath
JOURNAL OF INTELLIGENT SYSTEMS, 2018, 27 (01) : 81 - 90
[16] Complexity Analysis of the Parallel Memetic Algorithm for the Pickup and Delivery Problem with Time Windows
Blocho, Miroslaw
Nalepa, Jakub
MAN-MACHINE INTERACTIONS 5, ICMMI 2017, 2018, 659 : 471 - 480
[17] A PARALLEL ALGORITHM FOR DETERMINING ALL EIGENVALUES OF LARGE REAL SYMMETRICAL TRIDIAGONAL MATRICES
BASERMANN, A
WEIDNER, P
PARALLEL COMPUTING, 1992, 18 (10) : 1129 - 1141
[18] AN OPTIMAL PARALLEL ALGORITHM FOR SPARSE-MATRIX BANDWIDTH REDUCTION ON A LINEAR-ARRAY
PRASAD, ID
PATNAIK, LM
MURTHY, ISN
INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS, 1992, 42 (1-2) : 7 - 20
[19] Fast Parallel Montgomery Binary Exponentiation Algorithm Using Canonical-Signed-Digit Recoding Technique
Wu, Chia-Long
ALGORITHMS AND ARCHITECTURES FOR PARALLEL PROCESSING, PROCEEDINGS, 2009, 5574 : 428 - 438
[20] DNS of hydrodynamically interacting droplets in turbulent clouds: Parallel implementation and scalability analysis using 2D domain decomposition
Ayala, Orlando
Parishani, Hossein
Chen, Liu
Rosa, Bogdan
Wang, Lian-Ping
COMPUTER PHYSICS COMMUNICATIONS, 2014, 185 (12) : 3269 - 3290

← 1 2 →