Semantics of Parallel Programs

并行程序的语义

• 批准号: 9006064
• 负责人: Stephen Brookes
• 金额: $ 20.96万
• 依托单位: Carnegie-Mellon University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 1990
• 资助国家: 美国
• 起止时间: 1990-12-15 至 1994-05-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9006064&HistoricalAwards=false
• 关键词: Semantics; Parallel; Programs

This is a basic research program concerning semantic models for parallel programming languages. Initial emphasis is on the design of a mathematical model of parallel algorithms extending and generalizing earlier work of Berry and Curien on sequential algorithms and concrete data structures. The model is intensional, in that the denotation of a program includes information about parallel computation strategy in addition to information about the extensional or functional behavior of the program. This allows a novel intensional strictness ordering on parallel algorithms that plays a fundamental role in our theory; for instance, application of a parallel algorithm to its arguments is a continuous operation with respect to this ordering. It will be shown that the model forms a cartesian closed category in which an elegant account of parallel functional computation can be given. It will support semantically-based techniques for proving both traditional (extensional) correctness properties and efficiency properties that depend on intensional aspects of program behavior. The intensional information will be used to determine a hierarchical class of algorithms based on an intuitively reasonable notion of "degree of parallelism". This idea will provide a framework for assessing the relative expressive powers of various sequential and parallel primitives. In the long term theoretical insights gained in this investigation will be in the design of new programming languages that employ parallelism uniformly and generally, yet whose semantic properties are well understood, and for which tractable proof methods can be devised.

这是一个关于并行编程语言语义模型的基础研究项目。最初的重点是设计并行算法的数学模型，扩展和推广Berry和curen在顺序算法和具体数据结构方面的早期工作。该模型是内蕴的，因为程序的外延除了包含有关程序的外延或功能行为的信息外，还包含有关并行计算策略的信息。这允许在并行算法上建立一种新的内涵严格排序，这在我们的理论中起着基础作用；例如，并行算法对其参数的应用是对该顺序的连续操作。它将表明，该模型形成一个笛卡尔封闭范畴，其中一个优雅的并行函数计算可以给出。它将支持基于语义的技术来证明传统的（外延的）正确性属性和依赖于程序行为的内蕴方面的效率属性。该内涵信息将用于确定基于直观合理的“并行度”概念的分层算法类。这个想法将为评估各种顺序和并行原语的相对表达能力提供一个框架。从长远来看，在这项研究中获得的理论见解将是在设计新的编程语言中，这些语言统一地和普遍地使用并行性，但其语义属性被很好地理解，并且可以为其设计易于处理的证明方法。