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

בחירות מקומיות

בעקבות מדידות קודמות שביצעתי על ה-RF Link Kit, ידעתי שמשך אות של 50 מיליוניות השניה הוא פחות או יותר הגבול התחתון הריאלי, ושההפרש בין משך האות שנכנס למשדר למשך האות שיוצא מהמקלט יכול להגיע עד כ-20-30 מיליוניות השניה. כדי לא לדחוק את המעטפת יותר מדי, בחרתי לעבוד עם יחידות זמן של מאה מיליוניות השניה. כלומר, אם נתעלם מההקשר הרחב יותר, שידור של הערך 9 ייראה כך: סיגנל של 100us, דממה למשך 900us ועוד סיגנל של 100us.

כמו כן, בחרתי למדוד את משכי הזמן של הסיגנלים והשקט בעזרת פסיקה (interrupt) על הקלט הנכנס, וזאת כדי להבטיח דיוק מקסימלי ולא להוסיף על הסטיות הקיימות ממילא במערכת. המדידה הזו תהווה בסיס הן לקריאת המידע הנכנס והן להבדלה בין אותות לגיטימיים לרעשים לא רלוונטיים. למשל, אם אות HIGH אינו קרוב מספיק ל-100us, סימן שלא מדובר בשידור מכוון. וכאן הדברים מתחילים להסתבך…

צוואר בקבוק פוטנציאלי

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

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

למדוד, למדוד, למדוד

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

מייקל אבראש (Abrash), גורו האופטימיזציה המפורסם, כתב פעם ש"The only true measure of code performance is observing it in action" ("המדד המהימן היחיד לביצועים של קוד הוא לצפות בו בפעולה"). פעולות חילוק נחשבות אמנם, על פי המסורת, לאיטיות יחסית, אבל בשטח ייתכן שיתגלו גורמים נוספים שלא לקחנו בחשבון.

כתבתי קוד בסיסי ל-ATtiny85, שמבצע את החישוב הנאיבי (חילוק במאה ואז חישוב שארית מחלוקה במאה) על מספרים שונים, ומסמן את תחילת וסיום החישוב בעזרת פין פלט. הנה קוד המקור (שעון המערכת מכוון ל-16MHz):

#include <avr/io.h>

int main(void) {
    volatile uint16_t rd;
    uint16_t x = 0;
    
    DDRB  = 1; // PB0 Output
    PORTB = 0;
    
    while(1) {
  
        x += 10;

        PORTB = 1; // signal        
        rd = x / 100;
        if (x % 100 > 50) ++rd;
        PORTB = 0; // end signal
        
    }
}

הלוג'יק אנלייזר הראה שכל צעד כזה לוקח בסביבות 12-13.5 מיליוניות השניה – יותר גרוע אפילו ממה שחשבתי קודם. כדי לבדוק את האופטימיזציה שהזכרתי, נחליף את השורה עם חישוב השארית בפעולות הכפל והמינוס המקבילות:

        if (x - (rd * 100) > 50) ++rd;

ואכן, עכשיו כל צעד לוקח רק 14.2-14.9 מיליוניות השניה… רגע, מה? איך זה יכול להיות? איך החלפה של פעולה יקרה מאד בשתי פעולות זולות האריכה את משך החישוב במקום לקצר אותו?

לא אטריח אתכם בקוד האסמבלי המורכב שמסתתר מאחורי הסיפור הזה, אך על סמך הקריאה שלו אני יכול לומר שני דברים: ראשית, שפעולת חילוק היא באמת יקרה מאד ביחד לכפל או מינוס, ושנית, שאבראש צדק. פריט המידע החיוני שלא נלקח כאן בחשבון הוא שהקומפיילר עצמו חכם מאד. הוא זיהה שחישוב השארית מבוסס על פעולת חילוק בדיוק כמו זו שבוצעה זה-עתה, אז במקום לחשב הכל מהתחלה, הוא הסתמך על תוצרי הלוואי של החישוב הקודם! זה נעשה בצורה כל כך אלגנטית, שפעולות הכפל-ומינוס נראות מסורבלות בהשוואה, ומכאן ההבדל בזמנים (אפרופו, הטריק הזה התאפשר מכיוון שהקומפיילר ידע ש-x לא ישתנה לו פתאום בין החישוב הראשון לשני. אם נוסיף להגדרה של x את מילת המפתח volatile, שאומרת שהוא כן יכול להשתנות באמצע, נקבל את זמן החישוב שדורשות שתי פעולות חילוק נפרדות).

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

הסיפור האמתי

את כל העבודה והמדידות שהצגתי למעלה, מהכותרת "למדוד, למדוד, למדוד" ועד כאן, ביצעתי למעשה בדיעבד מתוך סקרנות. בזמן העבודה על המערכת, לעומת זאת, בערך דקה אחרי שבחרתי ביחידות של 100us, הבנתי שזו בחירה גרועה. כלומר, מספר עגול זה סבבה, אבל הוא צריך להיות עגול בבסיס 2. למשל, אם נבחר ביחידות של 128us (שתיים בחזקת שמונה), זמן השידור אמנם יתארך מעט – אבל פעולות של חילוק ב-128 ומציאת שארית מחילוק כזה הן לא יותר ממניפולציה קצרצרה ובסיסית להפליא של ביטים!

למעשה, מספיק לשנות את המספר 100 בקוד למעלה ל-128. הקומפיילר יתפוס את העניין לבד, יבחר בדרך היעילה ויוריד את זמן החישוב ל-1.5-2 מיליוניות השניה. אם אנחנו לא סומכים עליו, אפשר לכתוב את הקוד המשופר בעצמנו – למשל כך:

        rd = x >> 6;
        if (x & 0x0040) ++rd;

לא להניח הנחות

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