Высокопроизводительные вычисления с использованием системы остаточных классов

Автор: К. С. Исупов

Журнал: Программные системы: теория и приложения @programmnye-sistemy

Рубрика: Математические основы программирования

Статья в выпуске: 2 (49) т.12, 2021 года.

Бесплатный доступ

Система остаточных классов (СОК)—это непозиционная система счисления, являющаяся альтернативой двоичному представлению чисел. В СОК большое целое число представляется в виде набора меньших чисел, являющихся остатками от деления исходной величины на выбранные модули. СОК выполняет сложение, вычитание и умножение с каждым остатком по отдельности. Это приводит к параллельной, свободной от переносов и высокоскоростной компьютерной арифметике для высокопроизводительных вычислений. Однако немодульные операции, требующие оценки величины числа по остаткам, являются сложными для реализации в СОК, так как для них не существует параллельной формы. В вопросах практического использования СОК выполнение немодульных операций занимает центральное место. Представлен обзор исследований в области разработки и применения на практике методов высокопроизводительных вычислений на основе СОК: Рассмотрены существующие техники выполнения важнейших немодульных операций, таких как обратное преобразование, сравнение чисел, вычисление знака и деление. Акцент сделан на методы, пригодные для произвольных наборов модулей. Показано, каким образом арифметика на основе СОК находит практическое применение в облачных средах, блокчейн-технологиях, вычислениях многократной точности и глубоких нейронных сетях. Обзор ориентирован на развитие новых направлений исследований, посвященных применению непозиционных систем счисления с параллельной структурой в ресурсоемких приложениях.

Еще

Система остаточных классов, немодульные операции, высокопроизводительные вычисления, параллельные алгоритмы

Короткий адрес: https://sciup.org/143173919

IDR: 143173919 | DOI: 10.25209/2079-3316-2021-12-2-137-192

Список литературы Высокопроизводительные вычисления с использованием системы остаточных классов

P. V. Ananda Mohan. Residue Number Systems: Theory and Applications, Birkha¨user, Basel, 2016, ISBN 978-3-319-41385-3, x+351 pp.
A. Omondi, B. Premkumar. Residue Number Systems: Theory And Implementation, Imperial College Press, London, UK, 2007, ISBN 978-1- 86094-866-4.
A. S. Molahosseini, L. Sousa. “Introduction to residue number system: structure and teaching methodology”, Embedded Systems Design with Special Arithmetic and Number Systems, eds. A. S. Molahosseini, L. S. de Sousa, C. Chang, Springer, Cham, 2017, ISBN 978-3-319-49742-6, pp. 3–17.
И. Я. Акушинский, Д. И. Юдицкий. Машинная арифметика в остаточных классах, Сов. радио, М., 1968, 439 с.
Z. Guo, Z. Gao, H. Mei, M. Zhao, J. Yang. “Design and optimization for storage mechanism of the public blockchain based on redundant residual number system”, IEEE Access, 7 (2019), pp. 98546–98554.
H. Mei, Z. Gao, Z. Guo, M. Zhao, J. Yang. “Storage mechanism optimization in blockchain system based on residual number system”, IEEE Access, 7 (2019), pp. 114539–114546.
A. Qaisar Ahmad Al Badawi, Y. Polyakov, K. M. M. Aung, B. Veeravalli, K. Rohloff. “Implementation and performance evaluation of RNS variants of the BFV homomorphic encryption scheme”, IEEE Transactions on Emerging Topics in Computing, 9:2 (2019), pp. 941–956.
J. Bajard, J. Eynard, M. A. Hasan, V. Zucca. “A full RNS variant of FV like somewhat homomorphic encryption schemes”, Selected Areas in Cryptography, SAC 2016, Lecture Notes in Computer Science, vol. 10532, eds. R. Avanzi, H. Heys, Springer International Publishing, Cham, 2017, ISBN 978-3-319-69453-5, pp. 423–442.
K. Givaki, R. Hojabr, M. H. Najafi, A. Khonsari, M. H. Gholamrezayi, S. Gorgin, D. Rahmati. “Using residue number systems to accelerate deterministic bit-stream multiplication”, Proc. 2019 IEEE 30th International Conference on Application-Specific Systems, Architectures and Processors, ASAP (15–17 July 2019, New York, NY, USA), 2019, pp. 40.
M. Villari, A. Celesti, F. Tusa, A. Puliafito. “Data reliability in multi-provider cloud storage service with RRNS”, Advances in Service-Oriented and Cloud Computing, Communications in Computer and Information Science, vol. 393, eds. C. Canal, M. Villari, Springer, Berlin–Heidelberg, 2013, ISBN 978-3-642-45364-9, pp. 83–93.
A. Celesti, M. Fazio, M. Villari, A. Puliafito. “Adding long-term availability, obfuscation, and encryption to multi-cloud storage systems”, Journal of Network and Computer Applications, 59 (2016), pp. 208–218.
S. Salamat, M. Imani, S. Gupta, T. Rosing. “RNSnet: in-Memory neural network acceleration using residue number system”, Proc. 2018 IEEE International Conference on Rebooting Computing, ICRC, 7–9 Nov. 2018, McLean, VA, USA, pp. 1–12.
N. Samimi, M. Kamal, A. Afzali-Kusha, M. Pedram. “Res-DNN: A residue number system-Based DNN accelerator unit”, IEEE Transactions on Circuits and Systems I: Regular Papers, 67:2 (2020), pp. 658–671.
O. L. Usman, R. C. Muniyandi. “CryptoDL: predicting dyslexia biomarkers from encrypted neuroimaging dataset using energy-efficient residue number system and deep convolutional neural network”, Symmetry, 12:5 (2020), 836, 24 pp.
P. V. Ananda Mohan. “RNS-Based arithmetic circuits and applications”, Arithmetic Circuits for DSP Applications, Ch. 6, eds. P. K. Meher, T. Stouraitis, John Wiley and Sons, Ltd, 2017, ISBN 9781119206804, pp. 186–236.
G. C. Cardarilli, A. Nannarelli, M. Re. “RNS applications in digital signal processing”, Embedded Systems Design with Special Arithmetic and Number Systems, eds. A. S. Molahosseini, L. S. de Sousa, C. Chang, Springer, Cham, 2017, ISBN 978-3-319-49742-6, pp. 181–215.
D. Younes, P. Steffan. “Efficient image processing application using residue number system”, Proc. 20th International Conference Mixed Design of Integrated Circuits and Systems, MIXDES 2013, 20–22 June 2013, Gdynia, Poland, pp. 468–472.
E. Ochoa-Jim´enez, L. Rivera-Zamarripa, N. Cruz-Cort´es, F. Rodr´ıguez-Henr´ıquez. “Implementation of RSA signatures on GPU and CPU architectures”, IEEE Access, 8 (2020), pp. 9928–9941.
K. Isupov, V. Knyazkov. “Multiple-Precision BLAS library for graphics processing units”, RuSCDays 2020: Supercomputing, Communications in Computer and Information Science, vol. 1331, Springer International Publishing, Cham, 2020, ISBN 978-3-030-64616-5, pp. 37–49.
K. Isupov, V. Knyazkov, A. Kuvaev. “Design and implementation of multiple-precision BLAS level 1 functions for graphics processing units”, Journal of Parallel and Distributed Computing, 140 (2020), pp. 25–36.
V. Shoup. A Computational Introduction to Number Theory and Algebra, Cambridge University Press, Cambridge, UK, 2005, ISBN 9781139165464.
V. T. Goh, M. U. Siddiqi. “Multiple error detection and correction based on redundant residue number systems”, IEEE Transactions on Communications, 56:3 (2008), pp. 325–330.
L. Sousa. “Nonconventional computer arithmetic circuits, systems and applications”, IEEE Circuits and Systems Magazine, 21:1 (2021), pp. 6–40.
C. Chang, A. S. Molahosseini, A. A. E. Zarandi, T. F. Tay. “Residue number systems: A new paradigm to datapath optimization for low-power and high-performance digital signal processing applications”, IEEE Circuits and Systems Magazine, 15:4 (2015), pp. 26-44.
N. S. Szabo, R. I. Tanaka. Residue Arithmetic and its Application to Computer Technology, McGraw-Hill, New York, USA, 1967, ISBN 978-0070626591, 236 pp.
D. E. Knuth. The Art of Computer Programming. V. 2: Seminumerical Algorithms, 3rd ed., Addison-Wesley, USA, 1997, ISBN 0201896842, 784 pp.
H. M. Yassine, W. R. Moore. “Improved mixed-radix conversion for residue number system architectures”, IEE Proceedings G (Circuits, Devices and Systems), 138:1 (1991), pp. 120–124.
M. Akkal, P. Siy. “A new mixed radix conversion algorithm MRC-II”, Journal of Systems Architecture, 53:9 (2007), pp. 577–586.
Y. Wang. “New Chinese remainder theorems”, Conference Record of Thirty-Second Asilomar Conference on Signals, Systems and Computers. V. 1 (1–4 Nov. 1998, Pacific Grove, CA, USA), 1998, ISBN 0-7803-5148-7, pp. 165–171.
Y. Wang. “Residue-to-binary converters based on new Chinese remainder theorems”, IEEE Transactions on Circuits and Systems II: Analog and Digital Signal Processing, 47:3 (2000), pp. 197–205.
W. Zhang, P. Siy. “An efficient design of residue to binary converter for four moduli set {2n − 1, 2n + 1, 22n − 2, 22n+1 − 3} based on new CRT II”, Information Sciences, 178:1 (2008), pp. 264–279.
A. S. Molahosseini, K. Navi, C. Dadkhah, O. Kavehei, S. Timarchi. “Efficient reverse converter designs for the new 4-Moduli sets {2n − 1, 2n, 2n + 1, 22n+1 − 1} and {2n − 1, 2n + 1, 22n, 22n + 1} based on new CRTs”, IEEE Transactions on Circuits and Systems I: Regular Papers, 57:4 (2010), pp. 823–835.
S. Bi, W. Gross. “The mixed-Radix Chinese remainder theorem and its applications to residue comparison”, IEEE Transactions on Computers, 57:12 (2008), pp. 1624–1632.
G. Dimauro, S. Impedovo, G. Pirlo. “A new technique for fast number comparison in the residue number system”, IEEE Transactions on Computers, 42:5 (1993), pp. 608–612.
G. Dimauro, S. Impedovo, G. Pirlo, A. Salzo. “RNS architectures for the implementation of the ‘diagonal function’”, Information Processing Letters, 73:5–6 (2000), pp. 189–198.
P.V. Ananda Mohan. “RNS to binary conversion using diagonal function and Pirlo and Impedovo monotonic function”, Circuits, Systems, and Signal Processing, 35:3 (2016), pp. 1063–1076.
G. Pirlo, D. Impedovo. “A new class of monotone functions of the residue number system”, International Journal of Mathematical Models and Methods in Applied Sciences, 7:9 (2013), pp. 802–809.
M. Soderstrand, C. Vernia, J. Chang. “An improved residue number system digital-to-analog converter”, IEEE Transactions on Circuits and Systems, 30:12 (1983), pp. 903–907.
M. Lu, J. Chiang. “A novel division algorithm for the residue number system”, IEEE Transactions on Computers, 41:8 (1992), pp. 1026–1032.
K. Isupov, V. Knyazkov. “Interval estimation of relative values in residue number system”, Journal of Circuits, Systems and Computers, 27:1 (2018), pp. 1850004.
Н. И. Червяков, М. Г. Бабенко, П. А. Ляхов, И. Н. Лавриненко. «Приближенный метод сравнения модулярных чисел и его применение для деления чисел в системе остаточных классов», Кибернетика и системный анализ, 50:6 (2014), с. 176–186.
Jin Yul Kim, Kyu Ho Park, Hwang Soo Lee. “Efficient residue-to-binary conversion technique with rounding error compensation”, IEEE Transactions on Circuits and Systems, 38:3 (1991), pp. 315–317.
H. Br¨onnimann, I. Z. Emiris, V. Y. Pan, S. Pion. “Sign determination in residue number systems”, Theoretical Computer Science, 210:1 (1999), pp. 173–197.
A. A. Hiasat, H. S. Abdel-Aty-Zohdy. “Design and implementation of an RNS division algorithm”, Proc. 13th IEEE Sympsoium on Computer Arithmetic (6–9 July 1997, Asilomar, CA, USA), 1997, ISBN 0-8186-7846-1, pp. 240–249.
А. С. Коржавина, В. С. Князьков. «Реализация высокоточных вычислений в базисе модулярно-интервальной арифметики», Программные системы: теория и приложения, 10:3(42) (2019), с. 81-–127.
C. Y. Hung, B. Parhami. “An approximate sign detection method for residue numbers and its application to RNS division”, Computers & Mathematics with Applications, 27:4 (1994), pp. 23–35.
J. Yang, C. Chang , C. Chen. “A high-speed division algorithm in residue number system using parity-checking technique”, International Journal of Computer Mathematics, 81:6 (2004), pp. 775–780
R. Conway, J. Nelson. “New CRT-based RNS converter using restricted moduli set”, IEEE Transactions on Computers, 52:5 (2003), pp. 572–578.
K. Isupov. “Using floating-point intervals for non-modular computations in residue number system”, IEEE Access, 8 (2020), pp. 58603–58619.
S. Arthireena, G. Shanmugavadivel. “Efficient sign detection using parallel prefix adder”, Proc. 2017 IEEE International Conference on Electrical, Instrumentation and Communication Engineering, ICEICE, IEEE, 27–28 April 2017, Karur, India, pp. 1–5.
S. Kawamura, M. Koike, F. Sano, A. Shimbo. “Cox-Rower architecture for fast parallel Montgomery multiplication”, Advances in Cryptology, EUROCRYPT 2000, Lecture Notes in Computer Science, vol. 1807, ed. B. Preneel, Springer, Berlin–Heidelberg, 2000, ISBN 978-3-540-45539-4, pp. 523–538.
T. V. Vu. “Efficient implementations of the Chinese remainder theorem for sign detection and residue decoding”, IEEE Transactions on Computers, C-34:7 (1985), pp. 646–651.
S. J. Meehan, S. D. O’Neil, J. J. Vaccaro. “An universal input and output RNS converter”, IEEE Transactions on Circuits and Systems, 37:6 (1990), pp. 799–803.
N. Chervyakov, A. S. Molahosseini, P. A. Lyakhov, M. G. Babenko, M. A. Deryabin. “Residue-to-binary conversion for general moduli sets based on approximate Chinese remainder theorem”, International Journal of Computer Mathematics, 94:9 (2017), pp. 1833–1849.
N. Whitehead, A. Fit-Florea. Precision & performance: floating point and IEEE 754 compliance for NVIDIA GPUs, 2011 (Accessed 20 March 2021), 7 pp.
N. Burgess. “Scaled and unscaled residue number system to binary conversion techniques using the core function”, Proc. 13th IEEE Sympsoium on Computer Arithmetic, 6–9 July 1997, Asilomar, CA, USA, ISBN 0-8186-7846-1, pp. 250–257.
Shaoqiang Bi, Wei Wang, A. Al-Khalili. “New modulo decomposed residuetobinary algorithm for general moduli sets”, Proc. 2004 IEEE International Conference on Acoustics, Speech, and Signal Processing. V. V, 17–21 May 2004, Montreal, QC, Canada, ISBN 0-7803-8484-9, pp. 141–144.
A. Omondi. “Fast residue-to-binary conversion using base extension and the Chinese remainder theorem”, Journal of Circuits, Systems and Computers, 16:3 (2007), pp. 379–388.

Еще

Статья научная