10688

10688

تسريع هم ترازسازي زنجيره هاي بيولوژيكي بر روي شبكه پردازش موازي GPU

كارشناسي ارشد

كامپيوتر - معماري سيستم هاي كامپيوتري

تير 1391

تير 1391

دكترمحمود فتحي - دكتر رضا برنگي

هم¬ترازسازي زنجيره¬هاي بيولوژيكي به دانشمندان و محققان علم ژنتيك در تحليل و شناسايي نقاط تشابه و همپوشاني بين زنجيره¬هاي بيولوژيكي ياري خواهد رساند. اين همپوشاني¬ها نقاط اشتراك بين زنجيره¬ها در روند تكامل تدريجي و جهش¬هاي بيولوژيكي را نشان مي¬دهند كه باعث مي¬شود محققان بتوانند با اين شناخت راهكارهايي را براي پيشگيري از بيماري¬ها و همچنين درمان بيماري¬هاي منتج¬شده از ويروس¬هاي ساخته¬شده از زنجيره¬هاي بيولوژيكي ارائه دهند. از¬آنجا¬كه در اين فرآيند محدوده اطلاعات تحت جستجو و مقايسه بسيار وسيع است با استفاده از راهكارها و سخت¬افزارهاي متعارف همانند يك CPU همه¬منظوره، نمي¬توان به نتيجه مطلوب در مدت زمان قابل ¬قبول دست يافت. از¬اين¬رو استفاده از سخت¬افزارهاي تسريع¬دهنده به¬منظور تسريع هم¬ترازي به¬شدت مورد توجه قرار گرفته است. سخت¬افزارهاي تسريع¬دهنده گوناگوني نيز وجود دارند كه از ميان آن¬ها درحال¬حاضر واحد¬هاي پردازشگر گرافيكي(GPU) در كانون توجهات قرار دارند. روش¬هاي هم¬ترازسازي مختلفي وجود دارند كه عبارتند از: هم¬ترازسازي ساختاري، هم¬ترازسازي سراسري و هم ترازسازي محلي. از اين ميان، هم¬ترازسازي محلي نتايج دقيق¬تري را توليد مي¬كند. از ميان الگوريتم¬هاي هم ترازسازي محلي نيز الگوريتم اسميت واترمن از بهترين قابليت براي پياده¬سازي بر روي GPU برخوردار است، از¬آنجا¬كه اين الگوريتم دربرگيرنده هزاران عمليات ماتريسي يكسان بر روي داده¬هاي گوناگون مي¬باشد كه به واسطه نگاشت به هزاران نخ سخت¬افزاري مستقر در چند¬پردازنده¬هاي GPU، قابل موازي¬سازي مي¬باشند. در اين رساله ما روش¬هايي را ارائه خواهيم كرد كه منجر به تسريع الگوريتم اسميت واترمن بر روي شبكه پردازش موازي GPU خواهد شد. در ابتدا ساختار بانك اطلاعاتي را بر¬طبق ساختار GPU تغيير خواهيم داد و سپس روشي ارائه مي¬دهيم كه به ¬موجب¬ آن از قابليت ادغام دسترسي¬ها به حافظه سراسري GPU به بهترين شكل استفاده خواهد شد. در گام آخر نيز براي دسترسي سريع به عناصر ماتريسي مورد نياز اين الگوريتم روشي را بر¬مبناي استفاده از حافظه پرسرعت مشترك ارائه خواهيم داد كه از برخوردهاي بانكي در حين دسترسي¬ها جلوگيري مي¬كند. نتايج حاصل از آزمايش¬ها نشان مي¬دهند كه روش ما نسبت به CUDA-SW++ به¬عنوان بهترين كار انجام¬شده فعلي روي GPU، 82/1 تا 87/1 برابر و نسبت به CPU، 23/18برابر تسريع دارد. كلمات كليدي: هم¬ترازسازي زنجيره، الگوريتم اسميت واترمن، ادغام دسترسي¬ها، برخورد بانك