انجمن کامپیوتر ایران

هم¬ترازسازی زنجیره¬های بیولوژیکی به بیولوژیست¬ها در تحلیل و شناسایی نواحی مشابهت بین این زنجیره¬ها یاری خواهد رساند. این مشابهت¬های یافت¬شده نقاط مشترک بین زنجیره¬ها در روند تکامل تدریجی و همچنین جهش¬های بیولوژیکی را نشان می¬دهند. روش¬های هم¬ترازسازی مختلفی وجود دارند. الگوریتم اسمیت¬واترمن که مبتنی بر برنامه¬نویسی پویا می¬باشد یکی از دقیق¬ترین روشها برای هم¬ترازسازی زنجیره است،با این وجود این الگوریتم دارای میزان بسیار زیادی از محاسبات ماتریسی زمان¬بر است و ازاینرو می¬توان به¬منظور افزایش سرعت پردازش این الگوریتم، آن را از طریق شتاب¬دهنده¬های سخت¬افزاری موازی¬سازی و تسریع کرد. در این مقاله روش¬هایی ارائه می¬شود که منجر به تسریع این الگوریتم بر روی شبکه پردازش موازی GPU بر مبنای چارچوب CUDA خواهد شد. بهبود¬های ارائه¬شده در طی یک فرایند سه مرحله ای اعمال خواهند شد. در ابتدا ساختار بانک اطلاعاتی حاوی زنجیره¬های بیولوژیکی، تبدیل به ساختاری متناظر با مدل پردازش موازی GPU خواهد شد. سپس در مرحله بعد دسترسی¬ها به حافظه سراسری GPUجهت استفاده حداکثری از پهنای باند ادغام خواهند شد. در نهایت نیز روشی به¬منظور جلوگیری از برخورد پیمانه های حافظه مشترک GPU در نتیجه دسترسی¬های همزمان پرهزینه به پیمانه های آن ارائه خواهد شد. بررسی¬های انجام¬گرفته نشان می¬دهند که روش پیشنهادی دارای تسریع 82/1 تا 87/1 برابری، نسبت به CUDASW++ به عنوان یکی از سریع¬ترین پیاده¬سازی¬های انجام¬شده بر رویGPU، می¬باشد. همچنین این روش دارای تسریع 23/18 برابری نسبت به یک راه¬حل مبتنی بر CPU می¬باشد.