Abstract
Many embedded systems have hard resource constraints that make schedules found by list scheduling heuristics infeasible. One of the main challenges yielded by memory constraints and the high degree of parallelism is deadlock. In this paper, our primary goal is to find a feasible solution given the memory constraints. We propose a reservation-based solution, an extension for list scheduling algorithms, that can be integrated into those algorithms and make them aware of memory constraints. We show our technique prevents deadlock and significantly reduces the required memory size. The experimental results on randomly generated graphs and real world applications show that our proposed solution can obtain relatively high-quality solutions with up to 10% makespan improvement and 30% memory reduction on average.