Enhanced look-ahead scheduling technique to overlap communication with computation

作     者：Li, DC Iwahori, Y Hayashi, T Ishii, N 

作者机构：Nagoya Inst Technol Educ Ctr Informat Proc Nagoya Aichi 4668555 Japan 

出 版 物：《IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS》 (电子信息通信学会汇刊：信息与系统)

年 卷 期：1998年第E81D卷第11期

页      面：1205-1212页

核心收录：

学科分类：0810[工学-信息与通信工程] 08[工学] 0835[工学-软件工程] 081001[工学-通信与信息系统] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主　　题：parallelizing compilers interprocessor communication program optimization compile-time scheduling heuristics directed acyclic graphs 

摘      要：Reducing communication overhead is a key goal of program optimization for current scalable multiprocessors. A well-known approach to achieving this is to map tasks (indivisible units of computation) to processors so that communication and computation overlap as much as possible. In an earlier work, we developed a look-ahead scheduling heuristic for efficiently reducing communication overhead with the aim of decreasing the completion time of a given parallel program. In this paper, we report on an extension of the algorithm, which fills in the idle time slots created by interprocessor communication without increasing the algorithm s time complexity. The results of experiments emphasize the importance of optimally filling idle time slots in processors.