Efficient ranking and selection in parallel computing environments
From MaRDI portal
Abstract: The goal of ranking and selection (R&S) procedures is to identify the best stochastic system from among a finite set of competing alternatives. Such procedures require constructing estimates of each system's performance, which can be obtained simultaneously by running multiple independent replications on a parallel computing platform. However, nontrivial statistical and implementation issues arise when designing R&S procedures for a parallel computing environment. Thus we propose several design principles for parallel R&S procedures that preserve statistical validity and maximize core utilization, especially when large numbers of alternatives or cores are involved. These principles are followed closely by our parallel Good Selection Procedure (GSP), which, under the assumption of normally distributed output, (i) guarantees to select a system in the indifference zone with high probability, (ii) runs efficiently on up to 1,024 parallel cores, and (iii) in an example uses smaller sample sizes compared to existing parallel procedures, particularly for large problems (over alternatives). In our computational study we discuss two methods for implementing GSP on parallel computers, namely the Message-Passing Interface (MPI) and Hadoop MapReduce and show that the latter provides good protection against core failures at the expense of a significant drop in utilization due to periodic unavoidable synchronization.
Recommendations
- Fully sequential procedures for large-scale ranking-and-selection problems in parallel computing environments
- Knockout-tournament procedures for large-scale ranking and selection in parallel computing environments
- On parallel policies for ranking and selection problems
- Ranking and selection for steady-state simulation: procedures and perspectives
- Combined variance reduction techniques in fully sequential selection procedures
Cites work
- A fully sequential procedure for indifference-zone selection in simulation
- A sequential procedure for neighborhood selection-of-the-best in optimization via simulation
- Analysis of parallel replicated simulations under a completion time constraint
- Bias Properties of Budget Constrained Simulations
- Discrete Event Simulations and Parallel Processing: Statistical Properties
- Fully sequential indifference‐zone selection procedures with variance‐dependent sampling
- Fully sequential procedures for large-scale ranking-and-selection problems in parallel computing environments
- Handbook of simulation optimization
- Handbooks in operations research and management science: Simulation
- On the Asymptotic Validity of Fully Sequential Selection Procedures for Steady-State Simulation
- On two-stage selection procedures and related probability-inequalities
- Optimization for simulation: theory vs. practice
- Optimization via simulation: A review
- Regret analysis of stochastic and nonstochastic multi-armed bandit problems
- Selecting a selection procedure
- Simulation budget allocation for further enhancing the efficiency of ordinal optimization
- The Asymptotic Efficiency of Simulation Estimators
- Using Common Random Numbers for Indifference-Zone Selection and Multiple Comparisons in Simulation
- Using Ranking and Selection to “Clean Up” after Simulation Optimization
- Using rngstreams for parallel random number generation in C++ and R
Cited in
(27)- Posterior-Based Stopping Rules for Bayesian Ranking-and-Selection Procedures
- Optimal budget allocation policy for tabu search in stochastic simulation optimization
- Distributed simulation: state-of-the-art and potential for operational research
- A simple randomized parallel algorithm for list-ranking
- Selecting the Best Simulated System: Thinking Differently About an Old Problem
- scientific article; zbMATH DE number 4064468 (Why is no real title available?)
- Using cache or credit for parallel ranking and selection
- Improved feature selection with simulation optimization
- Predicting the simulation budget in ranking and selection procedures
- On parallel policies for ranking and selection problems
- Fifty years of stochastic simulation: where we are and where we need to go
- MapRedRnS
- Dynamic Sampling Allocation Under Finite Simulation Budget for Feasibility Determination
- Asymptotic efficiency analysis on the modified Paulson's procedure with a PAC guarantee
- Parallel Adaptive Survivor Selection
- Ranking and Selection with Covariates for Personalized Decision Making
- Speeding Up Paulson’s Procedure for Large-Scale Problems Using Parallel Computing
- Simple Bayesian algorithms for best-arm identification
- scientific article; zbMATH DE number 5033869 (Why is no real title available?)
- Information theory for ranking and selection
- Simulation budget allocation for improving scheduling and routing of automated guided vehicles in warehouse management
- Blackbox simulation optimization
- Review of large-scale simulation optimization
- Knockout-tournament procedures for large-scale ranking and selection in parallel computing environments
- Solving Large-Scale Fixed-Budget Ranking and Selection Problems
- Fully sequential procedures for large-scale ranking-and-selection problems in parallel computing environments
- A unified framework for stochastic optimization
Describes a project that uses
Uses Software
This page was built for publication: Efficient ranking and selection in parallel computing environments
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4604911)
