خوارزمية الذاكرة الخارجية

في مجال الحوسبة ، تُعرف خوارزميات الذاكرة الخارجية أو خوارزميات خارج الذاكرة الرئيسية بأنها خوارزميات مصممة لمعالجة البيانات التي تفوق حجمها سعة الذاكرة الرئيسية للحاسوب . يجب تحسين هذه الخوارزميات لجلب البيانات المخزنة في ذاكرة ثانوية بطيئة ( ذاكرة مساعدة ) مثل محركات الأقراص الصلبة أو محركات الأشرطة ، أو عند وجود الذاكرة على شبكة حاسوب ، والوصول إليها بكفاءة . ^{[ 1 ]}^{[ 2 ]} تُحلل خوارزميات الذاكرة الخارجية ضمن نموذج الذاكرة الخارجية .

نموذج

{\displaystyle {\tfrac {M}{B}}} — يحتوي المخزن الموجود على اليسار ${\tfrac {M}{B}}$ كتل من الحجم $B$ لكل منها، ليصبح المجموع $M$ كائنًا. الذاكرة الخارجية على اليمين غير محدودة.

تُحلل خوارزميات الذاكرة الخارجية ضمن نموذج حسابي مثالي يُسمى نموذج الذاكرة الخارجية (أو نموذج الإدخال/الإخراج ، أو نموذج الوصول إلى القرص ). يُعد نموذج الذاكرة الخارجية آلة مجردة تُشبه نموذج آلة ذاكرة الوصول العشوائي (RAM) ، ولكن مع وجود ذاكرة تخزين مؤقتة (كاش) بالإضافة إلى الذاكرة الرئيسية . يُجسد هذا النموذج حقيقة أن عمليات القراءة والكتابة أسرع بكثير في ذاكرة التخزين المؤقتة منها في الذاكرة الرئيسية ، وأن قراءة الكتل المتجاورة الطويلة أسرع من القراءة العشوائية باستخدام رأس القراءة والكتابة للقرص . يُحدد زمن تشغيل الخوارزمية في نموذج الذاكرة الخارجية بعدد عمليات القراءة والكتابة المطلوبة للذاكرة. ^[³^] طُوّر هذا النموذج بواسطة ألوك أغاروال وجيفري فيتر عام 1988. ^[⁴^] يرتبط نموذج الذاكرة الخارجية بنموذج عدم الاكتراث بذاكرة التخزين المؤقتة ، ولكن الخوارزميات في نموذج الذاكرة الخارجية قد تعرف حجم الكتلة وحجم ذاكرة التخزين المؤقتة . لهذا السبب، يُشار إلى هذا النموذج أحيانًا باسم نموذج الاكتراث بذاكرة التخزين المؤقتة . ^[⁵^]

يتكون النموذج من معالج مزود بذاكرة داخلية أو ذاكرة تخزين مؤقتة بحجم $M$ ، متصلة بذاكرة خارجية غير محدودة . تُقسّم كلتا الذاكرتين، الداخلية والخارجية، إلى كتل بحجم $B.$ تتألف عملية الإدخال/الإخراج أو نقل البيانات من نقل كتلة من $B$ عنصرًا متجاورًا من الذاكرة الخارجية إلى الداخلية، ويُحدد زمن تشغيل الخوارزمية بعدد عمليات الإدخال/الإخراج هذه. ^{[ 4 ]}

الخوارزميات

تستفيد الخوارزميات في نموذج الذاكرة الخارجية من حقيقة أن استرجاع عنصر واحد من الذاكرة الخارجية يسترجع كتلة كاملة بحجم $B.$ وتسمى هذه الخاصية أحيانًا بالموضعية.

يُمكن البحث عن عنصر من بين $N كائنًا في نموذج الذاكرة الخارجية باستخدام$ شجرة B ذات عامل تفرع $B.$ وباستخدام شجرة B، يُمكن تحقيق البحث والإدراج والحذف في $O(\log _{B}N)$ الوقت (في ترميز Big O ). من الناحية النظرية ، هذا هو الحد الأدنى لوقت التشغيل الممكن لهذه العمليات، لذا فإن استخدام شجرة B هو الأمثل تقاربياً . ^{[ 4 ]}

الفرز الخارجي هو عملية فرز تتم في بيئة ذاكرة خارجية. يمكن إجراء الفرز الخارجي عبر فرز التوزيع، وهو مشابه للفرز السريع ، أو عبر... ${\tfrac {M}{B}}$ فرز الدمج ذو الاتجاه الواحد . كلا المتغيرين يحققان وقت التشغيل الأمثل تقاربياً . $O\left({\frac {N}{B}}\log _{\frac {M}{B}}{\frac {N}{B}}\right)$ لفرز $N$ عنصرًا. ينطبق هذا الحد أيضًا على تحويل فورييه السريع في نموذج الذاكرة الخارجية. ^{[ 2 ]}

تتمثل مشكلة التبديل في إعادة ترتيب $N عنصرًا في$ تبديل محدد . يمكن القيام بذلك إما عن طريق الفرز، الذي يتطلب وقت تشغيل الفرز المذكور أعلاه، أو عن طريق إدخال كل عنصر بالترتيب وتجاهل فائدة الموضع. وبالتالي، يمكن إجراء التبديل في $O\left(\min \left(N,{\frac {N}{B}}\log _{\frac {M}{B}}{\frac {N}{B}}\right)\right)$ وقت.

التطبيقات

يُجسّد نموذج الذاكرة الخارجية التسلسل الهرمي للذاكرة ، وهو ما لا تُجسّده النماذج الشائعة الأخرى المستخدمة في تحليل هياكل البيانات ، مثل آلة الوصول العشوائي ، وهو مفيد لإثبات الحدود الدنيا لهياكل البيانات. كما يُفيد هذا النموذج في تحليل الخوارزميات التي تعمل على مجموعات بيانات أكبر من أن تتسع لها الذاكرة الداخلية. ^{[ 4 ]}

ومن الأمثلة النموذجية على ذلك نظم المعلومات الجغرافية ، وخاصة نماذج الارتفاع الرقمية ، حيث تتجاوز مجموعة البيانات الكاملة بسهولة عدة غيغابايت أو حتى تيرابايت من البيانات.

تتجاوز هذه المنهجية وحدات المعالجة المركزية للأغراض العامة لتشمل أيضًا الحوسبة باستخدام وحدات معالجة الرسومات ، بالإضافة إلى معالجة الإشارات الرقمية التقليدية . في الحوسبة للأغراض العامة على وحدات معالجة الرسومات (GPGPU)، تُستخدم بطاقات رسومات قوية ذات ذاكرة محدودة (مقارنة بذاكرة النظام الأكثر شيوعًا، والتي يُشار إليها غالبًا باسم ذاكرة الوصول العشوائي RAM )، مع نقل بيانات بطيء نسبيًا من وحدة المعالجة المركزية إلى وحدة معالجة الرسومات (مقارنة بعرض نطاق الحوسبة).

تاريخ

استُخدم مصطلح " خارج الذاكرة الأساسية" كصفة لأول مرة عام 1962 للإشارة إلى الأجهزة التي لا تُعد ذاكرة أساسية لجهاز IBM 360. ^{[ 6 ]} وظهر استخدام مبكر لمصطلح "خارج الذاكرة الأساسية" فيما يتعلق بالخوارزميات عام 1971. ^{[ 7 ]}

انظر أيضاً

مراجع

↑ فيتر، جيه إس (2001). "خوارزميات الذاكرة الخارجية وهياكل البيانات: التعامل مع البيانات الضخمة". مجلة ACM Computing Surveys . 33 (2): 209-271 . CiteSeerX 10.1.1.42.7064 . doi : 10.1145/384192.384193 . S2CID 2155038 .
1 2 فيتر، جيه إس (2008). الخوارزميات وهياكل البيانات للذاكرة الخارجية (ملف PDF) . سلسلة أسس واتجاهات علوم الحاسوب النظرية. المجلد 2. هانوفر، ماساتشوستس: ناو بابليشرز. الصفحات 305-474 . CiteSeerX 10.1.1.140.3731 . doi : 10.1561/0400000014 . ISBN 978-1-60198-106-6.{{cite book}}تم |journal=تجاهله ( مساعدة )
^ تشانغ ، دونغوي. تسوتراس، فاسيليس ج.؛ ليفيالدي، ستيفانو؛ جرينشتاين، جورج. بيري، ديمون أندرو؛ جويت برونيه، فاليري؛ كوش، هارالد. دولر، ماريو. دولر، ماريو. كوش، هارالد. ماير، بول. بهاتاشاريا، أرناب؛ ليوسا، فيبجورن؛ ناك، فرانك؛ بارتوليني، إيلاريا؛ جويت برونيه، فاليري؛ مي، تاو؛ روي، يونغ؛ كروسيانو، ميشيل. شيه، فرانك Y.؛ مروحة، وينفي؛ أولمان كولير، مولي؛ كلارك، يوجين. ارونسون، صموئيل. ميلين، جوناس. بيرندتسون، ميكائيل. غراني، غوستا؛ بيرتوسي، ليوبولدو؛ دونغ، جوزهو؛ وآخرون . (2009). “نموذج الإدخال / الإخراج للحساب”. موسوعة أنظمة قواعد البيانات . سبرينغر ساينس + بيزنس ميديا . الصفحات 1333-1334 . doi : 10.1007/978-0-387-39940-9_752 . ISBN 978-0-387-35544-3.
1 2 3 4 أغاروال، ألوك؛ فيتر، جيفري (1988). "تعقيد المدخلات/المخرجات في الفرز والمشاكل ذات الصلة" . اتصالات ACM . 31 (9): 1116-1127 . doi : 10.1145/48529.48535 . S2CID 6264984 .
↑ ديمين، إريك (2002). خوارزميات وهياكل بيانات غير حساسة لذاكرة التخزين المؤقت (ملف PDF) . ملاحظات محاضرات من المدرسة الصيفية لمؤسسة EEF حول مجموعات البيانات الضخمة. آرهوس: BRICS.
↑ ناسا إس بي . ناسا. 1962. ص. 276.
↑ الحواسيب في أزمة . ACM. 1971. ص 296.

روابط خارجية

[1] فيتر، جيه إس (2001). "خوارزميات الذاكرة الخارجية وهياكل البيانات: التعامل مع البيانات الضخمة". مجلة ACM Computing Surveys . 33 (2): 209-271 . CiteSeerX 10.1.1.42.7064 . doi : 10.1145/384192.384193 . S2CID 2155038 .

[Vitter-2] 1 2 فيتر، جيه إس (2008). الخوارزميات وهياكل البيانات للذاكرة الخارجية (ملف PDF) . سلسلة أسس واتجاهات علوم الحاسوب النظرية. المجلد 2. هانوفر، ماساتشوستس: ناو بابليشرز. الصفحات 305-474 . CiteSeerX 10.1.1.140.3731 . doi : 10.1561/0400000014 . ISBN 978-1-60198-106-6.{{cite book}}تم |journal=تجاهله ( مساعدة )

[Springer-3] تشانغ ، دونغوي. تسوتراس، فاسيليس ج.؛ ليفيالدي، ستيفانو؛ جرينشتاين، جورج. بيري، ديمون أندرو؛ جويت برونيه، فاليري؛ كوش، هارالد. دولر، ماريو. دولر، ماريو. كوش، هارالد. ماير، بول. بهاتاشاريا، أرناب؛ ليوسا، فيبجورن؛ ناك، فرانك؛ بارتوليني، إيلاريا؛ جويت برونيه، فاليري؛ مي، تاو؛ روي، يونغ؛ كروسيانو، ميشيل. شيه، فرانك Y.؛ مروحة، وينفي؛ أولمان كولير، مولي؛ كلارك، يوجين. ارونسون، صموئيل. ميلين، جوناس. بيرندتسون، ميكائيل. غراني، غوستا؛ بيرتوسي، ليوبولدو؛ دونغ، جوزهو؛ وآخرون . (2009). “نموذج الإدخال / الإخراج للحساب”. موسوعة أنظمة قواعد البيانات . سبرينغر ساينس + بيزنس ميديا . الصفحات 1333-1334 . doi : 10.1007/978-0-387-39940-9_752 . ISBN 978-0-387-35544-3.

[Aggarwal88-4] 1 2 3 4 أغاروال، ألوك؛ فيتر، جيفري (1988). "تعقيد المدخلات/المخرجات في الفرز والمشاكل ذات الصلة" . اتصالات ACM . 31 (9): 1116-1127 . doi : 10.1145/48529.48535 . S2CID 6264984 .

[Demaine02-5] ديمين، إريك (2002). خوارزميات وهياكل بيانات غير حساسة لذاكرة التخزين المؤقت (ملف PDF) . ملاحظات محاضرات من المدرسة الصيفية لمؤسسة EEF حول مجموعات البيانات الضخمة. آرهوس: BRICS.

[6] ناسا إس بي . ناسا. 1962. ص. 276.

[7] الحواسيب في أزمة . ACM. 1971. ص 296.

[ 1 ]

[ 2 ]

[

[

[

[ 6 ]

[ 7 ]

اللغة	العربية (RTL)
روابط موسوعية	30 رابطاً
المصدر الأصلي	ويكيبيديا ↗