Using Cache or Credit for Parallel Ranking and Selection
Open Access
- 26 October 2023
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Modeling and Computer Simulation
- Vol. 33 (4) , 1-28
Abstract
In this article, we focus on ranking and selection procedures that sequentially allocate replications to systems by applying some acquisition function. We propose an acquisition function, called gCEI, which exploits the gradient of the complete expected improvement with respect to the number of replications. We prove that the gCEI procedure, which adopts gCEI as the acquisition function in a serial computing environment, achieves the asymptotically optimal static replication allocation of Glynn and Juneja in the limit under a normality assumption. We also propose two procedures, called caching and credit, that extend any acquisition-function-based procedure in a serial environment into both synchronous and asynchronous parallel environments. While allocating replications to systems, both procedures use persistence forecasts for the unavailable outputs of the currently running replications, but differ in usage of the available outputs. We prove that, under certain assumptions, the caching procedure achieves the same asymptotic allocation as in the serial environment. A similar result holds for the credit procedure using gCEI as the acquisition function. In terms of efficiency and effectiveness, the credit procedure empirically performs as well as the caching procedure, despite not carefully controlling the output history as the caching procedure does, and is faster than the serial version without any number-of-replications penalty due to using persistence forecasts. Both procedures are designed to solve small-to-medium-sized problems on computers with a modest number of processors, such as laptops and desktops as opposed to high-performance clusters, and are superior to state-of-the-art parallel procedures in this setting.Keywords
Funding Information
- National Science Foundation (DMS-1854562, DMS-1854659)
This publication has 20 references indexed in Scilit:
- Parallel Ranking and Selection2017
- Efficient Ranking and Selection in Parallel Computing EnvironmentsOperations Research, 2017
- Myopic Allocation Policy With Asymptotically Optimal Sampling RateIEEE Transactions on Automatic Control, 2016
- Best-arm identification algorithms for multi-armed bandits in the fixed confidence setting2014
- Web Services-Based Parallel Replicated Discrete Event Simulation for Large-Scale Simulation OptimizationSIMULATION, 2009
- A Knowledge-Gradient Policy for Sequential Information CollectionSIAM Journal on Control and Optimization, 2008
- Selecting a Selection ProcedureManagement Science, 2007
- Control variates for screening, selection, and estimation of the bestACM Transactions on Modeling and Computer Simulation, 2006
- Distributed web-based simulation experiments for optimizationSimulation Practice and Theory, 2001
- A fully sequential procedure for indifference-zone selection in simulationACM Transactions on Modeling and Computer Simulation, 2001