Selection on k-dimensional meshes with multiple broadcasting

Yi Pan, Mounir Hamdi, Gurdip Singh

Research output: Contribution to journalArticle

Abstract

Randomized selection algorithms on k-dimensional mesh-connected computers with multiple broadcasting are proposed in this paper. We first show that a leader can be elected in O(log N) time on any k-dimensional mesh-connected computers with multiple broadcasting of size N. We then show that we can find the p-th smallest element among a data set of size N in O((log N + k + N1/(k(k+1))) log N) expected time using a regular N1/k × ... × N1/k k-dimensional mesh and in O((log N + k2N1/(k2k)) log N) expected time using an irregular N(2k-1 k+1)/{k2k} × N(2k-2 k+1)/(k2k) × ... × N(k+1)/(k2k) k-dimensional mesh. This leads to a selection algorithm which runs in O((log,N)2) expected time on a regular ((log N/log log N)1/2)-dimensional mesh or on an irregular (log log N)-dimensional mesh each with N processors. To our best knowledge, this is the first polylogarithmic selection algorithm on meshes with multiple broadcasting.

Original languageEnglish (US)
Pages (from-to)x5-144
JournalComputer Journal
Volume39
Issue number2
DOIs
StatePublished - 1996
Externally publishedYes

ASJC Scopus subject areas

  • Computer Science(all)

Fingerprint Dive into the research topics of 'Selection on k-dimensional meshes with multiple broadcasting'. Together they form a unique fingerprint.

  • Cite this