Mathur, Sudhanshu and Morozov, Sergei (2009): Massively Parallel Computation Using Graphics Processors with Application to Optimal Experimentation in Dynamic Control.

PDF
MPRA_paper_16721.pdf Download (268Kb)  Preview 
Abstract
The rapid increase in the performance of graphics hardware, coupled with recent improvements in its programmability has lead to its adoption in many nongraphics applications, including wide variety of scientific computing fields. At the same time, a number of important dynamic optimal policy problems in economics are athirst of computing power to help overcome dual curses of complexity and dimensionality. We investigate if computational economics may benefit from new tools on a case study of imperfect information dynamic programming problem with learning and experimentation tradeoff that is, a choice between controlling the policy target and learning system parameters. Specifically, we use a model of active learning and control of linear autoregression with unknown slope that appeared in a variety of macroeconomic policy and other contexts. The endogeneity of posterior beliefs makes the problem difficult in that the value function need not be convex and policy function need not be continuous. This complication makes the problem a suitable target for massivelyparallel computation using graphics processors. Our findings are cautiously optimistic in that new tools let us easily achieve a factor of 15 performance gain relative to an implementation targeting singlecore processors and thus establish a better reference point on the computational speed vs. coding complexity tradeoff frontier. While further gains and wider applicability may lie behind steep learning barrier, we argue that the future of many computations belong to parallel algorithms anyway.
Item Type:  MPRA Paper 

Original Title:  Massively Parallel Computation Using Graphics Processors with Application to Optimal Experimentation in Dynamic Control 
Language:  English 
Keywords:  Graphics Processing Units, CUDA programming, Dynamic programming, Learning, Experimentation 
Subjects:  C  Mathematical and Quantitative Methods > C6  Mathematical Methods; Programming Models; Mathematical and Simulation Modeling > C63  Computational Techniques; Simulation Modeling C  Mathematical and Quantitative Methods > C8  Data Collection and Data Estimation Methodology; Computer Programs > C80  General 
Item ID:  16721 
Depositing User:  Sergei Morozov 
Date Deposited:  10. Aug 2009 10:43 
Last Modified:  23. Feb 2013 15:32 
References:  Abdelkhalek, A., A. Bilas, and A. Michaelides(2001): “Parallelization, optimization and performance analysis of portfolio choice models,” in Proceedings of the 2001 International Conference on Parallel Processing (ICPP01). Backus, J. (1977): “Can Programming be Liberated from the von Neumann Style?,” Communications of the ACM, 21(8), 613–641. Bargen, B., and P. Donnelly (1998): Inside DirectX, Microsoft Programming Series. Microsoft Press, Redmond, Washington. Beck, G. W., and V. Wieland (2002): “Learning and control in a changing economic environment,” Journal of Economic Dynamics and Control, 26(910), 1359–1377. Bennemann, C., M. W. Beinker, D. Eggloff, and M. Guckler (2008): “Teraflops for Games and Derivatives Pricing,” Wilmott Magazine, pp. 50–54. Bertsekas, D. P. (2001): Dynamic Programming and Optimal Control, vol. 2. Athena Scientific, Nashua, NH, 2 edn. (2005): Dynamic Programming and Optimal Control, vol. 1. Athena Scientific, Nashua, NH, 3 edn. Brent, R. P. (1973): Algorithms for Minimization without Derivatives. PrenticeHall, Englewood Cliffs. Brezzia, M., and T. L. Lai (2002): “Optimal learning and experimentation in bandit problems,” Journal of Economic Dynamics and Control, 27(1), 87–108. Buck, I. (2005): “Stream computing on graphics hardware,” Ph.D. Dissertation, Stanford University, Stanford, CA, USA. Chandra, R., R. Menon, L. Dagum, and D. Kohr (2000): Parallel Programming in OpenMP. Morgan Kaufmann. Chapman, B., G. Jost, and R. van der Paas (2007): Using OpenMP: Portable Shared Memory Parallel Programming, Scientific and Engineering Computation Series. MIT Press, Cambridge, MA. Chong, Y. Y., and D. F. Hendry (1986): “Econometric Evaluation of Linear Macroeconomic Models,” The Review of Economic Studies, 53(4), 671–690. Coleman, W. J. (1992): “Solving Nonlinear Dynamic Models on Parallel Computers,” Discussion Paper 66, Institute for Empirical Macroeconomics, Federal Reserve Bank of Minneapolis. Conn, A. R., N. I. M. Gould, and P. L. Toint (1997): “A Globally Convergent Augmented Lagrangian Barrier Algorithm for Optimization with General Inequality Constraints and Simple Bounds,” Mathematics of Computation, 66(217), 261–288. Creel, M. (2005): “UserFriendly Parallel Computations with Econometric Examples,” Computational Economics, 26(2), 107–128. Creel, M., and W. L. Goffe (2009): “Multicore CPUs, Clusters, and Grid Computing: A Tutorial,” Computational Economics, p. forthcoming. Doornik, J. A., D. F. Hendry, and N. Shephard (2002): “Computationallyintensive econometrics using a distributed matrixprogramming language,” Philosophical Transactions of the Royal Society of London, Series A, 360, 1245–1266. Doornik, J. A., N. Shephard, and D. F. Hendry (2006): “Parallel Computation in Econometrics: A Simplified Approach,” in Handbook of Parallel Computing and Statistics, pp. 449–476. Chapman & Hall/CRC. Easley, D., and N. M. Kiefer (1988): “Controlling a Stochastic Process with Unknown Parameters,” Econometrica, 56(5), 1045–1064. Ferrall, C. (2003): “Solving Finite Mixture Models in Parallel,” Computational Economics 0303003, EconWPA. Goffe, W. L., G. D. Ferrier, and J. Rogers (1994): “Global optimization of statistical functions with simulated annealing,” Journal of Econometrics, 60(12), 65–99. Goldberg, D. E. (1989): Genetic Algorithms in Search, Optimization and Machine Learning. AddisonWesley, Reading, MA. Gropp, W., E. Lusk, A. Skjellum, and R. Thakur (1999): Using MPI: Portable Parallel programming with Message Passing Interface, Scientific and Engineering Computation Series. MIT Press, Cambridge, MA, 2 edn. Horst, R., and P. M. Paradalos (eds.) (1994): Handbook of Global Optimization, vol. 1 of Nonconvex Optimization and Its Applications. Kluwer Academic Publishers, Dordrecht, The Netherlands. Judge, G. G., T.C. Lee, and R. C. Hill (1988): Introduction to the Theory and Practice of Econometrics. Wiley, New York, 2 edn. Kendrick, D. A. (1978): “Nonconvexities from probing an adaptive control problem,” Journal of Economic Letters, 1(4), 347–351. Kessenich, J., D. Baldwin, and R. Rost (2006): The OpenGL Shading LanguageKhronos Group. Kirk, D., and W. Hwu (2009): CUDA Programming. Kirkpatrick, S., C. D. Gelatt Jr., and M. P. Vecchi (1983): “Optimization by Simulated Annealing,” Science, 220(4598), 671–680. Kola, K., A. Chhabra, R. K. Thulasiram, and P. Thulasiraman (2006): “A Software Architecture Framework for Online Option Pricing,” in Proceedings of the 4th International Symposium on Parallel and Distributed Processing and Applications (ISPA06), vol. 4330 of Lecture Notes in Computer Science, pp. 747–759, Sorrento, Italy. Springer Verlag. Lagarias, J. C., J. A. Reeds, M. H. Wright, and P. E. Wright (1998): “Convergence Properties of the NelderMeade Simplex Method in Low Dimensions,” SIAM Journal of Optimization, 9(1), 112–147. Lewis, R. M., and V. Torczon (2002): “A Globally Convergent Augmented Lagrangian Pattern Search Algorithm for Optimization with General Constraints and Simple Bounds,” SIAM Journal on Optimization, 12(4), 1075–1089. Lindoff, B., and J. Holst (1997): “Suboptimal Dual Control of Stochastic Systems with TimeVarying Parameters,” mimeo, Department of Mathematical Statistics, Lund Institute of Technology. Morozov, S. (2008): “Learning and Active Control of Stationary Autoregression with Unknown Slope and Persistence,” Working paper, Stanford University. Morozov, S. (2009a): “Bayesian Active Learning and Control with Uncertain TwoPeriod Impulse Response,” Working paper, Stanford University. Morozov, S. (2009b): “Limits of Passive Learning in the Bayesian Active Learning Control of Drifting Coefficient Regression,” Working paper, Stanford University. Nagurney, A., T. Takayama, and D. Zhang (1995): “Massively parallel computation of spatial price equilibrium problems as dynamical systems,” Journal of Economic Dynamics and Control, 19(12), 3–37. Nagurney, A., and D. Zhang (1998): “A massively parallel implementation of discretetime algorithm for the computation of dynamic elastic demand and traffic problems modeled as projected dynamical systems,” Journal of Economic Dynamics and Control, 22(8 9), 1467–1485. Nelder, J. A., and R. Mead (1965): “A simplex method for function minimization,” Computer Journal, 7, 308–313. NVIDIA Corporation (2008): NVIDIA CUDA Compute Unified Device Architecture: Programming Guide NVIDIA Corporation, Santa Clara, CA, 2 edn. Paradalos, P. M., and H. E. Romeijn (eds.) (2002): Handbook of Global Optimization, vol. 2 of Nonconvex Optimization and Its Applications. Kluwer Academic Publishers, Dordrecht, The Netherlands. Pflug, G. C., and A. Swietanowski (2000): “Selected parallel optimization methods for financial management under uncertainty,” Parallel Computing, 26(1), 3–25. Prescott, E. C. (1972): “The MultiPeriod Control Problem Under Uncertainty,” Econometrica, 40(6), 1043–1058. Rahman, M. R., R. K. Thulasiram, and P. Thulasiraman (2002): “Forecasting Stock Prices using Neural Networks on a Beowulf Cluster,” in Proceedings of the Fourteenth IASTED International Conference on Parallel and Distributed Computing and Systems (PDCS 2002), ed. by S. Akl, and T.Gonzalez, pp. 470–475, Cambridge, MA USA. IASTED, MIT Press. Seiler, L., D. Carmean, E. Sprangle, T. Forsyth, M. Abrash, P. Dubey, S. Junkins, A. Lake, J. Sugerman, R. Cavin, R. Espasa, E. Grochowski, T. Juan, and P. Hanrahan (2008): “Larrabee: A ManyCore x86 Architecture for Visual Computing,” ACM Transactions on Graphics, 27(3), 15 pages. Sims, C. A., D. F. Waggoner, and T. Zha (2009): “Methods for Inference in LargeScale Multiple Equation MarkovSwitching Models,” Journal of Econometrics, forthcoming. Spendley, W., G. R. Hext, and F. R. Himsworth (1962): “Sequential application of simplex designs in optimization and evolutionary design,” Technometrics, 4, 441–461. Svensson, L. E. O. (1997): “Optimal Inflation Targets, ’Conservative’ Central banks, and Linear Inflation Contracts,” American Economic Review, 87(1), 96–114. Swann, C. A. (2002): “Maximum Likelihood Estimation Using Parallel Computing: An Introduction to MPI,” Computational Economics, 19(2), 145–178. The Portland Group (2008): PGI Fortran & C Accelerator Compilers and Programming Model Technology PreviewThe Portalnd Group, Version 0.7. Wieland, V. (2000): “Learning by Doing and the Value of Optimal Experimentation,” Journal of Economic Dynamics and Control, 24(4), 501–535. Zabinsky, Z. B. (2005): Stochastic Adaptive Search for Global Optimization. Springer. Zenios, S. A. (1999): “Highperformance computing in finance: The last 10 years and the next,” Parallel Computing, 25(1314), 2149–2175. 
URI:  http://mpra.ub.unimuenchen.de/id/eprint/16721 