16522

16522

موازي‌سازي الگوريتم‌هاي تطبيق الگو روي پردازنده‌هاي چند ريسماني

كارشناسي ارشد

الكترونيك

دي ماه 1394

دكتر هادي‌شهريار شاه‌حسيني

برق

چكيده الگوريتم‌هاي تطبيق الگو در كاربردهاي زيادي مورد استفاده قرار مي‌گيرد و از مهم‌ترين آن‌ها استفاده از آن در توالي‌ياب DNA و سامانه‌هاي‌ تشخيص نفوذ در شبكه است كه با تطبيق دادن الگو‌هاي حمله، باعث تشخيص حمله به شبكه مي‌شود و در توالي‌ياب DNA، يك توالي خاص را پيدا مي‌كند. با توجه به اينكه پهناي باند شبكه‌هاي رايانه‌ي، هر روزه در حال افزايش است و اينكه داده‌هاي DNA بسيار زياد است، لذا خيلي مهم است كه سرعت تطبيق دادن الگو را افزايش دهيم . امروزه از واحد پردازشگر گرافيكي، به دليل قدرت بالاي محاسباتي و ارزان‌قيمت بودن، در پردازش موازي بسيار استفاده مي‌شود. الگوريتم رابين-كرپ يك الگوريتم‌ تطبيق الگو است. ما روش جديدي براي اجراي موازي الگوريتم رابين-كرپ روي پردازنده‌هاي گرافيكي ارائه شده است و در اين روش با استفاده از دسته‌بندي الگو‌ها، سبب افزايش ميزان تسريع نسبت به حالت معمول موازي‌سازي مي‌شود. اين روش اجرا دو مزيت دارد، يكي اينكه تعداد مقايسه مقادير درهم‌سازي را كاهش مي‌دهد و ديگر اينكه با توجه به كم كردن تعداد مقايسه، ميزان خواندن الگوها از حافظه سراسري پردازنده‌اي گرافيكي كم مي‌شود. با توجه به اينكه تبادل با حافظه هميشه يك تنگنا در كار با پردازنده‌هاي گرافيكي است، لذا كم كردن تبادل با حافظه مي‌تواند به بهبود گذردهي خروجي منجر شود. روش پيشنهادي دسته‌بندي الگوها براي دو حالت كلي مورد آزمايش قرار گرفت در يك حالت تعداد حروف موجود 26 باشد و حالت ديگر براي توالي‌ياب DNA كه تعداد حروف موجود 4 باشد. هر كدام از اين حالت‌ها براي سه حالت افزايش داده ورودي، افزايش تعداد الگو و افزايش طول الگو بر روي پردازنده‌هاي گرافيكي شركت انويديا با استفاده از بستر نرم‌افزاري كودا مورد پياده‌سازي قرار گرفت. براي حالتي كه تعداد حروف زياد باشد ميزان تسريع به اندازه 1.88 برابر نسبت به روش قبلي موازي‌سازي روي پردازنده‌هاي گرافيكي حاصل شد. بهترين نتيجه براي حالت افزايش تعداد‌ الگوها، نشان از دست يافتن به تسريع 3.22 مي‌دهد. اما براي توالي DNA به دليل اينكه تعداد حروف موجود 4 است و در نتيجه فقط 4 دسته‌ وجود دارد، بنابراين باعث بالا رفتن احتمال تلاش نادرست در الگوريتم رابين-كرپ مي‌شود كه در اين صورت نتايج پياده‌سازي به خوبي زماني كه تعداد حروف زياد باشد، نيست و براي حالت افزايش تعداد الگوها تسريع 1.63 بدست آمد. واژه‌هاي كليدي: الگوريتم تطبيق الگو، الگوريتم رابين-كرپ، پردازش موازي، CUDA، GPU، سامانه تشخيص نفوذ به شبكه، توالي‌ياب DNA

1395/11/17

1/1/1900 12:00:00 AM

Abstract: Pattern matching algorithms are used in many areas. One of their most important applications is in the network intrusion detection systems (NIDS) an​d DNA sequencing. Given the fact that Internet bandwidth is increasing by the day, it is highly important to speed up pattern matching. There are many ways to increase your speed, but is one of the most optimal ways to implement parallel processing algorithms. Today, the Graphics Processor Unit, due to the high power of parallel computing an​d cheap, widely used in parallel processing. The Rabin-Karp algorithm can be used for both single-pattern an​d multi-pattern matching. Nowadays GPUs are implemented due to their high processing power in parallel computations an​d their cheap prices in parallel processing. A new method was proposed for parallel execution of the Rabin-Karp algorithm. In this method, classification of patterns was used to prevent redundant comparisons an​d increase the speed up rate. This procedure has two advantages, one that reduces the number of comparators hash values an​d that given the low number of comparison, the reading patterns of global memory graphics processor is low. Given that the exchange is always a dilemma in memory parallel processing GPU, so the exchange with memory loss can lead to improved throughput output. The proposed algorithm was tested on GPUs powered by NVIDIA in two general cases. In one case large number of letters other case for sequencing DNA that is of little letters. Each of these cases has increased for three entries, increase the number of pattern an​d extend the pattern were compared on NVIDIA GPUs using CUDA Platform was about implementation. When the number of characters is large, the acceleration was good, especially for the increasing number of patterns, the results of more than three times the reach to accelerate. But due to the low number of letters of DNA sequence an​d thus the low number of categories, as well as increased risk of incorrect attempts at Robin algorithm-crepe, good results when the number of characters is large is not. As a result of the algorithm Rabin-Karp for applications where a large number of letters in it much more suitable for applications that have a small number of letters. Because when the number of characters is large, you can create many categories in which case the maximum benefit from the proposed method can be used Categories patterns. Keywords: Pattern Matching; Rabin-Karp; GPU; NIDS; Parallel Processing; DNA sequencing