Hardware-Software Multi-Level Partitioning for Distributed Embedded
Multiprocessor Systems
Abstract
A novel Multi-Level Partitioning (MLP) technique taking into account
real-world constraints for hardware-software partitioning in
Distributed Embedded Multiprocessor Systems (DEMS) is proposed.
This MLP algorithm uses a gradient metric based on hardware-software cost and
performance as the core metric for selection of optimal partitions and consists
of three nested levels. The innermost level is a simple binary search
that allows quick evaluations of a large number of possible partitions.
The middle level iterates over different possible allocations of processors
(that execute software) to subsystems. The outermost level iterates over the
number of processors and the hardware cost range. Heuristics are applied to each
level to avoid the expensive exhaustive search. The application of MLP as a
recently purposed Distributed Embedded System Codesign (DESC)
methodology shows its feasibility. Comparisons between real-world examples
partitioned using MLP and using other existing techniques demonstrate
contrasting strengths of MLP. Sharing, clustering, and hierarchical system
model are some important features of MLP, which contribute towards producing
more optimal partition results.
Keywords: distributed embedded multiprocessor system, multi-level
partitioning, codesign, clustering, sharing