Research on the Automatic Implementation of High Level Programming Constructs

这个项目关注的是包含大量相互连接的处理器的并行计算机系统的算法和编程环境的设计。目标是开发这种系统的用户将需要的一些通用算法技术，确定在高级并行编程语言中应该包括哪些基本操作，并解决在实现这些基本操作时将出现的一些算法问题。特别感兴趣的操作涉及到面向集合的数据结构和组合搜索。有效实现这些操作的方法使用了随机负载平衡、并行树搜索和动态树嵌入的思想。为了支持高级并行编程，还研究了在存在故障处理器时进行排序、消息路由和同步控制的有效算法。

This project is concerned with the design of algorithms and programming environments for parallel computer systems containing large numbers of interconnected processors. The goals are to develop some of the generic algorithmic techniques that users of such systems will require, to determine what primitive operations should be included in a high-level parallel programming language, and to solve some of the algorithmic problems that will arise in the implementation of such primitive operations. The operations of particular interest relate to set-oriented data structures and combinatorial search. The approach to the efficient implementation of these operations uses ideas from randomized load balancing, parallel tree search and dynamic tree embedding. In order to support high-level parallel programming, efficient algorithms for sorting in the presence of faulty processors, message routing and synchronization control are also investigated.