The transitive closure and related algorithms of digraph on the reconfigurable architecture

Tien Tai Pan, Shun Shii Lin

Research output: Contribution to journalArticle

1 Citation (Scopus)

Abstract

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

Original languageEnglish
Pages (from-to)27-43
Number of pages17
JournalParallel Processing Letters
Volume21
Issue number1
DOIs
Publication statusPublished - 2011 Mar 1

Fingerprint

Reconfigurable architectures
Reconfigurable Architectures
Transitive Closure
Digraph
Reconfigurable Mesh
Parallel processing systems
Resolve
Reconfigurable Systems
Model
Matrix multiplication
Parallel Computation
Minimum Distance
Connected Components
Connectivity
Cycle
Three-dimensional
Path

Keywords

  • Reconfigurable architecture
  • digraph
  • directional
  • parallel computation model
  • reconfigurable mesh
  • strongly connected component
  • transitive closure

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture

Cite this

The transitive closure and related algorithms of digraph on the reconfigurable architecture. / Pan, Tien Tai; Lin, Shun Shii.

In: Parallel Processing Letters, Vol. 21, No. 1, 01.03.2011, p. 27-43.

Research output: Contribution to journalArticle

@article{9c7af6b4e73e4bcd96eeab43c5f73ddd,
title = "The transitive closure and related algorithms of digraph on the reconfigurable architecture",
abstract = "The reconfigurable architecture is a parallel computation model that consists of many processor elements (PEs) and a reconfigurable bus system. There are many variant proposed reconfigurable architectures, for example, reconfigurable mesh (R-Mesh), directional reconfigurable mesh (DR-Mesh), processor arrays with reconfigurable bus systems (PARBS), complete directional processor arrays with reconfigurable bus systems (CD-PARBS), reconfigurable multiple bus machine (RMBM), directional reconfigurable multiple bus machine (directional RMBM), and etc. In this paper, a transitive closure (TC) algorithm of digraph is proposed on the models without the directional capability (non-directional). Some related digraph problems, such as strongly connected digraph, strongly connected component (SCC), cyclic checking, and tree construction, can also be resolved by modifying our transitive closure algorithm. All the proposed algorithms are designed on a three-dimensional (3-D) n×n×n non-directional reconfigurable mesh, n is the number of vertices in a digraph D, and can resolve the respective problems in O(log d(D)) time, d(D) is the diameter of the digraph D. The cyclic checking problem can be further reduced to O(log c(D)) time, c(D) is the minimum distance of cycles in the digraph D. There exist two different approaches: the matrix multiplication approach on the non-directional models for algebraic path problems (APP) and s-t connectivity approach on the directional models. In this paper, we will use the tree construction algorithm to prove those two approaches are insufficient to resolve all digraph problems and demonstrate why our approach is so important and innovative for digraph problems on the reconfigurable models.",
keywords = "Reconfigurable architecture, digraph, directional, parallel computation model, reconfigurable mesh, strongly connected component, transitive closure",
author = "Pan, {Tien Tai} and Lin, {Shun Shii}",
year = "2011",
month = "3",
day = "1",
doi = "10.1142/S0129626411000059",
language = "English",
volume = "21",
pages = "27--43",
journal = "Parallel Processing Letters",
issn = "0129-6264",
publisher = "World Scientific Publishing Co. Pte Ltd",
number = "1",

}

TY - JOUR

T1 - The transitive closure and related algorithms of digraph on the reconfigurable architecture

AU - Pan, Tien Tai

AU - Lin, Shun Shii

PY - 2011/3/1

Y1 - 2011/3/1

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

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

KW - Reconfigurable architecture

KW - digraph

KW - directional

KW - parallel computation model

KW - reconfigurable mesh

KW - strongly connected component

KW - transitive closure

UR - http://www.scopus.com/inward/record.url?scp=79953077914&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=79953077914&partnerID=8YFLogxK

U2 - 10.1142/S0129626411000059

DO - 10.1142/S0129626411000059

M3 - Article

AN - SCOPUS:79953077914

VL - 21

SP - 27

EP - 43

JO - Parallel Processing Letters

JF - Parallel Processing Letters

SN - 0129-6264

IS - 1

ER -