Notes on the complexity of systolic programs

This paper presents two notes which discuss basic theoretical issues concerning the systolic programming methodology and demonstrates simple techniques which can by used to structure communication. The first note shows how the complexity of two simple algorithms is adversely affected by the cost of data movement in a parallel system. Programming techniques which introduce pipelining are used to overcome the problem and improve the complexity. The second note shows an upper bound on the speedup which can be obtained using the methodology on a mesh connected architecture. This bound is stated in terms of the sequential lower bound for the algorithm concerned.