×

Multigrid solvers in reconfigurable hardware. (English) Zbl 1131.65096

Summary: The problem of finding the solution of partial differential equations plays a central role in modeling real world problems. Over the past years, multigrid solvers have shown their robustness over other techniques, due to its high convergence rate which is independent of the problem size. For this reason, many attempts for exploiting the inherent parallelism of multigrid have been made to achieve the desired efficiency and scalability of the method. Yet, most efforts fail in this respect due to many factors (time, resources) governed by software implementations.
In this paper, we present a hardware implementation of the V-cycle multigrid method for finding the solution of a 2D-Poisson equation. We use Handel-C to implement our hardware design, which we map onto available field programmable gate arrays (FPGAs). We analyze the implementation performance using the FPGA vendor’s tools. We demonstrate the robustness of multigrid over other similar iterative solvers, such as Jacobi and successive over relaxation (SOR), in both hardware and software. We compare our findings with a C++ version of each algorithm. The obtained results show better performance when compared to existing software versions.

MSC:

65N55 Multigrid methods; domain decomposition for boundary value problems involving PDEs
35J05 Laplace operator, Helmholtz equation (reduced wave equation), Poisson equation
65F10 Iterative numerical methods for linear systems
65N06 Finite difference methods for boundary value problems involving PDEs
65N12 Stability and convergence of numerical methods for boundary value problems involving PDEs
65Y05 Parallel numerical computation
65Y15 Packaged methods for numerical algorithms
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Altera \(\langle;\) http://www.altera.com \(\rangle;\).; Altera \(\langle;\) http://www.altera.com \(\rangle;\).
[2] N. Bagherzade, F. Kurdahi, H. Singh, G. Lu, M. Lee, E. Filho, MorphoSys: design and implementation of the MorphoSys reconfigurable computing processor, J. VLSI Signal Process. —Systems Signal Image Video Technol. 24 (2-3) (2000) 147-164.; N. Bagherzade, F. Kurdahi, H. Singh, G. Lu, M. Lee, E. Filho, MorphoSys: design and implementation of the MorphoSys reconfigurable computing processor, J. VLSI Signal Process. —Systems Signal Image Video Technol. 24 (2-3) (2000) 147-164.
[3] D. Bailey, J.M. Borwein, Future Prospects for Computer-assisted Mathematics, Canadian Mathematical Society Notes, vol. 37, no. 8, 2005, pp. 2-6.; D. Bailey, J.M. Borwein, Future Prospects for Computer-assisted Mathematics, Canadian Mathematical Society Notes, vol. 37, no. 8, 2005, pp. 2-6.
[4] Barr, M., A Reconfigurable Computing Primer (1998), Freeman Inc.: Freeman Inc. Miller
[5] Barrett, R.; Berry, M.; Chan, T. F.; Demmel, J.; Donato, J.; Dongarra, J.; Eijkhout, V.; Pozo, R.; Romine, C.; Van der Vorst, H., Templates for the Solution of Linear Systems: Building Blocks for Iterative Methods (1994), SIAM: SIAM Philadelphia, PA
[6] S. Barsky, BARSKY, \(2003 \langle;\) www.mgnet.org/mgnet-codes-barsky.html \(\rangle;\).; S. Barsky, BARSKY, \(2003 \langle;\) www.mgnet.org/mgnet-codes-barsky.html \(\rangle;\).
[7] Bertsekas, D.; Tsitsiklis, J., Some aspects of parallel and distributed iterative algorithms: a survey, Automatica, 27, 1, 3-21 (1991) · Zbl 0728.65041
[8] Bolz, J.; Farmer, I.; Grinspun, E.; Shroder, P., Sparse matrix solvers on the GPU: conjugate gradients and multigrid, ACM Trans. Graphics, 22, 3 (2003)
[9] A. Borzi, Introduction to multigrid methods, Institut fur Mthematik und Wissenschaftliches Rechnen, \(1999 \langle;\) www.kfunigraz.ac.at/imawww/borzi/mgintro.pdf.\( \rangle;\); A. Borzi, Introduction to multigrid methods, Institut fur Mthematik und Wissenschaftliches Rechnen, \(1999 \langle;\) www.kfunigraz.ac.at/imawww/borzi/mgintro.pdf.\( \rangle;\)
[10] J. Bramble, Multigrid Methods, Pitman Research Notes in Mathematics Series, vol. 294, Longman Scientific, New York, 1993.; J. Bramble, Multigrid Methods, Pitman Research Notes in Mathematics Series, vol. 294, Longman Scientific, New York, 1993.
[11] Brandt, A., Multi-level adaptive solutions to boundary value problems, Math. Comp., 1, 31, 333-390 (1977) · Zbl 0373.65054
[12] Briggs, W. L.; Henson, V. E.; Mccormick, S. F., A Multigrid Tutorial (2000), SIAM: SIAM Philadelphia, PA · Zbl 0958.65128
[13] Celoxica \(\langle;\) www.celoxica.com \(\rangle;\).; Celoxica \(\langle;\) www.celoxica.com \(\rangle;\).
[14] Chrzanowska-Jeske, M., Architecture and synthesis issues FPGAs, (Proceedings of NORTHCON’93 Electrical and Electronics Convention (1993)), 102-105
[15] Compton, K.; Hauck, S., Reconfigurable computing: a survey of systems and software, ACM Comput. Surveys, 34, 171-210 (2002)
[16] Cong, J., FPGA Synthesis and Reconfigurable Computing (1997), University of California: University of California Los Angeles, \( \langle\) www.ucop.edu/research/micro/\(96_9 7 / 96_1 76\).pdf \(\rangle \)
[17] Damaj, I.; Diab, H., Performance evaluation of linear algebraic functions using reconfigurable computing, Internat. J. Super Comput., 24, 1, 91-107 (2003) · Zbl 1033.68139
[18] Damaj, I.; Hawkins, J.; Abdallah, A., Mapping high-level algorithms onto massively parallel reconfigurable hardware, (IEEE International Conference of Computer Systems and Applications (2003)), 14-22
[19] K. Datta, S. Merchant, Multigrid methods for titanium heart simulation. Retrieved January 2006, from University of California, Berkeley, Department of Computer Science web site: \( \langle;\) http://www.cs.berkeley.edu/\( \sim;\) kdatta/classes/cs267.doc \(\rangle;\).; K. Datta, S. Merchant, Multigrid methods for titanium heart simulation. Retrieved January 2006, from University of California, Berkeley, Department of Computer Science web site: \( \langle;\) http://www.cs.berkeley.edu/\( \sim;\) kdatta/classes/cs267.doc \(\rangle;\).
[20] Douglas, C., MadPack: a family of abstract multigrid or multilevel solvers, Comput. Appl. Math., 14, 3-20 (1995) · Zbl 0836.65125
[21] A.J. Elbirt, C. Paar, An FPGA implementation and performance evaluation of the Serpent block Cipher, in: ACM/SIGDA International Symposium on FPGAs, 2000, pp. 33-40.; A.J. Elbirt, C. Paar, An FPGA implementation and performance evaluation of the Serpent block Cipher, in: ACM/SIGDA International Symposium on FPGAs, 2000, pp. 33-40.
[22] R. Enzler, The current status of reconfigurable computing, Technical Report, Electronics Laboratory, Swiss Federal Institute of Technology (ETH) Zurich, 1999.; R. Enzler, The current status of reconfigurable computing, Technical Report, Electronics Laboratory, Swiss Federal Institute of Technology (ETH) Zurich, 1999.
[23] FPGA4Fun, FPGA design entry, \(2005 \langle;\) www.fpga4fun.com/DesignEntry.html \(\rangle;\).; FPGA4Fun, FPGA design entry, \(2005 \langle;\) www.fpga4fun.com/DesignEntry.html \(\rangle;\).
[24] Goodnight, N.; Woolley, C.; Lewin, G.; Luebke, D.; Humphreys, G., A multigrid solver for boundary value problems using programmable graphics hardware, (Proceedings of the ACM SIGGRAPH/EUROGRAPHICS Conference on Graphics Hardware (2003)), 102-111
[25] Hackbusch, W., Multigrid Methods and Application (1985), Springer: Springer Berlin · Zbl 0577.65118
[26] Y. Khalilollahi, Switching elements, the key to FPGA architecture, in: WESCON Conference Record, 1994, pp. 682-687.; Y. Khalilollahi, Switching elements, the key to FPGA architecture, in: WESCON Conference Record, 1994, pp. 682-687.
[27] MGNet Homepage: \( \langle;\) http://www.mgnet.org/\( \rangle;\).; MGNet Homepage: \( \langle;\) http://www.mgnet.org/\( \rangle;\).
[28] Pellerin, D.; Thibault, S., Practical FPGA Programming in C, (Prentice-Hall Professional Technical Reference (2005), Prentice-Hall: Prentice-Hall Upper Saddle River, NJ)
[29] Peter, C., Overview: Hardware Compilation and the Handel-C language (2002), Oxford University Computing Laboratory, \( \langle\) http://web.comlab.ox.uk/oucl/work/christian.peter/\( \operatorname{overview}_h \operatorname{andelc} \).html \(\rangle \)
[30] A.K. Sharma, Programmable Logic Handbook PLDs, CPLDs and FPGAs, McGraw Hill, New York, 1998.; A.K. Sharma, Programmable Logic Handbook PLDs, CPLDs and FPGAs, McGraw Hill, New York, 1998.
[31] J. Shewel, A hardware/software co-design system using configurable computing technology, \(1998 \langle;\) http://ipdps.cc.gatech.edu/1998/it/schewel.pdf \(\rangle;\).; J. Shewel, A hardware/software co-design system using configurable computing technology, \(1998 \langle;\) http://ipdps.cc.gatech.edu/1998/it/schewel.pdf \(\rangle;\).
[32] Smedinghoff, M. L., Solving the Poisson equation with multigrid (2005), \( \langle\) http://cd-amr.fnal.gov/aas/poisson.pdf \(\rangle \)
[33] Terminology. Bournemouth University, School of Design, Engineering and Computing \(\langle;\) http://dec.bournemouth.ac.uk/\( \operatorname{drhw}_{\operatorname{l}} \operatorname{ib} \)/terminology.html \(\rangle;\).; Terminology. Bournemouth University, School of Design, Engineering and Computing \(\langle;\) http://dec.bournemouth.ac.uk/\( \operatorname{drhw}_{\operatorname{l}} \operatorname{ib} \)/terminology.html \(\rangle;\).
[34] Todman, T. J.; Constantinides, G. A.; Wilton, S. J.E.; Mencer, O.; Luk, W.; Cheung, P. Y.K., Reconfigurable computing: architectures and design methods, IEE Proceedings—Computers and Digital Techniques, 152, 2, 193-197 (2005)
[35] Torsti, T.; Heiskanen, M.; Puska, M.; Nieminen, R., MIKA: multigrid-based program package for electronic structure calculations, Internat. J. Quantum Chem., 91, 2, 171-176 (2003)
[36] Turely, J., How Chips are Designed, (Prentice-Hall Professional Technical Reference (2003), Prentice-Hall: Prentice-Hall Upper Saddle River, NJ), \( \langle\) www.phptr.com/articles/\( \rangle \)
[37] Vahid, F.; Givargis, T., Embedded Systems Design: A Unified Hardware/Software Introduction (2002), Wiley: Wiley New York
[38] Valentina, S. K., Designing a digital system with VHDL, Academic Open Internet J., 11 (2004)
[39] Wesseling, P., An Introduction to Multigrid Methods (1992), Wiley: Wiley New York · Zbl 0760.65092
[40] Xilinx \(\langle;\) www.xilinx.com \(\rangle;\).; Xilinx \(\langle;\) www.xilinx.com \(\rangle;\).
[41] D. Young, A historical review of iterative methods. Report CNA-206, Center for Numerical Analysis, University of Texas at Austin, 1987.; D. Young, A historical review of iterative methods. Report CNA-206, Center for Numerical Analysis, University of Texas at Austin, 1987.
[42] J. Yström, Multigrid methods improve solvers for both speed and memory, \(2005 \langle;\) www.comsol.fr/femlab2005/sample.doc \(\rangle;\).; J. Yström, Multigrid methods improve solvers for both speed and memory, \(2005 \langle;\) www.comsol.fr/femlab2005/sample.doc \(\rangle;\).
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.