''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
Abstract:
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.