بخشی از مقاله
خلاصه
الگوریتمهای تطبیق الگو در سامانههای زیادی کاربرد دارند. برای اجرای سریعتر این الگوریتمها نیاز به پردازش موازی این الگوریتمهای داریم. برای اجرای موازی این الگوریتم، جریان دادهی ورودی را به چندین قسمت تقسیم میکنیم و هر تکه را برای هستههای پردازشی ارسال میشود. مشکل در سر مرزهای این الگوریتم که بررسی جداگانهی آنها این مشکل برطرف میشود. بعد اجرای این الگوریتم روی پردازنده مرکزی و گرافیکی و بدست آوردن نتایج شبیهسازی، نشان از برتری 18 درصدی پردازنده گرافیکی نسبت به پردازنده مرکزی در اجرای این الگوریتم دارد.
کلمات کلیدی: الگوریتم موازی، GPU، پردازش موازی
1. مقدمه
موضوع پیدا کردن و جستجو یک از بحث اولیه در علوم کامپیوتر و تعداد زیادی از کاربردها است. تطبیق الگو یکی از روشهای مؤثر برای پیدا کردن این الگو است. تطبیق الگو یعنی پیدا کردن یک رشته یا الگو در یک رشتهای از الگوها یا دادهها است. روشها و الگوریتمهای بسیار زیادی برای تطبیق الگو معرفی میشود که هر کدام دارای مزایا و معایب خاص خود میباشند.
تطبیق الگو کاربردهای بسیار زیادی ازجمله در پردازش صدا و تصویر[2 ,1] که برای شناسایی الگو با دقت بالا، فشردهسازی[4 , 3]، جستجو[5] و پژشکی[2] مورد استفاده قرار میگیرید. . تطبیق رشته چندالگو در خیلی از کاربردها شامل تشخیص نفوذ شبکه، پزشکی قانونی دیجیتالی، آنالیز تجاری و پردازش زبان طبیعی مورد استفاده قرار میگیرد.
اصل تطبیق الگو به زمانی که محققان الگوریتمهای را برای افزایش سرعت شناسایی انجام میدادند که به الگوهایی در رشته، درخت، آرایهها در دادهها برمیخوردند برمیگردد. یک از نیازهایی که امروزه برای تطبیق الگو مطرح میشود انجام الگوریتمهای تطبیق الگو با استفاده از پردازش موازی است. نیاز به سرعت باعث شده است که محققان به فکر ارائه الگوریتمهای مناسب برای سامانههای پردازش موازی شوند.
1
The 9th Symposium on Advances in Science and Technology (9thSASTech), Mashhad, Iran . 9thSASTech.khi.ac.ir
امروزه استفاده از پردازندههای گرافیکی همهمنظوره بسیار پرکاربرد شده است. اگر نگاهی به لیست 500 سوپرکامپیوتر برتر بیندازیم میبینیم که بسیاری از آنها از پردازندههای گرافیکی استفاده میکنند زیرا که نسبت به CPUها بسیار کارایی بالاتری برای پردازش موازی دارند.
2. الگوریتم Aho-Corasick
یکی از مهمترین الگوریتمهای تطبیقالگو چندگانه، الگوریتم Aho-Corasick است. این الگوریتم در سال 1975 ارائه شد.[6] نحوهای عملکرد این الگوریتم به این صورت است که از یک سری انتقالات برای شناسایی و تطبیق الگو استفاده میکند. یکسری از این انتقالات معتبر هستند و یکسری دیگر انتقالات خطا است. هر چند اسم آنها انتقال خطا است و در واقع همین انتقال است که باعث تطبیق چندین الگو میشود.
نحوهی عملکرد این الگوریتم را در شکل مشاهده میکنید. در شکل (1) خطهای پررنگ به عنوان انتقال معتبر و خطچینها به عنوان انتقال خراب شناخته میشود. در این صورت در هر داده ورودی ابتدا توسط انتقال معتبر، انتقال مییابد و اگر هیچگونه انتقال معتبری وجود نداشته باشد انتقال خراب در صورت وجود صورت میگیرد در غیر این صورت آن عملیات خاتمه مییابد. دایرههای پررنگ نشانه یک خاتمه و تطبیق یک الگو است ولی این به معنای خاتمه آن عملیات نیست بلکه ممکن الگو دیگری را هم در همین ادامه داشته باشد .
مثلا اگر کلمههای محسن، حسین، حمید و محس را به عنوان الگو در نظر بگیرم. طبق شکل (1) نحوهی انتقالات به صورت زیر میشود.
شکل :(1) نحوهی الگوهای در الگوریتم Aho-Corasick
اگر داده ورودی به صورت "نتامحسن" باشد. برای حرف ن هیچانتقالی وجود ندارد. برای حرفهای ت و الف هم همینگونه است. برای م انتقال برای ردیف اول شروع میشود، بعد از با ح وارد مرحله بعدی و سین میشود این یک حالت پایانی است و بعد از آن به نون که آن هم یک مرحله آخر است میرسد و با دایره پررنگ نشان داده شده است. در این صورت با یک داده ورودی میتوان دو الگو را شناسایی کرد. اگر جریان داده ورودی به صورت محسین باشد هم دو الگو شناسایی میشود. در این صورت تا حرف سین یک الگو شناسایی میشود و سپس بعد از آن چون برای ی بعد از س هیچگونه انتقال معتبری وجود ندارد ولی یک انتقال خطا وجود دارد در این صورت با یک انتقال خطا به ی ردیف دوم میرود و بعد از آن به ن آخر که یک مرحله پایانی است میرسد. در اینجا هم مثل جریان داده ورودی مثال قبل دو الگو شناسایی شد، با این تفاوت که در این مثال از انتقال خراب برای شناسایی دو الگو همزمان استفاده شده است. همانطور که اشاره شد این انتقالات باعث شناسایی چندالگو میشوند.
