The Extended Partitioning Problem: Hardware/Software Mapping
and Implementation-Bin Selection
by Asawaree Kalavade and Edward A. Lee
"The Extended Partitioning Problem: Hardware/Software Mapping
and Implementation-Bin Selection,"
to appear,
Proc. Sixth International Workshop on Rapid Systems Prototyping,
June, 1995.
ABSTRACT
The extended partitioning problem is the joint problem of
mapping nodes in a precedence graph to hardware or software,
and within each mapping, selecting an appropriate implementation
for each node. The end-goal is to minimize the hardware area,
subject to architectural and performance constraints. This is
an NP-complete problem; we present an efficient heuristic called
MIBS to solve it. The MIBS algorithm solves the extended partitioning
problem by decomposing it into an iterative process consisting of
two steps: mapping and implementation-bin selection. The GCLP
algorithm computes a mapping by using an adaptive optimization
objective at each iteration. This objective is selected on the
basis of a global time criticality measure and local optimality
measures. The IBS algorithm solves the implementation-bin selection
problem. It uses a bin sensitivity measure, which correlates the
implementation-bin motion with the overall hardware area reduction,
to determine the implementation bin of a node for a given mapping.
Experimental results indicate that the added dimension of design
flexibility (offered by implementation bins) can be used effectively
in partitioning to reduce the overall area. The MIBS algorithm has
O(|N|^3) complexity, with a solution quality comparable to that of ILP.