Efficient Execution of Dataflow Programs

数据流程序的高效执行

• 批准号: 8709817
• 负责人: Lubomir Bic
• 金额: $ 13.59万
• 依托单位: University of California-Irvine
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 1987
• 资助国家: 美国
• 起止时间: 1987-08-01 至 1990-01-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=8709817&HistoricalAwards=false
• 关键词: Efficient; Execution; Dataflow; Programs

A number of architectures have been proposed to implement the basic principles of dataflow computation. The main problem common to all these architectures is a large overhead associated with the execution of each individual instruction. In particular, each operand that passes from one instruction to another may have to travel considerable distances through a communication network and various hardware components (special memories and queues) before it reaches its destination. Furthermore, operands destined for the same instruction must be recognized and segregated in a special token matching store. Only when all operands have arrived for an instruction, can it be scheduled for execution on a processor. In comparison, passing an operand from one instruction to another in a von Neumann computer requires only a simple memory store operation. In this research, a different approach is used to executing dataflow program, which significantly reduces the overhead of operand routing and matching. The approach is based on the idea of breaking a given dataflow program into segments of code which, due to their operand dependencies, must be executed sequentially. Each such sequence may be loaded into memory for execution whenever its first instruction is enabled. Once loaded,it can be viewed as a very simple sequential process, which is ready when its current instruction is enabled, running when there is a free processor, and blocked when its current instruction is waiting for operands to arrive. Hence, the dataflow program may be viewed as a collection of very simple communicating processes. In this research, they will investigate the process-oriented approach by formulating the model and the architecture in more detail and by performing extensive simulation experiments to compare its performance to von Neumann computers and to other dataflow systems.

已经提出了许多体系结构来实现数据流计算的基本原理。所有这些体系结构的共同主要问题是与执行每条单独的指令相关的大量开销。具体地说，从一条指令传递到另一条指令的每个操作数在到达其目的地之前可能必须通过通信网络和各种硬件组件(特殊存储器和队列)传输相当长的距离。此外，指定给同一指令的操作数必须在特殊的令牌匹配存储中识别和隔离。只有当指令的所有操作数都到达时，才能调度它在处理器上执行。相比之下，在冯·诺伊曼计算机中，将操作数从一条指令传递到另一条指令只需要简单的内存存储操作。在本研究中，使用了一种不同的方法来执行数据流程序，从而显著降低了操作数路由和匹配的开销。该方法基于将给定的数据流程序分解成代码段的思想，由于它们的操作数相关性，这些代码段必须顺序执行。无论何时启用其第一条指令，都可以将每个这样的序列加载到存储器中以供执行。一旦加载，它可以被视为一个非常简单的顺序进程，当其当前指令被启用时，它就准备好了，当有空闲处理器时，它就运行，当它的当前指令等待操作数到达时，它就被阻止了。因此，数据流程序可以被视为非常简单的通信进程的集合。在这项研究中，他们将通过更详细地制定模型和体系结构，并通过进行广泛的模拟实验来比较其与冯·诺伊曼计算机和其他数据流系统的性能，来研究面向过程的方法。