Title: Partitioning bin-packing algorithms for distributed real-time systems

Authors: Dionisio De Niz, Raj Rajkumar

Addresses: Software Engineering Institute, Carnegie Mellon University, Pittsburgh PA, USA. ' Real-Time and Multimedia Systems Laboratory, Electrical and Computer Engineering, Carnegie Mellon University, Pittsburgh PA, USA

Abstract: In this paper, we study extensions to bin packing algorithms to pack software modules into processors in real-time systems. We refer to this approach as Partitioning Bin-Packing. In this study, we analytically show that with partitioning bin-packing techniques the number of bins required by traditional bin packing can be reduced. We also evaluate heuristics to minimise both the number of processors (bins) needed and the network bandwidth required by communicating software modules that are partitioned across different processors. We find that a significant reduction in the number of bins is possible. Finally, different heuristics lead to different tradeoffs in processing vs. network needs.

Keywords: real-time systems; partitioning bin packing; thread allocation; deployment; network bandwidth; embedded systems; distributed systems; software modules.

DOI: 10.1504/IJES.2006.014855

International Journal of Embedded Systems, 2006 Vol.2 No.3/4, pp.196 - 208

Published online: 12 Aug 2007 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article