بخشی از مقاله
طراحی و سنتز یک پردازنده جانبی به منظور مرتب سازی اطلاعات با استفاده از حافظه داخلی آرایه های برنامه پذیر
چکیده مقاله:
مرتب سازی داده ها یکی از مسائل مهم در هنگام پردازش اطلاعات دیجیتال می باشد. بسته به نحوه پیاده سازی مرتب کننده، معمولاً سه پارامتر سرعت، سطح اشغالی بر روی تراشه و توان مصرفی از اهمیت ویژه برخوردار هستند. وقتی مرتب کننده بر روی آرایه های منظقی برنامه پذیر (FPGA) پیاده سازی شود، از آنجا که این بلوک به عنوان یک پردازشگر جانبی در کنار سایر بلوک های افزاری قرار می گیرد، تعداد CLB های اشغال شده پارامتری مهم می باشد. در این مقاله، از الگوریتم جدیدی به منظور پیاده سازی مرتب کننده استفاده نموده ایم تا حداقل تعداد CLB ها اشغال گردند. بر خلاف همه الگوریتم های قبلی که از مقایسه کننده به منظور مرتب سازی استفاده می کنند در این روش، نیازی به این بلوک وجود ندارد و عمده پردازش، با کمک حافظه با دسترسی تصادفی انجام می شود. در نتیجه علاوه بر اینکه تعداد کمتری ازCLB ها بر روی تراشه اشغال شده و ساختار ساده تر می شود، قابلیت اطمینان نیز بالاتر می رود. به منظور نشان دادن کارایی این نحوه پیاده سازی، سنتز یک مرتب کننده 256 کلمه ای و با طول کلمه 16 بیتی بر روی یک FPGA از نوع Xilinx Spartan3 XC3S1500 انجام شده است.
-1 مقدمه
از بدو پیدایش ریز پردازنده های برنامه پذیر، مسئله مرتبسازی اطلاعات مطرح بوده و مورد اهتمام طراحان قرار گرفته است. با توجه به کاربرد وسیع این مسئله در پردازش سخت افزاری اطلاعات، در حال حاضر گرایش بیشتر به سمت استفاده از یک پردازشگر جانبی به منظور مرتب سازی اطلاعات است به گونه ای که وقت پردازشگر اصلی صرف کارهای مهم تر شود
(1-16)
پیاده سازی مرتب ساز داده های ورودی از بزرگ به کوچک (یا بالعکس) ، علیرغم سادگی از نقطه نظر صورت مسئله، به صورت کارا و به گونه ای که با ساختار پردازشگرهای کنونی منطبق باشد بسیار پیچیده است. در نتیجه از همان ابتدا نیاز به تحقیق و پژوهش به منظور یافتن الگوریتم های سریع تر و کاراتر احساس می شد و تبدیل به یکی از مسائل مهم در پردازش اطلاعات دیجیتال شد .(5.8.9.16)
الگوریتم مرتب سازی به شیوه حبابی (Bubble Sort) اولین شیوه معرفی شده برای حل این مسئله، در سال 1956 بود(1-3) این شیوه گرچه از لحاظ تئوری ساده به نظر می رسد، اما پیاده سازی آن به شیوه سخت افزاری نیازمند صرف زمان، سطح اشغالی و توان مصرفی زیادی از پردازشگر است. علی رغم اینکه مسئله مرتب سازی از نقطه نظر نرم افزاری تقریبا حل شده است اما کماکان پژوهش به منظور بدست آوردن الگوریتم های کاراتر از نقطه نظر پیاده سازی سخت افزاری ادامه دارد. به عنوان مثال مرتب سازی به شیوه کتابخانهای با این رویکرد در سال 2004 مطرح شده است(1-6؛2-7 و 9)
مرتب کننده های داده Sorter) ها) یکی از اجزاء مهم و رایج در پردازشگرهای اطلاعات می باشند. به عنوان مثال مرتب سازی به شیوه ای کارا در بهینه سازی الگوریتم هایی که به لیست مرتب شده نیاز دارند (مثلا روش های جستجو و ترکیب) اهمیت دارد-6-
الگوریتم جدیدی که در این مقاله برای اولین بار پیشنهاد شده است مرتب سازی اطلاعات ورودی با استفاده از یک حافظه با دسترسی تصادفی (RAM) است. این شیوه همانگونه که در ادامه توضیح داده خواهد شد، بسیار ساده و انعطاف پذیر بوده و بر خلاف الگوریتم های گذشته نیازی به پردازش پیچیده بر روی اطلاعات با استفاده از مقایسه کننده ندارد. این الگوریتم همچنین از نقطه نظر پیاده سازی به خصوص بر روی FPGA حائز اهمیت است(11-6 ،10)چرا که در آن نیاز کمی به استفاده از المان های پردازشی وجود دارد. در نتیجه می توان از این المان ها به منظور پیاده سازی بلوک های پردازشی دیگر در کنار یک مرتب کننده استفاده نمود. در بخش های بعد، مرتب سازی اطلاعات با این روش، با جزئیات بیشتری آورده شده است.
2- الگوریتم مرتب سازی اطلاعات با استفاده از ram
در مرتب سازی اطلاعات بوسیله RAM، خط داده ورودی مرتب کننده، به خط آدرس ورودی RAM وصل می شود. در نتیجه در ساده ترین حالت ممکن بجای ذخیره سازی مستقیم داده ورودی، در خانه حافظه منطبق با آن ورودی، عدد یک قرار می گیرد. پس در این حالت که با فرض عدم وجود تکرار می باشد، برای مرتب کردن داده هایی به طول n بیت، به 2n خانه حافظه نیاز است. پس از اتمام مرحله خواندن داده های ورودی، با استفاده از یک شمارنده که به پورت آدرس وصل می شود، حافظه از بالا به پایین خوانده شده و آدرسهایی که مقدار متناظر در آنها یک باشد (خروجی شمارنده) در پورت خروجی داده قرار داده می شوند. پس در نهایت داده های ورودی مرتب می شوند. با توجه به این بحث، می توان فهمید که در این الگوریتم فقط به حافظه و شمارنده (آدرس) نیاز است.
اما روش بالا، در شرایطی صحیح است که در داده های ورودی، جزء تکراری وجود نداشته و نیاز به خروج اطلاعات با فرکانس کلاک ورودی نباشد. اگر این دو شرط نیز در مساله لحاظ شوند، علاوه بر بلوک های ذکر شده به یک شمارنده اضافی (به منظور شمارش تعداد داده های تکراری)
یک ثبات ذخیره ساز به اندازه کل داده های ورودی (به منظور قرار دادن داده های مرتب شده با فرکانس کلاک در پورت خروجی ) نیز نیاز داریم که در مورد آنها در قسمت بعد بحث می شد. علاوه بر این در حالت کلی، هر خانه مربوط به یک آدرس حافظه RAM بجای یک بیت باید برابر m بیت باشد که عدد m با حداکثر تکرار (برابر با تعداد داده های ورودی) متناسب می باشد. به عبارت دیگر عدد m باید بگونه ای باید انتخاب شود که نامساوی زیر برقرار شود:
(1) تعداد داده های ورودی 2m
در این شرایط مقدار موجود در هر آدرس حافظه متناظر با تعداد تکرار آن آدرس به عنوان داده ورودی می باشد. همچنین باید در هنگام خواندن حافظه از بالا به پایین هر آدرسی از حافظه، به تعدادی که عدد موجود در آن آدرس نشان می دهد، در ثبات خروجی نوشته شود.
در نهایت با هر کلاک یکی از داده های مرتب شده در ثبات، در پورت خروجی قرار می گیرند. به عنوان مثال شکل 1 ایده اصلی این الگوریتم را برای مرتب نمودن شش داده ورودی سه بیتی به تصویر می کشد. همانطور که نشان داده شد در این الگوریتم بدون انجام مقایسه عمل مرتب سازی صورت گرفته است. بنابراین روش پیشنهادی، در مقایسه با الگوریتم های پیشین که از طریق مقایسه های متعدد، طبق الگوریتم های مختلف عمل مرتب سازی را انجام می دادند، از قابلیت اطمینان بالاتری برخوردار است.
-3 پیاده سازی الگوریتم مورد نظر بر روی FPGA
شکل 2 بلوک دیاگرام ساختاری الگوریتم مورد نظر را نشان می دهد. عملکرد این سیستم به این صورت است که در هنگام ورود داده، واحد کنترل، مالتی پلکسرهای ورودی و خروجی را طوری انتخاب می کند که درگاه ورودی داده به ورودی آدرس RAM وصل شده و خروجی RAM نیز به ورودی جمع کننده متصل گردد. در این زمان محتوی هر خانه حافظه که بوسیله داده های ورودی آدرس داده می شود، یک واحد زیاد شده و در جای خود نوشته می شود. پس از اتمام ورود داده ها محتوی هر خانه نشانگر تعداد تکرار آن آدرس به عنوان داده ورودی می باشد. عمل جمع بصورت ترکیبی انجام می شود . بنابراین هر خواندن و نوشتن در دو کلاک انجام می شود و برای ورود n داده، به 2n کلاک نیاز است. پس از اتمام مرحله نوشتن، وضعیت مالتی پلکسرها برعکس حالت قبل می شود یعنی ورودی آدرس RAM به شمارنده آدرس و خروجی داده RAM به شمارنده تکرار وصل می شوند. در این مرحله شمارنده های آدرس و تکرار وارد عمل می شوند. شمارنده آدرس، حافظه را از بالاترین آدرس تا پایین ترین می خواند، در هر خانه مشخص که مقدار موجود در آن غیر صفر باشد، این شمارنده، مقدار را به شمارنده تکرار می دهد و خودش در مقدار مذکور متوقف می شود این شمارنده که بصورت معکوس می شمارد، به همان تعداد آدرس متناظر مربوطه را در ثبات خروجی قرار می دهد. در آخرین دفعه قرار دادن آدرس در ثبات خروجی، شمارنده آدرس به صورت همزمان فعال می شود و از همان مقدار قبلی بصورت نزولی می شمارد تا دو باره به خانه ای با محتوی غیر صفر برسد. یک شدن بیت سر ریز شمارنده آدرس، اتمام این عملیات را به واحد کنترل اعلام می کند و پس از آن داده های مرتب شده با فرکانس کلاک در پورت خروجی قرار می گیرند. برای مرتب کردن n داده ی m بیتی، بدون نیاز به انجام عمل مقایسه، تعداد کلاک مورد نیاز برابر است با:
(2) (مجموع کل تکرارها)= 2n+2m+ تعداد کلاک
برای مرتب کننده ای که اعداد 16 بیتی را مرتب می کنـد به 216خانه حافظه نیاز است. از آنجا که ساختار این پژوهش برای مرتب سازی 256 داده ورودی طراحی شده اسـت، لـذا حداکثر تکرار ممکن برابر با 256 می باشد. در نتیجه حافظه RAM برای اینکه توانایی ذخیره این تعداد تکرار را در هـر خانه داشته باشد، باید طول هر خانه اش هشـت بیـت باشـد .(28=256) حافظه های RAM تعبیـه شـده در FPGA به صورت بلوکهای 16Kbit مـی باشـد کـه بـه روش هـای مختلفی پیکره بندی مـی شـوند-13-.
در ایـن پـروژه، ایـن بلوک ها به صورت 2Kbyte پیکره بندی گردیدند:
16Kbit=2. 210. 23=2Kbyte (3)
از طرف دیگر همـانطور کـه نشـان داده شـد بـه 216 یـا 64Kbyte خانه حافظه نیـاز بـود کـه بـرای ایجـاد چنـین بلوکی از حافظه RAM باید 32 بلوک 2Kbyte را بـا هـم ترکیب نمود. بنابراین از تراشـه نـوع Xilinx Spartan3 XC3S1500 استفاده گردید (13)از پـنج بیـت بـا ارزش خط آدرس بصورت یک شناسه طوری استفاده شد که در هر لحظه فقط یکی از بلوک ها فعال باشند.
