[go: up one dir, main page]
IDEAS home Printed from https://ideas.repec.org/p/pra/mprapa/16721.html
   My bibliography  Save this paper

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

Author

Listed:
  • Mathur, Sudhanshu
  • Morozov, Sergei
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.

Suggested Citation

  • Mathur, Sudhanshu & Morozov, Sergei, 2009. "Massively Parallel Computation Using Graphics Processors with Application to Optimal Experimentation in Dynamic Control," MPRA Paper 16721, University Library of Munich, Germany.
    • Handle: RePEc:pra:mprapa:16721
    as

    Download full text from publisher

    File URL: https://mpra.ub.uni-muenchen.de/16721/1/MPRA_paper_16721.pdf
    File Function: original version
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Svensson, Lars E O, 1997. "Optimal Inflation Targets, "Conservative" Central Banks, and Linear Inflation Contracts," American Economic Review, American Economic Association, vol. 87(1), pages 98-114, March.
    2. Yock Y. Chong & David F. Hendry, 1986. "Econometric Evaluation of Linear Macro-Economic Models," The Review of Economic Studies, Review of Economic Studies Ltd, vol. 53(4), pages 671-690.
    3. Wieland, Volker, 2000. "Learning by doing and the value of optimal experimentation," Journal of Economic Dynamics and Control, Elsevier, vol. 24(4), pages 501-534, April.
    4. Nagurney, Anna & Takayama, Takashi & Zhang, Ding, 1995. "Massively parallel computation of spatial price equilibrium problems as dynamical systems," Journal of Economic Dynamics and Control, Elsevier, vol. 19(1-2), pages 3-37.
    5. Michael Creel, 2005. "User-Friendly Parallel Computations with Econometric Examples," UFAE and IAE Working Papers 637.05, Unitat de Fonaments de l'Anàlisi Econòmica (UAB) and Institut d'Anàlisi Econòmica (CSIC).
    6. Sims, Christopher A. & Waggoner, Daniel F. & Zha, Tao, 2008. "Methods for inference in large multiple-equation Markov-switching models," Journal of Econometrics, Elsevier, vol. 146(2), pages 255-274, October.
    7. Goffe, William L. & Ferrier, Gary D. & Rogers, John, 1994. "Global optimization of statistical functions with simulated annealing," Journal of Econometrics, Elsevier, vol. 60(1-2), pages 65-99.
    8. Coleman, Wilbur John, II, 1993. "Solving Nonlinear Dynamic Models on Parallel Computers," Journal of Business & Economic Statistics, American Statistical Association, vol. 11(3), pages 325-330, July.
    9. Nagurney, Anna & Zhang, Ding, 1998. "A massively parallel implementation of a discrete-time algorithm for the computation of dynamic elastic demand traffic problems modeled as projected dynamical systems," Journal of Economic Dynamics and Control, Elsevier, vol. 22(8-9), pages 1467-1485, August.
    10. Michael Creel, 2005. "User-Friendly Parallel Computations with Econometric Examples," Computational Economics, Springer;Society for Computational Economics, vol. 26(2), pages 107-128, October.
    11. Kendrick, David, 1978. "Non-convexities from probing in adaptive control problems," Economics Letters, Elsevier, vol. 1(4), pages 347-351.
    12. Beck, Gunter W. & Wieland, Volker, 2002. "Learning and control in a changing economic environment," Journal of Economic Dynamics and Control, Elsevier, vol. 26(9-10), pages 1359-1377, August.
    13. Brezzi, Monica & Lai, Tze Leung, 2002. "Optimal learning and experimentation in bandit problems," Journal of Economic Dynamics and Control, Elsevier, vol. 27(1), pages 87-108, November.
    14. Swann, Christopher A, 2002. "Maximum Likelihood Estimation Using Parallel Computing: An Introduction to MPI," Computational Economics, Springer;Society for Computational Economics, vol. 19(2), pages 145-178, April.
    15. Anna Nagurney & Ding Zhang, "undated". "Massively Parallel Computation of Dynamic Traffic Problems Modeled as Projected Dynamical Systems," Computing in Economics and Finance 1996 _039, Society for Computational Economics.
    16. Jurgen A. Doornik & David F. Hendry & Neil Shephard, "undated". "Computationally-intensive Econometrics using a Distributed Matrix-programming Language," Economics Papers 2001-W22, Economics Group, Nuffield College, University of Oxford.
    17. A. Abdelkhalek, A. Bilas and A. Michaelides, 2001. "Parallelization and Performance of Portfolio Choice Models," Computing in Economics and Finance 2001 114, Society for Computational Economics.
    18. Prescott, Edward C, 1972. "The Multi-Period Control Problem Under Uncertainty," Econometrica, Econometric Society, vol. 40(6), pages 1043-1058, November.
    19. Christopher Ferrall, 2003. "Solving Finite Mixture Models in Parallel," Computational Economics 0303003, University Library of Munich, Germany.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Casarin, Roberto & Grassi, Stefano & Ravazzolo, Francesco & van Dijk, Herman K., 2015. "Parallel Sequential Monte Carlo for Efficient Density Combination: The DeCo MATLAB Toolbox," Journal of Statistical Software, Foundation for Open Access Statistics, vol. 68(i03).
    2. Roberto Casarin & Stefano Grassi & Francesco Ravazzolo & Herman K. van Dijk, 2015. "Dynamic predictive density combinations for large data sets in economics and finance," Working Paper 2015/12, Norges Bank.
    3. Federico Bassetti & Roberto Casarin & Francesco Ravazzolo, 2019. "Density Forecasting," BEMPS - Bozen Economics & Management Paper Series BEMPS59, Faculty of Economics and Management at the Free University of Bozen.
    4. Michael C. Hatcher & Eric M. Scheffel, 2016. "Solving the Incomplete Markets Model in Parallel Using GPU Computing and the Krusell–Smith Algorithm," Computational Economics, Springer;Society for Computational Economics, vol. 48(4), pages 569-591, December.
    5. John Gibson & James P Henson, 2016. "Getting the most from MATLAB: ditching canned routines and embracing coder," Economics Bulletin, AccessEcon, vol. 36(4), pages 2519-2525.
    6. Nalan Baştürk & Stefano Grassi & Lennart Hoogerheide & Herman K. Van Dijk, 2016. "Parallelization Experience with Four Canonical Econometric Models Using ParMitISEM," Econometrics, MDPI, vol. 4(1), pages 1-20, March.
    7. Matt Dziubinski & Stefano Grassi, 2014. "Heterogeneous Computing in Economics: A Simplified Approach," Computational Economics, Springer;Society for Computational Economics, vol. 43(4), pages 485-495, April.
    8. Nalan Baştürk & Roberto Casarin & Francesco Ravazzolo & Herman K. Van Dijk, 2016. "Computational Complexity and Parallelization in Bayesian Econometric Analysis," Econometrics, MDPI, vol. 4(1), pages 1-3, February.
    9. Lilia Maliar, 2015. "Assessing gains from parallel computation on a supercomputer," Economics Bulletin, AccessEcon, vol. 35(1), pages 159-167.
    10. Yongyang Cai & Kenneth Judd & Greg Thain & Stephen Wright, 2015. "Solving Dynamic Programming Problems on a Computational Grid," Computational Economics, Springer;Society for Computational Economics, vol. 45(2), pages 261-284, February.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Morozov, Sergei & Mathur, Sudhanshu, 2009. "Massively parallel computation using graphics processors with application to optimal experimentation in dynamic control," MPRA Paper 30298, University Library of Munich, Germany, revised 04 Apr 2011.
    2. Sergei Morozov & Sudhanshu Mathur, 2012. "Massively Parallel Computation Using Graphics Processors with Application to Optimal Experimentation in Dynamic Control," Computational Economics, Springer;Society for Computational Economics, vol. 40(2), pages 151-182, August.
    3. Jurgen A. Doornik & Neil Shephard & David F. Hendry, 2004. "Parallel Computation in Econometrics: A Simplified Approach," Economics Papers 2004-W16, Economics Group, Nuffield College, University of Oxford.
    4. Michael Creel & William Goffe, 2008. "Multi-core CPUs, Clusters, and Grid Computing: A Tutorial," Computational Economics, Springer;Society for Computational Economics, vol. 32(4), pages 353-382, November.
    5. Lilia Maliar, 2015. "Assessing gains from parallel computation on a supercomputer," Economics Bulletin, AccessEcon, vol. 35(1), pages 159-167.
    6. Kendrick, David A., 2005. "Stochastic control for economic models: past, present and the paths ahead," Journal of Economic Dynamics and Control, Elsevier, vol. 29(1-2), pages 3-30, January.
    7. Beck, Gunter W. & Wieland, Volker, 2002. "Learning and control in a changing economic environment," Journal of Economic Dynamics and Control, Elsevier, vol. 26(9-10), pages 1359-1377, August.
    8. David Kendrick & Hans Amman, 2006. "A Classification System for Economic Stochastic Control Models," Computational Economics, Springer;Society for Computational Economics, vol. 27(4), pages 453-481, June.
    9. Koulovatianos, Christos & Mirman, Leonard J. & Santugini, Marc, 2009. "Optimal growth and uncertainty: Learning," Journal of Economic Theory, Elsevier, vol. 144(1), pages 280-295, January.
    10. Leonard J. Mirman & Kevin Reffett & Marc Santugini, 2016. "On learning and growth," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 61(4), pages 641-684, April.
    11. Tim Willems, 2017. "Actively Learning by Pricing: A Model of an Experimenting Seller," Economic Journal, Royal Economic Society, vol. 127(604), pages 2216-2239, September.
    12. Yongyang Cai & Kenneth Judd & Greg Thain & Stephen Wright, 2015. "Solving Dynamic Programming Problems on a Computational Grid," Computational Economics, Springer;Society for Computational Economics, vol. 45(2), pages 261-284, February.
    13. Donghoon Lee & Matthew Wiswall, 2007. "A Parallel Implementation of the Simplex Function Minimization Routine," Computational Economics, Springer;Society for Computational Economics, vol. 30(2), pages 171-187, September.
    14. Hans M. Amman & Marco Paolo Tucci, 2018. "How active is active learning: value function method vs an approximation method," Department of Economics University of Siena 788, Department of Economics, University of Siena.
    15. Hans Amman & David Kendrick, 2014. "Comparison of policy functions from the optimal learning and adaptive control frameworks," Computational Management Science, Springer, vol. 11(3), pages 221-235, July.
    16. H.M. Amman & D.A. Kendrick, 2012. "Conjectures on the policy function in the presence of optimal experimentation," Working Papers 12-09, Utrecht School of Economics.
    17. Volker Wieland, "undated". "Monetary Policy and Uncertainty about the Natural Unemployment Rate," Computing in Economics and Finance 1997 11, Society for Computational Economics.
    18. Cosimano, Thomas F., 2008. "Optimal experimentation and the perturbation method in the neighborhood of the augmented linear regulator problem," Journal of Economic Dynamics and Control, Elsevier, vol. 32(6), pages 1857-1894, June.
    19. In Chang Hwang, 2016. "Active learning and optimal climate policy," EcoMod2016 9611, EcoMod.

    More about this item

    Keywords

    Graphics Processing Units; CUDA programming; Dynamic programming; Learning; Experimentation;
    All these keywords.

    JEL classification:

    • C63 - Mathematical and Quantitative Methods - - Mathematical Methods; Programming Models; Mathematical and Simulation Modeling - - - Computational Techniques
    • C80 - Mathematical and Quantitative Methods - - Data Collection and Data Estimation Methodology; Computer Programs - - - General

    NEP fields

    This paper has been announced in the following NEP Reports:

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:pra:mprapa:16721. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Joachim Winter (email available below). General contact details of provider: https://edirc.repec.org/data/vfmunde.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.