Automatic Parallelization of Probabilistic Models with Varying Load Imbalance

Abstract

As scientists are designing increasingly complex and intricate models, the prominent way today to achieve acceptable execution time without sacrificing accuracy is through parallel computing. These techniques can improve execution time either on the level of the optimization methods or on the level of the model evaluations. This paper outlines an automatic par-allelization approach for the latter. Processor specific procedures with embedded communication primitives are generated from static schedules produced by an evolutionary algorithm. These are passed to an optimizing compiler to avoid the overhead of typical task runtime systems. The two key insights are that the parallel structure of probabilistic models is revealed when the data is combined with the model and that static schedules can be combined into more robust schedules that can deal with varying load imbalance. For this, LogP model parameters and execution time of each computational task are measured and fed into a discrete event simulator to estimate the running time on the target parallel system. Performance is evaluated with three pharmacological models with different characteristics. The first model lacks enough exploitable parallelism while up to approximately 6x and 8x improvements are achieved for the other models. Compared to a theoretical system with infinite processors and no communication delay, this equates to exploiting 66% and 99% of the available parallelism. Performance improves even when load imbalance varies.