מיון של מערך לזכרון FLASH

[joeher]

מיון של מערך לזכרון FLASH

של מערכת משובצת (embedded) הבעיה: אלגוריתם שימיין טבלא עם מינימום פעמים של כתיבה לזכרון (מספר הפעמים שניתן לכתוב בזכרון FLASH הוא מוגבל). נתנונה כמות מוגבלת של RAM ( אין אפשרות להעתיק ל RAM למיין ולהחזיר) מספר הקריאות לא מוגבל. רעיונות?

 

[DadleFish]

לא נראה לי שהבנתי.

המערך הוא בגודל N, יושב כולו ב-FLASH, וצריך למיין אותו תוך שימוש ב-RAM כאשר גודל ה-RAM קטן מ-N?

 

[joeher]

כן ה RAM ממש ממש קטן

 

[DadleFish]

טוב, רעיון ראשון...

ברוטאלי קצת: נגיד שה-RAM הוא בגודל M, והמערך הוא בגודל N. נבצע את המיון בצורה איטרטיבית, כאשר בכל איטרציה נטפל בעוד M איברים, בצורה כזו: 1. עבור I=1..M איברים בצע 1.1. מצא את האיבר הקטן ביותר במערך שנשאר לא ממוין. 1.2. שמור את האיבר הנ"ל בזכרון ה-RAM. 1.3. דרוס את האיבר הקטן ביותר עם האיבר ה-I במערך שנשאר 2. העתק את האיברים מה-RAM לתחילת המערך הלא ממוין יש לחזור על הפעולה עד לסיום המיון. סה"כ כתיבות - 2*N. נראה לי שהאלגוריתם לא היה ברור כל כך, ולכן אדגים. נגיד שהמערך הוא בגודל 7, וה-RAM בגודל 3. המערך יהיה:

19,2,7,14,12,1,3​

מוצאים את האיבר הכי קטן (1), שמים אותו ב-RAM, ודורסים אותו עם האיבר הראשון במערך, כך:

19,2,7,14,12,19,3​

ממשיכים גם עם 2 (שבו במקרה אין דריסה - הרווחנו כתיבה במקרה) ועם 3, לקבלת התוצאה הזו:

19,2,7,14,12,19,7​

עכשיו דורסים את שלושת האיברים הראשונים עם תוצאת המיון:

1,2,3,14,12,19,7​

אחרי הסיבוב השני ולפני ההעתקה מה-RAM זה יהיה:

1,2,3,14,12,19,19​

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

1,2,3,7,12,14,19​

עכשיו "ממיינים" את האיבר האחרון - וזהו, סיימנו. השאלה היא אם אפשר למצוא משהו שיעבוד ב-K*N כתיבות, כאשר K קטן מ-2.

 

[DNile]

תהייה..

הפורום הזה כבוד, אבל דווקא בנושאים כאלה של Embedded/RT, נראה לי שהוא קצת לוקה בחסר... מישהו מכיר מקור קצת יותר כבד לדיונים בנושא?

 

[DadleFish]

יש news groups שעוסקים ב-E/RT

 

[joeher]

K*2 זה לא נורא. ../images/Emo51.gif האם לדעתך

יהיה שיפור אם נשכלל קצת ובכל איטרציה נסתכל גם על איבר הגדול ביותר?

 

[DadleFish]

איך זה יעזור?

השתמשתי בכל ה-RAM שעומד לרשותי וניסיתי לצמצם כתיבות ל-FLASH. מעניין אם אפשר לצמצם ל-K=1, או להוריד את K ככה שיהיה פחות מ-2 בד"כ.

 

[joeher]

מבחינת כמות הכתיבות לא יעזור אולי

יהיה יותר יעיל כי "סוגרים" גם מלמעלה וגם מלמטה בכל מעבר. אני גם נוטה לחשוב ש גודל N לא משנה אם הוא 1 או יותר - הרי לכל חיפוש מינימום עוברים על שאר המערך אז מה אכפת לי אם N > 1?

 

[codec]

עוד פחות RAM

אפשר לעבוד עם כמות RAM קבועה של 2: להתחיל ממקום 1, ובכל פעם לחפש הכי קטן, ולהחליף עם המקום הנוכחי במערך. כל החלפה היא 2 כתיבות. בדוגמה שלך:

19,2,7,14,12,1,3​

נחליף 1 ו-19

1,2,7,14,12,19,3​

2 נשאר במקום, נחליף 7 ו-3

1,2,3,14,12,19,7​

נחליף 7 ו-14

1,2,3,7,12,19,14​

12 במקום, נחליף 14 ו-19

1,2,3,7,12,14,19​

נגמר. במקרה הזה הרווחנו שתי החלפות, ולכן רק 8 כתיבות. בחישוב שלי יוצא תמיד 2N-2. בכיוון אחר לגמרי, הייתי אולי "מזיז" את המערך למקומות שונים בזיכרון כל כמה זמן (אם יש מקום פנוי, ואפשרות לעדכן את ההצבעות אליו), כדי לפזר את הכתיבות ל-FLASH.

 

[DadleFish]

אין הגבלה על ה-RAM.

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

 

[DadleFish]

כלומר...

לא "אין הגבלה על ה-RAM" אלא "אין צורך לחסוך ב-RAM, אם יש"

 

[codec]

החיסכון ב-RAM הוא סתם בונוס

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

 

[joeher]

יעלות הכתיבה תלויה בסוג הFLASH

למשל כדי לכתו אתה צריך קודם למחוק ואז קל יותר למחוק "סקטור" (למשל 64 BYTES) ולכתוב אותו כבלוק. זה הרבה יותר יעיל מבחינת זמן ריצה - אבל אותה השפעה על "אורך החיים" של הFLASH מבחינת הכתיבות. חשבתי על זה די הרבה ולא מצאתי אלא את הפתרון שאלדד כתב (כאמור זה אותו דבר לכל N > 0 ובשיטה הזו אין משמעות לגודל ה RAM).