SYSTOLIC ARRAY FOR SOLVING CYCLIC LOOP DEPENDENT ALGORITHMS

摘要

AbstractSYSTOLIC ARRAY FOR SOLVINGCYCLIC LOOP DEPENDENT ALGORITHMSA systolic array (1) for reducing the time required tosolve an algorithm having cyclic loop dependency, i.e.,nested loops in which values calculated by inner loopsdepend upon indices of said inner loops and upon indicesof outer loops. The array (1) comprises a chain of severalidentical serially connected and sequentially accessedcells. In the preferred embodiment, each cell, except forfirst and last cells in the chain, is connected to its twoadjacent cells only. Multiprocessing is employed: atcertain times during the algorithm solving, more than onecell is simultaneously activated to perform portions of thesolving, so that the total time required to solve thealgorithms is shortened to be a linear function of n and m.The algorithm can represent measurement of the distancebetween two symbolic strings, or other problems in artificialintelligence or logic, The algorithm is broken up into nxmsubalgorithms D(i,j); at each processing step, thosesubalgorithms D(i,j) are solved for which sufficientinformation exists for their solution. In the illustratedexample, this condition is represented by diagonallytime-slicing a two-dimensional matrix having as elementseach of the subalgorithms D(i,j).