Lin, Tsung-HanTarsa, StephenKung, H.2014-03-052013Lin, Tsung-Han, Stephen J. Tarsa, and H.T. Kung. 2013 "Parallelization Primitives for Dynamic Sparse Computations." In Proceedings of the 5th USENIX Workshop on Hot Topics in Parallelism (HotPar'13), June 24-25, 2013, San Jose, CA: 1-7.http://nrs.harvard.edu/urn-3:HUL.InstRepos:11859321We characterize a general class of algorithms common in machine learning, scientific computing, and signal processing, whose computational dependencies are both sparse, and dynamically defined throughout execution. Existing parallel computing runtimes, like MapReduce and GraphLab, are a poor fit for this class because they assume statically defined dependencies for resource allocation and scheduling decisions. As a result, changing load characteristics and straggling compute units degrade performance significantly. However, we show that the sparsity of computational dependencies and these algorithms’ natural error tolerance can be exploited to implement a flexible execution model with large efficiency gains, using two simple primitives: selective push-pull and statistical barriers. With reconstruction for compressive time-lapse MRI as a motivating application, we deploy a large Orthogonal Matching Pursuit (OMP) computation on Amazon’s EC2 cluster to demonstrate a 19x speedup over current static execution models.en-USConference Paper2014-01-03Tsung-Han Lin, Stephen J. Tarsa, and H.T. Kung2014-03-05