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