THE TRANSITIVE CLOSURE AND RELATED ALGORITHMS OF DIGRAPH ON THE RECONFIGURABLE ARCHITECTURE

摘要

The reconfigurable architecture is a parallel computation model that consists of manynprocessor elements (PEs) and a reconfigurable bus system. There are many variant pro-nposed reconfigurable architectures, for example, reconfigurable mesh (R-Mesh), direc-ntional reconfigurable mesh (DR-Mesh), processor arrays with reconfigurable bus sys-ntems (PARBS), complete directional processor arrays with reconfigurable bus systemsn(CD-PARBS), reconfigurable multiple bus machine (RMBM), directional reconfigurablenmultiple bus machine (directional RMBM), and etc. In this paper, a transitive closuren(TC) algorithm of digraph is proposed on the models without the directional capabilityn(non-directional). Some related digraph problems, such as strongly connected digraph,nstrongly connected component (SCC), cyclic checking, and tree construction, can alsonbe resolved by modifying our transitive closure algorithm. All the proposed algorithmsnare designed on a three-dimensional (3-D) n×n×n non-directional reconfigurable mesh,nn is the number of vertices in a digraph D, and can resolve the respective problems innO(log d(D)) time, d(D) is the diameter of the digraph D. The cyclic checking problemncan be further reduced to O(log c(D)) time, c(D) is the minimum distance of cycles innthe digraph D. There exist two different approaches: the matrix multiplication approachnon the non-directional models for algebraic path problems (APP) and s-t connectivitynapproach on the directional models. In this paper, we will use the tree construction al-ngorithm to prove those two approaches are insufficient to resolve all digraph problemsnand demonstrate why our approach is so important and innovative for digraph problemsnon the reconfigurable models.