Task mapping and scheduling are two very difficult prob- lems that must be addressed when a sequential program is transformed into a parallel program. Since these problems are NP-hard, compiler writers have opted to concentrate their efforts on optimizations that produce immediate gains in per- formance. As a result, current parallelizing compilers either use very simple methods to deal with task scheduling or they simply ignore it altogether Unfortunately, the programmer does not have this luxury. The burden of repartitioning or rescheduling, should the compiler produce inefficient paral- lel code, lies entirely with the programmer We were able to create an algorithm (called a meta- heuristic), which automatically chooses a scheduling heuris- tic for each input program. The metaheuristic produces bet- ter schedules in general than the heuristics upon which it is based. This technique was tested on a suite of real scien- tific programs written in SISAL and simulated on four dif ferent network configurations. Averaged over all of the test cases, the metaheuristic out-performed all eight underlying scheduling algorithms, beating the best one by 2, 12, l3, and 3 on the four separate network configurations. It is able to do this, not always by picking the best heuristic, but rather by avoiding the heuristics when they would produce very poor schedules. For example, while the metaheuristic only picked the best algorithm about 50 of the time for the 100 Gbps Ethernet, its worst decision was only 49 away from optimal. In contrast, the best of the eight scheduling al- gorithm
展开▼
