Аннотация.

В работе показана быстрая реализация расстояния Хэмминга на платформе Эльбрус, обладающей VLIW-архитектурой. Приведены и экспериментально исследованы ключевые особенности архитектуры Эльбрус, позволяющие значительно повысить быстродействие вычисления расстояния Хэмминга, такие как наличие нескольких арифметико-логических устройств, работающих параллельно, особенности доступа в память, наличие буфера подкачки массивов и другие возможности параллельного исполнения команд. Реализация с учетом этих особенностей оказалась в 11,5 раз быстрее базовой реализации для достаточно больших длин массивов. Более того, исследованные техники повышения быстродействия для процессоров Эльбрус не являются специфичными для рассмотренного алгоритма и могут применяться для ряда других алгоритмов обработки данных.

Ключевые слова:

расстояние Хэмминга, VLIW-архитектура, процессор Эльбрус.

Стр. 65-72.

DOI: 10.14357/20790279180507

Полная версия статьи в формате pdf. 

Литература

1. Ray J., Koopman P. Efficient high Hamming distance CRCs for embedded networks // Dependable Systems and Networks, 2006. DSN 2006. International Conference on. – IEEE, 2006. – С. 3-12.
2. Hamming R.W. Error detecting and error correcting codes // Bell Labs Technical Journal. – 1950. – Т. 29. – №. 2. – С. 147-160.
3. Rigas I., Economou G., Fotopoulos S. Efficient modeling of visual saliency based on local sparse representation and the use of hamming distance // Computer Vision and Image Understanding. – 2015. – Т. 134. – С. 33-45.
4. Revathy S., Ramasethu M.L. Face and IRIS recognition in a video sequence using DBPNN and adaptive Hamming Distance. – 2016.
5. Fakhfakh S., Tmar M., Mahdi W. Image Retrieval Based on Using Hamming Distance // Procedia Computer Science. – 2015. – Т. 73. – С. 320-327.
6. Li W., Packard N. The structure of the elementary cellular automata rule space //Complex systems. – 1990. – Т. 4. – №. 3. – С. 281-297.
7. Souza J.W.G. et al. A new proposal for analyzing combustion process stability based on the Hamming distance // Physica A: Statistical Mechanics and its Applications. – 2014. – Т. 413. – С. 301-306.
8. Ghani R. Using error-correcting codes for text classification // ICML. – 2000. – С. 303-310.
9. Ruan Y. et al. Quantum Algorithm for K-Nearest Neighbors Classification Based on the Metric of Hamming Distance // International Journal of Theoretical Physics. – 2017. – Т. 56. – №. 11. – С. 3496-3507.
10. Norouzi M., Fleet D.J., Salakhutdinov R.R. Hamming distance metric learning // Advances in neural information processing systems. – 2012. – С. 1061-1069.
11. Xin H. et al. Shifted Hamming distance: a fast and accurate SIMD-friendly filter to accelerate alignment verification in read mapping // Bioinformatics. – 2015. – Т. 31. – №. 10. – С. 1553-1560.
12. Sood S., Loguinov D. Probabilistic near-duplicate detection using simhash // Proceedings of the 20th ACM international conference on Information and knowledge management. – ACM, 2011. – С. 1117-1126.
13. Kaiser M. et al. Accelerating Hamming Distance Comparisons for Locality Sensitive Hashing (LSH) using FPGAs // 12th CeBiTec Symposium- Big Data in Medicine and Biotechnology-Abstract Book. – 2018. – Т. 12.
14. Kuznetsova E. et al. Viola-Jones based hybrid framework for real-time object detection in multispectral images // ICMV 2015, SPIE, vol. 9875, publ. code 98750N, pp. 1-6, 2015, DOI: 10.1117/12.2228707.
15. Skoryukina N. et al. Real Time Rectangular Document Detection on Mobile Devices // ICMV 2014, SPIE, 2015, vol. 9445, publ. code 94452A, pp. 1-6, 2015, DOI: 10.1117/12.2181377.
16. Skoryukina N. et al. Snapscreen: TV-stream frame search with projectively distorted and noisy query // Proc. SPIE 10341, ICMV 2016, 10341 ed., Antanas Verikas, Ed., Ninth International Conference on Machine Vision, 2017, vol. 10341, ISBN 978-15-10611-32-0, publ. code 103410Y, pp. 1-5, 2017, DOI: 10.1117/12.2268735.
17. Бочаров Н.А., Лимонова Е.Е., Парамонов Н.Б. и др. Оптимизация для вычислительной архитектуры Эльбрус модифицированного метода Виола и Джонса // Труды ИСА РАН. 2017. Т. 67. № 4. С. 10-21.
18. Лимонова Е.Е., Бочаров Н.А., Парамонов Н.Б., Богданов Д.С., Арлазаров В.В., Славин О.А., Николаев Д.П. Оценка быстродействия системы распознавания на VLIW архитектуре на примере платформы Эльбрус // Программирование (в печати).
19. Hirvola T. et al. Bit-parallel approximate string matching under Hamming distance. – 2016.
20. Muła W., Kurz N., Lemire D. Faster population counts using AVX2 instructions // The Computer Journal. 2017. Т. 61. №. 1. С. 111–120.
21. Ким А.К., Бычков И.Н. и др. Российские технологии «Эльбрус» для персональных компьютеров, серверов и суперкомпьютеров //Современные информационные технологии и ИТ-образование, М.: Фонд содействия развитию интернет-медиа, ИТ-образования, человеческого потенциала «Лига интернет-медиа», 2014, № 10, с. 39-50.
22. Ким А.К., Перекатов В.И., Ермаков С.Г. Микропроцессоры и вычислительные комплексы семейства «Эльбрус». – СПб.: Питер, 2013. – 272 С.
23. Porpodas V., Jones T.M. Throttling automatic vectorization: When less is more // Parallel Architecture and Compilation (PACT), 2015 International Conference on. – IEEE, 2015. – С. 432-444.