Multi-stage Benders decomposition for optimizing multicore architectures. (English) Zbl 1142.68506

Benini, Luca; Lombardi, Michele; Mantovani, Marco; Milano, Michela; Ruggiero, Martino

Perron, Laurent (ed.) et al., Integration of AI and OR techniques in constraint programming for combinatorial optimization problems. 5th international conference, CPAIOR 2008 Paris, France, May 20–23, 2008. Proceedings. Berlin: Springer (ISBN 978-3-540-68154-0/pbk). Lecture Notes in Computer Science 5015, 36-50 (2008).

Summary: Software optimization for multicore architectures is one of the most critical challenges in today’s high-end computing. In this paper we focus on a well-known multicore platform, namely the Cell BE processor, and we address the problem of allocating and scheduling its processors, communication channels and memories, with the goal of minimizing application execution time.
We have developed a complete optimization strategy based on Benders’ decomposition. Unfortunately, a traditional two-stage decomposition produces unbalanced components: the allocation part is difficult, while the scheduling part is much easier. To address this issue, we have developed a multi-stage decomposition, which is a recursive application of standard Logic based Benders’ Decomposition (LBD). Our experiments demonstrate that this approach is very effective in obtaining balanced sub-problems and in reducing the runtime of the optimizer.
For the entire collection see [Zbl 1136.68010].

MSC:

68T20	Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
68M07	Mathematical problems of computer architecture
68M20	Performance evaluation, queueing, and scheduling in the context of computer systems