مقاله طراحی و بهبود مدار ضرب کننده بوفولی علامت دار برگشت پذیر

بخشی از مقاله

چکیده -

اگر در طراحی مدارها از گیتهای برگشتپذیر استفاده شود، توان مصرفی داخلی کامپیوتر به صفر خواهد رسید. با انجام محاسبات به روش برگشتپذیر، میزانی از انرژی مصرفی که به دلیل از دست رفتن اطلاعات است، در فرآیند برگشتپذیری حذف میشود. در طراحی مدار بر اساس تکنولوژیهای نانو،کاهش اتلاف انرژی یکی از اهداف مهم به شمار میرود و به تبع آن برگشتپذیری مدارات منطقی یکی از اصول اساسی است

مدارات برگشتپذیر به صورت وسیعی در محاسبات کوانتومی، سیستمهای مبتنی بر تکنولوژی نانو و اتوماتای سلولی کوانتومی کاربرد دارند. در این مقاله، به مقولهی پیادهسازی عمل ضرب با روش بو فولی - Baugh-Wooley - در منطق برگشتپذیر پرداخته شده است. مدار ضرب کننده ی بو فولی را از نظر تعداد ورودی یا خروجیهای بلااستفاده بررسی کردهایم و تعداد ورودیهای ثابت و خروجیهای بلااستفاده در مقایسه با سایر کارهای انجام شده را کاهش دادهایم.

-1  مقدمه

چارلز بنت در سال 1973 نشان داد در صورتی که محاسبات بهصورت برگشتپذیر انجام شوند شاهد انرژی اتلافشده از سوی مدارهای معمولی و برگشتناپذیر نخواهیم بود و از دیدگاه نظری مصرف انرژی در کامپیوترها به صفر میرسد

برای اینکه بتوان یک گیت کلاسیک را به یک گیت برگشتپذیر تبدیل کرد مجموعهای از بیتهای خدمتکار یا Ancilla Bit را به گیت اضافه میکنند. با اضافه کردن این بیتها میتوان گیتهای کلاسیک یا توابع کلاسیک را برگشتپذیر کرد. در مدارهای کوانتومی به ورودیهایی که به یک تابع k×n اضافه میشود تا آن تابع را به یک تابع برگشتپذیر مورد انتظار تبدیل کند، ورودیهای ثابت گفته میشود .[2]

خروجیهای بلااستفاده در یک مدار برگشتپذیر، آن دسته از خروجیها هستند که در هیچ عملیات محاسباتی دیگری درون مدار استفاده نخواهند شد و به عبارتی این خروجی نمیتواند بیشتر برای فرایند محاسبه بهکار برده شود.[3] یکی از معیارهای سنجش مدارهای برگشتپذیر هزینهی کوانتومی مدار میباشد. تعداد گیتهای برگشتپذیر پایه با اندازه-های 1×1 و 2×2 که به ترتیب دارای ارزش کوانتومی صفر و یک میباشند و در طراحی یک گیت برگشتپذیر مورد نیاز میباشند بهعنوان هزینهی کوانتومی آن گیت در نظر گرفته میشود.

از ضربکنندهها بهعنوان یکی از عملگرهای پایهای ریاضی یاد میشود که در بسیاری از کاربردهای عمومی میکروپروسسورها و کاربردهای خاص سیگنال پروسسورهای دیجیتال مورداستفاده قرار میگیرد. با پیشرفتهای حاصل شده در تکنولوژی، همواره سعی میشود ضربکنندههایی طراحی کنند که دارای سرعت بالا، مصرف توان کم و فضای کمی باشند. ضربکنندهی بو فولی نیز از این قاعده مستثنی نیست و نیمجمعکننده و تمامجمعکننده جزء مهمترین بخش این مدار ضرب کننده است.

نمونه کارهای زیادی به طراحی مدار ضربکننده پرداختهاند. به عنوان مثال در مرجع [7] دو طرح از ضربکنندهی علامتدار پیشنهاد شده است که از درخت والاس و الگوریتم بوفولی تغییریافته برای انجام عملیات ضرب و محاسبهی حاصل نهایی بهره گرفتهاند. روش کار بدین ترتیب است که عملیات در دو مرحله انجام میپذیرد: ابتدا با استفاده از دو روش متفاوت حاصلضربهای جزئی تولید شدهاند و در ادامه عملیات جمعکردن حاصلضربهای جزئی انجام پذیرفته است.

در رویکرد اول برای تولید حاصلضربهای جزئی از گیتهای PG و TG و FG استفاده شده است.در مدار نوع دوم برای تولید حاصلضربهای جزئی از گیتهای PG و TG استفاده شده است. برای تولید حاصلضربهای جزئی در طرح دوم سعی شده است که از تعداد گیت کمتری استفاده شود و ورودیهای ثابت و خروجیهای بلااستفادهی کمتری تولید شود. همچنین برای تولید گیتهای AND از گیت PG استفاده شده است تا هزینهی کوانتومی مدار به حداقل کاهش یابد.

برای کاهش گیتهای Toffoli در مدارهای ضربکننده در برخی موارد گیتهای موجود را بازسازی میکنند تا مدار را بتوان بهینه کرد. در [8] گیت Fredkin با ساختاری جدید با نام RF ارائه شده است. با استفاده از گیت جدید گیتهای 4*4 برگشتپذیر و جدیدی با نام ZS ارائه شدهاند که قابلیت جمع برگشتپذیر دو عدد علامتدار را دارند.

الگوریتمی که تحت عنوان بو فولی مشهور است برای ضرب آرایهای مکمل دوی اعداد طراحی شده بود. مزیت این الگوریتم آن است که علامت تمامی جمعوندها مثبت است و بدین ترتیب میتوان آرایه را کلا با تمامجمعکنندهها ساخت و مدیریت بیت علامت به صورتی کارا انجام میپذیرد. چنین ساختاری در طراحی مدارهای VLSI بسیار جذاب و دارای اهمیت است.

در [9] برای اولین بار طراحی فشردهای از ضربکنندهی بو فولی با استفاده از منطق برگشتپذیر ارائه شده است. در این کار ضرب کنندهی 5x5 جدیدی برای طراحی ضرب کنندهی بو فولی پیشنهاد گردیده است. در [10] ضرب کنندهی بو فولی علامت دار با استفاده از کمپرسورها ارائه شده است. در این کار دو نوع کمپرسور جدید 4:2 و 5:2 معرفی شدهاند و از ساختار درخت Wallace برای کاهش تعداد مراحل استفاده شده است.

کمپرسورهای پیشنهاد شده مقدار تاخیر و فضای مورد استفاده در مدار را نیز بهبود بخشیدهاند. کارایی کمپرسورهای پیشنهادی با استفاده کردن از آنها در ضربکنندهی بو فولی با درخت Wallace سنجیده شده است. نتایج نشان میدهند که هنگام استفاده از کمپرسور 5:2 فضای مورد استفاده 6,77 درصد و سرعت مدار 7,04 درصد بهبود پیدا کرده است.

در [7] یک ضرب کنندهی علامتدار Wallace با استفاده از ایجاد تغییرات در مدار بو فولی ارائه شده است. در این کار و در یکی از ساختارهای ارائه شده با کاهش عمق مدار سرعت آن افزایش پیدا کرده است. ساختار بعدی با هدف بهبود هزینهی کوانتومی، خروجیهای بلااستفاده و سایر پارامترها ارائه شده است.

در مقاله [11] با استفاده از منطق CMOS TSPC یک مدار ضرب کنندهی BW علامت دار 8*8 خط لولهای، ارائه و پیاده سازی شده است. منطق TSPC عملیات مداری خط لولهای با سرعت بالا را پشتیبانی میکند. نتایج شبیه سازی نشان داد که ورودیها میتوانند در هر کلاک اعمال شوند و پس از 17 سیکل کلاک در سرعت کلاک 500MHz، خروجی صحیح تولید میشود. این پیاده سازی دارای قابلیت کاهش در تعداد ترانزیستورها، توان میانگین و تاخیر نسبت به نمونههای مشابه میباشد.

در [12]، یک درخت ضرب کنندهی کارا - HPM - پیشنهاد شده است که در آن از الگوریتم بو فولی استفاده شده است. این درخت یک چینش منظم را با عمق منطق لگاریتمی ترکیب میکند. نویسندگان نشان دادهاند که برای یک محدوده از عملگرها، درتکنولوژیهای 130 نانومتر و 65 نانومتر، ضرب کنندههای بو فولی، تاخیر مشابه، اتلاف توان و مساحت کمتری را نسبت به ضرب کنندههای Booth صرف میکنند.

در این مقاله یک ضرب کنندهی برگشتپذیر علامتدار بهبودیافته بر پایهی الگوریتم یا ضرب کنندهی بو فولی پیشنهاد داده شده است. ضربکنندهی پیشنهاد شده از نظر تعداد ورودیهای ثابت و خروجیهای بلااستفاده در میان کارهای مشابه موجود بهینه میباشد و طبق مقایسات صورت گرفته کمترین تعداد ورودی ثابت و خروجی بلااستفاده را دارد. در طراحی مداراتی که در آنها تعداد ورودی ثابت و یا خروجی بلااستفاده حیاتی میباشد، میتوان از مدار پیشنهادی در این مقاله با کمترین هزینه استفاده کرد.

-2 گیتهای برگشت پذیر

در این بخش گیتهایی از منطق برگشتپذیر را مرور میکنیم که در این پژوهش مورد استفاده قرار گرفته است. نکته مهم در گیتهای برگشتپذیر، نگاشتی است که یک به یک بین بردار ورودی و بردار خروجی برقرار است. از جمله مهمترین گیتهای برگشتپذیر عبارتند از: Feynmann، Toffoli، Peres، MKG، HNG و غیره.

گیت Toffoli یا TG که تحت عنوان CCNOT هم شناخته میشود، گیتی برگشتپذیر و دارای سه عدد ورودی و سه عدد خروجی است. چون گیت Toffoli را میتوان با استفاده از پنج گیت 2x2 ساخت، هزینهی کوانتومی این گیت برابر 5 است؛ این گیت با استفاده از دو گیت V، یک گیت V+ و دو گیت CNOT پیادهسازی میشود .[4] گیت Toffoli جامع است؛ بدین معنی که هر مدار برگشتپذیر را میتوان با استفاده از تعداد متناهی از گیتهای Toffoli و ورودیهای ثابت ساخت. اگر ورودی هدف این گیت - ورودی - C برابر 0 قرار داده شود خروجی هدف - خروجی - R برابر با A.B میشود.

بردار ورودی، A را ورودی کنترلکننده و B را ورودی کنترلشونده میگویند . گیت FG برگشتپذیر و 2x2 است و دارای هزینه کوانتومی است.

جدول 1 بلوک دیاگرام گیت CNOT را نشان میدهد. اگر مقدار A برابر 1 باشد، NOT - B - اعمال میشود و در غیر اینصورت مقدار خود B اعمال میشود.از آنجایی که گنجایش خروجی در مدارهای برگشتپذیر تعریف نمیشود، گیت Feynman میتواند در این مورد بسیار سودمند باشد. میتوان در مدارهای برگشتپذیر از این گیت برای کپی کردن سیگنال استفاده کرد که به خودی خود مسالهی گنجایش خروجی را برای ما حل میکند.

گیت Peres یا PG که تحت عنوان گیت New Toffoli یا NTG هم شناخته میشود، گیتی برگشتپذیر و دارای سه عدد ورودی و سه عدد خروجی است - 3x3 - و از یک گیت Toffoli و یک گیتFeynman ساخته میشود.

پیادهسازی کوانتومی گیت Peres نیازمند دو گیت V+، یک گیت V و یک گیت CNOT است. بنابراین هزینهی کوانتومی آن برابر با 4 است. PG نیز مانند Toffoli یک گیت جامع است و با وجود پیچیدگی ظاهریاش دارای هزینهی کوانتمومی کمتری نسبت به گیت Toffoli است.

جدول :1 بلوک دیاگرام گیتهای برگشت پذیر معرفی شده

در ادامه عملیات جمعکردن حاصلضربهای جزئی انجام پذیرفته است.

در رویکرد اول برای تولید حاصلضربهای جزئی از گیتهای PG و TG و FG استفاده شده است. در مدار نوع دوم برای تولید حاصلضربهای جزئی از گیتهای PG و TG استفاده شده است. برای تولید حاصلضربهای جزئی در طرح دوم سعی شده است که از تعداد گیت کمتری استفاده شود و ورودیهای ثابت و خروجیهای بلااستفادهی کمتری تولید شود. همچنین برای تولید گیتهای AND از گیت PG استفاده شده است تا هزینهی کوانتومی مدار به حداقل کاهش یابد.

برای کاهش گیتهای Toffoli در مدارهای ضربکننده در برخی موارد گیتهای موجود را بازسازی میکنند تا مدار را بتوان بهینه کرد. در [8] گیت Fredkin با ساختاری جدید با نام RF ارائه شده است. با استفاده از گیت جدید گیتهای 4*4 برگشتپذیر و جدیدی با نام ZS ارائه شدهاند که قابلیت جمع برگشتپذیر دو عدد علامتدار را دارند.

الگوریتمی که تحت عنوان بو فولی مشهور است برای ضرب آرایهای مکمل دوی اعداد طراحی شده بود. مزیت این الگوریتم آن است که علامت تمامی جمعوندها مثبت است و بدین ترتیب میتوان آرایه را کلا با تمامجمعکنندهها ساخت و مدیریت بیت علامت به صورتی کارا انجام میپذیرد. چنین ساختاری در طراحی مدارهای VLSI بسیار جذاب و دارای اهمیت است.
در [9] برای اولین بار طراحی فشردهای از ضربکنندهی بو فولی با استفاده از منطق برگشتپذیر ارائه شده است. در این کار ضرب کنندهی 5x5 جدیدی برای طراحی ضرب کنندهی بو فولی پیشنهاد گردیده است. در [10] ضرب کنندهی بو فولی علامت دار با دو نوع کمپرسور جدید 4:2 و 5:2 معرفی شدهاند و از ساختار درخت Wallace برای کاهش تعداد مراحل استفاده شده است. کمپرسورهای پیشنهاد شده مقدار تاخیر و فضای مورد استفاده در مدار را نیز بهبود بخشیدهاند. نتایج نشان میدهند که هنگام استفاده از کمپرسور 5:2 فضای مورد استفاده 6,77 درصد و سرعت مدار 7,04 درصد بهبود پیدا کرده است.

-3 مدار ضربکننده های بو فولی

مرجع [7] دو طرح از ضربکنندهی علامتدار پیشنهاد کرده که از درخت والاس و الگوریتم بو فولی تغییریافته برای انجام عملیات ضرب و محاسبهی حاصل نهایی بهره گرفتهاند. روش کار بدین ترتیب است که عملیات در دو مرحله انجام میپذیرد: ابتدا با استفاده از دو روش متفاوت حاصلضربهای جزئی تولید شدهاند و در مقاله [11] با استفاده از منطق CMOS TSPC یک مدار ضرب کنندهی BW علامت دار 8*8 خط لولهای، ارائه و پیاده سازی شده است. منطق TSPC عملیات مداری خط لولهای با سرعت بالا را پشتیبانی میکند . در [12]، یک درخت ضرب کنندهی کارا - HPM - پیشنهاد شده است که در آن از الگوریتم BW استفاده شده است. این درخت یک چینش منظم را با عمق منطق لگاریتمی ترکیب میکند.