TITLE:
Understanding the Theory of Karp, Miller and Winograd
AUTHORS:
Athanasios I. Margaris
KEYWORDS:
Computability, Scheduling, Computations, Recurrent Equations
JOURNAL NAME:
Journal of Applied Mathematics and Physics,
Vol.12 No.4,
April
26,
2024
ABSTRACT: The objective of this tutorial is to present the fundamental theory of Karp, Miller and Winograd, whose seminal paper laid the foundations regarding the systematic description of the organization of computations in systems of uniform recurrent equations by means of graph structures, via the definition of computability conditions and techniques for the construction of one-dimensional and multi-dimensional scheduling functions. Besides the description of this theory, the paper presents improvements and revisions made by other authors and furthermore, points out the differences regarding the conditions of causality and dependency between the general case of systems of recurrent equations and the special case of multiple nested loops.