Algorithms for scheduling hardware-software co-design systems

This thesis addresses the hardware–software co-design scheduling problem for real-time systems involving a single CPU and multiple reconfigurable Field Programmable Gate Arrays (FPGAs). The problem requires assigning tasks with precedence, release, and deadline constraints to either the CPU or an FPGA, while respecting reconfiguration overheads and minimizing a composite cost that balances scheduling delay and hardware usage. Building on the seminal work of Ali et al.~\cite{ali2012}, who introduced a time-indexed mixed-integer programming (MIP) formulation, we first replicated and validated the original model to establish a performance baseline. While the MIP approach guarantees optimal solutions for small instances, its scalability is limited by the exponential growth of variables and constraints. To address this, we developed two new algorithms. The first is a \emph{mat-heuristic} that combines a time-limited MIP solve with iterative window-based refinements. This approach preserves near-optimal solution quality (typically within 5--10\% of the MIP) while drastically reducing runtime, enabling the solution of medium to large task sets. The second is a \emph{greedy + simulated annealing} method that constructs an initial feasible schedule in linear time and improves it through local search. Although this algorithm sacrifices optimality (with a gap of 10--20\% compared to MIP), it achieves solutions within seconds even for the largest test cases considered. Experimental comparisons demonstrate a clear trade-off between accuracy and speed: MIP ensures optimality but does not scale; the mat-heuristic achieves a practical balance; and the greedy + SA method offers unmatched speed for very large instances. Together, these three approaches provide a complementary toolkit for hardware–software co-design scheduling, allowing practitioners to choose depending on whether accuracy, efficiency, or responsiveness is prioritized.