موازی سازی الگوریتم ساخت آرایه پسوندی به منظور تطبیق دقیق رشته های DNA برروی پردازنده گرافیکی
Paper ID : 1145-ICTCK (R3)
Authors:
1سعیده ظریف *, 2حسین دلداری
1دانشگاه آزاد
2دانشگاه آزاد اسلامی واحد مشهد
Abstract:
چکیده - آرایه‌های پسوندی یک‌رشته، مجموعه‌ی مرتبی از تمام پسوندهای آن رشته هستند که این ساختمان داده در زمینه‌های شاخص گذاری متن، فشردگی داده و تطبیق الگو کاربرد دارند. در دهه اخیر، الگوریتم‌های سری زیادی برای ساخت آرایه‌های پسوندی ارائه‌شده است. در این مقاله بر روی یکی از دسته‌های اصلی الگوریتم‌های ساخت آرایه‌های پسوندی مطالعه‌ای انجام شد و هدف موازی‌سازی یکی از الگوریتم‌های سری ارائه‌شده در دسته دوم بر روی معماری موازی پردازنده‌ی گرافیکی است. الگوریتم SA-IS (Suffix Array-Induce Sorting) که یک الگوریتم بازگشتی بازمان خطی است، قابلیت موازی‌سازی به روش تقسیم و غلبه را دارد و جزء آخرین کارهای تحقیقاتی در این دسته است را می‌توان به‌صورت موازی بر روی سخت‌افزار پردازنده گرافیکی پیاده‌سازی کرد. این الگوریتم توسط پلت فرم کودا با استفاده از تکنیک‌های پردازنده‌ی گرافیکی قابل پیاده‌سازی است. سرعت این الگوریتم موازی نسبت به الگوریتم سری آن درداده هایی با حجم بالا تا 40 برابر و نسبت به الگوریتم موازی مشابه در دسته خودش 2/1 برابر افزایش می‌یابد.
Keywords:
کلیدواژه- آرایه‌های پسوندی، الگوریتم SA-IS ، پردازنده‌ی گرافیکی،کودا.
Status : Paper Accepted