Change search
ReferencesLink to record
Permanent link

Direct link
Computing transitive closure on systolic arrays of fixed size
Number of Authors: 1
1989 (English)Report (Refereed)
Abstract [en]

Forming the transitive closure of a binary relation (or directed graph) is an important part of many algorithms. When the relation is represented by a bit matrix, the transitive closure can be efficiently computed in parallel in a systolic array. Various such arrays for computing the transitive closure have been proposed. They all have in common, though, that the size of the array must be proportional to the number of nodes. Here we propose two ways of computing the transitive closure of an arbitrarily big graph on a systolic array of fixed size. The first method is a simple partitioning of a well-known systolic algorithm for computing the transitive closure. The second is a block-structured algorithm for computing the transitive closure. This algorithm is suitable for execution on a systolic array, that can multiply fixed size bit matrices and compute transitive closure of graphs with a fixed number of nodes. The algorithm is, however, not limited to systolic array implementations; it works on any parallel architecture that can form the transitive closure and product of fixed-size bit matrices efficiently. The shortest path problem, for directed graphs with weighted edges, can also be solved for arbitrarily large graphs on a fixed-size systolic array in the same manner, devised above, as the transitive closure is computed.

Place, publisher, year, edition, pages
Kista, Sweden: Swedish Institute of Computer Science , 1989, 1. , 24 p.
Series
SICS Research Report, ISSN 0283-3638 ; R89:10
National Category
Computer and Information Science
Identifiers
URN: urn:nbn:se:ri:diva-22180OAI: oai:DiVA.org:ri-22180DiVA: diva2:1041724
Note
Original report number R89010.Available from: 2016-10-31 Created: 2016-10-31

Open Access in DiVA

fulltext(2201 kB)3 downloads
File information
File name FULLTEXT01.pdfFile size 2201 kBChecksum SHA-512
2b9e55c3281a1a937349dcef3d088ed6ff4b0ba4a3f76cca0dd5a44ebce2246202322f52a327d70f376930b2f8cf4b4d85ad1f941eaea8d79b42810bf5d814aa
Type fulltextMimetype application/pdf

Computer and Information Science

Search outside of DiVA

GoogleGoogle Scholar
Total: 3 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 1 hits
ReferencesLink to record
Permanent link

Direct link