''Tighter and Broader Complexity Results for Reconfigurable Models''

Jerry L. Trahan

Anu G. Bourgeois

Ramachandran Vaidyanathan

Parallel Processing Letters vol. 8, no. 3, pp. 271-282, 1998


A number of models allow processors to reconfigure their local connections to create and alter various bus configurations. This reconfiguration enables development of fast algorithms for fundamental problems, many in constant time. We investigate the ability of such models by relating time and processor bounded complexity classes defined for these models to each other and to those of more traditional models. In this work, (1) we tighten the relations for some of the models, placing them more precisely in relation to each other than was previously known (particularly, the Linear Reconfigurable Network and Directed Reconfigurable Network relative to circuit-defined classes), and (2) we include models (Fusing-Restricted Reconfigurable Mesh and Pipelined Reconfigurable Mesh) not previously considered.

This work was supported in part by the National Science Foundation under grant number CCR-9503882 and the Louisiana Board of Regents through the Louisiana Education Quality Support Fund under contract number LEQSF(1994-96)-RD-A-07.