TY - GEN
T1 - Multiplicative weights algorithms for parallel automated software repair
AU - Renzullo, Joseph
AU - Weimer, Westley
AU - Forrest, Stephanie
N1 - Funding Information:
We gratefully acknowledge the partial support of NSF (CCF 1763674, CCF 1908633, IOS 2029696), DARPA (FA8750-19C-0003, N6600120C4020), AFRL (FA8750-19-1-0501), and the Santa Fe Institute.
Publisher Copyright:
© 2021 IEEE.
PY - 2021/5
Y1 - 2021/5
N2 - Multiplicative Weights Update (MWU) algorithms are a form of online learning that is applied to multi-armed bandit problems. Such problems involve allocating a fixed number of trials among multiple options to maximize cumulative payoff. MWU is a popular and effective method for dynamically balancing the trade-off between exploring the value of new options and exploiting the information already gained. However, no clear strategy exists to help practitioners choose which of the several algorithmic designs within this family to deploy. In this paper, three variants of parallel MWU algorithms are considered: Two parallel variants that rely on global memory, and one variant that uses distributed memory. The three variants are first analyzed theoretically, and then their effectiveness is assessed empirically on the task of estimating distributions in the context of stochastic search for repairs to bugs in software. Earlier work on APR suffers from various inefficiencies, and the paper shows how to decompose the problem into two stages: one that is embarrassingly parallel and one that is amenable to MWU. We then model the cost of each MWU variant and derive the conditions under which it is likely to be preferred in practice. We find that all three MWU algorithms achieve accuracy above 90% but that there are significant differences in runtime and total cost. When 90% accuracy is sufficient and evaluating options is expensive, such as in our use case, we find that the algorithm that uses global memory and has high communication cost outperforms the other two. We analyze the reasons for this surprising result.
AB - Multiplicative Weights Update (MWU) algorithms are a form of online learning that is applied to multi-armed bandit problems. Such problems involve allocating a fixed number of trials among multiple options to maximize cumulative payoff. MWU is a popular and effective method for dynamically balancing the trade-off between exploring the value of new options and exploiting the information already gained. However, no clear strategy exists to help practitioners choose which of the several algorithmic designs within this family to deploy. In this paper, three variants of parallel MWU algorithms are considered: Two parallel variants that rely on global memory, and one variant that uses distributed memory. The three variants are first analyzed theoretically, and then their effectiveness is assessed empirically on the task of estimating distributions in the context of stochastic search for repairs to bugs in software. Earlier work on APR suffers from various inefficiencies, and the paper shows how to decompose the problem into two stages: one that is embarrassingly parallel and one that is amenable to MWU. We then model the cost of each MWU variant and derive the conditions under which it is likely to be preferred in practice. We find that all three MWU algorithms achieve accuracy above 90% but that there are significant differences in runtime and total cost. When 90% accuracy is sufficient and evaluating options is expensive, such as in our use case, we find that the algorithm that uses global memory and has high communication cost outperforms the other two. We analyze the reasons for this surprising result.
KW - Automated Program Repair
KW - Multiplicative Weights Update
KW - Online Learning
UR - http://www.scopus.com/inward/record.url?scp=85113478831&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85113478831&partnerID=8YFLogxK
U2 - 10.1109/IPDPS49936.2021.00107
DO - 10.1109/IPDPS49936.2021.00107
M3 - Conference contribution
AN - SCOPUS:85113478831
T3 - Proceedings - 2021 IEEE 35th International Parallel and Distributed Processing Symposium, IPDPS 2021
SP - 984
EP - 993
BT - Proceedings - 2021 IEEE 35th International Parallel and Distributed Processing Symposium, IPDPS 2021
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 35th IEEE International Parallel and Distributed Processing Symposium, IPDPS 2021
Y2 - 17 May 2021 through 21 May 2021
ER -