بخشی از مقاله
چکیده
واحد حافظه در هر کامپیوتر دیجیتال یکی از بخشهای اصلی آن است. واحد حافظهای که دستیابی به آن بر اساس محتوا انجام میشود حافظهی تداعیگر یا حافظه ی قابل آدرسدهی با محتوا - - CAM خوانده میشود. تحقیقات درزمینه ی حافظههای تداعیگر دارای یکسری، مشکلات کلیدی هست که از آن جمله میتوان مصرف توان بالا در خطوط جستجوی داده و خطوط تطبیق، سربار مساحت و قابل پیادهسازی بودن در آرایههای قابلبرنامهریزی - - FPGA نام برد.
در این مقاله یک طراحی جدید حافظهی CAM، مبتنی بر بلوکهای RAM قطعه ای که بهطور بهینه بر روی آرایههای قابلبرنامهریزی، قابل پیاده سازی هست وکارآیی جستجو - توان، سرعت و - latency را بالا میبرد ارائه خواهد شد.
کاربرد این طرح در مسیریابهای شبکه که هدفشان پیدا کردن hop بعدی بر اساس آدرس ورودی هست و برای بهروز کردن جداول مسیریابی از FPGA ها استفاده میکنند خواهد بود. ساختار ارائهشده توسط نرمافزار Xilinx ISE شبیهسازیشده و درنهایت این ساختار با ساختارهای پیشین ازلحاظ کارآیی مقایسه شده است. نتایج بهدستآمده بهبود کارآیی در ساختار ارائهشده را در مقایسه با ساختارهای پیشین نشان میدهد.
-1 مقدمه
در هر کامپیوتر دیجیتال واحد حافظه یکی از قسمتهای اصلی هست. بسیاری از کاربردهای دادهپردازی به جستجوی اقلامی که در یک جدول حافظه ذخیرهشدهاند نیاز دارد. روش متداول در جستجوی جدول، ذخیره ی اقلام آن در مکانی است که بتواند بهصورت متوالی آدرسدهی شود. اگر بتوان دادهی ذخیرهشده در حافظه را بهمنظور دستیابی به آنها بر اساس محتوای خود داده و نه بر اساس یک آدرس شناسایی کرد زمان لازم برای یافتن یک داده تا حد قابلتوجهی کاهش مییابد.
واحد حافظهای که دستیابی به آن بر اساس محتوا انجام می شود حافظهی تداعیگر2 یا حافظه قابل آدرسدهی با محتوا3، خوانده می شود. دستیابی به این حافظهها بهطور همزمان و موازی و بر اساس محتوای داده بهجای آدرس یا مکان خاصی انجام میشود.
دو نوع حافظهی تداعیگر وجود دارد: حافظه ی تداعیگر باینری4 و حافظهی تداعیگر سهگانه .5 حافظههای تداعیگر باینری فقط دو بیت 0 و1 را حمایت میکنند. دادهها در حافظههای تداعیگر سهگانه میتوانند شامل 3 حالت 0 و 1 و بیتفاوت6 باشند. این حافظهها در دو نوع NAND و NOR موجود میباشند. حافظههای تداعیگر باینری و حافظههای تداعیگر سهگانه در بسیاری از کاربردها مانند جدولهای مسیریابهای شبکه و کاربردهایی که جستجو با سرعتبالا مهم هست استفاده میشوند. همانطور که در شکل - 1 - نشان دادهشده است؛ حافظه ی تداعیگر سهگانهی مرسوم از 3 قطعهی اصلی قطعهی حافظه ی تداعیگر از نوع XOR، سلول نقاب7 و مدار کنترلکننده ساخته شده است
شکل - : - 1 حافظهی تداعیگر سهگانه ی مرسوم
در حافظهی تداعیگر سهگانهی مرسوم ابتدا خطوط جستجو دشارژ و خطوط تطبیق8 تا VDD شارژ میشوند - فاز پیش شارژ - 9 و سپس دادهی ورودی روی خطوط جستجو قرار میگیرد، در قطعهی اول دادهی ورودی با دادهی ذخیرهشده توسط گیت XOR مقایسه میشود . بهطور همزمان بیت نقاب10 از سلول نقاب خارج میشود و این دو خروجی به ترانزیستورهای مدار کنترلکننده وارد میشوند. ترانزیستورهای مدار کنترلکننده که به خط تطبیق متصل هستند مشخص میکنند که خط تطبیق باید شارژ بماند یا دشارژ شود. منطق خط تطبیق، با در نظر گرفتن نوع حافظهی تداعیگر سهگانه، مشخص میکند که تطبیق اتفاق افتاده است یا نه .
جدول - 1 - حالتهای متناظر با عملکرد حافظه ی تداعیگر سهگانهی مرسوم را نشان میدهد . حالت حافظهی تداعیگر سهگانه، بابیت نقاب و دادهی ذخیرهشده تعیین میشود. بیت نقاب، M=1، مشخص میکند که سلول حافظهی تداعیگر سهگانه در حالت بیتفاوت هست و به معنای این است که صرفنظر از مقایسهی نتایج سلول حافظه ی تداعیگر باینری یک تطبیق ایجاد میشود. در مقایسه اگر بیت نقاب صفر باشد سلول حافظهی تداعیگر سهگانه وابسته به دادهی ورودی یکی از دو حالت "0"یا "1"را دارد. در حالت M=0 اگر دادهی جستجو مساوی با دادهی ذخیرهشده باشد تطبیق نرمال نام دارد و قابلتشخیص از تطبیق همهجانبه11 هست.
جدول : - 1 - حالتهای متناظر با عملکرد حافظهی تداعی گر سهگانهی مرسوم
تطبیق نرمال:Normal match عدم تطابق:Mismatch
تطبیق همه جانبه:Wild match
در این نوع حافظهها توان مصرفی، کارایی جستجو و سرعت جستجو پارامترهای مهمی هستند که باید بهینه شوند. باوجوداینکه، حافظههای تداعیگر سهگانه سریعترین ابزار برای جستجوی مسیر هستند ولی دارای مصرف تواننسبتاً زیادی می باشند. در حافظههای تداعیگر باینری و تداعیگر سهگانه، سه مصرفکنندهی عمدهی توان خطوط جستجوی داده، خطوط تطبیق، کنترل و کلاک وجود دارند.
با مینیمم کردن سوئیچهای غیرضروری خطوط جستجو میتوان، توان مصرفی خطوط جستجو را کاهش داد .[2]
مسیریابها از حافظههای تداعیگر سهگانه برای ذخیرهسازی آدرسها و جستجوی آدرس در جدولهای مسیریابی استفاده میکنند. در این جدولها دادهها بر اساس خصوصیت حالت بیتفاوت ممتد عمودی12 ذخیره می شوند؛ درواقع آدرسها به ترتیب کاهشی از طول پیشوندها ذخیره میشوند؛ یعنی مطابق با شکل - 2 - آدرسهایی که حالت بیتفاوت کمتری دارند در خانههای بالایی و آدرسهایی که حالت بیتفاوت بیشتری دارند
در خانه های پایینتر جدول قرار میگیرند؛ بنابراین باید طولانیترین پیشوند متناظر با آدرس ورودی پیدا شوند که به این خصوصیت، خاصیت طولانیترین پیشوند تطبیق13 گفته می شود.
شکل : - 2 - خصوصیت طولانیترین پیشوند تطبیق
ازاینرو روشهای بسیاری برای جستجوی داده در حافظههای تداعیگر سهگانه به طوریکه کارایی جستجو بالا باشد و بهترین تطبیق با دادهی ورودی پیدا شود و خصوصیت طولانیترین پیشوند تطبیق حفظ شود ارائهشدهاند. روشهای DCG یک سطحی[2] و دوسطحی[1] به همراه تکنیکهایSE و [4] RSE توان خط جستجو و[12] CRSLDو [6,7]با شکستن خطوط تطبیق توان خطوط تطبیق را کاهش میدهند. طراحیهای سلسله مراتبی نیز برای شکستن خطوط جستجو پیشنهادشدهاند
از طرف دیگر اگر بخواهیم حافظههای تداعیگر مرسوم را روی آرایههای قابلبرنامهریزی14 پیادهسازی کنیم و جستجوی دادهی ورودی را انجام دهیم، به ازای ذخیرهسازی و جستجوی هر بیت، تعداد زیادی از حافظههای توزیعشده روی آرایههای قابلبرنامهریزی، نیاز خواهد بود که باعث میشود؛ هزینهی مصرف حافظهی توزیعشده و توان، افزایش و سرعت جستجو کاهش یابد؛ بنابراین استفاده از این حافظههای توزیعشده با توجه به محدودیت مصرف حافظه و محدودیتهای توان باید حداقل شود.
یک روش مؤثر برای پیاده سازی کردن حافظهی تداعیگر روی آرایههای قابلبرنامهریزی، روش[8]HPSBT15 هست و باعث میشود حافظهی توزیعشدهی کمتری استفاده شود. ازاینرو طراحی حافظهی تداعیگری که بر اساس بلوکهای حافظه با دسترسی تصادفی 16 کار میکند در هرلحظه از زمان بهجای دسترسی به یک بیت، به یک ردیف حافظه دسترسی دارد و قابل پیادهسازی در آرایههای قابلبرنامهریزی هست و همچنین کارایی آن بهینه باشد، مسئلهای چالشبرانگیز است.
در این مقاله سعی شده است در قسمت 2، ابتدا مختصری از کارهای گذشته بیان شود و ازلحاظ پارامترهایی نظیر توان مصرفی، کارایی، حافظهی مصرفی و قابل پیاده سازی بودن در آرایه های قابل برنامه ریزی باهم مقایسه شوند و حافظهی پیشنهادشده بررسی شود و درنهایت در قسمت 3 نتیجهگیری حاصل از بررسی این حافظهها بیان خواهد شد.
-2 طراحی حافظهی تداعیگر نوین
-1-2 معماری حافظهی - HPSBTحافظهی تداعیگر سهگانه مبتنی بر SRAM قسمتبندی شده -
آرایه های قابل برنامه ریزی دارای یک سری از حافظه های توزیعشده و یک حافظهی متمرکز هست. اگر بخواهیم حافظهی تداعیگر سهگانهی مرسوم را روی آرایه های قابل برنامه ریزی پیاده سازی کنیم به ازای ذخیرهسازی هر بیت نیاز به یک حافظهی توزیع شده داریم که باعث میشود حافظهی زیادی مصرف شود. ازاین رو پیاده سازی حافظه های تداعیگر سه گانهی مرسوم روی آرایه های قابل برنامه ریزی مسئله ای چالش برانگیز است.
HPSBT17 یک معماری جدید حافظهی تداعیگر سهگانهی مبتنی بر SRAM قسمتبندی شده هست. در این روش جدول حافظهی تداعیگر سه گانه مرسوم به صورت پیوندی به زیر جدول های کوچک تر حافظهی تداعیگر سه گانه تقسیم میشود. درواقع بیتهای موجود در حافظهی تداعیگر سهگانه با تقسیمبندی ردیفی و ستونی به قسمتهای کوچکتری که هرکدام زیر جدول نامیده میشود تقسیم میشود
