Title :
Sublogarithmic deterministic selection on arrays with a reconfigurable optical bus
Author :
Han, Yijie ; Pan, Yi ; Shen, Hong
Author_Institution :
Electron. Data Syst. Corp., Troy, MI, USA
fDate :
6/1/2002 12:00:00 AM
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((loglogN)2/ log log log N) time. To our best knowledge, this is the best deterministic selection algorithm on any model with a reconfigurable optical bus
Keywords :
computational complexity; deterministic algorithms; optical computing; optical interconnections; parallel algorithms; pipeline processing; reconfigurable architectures; system buses; LARPBS model; deterministic selection algorithm; linear array with reconfigurable pipelined bus system; parallel computational model; reconfigurable optical bus; sublogarithmic deterministic selection; Computer networks; Concurrent computing; Costs; Optical arrays; Optical computing; Optical interconnections; Optical switches; Optical waveguides; Phase change random access memory; Sorting;
Journal_Title :
Computers, IEEE Transactions on
DOI :
10.1109/TC.2002.1009153