Реализация векторной модели данных с использованием SIMD регистров

Аннотация

В статье рассматривается возможность реализации векторной модели данных с использованием SIMD регистров. Необходимость решения этой проблемы вытекает из того факта, что человечество находится на пороге перехода от обычных компьютеров к их квантовым аналогам. На данный момент эмуляторы развиты недостаточно хорошо для свободной работы над квантовыми алгоритмами. Однако потребность в построении квантовых алгоритмов растёт с каждым новым шагом в разработке полноценного общедоступного квантового компьютера. В статье предлагается метод реализации векторной модели данных с использованием SIMD регистров. Наиболее близкой к параллельной векторной реализации является гипотетическая реализация квантового компьютера, поэтому именно она может послужить основой к разработке модели отвечающей всем критериям квантовой модели, но без использования реальной квантовой системы, что позволит сэкономить средства и увеличить эффективность разработки квантовых систем. Используется терминология области разработки квантовых компьютеров. На сегодняшний день, в большинстве источников, которые приводят метод формирования квантового сумматора, речь идёт о создании неких кубитовых регистров для хранения складываемых чисел. То есть, число хранится в двоичной форме в регистре кубит, каждый из которых находится в определённом квантовом состоянии, не запутанном, а измеренном. Значит, регистр такого вида является по своей сути обыкновенным битовым регистром. Такой подход относительно лёгок в реализации, но он не имеет практического смысла и применения, ведь выигрыш в скорости вычисления в этом случае крайне низок. Поэтому, можно сказать, что превращение кубита в обычный бит, не имеет смысла. Целью данной работы является оформление полученных ранее теоретических результатов в виде полноценной модели вычислений, которая позволит разработать новый тип сумматора на основе матричных операций.

Сведения об авторах

Valerii Yurevich Khodchenkov, Смоленский государственный университет

аспирант физико-математического факультета

Victor Iosifovich Munerman, Смоленский государственный университет

доцент кафедры информатики физико-математического факультета, кандидат технических наук, доцент

Литература

1. Feynman R.P. Simulating physics with computers. International Journal of Theoretical Physics. 1982;21(6):467-488. doi: https://doi.org/10.1007/BF02650179
2. Munerman V.I., Samoylova T.A. Algebraic approach to algorithmization of routing problems. Highly available systems. 2018;14(5):50-56. (In Russ., abstract in Eng.) doi: https://doi.org/10.18127/j20729472-201805-08
3. Ablayev F., Ablayev M., Khadiev K., Salihova N., Vasiliev A. Quantum Algorithms for String Processing. In: Badriev I.B., Banderov V., Lapin S.A. (eds.) Mesh Methods for Boundary-Value Problems and Applications. Lecture Notes in Computational Science and Engineering. Vol. 141. Cham: Springer; 2022. doi: https://doi.org/10.1007/978-3-030-87809-2_1
4. Valiev K.A. Quantum computers and quantum computing. Physics-Uspekhi. 2005;48(1):1-36. doi: https://doi.org/10.1070/PU2005v048n01ABEH002024
5. Draper T.G. Addition on a Quantum Computer. arXiv:quant-ph/0008033. 2000. doi: https://doi.org/10.48550/arXiv.quant-ph/0008033
6. Bocharov L.Yu., Malcev P.P. The main directions development and future of quantum information technologies. NANO-and MICROSYSTEMS TECHOLOGY. 2007;(5):2-10. Available at: https://www.elibrary.ru/item.asp?id=9594914 (accessed 14.09.2022). (In Russ., abstract in Eng.)
7. Munerman V.I. Algebraic approach the data preparation for the associative rules derivation. Highly available systems. 2017;13(3):34-37. Available at: https://www.elibrary.ru/item.asp?id=30554619 (accessed 14.09.2022). (In Russ., abstract in Eng.)
8. Grigorieva G.M., Mironov M.A., Munerman V.I., Khodchenkov V.Yu. Vector addition algorithm in a quantum computer. Computer Mathematics Systems and Their Applications. 2019;(20-1):124-128. Available at: https://www.elibrary.ru/item.asp?id=39103168 (accessed 14.09.2022). (In Russ., abstract in Eng.)
9. Grigoryeva G., Khodchenkov V., Mironov A., Munerman V. Creating a Vector Processor Based on Quantum Computing. In: 2019 IEEE Conference of Russian Young Researchers in Electrical and Electronic Engineering (EIConRus). Saint Petersburg and Moscow, Russia: IEEE Computer Society; 2019. p. 1745-1748. doi: https://doi.org/10.1109/EIConRus.2019.8657294
10. Grigoryeva G., Khodchenkov V. Implementation of Operations of a Quantum Computer in the Language of the Algebra of Multidimensional Matrices. In: 2021 IEEE Conference of Russian Young Researchers in Electrical and Electronic Engineering (ElConRus). St. Petersburg, Moscow, Russia: IEEE Computer Society; 2021. p. 2181-2184. doi: https://doi.org/10.1109/ElConRus51938.2021.9396119
11. Munerman V.I. The object-oriented model of mass data processing. Highly available systems. 2011;7(4):72-74. Available at: https://www.elibrary.ru/item.asp?id=18049084 (accessed 14.09.2022). (In Russ., abstract in Eng.)
12. Ambainis A. Understanding quantum algorithms via query complexity. In: Sirakov B., de Souza P.N., Viana M. (eds.) Proceedings of the International Congress of Mathematicians. Vol. 4. Rio de Janeiro: World Scientific; 2018. p. 3283-3304. Available at: https://eta.impa.br/dl/ICM-2018-vol4-ver1-eb.pdf (accessed 14.09.2022).
13. Zakharov V.N., Munerman V.I., Samoilova T.A. Parallel methods for deriving associative rules with the usage in-database and in-memory technologies. CEUR Workshop Proceedings. 2017;2064:219-225. Available at: https://ceur-ws.org/Vol-2064/paper26.pdf (accessed 14.09.2022). (In Russ., abstract in Eng.)
14. Sokolov N.P. Functions of multidimensional matrices and their applications for the solutions of linear systems of partial differential equations. Ukrainian Mathematical Journal. 1970;22(6):657-674. doi: https://doi.org/10.1007/BF01086271
15. Iljin P.L., Munerman V.I. Recursive Computation of the Multidimensional Matrix Determinant. Computer Mathematics Systems and Their Applications. 2019;(20-1):162-167. Available at: https://elibrary.ru/item.asp?id=39103176 (accessed 14.09.2022). (In Russ., abstract in Eng.)
16. Fujiki D., Mahlke S., Das R. In-Memory Data Parallel Processor. ACM SIGPLAN Notices. 2018;53(2):1-14. doi: https://doi.org/10.1145/3296957.3173171
17. Liu J.-Sh., Lin J.-Yu., Chung Y.-C. Efficient parallel algorithms for multi-dimensional matrix operations. In: Proceedings International Symposium on Parallel Architectures, Algorithms and Networks (I-SPAN 2000). Dallas, TX, USA: IEEE Computer Society; 2000. p. 224-229. doi: https://doi.org/10.1109/ISPAN.2000.900289
18. Pan V.Y., Yu Y., Stewart C. Algebraic and Numerical Techniques for the Computation of Matrix Determinants. Computers & Mathematics with Applications. 1997;34(1):43-70. doi: https://doi.org/10.1016/S0898-1221(97)00097-7
19. Grigorieva G.M., Khodchenkov V.Yu. On the possibility of building a quantum computer emulator using XMM registers. Computer Mathematics Systems and Their Applications. 2021;(22):113-116. Available at: https://www.elibrary.ru/item.asp?id=46649884 (accessed 14.09.2022). (In Russ., abstract in Eng.)
20. Munerman V.I., Munerman D.V. About the correspondence of data models and calculation models. Computer Mathematics Systems and Their Applications. 2021;(22):146-152. Available at: https://elibrary.ru/item.asp?id=46649891 (accessed 14.09.2022). (In Russ., abstract in Eng.)
21. Emelchenkov Ye.P., Munerman V.I., Munerman D.V., Samoilova T.A. The Object Oriented Approach to Designing Data Models. Modern Information Technologies and IT-Education. 2020;16(3):564-574. (In Russ., abstract in Eng.) doi: https://doi.org/10.25559/SITITO.16.202003.564-574
22. Munerman V.I. Construction of hardware-software complexes architecture to improve massively data processing. Highly Available Systems. 2015;11(2):13-18. Available at: https://www.elibrary.ru/item.asp?id=23819273 (accessed 14.09.2022). (In Russ., abstract in Eng.)
23. Furtak T., Amaral J.N., Niewiadomski R. Using SIMD registers and instructions to enable instruction-level parallelism in sorting algorithms. In: Proceedings of the nineteenth annual ACM symposium on Parallel algorithms and architectures (SPAA '07). New York, NY, USA: Association for Computing Machinery; 2007. p. 348-357. doi: https://doi.org/10.1145/1248377.1248436
24. Nuzman D., Rosen I., Zaks A. Auto-vectorization of interleaved data for SIMD. ACM SIGPLAN Notices. 2006;41(6):132-143. doi: https://doi.org/10.1145/1133255.1133997
25. Willhalm T., Popovici N., Boshmaf Y., Plattner H., Zeier A., Schaffner J. SIMD-scan: ultra fast in-memory table scan using on-chip vector processing units. Proceedings of the VLDB Endowment. 2009;2(1):385-394. doi: https://doi.org/10.14778/1687627.1687671
Опубликована
2022-12-20
Как цитировать
KHODCHENKOV, Valerii Yurevich; MUNERMAN, Victor Iosifovich. Реализация векторной модели данных с использованием SIMD регистров. Современные информационные технологии и ИТ-образование, [S.l.], v. 18, n. 4, p. 756-766, dec. 2022. ISSN 2411-1473. Доступно на: <http://sitito.cs.msu.ru/index.php/SITITO/article/view/897>. Дата доступа: 22 apr. 2024 doi: https://doi.org/10.25559/SITITO.18.202204.756-766.
Раздел
Параллельное и распределенное программирование, грид-технологии

Наиболее читаемые статьи этого автора (авторов)