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

מדוע מסלולים ושבבים חכמים חשובים

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

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

בעיית סוכן הנוסע שואלת שאלה פשוטה: נתונה רשימת ערים והמרחקים ביניהן, מהו הסיור הקצר ביותר שמבקר בכל עיר בדיוק פעם אחת וחוזר לנקודת ההתחלה? הבעיה היא שמספר הסיורים האפשריים מתפוצץ ככל שמוסיפים ערים, ולכן בדיקה של כל האפשרויות בלתי מעשית. במקום זאת, גישות מודרניות מחפשות מסלולים טובים מאוד, אם לא מושלמים. גישה מבטיחה מחקה כיצד רשת של מגנטים זעירים, מודל Ising, יכולה להתייצב למצב אנרגיה נמוכה שמייצג פתרון טוב. באמצעות מתן אפשרות לרשת "לרטוט" על ידי שינויים אקראיים שמרגיעים בהדרגה, המערכת נמלטת מבחירות מקומיות רעות ומוצאת מסלולים טובים יותר.

הפיכת שבב זיכרון לפותר בעיות

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

פיצול מפות גדולות לשכונות קטנות

אחד המכשולים העיקריים בשימוש בפותרים בסגנון Ising על משימות תכנון מסלולים גדולות הוא כמות הנתונים הנדרשת: ייצוג מפורט של סיור של 96 ערים היה דורש בדרך כלל רשת עצומה של חיבורים וזיכרון. כדי להימנע מכך, החוקרים מקבצים ערים סמוכות לאשכולות קטנים ואז מארגנים את האשכולות ברמות היררכיות. ברמה העליונה השבב פותר את סדר האשכולות; ברמה הבאה הוא מחדד את סדר הערים בתוך כל אשכול; וכן הלאה. גישה שלב-אחרי-שלב זו מקטינה במידה דרמטית את כמות הזיכרון והחיבורים הנדרשים, מורידה את מורכבות החומרה מגדילה בחזקת ארבע של מספר הערים למה שגדל רק בריבוע, ואז דוחסת עוד את המרחקים המאוחסנים על ידי אריזה צמודה של רק אלה שנדרשים באמת.

כיצד השבב מעדכן הרבה בחירות בבת אחת

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

ממצב שבב במעבדה למסלולים בקנה מידה גדול

השבב הניסיוני מכיל זיכרון מיוחד צנוע של 6 קילוביטים אך כבר מסוגל לפתור מקרים של בעיית סוכן הנוסע עם 96 ערים בכ־620 מיקרו־שניות ובצריכה של פחות ממיקרו־ג'ול אנרגיה. בהשוואה לחומרה קודמת שתוכננה לאותה משימה, הוא משיג שיפורים של עד מאות פעמים בכמות הזיכרון הדרושה ביחס לגודל הבעיה. סימולציות גם מראות שעל ידי הצבה של בלוקים רבים כאלה זה לצד זה, אותו עיצוב יכול לגדול לבעיות עם אלפי ערים תוך שמירה על הגדלת חומרה כמעט לינארית. עבור הקורא שאינו מומחה, המסקנה העיקרית היא שעל ידי עיצוב מחדש של שבב זיכרון מוכר לפותר פעיל — ועל ידי הפיכת ליקויי הייצור הבלתי נמנעים למאפיין שימושי — עבודה זו מצביעה על חומרה קטנה, מהירה וחסכונית באנרגיה שיכולה לסייע בתכנון מסלולים ולוחות זמנים מורכבים בזמן אמת.

ציטוט: Kong, Y., Lu, A., Liu, H. et al. A compact digital compute-in-memory Ising annealer with probabilistic SRAM bit in 28 nm for travelling salesman problem. npj Unconv. Comput. 3, 15 (2026). https://doi.org/10.1038/s44335-026-00060-w

מילות מפתח: בעיית סוכן הנוסע, אִין-אֵיזִינג (Ising) אנילר, חישוב-בזיכרון, חומרת SRAM, אופטימיזציה קומבינטורית