The Extended Partitioning Problem: Hardware/Software Mapping, Scheduling, and Implementation-bin Selection

In system-level design, applications are represented as task graphs where tasks (called nodes) have moderate to large granularity and each node has several implementation options differing in area and execution time. We define the extended partitioning problem as the joint determination of the mapping (hardware or software), the implementation option (called implementation bin), as well as the schedule, for each node, so that the overall area allocated to nodes in hardware is minimum and a deadline constraint is met. This problem is considerably harder (and richer) than the traditional binary partitioning problem that determines just the best mapping and schedule. Both binary and extended partitioning problems are constrained optimization problems and are NP-hard. We first present an efficient (O(N²)) heuristic, called GCLP, to solve the binary partitioning problem. The heuristic reduces the greediness associated with traditional list-scheduling algorithms by formulating a global m..