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

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

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

188911

دانشگاه علم و صنعت ايران

الكترونيك

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