2.0 - תיאור היחידה האריתמטית(המכפל)

אנו מחלקים את הביטים לקבוצות ומבצעים כפל כמו בבסיס $10$ כך שמתקיים:

(a+b+c+d)(x+y)=ax+bx+cx+dx+ay+by+cy+dy

את המספר $b$ נחלק לשתי קבוצות של $16$ בטים ואת המספר $a$ נחלק לארבע קבוצות של $8$ ביטים.
לאחר שמתבצע כפל של קבוצה מסויימת, המכפלה נכנסת לקופסה השחורה של המכפיל $16\times 8$ ויוצאת אל המזיזים( $shifters$ ) אשר מזיזים בהתאם למיקום של המכפלה, אם נניח מכפילים את $8$ הביטים הראשונים של $a$ עם $16$ הביטים הראשונים של $b$ אז לא צריך הזזה בכלל, אך אם מכפילים את $16$ הביטים הראשונים של $b$ עם $8$ הביטים שנמצאים אחרי $16$ הביטים הראשונים ב- $a$ (כלומר, הביטים $16:24$ ) אז אנו צריכים להשתמש ב- $shifter16$ .
לאחר שאנו בוחרים את המיקום לביטים שהתקבלו, אנו מחברים אותם עם הקודמים באמצעות המחבר של $64$ ביטים ואז התוצאה נשמרת ברגיסטר.

2.1 - מכונת מצבים $Mealy$

נגדיר:

\star = \left.\begin{matrix} start=\varnothing \\ clk=\varnothing\\ rst=1 \end{matrix} \middle/ \begin{align*} & busy=0,\; a\_sel=\varnothing,\; b\_sel=\varnothing, \\ & shift\_{sel}=\varnothing,\; upd\_{prod}=\varnothing, \\ & clr\_{prod}=1 \end{align*}\right.

ואז נסתכל על מכונת המצבים הבאה, כאשר בכל מצב, אם $clk=0$ המצב או הקלט לא משתנה:
סימולציה 2 - יש לי מכונה.png

2.2 - שינוי למכונת המצבים

סימולציה 2 - יש לי מכונה 2.png

2.3 - מימוש בקוד

אם נכתוב תוכנה שכזו במחשב נדרש להרבה פחות מחשבה שכן לא נצטרך לדאוג לחוטים ולמכונת מצבים ונוכל לשלוט בהכל עם לולאות $for$ פשוטות יחסית.
הנה האלגוריתם ב- $pesudo\;code$ :

Algorithm 1 8Nx8N Multiplier

Input: 2, 8N bit unsigned integers: a, b

Output: 1 8N bit unsigned integer that represents a*b

1: $sum \gets 0$

2:for $i=0$ to $\frac{N}{2}-1$ do

3:for $j=0$ to $N-1$ do

4: $current \gets a{\Large [} 8 \cdot j \;\;{\Large :}\;\; 8\cdot(j+1) {\Large]} \cdot b{\Large [}16\cdot i\;\;{\Large :}\;\;16\cdot (i+1){\Large ]}$ // Uses the 16x8 Multiplier given for the $\cdot$ .

5: $sum \gets sum + current \cdot2^{8(2i+j)}$

6:end for

7:end for

מה שאנו עושים מאוד דומה לאיך שהמערכת עובדת בחומרה, אנו מחלקים את המספרים שלנו ל- $8$ ו- $16$ ביטים ואז כופלים כל אחד מהם בכל אחד אחר באמצעות המעבד שיכול להכפיל(ראו את השורה עם ההערה מימין)
לאחר מכן, אנו מחברים לסכום את המספר החדש שלנו ומזיזים אותו את כמות הביטים הרצויה באינטרבלים של $8$ או $16$ בהתאם לקבוצה שבחרנו ב- $a$ וב- $b$ . (להסבר מפורט יותר ראו את סעיף 2.0 וההסבר על ה- $shifter$ -ים)

נשים לב כי אנו מבצעים $N$ הכפלות, $\frac{N}{2}$ פעמים ולכן, יש סך הכל, $\frac{N^2}{2}$ הכפלות ולכן, הסיבוכיות הזמן הינה $\Theta(N^2)$ .

2.4 - כתיבת קוד אסמבלי

יש $10$ פקודות על מנת לבצע את אלגוריתם הכפל, לכן, ישנם $11$ מחזורי שעון מהכנסת המספרים עד קבלת המכפלה.

סימולציות

סימולציה עבור המערכת הרגילה

digitalSystemsAndComputerArcitucture-Sim2-SystemVerilogRun-1.png

סימולציה עבור המערכת המהירה

סימולציה 2 - תמונת גלים 1.png

2.0 - תיאור היחידה האריתמטית(המכפל)

אנו מחלקים את הביטים לקבוצות ומבצעים כפל כמו בבסיס

10

כך שמתקיים:

(a+b+c+d)(x+y)=ax+bx+cx+dx+ay+by+cy+dy

את המספר

b

נחלק לשתי קבוצות של

16

בטים ואת המספר

a

נחלק לארבע קבוצות של

8

ביטים.
לאחר שמתבצע כפל של קבוצה מסויימת, המכפלה נכנסת לקופסה השחורה של המכפיל

16\times 8

ויוצאת אל המזיזים(

shifters

) אשר מזיזים בהתאם למיקום של המכפלה, אם נניח מכפילים את

8

הביטים הראשונים של

a

עם

16

הביטים הראשונים של

b

אז לא צריך הזזה בכלל, אך אם מכפילים את

16

הביטים הראשונים של

b

עם

8

הביטים שנמצאים אחרי

16

הביטים הראשונים ב-

a

(כלומר, הביטים

16:24

) אז אנו צריכים להשתמש ב-

shifter16

.
לאחר שאנו בוחרים את המיקום לביטים שהתקבלו, אנו מחברים אותם עם הקודמים באמצעות המחבר של

64

ביטים ואז התוצאה נשמרת ברגיסטר.

2.1 - מכונת מצבים

Mealy

נגדיר:

\star = \left.\begin{matrix} start=\varnothing \\ clk=\varnothing\\ rst=1 \end{matrix} \middle/ \begin{align*} & busy=0,\; a\_sel=\varnothing,\; b\_sel=\varnothing, \\ & shift\_{sel}=\varnothing,\; upd\_{prod}=\varnothing, \\ & clr\_{prod}=1 \end{align*}\right.

ואז נסתכל על מכונת המצבים הבאה, כאשר בכל מצב, אם

clk=0

המצב או הקלט לא משתנה:
סימולציה 2 - יש לי מכונה.png

2.3 - מימוש בקוד

אם נכתוב תוכנה שכזו במחשב נדרש להרבה פחות מחשבה שכן לא נצטרך לדאוג לחוטים ולמכונת מצבים ונוכל לשלוט בהכל עם לולאות

for

פשוטות יחסית.
הנה האלגוריתם ב-

pesudo\;code

Algorithm 1 8Nx8N Multiplier

Input: 2, 8N bit unsigned integers: a, b

Output: 1 8N bit unsigned integer that represents a*b

1: $sum \gets 0$

2:for $i=0$ to $\frac{N}{2}-1$ do

3:for $j=0$ to $N-1$ do

5: $sum \gets sum + current \cdot2^{8(2i+j)}$

6:end for

7:end for

מה שאנו עושים מאוד דומה לאיך שהמערכת עובדת בחומרה, אנו מחלקים את המספרים שלנו ל-

8

ו-

16

ביטים ואז כופלים כל אחד מהם בכל אחד אחר באמצעות המעבד שיכול להכפיל(ראו את השורה עם ההערה מימין)
לאחר מכן, אנו מחברים לסכום את המספר החדש שלנו ומזיזים אותו את כמות הביטים הרצויה באינטרבלים של

8

או

16

בהתאם לקבוצה שבחרנו ב-

a

וב-

b

. (להסבר מפורט יותר ראו את סעיף 2.0 וההסבר על ה-

shifter

-ים)

נשים לב כי אנו מבצעים

N

הכפלות,

\frac{N}{2}

פעמים ולכן, יש סך הכל,

\frac{N^2}{2}

הכפלות ולכן, הסיבוכיות הזמן הינה

\Theta(N^2)

חלק יבש

מערכות ספרתיות ומבנה המחשב

חלק יבש

חלק יבש

מערכות ספרתיות ומבנה המחשב

חלק יבש

2.0 - תיאור היחידה האריתמטית(המכפל)

2.1 - מכונת מצבים $Mealy$

2.2 - שינוי למכונת המצבים

2.3 - מימוש בקוד

2.4 - כתיבת קוד אסמבלי

סימולציות

סימולציה עבור המערכת הרגילה

סימולציה עבור המערכת המהירה

2.0 - תיאור היחידה האריתמטית(המכפל)

2.1 - מכונת מצבים $Mealy$

2.2 - שינוי למכונת המצבים

2.3 - מימוש בקוד

2.4 - כתיבת קוד אסמבלי

סימולציות

סימולציה עבור המערכת הרגילה

סימולציה עבור המערכת המהירה

מערכות ספרתיות ומבנה המחשב

חלק יבש

מערכות ספרתיות ומבנה המחשב

חלק יבש

2.0 - תיאור היחידה האריתמטית(המכפל)

2.1 - מכונת מצבים MealyMealyMealy

2.2 - שינוי למכונת המצבים

2.3 - מימוש בקוד

2.4 - כתיבת קוד אסמבלי

סימולציות

סימולציה עבור המערכת הרגילה

סימולציה עבור המערכת המהירה

2.0 - תיאור היחידה האריתמטית(המכפל)

2.1 - מכונת מצבים MealyMealyMealy

2.2 - שינוי למכונת המצבים

2.3 - מימוש בקוד

2.4 - כתיבת קוד אסמבלי

סימולציות

סימולציה עבור המערכת הרגילה

סימולציה עבור המערכת המהירה

2.1 - מכונת מצבים $Mealy$

2.1 - מכונת מצבים $Mealy$