موضوع مقاله: ضرب کننده دادا | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # ضرب کننده دادا | مقدمه: در این روش، حاصل‌ضرب‌های جزئیِ تولیدشده در ضرب دودویی، طی چند مرحله با استفاده از تمام جمع کننده ها و نیم جمع‌کننده‌ها کاهش می‌یابند تا در نهایت تنها دو ردیف باقی بماند. | ## بخش 1: ضرب کننده دادا | ساختار کلی این ضرب‌کننده از بسیاری جهات به ضرب‌کنندهٔ والاس شباهت دارد، اما روش متفاوتِ کاهش درختی در آن باعث می‌شود تعداد گیت‌های موردنیاز—به‌ویژه در اندازه‌های بزرگ‌تر عملوند—کمتر باشد و در نتیجه سرعت اجرای مدار اندکی بهبود یابد. حاصل این مرحله، مقدار است که بر اساس وزن بیتی، در ستون‌های مربوط به خود دسته‌بندی می‌شوند. حاصل‌ضرب‌های جزئیِ به‌دست‌آمده، با استفاده از مراحل متوالیِ تمام جمع کننده ها و نیم‌ جمع‌ کننده ها کاهش می‌یابند تا در نهایت در هر ستون، بیش از دو بیت باقی نماند. دو ردیف باقی‌مانده با کمک یک جمع‌کنندهٔ معمولی ترکیب می‌شوند تا نتیجهٔ نهایی ضرب تولید شود. همانند ضرب‌کنندهٔ والاس، حاصل‌ضرب‌هایی که در مرحلهٔ نخست تولید می‌شوند هرکدام وزن بیتی متفاوتی دارند؛ این وزن‌ها نشان‌دهندهٔ جایگاه و ارزش بیت‌های ورودی در عملیات ضرب هستند. برخلاف ضرب‌کنندهٔ والاس که در هر مرحله تا حد امکان تعداد بیت‌ها را کاهش می‌دهد، ضرب‌کنندهٔ دادا با هدف کاهش تعداد گیت‌های مصرفی و بهبود تأخیر ورودی–خروجی عمل می‌کند. به همین دلیل، مرحلهٔ کاهش در ضرب‌کنندهٔ دادا از نظر سخت‌افزاری کم‌هزینه‌تر است؛ با این حال، خروجی میانی ممکن است اندکی طولانی‌تر باشد و در نتیجه برای تولید نتیجهٔ نهایی، به یک جمع‌کنندهٔ بزرگ‌تر نیاز خواهد بود. برای دستیابی به یک خروجی بهینه‌تر، روند کاهش در ضرب‌کنندهٔ دادا بر پایهٔ مجموعه‌ای از قوانین ساختاریِ دقیق‌تر—نسبت به آنچه در ضرب‌کنندهٔ والاس به‌کار می‌رود—سازمان‌دهی می‌شود. فرآیند کاهش در ضرب‌کنندهٔ دادا با تکیه بر یک توالی ارتفاع‌های بیشینه‌ کنترل می‌شود که با نمایش داده می‌شود و به‌صورت زیر تعریف می‌گردد: and , این تعریف در نهایت به دنباله‌ای با شکل کلیِ زیر منتهی می‌شود: برای آغاز فرایند، مقدار اولیهٔ به‌گونه‌ای انتخاب می‌شود که بزرگ‌ترین مقدار ممکن باشد، به شرط آن‌که برقرار باشد؛ جایی که و به‌ترتیب تعداد بیت‌های مضروب و مضرب ورودی هستند. حداقلِ این دو مقدار همان حداکثر ارتفاعی است که هر ستونِ وزن پس از مرحلهٔ نخست ضرب می‌تواند داشته باشد. در هر گام از کاهش با اندیس ، هدف الگوریتم آن است که ارتفاع هر ستون به مقداری کمتر یا مساوی کاهش یابد. برای هر یک از مراحل کاهش از تا1،ستون‌ها باید از کم‌وزن‌ترین ستون—یعنی —شروع شده و بر اساس قوانین زیر کاهش یابند: اگر ارتفاع ستون کمتر یا برابر با باشد، نیازی به کاهش ندارد و می‌توان مستقیماً به ستون بعدی، یعنی، رفت. اگر ارتفاع ستون برابر با باشد، دو بیت بالایی با استفاده از نیم‌جمع‌کننده ترکیب می‌شوند؛ بیت حاصل در پایین همان ستون قرار می‌گیرد و رقم نقلی نیز در پایین ستون بعدی، ،جای‌گذاری می‌شود. در صورتی که ارتفاع ستون بزرگ‌تر از این مقدار باشد، سه بیت بالایی با استفاده از یک تمام جمع کننده فشرده می‌شوند؛ حاصل جمع در پایین ستون و رقم نقلی در پایین ستون قرار می‌گیرد. سپس دوباره به ستون بازمی‌گردیم و این فرایند از مرحلهٔ نخست تکرار می‌شود تا ارتفاع ستون به حد مطلوب برسد. ساختار درختی دادا در یک ضرب‌کنندهٔ دودویی ۸×۸، حاصل‌ضرب‌های جزئی را می‌توان به صورت یک ماتریس در نظر گرفت که در آن هر ستون مجموعه‌ای از بیت‌ها با وزن بیتی یکسان را شامل می‌شود. | ## بخش 2: ضرب کننده دادا | در مرحلهٔ نخست، تعداد بیت‌های هر ستون از یک تا هشت متغیر است و ستون‌های میانی ارتفاع بیش‌تری دارند. در هر مرحله، ستون‌هایی که ارتفاع آن‌ها بیش‌تر از حد مجاز است، با استفاده از نیم‌جمع‌کننده‌ها و تمام‌جمع‌کننده‌ها فشرده می‌شوند تا ارتفاع ستون به مقدار مجاز برسد. ستون‌هایی که ارتفاع آن‌ها از ابتدا کمتر یا مساوی باشد، دست‌نخورده به مرحلهٔ بعد منتقل می‌شوند. به‌طور شهودی، می‌توان این فرایند را یک «درخت کاهش» دانست که در گام‌های متوالی، تعداد گره‌ها (بیت‌ها) در هر سطح را کاهش می‌دهد تا در نهایت ماتریسی با ۱۵ ستون و حداکثر دو بیت در هر ستون باقی بماند. مقایسه با ضرب‌کنندهٔ والاس معمولاً ضرب‌کننده‌های والاس و دادا به عنوان دو معماری استاندارد برای کاهش حاصل‌ضرب‌های جزئی مقایسه می‌شوند. هر دو از درختی از نیم‌جمع‌کننده‌ها و تمام‌جمع‌کننده‌ها استفاده می‌کنند، اما راهبرد کاهش در آن‌ها متفاوت است. معماری عمق کاهش (تقریباً) تعداد جمع‌کننده‌ها (نسبی) ویژگی شاخص درخت والاس کمتر بیشتر کاهش حداکثری در هر مرحله؛ تأخیر کمی کمتر در مسیر بحرانی درخت دادا کمی بیشتر کمتر کاهش کنترل‌شده؛ استفادهٔ بهینه‌تر از گیت‌ها و مساحت کمتر تراشه درخت والاس در هر مرحله، تا حد امکان بیت‌های هر ستون را با استفاده از تمام‌جمع‌کننده‌ها و نیم‌جمع‌کننده‌ها کاهش می‌دهد؛ بنابراین عمق منطق نسبتاً کم است، اما تعداد گیت‌ها و سیم‌کشی‌ها بیشتر می‌شود. در مقابل، درخت دادا با تعریف دنبالهٔ مقدار کاهش در هر مرحله را محدود می‌کند و به این ترتیب، با کمی افزایش در عمق مدار، به کاهش قابل‌توجه در تعداد گیت‌ها و مصرف توان دست می‌یابد. در طراحی‌های VLSI که مساحت و توان معیارهای مهمی هستند، این مزیت می‌تواند تعیین‌کننده باشد. هر نقطه در یک ستون نشان‌دهندهٔ یک بیت با وزن بیتی یکسان است؛ ستون‌های سمت راست بیت‌هایی با وزن کمتر را شامل می‌شوند و وزن ستون‌ها به‌تدریج در سمت چپ افزایش می‌یابد. نمونهٔ نشان‌داده‌شده در تصویر کنار، مراحل کاهش را برای ضربِ عدد ۸ در ۸ نمایش می‌دهد؛ همان مثالی که در این بخش به آن پرداخته شده است. در این مثال، مقدار آغازین انتخاب شده است، زیرا بزرگ‌ترین ارتفاعی است که هنوز از مقدار ۸ کمتر است. در مرحلهٔ مقدار مجاز حداکثر ارتفاع برابر با در نظر گرفته می‌شود: ارتفاع ستون‌های تا همگی شش بیت یا کمتر است؛ بنابراین در این مرحله نیازی به اعمال هیچ تغییری وجود ندارد. ارتفاع ستون برابر با است؛ بنابراین باید یک نیم‌جمع‌کننده بر روی آن اعمال شود تا ارتفاع ستون به شش بیت کاهش یابد و رقمِ نقلیِ حاصل به ستون بعدی، یعنی اضافه شود. ارتفاع ستون با در نظر گرفتن رقمِ نقلیِ انتقال‌یافته از ، برابر با ۹ بیت است؛ بنابراین برای کاهش آن به شش بیت، یک تمام جمع کننده و سپس یک نیم‌جمع‌کننده به‌کار گرفته می‌شود. ارتفاع ستون با احتساب دو رقم نقلی منتقل‌شده از ، به ۹ بیت می‌رسد؛ بنابراین همانند مرحلهٔ قبل، برای کاهش ارتفاع آن به شش بیت، ابتدا یک تمام جمع کننده و سپس یک نیم‌جمع‌کننده استفاده می‌شود. | ## بخش 3: ضرب کننده دادا | ارتفاع ستون با در نظر گرفتن دو رقم نقلی که از منتقل شده‌اند، برابر با ۸ بیت است؛ بنابراین با به‌کارگیری یک تمام جمع کننده، ارتفاع آن به شش بیت کاهش داده می‌شود. در مرحلهٔ ، حداکثر ارتفاع مجاز ستون‌ها برابر با در نظر گرفته می‌شود: ارتفاع ستون‌های تا همگی بیش از چهار بیت نیست؛ بنابراین در این مرحله نیازی به هیچ تغییری وجود ندارد. ارتفاع ستون برابر با است؛ بنابراین یک نیم‌جمع‌کننده روی آن اعمال می‌شود تا ارتفاع ستون به چهار بیت کاهش یابد و رقمِ نقلیِ حاصل به ستون بعدی، یعنی ، منتقل شود. ارتفاع ستون با احتساب رقمِ نقلی منتقل‌شده از به ۷ بیت می‌رسد؛ بنابراین برای کاهش ارتفاع آن به چهار بیت، ابتدا یک تمام جمع کننده و سپس یک نیم‌جمع‌کننده مورد استفاده قرار می‌گیرد. ارتفاع ستون‌های تا با در نظر گرفتن تمام رقم‌های نقلیِ مراحل قبل، برابر با ۸ بیت است؛ بنابراین برای کاهش ارتفاع هر یک از این ستون‌ها به چهار بیت، از دو تمام جمع کننده استفاده می‌شود. ارتفاع ستون با احتساب رقم‌های نقلی مرحله‌های پیشین، به ۶ بیت می‌رسد؛ بنابراین یک تمام جمع کننده به‌کار گرفته می‌شود تا ارتفاع آن به چهار بیت کاهش یابد. ارتفاع ستون‌های تا با در نظر گرفتن تمام رقم‌های نقلی، چهار بیت یا کمتر است؛ بنابراین در این مرحله نیازی به اعمال هیچ تغییری نیست. در مرحلهٔ ، حداکثر ارتفاع مجاز ستون‌ها برابر با در نظر گرفته می‌شود: ارتفاع ستون‌های تا همگی سه بیت یا کمتر هستند؛ بنابراین در این مرحله نیازی به هیچ‌گونه تغییری وجود ندارد. ارتفاع ستون برابر با است؛ بنابراین یک نیم‌جمع‌کننده روی آن اعمال می‌شود تا ارتفاع ستون به سه بیت کاهش یابد و رقمِ نقلیِ حاصل به ستون بعدی، یعنی ،منتقل شود. ارتفاع ستون‌های تا با در نظر گرفتن رقم‌های نقلی مراحل قبل، به ۵ بیت می‌رسد؛ بنابراین برای کاهش ارتفاع هر ستون به سه بیت، از یک تمام جمع کننده استفاده می‌شود. ارتفاع ستون‌های تا با احتساب رقم‌های نقلی، سه بیت یا کمتر است؛ بنابراین در این مرحله نیازی به انجام هیچ تغییری نیست. در مرحلهٔ ، حداکثر ارتفاع مجاز ستون‌ها برابر با در نظر گرفته می‌شود: ارتفاع ستون‌های تا در حد دو بیت یا کمتر است؛ بنابراین در این مرحله نیازی به اعمال هیچ تغییری وجود ندارد. ارتفاع ستون برابر با است؛ بنابراین یک نیم‌جمع‌کننده روی آن اعمال می‌شود تا ارتفاع ستون به دو بیت کاهش یابد و رقمِ نقلیِ حاصل به ستون بعدی، یعنی ، منتقل شود. ارتفاع ستون‌های تا با در نظر گرفتن رقم‌های نقلیِ مراحل قبلی، به ۴ بیت می‌رسد؛ بنابراین برای رساندن ارتفاع هر ستون به دو بیت، از یک تمام جمع کننده استفاده می‌شود. ارتفاع ستون با احتساب رقمِ نقلی منتقل‌شده از ، دو بیت است؛ بنابراین در این مرحله نیازی به هیچ تغییری وجود ندارد. | ## جمع‌بندی | علاوه بر این در پایان آخرین مرحله، ۱۵ ستون باقی می‌ماند که ارتفاع هرکدام دو بیت یا کمتر است؛ این ستون‌ها در نهایت می‌توانند مستقیماً وارد یک جمع‌کنندهٔ استاندارد شوند تا نتیجهٔ نهایی ضرب به‌دست آید.