Schedulers-Driven approach for dynamic placement/scheduling of multiple DAGs onto SoPCs

With the advent of System on Programmable Chips (SoPCs), there is a serious need for placing and scheduling algorithms which can allow multiple Directed Acyclic Graphs (DAGs) structured applications to compete for the computational resources provided by SoPCs. A runtime scheme for distributed scheduling and placement of DAG-based real time tasks on SoPCs is described in this paper. In the proposed distributed approach, called Schedulers-Driven, each scheduler associated to a DAG makes its own placement/scheduling decisions and collaborates with the available placers corresponding to SoPCs in the system. The placers focus in managing free resource space for the requirements of elected tasks. Schedulers-Driven aims at optimizing the DAG slowdowns and reducing the rejection ratio of real-time DAGs. Other important goals are attained by this approach, which are the reduction of placement and scheduling overheads ensured by the techniques of prefetch and reuse, and the efficiency of resource utilization guaranteed by the reuse technique and the slickness of placement method.