جستجوهای بیوانفورماتیکی با استفاده از یک چندپردازندۀ تک تراشه‌ای حافظه اشتراکی

چکیده

کلیدواژه‌ها

مقدمه

سازماندهی سیستم

شکل1. یک بخش گذرگاه با یک پردازنده و سه جفت رابط آسنکرون. 

شکل2. رابط آسنکرون با بافر ورودی اختیاری

شکل3. جزئیات رابط آسنکرون با پهنای داده‌ای 1 بیت. 

شکل4. بخشی از یک گذرگاه، که به ترافیک تا ریشه رسیدگی می‌کند. 

شکل5. بخشی از گذرگاه، که به ترافیک خروجی از ریشه رسیدگی می‌کند. 

تحلیل عملکرد

جدول 1 : حداکثر نرخ‌های جستجوی قابل حصول برای یک رشتۀ جستجوی 500 کاراکتری

نتیجه‌گیری

ساختار چندپردازندۀ تک تراشه‌ای حافظه اشتراکی ارائه می‌شود که مخصوصا برای عملیات محاسباتی بیوانفورماتیکی مرسوم بسیار مناسب است. این ساختار از رابط‌های گذرگاه آسنکرون برای ایجاد یک روش طراحی مدار مجتمع بهره می‌برد که امکان مقیاس‌بندی چندپردازنده با تلاش بسیار کم طراحی را میسر می‌کند. جنبۀ کلیدی این روش طراحی این است که لازم نیست منابع طراحی و مساحت تراشه روی درخت کلاک به طور قابل توجه توسعه یابد. تحلیل الگوریتم همترازسازی اسمیت- واترمن که روی این ساختار اجرا می‌شود نشان دهندۀ این مطلب است که جریمۀ عملکرد ناشی از افزایش تاخیر در مقایسه با ساختار کاملا سنکرون ناچیز است.

اغلب جستجوی پایگاه دادۀ یک پروتئین یا ژنوم برای مکانهایی مشابه با مکان‌های برخی از توالی جستجوها، موردنظر می‌باشد. این پایگاه‌ داده‌ها در حال حاضر شامل میلیاردها کاراکتر از داده‌های متوالی بوده و میزان داده‌های موجود به طور فزاینده‌ای در حال افزایش است. حتی یک جستجوی سادۀ ذهنی که به دنبال تطابق دقیق بین رشتۀ جستجو و یک زیررشته‌ از پایگاه داده است یک عمل به شدت محاسباتی است. متاسفانه، یک چنین روش ساده همواره مفید نیست. جستجوهای خوب نیازمند درنظر گرفتن این امکان است که کاراکترهای منفرد پایگاه داده ممکن است جهش یابند یا اینکه زیرتوالی‌هایی به پایگاه داده افزوده و یا از آن حذف شوند. روش‌های ابتکاری مانند BLAST و FASTA [1] موارد جهش، افزودن و حذف کردن را در نظر می‌گیرند، اما همانند الگوریتم‌های مبتنی بر برنامه‌نویسی پویا مثل اسمیت – واترمن، دارای ویژگی‌های آماری خوب تعریف شده‌ای نمی‌باشند [2]. هرچند اسمیت- واترمن از لحاظ فنی برتر است، اما زمان محاسباتی موردنیاز آن بسیار بیشتر بوده و لذا اغلب به کار نمی‌رود. چهار نوع سیستم پردازش مرسوم وجود دارد که برای پردازش همترازسازی توالی به کار می‌روند: رایانه‌های رومیزی عمومی، ابررایانه‌های عمومی، شتاب‌دهنده‌های مبتنی بر مدار مجتمع با کاربرد خاص (ASIC)، و شتاب‌دهنده‌های مبتنی بر آرایۀ گیت قابل برنامه‌ریزی میدان (FPGA). رایانه‌های رومیزی عمومی معمولا محدود به استفاده از الگوریتم‌هایی چون BLAST یا FASTA هستند چون اسمیت- واترمن خیلی کند است. سه نوع دیگر از سیستم‌های پردازنده قادر به دست و پنجه نرم کردن با اسمیت- واترمن هستند. ابررایانه‌های عمومی اغلب بسیار گرانقیمت هستند، اما این هدف این مقاله است که به ابررایانه‌های عمومی کم‌بهاتر نگاهی بیندازد. شتاب‌دهنده‌های مبتنی بر ASIC دارای این نقص هستند که حجم محصول برای ASIC کوچک خواهد بود و بنابراین هزینه‌های طراحی را نمی‌توان روی واحدهای بسیار زیادی توزیع کرد. نمونه‌های از این نوع شتاب‌دهنده‌ها عبارتند از Kestrel [3]، SAMBA [4]، و GeneMatcher2 [5]. عملکرد Kestrel در بخش3 بحث شده است، SAMBA نسخۀ نسبتا قدیمی بوده (1997) و GeneMatcher2 اختصاصی است، بنابراین اطلاعات چندان زیادی روی جزئیات طراحی آن در اختیار نیست. شتاب‌دهنده‌های مبتنی بر FPGA از لحاظ طراحی کم‌بهاتر هستند، اما هزینۀ واحد FPGAها (که به صورت یک بخش استاندارد از یک کمپانی FPGA خریده می‌شود) نسبتا گران است. نمونه‌ای از یک شتاب‌دهندۀ مبتنی بر FPGA، DeCypher [6] است که دارای طراحی اختصاصی است.