РЕАЛИЗАЦИЯ ПОИСКА НАИБОЛЕЕ ЧАСТО ВСТРЕЧАЮЩИХСЯ ПОСЛЕДОВАТЕЛЬНОСТЕЙ ДНК С ИСПОЛЬЗОВАНИЕМ БИБЛИОТЕКИ KOKKOS

Авторы: 
М.А. Козлов, Е.А. Панова, И. Б. Мееров
УДК: 
004.424, 575.112
DOI: 
10.24412/2073-0667-2024-2-58-71
Аннотация: 

Существующее на текущий день большое разнообразие архитектур ставит вопрос разработки универсального программного обеспечения. В связи с этим появляются и развиваются раз­личные программные средства, позволяющие создавать единый кроссплатформенный код для запуска на CPU, GPU, FPGA и других архитектурах. Тем не менее, остается вопрос эффек­тивности и переносимости производительности разработанного кода. В данной работе мы ис­следуем этот и другие аспекты применительно к библиотеке Kokkos, которая на сегодняшний день является одним из наиболее популярных средств для создания кроссплатформенного ко­да. В качестве бенчмарка мы рассматриваем задачу из области биоинформатики по поиску наиболее часто встречающихся последовательностей ДНК, которая решается с использовани­ем строковых алгоритмов. Мы приводим несколько алгоритмов решения задачи, реализуем их с использованием технологий OpenMP, Cuda и Kokkos и демонстрируем, что потери произво­дительности при использовании Kokkos не превышают 10%, в то время как код может быть запущен как на CPU, так и на GPU.

Список литературы

  1. Gaster В., Howes L., Kaeli D. R., Mistry P., and Schaa D. Heterogeneous computing with openCL: revised openCL. Newnes, 2012.
  2. Farber R. Parallel programming with OpenACC. Newnes, 2016.
  3. 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. Vol. 33, no. 4. P. 805-817.
  4. 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.
  5. Reinders J. et al. Data parallel C++: mastering DPC++ for programming of heterogeneous systems using C++ and SYCL. Springer Nature, 2021. P. 548.
  6. Библиотека Kokkos. URL: https://github.com/kokkos/kokkos. Дата доступа: 10.01.2024.
  7. Subirana J. A., Messeguer X.. The most frequent short sequences in non-coding DNA // Nucleic acids research. 2010. Vol. 38, no. 4. P. 1172-1181.
  8. Faro S., Lecroq T. The exact online string matching problem: A review of the most recent results // ACM Computing Surveys(CSUR). 2013. Vol. 45, no. 2. P. 1-42.
  9. 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. Vol. 7. P. 69614-69637.
  10. Stephen G. A. String searching algorithms. World Scientific, 1994.
  11. Al-Khamaiseh K., Alshagarin S. A survey of string matching algorithms // Int. J. Eng. Res. Appl. 2014. Vol. 4, no. 7. P. 144-156.
  12. Karp R. M., Rabin M. O. Efficient randomized patternmatching algorithms // IBM Journal of Research and Development. 1987.Vol. 31, no. 2. P. 249-260.
  13. Lecroq T. Fast exact string matching algorithms // Information Processing Letters. 2007. Vol. 102, no. 6. P. 229-235.
  14. Galil Z. A constant-time optimal parallel string-matching algorithm // Journal of the ACM (JACM). 1995. Vol. 42, no. 4. P. 908-918.
  15. Park J. H., George К. M. Efficient parallel hardware algorithms for string matching // Microprocessors and Microsystems. 1999. Vol. 23,no. 3. P. 155-168.
  16. Accelerating string matching using multi-threaded algorithm on GPU / Lin С. H., Tsai S. Y., Liu С. H., Chang S. C., and Shyu J. M. // 2010 IEEE Global Telecommunications Conference GLOBECOM 2010 / IEEE. 2010. P. 1-5.
  17. Kouzinopoulos C. S., Michailidis P. D., Margaritis K. G. Multiple string matching on a GPU using cudas //Scalable Computing: Practice and Experience. 2015. Vol. 16, no. 2. P. 121-138.
  18. Козлов M. А., Панова E. А., Мееров И. Б. Реализация поиска наиболее часто встречаю­щихся последовательностей ДНК с использованием библиотеки Kokkos // Математическое мо­делирование и суперкомпьютерные технологии. Труды XXIII Международной конференции (И. Новгород, 13-16 ноября 2023 г.) / Под ред. проф. Д.В. Баландина. Нижний Новгород: Изд-во Нижегородского госуниверситета, 2023. ISBN 978-5-91326-834-1. 2023. С. 73-78.
  19. Открытый исходный код бенчмарка. URL: https://github.com/Mishaizlesa/ most_common_string_kokkos. Дата доступа: 10.01.2024.
  20. DNA Bank (National library of medicine). URL: https://www.ncbi.nlm.nih.gov/genbank.
Ключевые слова: 
Kokkos, кроссплатформенное ПО, гетерогенные вычисления, оптими­зация программ, строковые алгоритмы, биоинформатика.
Номер журнала: 
2(63) 2024 г.
Год: 
2024
Адрес: 
Национальный исследовательский Нижегородский государственный университет им. Н. И. Лобачевского, 603950, Нижний Новгород, Россия
Библиографическая ссылка: 
Козлов М.А., Панова Е.А., Мееров И. Б. Реализация поиска наиболее часто встречающихся последовательностей ДНК с использованием библиотеки Kokkos //"Проблемы информатики", 2024, № 2, с.58-71. DOI: 10.24412/2073-0667-2024-2-58-71. - EDN: TGQKBV