بخشی از مقاله
چکیده
محاسبات تخمینی یکی از جدیدترین شاخه محاسبات کامپیوتری است که به ازای سرعت، توان مصرفی و سطح سیلیکون، دقت را اندکی نادیده میگیرد. ازجمله واحدهای محاسباتی دیجیتال، ضربکنندههای برش یافته هستند که بهصورت تخمینی پیادهسازی میشوند . در این مقاله یکضربکننده برش یافته تخمینی اعداد ممیز شناور با دقت عادی، طراحیشده است که میتواند با استفاده از ستونهای پرارزش ماتریس حاصلضرب جزیی کمارزش، خطای ناشی از حذف رقمهای نقلی انتقالی از ستونهای حذفشده را که در محاسبه بیتهای شرکتکننده در عمل گرد کردن اعداد ممیز شناور، نقش مستقیم دارند را تا حد مطلوبی جبران کند. ارزیابیهای انجامشده نشان میدهد که روش بکار گرفتهشده، میزان خطای حاصل از حذف مابقی ستونهای کمارزش را تا حد مطلوبی کاهش میدهد.
-1مقدمه
ضربکنندهها یکی از اصلیترین واحدهای محاسباتی هستند که در سیستمهای دیجیتالی مانند سیستمهای پردازش سیگنال دیجیتال، سیستمهای جاسازیشده، پردازندهها و سیستمهای موبایل بهطور گسترده کاربرد دارند. ازجمله مهمترین مشکلات این سیستمها میتوان بهسرعت پایین، توان مصرفی و سطح سیلیکون اشغالی بالا اشاره کرد که موجب افت عملکرد سیستم دیجیتال میشود.
محاسبات تخمینی ایده مشهوری است که با حذف بخشی از مدارات محاسباتی و برخی محاسبات میانی، پیادهسازی میشود. هرچند این حذف موجب بالا رفتن سرعت و کاهش سطح سیلیکون و توان مصرفی میشود ولی موجب کاهش اندک دقت مدار محاسباتی میگردد، همچنین این ایده سعی در یافتن نقطه بهینهای از میان سه ویژگی سرعت، توان و سطح سیلیکون دارد.[2]
در میان واحدهای محاسباتی، جمعکنندههای متنوعی با استفاده از روش تخمینی پیادهسازی شدهاند و مطالعات نشان میدهند تکنیکهای پیشنهادشده بهخوبی توانستهاند چالشهای موجود بر سر راه این جمعکنندهها را برطرف نمایند .[3-5] حذف k ستون کمارزش از ماتریس حاصلضرب جزیی روشی است که در[6-7] بکار رفته، این مدار در جبران خطای ناشی از حذف ستونهای کمارزش، عدد ثابتی را که برابر میانگین وزندار قسمت حذفشده میباشد را به حاصل اضافه میکند. ازجمله اشکالات این روش این است که تأثیری در کاهش توان مصرفی و مساحت ندارد.
استفاده از پرارزشترین قسمت ستونهای کمارزش - Least LSP - Signification Part برای تخمین بیت نقلی انتقالی از این ستون به قسمت - Most Signification Part - پرارزشMSP ، روشی است که در [8-9] بیانشده است. این روش به ورودیهای مدار ضرب وابسته است و دارای مدار تخمین پیچیدهای است ولی دقت بالای دارد. استفاده از ایده ضربکنندههای برش یافته موازی روشی است که در [10] بکار رفته و ضربکننده ترتیبی ارائه میکند که جواب نهایی آن n بیتی است و به میزان اندکی سرعت مدار و سطح سیلیکون را بهبود میبخشد ولی راهحلی برای جبران خطا ارائه نمیکند.
در این مقاله به پیادهسازی ضربکننده تخمینی ترتیبی برش یافته اعداد ممیز شناور در دقت عادی پرداخته میشود که برشهایی روی قسمتهایی از ماتریس حاصلضرب جزیی کمارزش انجامشده که درنهایت با بهکارگیری چهارستون از قسمت کمارزش ماتریس حاصلضربهای جزیی کمارزش و استفاده از یک مدار کوچک جهت تخمین رقم نقلی انتقالی از ستون پنجم، خطا را به میزان قابلتوجهی کاهش میدهد و حاصل به مقدار دقیق ضرب همگرا میشود.
ساختار این مقاله به شرح زیر است. بخش دوم الگوریتم ضرب اعداد ممیز شناور معرفی میشود، بخش سوم به ضربکننده تخمینی ترتیبی پیشنهادی میپردازد، در بخش چهارم احتمال خطای بیشینه محاسبه میگردد، بخش پنجم به شبیهسازی و ارزیابی روش جدید همراه با مقایسه آن باحالتهای دیگر ضرب میپردازد و نهاتاًی بخش ششم به نتیجهگیری اختصاص دادهشده است.
-2الگوریتم ضرب اعداد ممیز شناور
-2-1 اعداد ممیز شناور
ممیز شناور به روشی گفته می شودکه برای نمایش اعداد حقیقی بکار میرود. برتری اعداد ممیز شناور به ممیز ثابت و اعداد صحیح در توانایی پشتیبانی آنها از دامنه گستردهتری از مقادیر است. سرعت عملیات محاسباتی اعداد ممیز شناور از ویژگی مهم ماشینها میباشد.[11] از دهه 1990به بعد، نمایش معمول این اعداد بر اساس استاندارد IEEE754-2008 تعیین میشود.
-2-2ضرب اعداد ممیز شناور
شکل1 الگوریتم ضرب اعداد ممیز شناور را نشان میدهد. الگوریتم شامل سه قسمت علامت، نما ومانتیس میباشد، در این تحقیق قسمت ضرب مانتیس عدد موردنظر است که شامل مراحل زیر است:[12] -1جداسازی بیتهای عدد -2انجام عمل ضرب - بر اساس الگوریتم ضرب ترتیبی - -3هنجارسازی -4گرد کردن -5هنجارسازی مجدد -6برگرداندن عدد به قالب اولیه
-2-3گرد کردن
شکل2، ماتریس حاصلضربهای جزیی حاصل ازضرب مانتیسهای دو عدد ممیز شناور را در دقت عادی نشان میدهد، این حاصل 48 بیت دارد که به دلیل محدودیتهای اعمالشده توسط استاندارد تنها 24 بیت 23 - بیت مانتیس و یک بیت حاصل از هنجارسازی - پرارزش را مجاز به نگهداری هستیم، بهمنظور جبران خطای حاصل از حذف قسمت کمارزش، با استفاده از سه بیت S - Sticky - ، G - Gard - ، R - Round - مربوط به پرارزشترین مکان قسمت کمارزش، عمل گرد کردن را انجام میدهیم که البته طبق استاندارد S= 22 OR 21 OR … 25 1 میباشد. .[11]
-3ضرب ترتیبی تخمینی پیشنهادی
-3-1 الگوریتم
شکل 3 مدار این ضربکننده را نشان میدهد که شامل ثبات 20 بیتی A - برای ذخیره بیتهای 1ام تا 20 ام مضروب - ، ثبات 24 بیتی B - برای ذخیره مضروبفیه - و ثبات 28 بیتی P - برای ذخیره حاصل - با مقدار اولیه صفرمیباشد. با توجه به اینکه این ضربکننده یک ضربکننده برش یافته 28 بیتی ترتیبی است و در این طرح به 20 بیت کم ارزش جواب نهایی نیازی نیست میتوان بخشی از مدار را که این 20 بیت کم ارزش را محاسبه میکند حذف کرد.
-3-2مدار جبران خطا
در ضربکننده برش یافته ترتیبی پیشنهادی بیتهای 2، 3، 4 واقع در ثبات p درواقع بیتهای S، G، R - به ترتیب از چپ به راست - در عمل گرد کردن در شکل 2 میباشند که طبق اظهارات قبل بهمنظور محاسبه بیت S باید تمامی بیتهای کمارزش از بیت 22 به بعد در دسترس باشد که در این ضربکننده برش یافته تنها بیتهای 21 و 1 - 22 و 2 ثبات - P در دسترس میباشد.
از طرفی در هر مرحله از ضرب ترتیبی رقم نقلی انتقالی از بیتهای کمارزش به قسمت پرارزش انتقال مییابد [1]، اما در این ضربکننده برش یافته بیتهای 20ام تا 1ام حاصلجمع میانی در دسترس نیست بنابراین رقم نقلی انتقالی از این بیتهای حذفشده در محاسبه S نقشی ندارد و این بهنوبه خود موجب ایجاد خطا در محاسبه بیت S و نتیجه نادرست عمل گرد کردن در استاندارد خواهد شد. پس با توجه به دو نکته میتوان حاصل دقیقتری برای S به دست آورد، اول اینکه رقمهای نقلی انتقالی حذفی از کدام ستون ماتریس حاصلضربهای جزیی بیشترین تأثیررا در محاسبه S دارد، دوم اینکه بتوان مدار کوچکی طراحی کرد که این رقم نقلی را تخمین بزند.
با واردکردن ستونهای مختلف در محاسبات، مشخص شد که استفاده از ستون 20ام ماتریس حاصلضربهای جزیی واقع در شکل2 بیشترین تأثیر
را در محاسبه S دارد همچنین میتوان این رقمهای نقلی انتقالی میانی را با مدار ecv مشخصشده در شکل 3 تخمین زد. مدار ecv باید رقم نقلی انتقالی را در سیکل iام که مربوط به ستون 20ام ماتریس حاصلضربهای جزیی است - ,20 - را تخمین بزند، بنابراین لازم است تا عناصری که در ایجاد آن نقش دارند، مشخص گردد. برای تولید ,20 نیاز به سه بیت است:
-1حاصلضرب جزیی واردشده در سیکل i که برابر مقدار 20− +1 است و با مشخص می شود.
-2مجموع حاصلضربهای جزیی از سیکل صفر تا - i-1 - ام که با مشخص می گردد.
-3رقم نقلی تولیدشده در سیکل iام و ستون 19ام . - ,19 - با توجه به اینکه در روش پیشنهادی این بیت در دسترس نیست برای پیش بینی رقم نقلی سیکل iام و ستون 20ام از ماتریس حاصلضربهای جزیی، فقط از و استفاده می کنیم. با AND کردن و +1` مقدار .20 بهجز در یک حالت بهدرستی پیشبینی میشود و آن زمانی است که یکی از بیتهای و +1 صفر و دیگری یک باشد، آنگاه روش جبران خطا، رقم نقلی را معادل صفر پیشبینی میکند، این در حالی است که اگر در ستون 19ام رقم نقلی یک باشد برخلاف پیشبینی فوق رقم نقلی باید یک باشد، و این بدان معناست که تنها در یک حالت است که جبران خطا بهدرستی صورت نمیگیرد. همانطور که در شکل 3 مشخص است مدار ecv رقم نقلی را در هر سیکل تولید و به جمعکننده میافزاید تا بخشی از خطای محاسبه S جبران گردد.
-4محاسبه احتمال خطای بیشینه
خطای بیشینه در عمل گرد کردن، بر اساس حالتهای مختلفی که برای بیتهایS، G، R اتفاق میافتد، تعریف میگردد. درواقع خطای بیشینه زمانی تعریف میشود که بیتهای G، R وS - یا به عبارتی بیتهایی که S بر اساس آن محاسبه میگردد - در اختیار نباشد یا مقادیر نادرستی از آنها در دسترس باشد، بنابراین عمل گرد کردن یا صورت نمیگیرد یا به اشتباه انجام میپذیرد.از طرفی بیتهای G، R درواقع همان بیتهای 23، 24 - به ترتیب از چپ به راست - درشکل2 میباشند ولی بیت S= - 22 21 20 - میباشد که 20 در دو حالت برش یافتهو بهصورت تخمینی محاسبه میگردد [1]، نتیجه حاصل از اعمال این دو روش در مقدار خطای بیشینه و تأثیر آن در محاسبه S در قسمت بعدی بیان میگردد.
