הכלכלן שנאלץ להמציא מחדש את מדעי המחשב ומהנדסי החשמל שהאירו את אמריקה

המוטיבציה

אחד החלוצים בחשיבה על מטריצות דלילות היה הכלכלן הארי מרקוביץ', שלימים זכה בפרס בנק שוודיה למדעי הכלכלה לזכרו של אלפרד נובל ב-1990. בשנת 1957, בזמן שעבד במכון המחקר RAND, הוא ניסה להריץ מודלים מתמטיים של תכנון לינארי כדי להוכיח את תיאוריית תיקי ההשקעות שלו. המחשבים של אותה תקופה, שפעלו עם כרטיסי ניקוב, פשוט קרסו ולא הצליחו להכיל את מטריצות הענק הנדרשות.

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

בעיה דומה הופיעה אצל מהנדסי חשמל בארה"ב בשנות ה-60. הם נדרשו לחשב התפלגות זרמים ברשתות חשמל לאומיות עצומות. מהנדסים כמו ביל טיני וחבריו הבינו שברשת החשמל, כל עמוד או תחנת כוח מחוברים פיזית רק לעוד 2-4 צמתים סמוכים.

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

אז מה זה CSR / CRS ?

מבנה הנתונים CRS, שמכונה גם CSR - Compressed Sparse Row, הוא גישה חכמה וחסכונית לאחסון של מטריצות דלילות בזיכרון המחשב. מטריצה דלילה היא מטריצה שבה הרוב המוחלט של התאים מכילים את הערך אפס.

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

דמיינו גיליון נתונים ענק עם מיליון שורות ומיליון עמודות, אבל רק ב-50 תאים מפוזרים יש מספרים ממשיים. במקום לשמור טבלה שלמה עם טריליון תאים, עדיף פשוט להכין רשימה שאומרת: בשורה 5, עמודה 12, נמצא המספר 8.

מבנה הנתונים CRS לוקח את הרעיון הזה ומייעל אותו אפילו יותר, כדי לא לכתוב מחדש את מספר השורה עבור כל תא בנפרד. הוא משתמש בשלושה מערכים חד-ממדיים בלבד:

1. מערך הערכים: רשימה ששומרת את כל הערכים שאינם אפס. הנתונים נאספים משמאל לימין ומלמעלה למטה, שורה אחר שורה.

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

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

אם למטריצה יש N שורות, M עמודות, ומספר התאים שאינם אפס הוא NNZ, מטריצה רגילה תדרוש זיכרון של O(N × M). לעומתה, CRS ידרוש רק O(2 × NNZ + N + 1).

מי המציא את זה?

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

הפורמט המסוים שמוכר לנו כיום כ-CSR מזוהה היסטורית בעיקר עם Yale Sparse Matrix Format. פורמט זה קיבל את צורתו הסטנדרטית בשנות ה-70 באוניברסיטת ייל, בזכות קבוצת חוקרים שכללה את סטנלי אייזנשטט, מרטין שולץ, אנדרו שרמן וקרייג דאגלס. הם בנו ספריות תוכנה שנועדו לבצע חישובים מהירים למטריצות הללו, והפכו את הפורמט לסטנדרט שחצה את גבולות האקדמיה אל התעשייה.

למה זה כל כך יעיל והיכן החסרונות?

לוקאליות זיכרון

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

הכפלת מטריצה בווקטור

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

אבל יש גם חיסרון

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

לסיכום

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

הכלכלן שנאלץ להמציא מחדש את מדעי המחשב ומהנדסי החשמל שהאירו את אמריקה

יש לכם צורך במבני נתונים ו/או אלגוריתמים מותאמים או שדורשים שיפורים? צריכים עזרה עם מתמטיקה שימושית? עיבוד אותות? צריכים מחקר אלגוריתמי יישומי? צריכים להאיץ תהליכים אלגוריתמיים? ה-AI שלכם צריך שיפור ביצועים, שיפור בדיוק, שיפור בנראות או שיפור בהסברתיות?

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

דברו איתי:

שלמה יונה

מייסד ומדען ראשי, מתמטיקאי מחקר ופיתוח בע"מ

053-7326360

shlomo.yona@mathematic.ai 

https://mathematic.ai

פודקאסט על החברה ועליי, שלמה יונה, ואופן העבודה שלנו ואיתנו: A technical deep dive about