ضرب دو عدد به صورت موازی و تفاوت آن با جمع اعداد

برای جمع اعداد اگر رقمهای اعداد را از چپ به راست داشتیم می توانستیم به ترتیب با هم جمع کنیم و جواب به دست می آمد. برای ضرب دو عدد چون بیت اول عدد اول باید در همه ی بیت های عدد دوم ضرب شود و بعد به سراغ بیت دوم عدد اول برویم، نمی توانیم دو عدد را مثل هم وارد سیستم کنیم. از طرفی هر عدد را یک بار بیشتر نمی توانیم وارد کنیم، پس باید کاری کنیم که با همان یک بار عمل ضرب انجام شود. قسمت ساده ای که می دانیم چطور انجام بدهیم جمع حاصل ضرب هر بیت عدد اول در عدد دوم است. با توجه به اینکه باید بتوانیم حاصل جمع های میانی را نگه داریم و جمع کنیم تا به جواب آخر برسیم، به 2n پردازنده نیاز داریم، که از آنجایی که طول جواب از این مقدار کمتر است می توانیم هر بیت جواب را در یک پردازنده نگه داریم. بیت jام جواب از رابطه ی زیر به دست می آید:

c_j = sum_i_1_j (a_i*b_(j-i+1))+carry(j-1)

برای محاسبه ی رابطه ی بالا در مدل آرایه خطی، اولین چیزی که به ذهن می رسد این است که خود عدد a و معکوس عدد b را وارد سیستم کنیم، اما از آنجایی که نمی خواهیم اعداد ورودی را تغییر بدهیم، عدد b را از سمت دیگر وارد می کنیم و خود به خود باعث می شود ترتیب آن عکس ترتیب a باشد.

وقتی دو عدد کامل وارد پردازنده ها می شوند به صورت متوالی نوشته شده اند:

a3 a2 a1 b3 b2 b1

next step:

    a3 a2 a1

        b3 b2 b1

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

بعد از این دیگر کافی است که جمع ها را انجام بدهیم و در هر پردازنده حاصل را نگه داریم.

برای حل مشکل بیکار بودن پردازنده ها در نصف سیکل ها از یکی از دو مدل زیر می توانیم استفاده کنیم: