"הרשו לי לפנות את הבמה בפוסט הזה לטובת בלוגר אורח – יגאל ירוסלבסקי, אשר עובד יחד עמי בחברת סיסטמטיקס. יגאל מתמחה בכלי MathWorks המיועדים לעולם התקשורת, עיבוד אות, יצירה אוטומטית של קוד HDL ואימות (Verification) שלו, וכן בתהליכי פיתוח של אלגוריתמים המתוכננים לפעול על FPGA-ים. וכפי שתגלו – יגאל הוא גם תאולוג לא קטן..."
שלום,
אני יגאל, ומבחינתי הנדסת אלקטרוניקה היא סוג של דת.
וכפי שבכל דת יש זרמים שונים ולפעמים די משונים, גם להנדסת אלקטרוניקה יש זרמים, כשהזרם שאני משתייך אליו נקרא "חומרה ספרתית".
אז איך זה מסתדר עם העובדה שאני עובד כמהנדס אפליקציה המתמחה בכלי MathWorks? הרי MATLAB היא תוכנה מובילה בתחום החישובים הנומריים, עיצוב אלגוריתמים וסימולצית מערכות...
אז זהו, שזה מסתדר לא רע. כידוע, כשדת כלשהי מתנגשת בדבר כזה או אחר שדורש ממנה להיתפשר, היא לא מתפשרת, אבל מוצאת הסבר למה אין פה למעשה שום התנגשות אלא להיפך, שהדבר הזה למעשה מבוסס על אותה הדת ומהווה עוד דוגמא לנכונותה.
ובמקרה שלי, אני משתמש ב-MATLAB על מנת לעצב ולבצע סימולציות למערכות חומרה ספרתית.
איך זה אפשרי? המאמר המפורט להלן יתן לכם הצצה ראשונה לשימוש ב-MATLAB עבור מערכות חומרה ספרתית.
המרת אלגוריתמי MATLAB למערכות טוריות למטרת יצירת קוד HDL
מאת: Kiran Kintali, MathWorks
אף על פי שמתאפשרת אינטגרצית אלגוריתמי MATLAB לתוך מערכות Simulink המיועדות ליצירת קוד C או HDL, חלק לא מבוטל של יישומי עיבוד אות, תקשורת ועיבוד תמונה דורש עיצוב מחדש על מנת להפוך אותם למתאימים ליצירת קוד HDL. למשל, יישומים אלה, לעיתים קרובות, עושים שימוש במשתנים מסוג נקודה צפה בדיוק כפול (double precision floating point) או במחרוזות ו- structures ואף כוללים לולאות בקרת זרימה (למשל מבני for או while). מבנים ומשתנים אלה לא משתלבים טוב עם עולם החומרה הסיפרתית. מעבר לכך, אלגוריתמי MATLAB, במיוחד אלה הפועלים על קבוצות גדולות של נתונים, לא תמיד נכתבים תוך כדי התחשבות באילוצי עיצוב חומרה, למשל שיתוף ושימוש חוזר במשאבי הרכיב. מאמר זה מדגים תהליך המרת אלגוריתם MATLAB של מסנן חציון מסתגל (adaptive median filter) והתאמתו למימוש HDL.
נקודת המוצא שלנו היא מודל Simulink שבכניסתו תמונה רועשת בגודל 131X131 פיקסלים עליה מופעל אלגוריתם adaptive median filter שנותן את התמונה הנקיה במוצא (תמונה 1, צד שמאל למעלה).
הגרסה הנוכחית של האלגוריתם מיושמת למטרת יצירת קוד C (תמונה 1, צד ימין למעלה). האלגוריתם לוקח את כל התמונה בכניסת המערכת, מעבד את המידע בדיוק נקודה צפה כפול ושולח התמונה הנקיה למוצא המערכת. ליבת האלגוריתם מיושמת על ידי שלושה שלבים מקוננים של לולאות for הפועלות על כל התמונה. שתי הלולאות החיצוניות "רצות" על השורות והעמודות של התמונה ואילו הלולאה הפנימית מיישמת את אופיו המסתגל של המסנן על ידי השוואת החציון לתנאי סף והחלטה האם להחליף את הפיקסל או להגדיל את אזור החישוב ולחשב את החציון מחדש.
תמונה 1: מודל סימולינק של מסנן חציון מסתגל, מותאם ליצירת קוד C. תמונות כניסה ויציאה בצד שמאל למעלה, קוד MATLAB תואם בצד ימין למעלה.
האלגוריתם משתמש בארבעה גודלי אזור חישוב אפשריים 3X3, 5X5, 7X7 ו 9X9. בזמן שהיישום, כפי שהוא, כולל מבנים ותבניות אופייניות ליישומי תוכנה והינו לעיל במונחי תוכנה, הוא איננו מתאים ליישום חומרה כלל. להלן מספר סיבות:
האלגוריתם פועל על תמונה בשלמותה. דמיינו לכם לרגע את רוחב הממשק שידרש על מנת להעביר בדגימה אחת 131X131 פיקסלים וזאת עוד לפני שאנחנו מתחשבים בכמות הסיביות שדורש כל פיקסל. לכן על מנת להקטין את רוחב הממשק הנדרש יישומי חומרה אופיינים מזרימים מידע במנות קטנות הנקראות windows או kernels, המידע מעובד בקצב גבוה יותר והשבב מסיים את העיבוד על כל התמונה לפני שהתמונה הבאה מגיעה.
האלגוריתם משתמש במידע מסוג נקודה צפה בדיוק כפול. סוג מידע זה איננו יעיל למימוש בחומרה שכן מימוש חישובים בדיוק כזה דורש הרבה שטח והספק. לפיכך ביישומי חומרה רצוי להימנע משימוש בסוגי מידע בזבזנים ולהישתמש בנתונים וחישובים בעלי נקודה קבועה.
האלגוריתם משתמש בפונקציות מתמטיות יקרות. שימוש בפונקציות כמו חישוב סינוס בזווית, חילוק או חילוק שלם עם שארית מוביל לשימוש לא יעיל במשאבי חומרה. יישום נאיבי של הפונקציות האלה מוביל לקצבי שעון נמוכים. ביישומי חומרה נהוג להישתמש באלגוריתמים זולים, המבוססים על חיבורים או חיסורים חוזרים, לדוגמא אלגוריתם CORDIC.
לולאות תוכנה אינן יעילות במימוש חומרה. ביצוע על גבי חומרה חייב להיות דטרמיניסטי ולכן לא יתכנו לולאות בעלות גבולות דינמיים. רכיבי החומרה פועלים בצורה מקבילית אחד לשני ולכן ניתן לפרוש לולאות על מנת להאיץ את הביצועים, אבל זה דורש יותר שטח סיליקון.
האלגוריתם משתמש במערכים גדולים ומטריצות גדולות. ואלה, כשהם מומרים לחומרה, צורכים משאבי שטח בינהם זכרונות גישה אקראית RAM ואוגרים (registers) רבים.
בהמשך המאמר נראה כיצד יישום מסנן חציון מסתגל מוכוון חומרה מוכל בכל אחת מבעיות הנ"ל.
התאמת אלגוריתם מסנן חציון מסתגל ליישום על גבי חומרה
תהליך התאמת האלגוריתם המקורי ליישום על גבי חומרה כולל מספר צעדים:
- פרישת תמונת מבוא לאות טורי לפני עיבוד (image serialization)
- פרישת המסנן המסתגל לעיבוד מקבילי (parallelization)
- עדכון התמונה המקורית עם ערכי פיקסלים נקיים מרעש (image update)
המאמר מתמקד בשני הצעדים הראשונים.
פרישת תמונת מבוא
רוב אלגוריתמי החומרה אינם מעבדים את כל התמונה אלא פועלים על חלק קטן יותר - חלון (window) בכל צעד בזמן. כתוצאה מכך על התמונה המקורית לעבור פרישה ולהיכנס לתוך השבב בצורה טורית. כמו כן, כתלות בחלק מהתמונה הנדרש להיות זמין לטובת העיבוד, יתכן צורך בחציצת תמונה (buffering) בזכרון השבב. אלגוריתם מתואם חומרה חייב לקחת בחשבון את כמות הזכרון הזמין לטובת החציצה ואת מספר רגלי הממשק הזמינות להזרמת המידע לתוך השבב.
בדוגמה שלנו, מודל הSimulink שונה כך שיפרוש את התמונה לעמודות בגודל 1X9 ויזין אותן לתוך המסנן. המידע נחצץ בתוך המסנן במשך 9 מחזורים כך שנוצר חלון של 9X9 פיקסלים. המסנן מעבד את המידע ומזרים החוצה את הערך המעודכן של פיקסל האמצע. במוצא המסנן הפיקסל מעדכן את הפיקסל התואם בתמונה המקורית. עתה כשהמסנן פועל על חלונות מידע קטנים עליו לרוץ בקצב מהיר יותר, כך שיספיק לסיים את כל התמונה לפני שהתמונה הבאה תהיה זמינה בממשק הכניסה.
חציצת מידע כזאת, בנוסף לממשקי מידע, דורשת גם אותות בקרה על זרימת מידע לעיבוד על ידי האלגוריתם הממומש בחומרה. במודל זה (תמונה 2) תת-המערכת (sub-system "capture_column_data") עוזרת לסרוק את התמונה ולהזין חלונות של 1X9 פיקסלים לתת-מערכת "MedianFilter_2D_HW" שהיא המסנן. מפני שמסנן דו-מימדי מסתגל פועל על מידע בגודל מקסימל של 9X9, מילוי צינור עיבוד הנתונים (pipeline) וחישוב ערך הפיקסל המרכזי לוקח 9 מחזורים. לכן, יש צורך באות בקרה המסמן את תקפות הפיקסל במוצא המסנן.
תמונה 2: מודל סימולינק של מסנן חציון מסתגל מתואם ליצירת קוד HDL, סריקת תמונה ויצירת חלונות 1X9 מיוצגות ע"י תת-מערכת "capture_column_data" (שמאל למטה). יישום מסנן חציון מסתגל מוצג בצד ימין למטה.
במוצא המסנן תת-מערכת "update_image" משחזרת תמונת כניסה נקיה תוך שימוש בפיקסל מסונן ואותות בקרה.
מיקבול האלגוריתם
המסנן המסתגל בוחר את גודל אזור חישוב החציון על בסיס סטטיסטיקה מקומית, גרסת מסנן מתואמת תוכנה מחשבת את הסטטיסטיקה לכל גודל אזור נפרד, תוך כדי שימוש בלולאות מקוננות. גרסת חומרה יכולה לבצע את חישובי כל הגדלים במקביל.
היישום החדש של המסנן מחלק את חוצץ המידע לאזורים של 3X3, 5X5, 7X7, 9X9, מיישם מסנן חציון נפרד לכל אזור ומחשב מינימום, מקסימום וחציון לכל אזור במקביל (תמונה 2, צד ימין למטה). מיקבול חישובי החלונות מאיץ את ביצועי האלגוריתם על גבי החומרה.
ייעול האלגוריתם לחומרה
על מנת למצוא ערכי מינימום, מקסימום וחציון של פיקסלים שכנים בתוך אזור החישוב האלגוריתם המקורי (מתואם תוכנה) רץ על כל השורות משמאל לימין ומלמעלה למטה. בגרסת חומרה של האלגוריתם חישובי מינימום / מקסימום / חציון מבוצעים רק על אזורי עניין מזוהים על ידי מסנן חציון חד-מימדי. תמונה 3 (למעלה) מראה את אופן חישוב ערכי מינימום / מקסימום / חציון על חלון 3X3, כפני שאנחנו רואים אזור חישוב בגודל NxN דורש (N2 * floor log2 N2/2) פעולות השוואה.
תמונה 3: למעלה – אלגוריתם לחישוב מינימום / מקסימום / חציון עבור חלון 3X3. למטה: מסנן חציון חד-מימדי מתואם חומרה
יישום האלגוריתם לאזורים 3X3, 5X5, 7X7 ו 9X9 ידרוש, לפיכך,
(9*4+25*12+49*24+81*41) = 4752 פעולות השוואה.
מקום אחר בו ניתן לצמצם את שטח הסיליקון הנצרך על ידי האלגוריתם, הוא למשל, יישום מסנן דו-מימדי שיפעל על השורות והעמודות של איזור NxN, במקום על הפיקסלים הבודדים. יישום כזה ידרוש פחות משאבים וידרוש 800 משווים
(18+100+196+486) במקום 4752. אבל, מפני שידוע לנו כי ערך פיקסל אמצעי נמצא בדרך כלל בתוך איזור ה 3X3 אנחנו יכולים להיתפשר על האיכות ולהישתמש באלגוריתם מאבד מידע (lossy) על אזורים אחרים (get_median_2d) ואילו על איזור 3X3 להישתמש באלגוריתם חד מימדי (תמונה 3, למטה).
על מנת לבדוק את ביצועי האלגוריתם אנחנו פשוט נחליף בין הפונקציה get_median_1d לבין הפונקציה
get_ median_2d, נבצע סימולציה ונשווה בין התוצאות. הפיקסל במוצא הפונקציה משמש לביטול הרעש בתמונת מקור
(denoising).
יתרונות הגישה
MATLAB ו-Simulink מספקים דרך תמציתית להצגת אלגוריתם: מסנן חציון מסתגל מתואר באמצעות כ-186 שורות קוד MATLAB. יישום של אותו האלגוריתם בשפת C היה מצריך לא פחות מ-1000 שורות קוד ואילו במקרה של שפת HDL לא פחות מ-200 שורות קוד. הבנת הקשר שבין בין מריכיבי המערכת, ביצועיה ומשאביה היא מפתח ליישום יעיל של אלגוריתמים מורכבים לעיבוד אותות ותמונות. MATLAB ו- Simulink עוזרים לחקור את הקשר הנ"ל עוד בשלב הפשטה (abstraction) גבוה, לפני שכתבנו יותר מדי שורות קוד חומרה ועל ידי כך מאפשרים להישתמש ביכולות MATLAB בפיתוח ישומי חומרה.
מקור:
Converting MATLAB Algorithms to HDL by Kiran Kintali
אני יגאל, ומבחינתי הנדסת אלקטרוניקה היא סוג של דת.
וכפי שבכל דת יש זרמים שונים ולפעמים די משונים, גם להנדסת אלקטרוניקה יש זרמים, כשהזרם שאני משתייך אליו נקרא "חומרה ספרתית".
אז איך זה מסתדר עם העובדה שאני עובד כמהנדס אפליקציה המתמחה בכלי MathWorks? הרי MATLAB היא תוכנה מובילה בתחום החישובים הנומריים, עיצוב אלגוריתמים וסימולצית מערכות...
אז זהו, שזה מסתדר לא רע. כידוע, כשדת כלשהי מתנגשת בדבר כזה או אחר שדורש ממנה להיתפשר, היא לא מתפשרת, אבל מוצאת הסבר למה אין פה למעשה שום התנגשות אלא להיפך, שהדבר הזה למעשה מבוסס על אותה הדת ומהווה עוד דוגמא לנכונותה.
ובמקרה שלי, אני משתמש ב-MATLAB על מנת לעצב ולבצע סימולציות למערכות חומרה ספרתית.
איך זה אפשרי? המאמר המפורט להלן יתן לכם הצצה ראשונה לשימוש ב-MATLAB עבור מערכות חומרה ספרתית.
המרת אלגוריתמי MATLAB למערכות טוריות למטרת יצירת קוד HDL
מאת: Kiran Kintali, MathWorks
אף על פי שמתאפשרת אינטגרצית אלגוריתמי MATLAB לתוך מערכות Simulink המיועדות ליצירת קוד C או HDL, חלק לא מבוטל של יישומי עיבוד אות, תקשורת ועיבוד תמונה דורש עיצוב מחדש על מנת להפוך אותם למתאימים ליצירת קוד HDL. למשל, יישומים אלה, לעיתים קרובות, עושים שימוש במשתנים מסוג נקודה צפה בדיוק כפול (double precision floating point) או במחרוזות ו- structures ואף כוללים לולאות בקרת זרימה (למשל מבני for או while). מבנים ומשתנים אלה לא משתלבים טוב עם עולם החומרה הסיפרתית. מעבר לכך, אלגוריתמי MATLAB, במיוחד אלה הפועלים על קבוצות גדולות של נתונים, לא תמיד נכתבים תוך כדי התחשבות באילוצי עיצוב חומרה, למשל שיתוף ושימוש חוזר במשאבי הרכיב. מאמר זה מדגים תהליך המרת אלגוריתם MATLAB של מסנן חציון מסתגל (adaptive median filter) והתאמתו למימוש HDL.
נקודת המוצא שלנו היא מודל Simulink שבכניסתו תמונה רועשת בגודל 131X131 פיקסלים עליה מופעל אלגוריתם adaptive median filter שנותן את התמונה הנקיה במוצא (תמונה 1, צד שמאל למעלה).
הגרסה הנוכחית של האלגוריתם מיושמת למטרת יצירת קוד C (תמונה 1, צד ימין למעלה). האלגוריתם לוקח את כל התמונה בכניסת המערכת, מעבד את המידע בדיוק נקודה צפה כפול ושולח התמונה הנקיה למוצא המערכת. ליבת האלגוריתם מיושמת על ידי שלושה שלבים מקוננים של לולאות for הפועלות על כל התמונה. שתי הלולאות החיצוניות "רצות" על השורות והעמודות של התמונה ואילו הלולאה הפנימית מיישמת את אופיו המסתגל של המסנן על ידי השוואת החציון לתנאי סף והחלטה האם להחליף את הפיקסל או להגדיל את אזור החישוב ולחשב את החציון מחדש.
תמונה 1: מודל סימולינק של מסנן חציון מסתגל, מותאם ליצירת קוד C. תמונות כניסה ויציאה בצד שמאל למעלה, קוד MATLAB תואם בצד ימין למעלה.
האלגוריתם משתמש בארבעה גודלי אזור חישוב אפשריים 3X3, 5X5, 7X7 ו 9X9. בזמן שהיישום, כפי שהוא, כולל מבנים ותבניות אופייניות ליישומי תוכנה והינו לעיל במונחי תוכנה, הוא איננו מתאים ליישום חומרה כלל. להלן מספר סיבות:
האלגוריתם פועל על תמונה בשלמותה. דמיינו לכם לרגע את רוחב הממשק שידרש על מנת להעביר בדגימה אחת 131X131 פיקסלים וזאת עוד לפני שאנחנו מתחשבים בכמות הסיביות שדורש כל פיקסל. לכן על מנת להקטין את רוחב הממשק הנדרש יישומי חומרה אופיינים מזרימים מידע במנות קטנות הנקראות windows או kernels, המידע מעובד בקצב גבוה יותר והשבב מסיים את העיבוד על כל התמונה לפני שהתמונה הבאה מגיעה.
האלגוריתם משתמש במידע מסוג נקודה צפה בדיוק כפול. סוג מידע זה איננו יעיל למימוש בחומרה שכן מימוש חישובים בדיוק כזה דורש הרבה שטח והספק. לפיכך ביישומי חומרה רצוי להימנע משימוש בסוגי מידע בזבזנים ולהישתמש בנתונים וחישובים בעלי נקודה קבועה.
האלגוריתם משתמש בפונקציות מתמטיות יקרות. שימוש בפונקציות כמו חישוב סינוס בזווית, חילוק או חילוק שלם עם שארית מוביל לשימוש לא יעיל במשאבי חומרה. יישום נאיבי של הפונקציות האלה מוביל לקצבי שעון נמוכים. ביישומי חומרה נהוג להישתמש באלגוריתמים זולים, המבוססים על חיבורים או חיסורים חוזרים, לדוגמא אלגוריתם CORDIC.
לולאות תוכנה אינן יעילות במימוש חומרה. ביצוע על גבי חומרה חייב להיות דטרמיניסטי ולכן לא יתכנו לולאות בעלות גבולות דינמיים. רכיבי החומרה פועלים בצורה מקבילית אחד לשני ולכן ניתן לפרוש לולאות על מנת להאיץ את הביצועים, אבל זה דורש יותר שטח סיליקון.
האלגוריתם משתמש במערכים גדולים ומטריצות גדולות. ואלה, כשהם מומרים לחומרה, צורכים משאבי שטח בינהם זכרונות גישה אקראית RAM ואוגרים (registers) רבים.
בהמשך המאמר נראה כיצד יישום מסנן חציון מסתגל מוכוון חומרה מוכל בכל אחת מבעיות הנ"ל.
התאמת אלגוריתם מסנן חציון מסתגל ליישום על גבי חומרה
תהליך התאמת האלגוריתם המקורי ליישום על גבי חומרה כולל מספר צעדים:
- פרישת תמונת מבוא לאות טורי לפני עיבוד (image serialization)
- פרישת המסנן המסתגל לעיבוד מקבילי (parallelization)
- עדכון התמונה המקורית עם ערכי פיקסלים נקיים מרעש (image update)
המאמר מתמקד בשני הצעדים הראשונים.
פרישת תמונת מבוא
רוב אלגוריתמי החומרה אינם מעבדים את כל התמונה אלא פועלים על חלק קטן יותר - חלון (window) בכל צעד בזמן. כתוצאה מכך על התמונה המקורית לעבור פרישה ולהיכנס לתוך השבב בצורה טורית. כמו כן, כתלות בחלק מהתמונה הנדרש להיות זמין לטובת העיבוד, יתכן צורך בחציצת תמונה (buffering) בזכרון השבב. אלגוריתם מתואם חומרה חייב לקחת בחשבון את כמות הזכרון הזמין לטובת החציצה ואת מספר רגלי הממשק הזמינות להזרמת המידע לתוך השבב.
בדוגמה שלנו, מודל הSimulink שונה כך שיפרוש את התמונה לעמודות בגודל 1X9 ויזין אותן לתוך המסנן. המידע נחצץ בתוך המסנן במשך 9 מחזורים כך שנוצר חלון של 9X9 פיקסלים. המסנן מעבד את המידע ומזרים החוצה את הערך המעודכן של פיקסל האמצע. במוצא המסנן הפיקסל מעדכן את הפיקסל התואם בתמונה המקורית. עתה כשהמסנן פועל על חלונות מידע קטנים עליו לרוץ בקצב מהיר יותר, כך שיספיק לסיים את כל התמונה לפני שהתמונה הבאה תהיה זמינה בממשק הכניסה.
חציצת מידע כזאת, בנוסף לממשקי מידע, דורשת גם אותות בקרה על זרימת מידע לעיבוד על ידי האלגוריתם הממומש בחומרה. במודל זה (תמונה 2) תת-המערכת (sub-system "capture_column_data") עוזרת לסרוק את התמונה ולהזין חלונות של 1X9 פיקסלים לתת-מערכת "MedianFilter_2D_HW" שהיא המסנן. מפני שמסנן דו-מימדי מסתגל פועל על מידע בגודל מקסימל של 9X9, מילוי צינור עיבוד הנתונים (pipeline) וחישוב ערך הפיקסל המרכזי לוקח 9 מחזורים. לכן, יש צורך באות בקרה המסמן את תקפות הפיקסל במוצא המסנן.
תמונה 2: מודל סימולינק של מסנן חציון מסתגל מתואם ליצירת קוד HDL, סריקת תמונה ויצירת חלונות 1X9 מיוצגות ע"י תת-מערכת "capture_column_data" (שמאל למטה). יישום מסנן חציון מסתגל מוצג בצד ימין למטה.
במוצא המסנן תת-מערכת "update_image" משחזרת תמונת כניסה נקיה תוך שימוש בפיקסל מסונן ואותות בקרה.
מיקבול האלגוריתם
המסנן המסתגל בוחר את גודל אזור חישוב החציון על בסיס סטטיסטיקה מקומית, גרסת מסנן מתואמת תוכנה מחשבת את הסטטיסטיקה לכל גודל אזור נפרד, תוך כדי שימוש בלולאות מקוננות. גרסת חומרה יכולה לבצע את חישובי כל הגדלים במקביל.
היישום החדש של המסנן מחלק את חוצץ המידע לאזורים של 3X3, 5X5, 7X7, 9X9, מיישם מסנן חציון נפרד לכל אזור ומחשב מינימום, מקסימום וחציון לכל אזור במקביל (תמונה 2, צד ימין למטה). מיקבול חישובי החלונות מאיץ את ביצועי האלגוריתם על גבי החומרה.
ייעול האלגוריתם לחומרה
על מנת למצוא ערכי מינימום, מקסימום וחציון של פיקסלים שכנים בתוך אזור החישוב האלגוריתם המקורי (מתואם תוכנה) רץ על כל השורות משמאל לימין ומלמעלה למטה. בגרסת חומרה של האלגוריתם חישובי מינימום / מקסימום / חציון מבוצעים רק על אזורי עניין מזוהים על ידי מסנן חציון חד-מימדי. תמונה 3 (למעלה) מראה את אופן חישוב ערכי מינימום / מקסימום / חציון על חלון 3X3, כפני שאנחנו רואים אזור חישוב בגודל NxN דורש (N2 * floor log2 N2/2) פעולות השוואה.
יישום האלגוריתם לאזורים 3X3, 5X5, 7X7 ו 9X9 ידרוש, לפיכך,
(9*4+25*12+49*24+81*41) = 4752 פעולות השוואה.
מקום אחר בו ניתן לצמצם את שטח הסיליקון הנצרך על ידי האלגוריתם, הוא למשל, יישום מסנן דו-מימדי שיפעל על השורות והעמודות של איזור NxN, במקום על הפיקסלים הבודדים. יישום כזה ידרוש פחות משאבים וידרוש 800 משווים
(18+100+196+486) במקום 4752. אבל, מפני שידוע לנו כי ערך פיקסל אמצעי נמצא בדרך כלל בתוך איזור ה 3X3 אנחנו יכולים להיתפשר על האיכות ולהישתמש באלגוריתם מאבד מידע (lossy) על אזורים אחרים (get_median_2d) ואילו על איזור 3X3 להישתמש באלגוריתם חד מימדי (תמונה 3, למטה).
על מנת לבדוק את ביצועי האלגוריתם אנחנו פשוט נחליף בין הפונקציה get_median_1d לבין הפונקציה
get_ median_2d, נבצע סימולציה ונשווה בין התוצאות. הפיקסל במוצא הפונקציה משמש לביטול הרעש בתמונת מקור
(denoising).
יתרונות הגישה
MATLAB ו-Simulink מספקים דרך תמציתית להצגת אלגוריתם: מסנן חציון מסתגל מתואר באמצעות כ-186 שורות קוד MATLAB. יישום של אותו האלגוריתם בשפת C היה מצריך לא פחות מ-1000 שורות קוד ואילו במקרה של שפת HDL לא פחות מ-200 שורות קוד. הבנת הקשר שבין בין מריכיבי המערכת, ביצועיה ומשאביה היא מפתח ליישום יעיל של אלגוריתמים מורכבים לעיבוד אותות ותמונות. MATLAB ו- Simulink עוזרים לחקור את הקשר הנ"ל עוד בשלב הפשטה (abstraction) גבוה, לפני שכתבנו יותר מדי שורות קוד חומרה ועל ידי כך מאפשרים להישתמש ביכולות MATLAB בפיתוח ישומי חומרה.
מקור:
Converting MATLAB Algorithms to HDL by Kiran Kintali
וואו! לא ידעתי שאפשר לעשות את זה.... תודה!
השבמחק