This paper extends the expressive power of FP by introducing stream and recursive equations on stream for the description of parallel algorithms with cyclic data dependency and states. The decidability theorem of about whether the FP program has its systolic implementation is given. This research also shows that the systoliclizing method on graph can be easily used on FP description.
参考文献
[1] J.Backus,“Can Programming be Liberated from the Von Neumann Style? A Functional Style and Its Algebra of Programs”,CACM,No.3,1978.
[2] H.T.Kung,“Let's Design Algorithms for VLSI Systems”,Tech.Report,Carnegie-Mellon Univ.TRCMU-CS-79-151.
[3] U.Weiser,A.L.Davis,“Mathematical Representation for VLSI Arrays”,Tech.Report,Utah Univ. TR-UU-CS-80-111.
[4] D.I.Moldovan,J.A.B.Forts,“Partitioning and Mapping Algorithms into Fixed Size Systolic Arrays”,IEEE Trans.on Computer,Vol.c-35,No.1,1986.