Massively Parallel Computation Using Graphics Processors with Application to Optimal Experimentation in Dynamic Control

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

Abstract

The rapid increase in the performance of graphics hardware, coupled with recent improvements in its programmability has lead to its adoption in many non-graphics 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 trade-off 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 massively-parallel 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 single-core processors and thus establish a better reference point on the computational speed vs. coding complexity trade-off 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
• 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

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(9-10), 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. Prentice-Hall, 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): “User-Friendly Parallel Computations with Econometric Examples,” Computational Economics, 26(2), 107–128.

Creel, M., and W. L. Goffe (2009): “Multi-core CPUs, Clusters, and Grid Computing: A Tutorial,” Computational Economics, p. forthcoming.

Doornik, J. A., D. F. Hendry, and N. Shephard (2002): “Computationally-intensive econometrics using a distributed matrix-programming 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(1-2), 65–99.

Goldberg, D. E. (1989): Genetic Algorithms in Search, Optimization and Machine Learning. Addison-Wesley, 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): “Non-convexities 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 On-line Option Pricing,” in Proceedings of the 4th International Symposium on Parallel and Distributed Processing and Applications (ISPA-06), 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 Nelder-Meade 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 Time-Varying 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 Two-Period 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(1-2), 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 Multi-Period 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 Many-Core 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 Large-Scale Multiple Equation Markov-Switching 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): “High-performance computing in finance: The last 10 years and the next,” Parallel Computing, 25(13-14), 2149–2175.