Randomized Initialization on the 1-Dimensional Reconfigurable Mesh
Koji Nakano · 2007
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 algorithms on the 1-dimensional reconfigurable mesh with n processors. We assume that processors are identical, and does not have unique IDs. Initialization is a task that assigns sequential IDs to processors in the reconfigurable mesh. We first show a simple deterministic initialization algorithm for the I-dimensional reconfigurable mesh that runs inO(n) time. This deterministic algorithm is optimal, because no deterministic solution can perform initialization in less thanO(n) time. Quite surprisingly, we show that expected sublinear-time initialization is possible if we use randomized techniques. Our initialization algorithm runs inO((log n + log f) log log n) time with probability at least 1-1/4 for every real number f ges 1. It follows that the initialization algorithm runs in expected O(log n log log n) time. We also proved that any randomized initialization need to run inO(log n) time. Thus, our randomized initialization algorithm running inO(log n log log n) time is very close to a theoretical lower bound Omega(log n) time.