پروژه متلب پیاده سازی الگوریتم YEN به صورت موازی بر مبنای پردازش موازی بر مبنای CUDA با استفاده از پردازنده گرافیکی GPGPU مورد بررسی قرار گرفته است.
الگوریتم‌های تطابق رشته ای، که گاهی الگوریتم‌های جسیتجوی رشته ای گقته می‌شوند، دسته مهمی از الگوریتم‌های رشته‌ای هستند که سعی می‌کنند محل رخداد یک یا چند رشتهدر یک رشته بزرگتر (یا متن) را پیدا کنند.
Σ را مجموعه الفبای محدودی فرض کنید.معمولا، هم الگو و هم متن مورد نظر، ترکیبی از عناصرΣ می‌باشند. Σ می‌تواند یک الفبای انسانی معمولی باشد (مثلا، حروف A تا Z در زبان انگلیسی). در کاربردهای دیگر ممکن است از الفبای دودویی ({(Σ = {۰,۱) یا الفبای DNA در بیوانفورماتیک استفاده شود. به طور خاص، این که رشته چگونه رمز شده‌است می‌تواند روی الگوریتم ملموس تطابق، تاثیر گذار باشد. مخصوصا اگر رمز نگاری طولی متغیر مورد استفاده قرار گیرد، به کندی می‌توان کاراکتر N ام را پیدا کرد. این می‌تواند به طور محسوسی الگوریتم‌های جستجوی پیشرفته تر را کند، کند. یک راه حل این است که به دنبال دنباله‌ای از واحدهای رمز بگردیم، اما این روش ممکن است باعث ایجاد مطابقت‌های اشتباه گردد. اگر رمز نگاری به گونه‌ای خاص طراحی شده باشد، از این مشکل جلوگیری می‌شود. در تئوری اطلاعات فاصله‌ی همینگ برای دو رشته با طول مساوی، برابر تعداد مکانهایی است که سمبولهای متناظر متفاوت هستند. به عبارت دیگر، کمترین تعداد جایگزینی هایی است که یک رشته به یک رشته دیگر تغییرپیدا کند، یا تعداد خطاهایی که یک رشته به رشته دیگر تبدیل گردد. برای یک طول ثابت n، فاصله همینگ یک معیاراندازه روی فضای برداری از کلماتی با آن طول می‌باشد، بطوریکه دارای شرایط غیر منفی، هویت متقارن و غیر قابل تشخیص تحقق می‌یابد، و آن می‌تواند بخوبی مساله ارضاء نابرابری مثلث رابوسیله استقراءکامل نشان دهد. فاصله همینگ بین دوکلمه a و b می‌تواند همچنین بوسیله وزن هامینگ a-b برای یک انتخاب مناسب از عملگر – مشاهده گردد. برای رشته دودویی a و b فاصله همینگ برابر با تعداد یک‌های a یای مانعةالجمع b می‌باشد. فضای برداری رشته‌های دودویی با طول n، با فاصله همینگ، بعنوان Hamming cube شناخته می‌شود;که آن معادل با فضای برداری مجموعه فواصل بین برداری در یک گراف ابر مکعبمی‌باشد. می توان یک رشته دودویی با طول n رادر نشان داد بطوریکه هر سمبل در رشته بعنوان یک مولفه حقیقی رفتار نماید. با این تعبیه، رشته هاراس‌های یک ابرمکعب n بعدی را شکل می‌دهند، و فاصله همینگ رشته‌ها برابر با فاصله مانهاتان )فاصله منهتن(بین راس‌ها می‌باشد.
Parallel Algorithms for Approximate String Matching with k mismatches on cuda
Abstract :
Approximate string matching using the k – mismatch technique has been widely applied to many fields such as virus detection and computational biology . The traditional parallel algorithms are all based on multiple processors , which have high costs of computing and communication . GPU has high parallel processing capability , low cost of computing , and less time of communication . To the best of our knowledge , there is no any parallel algorithm for approximate string matching with k mismatches on GPU . With a new parallel programming model based on cuda , we present three parallel algorithms and their implementations on GPU , namely , the thread parallel algorithm , the block – thread parallel algorithm , and the OPT – block – thread parallel algorithm . The OPT – block thread parallel algorithm can take full advantage of the powerful parallel capability of GPU . Furthermore , it balances the load among the threads and optimizes the execution time with the memory model of GPU . Experimental results show that compared with the traditional sequential algorithm on CPU , our best parallel algorithm on GPU in this paper achieves speedup of 40 – 80 .
الگوریتم‌های موازی برای انطباق تقریبی با k عدم mismatches در cuda
چکیده:
تطابق رشته‌ای تقریبی با استفاده از تکنیک k – mismatch به طور گسترده برای بسیاری از زمینه‌ها مثل تشخیص ویروس و زیست‌شناسی محاسباتی اعمال شده‌است. الگوریتم‌های موازی سنتی همگی بر پایه پردازنده‌های چند گانه هستند، که هزینه‌های بالایی از محاسبه و ارتباط دارند. GPU دارای قابلیت پردازش موازی بالا، هزینه پایین محاسبه و زمان کم‌تر ارتباط است. برای بهترین دانش ما، هیچ الگوریتم موازی برای تطابق رشته‌ای تقریبی با k mismatches در GPU وجود ندارد. ما با یک مدل برنامه‌نویسی موازی جدید مبتنی بر cuda، سه الگوریتم موازی و اجرای آن‌ها را بر روی GPU، یعنی، الگوریتم موازی رشته‌ای، الگوریتم موازی رشته رشته‌ای، و الگوریتم موازی – بلوکی present ارایه می‌دهیم. الگوریتم موازی رشته‌ای OPT – بلوکی نیز می‌تواند مزیت کامل قابلیت موازی قوی GPU را به دست آورد. علاوه بر این، آن بار در میان نخ‌ها را متعادل می‌کند و زمان اجرا را با مدل حافظه of بهینه می‌کند. نتایج تجربی نشان می‌دهد که در مقایسه با الگوریتم ترتیبی سنتی روی CPU، بهترین الگوریتم موازی ما روی GPU در این مقاله به سرعت ۴۰ – ۴۰ دست می‌یابد.
لطفاً براي ارسال دیدگاه، ابتدا وارد حساب كاربري خود بشويد