×

Parallel ‘go with the winners’ algorithms in distributed memory models. (English) Zbl 1053.68124

Summary: We parallelize the ‘go with the winners’ algorithm of D. Aldous and U. Vazirani [in: Proceedings of the 35th IEEE Symposium on the Foundations of Computer Science, IEEE Computer Society Press, Silver Spring., MD, 492–501 (1994)] and analyze the resulting parallel algorithm in the LogP-model. The main issues in the analysis are load imbalances and communication delays. The result of the analysis is a practical algorithm which, under reasonable assumptions, achieves linear speedup. Finally, we analyze our algorithm for a concrete application: generating models of amorphous chemical structures.

MSC:

68W10 Parallel algorithms in computer science
68M20 Performance evaluation, queueing, and scheduling in the context of computer systems
PDFBibTeX XMLCite
Full Text: DOI