Efficient Ranking And Selection In Parallel Computing Environments
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. This dissertation develops efficient parallel R&S procedures. In this dissertation, several design principles are proposed 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 the three parallel R&S procedures analyzed, each of which features a unique sampling and screening approach, and a specific statistical guarantee on the quality of the final solution. Finally, in our computational study we discuss three methods for implementing R&S procedures on parallel computers, namely the Message-Passing Interface (MPI), Hadoop MapReduce, and Apache Spark, and show that MPI performs the best while Spark provides good protection against core failures at the expense of a moderate drop in core utilization.
ranking and selection; simulation optimization; parallel computing
Martinez,Jose F.; Frazier,Peter
Ph.D. of Operations Research
Doctor of Philosophy
dissertation or thesis