### Abstract

A systolic design for the algebraic path problem (APP) is introduced. The APP is a generalization of a cross-disciplinary set of problems that includes transitive closure, shortest path, and matrix inversion. Special cases of the array can be used to solve any instance of the APP. The array uses N**2 processing elements, and requires 2N I/O connections. A design methodology that is based on dependence-graph analysis is introduced to derive this array. The design methodology is an extension of methods based on uniform recurrence equations. The algorithm for the APP is described in a localized, indexed, single-assignment form. A systolic implementation of the algorithm is generated by mapping its dependence graph onto an array configuration. Different mappings of the same dependence graph produce both the array used here and those previously proposed for the APP. A comparison is made of all arrays proposed for the APP.

Original language | English (US) |
---|---|

Title of host publication | Conference Record - Asilomar Conference on Circuits, Systems & Computers |

Publisher | IEEE |

Pages | 13-18 |

Number of pages | 6 |

ISBN (Print) | 0818608161 |

State | Published - Jan 1 1987 |

Externally published | Yes |

### Publication series

Name | Conference Record - Asilomar Conference on Circuits, Systems & Computers |
---|---|

ISSN (Print) | 0736-5861 |

### All Science Journal Classification (ASJC) codes

- Engineering(all)

## Fingerprint Dive into the research topics of 'DEPENDENCE GRAPH BASED DESIGN OF SYSTOLIC ARRAYS FOR THE ALGEBRAIC PATH PROBLEM.'. Together they form a unique fingerprint.

## Cite this

*Conference Record - Asilomar Conference on Circuits, Systems & Computers*(pp. 13-18). (Conference Record - Asilomar Conference on Circuits, Systems & Computers). IEEE.