并行算法的FP描述及其脉动化的判定
作者:

DESCRIPTION OF PARALLEL ALGORITHMS BY FP AND DECIDABILITY OF ITS SYSTOLIC IMPLEMENTATION
  • 摘要
  • | |
  • 访问统计
  • |
  • 参考文献 [14]
  • |
  • 相似文献 [20]
  • | | |
  • 文章评论
    摘要:

    本文通过引入流及流上的递归方程,增强了FP表达并行算法的能力,有效地克服了用FP描述循环数据依赖及状态记忆的困难,文中给出了并行算法的FP描述及其可脉动化的判定定理。同时说明,许多在图上研究的脉动方法可以方便地应用到用FP描述脉动化的研究中去。

    Abstract:

    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.
    [5] S.Y.Kung,K.S.Arum,“Wavefront Array Processor:Language,Architecture,and Application”,IEEE Trans.on Computer,Vol.c一31,No.11,1982.
    [6] P.Quiton,“Automatic Synthesis of Systolic Arrays from Uniform Recurrent Equations”,Proc. IEEE. 1984.
    [7] c.E.Leiserson,J.B.Saxe,“Optimizing Synchronous System”,Tech.Report,Carnegie-Mellon Univ.TR-CMU-CS-82-101.
    [8] M.Sheeran,“μFP-An Algebraic VLSI Design Language”,Ph.D Thesis,Oxfors Univ.TM-PRG-39. NOV.1983.
    [9] s.Y.Kung,“On Supercomputing with Systolic/Wavefront Array Processors”Proc.IEEE Vol.72,July, 1984.
    [10] J.D.Ullman,“Computational Aspects of VLSI”,Computer Science Press,1983.
    [11] J.A.B.Forts,K.S.Fu,“Systematic Approaches to the Design of Algorithmically Specified Systolic Arrays”,Purdue Univ.TR-EE84-39.
    [12] W.Luk,G.Jones,“The Derivation of Regular Synchronous Circuits”IEEE Int.Conf.on Systolic Array.1988.
    [13] Y.C.Lin,F.C.Lin,“The Use of A FP to Design Regular Array Algorithms”Proc.1988 Int.Conf. On Comp.Lang.,Oct.1988.
    [14] G.Milne,“cIRcAL:A Calculus for circuit Description”,Univ.of Edinburgh,1982,Tech.Report.CSR-122-82.
    引证文献
    网友评论
    网友评论
    分享到微博
    发 布
引用本文

胡振江,孙永强.并行算法的FP描述及其脉动化的判定.软件学报,1992,3(3):9-16

复制
分享
文章指标
  • 点击次数:3355
  • 下载次数: 4824
  • HTML阅读次数: 0
  • 引用次数: 0
历史
  • 收稿日期:1990-05-18
  • 最后修改日期:1990-08-15
文章二维码
您是第19829859位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京市海淀区中关村南四街4号,邮政编码:100190
电话:010-62562563 传真:010-62562533 Email:jos@iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号