In den Arbeiten A systolic array algorithm for the algebraic path problem (shortest paths; matrix inversion) wird ein gitterförmiges Prozessorennetzwerk und ein zugehöriger paralleler Algorithmus für die im Titel genannten Probleme entwickelt. Bei einem systolischen Algorithmus "fließen" die Datenelemente synchron in einem regelmäßigen Muster durch die Prozessoren, und das Problem ist, die Bewegung so zu steuern, dass die Daten, die miteinander verknüpft werden, zur rechten Zeit in einem Prozessor zusammentreffen. Der von mir entwickelte systolische Algorithmus ist einer der wenigen systolischen Algorithmen für ein zweidimensionalen Prozessorfeld mit einem nichttrivialen Datenfluss.
Mittlerweile gibt es auch andere Algorithmen für dasselbe Problem, die jedoch durch eine Transformation des Orts-Zeit-Raumes ineinander übergeführt werden können. Diese Transformierbarkeit, die auch von vielen anderen Autoren beobachtet worden ist, ist das Thema meiner kleinen Arbeit On the connection between hexagonal and unidirectional rectangular systolic arrays.
Die Arbeit A parallel scheduling algorithm for minimizing the number of unscheduled jobs beschreibt einen parallelen Algorithmus für ein klassisches ein-Maschinen-Schedulingproblem für ein PRAM-Rechnermodell (paralleles RAM).
zum Überblick