Реализация поиска наиболее часто встречающихся последовательностей ДНК с использованием библиотеки Kokkos
Автор: Козлов М.А., Панова Е.А., Мееров И.Б.
Журнал: Проблемы информатики @problem-info
Рубрика: Прикладные информационные технологии
Статья в выпуске: 2 (63), 2024 года.
Бесплатный доступ
Существующее на текущий день большое разнообразие архитектур ставит вопрос разработки универсального программного обеспечения. В связи с этим появляются и развиваются различные программные средства, позволяющие создавать единый кроссплатформенный код для запуска на CPU, GPU, FPGA и других архитектурах. Тем не менее, остается вопрос эффективности и переносимости производительности разработанного кода. В данной работе мы исследуем этот и другие аспекты применительно к библиотеке Kokkos, которая на сегодняшний день является одним из наиболее популярных средств для создания кроссплатформенного кода. В качестве бенчмарка мы рассматриваем задачу из области биоинформатики по поиску наиболее часто встречающихся последовательностей ДНК, которая решается с использованием строковых алгоритмов. Мы приводим несколько алгоритмов решения задачи, реализуем их с использованием технологий OpenMP, Cuda и Kokkos и демонстрируем, что потери производительности при использовании Kokkos не превышают 10 %, в то время как код может быть запущен как на CPU, так и на GPU.
Kokkos, кроссплатформенное по, гетерогенные вычисления, оптимизация программ, строковые алгоритмы, биоинформатика
Короткий адрес: https://sciup.org/143183458
IDR: 143183458 | DOI: 10.24412/2073-0667-2024-2-58-71
Список литературы Реализация поиска наиболее часто встречающихся последовательностей ДНК с использованием библиотеки Kokkos
- Gaster B., Howes L., Kaeli D. R., Mistry P., and Schaa D. Heterogeneous computing with openCL: revised openCL. Newnes, 2012.
- Farber R. Parallel programming with OpenACC. Newnes, 2016.
- Kokkos 3: Programming model extensions for the exascale era / Trott C. R., Damien LG, Arndt D., Ciesko J., Dang V., Ellingwood N., Gayatri R., Harvey E., Hollman D. S., Ibanez D., et al. // IEEE Transactions on Paralleland Distributed Systems. 2021. V. 33, N 4. P. 805–817.
- Alpaka — an abstraction library for parallel kernel acceleration / Zenker E., Worpitz B., Widera R., Huebl A., Juckeland G., Knupfer A., Nagel W. E., and Bussmann M. // 2016 IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW) / IEEE. 2016. P. 631–640.
- Reinders J. et al. Data parallel C++: mastering DPC++ for programming of heterogeneous systems using C++ and SYCL. Springer Nature, 2021. P. 548.
- Библиотека Kokkos. [Электрон. рес.]: https://github.com/kokkos/kokkos. Дата доступа: 10.01.2024.
- Subirana J. A., Messeguer X. The most frequent short sequences in non-coding DNA // Nucleic acids research. 2010. V. 38, N 4. P. 1172–1181.
- Faro S., Lecroq T. The exact online string matching problem: A review of the most recent results // ACM Computing Surveys(CSUR). 2013. V. 45, N 2. P. 1–42.
- Exact string matching algorithms: survey, issues, and future research directions / Hakak S. I., Kamsin A., Shivakumara P., Gilkar G. A., Khan W. Z., and Imran M. // IEEE access. 2019. V. 7. P. 69614–69637.
- Stephen G. A. String searching algorithms. World Scientific, 1994.
- Al-Khamaiseh K., Alshagarin S. A survey of string matching algorithms // Int. J. Eng. Res. Appl. 2014. V. 4, N 7. P. 144–156.
- Karp R. M., Rabin M. O. Efficient randomized patternmatching algorithms // IBM Journal of Research and Development. 1987. V. 31, N 2. P. 249–260.
- Lecroq T. Fast exact string matching algorithms // Information Processing Letters. 2007. V. 102, N 6. P. 229–235.
- Galil Z. A constant-time optimal parallel string-matching algorithm // Journal of the ACM (JACM). 1995. V. 42, N 4. P. 908–918.
- Park J. H., George K. M. Efficient parallel hardware algorithms for string matching // Microprocessors and Microsystems. 1999. V. 23,N 3. P. 155–168.
- Accelerating string matching using multi-threaded algorithm on GPU / Lin C. H., Tsai S. Y., Liu C. H., Chang S. C., and Shyu J. M. // 2010 IEEE Global Telecommunications Conference GLOBECOM 2010 / IEEE. 2010. P. 1–5.
- Kouzinopoulos C. S., Michailidis P. D., Margaritis K. G. Multiple string matching on a GPU using cudas //Scalable Computing: Practice and Experience. 2015. V. 16, N 2. P. 121–138.
- Козлов М. А., Панова Е. А., Мееров И. Б. Реализация поиска наиболее часто встречающихся последовательностей ДНК с использованием библиотеки Kokkos // Математическое моделирование и суперкомпьютерные технологии. Труды XXIII Международной конференции (Н. Новгород, 13–16 ноября 2023 г.) / Под ред. проф. Д. В. Баландина. Нижний Новгород: Изд-во Нижегородского госуниверситета, 2023. ISBN 978-5-91326-834-1. 2023. С. 73–78.
- Открытый исходный код бенчмарка. [Электрон. рес.]: https://github.com/Mishaizlesa/most_common_string_kokkos. Дата доступа: 10.01.2024.
- DNA Bank (National library of medicine). [Электрон. рес.]: https://www.ncbi.nlm.nih.gov/genbank. Дата доступа: 10.01.2024.
