Narrow Results

We prove a separation between two models of the reconfigurable mesh (rmesh), the cross-over model and the non-cross-over model. Specifically, for any constant k ≥ 1, we show that in the non-cross-over model, a k × n rmesh requires Ω(log n) time to compute the parity of n bits stored one per column, while in the cross-over model, when k ≥ 3, a k × n rmesh can compute the parity in constant time. This is the first separation demonstrated between the cross-over and non-cross-over model. The lower bound does not rely on the bandwidth constraints of the mesh and does not restrict the instruction sets of the processors. Moreover, it is the first lower bound for the rmesh which requires only binary inputs.