بخشی از مقاله
*** این فایل شامل تعدادی فرمول می باشد و در سایت قابل نمایش نیست ***
طراحي يک ضرب کننده ترتيبي تخميني مميز شناور با قابليت جبران خطا
چکيده
محاسبات تخميني ييک از جديدترين شاخه محاسبات کامپيوتري است که به ازاي سرعت ، توان مصرفي و سطح سيليکون ، دقت را اندکي ناديده ميگيرد. ازجمله واحدهاي محاسباتي ديجيتال ، ضرب کننده هاي برش يافته هستند که به صورت تخميني پياده سازي ميشوند. در اين مقاله يک ضرب کننده برش يافته تخميني اعداد مميز شناور با دقت عادي ، طراحيشده است که ميتواند با استفاده از ستون هاي پرارزش ماتريس حاصل ضرب جزيي کم ارزش ، خطاي ناشي از حذف رقم هاي نقلي انتقالي از ستون هاي حذف شده را که در محاسبه بيت هاي شرکت کننده در عمل گرد کردن اعداد مميز شناور، نقش مستقيم دارند را تا حد مطلوبي جبران کند. ارزيابي هاي انجام شده نشان مي دهد که روش بکار گرفته شده ، ميزان خطاي حاصل از حذف مابقي ستون هاي کم ارزش را تا حد مطلوبي کاهش مي دهد.
واژه هاي کليدي
محاسبات تخميني، ضرب کننده برش يافته ، ماتريس حاصل ضرب جزيي ، گردکردن .
١-مقدمه
ضرب کننده ها يکي از اصلي ترين واحدهاي محاسباتي هستند که در سيستم هاي ديجيتالي مانند سيستم هاي پردازش سيگنال دييجتال ، سيستم هاي جاسازي شده ، پردازنده ها و سيستم هاي موبايل به طور گسترده کاربرد دارند. ازجمله مهم ترين مشکلات اين سيستم ها ميتوان به سرعت پايين ، توان مصرفي و سطح سيليکون اشغالي بالا اشاره کرد که موجب افت عملکرد سيستم ديجيتال ميشود.
محاسبات تخميين ايده مشهوري است که با حذف بخشي از مدارات محاسباتي و برخي محاسبات مياني ، پياده سازي يمشود. هرچند اين حذف موجب بالا رفتن سرعت و کاهش سطح سيليکون و توان مصرفي ميشود ولي موجب کاهش اندک دقت مدار محاسباتي ميگردد، همچنين اين ايده سعي در يافتن نقطه بهينه اي از ميان سه ويژگي سرعت ، توان و سطح سيليکون دارد[٢].
در ميان واحدهاي محاسباتي، جمع کننده هاي متنوعي با استفاده از روش تخميني پياده سازي شده اند و مطالعات نشان ميدهند تکنيک هاي پيشنهادشده به خوبي توانسته اند چالش هاي موجود بر سر راه اين جمع کننده ها را برطرف نمايند [٥-٣].
حذف k ستون کم ارزش از ماتريس حاصل ضرب جزيي روشي است که در[٧-٦] بکار رفته ، اين مدار در جبران خطاي ناشي از حذف ستون هاي کم ارزش ، عدد ثابتي را که برابر ميانگين وزن دار قسمت حذف شده ميباشد را به حاصل اضافه ميکند. ازجمله اشکالات اين روش اين است که تأثيري در کاهش توان مصرفي و مساحت ندارد.
استفاده از پرارزش ترين قسمت ستون هاي کم ارزش ( Least Signification Part)LSP براي تخمين بيت نقلي انتقالي از اين ستون به قسمت (Most Signification Part) پرارزش MSP ، روشي است که در [٩-٨] بيان شده است . اين روش به وروديهاي مدار ضرب وابسته است و داراي مدار تخمين پيچيده اي است ولي دقت بالاي دارد.
استفاده از ايده ضرب کننده هاي برش يافته موازي روشي است که در [١٠] بکار رفته و ضرب کننده ترتيبي ارائه ميکند که جواب نهايي آن n بيتي است و به ميزان اندکي سرعت مدار و سطح سيليکون را بهبود ميبخشد ولي راه حلي براي جبران خطا ارائه نمي کند.
در اين مقاله به پياده سازي ضرب کننده تخميني ترتيبي برش يافته اعداد مميز شناور در دقت عادي پرداخته ميشود که برش هايي روي قسمت هايي از ماتريس حاصل ضرب جزيي کم ارزش انجام شده که درنهايت با به کارگيري چهارستون از قسمت کم ارزش ماتريس حاصل ضرب هاي جزيي کم ارزش و استفاده از يک مدار کوچک جهت تخمين رقم نقلي انتقالي از ستون پنجم ، خطا را به ميزان قابل توجهي کاهش ميدهد و حاصل به مقدار دقيق ضرب همگرا ميشود.
ساختار اين مقاله به شرح زيراست . بخش دوم الگوريتم ضرب اعداد مميز شناور معرفي ميشود، بخش سوم به ضرب کننده تخميني ترتيبي پيشنهادي ميپردازد، در بخش چهارم احتمال خطاي بيشينه محاسبه ميگردد، بخش پنجم به شبيه سازي و ارزيابي روش جديد همراه با مقايسه آن باحالت هاي ديگر ضرب مي پردازد و نهايتا بخش ششم به نتيجه گيري اختصاص داده شده است .
٢-الگوريتم ضرب اعداد مميز شناور
١-٢- اعداد مميز شناور
مميز شناور به روشي گفته مي شودکه براي نمايش اعداد حقيقي بکار ميرود. برتري اعداد مميز شناور به مميز ثابت و اعداد صحيح در توانايي پشتيباني آن ها از دامنه گسترده تري از مقادير است . سرعت عمليات محاسباتي اعداد مميز شناور از ويژگي مهم ماشين ها ميباشد[١١].
از دهه ١٩٩٠به بعد، نمايش معمول اين اعداد بر اساس استاندارد 2008-IEEE754 تعيين مي شود. اين استاندارد چند پهناي بيتي براي اعداد مميز شناور تعيين کرده که دو پهناي دقت عادي و دقت مضاعف بيشتر از همه موارد، مورد استفاده است . اعداد با دقت عادي ٣٢ بيت و با دقت مضاعف ٦٤ بيت طول دارند که در اين تحقيق دقت عادي اعداد موردنظر است . نمايش هر عدد مميز شناور طبق استاندارد، در دقت عادي به صورت زير است [١١]:
که Sيک بيت مشخص کننده علامت ، E هشت بيت مشخص کننده محدوده ديناميکي عدد و m٢٣ بيت مشخص کننده دقت عدد ميباشد[١١].
٢-٢-ضرب اعداد مميز شناور
شکل ١ الگوريتم ضرب اعداد مميزشناور را نشان ميدهد. الگوريتم شامل سه قسمت علامت ، نما ومانتيس ميباشد، در اين تحقيق قسمت ضرب مانتيس عدد موردنظر است که شامل مراحل زير است [١٢]:
١-جداسازي بيت هاي عدد
٢-انجام عمل ضرب (بر اساس الگوريتم ضرب ترتيبي)
٣-هنجارسازي
٤-گرد کردن
٥-هنجارسازي مجدد
٦-برگرداندن عدد به قالب اوليه
٣-٢-گرد کردن
شکل ٢، ماتريس حاصل ضرب هاي جزيي حاصل ازضرب مانتيس هاي دو عدد مميز شناور را در دقت عادي نشان مي دهد، اين حاصل ٤٨ بيت دارد بکيه ت به ماندتلييل س موحيدک ودبييت ت هاحيصاعل ماازل هشندجه ارتوساسزط ي)سپرتاارنزداش رد رتنمهاجا٢٤به بنيگت هد(ار٣ي هستيم ، به منظور جبران خطاي حاصل از حذف قسمت کم ارزش ، با استفاده از سه بيت مربوط به پرارزش ترين مکان قسمت کم ارزش ، عمل گرد کردن را انجام مي دهيم که البته طبق استاندارد ميباشد. [١١].
شکل ١: الگوريتم ضرب اعداد مميز شناور
شکل ٢: ماتريس حاصل ضرب جزيي مانتيس هاي دو عدد مميز شناور در دقت عادي
٣-ضرب ترتيبي تخميني پيشنهادي
١-٣- الگوريتم
شکل ٣ مدار اين ضرب کننده را نشان ميدهد که شامل ثبات ٢٠ بيتي A (براي ذخيره بيت هاي ١ام تا ٢٠ام مضروب )، ثبات ٢٤ بيتي B (براي ذخيره مضروب فيه ) و ثبات ٢٨ بيتي P (براي ذخيره حاصل ) با مقدار اوليه صفرمي باشد. با توجه به اينکه اين ضرب کننده يک ضرب کننده برش يافته ٢٨ بيتي ترتيبي است و در اين طرح به ٢٠ بيت کم ارزش جواب نهايي نيازي نيست ميتوان بخشي از مدار را که اين ٢٠ بيت کم ارزش را محاسبه ميکند حذف کرد، براي رسيدن به اين هدف ثبات ٢٨ بيتي Ex را تعريف کرده که مقدار اوليه اي به صورت زير دارا مي باشد:
1 که A1 ثبات فرضي با مقدار اوليه مضروب مي باشد.
شکل ٣: مدار ضرب کننده پيشنهادي
عملکرد ضرب کننده به شرح زير است :
١-در سيکل اول در صورت يک بودن بيت کم ارزش ثبات B،Ex با P جمع شده و حاصل درP قرار مي گيرد در غير اين صورت P مقدار قبلي خود را حفظ مي کند.
٢-در هر سيکل i ابتدا ثبات A يک بيت به چپ جابجا شده و بيت بيرون افتاده ، از راست وارد ثبات Ex مي گردد.
٣-با توجه به مقدار کم ارزش ترين بت ي مضروب فيه (B) در سيکل i، يا ثبات Ex باثبات حاصل ضرب جزيي به نام p جمع شده يا P همان مقدار قبلي خود را حفظ مي کند.
٤- دو مرحله اخيرتا ٢٤ سيکل تکرار مي شود و در سيکل آخر حاصل در p قرار مي گيرد.
٢-٣-مدار جبران خطا
در ضرب کننده برش يافته ترتيبي پيشنهادي بيت هاي p2، p3، p4 واقع در ثبات p درواقع بيت هاي S،G ،R (به ترتيب از چپ به راست ) در عمل گرد کردن در شکل ٢ ميباشند که طبق اظهارات قبل به منظور محاسبه بيت S بايد تمامي بيت هاي کم ارزش از بيت ٢٢ به بعد در دسترس باشد که در اين ضرب کننده برش يافته تنها بيت هاي ٢١ و٢٢ (p1 وp2 ثبات P) در دسترس مي باشد. از طرفي در هر مرحله از ضرب ترتيبي رقم نقلي انتقالي از بيت هاي کم ارزش به قسمت پرارزش انتقال مي يابد [١]، اما در اين ضرب کننده برش يافته بيت هاي ٢٠ام تا ١ام حاصل جمع مياني در دسترس نيست بنابراين رقم نقلي انتقالي از اين بيت هاي حذف شده در محاسبه S نقشي ندارد و اين به نوبه خود موجب ايجاد خطا در محاسبه بيت S و نتيجه نادرست عمل گرد کردن در استاندارد خواهد شد. پس با توجه به دو نکته ميتوان حاصل دقيق تري براي S به دست آورد، اول اينکه رقم هاي نقلي انتقالي حذفي از کدام ستون ماتريس حاصل ضرب هاي جزيي بيشترين تأثيررا در محاسبه S دارد، دوم اينکه بتوان مدار کوچکي طراحي کرد که اين رقم نقلي را تخمين بزند.
با واردکردن ستون هاي مختلف در محاسبات ، مشخص شد که استفاده از ستون ٢٠ام ماتريس حاصل ضرب هاي جزيي واقع در شکل ٢ بيشترين تأثير را در محاسبه S دارد همچنين ميتوان اين رقم هاي نقلي انتقالي مياني را با مدار ecv مشخص شده در شکل ٣ تخمين زد. مدار ecv بايد رقم نقلي انتقالي را در سيکل iام که مربوط به ستون ٢٠ام ماتريس حاصل ضرب هاي جزيي است (٢٠,ci) را تخمين بزند، بنابراين لازم است تا عناصري که در ايجاد آن نقش دارند، مشخص گردد. براي توليد ٢٠,ci نياز به سه بيت است :
١-حاصل ضرب جزيي واردشده در سيکل i که برابر مقدار است و با ppi مشخص مي شود.
٢-مجموع حاصل ضرب هاي جزيي از سيکل صفر تا (١-i)ام که با Avi مشخص مي گردد.
٣-رقم نقلي توليدشده در سيکل iام و ستون ١٩ام (١٩,ci). با توجه به اينکه در روش پيشنهادي اين بيت در دسترس نيست براي پيش بيني رقم نقلي سيکل iام و ستون ٢٠ام از ماتريس حاصل ضرب هاي جزيي، فقط از ppi و Avi استفاده مي کنيم .
مقدار ppi در هر سيکل در دسترس است ، اما به دليل وابستگي Avi به مابقي ppiها از يک فليپ فلاپ براي ذخيره مجموع ppiها استفاده شده است که مقدار آن در سيکل iام با vffi مشخص مي شود بنابراين داريم :
