loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
Eighth International Conference on Parallel and Distributed Computing, Applications and Technologies (PDCAT 2007)
Randomized Initialization on the 1-Dimensional Reconfigurable Mesh
Adelaide, Australia
December 03-December 06
ISBN: 0-7695-3049-4
The reconfigurable mesh is a processor array that consists processors arranged in 1-dimensional or 2- dimensional grids with a reconfigurable bus system. The main contribution of this paper is to show initialization al- gorithms on the 1-dimensional reconfigurable mesh with ? processors. We assume that processors are identical, and does not have unique IDs. Initialization is a task that as- signs sequential IDs to processors in the reconfigurable mesh. We first show a simple deterministic initialization algorithm for the 1-dimensional reconfigurable mesh that runs in ?? time. This deterministic algorithm is optimal, because no deterministic solution can perform initialization in less than ?? time. Quite surprisingly, we show that expected sublinear-time initialization is possible if we use randomized techniques. Our initialization algorithm runs in ???? ? ? ?? ? ?? ?? ? time with probability at least ? ? for every real number ? . It follows that the initial- ization algorithm runs in expected ??? ? ?? ?? ? time. We also proved that any randomized initialization need to run in ???? ? time. Thus, our randomized initialization algorithm running in ??? ? ?? ?? ? time is very close to a theoretical lower bound ???? ? time.
Citation:
Koji Nakano, "Randomized Initialization on the 1-Dimensional Reconfigurable Mesh," pdcat, pp.293-300, Eighth International Conference on Parallel and Distributed Computing, Applications and Technologies (PDCAT 2007), 2007
Usage of this product signifies your acceptance of the Terms of Use.