Sublogarithmic deterministic selection on arrays with a reconfigurable optical bus

Yijie Han; Yi Pan; Hong Shen

doi:10.1109/TC.2002.1009153

Sublogarithmic deterministic selection on arrays with a reconfigurable optical bus

Yijie Han, Yi Pan, Hong Shen

Research output: Contribution to journal › Article › peer-review

15 Citations (Scopus)

Abstract

The Linear Array with a Reconfigurable Pipelined Bus System (LARPBS) is a newly introduced parallel computational model, where processors are connected by a reconfigurable optical bus. In this paper, we show that the selection problem can be solved on the LARPBS model deterministically in O((log log N) ²/logloglog N) time. To our best knowledge, this is the best deterministic selection algorithm on any model with a reconfigurable optical bus.

Original language	English
Pages (from-to)	702-707
Number of pages	6
Journal	IEEE Transactions on Computers
Volume	51
Issue number	6
DOIs	https://doi.org/10.1109/TC.2002.1009153
Publication status	Published - Jun 2002
Externally published	Yes

Keywords

Analysis of algorithms
Massive parallelism
Optical bus
Parallel algorithms
Selection

Access to Document

10.1109/TC.2002.1009153

Cite this

@article{1205e02ec45a4266807343c924045b20,

title = "Sublogarithmic deterministic selection on arrays with a reconfigurable optical bus",

abstract = "The Linear Array with a Reconfigurable Pipelined Bus System (LARPBS) is a newly introduced parallel computational model, where processors are connected by a reconfigurable optical bus. In this paper, we show that the selection problem can be solved on the LARPBS model deterministically in O((log log N) 2/logloglog N) time. To our best knowledge, this is the best deterministic selection algorithm on any model with a reconfigurable optical bus.",

keywords = "Analysis of algorithms, Massive parallelism, Optical bus, Parallel algorithms, Selection",

author = "Yijie Han and Yi Pan and Hong Shen",

note = "Funding Information: This research was supported in part by the US National Science Foundation under Grants CCR-9211621, OSR-9350540, and CCR-9503882 and the Australian Research Council under its Large Grants Scheme (1996-98) A849602031 and Small Grants Scheme (1998).",

year = "2002",

month = jun,

doi = "10.1109/TC.2002.1009153",

language = "English",

volume = "51",

pages = "702--707",

journal = "IEEE Transactions on Computers",

issn = "0018-9340",

publisher = "IEEE Computer Society",

number = "6",

}

TY - JOUR

T1 - Sublogarithmic deterministic selection on arrays with a reconfigurable optical bus

AU - Han, Yijie

AU - Pan, Yi

AU - Shen, Hong

N1 - Funding Information: This research was supported in part by the US National Science Foundation under Grants CCR-9211621, OSR-9350540, and CCR-9503882 and the Australian Research Council under its Large Grants Scheme (1996-98) A849602031 and Small Grants Scheme (1998).

PY - 2002/6

Y1 - 2002/6

N2 - The Linear Array with a Reconfigurable Pipelined Bus System (LARPBS) is a newly introduced parallel computational model, where processors are connected by a reconfigurable optical bus. In this paper, we show that the selection problem can be solved on the LARPBS model deterministically in O((log log N) 2/logloglog N) time. To our best knowledge, this is the best deterministic selection algorithm on any model with a reconfigurable optical bus.

AB - The Linear Array with a Reconfigurable Pipelined Bus System (LARPBS) is a newly introduced parallel computational model, where processors are connected by a reconfigurable optical bus. In this paper, we show that the selection problem can be solved on the LARPBS model deterministically in O((log log N) 2/logloglog N) time. To our best knowledge, this is the best deterministic selection algorithm on any model with a reconfigurable optical bus.

KW - Analysis of algorithms

KW - Massive parallelism

KW - Optical bus

KW - Parallel algorithms

KW - Selection

UR - http://www.scopus.com/inward/record.url?scp=0036603175&partnerID=8YFLogxK

U2 - 10.1109/TC.2002.1009153

DO - 10.1109/TC.2002.1009153

M3 - Article

AN - SCOPUS:0036603175

SN - 0018-9340

VL - 51

SP - 702

EP - 707

JO - IEEE Transactions on Computers

JF - IEEE Transactions on Computers

IS - 6

ER -

Sublogarithmic deterministic selection on arrays with a reconfigurable optical bus

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this