חזור לתיקייה: תרגול

8 - פיפליין ושאלות חזרה

חיפוש בתיקיה
Ctrl K
לחץ כאן או הקש Ctrl K כדי לחפש בכל התיקיה
  • Pipeleine
  • שיטה לצינור
  • שאלות חזרה

8 - פיפליין ושאלות חזרה

00440252

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

רשימות תרגול לקריאה בשבת

פיפליין ושאלות חזרה

הופק מתוך תקיית התואר של שקד

uni-folder.vercel.app

PipeleinePipeleinePipeleine

הגדרה 1 (השהייה (LatencyLatencyLatency))

הזמן החולף מרגע התייצבות הכניסות למערכת עד לסיום ביצוע החישוב.

הגדרה 2 (ספיקה (ThroughputThroughputThroughput))

מספר התפוקות שהמערכת מייצרת ביחידת זמן.

בכל המקרים שראינו עד כה Throughput=1LatencyThroughput=\frac{1}{Latency}Throughput=Latency1​ והיום נראה כיצד ניתן לשפר את הספיקה מבלי לשפר את השהייה.

דוגמה

נניח ויש לנו מכבסה. במכבסה יש מכונת כסיבה, מייבש ועובד אשר מקפל את הכביסה.
נניח ולמכונה לוקח 303030 דק', למייבש 404040 דק' ולאיש לקפל לוקח 202020 דק'.
אם לקוח יוכל להיכנס רק כשהקודם סיים, היינו מאוד לא יעילים ⟸ היינו צריכים 181818 שעות כדי להכניס 4 אנשים.
אבל מה קורה עם המכונת כביסה לאחר שהוציאו את הכביסה מהמכונה? היא פשוט עומדת שם 606060 דק'.
נוכל ברגע שלקוח מסיים עם מכונת הכביסה להכניס את ההבא אחריו ⟸ כך, אמנם כל לקוח עדיין יבלה שעה במכבסה, אבל נוכל להכניס 4 לקוחות ב-3.53.53.5 שעות במקום 181818 שעות שזה נהדר.

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

הגדרה 3 (צינור מדרגה KKK)

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

הערה

יש למקם רגיסטר בכניסת המערכת או ביציאתה לצורך סנכרון עם מערכות אחרות.
⟸ נהוג למקם את הרגיסטר ביציאה מהמערכת.

נחשב כעת ביצועים עבור מערכת מצונררת:

  1. נזהה את היחידה בעלת ה-tpdt_{pd}tpd​ המקסימלי (כי לכל ה-FFFFFF-ים אותו מחזור שעון)
  2. נקבע את זמן המחזור המינימלי tmint_{min}tmin​ כך שמתקיים: tmin=tpCQ(FF)+tpd(CL)+tsetup(FF)t_{min}=t_{pCQ}(FF)+t_{pd}(CL)+t_{setup}(FF)tmin​=tpCQ​(FF)+tpd​(CL)+tsetup​(FF).
  3. נקבע את דרגת הצינור KKK.
  4. נקבל:
    Latency=K⋅tminThroughput=1tmin\text{Latency}=K\cdot t_{min} \qquad \qquad \text{Throughput}=\frac{1}{t_{min}}Latency=K⋅tmin​Throughput=tmin​1​
תרגיל

נדרש לבנות את המערכת המחשבת את הפונקציה:

f(x)=243x=35xf(x)=243x=3^5xf(x)=243x=35x

לצורך כך יש להשתמש ברכיב הצירופי הבא:
​8 - פיפליין ושאלות חזרה 2026-06-24 18.48.35.excalidraw.svg
א. ממשו את הפונקציה כמערכת צירופית.
ב. נתון FFFFFF עם המאפיינים: tsetup=20ns,  thold=5ns,  tpCQ(FF)=40nst_{setup}=20ns,\;t_{hold}=5ns,\;t_{pCQ}(FF)=40nstsetup​=20ns,thold​=5ns,tpCQ​(FF)=40ns בנו מערכת מצונררת המבצעת את אותו החישוב.
ג. מצאו מימוש חסכוני ברכיבים.

פתרון א':
פשוט נמקם 555 רכיבים כאלו אחד אחרי השני.

Latecny=5tpd=5⋅50ns=250ns\text{Latecny}=5t_{pd}=5\cdot 50ns=250nsLatecny=5tpd​=5⋅50ns=250ns Throughput=1250ns=4Mresultssec⁡\text{Throughput}=\frac{1}{250ns}=4M \frac{results}{\sec}Throughput=250ns1​=4Msecresults​

פתרון ב':
פה כל ה-tpdt_{pd}tpd​-ים זהים ולכן זה לא משנה איזה נבחר.
אנחנו נשים פלופ לאחר כל יציאה מרכיב. לא צריך לשים בכניסה כי שמנו ביציאה.

tmin=tsetup+tpCQ(FF)+tpd(CL)=110nst_{min}=t_{setup}+t_{pCQ}(FF)+t_{pd}(CL)=110nstmin​=tsetup​+tpCQ​(FF)+tpd​(CL)=110ns

לכן:

Latency=5tmin=550nsThroughput=1tmin=9.09Mresultssec⁡\text{Latency}=5t_{min}=550ns \qquad \qquad \text{Throughput}=\frac{1}{t_{min}}=9.09M \frac{results}{\sec}Latency=5tmin​=550nsThroughput=tmin​1​=9.09Msecresults​

פתרון ג':
​ספרתיות - תרגול פיפליין - תמונה 1.png
במחזור הראשון, S=0S=0S=0 והערך xxx נבחר.
בארבעת המחזורים הבאים S=1S=1S=1 וערך התוצאה הקודמת מועבר.
לאחר חמישה מחזורי שעון הערך במוצא ה-FFFFFF הוא 243x243x243x.
ע"י קביעת S=0S=0S=0 מוכנס ערך xxx הבא.

הערה

במעגל אמיתי נדרש גם לאיזשהו controlercontrolercontroler אשר ישלוט במתי ה-muxmuxmux 0 ומתי הוא 111.
ככל הנראה יהיו לו פחות מחמישה רכיבים ואז זה עדיין יעבוד.

tmin=tpCQ(FF)+tpd(sel)+tpd(x3)+tsetup(FF)=125nst_{min}=t_{pCQ}(FF)+t_{pd}(sel)+t_{pd}(x_{3})+t_{setup}(FF)=125nstmin​=tpCQ​(FF)+tpd​(sel)+tpd​(x3​)+tsetup​(FF)=125ns Latency=5tmin=625nsThroughput=1Latency=1.6Mresultssec⁡\text{Latency}=5t_{min}=625ns \qquad \qquad \text{Throughput}=\frac{1}{\text{Latency}}=1.6M \frac{results}{\sec}Latency=5tmin​=625nsThroughput=Latency1​=1.6Msecresults​
מסקנה

LatecnyThroughputמספר הרגיסטריםמספר הרכיבים הצירופיים2504M05מערכת לא מצונררת5509.09M55מערכת מצונרת6251.6M11:x31:SELמערכת עקיבה\begin{array}{|c|c|c|c|c|} \hline \text{Latecny} & \text{Throughput} & \R{\text{מספר הרגיסטרים}} & \R{\text{מספר הרכיבים הצירופיים}} \\ \hline 250 & 4M & 0 & 5 & \R{\text{מערכת לא מצונררת}} \\ \hline 550 & 9.09M & 5 & 5 & \R{\text{מערכת מצונרת}} \\ \hline 625 & 1.6M & 1 & 1:x3 \quad 1:SEL & \R{\text{מערכת עקיבה}} \\ \hline \end{array}Latecny250550625​Throughput4M9.09M1.6M​מספר הרגיסטרים051​מספר הרכיבים הצירופיים551:x31:SEL​מערכת לא מצונררתמערכת מצונרתמערכת עקיבה​​
תרגיל

נתונים שני רכיבים לוגיים צירופיים AAA ו-BBB.
​ספרתיות תרגול פיפליין - תמונה 2.png
לרכיב AAA יש N1N_{1}N1​ כניסות ו-N2N_{2}N2​ יציאות. לרכיב BBB יש N2N_{2}N2​ כניסות ו-N1N_{1}N1​ יציאות.
רכיב ABABAB מוגדר כשרשור של רכיב AAA לרכיב BBB כך שיציאה yiy_{i}yi​ של AAA מחוברת לכניסה xix_{i}xi​ של BBB עבור כל 1≤i≤N21\leq i\leq N_{2}1≤i≤N2​.
א. מדוע יש צורך להציב רגיסטר ביציאה של כל דרגה?
ב. כמה רגיסטרים נדרשים לצינור רכיב ABABAB על מנת להשיג ספיקה מקסימלית?
ג. מהו מספר דרגות הצינור האופטימלי(מקסימום ספיקה עם מינימום רגיסטריפ) עבור רכיב ABABAB יחיד בהנחת רגיסטרים אידיאליים?
ד. 202020 רכיבי ABABAB משורשרים זה לזה, מהו מספר דרגות הצינור האופטימלי כעת?
ה. הניחו כי tpd(A)=3t_{pd}(A)=3tpd​(A)=3 ו-tpd(B)=2t_{pd}(B)=2tpd​(B)=2. מה יהיו הספיקה וההשהייה של המערכת עם צינור אופטימלי וללא צינור. (בהנחת רגיסטרים אידיאלים)
ו. כעת נניח כי הרגיסטרים לא אידאליים tpCQ=1,tsetup=1t_{pCQ}=1,t_{setup}=1tpCQ​=1,tsetup​=1 ותנאי holdholdhold מתקיים. מהו זמן המחזור המינימלי, ההשהייה והספיקה כעת?

פתרון א':
כדי לשמור על זמן מחזור בשרשור מערכות וכדי להבטיח התייצבות של הכניסות לזמן קצר לאחר עליית השעון.

פתרון ב':
N2N_{2}N2​ - עבור על החיבורים בין המוצא של AAA לכניסה של BBB.
N1N_{1}N1​ - עבור כל המוצאים של BBB.
סה"כ N1+N2N_{1}+N_{2}N1​+N2​ רגיסטרים.

פתרון ג':
צינור בעל 2 דרגות.

פתרון ד':
222 דרגות צינור כפול 202020 רכיבים ⟸ דרגת הצינור האופטימלי היא 404040.

פתרון ה':
ללא צינור:

Latency=20(tpdA+tpdB)=100ns\text{Latency}=20(t_{pd}A+t_{pd}B)=100nsLatency=20(tpd​A+tpd​B)=100ns Throughput=1100\text{Throughput}=\frac{1}{100}Throughput=1001​

עם הצינור:
הרכיב הגרוע יקבע את זמן המחזור ולכן tmin=3t_{min}=3tmin​=3.

Latency=20(3⋅2)=120ns\text{Latency}=20(3\cdot 2)=120nsLatency=20(3⋅2)=120ns Throughput=13\text{Throughput}=\frac{1}{3}Throughput=31​

פתרון ו':

tmin=tpCQ(FF)+max⁡(tpdA+tpdB)+tsetup(FF)=5t_{min}=t_{pCQ}(FF)+\max(t_{pd}A+t_{pd}B)+t_{setup}(FF)=5tmin​=tpCQ​(FF)+max(tpd​A+tpd​B)+tsetup​(FF)=5 Latency=40tmin=200ns\text{Latency}=40t_{min}=200nsLatency=40tmin​=200ns Throughput=1tmin=15\text{Throughput}=\frac{1}{t_{min}}=\frac{1}{5}Throughput=tmin​1​=51​

שיטה לצינור

נעביר קוים כאשר אנו חוצים כל חץ באותו הכיוון ורק באותו הכיוון.
​ספרתיות תרגול פייפלין - תמונה 3.png
נשים לב כי הכחול אינו הכרחי שכן אין סיבה סתם לפגוע ב-Latency\text{Latency}Latency.

תרגיל

בצעו pipeliningpipeliningpipelining למערכת באמצעות רגיסטרים אידיאליים להשגת Throughput\text{Throughput}Throughput מקסימלי.

tpdA=10ns,tpdC=25nst_{pd}A=10ns, \quad t_{pd}C=25nstpd​A=10ns,tpd​C=25ns

​ספרתיות תרגול פייפלין - תמונה 5.png

נשים לב כי נוכל לשער את הספיקה המקסימלית:

Thptmax≤1max⁡{tpdA,tpdC}=40Mressec⁡Thpt_{max}\leq \frac{1}{\max\left\{ t_{pd}A,t_{pd}C \right\}}=40M \frac{res}{\sec}Thptmax​≤max{tpd​A,tpd​C}1​=40Msecres​

אם הגענו למספר הזה ניצחנו.

תחילה נשים רגיסטר ביציאה של CCC ולאחר מכן נחסום אותו. נרצה שכל זמן מחזור יהיה בדיוק tpdCt_{pd}Ctpd​C ולכן נדרש לדאוג לכך שכל מערך רגיסטרים שאנו מוסיפים לא יהיה רחוק מידי מהקודם.
בנוסף, אנו תמיד צריכים לוודא שהכל מסונכרן לזמני מחזור.
​ספרתיות תרגול פייפלין - תמונה 6.png
זה עובד ונבדק בתרגול(אני לא ממש יכול לכתוב את הבדיקה הזו)
לכן, נדרש 171717 רגיסטרים.

תרגיל

בצעו צנרור למערכת הבאה עם רגיסטרים אידיאליים להשגת ספיקה מקסימלית(דרישה משנית, השהייה מינימלית).
מהי דרגת הצינור? מה הספיקה מתקבלת?
המספרים בתוך העיגולים הם tpdt_{pd}tpd​ ביחידות nsnsns.
​ספרתיות תרגול פייפליין - תמונה 6.png

איך דואגים לזה שהכל מאוזן כל הזמן? נקח שתי נקודות שהן יהיו העוגנים שלנו וכל קו שאנו שמים כדי לצנרר את המערכת יתחיל בנקודה אחת ויסתיים בנקודה השנייה.
נתחיל להעביר קווים: נעביר דרך המוצא תחילה, לאחר מכן נחסום את ה-101010 באמצעות קו ביציאה שלו וקו בכניסה שלו וזה הכל כי 5+2+2=95+2+2=95+2+2=9 שזה פחות מ-101010 ולכן לא נדרש שם לעוד קו שיגרע לנו מההשהייה.
​ספרתיות תרגול פייפלין - תמונה 7.png
לכן, יש לנו 333 שלבי צינור עם ספיקה של 110ns=100Mressec⁡\frac{1}{10ns}=100M \frac{res}{\sec}10ns1​=100Msecres​.

שאלות חזרה

תרגיל (מועד א' אביב 2025 - שאלה 6)

נתונה המערכת הבאה:
​תרגול ספרתיות 29.6 - 3.png
נתונים התזמונים:

tpd(NOT)=150nstcd(NOT)=20nstpd(AND)=80nstcd(AND)=15nst_{pd}(NOT)=150ns \qquad t_{cd}(NOT)=20ns \qquad t_{pd}(AND)=80ns \qquad t_{cd}(AND)=15nstpd​(NOT)=150nstcd​(NOT)=20nstpd​(AND)=80nstcd​(AND)=15ns

עבור פולס ברוחב 475475475 ננו-שניות בכניסה AAA, מהו הרוחב המינימלי של הפולס ביציאה ZZZ?

נרצה לדעת כמה tcdt_{cd}tcd​ יש לנו במסלול הכי קצר, שכן השער ANDANDAND משתנה עם הראשון שמשתנה מ-111 ל-000.

tcdAND=15=15t_{cd}AND=15=15tcd​AND=15=15

במשך זמן זה בוודאות הערך נשאר זהה. (יכול להיות קצת יותר)
נבדוק כעת מה הזמן שלוקח עד שהערך החדש מתייצב בכניסה:

2tpdNOT+tpdAND=300+80=3802t_{pd}NOT+t_{pd}AND=300+80=3802tpd​NOT+tpd​AND=300+80=380

לוקח את משך זמן זה כדי שהערך במוצא יתייצב בוודאות. (יכול להיות קצת פחות)
לכן, הזמן שהאות ביציאה יהיה יציב הינו:

475−380+15=490−380=110ns475-380+15=490-380=110ns475−380+15=490−380=110ns

זהו רוחב הפולס המינימלי של ZZZ. כלומר, זה כמות הזמן המינימלית ב-ZZZ יהיה 111.

תרגיל (מועד ב' חורף 25-26 שאלה 6)

נתון המעגל הבא:
​תרגול ספרתיות 29.6 - 4.png
נתוני הרכיבים הינם:
​תרגול ספרתיות 29.6 - 6.png
הניחו כי הכניסות x,yx,yx,y מקיימות תנאי setup/holdsetup/holdsetup/hold. עבור אילו ערכים של tclockt_{clock}tclock​ ו-tdelayt_{delay}tdelay​ מובטחת עבודה תקינה של המעגל?
א. tclock=19ns,tdelay=0nst_{clock}=19ns,t_{delay}=0nstclock​=19ns,tdelay​=0ns
ב. tclock=19ns,tdelay=3nst_{clock}=19ns,t_{delay}=3nstclock​=19ns,tdelay​=3ns.
ג. tclock=20ns,tdelay=2nst_{clock}=20ns,t_{delay}=2nstclock​=20ns,tdelay​=2ns.
ד. tclock=23ns,tdelay=5nst_{clock}=23ns,t_{delay}=5nstclock​=23ns,tdelay​=5ns.
ה. tclock=18ns,tdelay=1nst_{clock}=18ns,t_{delay}=1nstclock​=18ns,tdelay​=1ns.

נדרש ששני התנאים ייתקימו:

tpdFF1+tpdLogic+tsetupFF2≤tclock+tdelaytcdFF1+tcdLogic≥tholdFF2+tdelay\begin{matrix} t_{pd}FF_{1}+t_{pd}Logic+t_{setup}FF_{2}\leq t_{clock}+t_{delay} \\ t_{cd}FF_{1}+t_{cd}Logic\geq t_{hold}FF_{2}+t_{delay} \end{matrix}tpd​FF1​+tpd​Logic+tsetup​FF2​≤tclock​+tdelay​tcd​FF1​+tcd​Logic≥thold​FF2​+tdelay​​

עבור החלק הראשון נדרוש:

2+6≥5+tdelay  ⟹  tdelay≤320=4+9+7≤tclock+tdelay  ⟹  20−tdelay≤tclock\begin{matrix} 2+6\geq 5+t_{delay} \implies t_{delay} \leq 3\\ 20=4+9+7\leq t_{clock}+t_{delay} \implies 20-t_{delay}\leq t_{clock} \end{matrix}2+6≥5+tdelay​⟹tdelay​≤320=4+9+7≤tclock​+tdelay​⟹20−tdelay​≤tclock​​

עבור החלק השני של המעגל נדרוש:

19=4+8+7≤tclock4+4≥5  ✓\begin{matrix} 19=4+8+7\leq t_{clock} \\ 4+4\geq 5 \;\checkmark \end{matrix}19=4+8+7≤tclock​4+4≥5✓​

כעת, נבדוק את החלק האחרון, הסיבוב:

tdelay≥thold−tcdFF−2tcdOR=117=4+6+7≤tclock−tdelay  ⟹  17+tdelay≤tclock\begin{matrix} t_{delay}\geq t_{hold}-t_{cd}FF-2t_{cd}OR=1 \\ 17=4+6+7\leq t_{clock}-t_{delay}\implies 17+t_{delay}\leq t_{clock} \end{matrix}tdelay​≥thold​−tcd​FF−2tcd​OR=117=4+6+7≤tclock​−tdelay​⟹17+tdelay​≤tclock​​

לכן, tclock≥19t_{clock}\geq 19tclock​≥19 ולכן, התשובה הנכונה היא tclock=20ns,  tdelay=2nst_{clock}=20ns,\;t_{delay}=2nstclock​=20ns,tdelay​=2ns.
(כי כאשר אנו מציבים tdelay=3t_{delay}=3tdelay​=3 במשוואה 17+tdelay≤tclock17+t_{delay}\leq t_{clock}17+tdelay​≤tclock​ נקבל כי 20≤tclock20\leq t_{clock}20≤tclock​ שזה לא תואם ל-ב')

תרגיל (מועד א' חורף 25-26 שאלה 2)

נתון הקוד הבא אשר משמש לקידוד מילים:

קידודמילה00000אירנה00111לות’ר11001כרמלה11100ראובן\begin{array}{|c|c|} \hline \R{\text{קידוד}} & \R{\text{מילה}} \\ \hline 00000 & \R{\text{אירנה}} \\ \hline 00111 & \R{\text{לות'ר}} \\ \hline 11001 & \R{\text{כרמלה}} \\ \hline 11100 & \R{\text{ראובן}} \\ \hline \end{array}קידוד00000001111100111100​מילהאירנהלות’רכרמלהראובן​​

שאולי טוען שניתן לזהות עד שתי שגיאות ללא שינוי בקוד.
הקטור טוען שהוספת סיבית זוגיות לקוד הנתון תאפשר לתקן עד שגיאה אחת.
אמציה טוען שהפעלת קוד חזרות עם r=3r=3r=3 על הקוד המקורי, יאפשר לתקן עד שתי שגיאות.

האם מישהו מהם צודק? אם כן, אילו אנשים צודקים?

עבור קוד במרחק kkk ניתן לגלות k−1k-1k−1 שגיאות ולתקן ⌊k−12⌋\left\lfloor \frac{k-1}{2} \right\rfloor⌊2k−1​⌋.

נמצא את אורך הקוד אשר הינו המרחק בין המילים 11100 ו-11001 אשר הינו 222.
לכן, כמות השגיאות שניתן לגלות הינן 2−1=12-1=12−1=1. כלומר, שאולי טועה.

סיבית זוגיות עוזרת רק אם מרחק הקוד הוא אי זוגי, מרחק הקוד הוא זוגי ולכן זה לא יעזור. לכן, הקטור טועה.

עבור קוד חזרות עם r=3r=3r=3 נקבל מרחק קוד חדש של 666 ולכן ניתן לתקן 2 שגיאות ולכן, אמציה צודק.