N. Ventroux, F. Blanc, and D. Lavenier (France)
Distributed architectures, Multiprocessing, scheduling, task allocation, hardware implementation
Multi-Processor System-on-Chip (MPSoC) represents today the main trend for future architectural designs. Nonetheless, the scheduling of tasks on these distributed systems is a major problem since it has a central impact on global performances. This problem is known to be NP-complete and only approximate methods can be used. In the past, to approach optimal results, many heuristics have been proposed. But their complexity continue to in crease, without considering efficient HW implementations. The novel scheduling policy, introduced in this paper, finds an interesting trade off between performance and complexity. Our list scheduling heuristic, called LLD, can near-optimally compute non-malleable tasks on multiple processing elements to minimize the schedule length with a low complexity. The comparison study achieved with already proposed algorithms shows that the LLD scheduling algorithm significantly overcomes the previous approaches in terms of processing element occupation as well as overall execution time.
Important Links:
Go Back
