Code-size minimization in multiprocessor real-time systems

Program code size is a critical factor in determining the manufacturing cost of many embedded systems, particularly those aimed at the extremely cost-conscious consumer market. However, the focus of most prior theoretical research on partitioning algorithms for real-time multiprocessor platforms has been on ensuring that the cumulative computing requirements of the tasks assigned to each processor does not exceed the processor's computing capacity. We consider the problem of task partitioning in multiprocessor platforms in order to minimize the total code size, in application systems in which there may be several different implementations of each task available, with each implementation having different code sizes and different computing requirements. We prove that the general problem is intractable, and present polynomial-time algorithms for solving (well-defined) special cases of the general problem.