Design of a Modular Hard-Problems Solver Hardware Accelerator Utilizing Unique Signal Propagation and Parallelism

הרקע לפרויקט:

קיימות מגוון אפליקציות (חיפוש, תקשורת, אופטימיזציה, קריפטוגראפיה) שדורשות פתרון בעיות NP קשות, ופתרונן באופן יעיל (כמה שניתן) מהווה אתגר. כיום, פתרונן נעשה ע"י אלגוריתמים שונים אשר מנסים לשפר את זמן הריצה ולרוב נתקלים בטריידאוף חסמי זמן-ריצה\זכרון כאשר הפתרון מסתמך על זכרון זמני ומכונת מצבים. בסופו של יום, פתרונות אשר משאירים את זמן הפתרון אקספוננציאלי. במהלך מחקר בנושא התגלה מבנה חומרתי שמאפשר בעזרת חלחול אותות דרכו לפלוט את פתרון הבעיה בצורה ישירה לעיתים ללא זכרון כלל, שכן הפתרון כבר ברמת החומרה והאותות והבעיה מומרת לבעיית שטח (עם מגבלות מסוימות). המאיץ עשוי להביא למהפכה בזמני חישוב של בעיות קשות להן יש שימוש בתחומים רבים נוספים, עבור סטים של פרמטרים פרקטיים ובעלי ישימות.

מטרת הפרויקט:

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

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

תכולת הפרויקט:

הפרויקט כולל מספר שלבים:
1. לימוד רקע תיאורטי על בעיות לדוגמא שהמאיץ פותר, ביצועי דרכי הפתרון בתוכנה הנוכחיים לשם השוואה עתידית והכרת תכנון המעגל המוצע.
2. סינטזה על FPGA, כתיבת קוד ורילוג (בהנחייה).
3. ניתוח ביצועי המאיץ והשוואה לפתירה בתכנה.

קורסי קדם:

תכן לוגי, DDP (אך לא חובה כמצוין מטה)

דרישות נוספות:

- יתרון: עקרונות של תכנון מערכות דיגיטליות או בעלי רקע בתכנות VERILOG. (במידה ואין, ניתן ללמוד עצמאית מראש או גם במהלך הסמסטר הראשון (חומר הרצאות מלא יינתן ע"י המנחים וכמובן הכוונה והדרכה) VERILOG בסיסי ילמד בקורס מעגלי ומערכות VLSI דיגיטליים, קורס חובה למסלול ננו בסמסטר א')-

מקורות:

1. Aluf-Medina, Michelle & Korten, Till & Raviv, Avraham & Nicolau, Dan & Kugler, Hillel. (2021). Formal Semantics and Verification of Network-Based Biocomputation Circuits. 10.1007/978-3-030-67067-2_21.
2. Korten, Till & Diez, Stefan & Linke, Heiner & Nicolau, Dan & Kugler, Hillel. (2021). Design of network-based biocomputation circuits for the exact cover problem. New Journal of Physics. 23. 085004. 10.1088/1367-2630/ac175d.
3. Horowitz, Ellis & Sahni, Sartaj. (1974). Sahni, S.: Computing partitions with applications to the knapsack problem. Journal of the ACM 21, 277-292. J. ACM. 21. 277-292. 10.1145/321812.321823.