TY - GEN
T1 - Scaling exact multi-objective combinatorial optimization by parallelization
AU - Guo, Jianmei
AU - Zulkoski, Edward
AU - Olaechea, Rafael
AU - Rayside, Derek
AU - Czarnecki, Krzysztof
AU - Apel, Sven
AU - Atlee, Joanne M.
N1 - Publisher Copyright:
© 2014 ACM.
PY - 2014
Y1 - 2014
N2 - Multi-Objective Combinatorial Optimization (MOCO) is fundamental to the development and optimization of software systems. We propose five novel parallel algorithms for solving MOCO problems exactly and efficiently. Our algorithms rely on off-the-shelf solvers to search for exact Pareto-optimal solutions, and they parallelize the search via collaborative communication, divide-and-conquer, or both. We demonstrate the feasibility and performance of our algorithms by experiments on three case studies of software-system designs. A key finding is that one algorithm, which we call FS-GIA, achieves substantial (even super-linear) speedups that scale well up to 64 cores. Furthermore, we analyze the performance bottlenecks and opportunities of our parallel algorithms, which facilitates further research on exact, parallel MOCO.
AB - Multi-Objective Combinatorial Optimization (MOCO) is fundamental to the development and optimization of software systems. We propose five novel parallel algorithms for solving MOCO problems exactly and efficiently. Our algorithms rely on off-the-shelf solvers to search for exact Pareto-optimal solutions, and they parallelize the search via collaborative communication, divide-and-conquer, or both. We demonstrate the feasibility and performance of our algorithms by experiments on three case studies of software-system designs. A key finding is that one algorithm, which we call FS-GIA, achieves substantial (even super-linear) speedups that scale well up to 64 cores. Furthermore, we analyze the performance bottlenecks and opportunities of our parallel algorithms, which facilitates further research on exact, parallel MOCO.
KW - Multi-objective combinatorial optimization
KW - Parallelization
UR - https://www.scopus.com/pages/publications/84908642539
U2 - 10.1145/2642937.2642971
DO - 10.1145/2642937.2642971
M3 - 会议稿件
AN - SCOPUS:84908642539
T3 - ASE 2014 - Proceedings of the 29th ACM/IEEE International Conference on Automated Software Engineering
SP - 409
EP - 420
BT - ASE 2014 - Proceedings of the 29th ACM/IEEE International Conference on Automated Software Engineering
PB - Association for Computing Machinery, Inc
T2 - 29th ACM/IEEE International Conference on Automated Software Engineering, ASE 2014
Y2 - 15 September 2014 through 19 September 2014
ER -