A new graph structure for hardware-software partitioning of heterogeneous systems

We present a new graph representation, DADGP (directed acyclic data dependency graph with precedence) that extends the well-known directed acyclic graph (DAG) structure. DADGP is suitable for partitioning heterogeneous systems due to its data and precedence dependency features of processes. The partitioning technique described exposes parallelism among tasks and minimizes the overall system execution time. The DADGP-based system partitioning method starts with a single CPU software solution, finds the longest delay path in the DADGP structure and tries to map its nodes to dedicated hardware to minimize the execution time of the target system. Exposing parallelism simplifies the partitioning process and reduces the overall system cost.