Multigrid methods using block floating point arithmetic. (English) Zbl 07931245
Summary: Block floating point (BFP) arithmetic is currently seeing a resurgence in interest because it requires less power and less chip area and is less complicated to implement in hardware than standard floating point arithmetic. This paper explores the application of BFP to mixed- and progressive-precision multigrid methods, enabling the solution of linear elliptic partial differential equations (PDEs) in energy- and hardware-efficient integer arithmetic. While most existing applications of BFP arithmetic tend to use small block sizes, the block size here is chosen to be maximal such that matrices and vectors share a single exponent for all entries. This is sometimes also referred to as a scaled fixed point format. We provide algorithms for BLAS-like routines for BFP arithmetic that ensure exact vector-vector and matrix-vector computations up to a specified precision. Using these algorithms, we study the asymptotic precision requirements for achieving discretization-error-accuracy. We demonstrate that some computations can be performed using only 4-bit integers, while the number of bits required to attain a certain target accuracy is similar to that of standard floating point arithmetic. Finally, we present a heuristic for full multigrid in BFP arithmetic based on saturation and truncation that still achieves discretization-error-accuracy without the need for expensive normalization steps of intermediate results.
MSC:
| 65F10 | Iterative numerical methods for linear systems |
| 65G50 | Roundoff error |
| 65M55 | Multigrid methods; domain decomposition for initial value and initial-boundary value problems involving PDEs |
References:
| [1] | Baranowski, M., He, S., Lechner, M., Nguyen, T. S., and Rakamarić, Z., An SMT theory of fixed-point arithmetic, in Automated Reasoning, Peltier, N. and Sofronie-Stokkermans, V., eds., Springer International Publishing, Cham, 2020, pp. 13-31. · Zbl 07614504 |
| [2] | J. Dongarra, Basic linear algebra subprograms technical (blast) forum standard, Int. J. High Perform. Comput. Appl., 16 (2002), pp. 1-111, https://journals.sagepub.com/toc/hpcc/16/1. |
| [3] | Basumallik, A., Bunandar, D., Dronen, N., Harris, N., Levkova, L., McCarter, C., Nair, L., Walter, D., and Widemann, D., Adaptive block floating-point for analog deep learning hardware, IEEE Trans. Neural Networks Learn. Syst., 2022, submitted, doi:10.48550/arXiv.2205.06287. |
| [4] | Boland, D. P., Precision Analysis for Hardware Acceleration of Numerical Algorithms, Ph.D. thesis, Imperial College London, 2011, doi:10.25560/9169. |
| [5] | Boldo, S., Gallois-Wong, D., and Hilaire, T., A correctly-rounded fixed-point-arithmetic dot-product algorithm, in Proceedings of the 2020 IEEE 27th Symposium on Computer Arithmetic (ARITH), , Portland, OR, 2020, pp. 9-16, doi:10.1109/ARITH48897.2020.00011. |
| [6] | Dai, S., Venkatesan, R., Ren, H., Zimmer, B., Dally, W. J., and Khailany, B., VS-quant: Per-vector scaled quantization for accurate low-precision neural network inference, in Proceedings of Machine Learning and Systems, MLSys 3, , Smola, A., Dimakis, A., and Stoica, I., eds., 2021, pp. 873-884, https://proceedings.mlsys.org/paper_files/paper/2021/file/48a6431f04545e11919887748ec5cb52-Paper.pdf. |
| [7] | Drumond, M., Lin, T., Jaggi, M., and Falsafi, B., Training DNNs with hybrid block floating point, in Proceedings of NeurIPS 2018, Advances in Neural Information Processing Systems 31, Bengio, S., Wallach, H., Larochelle, H., Grauman, K., Cesa-Bianchi, N., and Garnett, R., eds., Curran Associates, Red Hook, NY, 2018, pp. 453-463, https://proceedings.neurips.cc/paper/2018/file/6a9aeddfc689c1d0e3b9ccc3ab651bc5-Paper.pdf. |
| [8] | J. L. Gustafson and I. T. Yonemoto, Beating floating point at its own game: Posit arithmetic, Supercomput. Front. Innov., 4 (2017), pp. 71-86, doi:10.14529/jsfi170206. |
| [9] | Gutknecht, M. H. and Röllin, S., The Chebyshev iteration revisited, Parallel Comput., 28 (2002), pp. 263-283, doi:10.1016/S0167-8191(01)00139-9. · Zbl 0984.68209 |
| [10] | Horowitz, M., Computing’s energy problem (and what we can do about it), in Proceedings of the 2014 IEEE International Solid-State Circuits Conference Digest of Technical Papers (ISSCC), , San Francisco, CA, 2014, pp. 10-14, doi:10.1109/ISSCC.2014.6757323. |
| [11] | Jouppi, N. P., Yoon, D. Hyun, Ashcraft, M., Gottscho, M., Jablin, T. B., Kurian, G., Laudon, J., Li, S., Ma, P., Ma, X., Norrie, T., Patil, N., Prasad, S., Young, C., Zhou, Z., and Patterson, D., Ten lessons from three generations shaped Google’s TPUv4i : Industrial product, in Proceedings of the 2021 ACM/IEEE 48th Annual International Symposium on Computer Architecture (ISCA), , Valencia, Spain, 2021, pp. 1-14, doi:10.1109/ISCA52012.2021.00010. |
| [12] | Köster, U., Webb, T. J., Wang, X., Nassar, M., Bansal, A. K., Constable, W. H., Elibol, O. H., Gray, S., Hall, S., Hornof, L., Khosrowshahi, A., Kloss, C., Pai, R. J., and Rao, N., Flexpoint: An adaptive numerical format for efficient training of deep neural networks, in Proceedings of NIPS 2017, Advances in Neural Information Processing Systems 30, Guyon, I., Luxburg, U. V., Bengio, S., Wallach, H., Fergus, R., Vishwanathan, S., and Garnett, R., eds., Curran Associates, Red Hook, NY, 2017, pp. 1742-1752, https://proceedings.neurips.cc/paper/2017/file/a0160709701140704575d499c997b6ca-Paper.pdf. |
| [13] | Kulisch, U., Very fast and exact accumulation of products, Computing, 91 (2011), pp. 397-405, doi:10.1007/s00607-010-0131-y. · Zbl 1231.65001 |
| [14] | Lian, X., Liu, Z., Song, Z., Dai, J., Zhou, W., and Ji, X., High-performance FPGA-based CNN accelerator with block-floating-point arithmetic, IEEE Trans. Very Large Scale Integr. (VLSI) Syst., 27 (2019), pp. 1874-1885, doi:10.1109/TVLSI.2019.2913958. |
| [15] | Martel, M., Najahi, A., and Revy, G., Trade-offs of certified fixed-point code synthesis for linear algebra basic blocks, J. Syst. Archit., 76 (2017), pp. 133-148, doi:10.1016/j.sysarc.2016.11.010. |
| [16] | McCormick, S. F., Benzaken, J., and Tamstorf, R., Algebraic error analysis for mixed-precision multigrid solvers, SIAM J. Sci. Comput., 43 (2021), pp. S392-S419, doi:10.1137/20M1348571. · Zbl 07378148 |
| [17] | Noh, S.-H., Koo, J., Lee, S., Park, J., and Kung, J., FlexBlock: A flexible DNN training accelerator with multi-mode block floating point support, IEEE Trans. Comput., 72 (2023), pp. 2522-2535, doi:10.1109/TC.2023.3253050. |
| [18] | Noh, S.-H., Park, J., Park, D., Koo, J., Choi, J., and Kung, J., LightNorm: Area and energy-efficient batch normalization hardware for on-device DNN training, in Proceedings of the 2022 IEEE 40th International Conference on Computer Design (ICCD), , Olympic Valley, CA, 2022, pp. 443-450, doi:10.1109/ICCD56317.2022.00072. |
| [19] | Parhami, B., Computer Arithmetic: Algorithms and Hardware Designs, 2nd ed., Oxford University Press, New York, 2010. |
| [20] | Zhang, S. Qian, McDanel, B., and Kung, H. T., FAST: DNN training under variable precision block floating point with stochastic rounding, in Proceedings of the 2022 IEEE International Symposium on High-Performance Computer Architecture (HPCA), , Seoul, Republic of Korea, 2022, pp. 846-860, doi:10.1109/HPCA53966.2022.00067. |
| [21] | Rouhani, B. D., Lo, D., Zhao, R., Liu, M., Fowers, J., Ovtcharov, K., Vinogradsky, A., Massengill, S., Yang, L., Bittner, R., Forin, A., Zhu, H., Na, T., Patel, P., Che, S., Chand Koppaka, L., Song, X., Som, S., Das, K., Tiwary, S., Reinhardt, S., Lanka, S., Chung, E., and Burger, D., Pushing the limits of narrow precision inferencing at cloud scale with Microsoft floating point, in Proceedings of NeurIPS 2020, , Larochelle, H., Ranzato, M., Hadsell, R., Balcan, M., and Lin, H., eds., Curran Associates, Red Hook, NY, 2020, pp. 10271-10281, https://proceedings.neurips.cc/paper/2020/hash/747e32ab0fea7fbd2ad9ec03daa3f840-Abstract.html. |
| [22] | Sung, W. and Kum, K.-I., Simulation-based word-length optimization method for fixed-point digital signal processing systems, IEEE Trans. Signal Process., 43 (1995), pp. 3087-3090, doi:10.1109/78.476465. |
| [23] | Tamstorf, R., Benzaken, J., and McCormick, S. F., Discretization-error-accurate mixed-precision multigrid solvers, SIAM J. Sci. Comput., 43 (2021), pp. S420-S447, doi:10.1137/20M1349230. · Zbl 07418114 |
| [24] | Wilkinson, J. H., Rounding Errors in Algebraic Processes, Prentice-Hall Series in Automatic Computation, Prentice-Hall, Englewood Cliffs, NJ, 1963. Republished as Classics in Applied Mathematics 89, SIAM, Philadelphia, 2023. · Zbl 1041.65502 |
| [25] | Williamson, D., Dynamically scaled fixed point arithmetic, in Proceedings of the [1991] IEEE Pacific Rim Conference on Communications, Computers and Signal Processing Conference Proceedings, , Vol. 1, Victoria, BC, Canada, 1991, pp. 315-318, doi:10.1109/PACRIM.1991.160742. |
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.
