سخت‌افزار چگونه اعداد را ضرب می‌کند: از منطق ساده تا مدارهای واقعی

چرا ضرب گران‌تر از جمع است

جمع دو عدد را در یک عبور واحد از مدار جمع‌کننده ترکیب می‌کند. ضرب اساساً متفاوت است: از نظر ریاضی، ضرب دو عدد معادل انجام یک سری جمع و شیفت بیتی است، که یعنی سخت‌افزار ضرب باید یا عملیات‌های ساده‌تر را چندین بار تکرار کند یا از مدارهای پیچیده‌تری برای انجام کار در گام‌های کمتر استفاده کند.

الگوریتم پایه ضرب

الگوریتم مفهومی که سخت‌افزار دنبال می‌کند، همان فرآیندی است که برای ضرب طولانی اعشاری آموزش داده می‌شود، اما با استفاده از ارقام باینری به‌جای اعشاری.

• هر بیت از Multiplier را یکی‌یکی بررسی کن، شروع از کم‌ارزش‌ترین بیت.
• اگر آن بیت ۱ باشد، یک کپی شیفت‌داده‌شده از Multiplicand را به یک مجموع در حال اجرا به نام Product اضافه کن.
• اگر آن بیت ۰ باشد، جمعی برای آن گام نیاز نیست، اما multiplicand همچنان به چپ شیفت داده می‌شود برای آماده‌سازی برای بیت بعدی.
• این فرآیند را برای هر بیت از multiplier تکرار کن، و نتیجه را در product جمع کن.

یک تصویرسازی ساده‌شده با استفاده از مقادیر ۴ بیتی کوچک:

Multiplicand: 0010 (2)
Multiplier:   0011 (3)

گام ۱ (بیت ۰ = ۱): Product += 0010
گام ۲ (بیت ۱ = ۱): Product += 0010 شیفت‌داده‌شده به چپ به‌اندازه ۱ (0100)
نتیجه: 0010 + 0100 = 0110 (6)

چرا نتیجه به دو برابر عرض بیتی نیاز دارد

ضرب دو عدد n بیتی می‌تواند نتیجه‌ای تولید کند که برای نمایش بدون از دست دادن اطلاعات، تا 2n بیت نیاز دارد. برای مثال، ضرب دو مقدار ۳۲ بیتی می‌تواند به یک نتیجه کامل ۶۴ بیتی نیاز داشته باشد. به همین دلیل، پردازنده‌ها یا یک رجیستر نتیجه گسترده‌تر برای ضرب تولید می‌کنند یا دستورات جداگانه‌ای برای بازیابی نیمه‌های بالایی و پایینی نتیجه ضرب به‌طور جداگانه فراهم می‌کنند.

ضرب علامت‌دار

هنگام ضرب Signed Numbers نمایش‌داده‌شده در مکمل دو، علامت نتیجه از قوانین معمول ریاضی پیروی می‌کند: ضرب دو مقدار با علامت یکسان نتیجه‌ای مثبت تولید می‌کند، در حالی که ضرب مقادیر با علامت‌های متفاوت نتیجه‌ای منفی تولید می‌کند. سخت‌افزار این را به‌درستی با کار مستقیم با نمایش مکمل دو در سراسر فرآیند ضرب مدیریت می‌کند، بدون نیاز به یک مدار کاملاً جداگانه برای مقادیر علامت‌دار.

چرا این موضوع برای کارایی نرم‌افزار اهمیت دارد

از آنجا که ضرب به گام‌های سخت‌افزاری بیشتری نسبت به جمع نیاز دارد، معمولاً روی بیشتر پردازنده‌ها عملیاتی کندتر است. این بخشی از دلیلی است که چرا کامپایلرها بهینه‌سازی‌هایی مانند جایگزینی ضرب در توان دو با یک شیفت بیتی ساده اعمال می‌کنند، و چرا کد حساس به کارایی گاهی محاسبات را طوری ساختاردهی می‌کند که تعداد عملیات‌های ضرب مورد نیاز را به حداقل برساند.