Affiliations: University of Michigan, Ann Arbor, MI 48109, USA
Note: [] E-mail: oehmke@engin.umich.edu
Abstract: We present a scalable, high-performance solution to multidimensional
recurrences that arise in adaptive statistical designs. Adaptive designs are an
important class of learning algorithms for a stochastic environment, and we
focus on the problem of optimally assigning patients to treatments in clinical
trials. While adaptive designs have significant ethical and cost advantages,
they are rarely utilized because of the complexity of optimizing and analyzing
them. Computational challenges include massive memory requirements, few
calculations per memory access, and multiply-nested loops with dynamic indices.
We analyze the effects of various parallelization options, and while standard
approaches do not work well, with effort an efficient, highly scalable program
can be developed. This allows us to solve problems thousands of times more
complex than those solved previously, which helps make adaptive designs
practical. Further, our work applies to many other problems involving neighbor
recurrences, such as generalized string matching.
