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