بخشی از مقاله
طراحی مدار جمع کننده/ تفریق کننده برگشت پذیر با قابلیت،تحمل پذیری خطا
چکیده :
با پیشرفت تکنولوژی ابعاد مدارها بسیار کوچک می شدند و یکی از عواملی که در این زمان خیلی مهم می شود اتلاف انرژی است. تمامی مدارهای معمولی که با آنها سروکار داریم برگشت ناپذیر هستند به طوری که هنگامی که ورود به خروجی تبدیل شد ورودی از بین می رود و با حذف اطلاعات امکان برگشت آنها وجود ندارد. محاسبات برگشت پذیر زمانی شروع شد که پردازش های اصلی اطلاعات ترمودینامیک نشان داد که مدارهای غیر قابل برگشت پذیر معمول به میزان زیادی گرما، به دلیل از دست رفتن اطلاعات در طول محاسبات، از دست می دهند. در مدارات منطقی برگشت پذیر، تعداد خط های ورودی باید با تعداد خط های خروجی برابر باشد و هر خروجی فقط برای یک بار می تواند استفاده شود. یکی از نکات مهم طراحی مدارات برگشت پذیر، اتلاف انرژی کمتر و محاسبات کوانتومی سریع تر است. بسیاری از گیت هایی که در طراحی دیجیتال استفاده می شوند مانند NAND , EXOR, OR غیر قابل برگشت هستند. یک گیت یا مدار برگشت پذیر می توانند بردار خروجی را از هر بردار ورودی منحصر به فردش تولید کند و بالعکس این قضیه هم صادق است. یعنی می تواند از روی بردار ورودی ، بردار خروجی منحصر به فردش را تولید کند.طراحی منطق برگشت پذیر یکی از جهت های تحقیقات امیدوار کننده و نوید بخش در طراحی مدارات اتلاف کم توان در چند سال گذشته بوده است و کاربردش در طراحی CMOS توان پایین، پردازش سیگنال دیجیتال و فناوری نانو پیدا کرده است بر این اساس در مطالعه صورت پذیرفته طراحی مدارجمع کننده/تفریق کننده برگشت پذیربا قابلیت تحمل خطا و مقایسه آن با سایر مدارات ارائه می گردد .
کلمات کلیدی : مدارات برگشت پذیر ، جمع کننده ،تفریق کننده ، تحمل پذیری خطا
-1 مقدمه
تحول بزرگ در محاسبات ماشینی در ابتدای قرن بیستم شروع شد. این زمانی است که الگوریتم و مفهوم فرآیندهای الگوریتمی به سرعت در ریاضیات و بتدریج در سایر علوم رشد کرد. ریاضیدانان شروع به معرفی سیستم های جدیدی برای پیاده سازی الگوریتمی کلی کردند که در نتیجه آن ، سیستم های انتزاعی محاسباتی بوجود آمدند. در این میان سهم برخی بیشتر از سایرین بود. آنچه امروزه آن را دانش کامپیوتر و یا الکترونیک دیجیتال می نامیم مرهون و مدیون کار ریاضیدانان برجسته انگلیسی به نام آلن تورینگ است. وی مدلی ریاضی را ابداع کرد که آن را ماشین تورینگ می نامیم و اساس تکنولوژی دیجیتال در تمام سطوح آن است. وی با پیشنهاد استفاده از سیستم دودویی برای محاسبات به جای سیستم عددنویسی دهدهی که تا آن زمان در ماشینهای مکانیکی مرسوم بود، انقلابی عظیم را در این زمینه بوجود آورد. درسال 1965 ، گوردون مور اظهار کرد که توان کامپوترها هر دو سال دو برابر خواهد شد. در تمام این سال ها، تلاش عمده در جهت افزایش قدرت و سرعت عملیاتی در کنار کوچک سازی زیر ساخت ها و اجزای بنیادی بوده است. نظریه مور در دهه های 60 و 70میلادی تقریباً درست بود. اما از ابتدای دهه 80 میلادی و با سرعت گرفتن این پیشرفت ها، شبهات و پرسش هایی در محافل علمی مطرح شد که این کوچک سازی ها تا کجا می توانند ادامه پیدا کند؟ کوچک کردن ترانزیستورها و مجتمع کردن آنها در فضای کمتری نمی تواند تا ابد ادامه باشد زیرا در حدود ابعاد نانومتری اثرات کوانتومی از قبیل تونل زنی الکترونی بروز می کنند.گرچه همیشه تکنولوژی چندین گام بزرگ از نظریه عقب است، بسیاری از دانشمندان در زمینه های مختلف به فکر رفع این مشکل تا زمان رشد فن آوری به حد مورد نظر افتادند. به این ترتیب بود که برای نخستین بار در سال 1982، محاسبات از دنیای دیجیتال وارد دنیای جدیدی به نام کوانتوم گردید. اتلاف انرژی یکی از فاکتورهای مهم در طراحی مدارات VLSI است . محاسبات برگشت پذیر زمانی شروع شد که پردازش های اصلی اطلاعات ترمودینامیک نشان داد که مدارهای غیر قابل برگشت پذیر معمول به میزان زیادی
گرما، به دلیل از دست رفتن اطلاعات در طول محاسبات، از دست می دهند. اصل لاندور نشان می دهد که محاسبات برگشت ناپذیر به ازای هر بیت اطلاعاتی که از دست می دهد، مقدار گرمایی برابر 2 log KT تولید می کند، این به این خاطر است که طبق قانون دوم ترمودینامیک ، اطلاعاتی که از دست داده می شوند با هیچ روشی قابل ارزیابی نیستند(.(Islam and Begum,2008اطلاعات زمانی از دست می روند که بردارهای ورودی نتوانند با بردارهای خروجی معادل تحت پوشش قرار بگیرند. به دلیل اینکه در مدارهای برگشت پذیر بردارهای ورودی می توانند توسط بردارهای خروجی منحصر بفرد خود تحت پوشش قرار گیرند، منطق برگشت پذیر بطور طبیعی از این اتلاف انرژی جلوگیری می کند.بنت نشان داد که چنانچه شبکه ها شامل گیت های برگشت پذیر باشد اتلاف انرژی صفر خواهد بود . (Rangaraju et all.,2010 ) بنابراین برگشت پذیری به روندهایی که در آینده به سمت طراحی اتلاف انرژی کمتر برود، تبدیل خواهد شد. طبق قانون مور تعداد TR های روی سطح هر 18 ماه، دو برابر میش ود. بنابراین این دستگاه های محافظ انرزی مورد نیاز روز است.طراحی مدارات برگشت پذیر به طور قابل توجهی با طراحی مدارات غیر قابل برگشت پذیر یا منطقی ترکیبی معمول متفاوت است. در مدارات منطقی برگشت پذیر، تعداد خط های ورودی باید با تعداد خط های خروجی برابر باشد و هر خروجی فقط برای یک بار می تواند استفاده شود. یکی از دغدغه های طراحی بسیار جالب، اتلاف انرژی کمتر و محاسبات کوانتومی سریع تر است. یک گیت یا مدار برگشت پذیر می توانند بردار خروجی را از هر بردار ورودی منحصر به فردش تولید کند و بالعکس این قضیه هم صادق است. یعنی می تواند از روی بردار ورودی ، بردار خروجی منحصر به فردش را تولید کند. بنابراین یک تناظر یک به یک بین بردارهای ورودی و خروجی وجود دارد ( .(Nayeem et all.,2009 به همین خاطر تعداد بردارهای خروجی در گیت یا مدار برگشت پذیر با تعداد بردارهای وردی اش برابر است و گیت معکوس کننده، تنها گیت برگشت پذیر است. گیت های منطقی برگشت پذیر فقط با توابع برگشت پذیر تحقق پیدا می کنند، ولی بسیاری از توابع بولین برگشت پذیر نیستند. قبل از تحقق این توابع، ما باید توابع را از غیر قابل برگشت پذیر بودن به برگشت پذیر تبدیل کنیم. هر الگوریتم انتقالی که تابع برگشت ناپذیر را به برگشت پذیر تبدیل کند یک خط ورودی را در سمت ورودی مدار معرفی می کند که باید مقدار صفر و یا یک داشته باشد. این ورودی ها، ورودی های ثابت نام دارند. پس هر طراحی بهینه باید طوری باشد که خروجی های زائد به همراه این ورودی های ثابت را کاهش دهد.طراحی منطق برگشت پذیر یکی از جهت های تحقیقات امیدوار کننده و نوید بخش در طراحی مدارات اتلاف کم توان در چند سال گذشته بوده است و کاربردش در طراحی CMOS توان پایین، پردازش سیگنال دیجیتال و فناوری نانو پیدا کرده است(. (Bennett,2003
-2 مدار برگشت پذیر
تراشه های با عملکرد بالا مقدار زیادی گرما آزاد می کنند که باعث می شود محدودیت های علمی در مورد اینکه ما تا کجا می توانیم عملکرد سیستم را بهبود دهیم ایجاد شود. مدارهای برگشت پذیر اطلاعات را از طریق غیر قابل محاسبه شدن بیت ها به جای دور انداختن آن ها، حفظ می کند، محاسبات برگشت پذیر همچنین به بهبود در مصرف انرژی منجر می شود. مصرف انرژی اساساً روی سرعت مدارها مثل مدارات نانویی و همچنین سرعت برنامه های کاربردی در حد نانو تاثیر می گذارد. برای افزایش قابلیت حامل دستگاه ها باز هم محاسبات برگشت پذیر مورد نیاز است. مدار برگشت پذیر اجازه می دهد که سایز های اجزای مدار، در حد سایز اتمی کوچک شود. از این رو دستگاه بیشتر قابل حمل می شود. اگرچه هزینه های طراحی سخت افزار متحمل شده در آینده نزدیک ممکن است بالا باشد، اما در این دوران محاسبات، هزینه توان و کارآیی بیشتر غالب خواهد شد. پس نیاز به محاسبات برگشت پذیر را نمی توان حذف کرد و نادید گرفت . (Yelekar and Chiwande,2011 )
1-2محدودیت های مهم در طراحی مدارهای منطقی برگشت پذیر
محدودیت های که در طراحی مدارهای منطقی برگشت پذیربه آنها دقت می شود عبارتند از :
▪ گیت های منطقی برگشت پذیر اجازه Fan-out ندارند.
▪ مدارهای منطقی برگشت پذیر باید حداقل ارزش کوانتومی را داشته باشند.
▪ طراحی که بهینه است، حداقل تعداد خروجی های زائد را تولید می کند یا از این تعداد پارمتر کمتر استفاده کند.
▪ مدارهای منطقی برگشت پذیر باید حداقل سطوح گیت و یا حداقل عمق منطق را استفاده کند.
▪ مدارهای منطقی برگشت پذیر باید حداقل سطوح گیت و یا حداقل عمق منطق را استفاده کند( . (Nayeem et all.,2009
2-2 مدارهای برگشت پذیر متحمل خطا
مدار متحمل خطا ، امکان تشخیص خطا را در خروجی اصلی اش دارا می باشد. یک مدار برگشت پذیر قادر به حفظ توازن است اگـر گیـت هـایش بـه خـودی خود قادر به حفظ توازن باشند. این محدودیت برای مدارهای برگشت پذیر محافظه کار نیز اعمال می شود. در مـدارهای برگشـت پـذیر حفـظ تـوازن، تمـامی خطاها ی تک بیتی در خروجی اصلی شناسایی و تشخیص داده می شود. در حالی که مدارهای محافظه کار عـلاوه بـر خطاهـای تـک بیتـی امکـان تشـخیص خطاهای چند بیتی را نیز دارند.
3-2 جایگزینی
یکی از احتیاجات لازم و مفید برای مدار برگشت پذیر حفظ توازن این است که هر گیت آن مدار باید دارای خاصیت حفـظ تـوازن باشـند. بنـابراین مـا دو راه برای پیاده سازی مدارهای برگشت پذیر حفظ توازن داریم. قبلا از طراحی های حفظ توازن ساده به صورت استفاده از گیت های برگشـت پـذیر حفـظ تـوازن استفاده می کردند. بعدها با استفاده از طرح های موجود با جایگزینی حفظ توازن، تمامی گیت های شناخته شده که دارای حفظ توزان نیسـتند نیـز اسـتفاده شدند. در این قسمت روش دوم برای گسترش مدارهای برگشت پذیر حفظ توازن که دارای تبدیل هزینه کم است استفاده شده است. مزیـت دیگـر ایـن روش این است که ابتدا اجازه می دهد که تمامی روش های مستند توسعه یافته برای تولید مدارهای برگشت پذیر بدون خاصیت تحمـل پـذیری خطـا بکـار گرفتـه شوند. بعد از آن می توان تحمل پذیری را نیز به آن اضافه و تلفیق کرد. این دو مرحله پردازش به راحتی می توانند طراحی شوند بدون اینکـه روی هـم تـاثیر
داشته باشند(.(Yelekar and Chiwande,2011
4-2جایگزین مدارهای برگشت پذیر
پروسه جایگزینی تمامی گیت های برگشت پذیر که دارای حفظ توازن نیستند را با جایگزین حفظ توزان خود ، جایگزین شـد. بـرای هـر تعـویض کـه شـامل ورودی ثابت محدود شده است، ما به یک خط اضافی نیاز داریم، در غیر این صورت همین خطوط کافی هستند. فراینـد تعـویض اسـتفاده شـده بـرای انتقـال مدارهای برگشت پذیر به مدارهای برگشت پذیر حفظ توازن در فلوچارت در شکل((1 نشان داده شده است.
شکل -1 فلوچارت قاعده حفظ توزان
5-2 تحمل پذیری مدارهای برگشت پذیر
خطا یک اشتباهی است که در سیستم رخ می دهد و باعث می شود سیستم از عملکرد اصلی خود منحرف شود. مدل های خطا پیچیدگی تست را با کاهش خطاهایی که باید در نظر گرفته شود، ساده می کند. برای تشخیص کارآمد خطا مدل های خطا برای منطق برگشت پذیر در مقالات ارائه شده است. به طور معمول مدل های خطا می توانند به مدل های خطای تکی و مدل های خطاهای چندتایی با توجه به تعداد خطاهای اتفاق افتاده در سیستم دسته بندی شوند.تحمل پذیری خطا یک ویژگی است که یک سیستم را قادر می سازد به عملکرد صحیح خود ادامه دهد در حالی که بعضی از اجزای آن سیستم دچار شکست و نقص شده اند . تحمل پذیری خطا نشان دهنده نیرومندی و استحکام یک سیستم است. سیستم های تحمل پذیری خطا قادر به تشخیص و تصحیح خطاها هستند. در منطق دیجیتال و سیستم هی ارتباطی، تشخیص خطا با حفظ توازن به دست می آید. این ویژگی می تواند برای مدارهای برگشت پذیر مفید باشد چون آنها مثل سیستم های ارتباطی دیجیتال تعداد ورودی ها و خروجی های یکسانی دارند.برای رسیدن به تحمل پذیری خطا، مرحله اول ، شناسایی وقوع خطاست. برای تشخیص وقوع، تکنیک های حفظ توازن در مقالات ارائه شده است. همه خطایی که روی بیشتر از یک بیت تاثیر نگذارد به راحتی در خروجی های اصلی مدارها در مدارهای برگشت پذیر حفظ توازن ما می توانیم تحمل پذیری خطا را در محاسبات برگشت پذیر داخل کنیم.منطق
محافظه کار نیز جایگزینی برای دستیابی به تحمل پذیری خطا در محاسبات برگشت پذیر است اما این روش هزینه بالا و مدارهای پیچیده ای را ارائه می کند.
-3 طراحی تمام و نیم جمع کننده / تفریق کننده
سه طراحی متفاوت از مدار نیم جمع کننده/ تفریق کننده و تمام جمع کننده /تفریق کننده ارئه و مقایسه شده است.
1-3 طراحی اول
در این طراحی ابتدا یک مدار نیم جمع کننده / تفریق کننده که دارای چهار گیت ، هزینه کوانتومی 12 ، سه عدد خروجی زائـد و دو عـدد ورودی ثابـت مـی باشد، معرفی شده است. سپس یک مدار تمام جمع کننده/ تفریق کننده ارائه شده که شامل هشت گیت است. این مدار تمـام جمـع کننـده سـه عـدد ورودی ثابت، پنج عدد خروجی زائد و هزینه کوانتومی 21 دارد.
1-1-3 نیم جمع کننده و نیم تفریق کننده
این مدار نیم جمع کننده و نیم تفریق کننده با چهار گیت برگشت پذیر پیاده سازی شده است، که شامل دو عدد گیت فـردکین و دو عـدد گیـت فـیمن مـی باشدشکل(.(2 دارای سه خروجی زائد g2 , g1 و g3 و دو عدد ورودی ثابت می باشد که این ورودی های ثابت ارزش منطقی دارند. هزینه کوانتومی ایـن مـدار 12 است . این هزینه به این خاطر است که مدار دارای دو عدد گیت فیمن است که هر کدام از گیت های فیمن هزینه کوانتومی یک دارنـد و همچنـین دارای دو عدد گیت فردکین که هر گیت فردکین دارای هزینه کوانتومی پنج می باشد(.(Rangaraju et all.,2010
شکل -2 مدار نیم جمع کننده/نیم تفریق کننده برگشت پذیر طراحی اول 2-1-3 تمام جمع کننده/تمام تفریق کننده
مدار تمام جمع کننده برگشت پذیر، با 5 عدد گیت fg، دو عدد گیت f و یک عدد گیت TR تشکیل شده اسـت کـه در شـکل((3نشـان داده شـده اسـت. سـه ورودی های این مدار B , A و Cin هستند و خروجی های ایـن مـدار نیـز S/D جمـع/ تفریـق و C/B بیـت هـای حامـل/1 قرضـی2 مـی باشـند.ورودی کنتـرل عملکردهای جمع و تفریق را از هم متمایز می کند. چنانچه مقدار کنترل صفر باشد. مدار عمل جمع را انجام می دهد و عمـل تفریـق بـرای زمـانی اسـت کـه مقدار کنترل یک شود. تعداد ورودی های ثابت سه عدد است که دارای مقدار صفر منطقی می باشد. خروجی های زائد 5 عدد است که با g1 تا g5 نشـان داده شده است. تابع جمع و تفریق از گیت FG4 تحقق می یابد و حاصل /قرضی از خروجی گیت TR تحقق می یابد. هزینه کوانتومی پنج عدد گیت FG، پـنج مـی شود، این بدین خاطر است که هر کدام از گیت FG دارای هزینه کوانتومی یک است و برای دو عدد گیت F، 10 می شود چـون هـر یـک هزینـه پـنج دارنـد. هزینه یک عدد گیت شش TR ، می باشد. بنابراین هزینه کوانتومی کل طراحی 21 است(.(Rangaraju et all.,2010
شکل -3 مدار تمام جمع کننده/ تمام تفریق کننده برگشت پذیر طراحی اول
1 carry
