Code-Mapping Policies for the Tagged-Token Dataflow Architecture

摘要

Multiprocessing seems to be the only viable way to gain significant speedup beyond that afforded by performance advances in semiconductor devices and hardware construction, which are beginning to face the limitations of physics. Although it is relatively easy to improve the raw computational performance of a system simply by adding more processors to it, the far more difficult task is to insure that the additional resources actually reduce a program's computing time. Thus, the ultimate success of multiprocessing as a means of increasing computation speed rests on the ability to parallelize computation: to partition, allocate, distribute, and schedule work efficiently amongst the large collection of available system resources, while maintaining a high rate of utilization of these resources. To keep many processors busy with work, it is necessary that the program has enough concurrent operations to map to those processors. But given that there is much concurrency in many large programs, the onus lies on the code-mapping process to maintain as much concurrency as is feasible without compromising its efficiency. This goal maximizes the scalability of the system. Our study is based on a dataflow computer, the MIT Tagged-Token Dataflow Architecture (TTDA). This study focuses on analyzing the effectiveness of the code-mapping policies for the TTDA. It develops metrics and a practical method for evaluating the effectiveness of mapping policies on a given benchmark program and proceeds to apply it to a variety of readily implementable schemes. (kr)