خوارزمية بووث

بووث

إذا كنا محددين بالنظر فقط الخانتين ثنائيتين فقط فإننا عندها نستطيع محاولة المطابقة مع الحالة السابقة بالنظر لحالة هاتين الخانتين الثنائيتين :

الضارب خوارزمية بووث الموضحة في المخطط التالي مع ملاحظة أن الحالة الأولى تملك أربع احتمالات : بالاعتماد على حالة الخانتين الثنائيتين ، وعدنا نفترض أن الخانتين الزوجيتين المفحوصتين تتألفان من الخانة الحالية والخانة التي على يمينها والتي كانت الخانة الحالية في الخطوة السابقة وبالتالي خطوات الخوارزمية كالتالي : 1- بالاعتماد على الخانة الآنية والسابقة قم بأحد التالي :

الآن وبعد أن شاهدنا آلية عمل خوارزمية BOOTH نحن الآن مستعدين لمعرفة سبب نجاحها في الأعداد الصحيحة الثنائية لنجعل (a) الضارب و (b) المضروب به وسوف نستخدم (ai) للإشارة إلى البت رقم (i) من (a) وباسقاط الخوارزمية السابقة على الفرضيات في مسألتنا هذه فإننا نجد : عنوان Booth

طالما أننا نعلم أن إزاحة الضارب يساراً على أنه ضرب لقوى العدد (2) فإن خوارزمية بووث يمكن أن تكتب كالتالي :

(a-1-a0)*6*2^0 (+)

(a0-a1)*6*2^1 (+)

(a1-a2)*6*2^2 (+)

(a29-a30)*6*2^30 (+)

(a30-a31)*6*2^31

في الواقع إن خوارزمية بووث تشكل جداء عبر المتمم الثنائي ب ِA&B كما هو موضح في الشكل  :

ملاحظة: إن استبدال العمليات الحسابية بعملية الإزاحة يمكن أن يحصل أيضاً في عملية الجداء بعدد ثابت ، حيث أن بعض المترجمات تستبدل عملية الجداء بعدد ثابت من خلال سلسلة من الإزاحات ، الجمع ، الطرح ولأن إزاحة عدد خانة واحدة نحو اليسار يمثل ضعفي العدد ، فإن إزاحة الخانات نحو اليسار له نفس التأثير كما لو أنه الضرب بقوى العدد (2) لذلك فإن كل مترجم سوف يستبدل كل إزاحة يسارية كجداء لقوى العدد 2

لقد مرت خوارزمية بووث أثناء تحديثها بثلاث مراحل :

• الإصدار الأول من خوارزمية القسمة وبنيتها الهاردويرية :

حيث يكون مسجل القاسم والمقسوم فرضاً وكذلك مسجل الALU ومسجل الباقي عبارة عن مسجلات بعرض (64 bit) أما مسجل الناتج فهو عبارة عن (32 bit) إن المخطط يظهر لنا البنية الهاردويرية والتي سوف نعتمدها.

• سوف نستخدم الخوارزمية في حساب قسمة (00000111)2 على (0010)2

الجدول يظهر كيفية خلق الناتج في أسفل المسجل للباقي وكيفية كون كلاهما سيزاح نحو اليسار في خطوة عملية واحدة .

• الإصدار الثاني لخوارزمية القسمة وبنيتها الهاردويرية :

مرة أخرى قام العلماء بتعديل هام على الإصدار الأول عند ملاحظة أنه دائماً يتم الاستغناء عن نصف المقسوم فماذا لو كانت لدينا معلومات هامة نريد وضعها في ذلك النصف وبالتالي دائماً لدينا المسجل للمقسوم وكذلك لل ALU مقسومات للنصف . إن إزاحة الباقي نحو اليسار بدلاً من الإزاحة للمقسوم نحو اليمين يولد نفس المجاراة ويحقق الأهداف في تبسيط البنية الهاردويرية الضرورية لل ALU والمقسوم والمخطط)يوضح البنية الهاردويرية المبسطة للإصدار الثاني من الخوارزمية .

• الإصدار الثالث والنهائي لخوارزمية القسمة :

يوضح الشكل البنية الهاردويرية لهذه الخوارزمية .

• سوف نستخدم الخوارزمية في حساب قسمة (00000111)2 على (0010)2

الجدول يظهر كيفية خلق الناتج في أسفل المسجل للباقي وكيفية كون كلاهما سيزاح نحو اليسار في خطوة عملية واحدة .

القسمة

خلاصة : من الممكن أن تكونوا قد لاحظتم يا شطار أن البنية الهاردويرية ممكن أن تستخدم من أجل كلا الضرب والقسمة . المطلب الوحيد هو مسجل خانة (64) الذي يكون بإزاحة نحو اليمين أو اليسار ، وكذلك ALU ب (32) خانة الذي يقوم الجمع والطرح فعلى سبيل المثال :MIPS تستخدم (32) خانة عليا و (32) خانة سفلية من أجل كل من الضرب والقسمة. كما يمكن أن نتوقع من الخوارزمية السابقة فإن الخانات العليا تحتوي الباقي والخانات السفلية تحتوي الناتج بعد اكتمال تعليمات القسمة للتعامل مع كل من الأعداد الصحيحة المؤشرة والأعداد غير المؤشرة فإن (MIPS) تحتوي على تعليمتين : divide(div) وكذلك divide unsigned أي (divu) أي مفسر الMIPS يسمح لتعليمات القسمة أن تحدد ثلاث مسجلات تولد التعليمات في مسجل أغراض عامة

MIPS

Mflo أو Mfhi لتوضيع النتائج المراجع:

المحاضرات التي ألقيت في جامعة حلب _سوريا من قبل الدكتور :شادي الجندي