Derivation of systolic algorithms for the algebraic path problem by recurrence transformations
| Autor: | Sanjay Rajopadhye, Tanguy Risset, Clémentin Tayou Djamegni, Patrice Quinton |
|---|---|
| Rok vydání: | 2000 |
| Předmět: |
Uniform recurrence equations
Discrete mathematics Computer Networks and Communications Computer Graphics and Computer-Aided Design Theoretical Computer Science Scheduling (computing) Algebra Artificial Intelligence Hardware and Architecture Piecewise affine Algebraic number Algorithm Software Mathematics |
| Zdroj: | Parallel Computing. 26:1429-1445 |
| ISSN: | 0167-8191 |
| DOI: | 10.1016/s0167-8191(00)00039-9 |
| Popis: | In this paper, we are interested in solving the algebraic path problem (APP) on regular arrays. We first unify previous contributions with recurrence transformations. Then, we propose a new localization technique without long-range communication which leads to a piecewise affine scheduling of 4 n + Θ (1) steps, where n is the size of the problem. The derivation of a locally connected space-time minimal solution with respect to the new scheduling constitutes the second contribution of the paper. This new design requires n 2 /3+ Θ ( n ) elementary processors and solves the problem in 4 n + Θ (1) steps, and this includes loading and unloading time. This is an improvement over the best previously known bounds. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect