✦ LIBER ✦

Deterministic parallel selection algorithms on coarse-grained multicomputers

✍ Scribed by M. Cafaro; Vincenzo De Bene; G. Aloisio

Publisher: John Wiley and Sons
Year: 2009
Tongue: English
Weight: 351 KB
Volume: 21
Category: Article
ISSN: 1532-0626
DOI: 10.1002/cpe.1453

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

We present two deterministic parallel Selection algorithms for distributed memory machines, under the coarse‐grained multicomputer model. Both are based on the use of two weighted 3‐medians, that allows discarding at least 1/3 of the elements in each iteration. The first algorithm slightly improves the current experimentally fastest algorithm by Saukas and Song where at least 1/4 of the elements are discarded in each iteration, while the second one is a fast, special purpose algorithm working for a particular class of input, namely an input that can be sorted in linear time using RadixSort. Copyright © 2009 John Wiley & Sons, Ltd.

📜 SIMILAR VOLUMES

Coarse grained parallel algorithms for g

Coarse grained parallel algorithms for graph matching

✍ Albert Chan; Frank Dehne; Prosenjit Bose; Markus Latzel 📂 Article 📅 2008 🏛 Elsevier Science 🌐 English ⚖ 236 KB

Scalable 2D Convex Hull and Triangulatio

Scalable 2D Convex Hull and Triangulation Algorithms for Coarse Grained Multicomputers

✍ Mohamadou Diallo; Afonso Ferreira; Andrew Rau-Chaplin; Stéphane Ubéda 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 627 KB

Analysis of crossovers and selections in

Analysis of crossovers and selections in a coarse-grained parallel genetic algorithm

✍ Kengo Katayama; Hisayuki Hirabayashi; Hiroyuki Narihisa 📂 Article 📅 2003 🏛 Elsevier Science 🌐 English ⚖ 774 KB

The Keywords-parallel genetic algorithm, Parameter determination, naveling salesman problem. Parallel computer, Genetic operators. is applied successfully to problems in engineering, science, and other areas, and is able to find good solutions with reasonable amounts of computation time. However, wh

Parallel thinning algorithms on multicom

Parallel thinning algorithms on multicomputers: experimental study on load balancing

✍ Montoya, M. G. ;Gil, C. ;Garcia, I. 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 156 KB

An efficient coarse-grained parallel alg

An efficient coarse-grained parallel algorithm for global–local multiscale computations on massively parallel systems

✍ Rahul; Suvranu De 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 545 KB

Solving large FPT problems on coarse-gra

Solving large FPT problems on coarse-grained parallel machines

✍ James Cheetham; Frank Dehne; Andrew Rau-Chaplin; Ulrike Stege; Peter J. Taillon 📂 Article 📅 2003 🏛 Elsevier Science 🌐 English ⚖ 208 KB

Fixed-parameter tractability (FPT) techniques have recently been successful in solving NP-complete problem instances of practical importance which were too large to be solved with previous methods. In this paper, we show how to enhance this approach through the addition of parallelism, thereby allow