Randomized Initialization on the 1-Dimensional Reconfigurable Mesh

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 in O(n) time. This deterministic algorithm is optimal, because no deterministic solution can perform initialization in less than O(n) time. Quite surprisingly, we show that expected sublinear-time initialization is possible if we use randomized techniques. Our initialization algorithm runs in O((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 in O(log n) time. Thus, our randomized initialization algorithm running in O(log n log log n) time is very close to a theoretical lower bound Omega(log n) time.