An efficient parallel algorithm for all pairs examination
Kevin B. Theobald, Guang R. Gao · 1991
ing with credit is permitted. To copy otherwise, to republish, to post on servers, or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from Publications Dept., ACM Inc., fax +1 (212) 869-0481, or ([email protected]). An Efficient Parallel Algorithm for All Pairs Examination Kevin B. Theobald Guang R. Gao School of Computer Science School of Computer Science McGill University McGill University Montr'eal, Qu'ebec H3A 2A7 Montr'eal, Qu'ebec H3A 2A7 [email protected] [email protected] Abstract This paper presents a parallel algorithm for the All Pairs Examination problem, which appears in many applications. This algorithm examines all pairs in a set of n 2 elements on n processors in n+1 computation steps. Each element resides in only one processor during each step. This method uses processor time optimally and requires fewer communication steps than previous algorithms, with minimal network traffic and low run-time overhead. The most ...