Montgomery Part Two

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

پس استفاده از CSA برای انجام جمع های متوالی مناسب است.

معماری پنج به دو در شکل زیر نمایش داده شده است. همان‌طور که مشاهده می نمایید خروجی این بلوک تنها یک بیت بیشتر از تعداد بیت‌های ورودی است :

 بنابراین می‌توانیم الگوریتم مونتگمری را با توجه به معماری پنج به دو به این صورت بنویسیم :

منظور از CSR در این الگوریتم همان بلوک معماری پنج به دو می‌باشد که پنج ورودی و دو خروجی دارد.

مسیر بحرانی در این معماری شامل محاسبه عبارت زیر می باشد.

برای محاسبه مقدار A اندیس i  می‌توان از BRFA  نشان داده شده در شکل 14 استفاده کرد و نیازی به محاسبه جمع دو مقدار A1 و A2 نمی باشد. زیرا در هر سیکل می‌توان مقدار A اندیس i را به دست آورد.

یک سیکل اضافی برای بازنشاندن دو رجیستر S1[0] و S2[0] مورد نیاز است. بنابراین در این روش برای محاسبه حاصل ضرب به K+1 سیکل ساعت احتیاج داریم.

برای ارتباطات ورودی و خروجی در این طرح از نمودار بلوکی شکل 15 استفاده می‌شود. که در هر سیکل ساعت برای هر کدام از مقادیر A1 , A2 , B1 , B2 , n یک بلوک سی دو بیتی خوانده شده است و در رجیستر ورودی ذخیره می‌شوند و همچنین پس از آماده شدن رجیستر خروجی ، آن نیز به صورت خروجی سی و دو بیتی ارسال می شود.

برای استفاده از معماری پنج به دو سی اس ای می‌توان الگوریتم مونتگمری را به صورت زیر نیز استفاده کنیم

منظور از MontMult در این الگوریتم روش ضرب مونتگمری است. D اندیس k نیز بیان کننده تعداد بیت‌های توان است. با توجه به اینکه در داخل حلقه دو بخش محاسبه توان و ضرب می‌توانند موازی با هم اجرا شوند ،برای افزایش سرعت می‌توان در پیاده‌سازی سخت افزاری می‌توان دو واحد محاسبه ضرب مونتگمری را به کار برد.

برای قرار دادن نتیجه در ورودی واحد ضرب مونتگمری برای محاسبه سیکل بعدی یک سیکل اضافی در نظر گرفته شده است.بنابراین هر ضرب مونتگمری در K+2 سیکل انجام می شود.

عملیات Pre-Proccessing و  Past-Proccessing برای تبدیل عملوند ها به قالب مورد نیاز الگوریتم و تبدیل برعکس آن لازم هستند. برای محاسبه نتیجه نهایی می‌توان از واحد BRFA استفاده کرده و و دو مقدار نهایی را با هم جمع کرد که در این صورت باید k سیکل برای محاسبه جمع و دو سیکل اضافی برای بازنشاندن و قرار دادن نتیجه در خروجی صرف کرد.

با توجه به بخش قبل می‌توان دریافت که به منظور تسریع در عمل توان رسانی بهتر است از دو واحد ضرب مونتگمری مجزا استفاده شود. از این دو واحد علاوه بر استفاده در داخل حلقه برای عملیات Pre-Processing و Past-Processing نیز استفاده می شود. ولی در انتهای عملیات که حاصل جمع واقعی دو مقدار M1 و M2 محاسبه می شود. این دو واحد عمل خاصی را انجام نمی دهند . و از واحد BRFA برای محاسبه عمل جمع استفاده می شود. که حداقل به تعداد بیت‌های عملوند به پالس ساعت احتیاج دارند. در این بخش نشان داده می‌شود که می‌توان با استفاده از این دو واحد تعداد پالس های ساعت را حداقل به یک سوم کاهش داد.

با توجه به روابط CSAدر صورتی که یکی از عملوند ها صفر باشد آن گاه روابط زیر برقرار می شوند.

بنابراین با هر بار عمل CSAیک بیت حاصل جمع دو مقدار X1و X2به دست می‌آید. برای مثال برای به دست آوردن حاصل جمع دو مقدار 0101 و و 1101 که پنج بیتی است ، به ترتیب مقادیر زیر محاسبه می شوند.

بنابراین به منظور جمع دو مقدار M1 و M2به دست آمده در الگوریتم می‌توان از واحد CSAبه جای BRFA استفاده کرد و به دلیل ثابت بودن پریود ساعت ، این رویکرد تأثیری در تأخیر کلی نخواهد داشت. زیرا بیش ترین تأخیر مربوط به سه واحد CSAمی‌باشد که در محاسبه ضرب مونتگمری استفاده می شود.در صورتی که بتوان از واحد ضرب مونتگمری به آن منظور استفاده کرد ، چون در یک پریود ساعت سه عمل CSA رخ می‌دهد ، تعداد پالس ها به یک سوم کاهش می‌یابد.

برای رسیدن به این مقصود بایستی ورودی های مناسبی را به این واحد اعمال کرد. با توجه به نمودار بلوکی ، برای جمع دو مقدار B1و B2 باید آن‌ها را به دو ورودی X1 و X2 نسبت داد و سایر ورودی ها را صفر در نظر گرفت. بنابراین باید واحد ضرب مونتگمری را تغییر داد تا در این مورد در هنگام باز نشاندن به جای مقدار صفر ، مقادیر B1 و B2در دو رجیستر S1 و S2 قرار گیرد. همچنین برای آنکه سایر ورودی ها صفر شوند باید ، در واحد ضرب کننده ورودی های A1و A2 و n صفر در نظر گرفته شوند. چون در الگوریتم ضرب مونتگمری پس از هر بار عمل جمع یک عمل تقسیم بر دو انجام می گیرد. برای جلوگیری از بین رفتن بیت‌های داده ، باید به تعداد مناسب صفر در سمت راست عملوند ها قرار داد.

برای پیاده‌سازی چنین جمع کننده ای باید دو مقدار M1 و M2را به دو قسمت تقسیم کرده و پس از اضافه کردن تعداد بیت‌های صفر لازم ، هر نیمه را به یک واحد ضرب صفر مونتگمری داد و سایر ورودی ها را صفر قرار داد.

برای تعیین تعداد بیت‌های صفر لازم می‌توان از رابطه nbits = [ K/6 ] استفاده کرد که در این رابطه منظور از K تعداد بیت‌های M1 یا M2است. پس از K/6پالس ساعت نتایج آماده می‌شود در صورتی که نیمه اول دارای رقم نقلی نباشد ، نتیجه نهایی به دست آمده است. اما اگر دارای رقم نقلی باشد ، باید یک بار دیگر نیمه دوم را همراه با مقدار یک پس از مراحل ذکر شده فوق ، به واحد ضرب مونتگمری داد. بنابراین در بهترین حالت تعداد پالس های مورد نیاز به یک ششم و در بدترین حالت به یک سوم مقدار اولیه کاهش می‌یابد . الگوریتم توان رسانی اصلاح شده را می‌توان به صورت زیر بیان کرد.

توجه شود که در هنگام محاسبه حاصل جمع نتیجه نهایی در اولین پارامتر واحد ضرب مونتگمری که نشان دهنده مقدار SUMاست قرار می‌گیرد بنابراین پاسخ نهایی شامل دو مقدار T1 و T3است. همچنین خروجی دو واحد ضرب مونتگمری پس از  K/6 پالس ساعت آماده است که پس از این زمان باید مقدار آن را از خروجی واحد خواند.

همان‌طور که مشاهده می‌شود در الگوریتم اصلاح شده با استفاده از دو واحد ضرب مونتگمری عمل جمع نهایی در K/3+2تا K/6+2 پالس ساعت انجام می شود. و چون در این سیستم برای قرار دادن نتیجه واحد ضرب کننده در ورودی آن یک پالس اضافه مصرف می‌شود ، به دلیل کم‌تر بودن تأخیر مولتی پلکسر استفاده شده برای انتخاب ورودی های این واحد ، از تأخیر سه واحد CSA تأخیر مسیر بحرانی افزایش نمی یابد و بنابراین در فرکانس سیستم تأثیر نخواهد گذاشت. برای مقایسه این الگوریتم به همراه الگوریتم اصلی به زبان VHDL پیاده‌سازی شده و توسط نرم‌افزار Leonardo Spectrum 2002 برای کتاب خانه‌های  CMOS 0.6 و خانواده Virtex2 شرکت  Xilinx سنتز شده است که نتایج آن در جدول های زیر قابل مشاهده است