‫ موازی‌سازی کارا و تسریع عملیات انطباق رشته‌ها بر روی بستر پردازنده های چند هسته ای

موازی‌سازی کارا و تسریع عملیات انطباق رشته‌ها بر روی بستر پردازنده های چند هسته ای

میلاد غفوری, آرمین احمدزاده, سعید گرگین

چکیده

انطباق رشته‌ها یک بحث پایه‌ای و پرکاربرد در بیوانفورماتیک است که جهت یافتن میزان مشابهت توالی‌های آمینواسیدی و یا رشتههای دی.ان.ای از آن استفاده می‌شود. عمل انطباق دو رشته با یکدیگر یک عمل پایه‌ای است که در انطباق‌های چندگانه نیز از آن استفاده می‌شود. یکی از الگوریتم‌های انطباق دو رشته، الگوریتم نیدلمن-وانچ است که در آن از شیوه‌ی برنامه‌سازی پویا برای انجام این عملیات استفاده می‌شود. از چالش‌های مطرح در این الگوریتم، بالا بودن پیچیدگی زمانی آن است که جهت بهبود در سرعت اجرای این الگوریتم از راه‌کارهایی موازی می‌توان استفاده نمود. از این‌رو با ظهور پردازنده‌های چندهسته‌ای و امکان انجام محاسبات به شکل موازی می‌توان تسریع قابل ملاحظه‌ای را بدست آورد. بر اساس روش¬های موازی‌سازی موجود برای این الگوریتم، در هر گام خانه‌های آرایه‌ی به کار رفته در روش برنامه‌سازی پویا یک قطر به‌طور همزمان و موازی تکمیل می‌شود. در این مقاله با یک تغییر دیدگاه نسبت به مسئله و در نظر گرفتن یک تصور گراف گونه، روشی ارائه شده‌است تا به نسبت روش‌های پیشین تسریع مناسبی را ارائه کند. نتایج بدست آمده نشان می دهد، در این پیاده‌سازی بهبود عملکردی تا حدود 5.9 برابر نسبت به پیاده‌سازی‌های پیشین حاصل می گردد.

کلمات کلیدی

الگوریتم نیدلمن-وانچ (Needleman-Wunsch), انطباق رشته ها, بیوانفورماتیک, موازی سازی