بخشی از مقاله
چکیده
در دنیای امروزی بسیاری از عملیات توسط سیستم های کامپیوتری انجام می گیرد. این عملیات شامل دستوراتی مانند مرتب سازی ، مقایسه و ... می باشند که برای پیاده سازی آن ها روش های مختلفی موجود است. یکی از روش های بسیار رایج در این زمینه استفاده از نرم افزار جهت انجام پردازش ها و به دست آوردن نتایج است. از طرفی نرم افزار های موجود نسبت به پیاده سازی های سخت افزاری سرعت نسبتا پایین تری دارند . در نتیجه استفاده از روش های سخت افزاری نسبت به الگوریتم های نرم افزاری از سرعت بالاتری برخوردار است. برای ساخت سخت افزار ها روش های مختلفی وجود دارد که یکی از این روش ها ، استفاده از زبان های توصیف سخت افزار است. به کار گرفتن این زبان ها علاوه بر سادگی انجام کار ، باعث سرعت در انجام فرایند طراحی مدار شده و عملیات تست و سنتز را ساده می کند.
یکی از زبان هایی که جهت توصیف سخت افزار از آن استفاده می شود و توسط IEEE نیز استاندارد شده زبان Verilog است که در مقاله از آن استفاده شده است. مرتب سازی سریع که می توان آن را بصورت بازگشتی نیز پیاده سازی نمود. در این مقاله این الگوریتم به بازگشتی مورد بررسی قرار گرفته و پس از توضیح مکانیزم کار آن ، بوسیله زبان Verilog پیاده سازی شده است .در نهایت زمان مورد نیاز جهت انجام عملیات مرتب سازی برای این الگوریتم در پیاده سازی سخت افزاری و نرم افزاری با هم مقایسه و مورد بررسی قرار گرفته و نشان داده شده که انجام عملیات بصورت سخت افزاری داری سرعت بیشتر و زمان اجرای کمتری می باشد.
.1 مقدمه
الگوریتم مرتبسازی، در دانش رایانه و ریاضی، الگوریتمی است که فهرستی از دادهها را به ترتیبی مشخص میچیند. پرکاربردترین ترتیبها، ترتیبهای عددی و واژهنامهای هستند. مرتبسازی کارا در بهینهسازی الگوریتمهایی که به فهرستهای مرتب شده نیاز دارند - مثل جستجو و ترکیب - اهمیت زیادی دارد.از آغاز علم رایانه مسائل مرتبسازی بررسیهای فراوانی را متوجه خود ساختند، شاید به این علت که در عین ساده بودن، حل آن به صورت کارا پیچیده است. برای نمونه مرتبسازی حبابی در سال 1956 به وجود آمد. در حالی که بسیاری این را یک مسئله حل شده میپندارند، الگوریتم کارآمد جدیدی همچنان ابداع میشوند.
- مثلاً مرتبسازی کتابخانهای در سال 2004 مطرح شد - مبحث مرتبسازی در کﻻسهای معرفی علم رایانه بسیار پرکاربرد است، مبحثی که در آن وجود الگوریتمهای فراوان به آشنایی با ایدههای کلی و مراحل طراحی الگوریتمهای گوناگون کمک میکند؛ مانند تحلیل الگوریتم، دادهساختارها، الگوریتمهای تصادفی، تحلیل بدترین و بهترین حالت و حالت میانگین، هزینه زمان و حافظه، و حد پایین.برخی از الگوریتم های مرتب سازی هم بصورت بازگشتی و هم بصورت غیر بازگشتی قابل پیاده سازی هستند که از آن جمله می توان الگوریتم مرتب سازی ادغامی را به عنوان یک مرتب سازی بازگشتی بررسی می کنیم .
در این الگوریتم مساله به چند جزء کوچکتر تقسیم میشود. هر کدوم از این قسمتها رو به طور مجزا حل کرده، و با ترکیب آنها به مساله اصلی میرسیم .در این روش دادهها به دو قسمت مساوی تقسیم میشوند، و هر کدوم از این قسمتها - به صورت بازگشتی - مرتب، و با ادغام آنها دادها بصورت کامل مرتب میشوند. اما توجه به این نکته ضروری است که اگر پس از یک بار تقسیم باز هم لیستهای ایجاد شده بزرگ باشند، میتوانیم برای هر زیر لیست مراحل بالا را دوباره انجام دهیم تا به زیر لیستهایی با تنها 1 عضو برسیم و واضح است که لیست تک عنصری خود مرتب است.پیاده سازی این الگوریتم ها با هر زبان برنامه سازی ممکن می باشد اما استفاده از زبان های برنامه سازی ، عملا استفاده کردن از یک نرم افزار است. درصورتیکه بتوان عملیاتی که توسط نرم افزار صورت می گیرد را در سخت افزار پیاده سازی نمود سرعت انجام عملیات بواسطه این پیاده سازی رشد خواهد یافت.
.2 معرفی FPGA
FPGA یک سخت افزار خام قابل پیکربندی است که قابلیت کار با داده های دیجیتال را دارد. بنابراین یک روش پیاده سازی الگوریتم بر سخت افزار را می توان استفاده از آن دانست. FPGA ها دارای نرم افزارهایی جهت پیکر بندی مثل VHDL یا VERILOG و ... هستند که در این تحقیق یک روش مرتب سازی با استفاده از این نرم افزار ها روی FPGA پیاده سازی خواهد شد.فن آوری آرایه سوئیچ فیوزهای قابل برنامهریزی چند باره، انقلابی نوین را در عرصه طراحی دیجیتال به وجود آورد که مفهوم طراحی دیجیتال را دچار تحولی عظیم در عرصه های دیدگاه معماری، حجم طراحی، سرعت و نوع نگرش به طراحی دیجیتال نموده است.
طوری که امروزهFPGA ها - آرایه های گیتی قابل برنامهریزی میدانی - یک بوم نقاشی سفید را در اختیار طراح قرار میدهند که به او اجازه میدهد تا طراحی دیجیتال خود را آنچنان که میخواهد و با هر حجم و پیچیدگی لازم، طراحی و سپس به جای انتخاب IC های استاندارد و جدا از هم و کنار هم قراردادن آنها در روی یک مدار و وصل کردن آنها از طریق یک بورد مدار چاپی، با استفاده از یکی از زبانهای توصیف سختافزاری نظیرVHDL ،هر یک از قطعات دیجیتالی مورد نیاز را نوشته و با وصل کردن نرم افزاری آنها، سرانجام فایل کامپایل شده نهایی را از طریق یک رابط سخت افزاری بر روی یک بسته سخت افزاری خام با تعداد پایه های مورد نیاز برنامه ریزی کرده و از این IC جدید "خود ساخته" استفاده کند
FPGA .ها نسل جدید مدارهای مجتمع دیجیتال قابل برنامه ریزی هستند که عبارت FPGA از سر کلمه های Field Programmable Logic Gate Array گرفته شده است. سرعت اجرای توابع منطقی در FPGA ها بسیار بالا و در حد نانو ثانیه است. اگر بخواهیم FPGAها را به طور ساده تشریح کنیم، عبارت است از یک تراشه که از تعداد بالایی بلوکهای منطقی، خطوط ارتباطی و پایه های ورودی/ خروجی تشکیل شده است که به صورت آرایه ای در کنار یکدیگر قرار دارند. خطوط ارتباطی که وظیفهء آنها ارتباط بین بلوک های منطقی است از سوئیچهای قابل برنامه ریزی تشکیل شده اند. این سوئیچها بسته به نوعی که دارند، برخی تنها یکبار برنامه ریزی هستند و برخی به تعداد دفعات زیادی برنامه ریزی می شوند.
بلوکهای منطقی نیز دارای انواع مختلفی هستند که عموما توسط المانی پایه، تمامی توابع منطقی را ایجاد می کنند. به عنوان مثال بلوکهای منطقی در خانواده ACT-1 از شرکتActel ، با پایهء مالتی پلکسری عمل می کنند. به این معنا که توسط مالتی پلکسر، توانایی ایجاد توابع منطقی مختلف را دارند.البته تعداد ورودی های هر بلوک منطقی متفاوت است و به نوع FPGA مربوط می شود. به عنوان مثال بلوک های منطقی در خانوادهء ACT-1، از نوع 8 ورودی است. البته در برخی موارد به بلوکهای منطقی سلولهای منطقی نیز گفته می شود. بلوک دیاگرام یک FPGA به طور ساده در شکل زیر نشان داده شده است.
شکل شماره - - 1 بلوک دیاگرام یکFPGA
البته بسیاری از سلول های منطقی بر اساس جداول LUT ساخته می شوند LUT .از تعدادی سلولهای حافظه SRAMتشکیل میشود که در هنگام برنامهریزی FPGA، مقداردهی می شوند. به طور خلاصهLUT عبارت است از تولید توابع آماده برای استفاده در سلولهای منطقی.پیاده سازی توابع مختلف نیز به وسیله در کنار هم قرار گرفتن بلوکهای منطقی و همچنین تنظیم ارتباط بین هر بلوک و به عهده گرفتن پردازش اطلاعات توسط هر بخش انجام می شود.در شکل زیر ساختار داخلی یک FPGAنشان داده شده است. که در آن بلوک های منطقی، سلولهای ورودی و خروجی، ارتباط بین سگمنتها و در شکلهای کوچکتر جزییات بلوکهای C و S نشان داده شده است.
