بخشی از مقاله
*** این مقاله شامل تعداد زیادی فرمول میباشد که در سایت قابل نمایش نیست ***
بهبود جمع چند عملوندي دهدهي با استفاده از کمپرسورها براي کاربرد در ضرب کننده هاي دهدهي سريع
چکيده
با توجه به نياز کاربردهايي مانند محاسبات مالي، تجاري و انجام عمليات بانکي به عمليات جمع و ضرب دهدهي و همچنين در دسترس بودن سخت افزارهاي سريع ، انجام مستقيم محاسبات دهدهي با سرعت بالا به جاي محاسبات دودويي مورد توجه قرار گرفته است . در اين ميان ، انجام عمليات جمع چندعملوندي سريع به عنوان روشي براي انجام عمليات ضرب سريع دهدهي اهميت ويژه اي دارد. در اين مقاله با بررسي روش هاي پيشين براي کاهش حاصل ضرب هاي جزئي با استفاده از جمع کننده هاي ذخيره نقلي ، يک ساختار کمپرسور دهدهي ١٦:٢ جديد ارائه مي شود که علاوه بر قابليت استفاده براي جمع چند عملوندي دهدهي، ميتواند براي کاهش حاصل ضرب هاي جزئي در ضرب کننده هاي دهدهي مورد استفاده قرار گيرد. ساختار پيشنهادي جديد در مقايسه با روش هاي قبلي باعث بهبود هم در تأخير کل و هم در مساحت مورد نياز ميشود.
واژه هاي کليدي
جمع کننده ذخيره نقلي (CSA)، ضرب دهدهي ، کمپرسور، BCD، کدگذاري .
١- مقدمه
محاسبات اعداد مبناي ده (دهدهي) که در کامپيوترهاي اوليه مورد استفاده قرار گرفته اند، براي بهره برداري مناسب تر از سيستم هاي الکترونيکي موجود در آن زمان ، با محاسبات اعداد مبناي دو (دودويي ) جايگزين شدند [١]. اما گرايش به استفاده از کدگذاري دهدهي هنوز در مراکز تحقيقاتي بسياري وجود دارد. در سال هاي اخير، با توجه به کاربردهايي مانند محاسبات مالي، تجاري و انجام عمليات بانکي، مجددا طراحي سيستم هاي مبتني بر اعداد دهدهي مورد توجه زيادي قرار گرفته است ؛ اين توجه به ويژه در ضرب اعداد دهدهي ايجاد شده است [٢].
جمع هم زمان چندين عملوند دهدهي، اساس اکثر الگوريتم هاي ضرب و تقسيم است . در بعضي از طرح هاي مربوط به ضرب کننده ها، هر حاصل ضرب جزئي با دو عدد دهدهي نمايش داده ميشود. بسته به درجه ي موازي سازي انتخاب شده ، نياز به جمع سه ، پنج ، هفت و ... عدد دهدهي وجود دارد. علاوه بر اين ، برنامه هاي کاربردي تجاري -مالي مبتني بر اينترنت ، به ويژه تحقيقات بازاري بر اساس پايگاه داده هاي عظيم موجود،
مي توانند با استفاده از جمع کننده هاي دهدهي چند عملوندي، آسان تر انجام شوند [٣].
عمليات جمع چند عملوندي سريع براي پياده سازي ضرب کننده هاي با تأخير کم و ساير واحدهاي محاسباتي مميز-ثابت و مميز-شناور اهميتي اساسي دارد. به عنوان مثال ، براي پشتيباني از عمليات ضرب ٦٤ عملوندي دهدهي مطابق استاندارد ٢٠٠٨-٧٥٤ IEEE، پياده سازي هاي موازي ضرب کننده هاي BCD ٣ بايد قادر به کاهش تا ١٦ يا ٣٢ عملوند دهدهي باشد.
يک روش متفاوت براي پياده سازي ضرب دهدهي مطابق استاندارد IEEE ٢٠٠٨-٧٥٤، استفاده از نمايش دودويي براي ضرب علمي به همراه سخت افزار اضافي براي گرد کردن و نرمال سازي دهدهي است . جمع چند عملوندي دهدهي به دليل مسائل مربوط به ناکارآمدي نمايش هاي دهدهي در مدارات بولين ، از نظر پياده سازي پيچيده تر از نمايش دودويي است .
تاکنون روش هاي مختلفي براي بهبود کارايي پياده سازي مستقيم با عملوندهاي BCD پيشنهاد شده است . يک روش مورد توجه ، استفاده از مجموعه اي متفاوت از کدگذاري BCD (با وزن ٤٢٢١ و ٥٢١١) براي نمايش عملوندهاي دهدهي است که اجازه اجراي جمع سه عملوندي دهدهي را به روش جمع ذخيره نقلي ٣:٢ همراه با يک تصحيح کوچک مي دهد [٤، ٥].
کاهش حاصل ضرب هاي جزئي، توان و زمان زيادي از ضرب کننده را به خود اختصاص ميدهد.روش هاي زيادي براي کاهش مسير بحراني عمودي در ضرب کننده ها پيشنهاد شده است که در اين ميان استفاده از کمپرسور٤ در مرحله کاهش حاصل ضرب هاي جزئي مورد اقبال زيادي قرار گرفته است . کمپرسورها مدارهاي پايه اي هستند که تعداد يک ها را در وروديهاي داده شده ميشمارند. نمونه هاي معروف در ميان کمپرسورها عبارت اند از کمپرسورهاي ٣:٢، ٤:٢، ٥:٢، ٥:٣ [٦].
در اين مقاله ، با استفاده از کمپرسور ٥:٣ معرفي شده در بخش ٢، يک ساختار براي کمپرسور ١٦:٢ پيشنهاد ميشود که از عملوندهاي دهدهي کد شده به صورت ٤٢٢١ -BCD به عنوان ورودي استفاده ميکند. اين کمپرسور قابل استفاده در ضرب کننده هاي دهدهي براي کاهش حاصل ضرب هاي جزئي هست .
شکل ١. کمپرسور ٥:٣ مرسوم
٢- مفاهيم پايه
٢-١- کمپرسور ٥:٣
کمپرسور ٥:٣ مرسوم ، پنج گيت XOR براي توليد خروجي دارد (شکل ١). به منظور توليد خروجي سه گيت XOR مورد نياز است . گيت XOR نسبت به ساير گيت ها تأخير بحراني بيشتري دارد. بنابراين کمپرسور ٥:٣ مرسوم تأخير بيشتري دارد و توان بيشتري مصرف ميکند. در [٧] مدار مربوطه مجددا به گونه اي مرتب شده است که استفاده از گيت هاي XOR در آن کاهش يافت . کمپرسور پيشنهاد شده در [٧] با کمک سه مالتي پلکسر ١-٤ طراحي شده است . سه حاصل ضرب جزئي از آرايه ي حاصل ضرب هاي جزئي به عنوان ورودي و دو حاصل ضرب جزئي به عنوان سيگنال هاي کنترلي مالتي پلکسر وارد ميشوند. در شکل ٢، D و E
سيگنال هاي کنترلي هستند؛ بنابراين ، توليد خروجيها (O1، O2 و O3) سريع تر انجام ميشود. با توجه به اين که مالتي پلکسر نسبت به گيت هاي XOR سريع تر است و همچنين توان کمتري مصرف ميکند، زيرا بر اساس سيگنال هاي کنترلي در هر لحظه از زمان تنها يک ورودي فعال دارد، براي طراحي کمپرسور ٥:٣ ارائه شده در[٧]، مورد استفاده قرار گرفته است .
معادلات مربوط به اين کمپرسور در زير آمده است . اين کمپرسور سريع تر است ، زيرا بر اساس سيگنال هاي کنترلي نياز به محاسبه تنها يک ورودي دارد.
٢-٢- جمع ذخيره نقلي دهدهي
يکي از مرسوم ترين عناصر در کاهش حاصل ضرب هاي جزئي ، تمام جمع کننده ٥ (FA) يا شمارنده ٦ ٣:٢ است که همان CSA ٣:٢ محسوب ميشود. همانند حالت دودويي، کاهش حاصل ضرب جزئي دهدهي نيز ميتواند از شمارنده هاي ٣:٢ بهره ببرد، با اين تفاوت که هر رقم براي مطابقت با کدگذاري ٨٤٢١ -BCD طول ٤ بيت خواهد داشت . نتيجه جمع با اضافه کردن حاصل جمع و بردار نقلي شيفت يافته به چپ ، به دست ميآيد. هر بيت رقم نقلي همان طور که در شکل ٣ نشان داده شده است ، ورودي نقلي براي بيت پرارزش بعدي است . تابع شمارنده ٣:٢ ميتواند با استفاده از معادله زير بيان شود [٨] :
A+ B + C = S + 2.H )4(
که A،B ،C ،S و H اعداد دهدهي هستند با
که مقدار بيتي A در موقعيت وزن مربوطه است . اگرچه اکسه تفادi ه از شمارنده هاي ٣:٢ دودويي نسبتiا ساده است ، يک عيب بزرگ براي کدگذاري ٨٤٢١ -BCD دارد. همان طور که در شکل ٣ مشاهده ميشود، بردار حاصل جمع S خارج از محدوده است ازآنجاييکه يک نمايش دهدهي معتبر نيست و جمع S و H يک نتيجه دودويي را ميدهد که مغاير با نتيجه ٨٤٢١ -BCD معتبر است ؛ بنابراين تبديل به BCD نياز به مدار اضافي خواهد داشت و درنتيجه کارآمد نخواهد بود[٥].
شکل ٣. نتيجه جمع ، بردار رقم نقلي شيفت يافته به چپ
يک راه حل ميتواند استفاده از يک نمايش BCD وزن دار متفاوت در طول فرايند جمع باشد؛ يعني بيت ها به نمايش دهدهي معتبر ديگري کد ميشوند که باعث ميشود رقم هاي نقلي، زماني که يک شيفت رخ ميدهد به درستي توليد شوند. براي يافتن بهترين نمايش BCD توجه نمودن به ويژگي مهم جمع دو عدد اهميت زيادي دارد. براي اجتناب از نتيجه خارج از محدوده ، کدهاي دهدهي که مجموع وزن هاي هر ٤ بيت آن ها برابر با ٩ باشد به کار گرفته ميشوند. اين ويژگي همچنين براي جمع کننده هاي علامت دار براي پرهيز از انتشار رقم نقلي استفاده ميشود [٩[.
کدهاي BCD از قبيل ٥٢١١، ٤٣١١، ٤٢٢١ و ٣٣٢١ اين شرط را برآورده ميکنند. مزيت ديگر اين نوع کدهاي BCD اين است که همه نمايش ها خود-مکمل هستند، يعني مکمل ٩ عدد به سادگي با معکوس کردن بيتي هر يک از ٤ بيت به دست مي آيد. با استفاده از اين امر بديهي، مکمل ١٠ عدد هم به آساني به همان روش اعداد دودويي به دست مي آيد.
استفاده از يک کد خود-مکمل باعث اجتناب از وضعيت خارج از محدوده شدن که در شکل ٣ مشاهده شد، مي شود. علاوه بر اين ، از آنجاييکه براي دست يابي به حاصل جمع نهايي، مقدار H .٢ (بردار نقلي) مورد نياز است ، روش کدگذاري BCD که در آن دو برابر کردن آسان است ، مطلوب خواهد بود، زيرا در نمايش دودويي، عمليات ضرب در ٢ به سادگي با يک شيفت به چپ بيتي انجام ميشود. هرچند، هنگام استفاده از کدهاي خود-مکمل ، شيفت دادن به طور مستقيم اعمال نمي شود. با اين وجود، اگر عدد مجددا کدگذاري شود، اين عمل به روش ساده تري انجام خواهد شد[٥].
يک راه حل بالقوه براي کدگذاري مجدد رقم هاي نقلي به يک خروجي خود مکمل ، پياده سازي کد ٥٢١١ است ، همان طور که در[٤] پيشنهاد شده است . با استفاده از اين روش ، عمليات ضرب در ٢ ميتواند به سادگي با اين فرض که نتيجه در کد ٢ ٢ ٤ ١٠ -BCD است مديريت شود. براي مثال عدد ٦ يا ١٠٠١ در کد ٥٢١١ -BCD همان ١٠٠١ در کد ٢ ٢ ٤ ١٠ -BCD خواهد ماند، اما در نمايش مقدار ١٢، اگرچه اين کد استفاده نميشود، زيرا خود-مکمل نيست ، اما پرارزش ترين بيت مي تواند به ستون رقم بعدي داده شود. کد BCD نتيجه شده در ٤٢٢١ است زيرا بيت با وزن ١٠ به صورت يک ١ در مکان رقم بعدي نمايش داده ميشود، همان طور که در شکل ٤ اين قضيه نشان داده شده است .
شکل ٤. عمليات ضرب در ٢، نتيجه به صورت ٤٢٢١ -BCD
به طور خلاصه ، اگر کدگذاري ٥٢١١ -BCD به کار گرفته شود، يک رقم نقلي خروجي با وزن ١٠ ظاهر ميشود و اجازه ميدهد تا کد دهدهي به ٤٢٢١ -BCD تبديل شود که يک کد خود-مکمل است . بيت شيفت يافته به خارج ، رقم نقلي خروجي به رقم دهدهي بعدي را نمايش مي دهد. فضاي خالي که در کم ارزش ترين مکان به وجود آمده ، براي دريافت رقم نقلي ورودي از رقم قبلي در دسترس است . براي کم ارزش ترين رقم ، اين مقدار صفر فرض مي شود (شکل ٥).
اگرچه اين کدگذاري به خوبي عمل ميکند، اما يک عمليات براي تبديل ورودي شمارنده ٣:٢ به کد دهدهي مورد نظر ضروري است . با استفاده از جدول ١ ميتوان يک عدد با کد ٨٤٢١ -BCD را با استفاده از يک سطح منطقي ساده به عدد معادل در کد ٤٢٢١ -BCD تبديل کرد[٥].
