[24] MIPS Improved Division Circuit - MIPS ALU Design

Summary

في هذا الدرس، نتابع مناقشة الدوائر الحسابية للتقسيم، مع تحسينات تتضمن دمج القاسم في السجل المتبقي، مما يؤدي إلى تقليل حجم السجل إلى 32 بت بدلاً من 64 بت. نشرح الخطوات الآلية والعمليات الحسابية التي تتضمن التحويل والتحقق من القيمة الصحيحة أو السالبة، مع مثالاً لعملية التقسيم. نناقش أيضًا التعليمات التي تقوم بعملية التقسيم في MIPS، مع التعامل مع القيمة الصحيحة والغير صالحة للأرقام، وكيفية التعرف على العلامة السلبية للنتيجة.

Takeaways

• 😀 المحاضرة تناقش الدوائر التقسيمية وتحسيناتها.
• 🔄 في الدوائر التقليدية، يستخدم سجل الباقي 64 بتًا، لكن النصف الأيسر دائمًا فارغ.
• 🆕 تم تصميم الدوائر المحسنة لدمج سجل الباقي وسجل الناتج في سجل واحد 64 بتًا.
• 📉 تم تقليل حجم مقسم الدوائر المحسنة إلى 32 بتًا.
• 🔢 في الدوائر المحسنة، سجل الباقي يحتوي على الباقي والناتج في النصف اليمين واليسار، على التوالي.
• 🔄 عند استخدام الدوائر المحسنة، يتم تحويل القيمة المراد قسمها (الدائن) بطريقة تتضمن تنقيط اليمين.
• ➗ في الخوارزمية، يتم تقسيم الدائن على المقسم بخطوات، مع التحقق من القيمة الفعلية للباقي بعد كل خطوة.
• ✅ عند التحقق أن الباقي سلبي، يتم استعادة القيمة الأصلية للجزء اليسرى من سجل الباقي.
• 🔄 في النهاية، يتم تنقيط النصف اليسرى من سجل الباقي للوصول إلى الناتج النهائي.
• 🛑 الدوائر المحسنة لا يمكن تحويلها لعمليات أسرع مثل الدوائر الضربية، بسبب الخطوات التي تتضمن التحقق من القيمة الفعلية للباقي.
• 💡 في MIPS، يمكن استخدام أوامر خاصة لإجراء العمليات الحسابية للتقسيم، مع استخدام سجلات high و low للوصول إلى الباقي والناتج.

Q & A

ما هو الهدف الرئيسي من تحسين دائرة القسمة التي تم شرحها في المحاضرة؟

الهدف الرئيسي هو دمج سجل الحاصل مع سجل الباقي لتقليل حجم الدائرة وتحسين أدائها.

لماذا يتم دمج سجل الحاصل مع سجل الباقي في الدائرة المحسنة؟

لأن نصف السجل الذي كان يُستخدم للباقي كان يحتوي على أصفار دائمًا، ودمج السجلين يوفر مساحة ويحسن الكفاءة.

ما هو حجم سجل الباقي في الدائرة المحسنة؟

سجل الباقي في الدائرة المحسنة يكون حجمه 64 بت.

كيف يتم تقسيم سجل الباقي بعد التحسين؟

النصف الأيسر من سجل الباقي يحتوي على الباقي، بينما النصف الأيمن يحتوي على الحاصل في نهاية العملية.

ما حجم القاسم في الدائرة المحسنة؟

حجم القاسم في الدائرة المحسنة هو 32 بت.

ماذا يحدث للقاسم أثناء العملية في الدائرة المحسنة؟

يتم تقسيم القاسم إلى 32 بت، ويتم الاستغناء عن الـ 64 بت المستخدمة سابقًا.

ما هي خطوات العملية في الدائرة المحسنة؟

تشمل الخطوات نقل سجل الباقي لليسار بمقدار بت واحد، وطرح القاسم من النصف الأيسر لسجل الباقي، ثم اختبار إذا كانت النتيجة موجبة أو سالبة، واتخاذ الإجراء المناسب بناءً على ذلك.

كيف يتم التعامل مع النتيجة السالبة في الدائرة المحسنة؟

إذا كانت النتيجة سالبة، يتم استعادة القيمة الأصلية للنصف الأيسر من سجل الباقي، ثم نقل السجل لليسار وإضافة صفر في النهاية اليمنى.

ما هو الفرق بين الدائرة المحسنة والدائرة الأصلية من حيث عدد التكرارات؟

الدائرة المحسنة تتكرر 32 مرة إذا كانت MIPS Register، بينما الدائرة الأصلية كانت تتكرر N+1 مرة.

كيف يتم تحديد إشارة النتيجة النهائية في التعليمات المستخدمة للقسمة في MIPS؟

يتم تحديد إشارة النتيجة بناءً على إشارات القيم المدخلة، فإذا كانت القيم المدخلة لها نفس الإشارة تكون النتيجة موجبة، وإذا كانت مختلفة تكون النتيجة سالبة.

Outlines

00:00

😀 Introduction to Improved Division Circuits

The lecturer begins by welcoming the audience back and introducing the topic of division circuits. They explain that while the previously discussed circuit functioned, there were inefficiencies that could be improved upon. The main issue was that the 64-bit remainder register was not fully utilized, with the left half often being zeros. The solution proposed is to combine the quotient into the remainder register, effectively making it a 64-bit register that holds both the quotient and the remainder, with the left half for the remainder and the right half for the quotient. The divisor is also reduced to 32 bits, and the process involves shifting and combining operations to optimize the circuit's performance.

05:02

🔄 Detailed Explanation of Division Circuit Algorithm

This paragraph delves into the step-by-step algorithm of the improved division circuit. The process starts with shifting the remainder register to the left and then iterating through subtraction and addition with two's complement where necessary. The讲师 explains how to handle negative remainders by restoring the original value and adjusting the remainder register accordingly. The summary includes the iterative process of subtraction, addition of two's complement, and the significance of checking the most significant bit to determine if the remainder is positive or negative. Each iteration is described in detail, showcasing the shift and conditional operations involved in the division process.

10:04

🔢 Final Steps and Conclusion of Division Circuit Operation

The final paragraph discusses the concluding steps of the division circuit operation. After several iterations, the讲师 explains the process of shifting the left half of the remainder register to the right to finalize the quotient and remainder. The讲师 clarifies any confusion regarding the shifting process and emphasizes the importance of the remainder register containing both the quotient and the remainder. The讲师 also touches on the limitations of speeding up the division process, unlike multiplication, due to the need to check the sign bit after each subtraction. The paragraph concludes with a brief mention of faster dividers that use SRT division for efficiency.

15:04

📘 MIPS Division Instructions and Sign Considerations

In the last paragraph, the讲师 shifts focus to the implementation of division in MIPS architecture. They explain the use of high and low registers to store the remainder and quotient, respectively. The讲师 outlines the two types of division instructions for signed and unsigned integers and simplifies the process of determining the sign of the result based on the input signs. The讲师 also mentions the absence of overflow in division and the use of move high and move low instructions to access the values in the high and low registers. The video concludes with a thank you to the viewers and an invitation to the next video.

Keywords

💡مقسم

المقسم هو الرقم الذي يُستخدم في العملية الحسابية للتقسيم، ويتم استكشاف في النص كيف يمكن تحسين كircuits التقسيم لتقليل حجم المقسم والتقليل من عدد العمليات. في النص، يُذكر أن المقسم في كircuits التقسيم قد يكون 64 بت ولكن يُقترح تقليل حجمه إلى 32 بت.

💡سجل الباقي

سجل الباقي هو جزء من كircuits التقسيم ويحتوي على القيمة التي تبقى بعد التقسيم. في النص يُناقش كيف يمكن تحسين كircuits التقسيم من خلال دمج سجل الباقي مع سجل الاقتباس لتحسين الأداء.

💡سجل الاقتباس

سجل الاقتباس هو السجل الذي يحتوي على النتيجة النهائية من العملية الحسابية للتقسيم. في النص يُناقش كيف يمكن دمج سجل الاقتباس مع سجل الباقي لتحسين كircuits التقسيم.

💡التقسيم الحسابي

التقسيم الحسابي هو العملية التي تتضمن تقسيم رقم على آخر. في النص يُناقش الخطوات التي تتم خلال كircuits التقسيم، مثل تحويل الباقي إلى إقتباس وتحويل المقسوم إلى مقسوم.

💡تحويل اثنين

تحويل اثنين هو العملية التي تُستخدم لتحويل رقم من شكل عكس اثنين إلى شكل عادي، وهي مفيدة في كircuits التقسيم لعمليات الطرح. في النص يُستخدم مثال التقسيم 6 / 2 لتوضيح العملية.

💡التحول الصحيح

التحول الصحيح هو عملية نقل البيانات من مكان إلى آخر، وفي النص يُستخدم للشرح كيف تُغير قيمة سجل الباقي في كircuits التقسيم.

💡التحقق الرقمي

التحقق الرقمي هو الخطوة التي تُستخدم لمعرفة ما إذا كانت القيمة الناتجة من العملية الحسابية موجبة أم سالبة. في النص يُستخدم للتحقق إذا كان الباقي سالب قبل التحويل إلى إقتباس.

💡الرمز ال Dungs

الرمز ال Dungs هو الطريقة التي يُستخدمها الكمبيوتر لتمثيل الأرقام السالبة. في النص يُناقش كيف يُستخدم في كircuits التقسيم لعمليات الطرح والتحقق.

💡معالج العمليات الحسابية MIPS

MIPS هو معالج العمليات الحسابية الذي يُستخدم في البرمجيات لمعالجة العمليات الحسابية. في النص يُناقش كيفية استخدام كircuits التقسيم مع معالج MIPS.

💡تعليمات التقسيم

تعليمات التقسيم هي الأوامر التي تُستخدم لتنفيذ العمليات الحسابية للتقسيم في معالج العمليات الحسابية. في النص يُناقش كيفية تنفيذ التقسيم في معالج MIPS باستخدام سجل الأعلى وسجل الأدنى.

💡التجاوز

التجاوز هو الحالة التي تحدث عندما لا يمكن لقيمة معينة أن تُمثل في عدد بит معين. في النص يُذكر أن التجاوز لا يُحدث في كircuits التقسيم لأن القيمة الناتجة دائمًا أقل من القيمة الإدخالة.

Highlights

Introduction to division circuits and hardware, exploring improvements over previous designs.

Discussion on the inefficiency of using a 64-bit remainder register when only the left half is utilized.

Proposing an improved division circuit that combines the quotient into the remainder register, reducing the register size to 32 bits.

Explanation of how the left half of the new register will be the remainder and the right half the quotient.

Introduction of a 32-bit divisor, halving the size of the divisor from previous designs.

Description of the initial setup where the remainder register is initialized with the dividend.

Illustration of the division process using an example of dividing six by two, highlighting the shift operations involved.

Introduction of the improved circuit with a single 64-bit register for quotient and remainder, and a 32-bit divisor.

Algorithm explanation for the improved division circuit, detailing the steps for dividing seven by two.

Step-by-step demonstration of the division algorithm, including shifting and subtraction operations.

Discussion on the handling of negative remainders and the process of restoring the original value.

Explanation of the iterative process and how it differs from the continuous operation of the original circuit.

Final result of the division example, showing the quotient and remainder in the remainder register.

Comparison of the improved division circuit with the original in terms of hardware consumption and speed.

Introduction to faster division methods like SRT division, which predicts the sign of the remainder.

Discussion on the simplicity of determining the sign of the division result in MIPS and the absence of overflow issues.

Explanation of how to use high and low registers in MIPS for division instructions and accessing their values.

Conclusion and summary of the division circuit improvements and their implications in hardware design.

Transcripts

hello guys welcome back to our lectures

in this lecture we're going to continue

to talk about division circuits division

hardware

so basically this is you know the

circuit that we explored the last time

it was you know doing the job

but there are some remarks and this

remarks about the operation of the

operation of this circuit will it will

lead us to the improved version of the

division circuit

so

the remainder register was 64 bits and

all the time whenever you use this

circuit you're gonna end up with

the left half of that register all zeros

and the divisor circuit will be is also

64 bit because we do shift right and

again the left half of this will be all

zeros all the time

i mean they are not used

and we should have a quotient register

of 32-bit to hold the is the question

for us

so the main idea or the main motivation

is basically to combine

the quotient into

the remainder register

so it now shouldn't be called the

remainder anymore although they call it

remainder because now this register this

64 register will contain the quotient

and is a remainder at the same time

so the left half will be the remainder

the right half at the end of the

operation will be the quotient right as

we're going to see in the improved

circuit

the divisor will be

32 bits so we're going to cut it in half

and we're going to initialize the

remainder register with the dividend and

it's dividend 32 bits so now

this

other circuit takes the 32 bits from the

remainder register which is the part is

in which the the dividend is located and

now is a divisor 32 bits so we don't

need 64 bit either we need only 32 bits

so

if we do this if we design it correctly

we're going to discard as a quotient

register because we're going to combine

it in the remainder register

the remainder register will continue at

the end our remainder and our quotient

all in the same place

and the divisor will be 32 bits

the other will be 32 bits

but we should know that anything of

shifting right is a

the divisor as we do

previously we're gonna shift left

as a remainder

let's let's have an insight about this

so when we do for example six divided by

two

we start like this does one zero goes

into one we said no

then we said does one zero goes into one

one we said yes

this is basically a shift operation so

here is the six

and here is the two

it doesn't work like this so we're gonna

shift it so it become like this so yes

one zero goes into one one

and this is shift

right

but we can do exactly the same if we

shift the lift the dividend so let's

write it again like this here is one

zero we're gonna shift

lift the dividend so it becomes

like this

and yes one zero guys can go into one

one

okay

so that's basically a highlight of what

we should do in order to have a better

circuit here is the better circuit where

is the improved circuit

one 64 register that called the quotient

and the remainder at the same time

the divisor is 32 bits

in the beginning

the remainder register will have

part zero

the bar two is a dividend

this part is 32 bits so we have here 32

bits 32 bits so that the arithmetic

operation is the other is only 32 bit

other

so we we we decreased the half of its

size which is good

now let's see an example of how this

works

here is the algorithm

of that

circuit here is a dividend

in this case seven so we're gonna divide

the seven by two

here is the divisor two which should

give us a quotient

of three and a reminder remainder of one

so let's go step by step with this

you know uh algorithm this algorithm

will repeat for four times in that case

because we are dealing with four bits if

it's a mips register it will be 32 times

so it's different from you know the is

the original circuit which is

continuous for n plus one times

so we should stop iterating after after

the fourth iteration

so the first system is to shift the

remainder register left by one bit

so it will become like this

then we go into the iteration

we subtract the divisor register from

the left half of the remainder register

here is the left half of the remainder

register

and here is the divisor

of course again we don't do subtraction

but we do the addition with the two's

complement so what is the twos

complement of

this value zero zero one zero

we convert it

then we add one one plus one is zero

we have a carry of one one plus one is

one plus zero is one is in one one

so basically we're gonna add zero zero

zero zero with one one one zero

which will give us one one one

zero so the left half here will be one

one one zero

and the right half will be the same

then we test this arima as a remainder

for the left is most significant if it's

a zero or or if it's positive or

negative

so to do this we check the most

significant bit which is one in that

case and we know that if it's one

so it's then it's uh it's a negative

like for example here's the complement

you see it's it's it's a negative here

so it's one here

so if it's uh less than zero if it's a

negative we do

that box here that box contains two

steps the first step is to restore

the original value of the device of the

left half of course because the right

half doesn't change

so it should go back to its original

value which is 0 0 0

0 1 1 1 0.

and then we also shift the remainder

register to the left

setting its right most bit or the least

significant bit to zero

so second step

will make

this register looks like this

okay so this value here will be in that

place

so it's two step in one in one in in one

step

so here is the subtraction

and here is you know the branch after

the check

that's one iteration

so this is iteration one

we still less than four so we're gonna

go back

again subtract the divisor from

you know left half of the remainder

here is the left half of the remainder

here is a divisor

but here is that

the two's complement of the device

you don't need to do it again you're

going to use it all the time and we're

gonna add

one plus zero is one

so

that's basically the new

remainder register

we check the remainder if it's positive

or negative it's a negative because the

most significant bit is one

that mean we should restore

we should lift the shift left and about

zero

restores that means we're gonna get back

the same value which is zero zero zero

one one one zero zero then we shift uh

left so we're going to add up

another zero here

so that's will be the values that we're

gonna

use and that is the second iteration

still we are not four so we go back we

subtract

so zero zero one one we're gonna add up

to one one one zero one plus zero is one

one plus one is zero we have a carry of

one

one uh zero we have a carry of one zero

we have a carrier one this will be

discarded and that's the new

left half of the remainder register

we tested the remainder now it's the

positive so it's most of so we go in

that direction

to do that

what's it gonna do

we will not restore

okay we're gonna keep the value of the

remainder as it is but

we're gonna

shift the remainder now

to the left but setting the right the

most bit to one

so we're gonna have something like this

that's the third iteration

we still need four so we go back

subtract divisor from the you know left

half of the remainder

0 0 1 1 plus 1 1

that was complement of the divisor one

plus zero is one one plus one is zero we

have a carry of one one plus one zero we

have a carry of one one plus one zero we

have a carry of one

that's the new

remainder

we check the remainder the remainder is

positive we go in that location here

we shift the left

the remainder and the boot one so this

will be one one

and that's the fourth iteration and the

last one

so we should go out now and do this step

this is the system is not done

we should do something here we should

shift the left

we should shift left half of the

remainder right

one bit

i know it's confusing so

we're gonna shift the left let's write

it in that way shift the left

who is going to be shifty lifted

the right half

i'm sorry we should i'm sorry we should

shift

right

the left half

of

the remainder so shift right i'm gonna

write it here

shift right

the uh

left half

of the remainder so

this part this right half will stay the

same

but this will be shift uh right so shift

right means that direction so that means

it will be zero zero zero one

and we're done there

so and we know that the remainder

register should contain both the

question and the remainder yes

this is the quotient

the right half

and the left half is the remainder and

we know we were expecting one in the

remainder that's correct we were

expecting three in the remainder that's

also correct

it is guys all the you know the in more

details

you know but in the form of a table

that's exactly the same solution that we

just did

using you know is a bin

but you know just to type it here with

more details about what happens in each

step

if you are confused of the use of you

know the marker

after we did the is a division they

improved division circuit in the

multiplication lectures

we

showed that we can do

you know

we can exhibit we can consume more

hardware and do faster the faster

multiplication

okay

but

unfortunately this is not the case here

we cannot do this this with with the

division and the problem is basically

lies

in that part here

okay

because

if the the if the remainder was less

than zero we should undo

the value of you know uh

remainder should restore the original

value before the subtraction that's the

problem so we can to do faster we should

we should do step and wait until we

check the

is the sign sign bit we check if it's

multiple negative

fortunately there are some faster

dividers that use some sort of division

called srt division

in which it predicts basically the sign

is the sign is the same value

you know off is a remainder

but still it's not so

fast like

what we did with the multiplication

finally how to do uh division the

instructions that do the division in

mips

uh first of all we still gonna use the

high and low registers like just like

the the multiplication but now the high

register will contain the remainder and

the low register will contain the

quotient

we have two instructions

that have an instruction for signed

integers

and if unsigned for unsigned integers

luckily for the division here

it's really simple to detect what will

be the sign of the result basically if

if both are positive the output will be

positive if both are negative the output

would be positive

but if it's like xor if they have

different

signs in the output would be negative

so

like a divided by two this is positive

four

minus 8 divided by minus 2 this is also

goes to 4

so

minus 8 divided by 2 is minus 4

and a divided by -2 is basically minus

4. so if they have the same

sign

they are to be positive if they have

different signs it would be negative

so it's easy to do here

and also we don't have overflow

that's also very good

because we know that which would be all

the time less than the input like for er

you know

at least the maximum the input

and to use the high and low register

values we use again

move high byte and move low

move high and move low

in instructions to access this high and

low registers

that's it guys for the division thank

you very much for watching and see you

in the next video bye