Optimizing packed string matching on AVX2 platform

Abstract

Dizgi eşleştirme verilen bir örüntünün P bir metin T üzerinde bir veya tüm eşleşmelerini bulma işlemi olarak tanımlanabilir ve bilgisayar bilimlerinde üzerinde geniş bir şekilde çalışma yapılan temel bir konudur. Dizgi eşleştirmenin birçok alanda uygulaması vardır, bunlar arasında doğal dil işleme, ses işleme, hesaplamalı biyoloji, bilgi gerigetirimi, saldırı tespit sistemleri, arama motorları, veri sıkıştırma, zaman serileri analizi gibi konular sayılabilir. Günümüzde farklı alanlardaki verilerin hızı, kapasitesi ve çeşitliliği sürekli artmaktadır, dolayısıyla bu büyük veri yığınları üzerindeki dizgi eşleştirme algoritmalarının hızları gittikçe önem kazanmaktadır. Özellikle zaman-kritik uygulamalarda dizgi eşleştirme algoritmalarının performansı en önemli kriterlerden biridir. Literatürde dizgi eşleştirme problemin tipine göre kategorilere ayrılmıştır; tam, yaklaşık, dairesel, karmaşık, sıra-korumalı olarak eşleştirme tipleri mevcuttur.Bu çalışmada tam dizgi eşleştirme için paketleme metoduna dayalı yeni algoritmalar geliştirilmiştir. Tam dizgi eşleştirme bir metin üzerinde verilen örüntünün tam eşleşen alt dizgilerini bulma olarak tanımlanmaktadır. Bu tezde yeni önerilen paketlenmiş dizgi eşleştirme algoritmalarında SIMD (Single Instruction Multiple Data) teknolojisinden yararlanılmıştır. SIMD teknolojisi bir komutla aynı anda çoklu veri üzerinde işlem yapma olanağı sunmaktadır. Ayrıca geliştirilen algoritmalarda optimum çözüme ulaşmak için algoritmalar üzerinde analiz yapılarak optimizasyonlar uygulanmıştır. 1970 yılından günümüze çok sayıda dizgi eşleştirme algoritmaları sunulmuştur, günümüzde ise daha iyi sonuçlara ulaşabilmek amacıyla yeni bakış açılarıyla yöntemler geliştirilmeye devam edilmektedir. SIMD ile paralleştirmeye dayalı yöntemlerle dizgi eşleştirme operasyonunu hızlandırma son yıllarda literatürde görülmeye başlanmıştır. Yapılan deneysel çalışmalarda SIMD ile veri seviyesinde paralelleştirme önemli derecede hızlanma sağlamaktadır, ayrıca artan `register` boyutlarıyla bu performans artışının devam etmesi beklenmektedir. Bu çalışmada daha önce 128 bit `register` boyutuna sahip `Intel SSE4.2 (Streaming SIMD Extensions 4.2)` teknolojisi üzerinde geliştirilen EPSM ve SSEF algoritmalarının yeni optimal varyantları önerilmiştir. Yeni önerilen algoritmalar 256 bit `register` boyutuna sahip Intel AVX2 (Advanced Vector Extensions 2) platformu üzerinde geliştirilmiştir ve artan `register` boyutuna karşılık performansın nasıl arttığı ve hangi sorunlarla karşılaşıldığı analiz edilmiştir. Bu bağlamda Intel Vtune Amplifier uygulaması ile algoritmalar üzerinde profilleme ile performans darboğazları tespit edilerek sebepleri araştırılmış ve bu bilgiler ışığında algoritmalar düzenlenmiştir. Çalışmada öncelikle AVX2 `intrinsic` fonksiyonları kullanılarak 256-bit veri üzerinde sabit zamanda çalışan kelime-boyu komutlar tanımlanmıştır. Daha sonra bu kelime-boyu komutlar kullanılarak yeni algoritmalar geliştirilmiştir. AVX2 platformu üzerinde çalışan bu komutlardan bahsedecek olursak; `kelime-boyu karşılaştırma komutu` argüman olarak aldığı iki adet 256-bit veriyi karşılaştırarak eşleştirme sonuçlarını 32 bit veri biçiminde vermektedir. `Kelime-boyu eşleştirme komutu` ise 256 bit iki veride dörtlü karakter grupları üzerinde 16 adet Mutlak Farklar Toplamı (SAD) hesaplayarak eşleşme olan durumları belirlemekte ve eşleşme sonuçlarını 32-bit veri olarak döndürmektedir. `Kelime-boyu değiştirme komutu` iki adet 256 bit veri üzerinde 32 karakterlik bölütlerin yerlerini değiştirerek istenen veri düzenini sağlamakta, bu yer değiştirme işlemini argüman olarak aldığı istenen sıralamayı temsil eden değişkene göre uygulamaktadır. Tanımlanan diğer `kelime-boyu filtre hesaplama komutu` 256 bitlik veri üzerinde kaydırma işlemi yaptıktan sonra tüm baytların en anlamlı bitlerini kullanarak 32 bitlik fitre değerini üretir. Kaydırma işlemindeki kaydırma miktarı üzerinde işlem yapılan verinin dahil olduğu alfabeye göre belirlenen 0 ile 7 arasında bir değerdir. Kelime-boyu komutlar kullanılarak EPSMA (EPSMA-1,2,3) ve SSEFA algoritmaları önerilmiştir. ESPMA-1 algoritması örüntü boyunun 8'den küçük olduğu durumlar için geliştirilmiştir ve temeli `kelime-boyu karşılaştırma komutu` kullanımına dayanmaktadır. Örüntü boyunun 8 ile 32 arasında olduğu durumlar için `kelime-boyu eşleştirme komutu` baz alınarak EPSMA-2 algoritması tasarlanmıştır. Ayrıca EPSMA-2 algoritmasında ardışıl eşleştirme komutları arasında `kelime-boyu değiştirme komutu` verinin düzenlenmesi amacıyla kullanılmıştır. EPSMA-3 algoritması ise `kelime-boyu filtre hesaplama komutu` ile filtreleme metoduna dayanmaktadır ve boyu 32 ile 64 arasında olan örüntüler için uygundur. 16 karakterlik bölütü temsil eden filtre 16 bitten oluşmaktadır ve bir filtre hesaplama komutuyla aynı anda 16 bitlik 2 adet filtre elde edilmektedir. EPSMA-3'de filtreler ayrı ayrı uygulanarak olası eşleşme adayları elde edilir ve bu adaylar üzerinde tam eşleşme karşılaştırması yapılır. Boyu 64'den büyük olan uzun örüntüler için ise SSEFA algoritması önerilmiştir ve bu algoritma da `kelime-boyu karşılaştırma komutu` tabanlı filtreleme yaklaşımına dayanmaktadır. Ancak SSEFA'da filtreler 32 karakter bölütü baz alınarak hesaplandığından her 32 karakteri 32 bitten oluşan bir filtre değeri temsil eder. 32-bit filtre değeri indeks olarak kabul edilip filtre vektörü oluşturulduğunda ise vektörün boyutu filtre değerinin alabileceği maksimum değer ile belirlenir. 32 bit filtre değeri kullanıldığında vektörün boyutu 4GB olacaktır, metin üzerinde her filtre arama işleminde vektörün ilgili elemanına erişim gerekeceğinden hafızaya erişimdeki gecikmeler performans üzerinde önemli bir performans kısıtı oluşturacaktır. Optimal filtre uzunluğu ve veri tipini belirlemek için Intel Vtune Amplifier aracı ile performans analizi yapılmıştır. Vtune Amplifier Intel tarafından geliştirilen yüksek performanslı hesaplama alanında modern mimariler üzerinde performans analizi yaparak olası sorunların kaynağını tespit eden ve daha hızlı uygulamalar için yol gösteren bir analiz aracıdır. Hafızaya erişim analizi için `Hardware Event-Based Sampling (EBS)` analiz tipi seçilerek farklı filtre uzunlukları ve veri tipleri için geçen süreler, komut başına çevrim sayısı (CPI) ve L1 kayıp oranı (miss rate) değerleri elde edilmiştir. Yapılan analizler sonucu hafızaya erişmede önbelleğin optimal kullanımı açısından en uygun filtrenin 14 bit uzunluğunda olduğu ve filtrelerin bağlı liste yarine array yapısında tutulması gerektiği tespit edilmiştir. Arama işleminde filtrelemeden geçebilen eşleşme adayı sayısını azaltmak için 32 bit ham filtrenin her bir yarısındaki ayrık bitlerden oluşan 2 adet 14 bit filtre ardışıl olarak uygulanmıştır. Algoritmalar C programlama dilinde yazılmıştır, performans testleri ise dizgi eşleştirme için test platformu sunan ve literatürdeki bilinen tüm algoritmaları içeren SMART ile yapılmıştır. Performans karşılaştırma işlemi alfabe boyutu 4 olan genom sekansı, 20 olan protein sekansı ve 128 olan ingilizce metin olmak üzere 3 farklı verisetinde ve literatürde en hızlı olarak bilinen diğer algoritmalar teste eklenerek farklı örüntü uzunlukları üzerinde yapılmıştır. Performans testleri tam dizgi eşleştirme problemi için yeni önerilen algortimaların önceki en verimli olarak kabul edilen algoritmalardan farklı örüntü uzunlukları ve alfabe boyları seçeneklerinin %90'nından fazlasında daha iyi sonuç verdiğini göstermiştir. Sonuç olarak geliştirilen algoritmaların farklı alfabelerde ve örüntü boylarında pratik uygulamalar için son derece kullanışlı olduğu söylenebilir. Gelecekte ise önerilen algoritmalar ARM, AMD gibi diğer işlemci mimarilerindeki eşdeğer SIMD fonksiyonlarıyla modifiye edilerek o mimarilerde de çalışabilecek hale getirilip algoritmaları kullanan uygulamaların taşınabilirliği arttırılabilir.

Exact string matching, searching for all occurrences of given pattern P on a text T, is a fundamental issue in computer science with many applications in natural language processing, speech processing, computational biology, information retrieval, intrusion detection systems, data compression, time series analysis and etc. The speed of string matching is gaining more importance due to today applications of scientific and industrial are operating on large datasets increasing continuously. Accelerating the pattern matching operations benefiting from the SIMD parallelism has received attention in the recent literature, where the empirical results on previous studies revealed that SIMD parallelism significantly helps, while the performance may even be expected to get automatically enhanced with the ever-increasing size of the SIMD registers. The variants of the previously presented EPSM and SSEF algorithms are proposed, which are originally implemented on Intel SSE4.2 (Streaming SIMD Extensions 4.2 version with 128-bit registers). The new algorithms are designed according to Intel AVX2 platform (Advanced Vector Extensions 2 with 256-bit registers) and the gain in performance is analyzed with respect to the increasing length of the SIMD registers. Particularly in algorithms based on filtering methods, the memory access time can be the performance bottleneck when working with large decimal values such as 32-bit filter values calculated from 256-bit registers. Profiling the new algorithms by using the Intel Vtune Amplifier for detecting performance issues led us to consider the cache friendliness in the AVX2 platform. Hardware Event-Based Sampling (EBS) analysis type is selected for profiling on various filter lengths and data structures and so performance metrics of algorithms are collected. Cache optimization techniques are applied to overcome the problems particularly addressing the search algorithms based on filtering.Experimental comparison of the new solutions with the previously known-to-be-fast algorithms on small (genome sequence), medium (protein sequence), and large alphabet (English language) text files with diverse pattern lengths showed that the algorithms on AVX2 platform optimized cache obliviously outperforms the previous solutions. It can be inferred from experiments that proposed algorithms are practicable for today applications. Also, proposed algorithms can be portable to other architectures like the ARM and AMD using equivalent SIMD instructions with some modifications.