Hardware-Software Multi-Level Partitioning for Distributed Embedded Multiprocessor Systems

Trong-Yen Lee
Pao-Ann Hsiung
Sao-Jie Chen
Department of Electrical Engineering
Deparment of Computer Science and Information Engineering
Department of Electrical Engineering
National Taiwan University, Taipei, Taiwan.
National Chung Cheng University, Chiayi, Taiwan.
National Taiwan University, Taipei, Taiwan.
( IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences,
IEICE Publishers, Japan, accepted in August 2000.)


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