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.
|
Task Graph File Name |
Number of Tasks |
Number of Processors |
Optimal Schedule Length [u.t.] |
|
proto000.stg |
452 |
20 |
537 |
|
proto001.stg |
473 |
4 |
1178 |
|
proto002.stg |
499 |
14 |
341 |
|
proto003.stg |
164 |
13 |
556 |
|
proto004.stg |
457 |
20 |
Time Over |
|
proto005.stg |
404 |
7 |
742 |
|
proto006.stg |
273 |
19 |
Time Over |
|
proto007.stg |
499 |
18 |
489 |
|
proto008.stg |
399 |
7 |
571 |
|
proto009.stg |
438 |
18 |
625 |
|
proto010.stg |
539 |
16 |
334 |
|
proto011.stg |
759 |
15 |
Time Over |
|
proto012.stg |
939 |
5 |
1793 |
|
proto013.stg |
799 |
11 |
681 |
|
proto014.stg |
636 |
12 |
Time Over |
|
proto015.stg |
712 |
15 |
491 |
|
proto016.stg |
641 |
6 |
Time Over |
|
proto017.stg |
722 |
15 |
Time Over |
|
proto018.stg |
730 |
10 |
700 |
|
proto019.stg |
617 |
9 |
667 |
|
proto020.stg |
1104 |
7 |
1504 |
|
proto021.stg |
1145 |
20 |
605 |
|
proto022.stg |
1189 |
7 |
1609 |
|
proto023.stg |
1353 |
8 |
1612 |
|
proto024.stg |
1218 |
9 |
1281 |
|
proto025.stg |
1258 |
10 |
1188 |
|
proto026.stg |
1239 |
8 |
1500 |
|
proto027.stg |
1055 |
5 |
2000 |
|
proto028.stg |
1424 |
9 |
1504 |
|
proto029.stg |
1341 |
20 |
830 |
|
proto030.stg |
1501 |
14 |
1051 |
|
proto031.stg |
1558 |
11 |
Time Over |
|
proto032.stg |
1756 |
12 |
Time Over |
|
proto033.stg |
1522 |
4 |
3685 |
|
proto034.stg |
1882 |
12 |
1507 |
|
proto035.stg |
1545 |
4 |
3841 |
|
proto036.stg |
1511 |
15 |
966 |
|
proto037.stg |
1719 |
4 |
4086 |
|
proto038.stg |
1999 |
12 |
1616 |
|
proto039.stg |
1992 |
6 |
3159 |
|
proto040.stg |
2482 |
17 |
Time Over |
|
proto041.stg |
2120 |
16 |
Time Over |
|
proto042.stg |
2382 |
4 |
5680 |
|
proto043.stg |
2058 |
18 |
1087 |
|
proto044.stg |
2369 |
7 |
3226 |
|
proto045.stg |
2198 |
13 |
Time Over |
|
proto046.stg |
2388 |
17 |
1374 |
|
proto047.stg |
2255 |
11 |
2027 |
|
proto048.stg |
2064 |
4 |
4903 |
|
proto049.stg |
2380 |
20 |
Time Over |
|
proto050.stg |
338 |
15 |
738 |
|
proto051.stg |
416 |
16 |
516 |
|
proto052.stg |
169 |
8 |
298 |
|
proto053.stg |
455 |
3 |
1581 |
|
proto054.stg |
158 |
12 |
630 |
|
proto055.stg |
349 |
17 |
713 |
|
proto056.stg |
349 |
12 |
386 |
|
proto057.stg |
279 |
11 |
575 |
|
proto058.stg |
137 |
19 |
543 |
|
proto059.stg |
421 |
7 |
618 |
|
proto060.stg |
551 |
4 |
1401 |
|
proto061.stg |
717 |
10 |
724 |
|
proto062.stg |
591 |
6 |
972 |
|
proto063.stg |
713 |
16 |
491 |
|
proto064.stg |
616 |
3 |
2112 |
|
proto065.stg |
681 |
6 |
1196 |
|
proto066.stg |
771 |
6 |
1368 |
|
proto067.stg |
627 |
10 |
Time Over |
|
proto068.stg |
822 |
20 |
Time Over |
|
proto069.stg |
778 |
15 |
534 |
|
proto070.stg |
1152 |
6 |
1970 |
|
proto071.stg |
1193 |
20 |
629 |
|
proto072.stg |
1455 |
20 |
744 |
|
proto073.stg |
1382 |
19 |
764 |
|
proto074.stg |
1007 |
12 |
891 |
|
proto075.stg |
1082 |
14 |
826 |
|
proto076.stg |
1385 |
8 |
1821 |
|
proto077.stg |
1471 |
6 |
2477 |
|
proto078.stg |
1009 |
18 |
609 |
|
proto079.stg |
1009 |
18 |
796 |
|
proto080.stg |
1824 |
15 |
1275 |
|
proto081.stg |
1607 |
6 |
2840 |
|
proto082.stg |
1570 |
8 |
2079 |
|
proto083.stg |
1951 |
12 |
1711 |
|
proto084.stg |
1701 |
7 |
2525 |
|
proto085.stg |
1803 |
18 |
1075 |
|
proto086.stg |
1521 |
3 |
5214 |
|
proto087.stg |
1992 |
5 |
4240 |
|
proto088.stg |
1916 |
15 |
1355 |
|
proto089.stg |
1650 |
11 |
1559 |
|
proto090.stg |
2217 |
19 |
Time Over |
|
proto091.stg |
2059 |
8 |
2752 |
|
proto092.stg |
2498 |
12 |
2172 |
|
proto093.stg |
2101 |
8 |
2688 |
|
proto094.stg |
2431 |
7 |
3603 |
|
proto095.stg |
2424 |
13 |
1991 |
|
proto096.stg |
2324 |
8 |
3042 |
|
proto097.stg |
2312 |
9 |
2721 |
|
proto098.stg |
2390 |
14 |
1797 |
|
proto099.stg |
2121 |
20 |
Time Over |
|
proto100.stg |
259 |
5 |
519 |
|
proto101.stg |
251 |
17 |
658 |
|
proto102.stg |
164 |
17 |
582 |
|
proto103.stg |
384 |
6 |
Time Over |
|
proto104.stg |
327 |
11 |
592 |
|
proto105.stg |
137 |
16 |
546 |
|
proto106.stg |
477 |
15 |
958 |
|
proto107.stg |
395 |
17 |
280 |
|
proto108.stg |
181 |
4 |
427 |
|
proto109.stg |
213 |
13 |
741 |
|
proto110.stg |
790 |
18 |
510 |
|
proto111.stg |
532 |
9 |
645 |
|
proto112.stg |
559 |
19 |
604 |
|
proto113.stg |
574 |
16 |
842 |
|
proto114.stg |
897 |
8 |
1149 |
|
proto115.stg |
581 |
19 |
342 |
|
proto116.stg |
983 |
19 |
547 |
|
proto117.stg |
613 |
14 |
693 |
|
proto118.stg |
741 |
8 |
1004 |
|
proto119.stg |
934 |
12 |
804 |
|
proto120.stg |
1064 |
9 |
1279 |
|
proto121.stg |
1353 |
9 |
1645 |
|
proto122.stg |
1401 |
6 |
2348 |
|
proto123.stg |
1091 |
19 |
605 |
|
proto124.stg |
1256 |
6 |
2144 |
|
proto125.stg |
1107 |
18 |
635 |
|
proto126.stg |
1143 |
4 |
3031 |
|
proto127.stg |
1120 |
12 |
925 |
|
proto128.stg |
1362 |
5 |
2750 |
|
proto129.stg |
1277 |
18 |
779 |
|
proto130.stg |
1538 |
13 |
1162 |
|
proto131.stg |
1978 |
3 |
6842 |
|
proto132.stg |
1623 |
12 |
1450 |
|
proto133.stg |
1753 |
14 |
1309 |
|
proto134.stg |
1894 |
10 |
1906 |
|
proto135.stg |
1881 |
19 |
1015 |
|
proto136.stg |
1659 |
8 |
2166 |
|
proto137.stg |
1795 |
17 |
1112 |
|
proto138.stg |
1741 |
17 |
1104 |
|
proto139.stg |
1696 |
20 |
886 |
|
proto140.stg |
2249 |
15 |
1554 |
|
proto141.stg |
2251 |
7 |
3407 |
|
proto142.stg |
2101 |
18 |
1251 |
|
proto143.stg |
2490 |
7 |
3728 |
|
proto144.stg |
2418 |
6 |
4302 |
|
proto145.stg |
2485 |
12 |
2090 |
|
proto146.stg |
2235 |
9 |
2592 |
|
proto147.stg |
2119 |
8 |
2884 |
|
proto148.stg |
2122 |
7 |
3189 |
|
proto149.stg |
2122 |
16 |
1398 |
|
proto150.stg |
442 |
7 |
Time Over |
|
proto151.stg |
80 |
16 |
119 |
|
proto152.stg |
459 |
7 |
Time Over |
|
proto153.stg |
277 |
15 |
251 |
|
proto154.stg |
135 |
18 |
212 |
|
proto155.stg |
406 |
5 |
777 |
|
proto156.stg |
489 |
17 |
427 |
|
proto157.stg |
311 |
18 |
349 |
|
proto158.stg |
194 |
11 |
358 |
|
proto159.stg |
211 |
15 |
148 |
|
proto160.stg |
585 |
19 |
Time Over |
|
proto161.stg |
658 |
10 |
Time Over |
|
proto162.stg |
620 |
16 |
Time Over |
|
proto163.stg |
900 |
7 |
1295 |
|
proto164.stg |
844 |
7 |
1170 |
|
proto165.stg |
560 |
20 |
269 |
|
proto166.stg |
745 |
13 |
546 |
|
proto167.stg |
951 |
11 |
Time Over |
|
proto168.stg |
607 |
13 |
Time Over |
|
proto169.stg |
837 |
20 |
506 |
|
proto170.stg |
1409 |
4 |
3366 |
|
proto171.stg |
1325 |
16 |
Time Over |
|
proto172.stg |
1144 |
12 |
Time Over |
|
proto173.stg |
1024 |
14 |
Time Over |
|
proto174.stg |
1198 |
20 |
Time Over |
|
proto175.stg |
1311 |
10 |
1253 |
|
proto176.stg |
1077 |
12 |
Time Over |
|
proto177.stg |
1144 |
15 |
753 |
|
proto178.stg |
1078 |
17 |
Time Over |
|
proto179.stg |
1432 |
6 |
2275 |
|
proto180.stg |
1892 |
14 |
1339 |
|
proto181.stg |
1516 |
19 |
Time Over |
|
proto182.stg |
1987 |
15 |
1308 |
|
proto183.stg |
1587 |
3 |
5113 |
|
proto184.stg |
1704 |
19 |
Time Over |
|
proto185.stg |
1674 |
8 |
Time Over |
|
proto186.stg |
1875 |
15 |
Time Over |
|
proto187.stg |
1841 |
14 |
Time Over |
|
proto188.stg |
1781 |
3 |
6008 |
|
proto189.stg |
1540 |
4 |
3635 |
|
proto190.stg |
2113 |
16 |
Time Over |
|
proto191.stg |
2317 |
8 |
2749 |
|
proto192.stg |
2470 |
20 |
1221 |
|
proto193.stg |
2295 |
6 |
3818 |
|
proto194.stg |
2007 |
3 |
6500 |
|
proto195.stg |
2250 |
4 |
5625 |
|
proto196.stg |
2048 |
9 |
Time Over |
|
proto197.stg |
2004 |
16 |
1221 |
|
proto198.stg |
2245 |
4 |
5597 |
|
proto199.stg |
2205 |
19 |
Time Over |
|
proto200.stg |
210 |
14 |
244 |
|
proto201.stg |
297 |
16 |
198 |
|
proto202.stg |
337 |
4 |
869 |
|
proto203.stg |
142 |
10 |
193 |
|
proto204.stg |
239 |
8 |
371 |
|
proto205.stg |
235 |
7 |
354 |
|
proto206.stg |
276 |
11 |
489 |
|
proto207.stg |
274 |
14 |
297 |
|
proto208.stg |
239 |
16 |
302 |
|
proto209.stg |
464 |
12 |
407 |
|
proto210.stg |
595 |
18 |
684 |
|
proto211.stg |
514 |
13 |
408 |
|
proto212.stg |
702 |
8 |
912 |
|
proto213.stg |
683 |
10 |
712 |
|
proto214.stg |
607 |
10 |
618 |
|
proto215.stg |
572 |
8 |
754 |
|
proto216.stg |
583 |
20 |
568 |
|
proto217.stg |
937 |
17 |
600 |
|
proto218.stg |
668 |
20 |
417 |
|
proto219.stg |
599 |
14 |
429 |
|
proto220.stg |
1489 |
18 |
Time Over |
|
proto221.stg |
1272 |
9 |
1505 |
|
proto222.stg |
1344 |
9 |
1520 |
|
proto223.stg |
1277 |
15 |
891 |
|
proto224.stg |
1081 |
7 |
1664 |
|
proto225.stg |
1122 |
14 |
Time Over |
|
proto226.stg |
1378 |
13 |
1112 |
|
proto227.stg |
1214 |
13 |
970 |
|
proto228.stg |
1187 |
8 |
1570 |
|
proto229.stg |
1108 |
13 |
Time Over |
|
proto230.stg |
1878 |
7 |
2829 |
|
proto231.stg |
1694 |
16 |
Time Over |
|
proto232.stg |
1881 |
11 |
1828 |
|
proto233.stg |
1980 |
19 |
1118 |
|
proto234.stg |
1587 |
5 |
3340 |
|
proto235.stg |
1782 |
16 |
Time Over |
|
proto236.stg |
1691 |
3 |
5841 |
|
proto237.stg |
1566 |
12 |
1340 |
|
proto238.stg |
1737 |
10 |
1839 |
|
proto239.stg |
1975 |
16 |
Time Over |
|
proto240.stg |
2264 |
12 |
1985 |
|
proto241.stg |
2187 |
12 |
1949 |
|
proto242.stg |
2131 |
12 |
1880 |
|
proto243.stg |
2166 |
20 |
1126 |
|
proto244.stg |
2426 |
17 |
1470 |
|
proto245.stg |
2156 |
10 |
2290 |
|
proto246.stg |
2199 |
3 |
7572 |
|
proto247.stg |
2351 |
14 |
1778 |
|
proto248.stg |
2215 |
19 |
Time Over |
|
proto249.stg |
2080 |
9 |
2407 |
|
proto250.stg |
447 |
10 |
560 |
|
proto251.stg |
160 |
11 |
276 |
|
proto252.stg |
132 |
14 |
195 |
|
proto253.stg |
342 |
7 |
495 |
|
proto254.stg |
250 |
8 |
345 |
|
proto255.stg |
138 |
12 |
360 |
|
proto256.stg |
163 |
11 |
292 |
|
proto257.stg |
157 |
5 |
460 |
|
proto258.stg |
145 |
14 |
359 |
|
proto259.stg |
139 |
6 |
328 |
|
proto260.stg |
645 |
16 |
435 |
|
proto261.stg |
900 |
3 |
3182 |
|
proto262.stg |
940 |
7 |
1456 |
|
proto263.stg |
971 |
5 |
1982 |
|
proto264.stg |
873 |
17 |
571 |
|
proto265.stg |
632 |
6 |
1093 |
|
proto266.stg |
612 |
12 |
490 |
|
proto267.stg |
612 |
3 |
2059 |
|
proto268.stg |
789 |
10 |
847 |
|
proto269.stg |
945 |
20 |
493 |
|
proto270.stg |
1464 |
15 |
1040 |
|
proto271.stg |
1348 |
12 |
1163 |
|
proto272.stg |
1017 |
14 |
776 |
|
proto273.stg |
1084 |
11 |
1052 |
|
proto274.stg |
1015 |
13 |
814 |
|
proto275.stg |
1472 |
19 |
807 |
|
proto276.stg |
1190 |
5 |
2412 |
|
proto277.stg |
1257 |
7 |
1880 |
|
proto278.stg |
1238 |
7 |
1965 |
|
proto279.stg |
1342 |
6 |
2217 |
|
proto280.stg |
1868 |
7 |
2800 |
|
proto281.stg |
1622 |
19 |
896 |
|
proto282.stg |
1793 |
6 |
3123 |
|
proto283.stg |
1591 |
7 |
2422 |
|
proto284.stg |
1703 |
4 |
4444 |
|
proto285.stg |
1766 |
15 |
1268 |
|
proto286.stg |
1703 |
20 |
918 |
|
proto287.stg |
1615 |
13 |
1353 |
|
proto288.stg |
1672 |
9 |
1925 |
|
proto289.stg |
1642 |
9 |
1915 |
|
proto290.stg |
2133 |
16 |
1428 |
|
proto291.stg |
2122 |
9 |
2591 |
|
proto292.stg |
2333 |
3 |
8009 |
|
proto293.stg |
2089 |
15 |
1472 |
|
proto294.stg |
2014 |
17 |
1257 |
|
proto295.stg |
2168 |
18 |
1318 |
|
proto296.stg |
2162 |
9 |
2563 |
|
proto297.stg |
2136 |
3 |
7703 |
|
proto298.stg |
2399 |
10 |
2471 |
|
proto299.stg |
2205 |
20 |
1141 |
|
