امیرحسین براری-27/4/91

 | آخرین بروزرسانی: 1391/4/24 | 

 

AWT IMAGE

آقای امیرحسین براری دانشجوی کارشناسی ارشد جناب آقایان دکتر محمود فتحی و دکتر رضا برنگی روز سه شنبه 27/4/91 ساعت 9:30 صبح در اتاق دفاعیه واقع در طبقه سوم دانشکده کامپیوتر از پروژه کارشناسی ارشد خود تحت عنوان تسریع همترازسازی زنجیره های بیولوژیکی بر روی شبکه پردازش موازی GPU دفاع خواهند نمود.

 

  چکیده پایان نامه:

  هم ترازسازی زنجیره های بیولوژیکی به دانشمندان و محققان علم ژنتیک در تحلیل و شناسایی نقاط تشابه و همپوشانی بین زنجیره های بیولوژیکی یاری خواهد رساند.این همپوشانی ها نقاط اشتراک بین زنجیره ها در روند تکامل تدریجی و جهش های بیولوژیکی را نشان می دهند که باعث می شود محققان بتوانند با این شناخت راهکارهایی را برای پیشگیری از بیماری ها و همچنین درمان بیماری های منتج شده از ویروس های ساخته شده از زنجیره های بیولوژیکی ارائه دهند.از آنجا که در این فرآیند محدوده اطلاعات تحت جستجو و مقایسه بسیار وسیع است با استفاده از راهکارها و سخت افزارهای متعارف همانند یک CPU همه منظوره، نمی توان به نتیجه مطلوب در مدت زمان قابل قبول دست یافت. از این رو استفاده از سخت افزارهای تسریع دهنده به منظور تسریع هم ترازی به شدت مورد توجه قرار گرفته است. سخت افزارهای تسریع دهنده گوناگونی نیز وجود دارند که از میان آن ها در حال حاضر واحد های پردازشگر گرافیکی( GPU ) در کانون توجهات قرار دارند.

  روش های هم ترازسازی مختلفی وجود دارند که عبارتند از: هم تراز ساختاری، هم ترازسازی سراسری و هم ترازسازی محلی. از این میان، هم ترازسازی محلی نتایج دقیق تری را تولید می کند.از میان الگوریتم های هم ترازسازی محلی نیز الگوریتم اسمیت واترمن از بهترین قابلیت برای پیاده سازی بر روی GPU برخوردار است، از آنجا که این الگوریتم دربرگیرنده هزارانعملیات ماتریسی یکسان بر روی داده های گوناگون می باشد که بواسطه نگاشت به هزاران نخ سخت افزاری مستقر در چند پردازنده های GPU ، قابل موازی سازی می باشند.

  در این گزارش ما روش هایی را ارائه خواهیم کرد که منجر به تسریع الگوریتم اسمیت واترمن بر روی شبکه پردازش موازی GPU خواهد شد. در ابتدا ساختار بانک اطلاعاتی را بر طبق ساختار پردازش موازی GPU تغییر خواهیم داد و سپس روشی ارائه می دهیم که به موجب آن از قابلیت ادغام دسترسی ها به حافظه سراسری GPU به بهترین شکل استفاده خواهد شد. در گام آخر نیز برای دسترسی سریع به عناصر ماتریسی مورد نیاز این الگوریتم روشی را بر مبنای استفاده از حافظه پرسرعت مشترک ارائه خواهیم داد که از برخوردهای بانکی در حین دسترسی ها جلوگیری می کند. نتایج حاصل از آزمایشات نشان می دهند که روش ما نسبت به بهترین کار انجام شده روی GPU ، 1.82 تا 1.87 برابر و نسبت به CPU ، 18.23 برابر تسریع داشته است.

  کلمات کلیدی:

  هم ترازسازی زنجیره، الگوریتم اسمیت واترمن، ادغام دسترسی ها، برخورد بانک

  Abstract :

  Biological sequences alignment will help to genetic science researchers and scientists for analysis and identification of similarity and overlapping points between biological sequences. This overlapsshow shared points between sequences in gradual evolutionary process and biological mutations so that it causes researchers can by this knowledge propose methods for diseases avoidance and treatment of diseases are resulted from viruses made of biological sequences. Because in this process the information domain of under searches and comparisonsare huge, the use of typical methods and hardwaresare not effective.Therefore the use of hardware accelerators for alignment acceleration is noteworthy. There are various hardware accelerators that among them graphical processing units (GPU) are remarkable.

  There are various alignment methods that arecontaining structural alignment, global alignment and local alignment. Among them local alignment produce more exactly results. Among the local alignment algorithms, smith waterman algorithm has best capability for implementation on the GPU. Because that this algorithm contains a lot of equal matrix operations on the different data that canbe parallelized onnumerous hardware threads located on the GPU multiprocessors.

  In this thesis, we present methods that cause to accelerate smith waterman algorithm on the GPU parallel processing network. At first, we change database structure according to GPU parallel processing structure and then propose a method that through it, we use capability of accesses coalescing to GPU global memory in best possible form. In the final step we propose a method for fast access to needed matrix elements for this algorithm based on use fast shared memory, so that it prevent of bank conflicts in access times. Experimental results show that our method with respect to best GPU-basedimplemented workuntil now, have 1.82 to 1.87 times speedup and with respect to CPU have 18.23 times speedup.

 

  Keywords:

  Sequence alignment, smith waterman algorithm, accesses coalescing, bank conflict

 

 

 

 

 

  ارائه­دهنده:

امیرحسین براری

  مهندسی کامپیوتر-معماری سیستم های کامپیوتری

  استاد راهنما:

 آقایان دکتر محمود فتحی و دکتر رضا برنگی

  استاد ممتحن داخلی : دکتر مهدی فاضلی

  استاد ممتحن خارجی :دکتر مرتضی صاحب الزمانی

  زمان : سه شنبه 27 خردادماه 91

  ساعت9:30 صبح

  مکان: دانشکده مهندسی کامپیوتر- طبقه سوم- اتاق دفاعیه

  از اساتید بزرگوار، دانشجویان گرامی و دیگر متخصصان و علاقه مندان به موضوع دفاعیه دعوت
می شود با حضور خود موجبات غنای علمی و ارتقای کیفی را فراهم سازند.

  دانشکده مهندسی کامپیوتر مدیریت تحصیلات تکمیلی


دفعات مشاهده: 5381 بار   |   دفعات چاپ: 1427 بار   |   دفعات ارسال به دیگران: 40 بار   |   0 نظر