Physicallyaware HW-SW partitioning for reconfigurable architectures with partial dynamic reconfiguration

Many reconfigurable architectures offer partial dynamic configura-bility, but current system-level tools cannot guarantee feasible im-plementations when exploiting this feature. We present a physically aware hardware-software (HW-SW) scheme for minimizing appli-cation execution time under HW resource constraints, where the HW is a reconfigurable architecture with partial dynamic reconfig-uration capability. Such architectures impose strict placement con-straints that lead to implementation infeasibility of even optimal scheduling formulations that ignore the nature of these constraints. We propose an exact and a heuristic formulation that simultane-ously partition, schedule, and do linear placement of tasks on such architectures. With our exact formulation, we prove the critical nature of placement constraints. We demonstrate that our heuris-tic generates high-quality schedules by comparing the results with the exact formulation for small tests and a popular, but placement-uanaware scheduling heuristic for larger tests. With a case study, we demonstrate extension of our approach to handle heterogenous architectures with specialized resources distributed between gen-eral purpose programmable logic columns. The execution time of our heuristic is very reasonable- task graphs with hundreds of nodes are processed in a couple of minutes