Data movement operations and applications on reconfigurable VLSI arrays

A mesh with reconfigurable bus (reconfigurable mesh), that consists of a VLSI array of processors connected to a reconfigurable bus system, is discussed. The N processing elements (PEs) are laid out as a square mesh in O(N) VLSI area. The reconfiguration scheme can be used to dynamically obtain various interconnection patterns between the PEs. In fact, the array can be used as a universal chip capable of simulating any O(N) area organization with a planar wiring layout without loss in time. The reconfiguration scheme also supports several parallel techniques developed for the concurrent-read-concurrent-write parallel random-access machine (CRCW PRAM). Fundamental data movement operations are developed for the reconfigurable mesh. These operations are used to give efficient solutions to a variety of problems involving graphs and digitized pictures. The running times of these algorithms are asymptotically superior to those developed for the mesh with multiple broadcasting, the mesh with multiple buses, the mesh-of-trees, and the pyramid computer.