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

研究成果: Article › 同行評審

15 引文斯高帕斯（Scopus）

摘要

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.

原文	English
頁（從 - 到）	702-707
頁數	6
期刊	IEEE Transactions on Computers
卷	51
發行號	6
DOIs	https://doi.org/10.1109/TC.2002.1009153
出版狀態	Published - 6月 2002
對外發佈	是

存取文件

10.1109/TC.2002.1009153

其它文件與鏈接

Link to publication in Scopus

引用此

@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 - https://www.scopus.com/pages/publications/0036603175

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

摘要

存取文件

其它文件與鏈接

指紋

引用此