Main Menu/
Search/
Help

Publications of the Ptolemy Group

#
The Extended Partitioning Problem

Summary of previous hardware/software design work
Asawaree Kalavade and Edward A. Lee,

"The Extended Partitioning Problem: Hardware/Software Mapping, Scheduling,
and Implementation-bin Selection,"
*Journal of Design Automation of Embedded Systems*,
special issue on System Partitioning Issues,
**submitted**.
Postscript version

## Abstract

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(N2)) heuristic, called GCLP, to solve the
binary partitioning problem. The heuristic reduces the greediness associated
with traditional list-scheduling algorithms by formulating a global measure,
called global criticality (GC). The GC measure also permits an adaptive
selection of the optimization objective at each step of the algorithm; since
the optimization problem is constrained by a deadline, either area or time
is optimized at a given step based on the value of GC. The selected objective
is used to determine the mapping of nodes that are "normal", i.e. nodes that
do not exhibit affinity for a particular mapping. To account for nodes that
are not "normal", we define "extremities" and "repellers". Extremities consume
disproportionate amounts of resources in hardware and software. Repellers are
inherently unsuitable to either hardware or software based on certain
structural properties. The mapping of extremities and repellers is determined
jointly by GC and their local preference.

We then present an efficient (O(N3 + N2B), for N nodes and B bins per node)
heuristic for extended partitioning, called MIBS, that alternately uses GCLP
and an implementation-bin selection procedure. The implementation-bin
selection procedure chooses, for a node with already determined mapping, an
implementation bin that maximizes the area-reduction gradient of as-yet
unmapped nodes. Solutions generated by both heuristics are shown to be
reasonably close to optimal. Extended partitioning generates considerably
smaller overall hardware as compared to binary partitioning.