Optimal Schedules for Prototype Standard Task Graph Set Table 1 represents optimal schedule lengths of Prototype Standard Task Graph Set. These optimal schedules were found by a practical parallel optimization algorithm PDF/IHS (Parallelized Depth First/Implicit heuristic Search) on a shared main memory multiprocessor system Sun Ultra Enterprise 3000 (E3000). The E3000 has 6 Ultra SPARC 167MHz CPUs and 384MB shared main memory. The upper limit on the search time was set to 10 minutes because of NP-completeness of the scheduling problem. In Table 1, "Time Over" means that PDF/IHS algorithm using 6 processor elements could not find an optimal schedule within 10 minutes.
|
Copyright (C) Kasahara Lab., Waseda Univ.. All rights reserved. |
![]() |
Kasahara Laboratory |