חזק באלגוריתמים

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

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

רביץ עוסק בבעיות מהתחום של רשתות תקשורת מחשבים, כמו מיקסום תעבורה ברשת או מזעור עלויות של בניית רשת. בארבע השנים האחרונות עסק במחקר במסגרת מאגד נפטון (המאגד הישראלי לרשתות מתכנתות) שתקציבו מגיע מהמדען הראשי במשרד הכלכלה. חברי המאגד הם חברות מתעשיית ההיטק וצוותים מהאקדמיה. "לרשתות מחשבים יש צורך תמידי להתרחב על מנת להתמודד עם התעבורה הגדלה. עם גדילת הרשתות, ניהול ותחזוק נהיות משימות מסובכות יותר ויותר," הוא מספר. "לאחרונה חלו התפתחויות שמטרתן היא שיפור ניצול הרשת: ניתוק של ישומי רשת מתשתית הרשת ומעבר מתכנון רשתות לתכנות רשתות. עד לאחרונה רשתות עבדו בצורה סטטית, ישומי רשת היו ממוקמים בשרתים קבועים. היום הדברים דינמיים יותר וישומים יכולים לזוז משרת לשרת. נניח שבלילה יש אזור מסוים שאין בו פעילות – אז אפשר לסגור שרתים ולרכז את כל הפעילות בשרת בודד, כדי לחסוך באנרגיה. זה מאפשר יותר דינמיות, אבל צריך לנהל את זה. במסגרת מאגד נפטון, המטרה שלי הייתה לתכנן אלגוריתמים לשיבוץ בקשות לתעבורה שכוללת הפעלה של מס' ישומי רשת. חלק מתוצאות המחקר הוצגו בכנס ALGOCLOUD 2017."

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

בעיה אחרת בה עוסק רביץ ידועה בשם בעיית הסקי. "נניח שאנחנו יוצאים לחופשת סקי. אנחנו יכולים לשכור ציוד סקי בתשלום יומי או לקנות את הציוד בתשלום חד פעמי. השאלה היא האם לקנות או לשכור? זו שאלה קלה אם אורך החופשה ידוע, אבל מה עושים אורך החופשה לא ידוע? ניתן לסבך את הבעיה ע"י הכנסת אפשרות נוספת של חברות מועדון, שגם היא עולה כסף, אבל פחות מקניית הציוד, והיא מוזילה את דמי השכירות של הציוד. במקרה זה השאלה היא מתי עוברים ממצב שכירות למשנהו כשאנחנו לא יודעים מתי החופשה נגמרת." הוא מסביר. "ישום אפשרי של הבעיה היא מעבר בין מצבי פעולה/שינה במחשב. למשל אם הפסקנו לגעת בלוח המקשים של המחשב, מתי עדיף להכניס אותו למצב שינה? מצד אחד, אם הוא נכנס למצב שינה הוא צריך לשמור את המצב הנוכחי שלו, להיכבות ואחר כך להידלק מחדש. זה בזבוז אנרגיה גדול - אבל חד פעמי. גם להישאר ער זה בזבוז אנרגיה – אבל זה תחזוקה של המצב הקיים, בזבוז אנרגיה נמוך יותר לאורך זמן. נשאלת השאלה מתי הכי טוב "להרדים" את המחשב. יתכן שהבעיה נשמעת פשוטה, אבל יש מספר רב של מאמרים שעוסקים בבעיה זו ובגירסאותיה. במאמר משנת 2012 (שהתפרסם בכתב העת SIAM Journal on Discrete Mathematics) עסקנו בגרסה של הבעיה שבה ישנם מספר מצבי שינה. עבודת המאסטר של אחת הסטונדטיות שלי גם עוסקת בבעיה זו."