האצת בעיות סיפוק בוליאניות היברידיות XOR–CNF באופן נייטיבי באמצעות מחשוב בזיכרון

מדוע פתרון מהיר יותר חשוב

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

הפיכת כללים מסובכים לגורמי בנייה פשוטים יותר

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

להשיג יותר עם חלקים נדירים יותר

חוקרים אלה השוו בקפידה את התיאור ההיברידי לתיאור המסורתי על פני מספר משפחות מבחן הנלקחות מעולם הקריפטוגרפיה ומבעיה קלאסית הנקראת "פרדוקס אי-הסכמה המזערית של שוויון פריטי" (minimal disagreement parity). על ידי שיקום אוטומטי של מבנה XOR נסתר ויישום פישוטים חכמים ראשונים, הם מראים שהייצוג המעורב יכול לצמצם את מספר המשתנים עד כמה וכמה פעמים ולחתוך את מספר הכללים בערך בפקטור של ארבע עד חמש. במילים אחרות, את אותו שאלה לוגית ניתן לעתים לשאול עם הרבה פחות מרכיבים נעים כאשר מרשים ל-XOR ו-OR להתקיים יחד. בעיות קטנות יותר קלות לא רק לתוכנה, אלא גם לחומרה ייעודית שיש לה מגבלות קפדניות על כמה כללים אפשר לאחסן בו־זמנית.

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

כדי לנצל את התיאור המלוטש הזה, הצוות מעצב מאיץ ייעודי של "מחשוב בזיכרון". במקום להעביר נתונים הלוך ושוב בין מעבד לזיכרון, התקן זה מבצע את רוב החישוב במקום שבו הנתונים נמצאים, בתוך רשתות של אלמנטים אלקטרוניים זעירים הנקראים ממיריסטורים. הם מתאימים אסטרטגיית חיפוש מקומית ידועה, WalkSAT, לגרסה חדשה בשם WalkSAT-XNF המטפלת נייטיבית בכלליי XOR–OR המשולבים. כל שלב באלגוריתם — בדיקת אילו כללים נשברים, הערכת חשיבות כל משתנה, הוספת קצת רעש כדי לצאת ממצבים תקועים והיפוך המועמד הטוב ביותר — מיושם ישירות במעגלים אנלוגיים על מערכי ה-crossbar, עם מעגלי תמיכה פשוטים הבוחרים איזה משתנה להפוך הבא.

ההוכחה במעבדה ובסימולציות

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

מה משמעות הדבר למחשבים בעתיד

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

ציטוט: Im, H., Böhm, F., Pedretti, G. et al. Accelerating hybrid XOR–CNF Boolean satisfiability problems natively with in-memory computing. Nat Commun 17, 2922 (2026). https://doi.org/10.1038/s41467-026-69465-2

מילות מפתח: סיפוק בוליאני, מחשוב בזיכרון, צלחתית ממירי-זיכרון, מאיצי חומרה, קריפטוגרפיה