מקבילות

[gmorphus]

מקבילות

אני הייתי שמח לקבל עצות וכיוונים לבעיה הבאה. מה שאני רוצה לעשות הוא כזה: יש לי קובץ ממש גדול. ממש ממש גדול

(כמה ג'יגות נניח). אני מעוניין לקרוא ממנו באפרים בגדלים שונים (גודל כל באפר נקבע ע"י ארבעת הבתים הראשונים שלו) ולעשות עיבוד על כל באפר. נניח לצורך העניין שעל כל באפר אני מבצע את אותו עיבוד. מכיוון שיש לי יותר ממעבד אחד אני רוצה לפתוח thread נוסף (או אולי יותר מאחד) וכל זה כדי להאיץ כמה שאפשר את העיבוד של הקובץ. נניח יהיה לי thread שקורא מהקובץ באופן א-סינכרוני (overlapped IO) ועוד thread-ים נוספים שמבצעים את העיבוד על הבאפרים. אני חשבתי להשתמש ב completion ports, כך שאני דוחף כל באפר (מצביע לבאפר מן הסתם) לתור, וכל thread שמסיים עיבוד לוקח באפר נוסף. יש לי כמה שאלות: 1. האם יש דרכים יותר מתוחכמות לעשות את זה, ואיך למעשה ממשים completion ports. 2. overlapped io: האם זה לא יפתח לי למעשה thread נוסף? 3. מה אם חשוב לי הסדר של הבאפרים? (נניח שכל thread רושם את העיבוד שלו לקובץ משותף) 4. עכשיו בעוד אני כותב שורות אלה חשבתי על עוד משהו שיפתור את (3): thread נוסף שיהיה אחראי על הכתיבה לקובץ ולמעשה הוא ידעה מתי כל thread לוקח באפר וייתן לו מספר בתור (מצידי שיהיה מספר סידורי רץ) ויהיה אחראי לסדר את הבאפרים... מה אתם חושבים? 5. ועכשיו וסוגיה היותר קשה: אני רוצה גם שיהיה לי פיקוח על עומסים. נניח אם הthread שקורא מהקובץ קורא מהר מאוד, ומצטבר הרבה מאוד מידע באחרים, אני רוצה שהוא גם יתחיל לעבד מידע. נניח על כל 10 באפרים שהוא קורא, שיעבד אותם. אבל הוא גם חייב לקחת מה completion ports, הוא לא יכול לשמור אותם לעצמו אלא לדחוף אותם לתור ולהוציא בזמנו הפנוי. ???

 

[stac]

עזוב אותך מהשטויות האלו....

שלם למישהו שיעשה עבורך את העבודה... [סתם עוזר לך להקפיץ]

 

[ChipsMan]

בקשר לסדר של הבאפרים..

אני מניח שהכוונה שלך היא שהבאפרים ייכתבו לפי הסדר שמכתיבים המספרים הסידוריים שאתה נותן להם. אפשרות 1 (פשוטה יותר למימוש): תממש מבנה נתונים שבו: 1) כל האיברים ממויינים לפי מספר סידורי מהנמוך לגבוה. 2) הכנסת באפר למבנה נעשית למקום המתאים כך האחרי ההכנסה כל הבאפרים יהיו ממויינים לפי מספר סידורי. 3) כל פעם שתרצה לשמור את הנתונים אתה תוציא את הבאפר בעל המספר הסידורי הנמוך ביותר (האיבר הראשון ברשימה) ותכתוב אותו לקובץ הפלט שלך. אפשר לעשות את זה באמצעות שימוש ב-list של STL. אפשרות 2 (יעילה יותר במקרה ויש לך הרבה מאוד באפרים קטנים, אבל קשה יותר למימוש. לא נראה לי שזה שמיש כל כך במקרה שלך): בנה ערימת מינימום (ערימה בינארית) שהמפתח שלה הוא המספר הסידורי. כל צומת בערימה יכיל מספר סידורי (המפתח), מצביע לבאפר שאותו הוא מייצג ומשתנה בוליאני. כאשר אתה קורא באפר מהדיסק הכנס איבר לערימה (שמור מצביע אליו ב-thread שעובד עליו) ותאתחל את המשתנה הבוליאני ל-false. ברגע שסיימת לעבוד על הבאפר עדכן את המצביע לנתוני הפלט בצומת ושנה את ערכו של המשתנה הבוליאני ל-true. ה-thread שלוקח את הבאפרים וכותב אותם לדיסק יעבוד באופן הבא: כל עוד הערימה לא ריקה אם בראש הערימה המשתנה הבוליאני הוא true הוצא את ראש הערימה וכתוב את הבאפר שלו לדיסק. אני מקווה שהבנתי מה בדיוק אתה מנסה לעשות ועזרתי.

 

[gmorphus]

מעניין

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

(אלדד, דווקא ממך האמת ציפיתי לתשובה מקצועית) נ.ב. תודה לstac

 

[ChipsMan]

המימוש לא מסובך..

הוא רק יותר מסובך מהפתרון הראשון. ערימה בינארית היא עסק פשוט. היא לא תקח יותר מ-30 שורות קוד (אני מקווה

)

 

[אלדד28]

מה, מה עשיתי רע? ../images/Emo6.gif

רעיון - תשתמש בשיטת "לוח המודעות". 1. יהיה thread אחד שינהל buffer-ים נכנסים, נקרא לו READER, ו-thread שני שינהל buffer-ים יוצאים, נקרא לו WRITER. 2. יהיה THREAD נוסף שישלוט על ה-WORKER-ים, שהם THREAD-ים נוספים, שמטרתם לעשות את העיבוד. נקרא לו MANAGER. הוא יוכל להתחיל THREAD-ים ולהעיף THREAD-ים לפי הצורך. כל הסטטיסטיקות (מייד נגיע לזה) יגיעו אליו. 3. ה-WORKER-ים, עם הקמתם, יישבו וימתינו ל-BUFFER-ים נכנסים. ברגע שנכנס BUFFER, אחד ה-WORKER-ים ייקח את ה-BUFFER ויתחיל לעבוד עליו. כשיסיים יעביר את ה-BUFFER המוכן אל ה-WRITER. 4. כל ה-THREAD-ים - ה-WRITER, ה-READER, וה-WORKERS, ידווחו סטטיסטיקות ל-MANAGER, שבהתאמה יחליט האם להקים WORKER-ים נוספים (אם יש עומס רב על ה-BUFFER-ים שממתינים לעיבוד) או לעצור WORKER-ים (אם ה-WORKER-ים מתבטלים), וייתכן גם לשלוט ב-EVENT-ים שיווסתו בין הקריאה לבין הכתיבה, כי אם אתה קורא/כותב לאותו דיסק, עדיף שה-READER יבצע קריאה מאסיבית, ובזמן העיבוד ע"י ה-WORKER-ים תתבצע כתיבה מאסיבית על ידי ה-WRITER. 5. נקיונות זכרון: ה-READER יוצר BUFFER בלתי מעובד, וה-WORKER המתאים מוחק אותו. ה-WORKER יוצר BUFFER מעובד, וה-WRITER מוחק אותו. 6. סדר כתיבה: ה-WORKER יסדר את ה-BUFFER-ים שלו ברשימה ממויינת, ויעקוב אחרי הסדר - יהיה לו משתנה CURRENT, וברגע שיגיע ה-BUFFER הבא בתור הוא יכתוב אותו אל הדיסק. אפשר לעשות את זה עוד יותר מתוחכם - לשלוט ב-PRIORITIES של ה-THREADS השונים לפי הצורך; לבדוק את יכולות המחשב, כמו מספר מעבדים; לבזר את העיבוד למחשבים נוספים; וכו'. חשוב מאוד לאסוף כמה שיותר סטטיסטיקות על הביצועים של ה-THREAD-ים ברמת ה-MANAGER. אפשר להתחיל ממודל מאוד פשוט, ולאסוף סטטיסטיקות שבעזרתן תהיה אפשרות לשפר את מודל הבקרה עם הזמן. היזהר משטחי זיכרון משותפים!!! תדאג לעשות CS-ים איפה שצריך, ותחשוב טוב טוב על מה שאתה עושה.

 

[ChipsMan]

סתם רעיון..

שאותו כבר כתבתי קודם. לדעתי בשביל 6 לא צריך רשימה ממויינת. זאת עבודה מיותרת מבחינת המחשב. אפשר לקחת ערימה בינארית.

 

[אלדד28]

נו, אם אתה אומר,

אתה ודאי יודע למה התכוונת אבל אחרי קריאה חוזרת עדיין לא הבנתי איך חילקת ל-THREAD-ים שונים. לגבי 6, ערימה בינארית היא מימוש מסובך שהוא מיותר לדעתי במקרה הזה.

 

[ChipsMan]

הבחור רוצה מהירות מקסימלית ../images/Emo3.gif

ולא דיברתי כלל על חלוקה ל-threads שונים בפתרון שהצעתי. הצעתי רק פתרון לסידור הבאפרים. אתה הצעת פתרון לחלוקה ל-threads שונים

וממתי ערימה בינארית זה מסובך? זה אחד מהמבנים הכי פשוטים ובסיסיים שיש והמימוש שלה לא ייקח יותר מ-30 שורות קוד (לא כולל הערות

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

 

[אלדד28]

אני יוצא מתוך נקודת הנחה כזו

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

 

[gmorphus]

אז ככה

קודם כל תודה לכולם על התשובות - למרות שעדיין לא באתי על סיפוקי ברמה הפרקטית. אלדד, מה שאתה אמרת הוא נכון וטוב, ולמעשה זה בדיוק מה שאני אמרתי אני חושב בהודעה המקורית. אני מחפש עכשיו תשובה יותר פרקטית. כלומר, איך אני מממש את כל זה (ברמה של איזה שיטות להשתמש). באיזה מנגנון אני משתמש להודיע ל"עובדים" שלי (worker threads) על באפרים חדשים? מה יהיה הכי יעיל? completion ports, window messages etc? אולי מנגנונים אחרים (event, semaphores)? מה לגבי הניהול של חלוקת המשאבים של המעבד? מה הדרך הכי טובה לשלוט על זה? איך אני אוסף סטטיסטיקות? ה"עובדים" מודיעים על כל באפר שהם מעבדים?

 

[אלדד28]

למה להסתבך?

תעשה QUEUE שאותה ימלא ה-READER, וממנה ה-WORKER-ים יקראו. כן - סטטיסטיקות יעברו מה-THREAD-ים השונים אל ה-MANAGER. אני חושב שאם תממש את זה בתור מודל פשוט ותתחיל לאסוף כל נתון שאתה יכול לחשוב עליו, תוכל לשפר את המודל לאט לאט עד שתגיע לתוצאות מיטביות. לא תצליח ממילא לחשוב על הכל מראש. תעשה את החשיבה בצורה איטרטיבית. בנה מודל פשוט, אח"כ שפר אותו וכו'.