الگوریتم حافظه خارجی

در مبحث محاسبات، الگوریتمهای حافظه خارجی (الگوریتم‌های خارج از هسته) به الگوریتم‌هایی می‌گویند که به منظور پردازش داده‌هایی طراحی می‌شوند که به دلیل حجم بالا، در حافظه اصلی رایانه گنجانده نمی‌شوند. این الگوریتم‌ها باید به گونه‌ای طراحی شوند که در بهترین زمان بتوانند به داده‌های درون حافظه‌های کمکی مانند هارد درایودسترسی داشته باشند و آن‌ها را استخراج کنند. الگوریتم‌های حافظه خارجی، در مدل حافظه خارجی بررسی می‌شوند.

مدل

مدل حافظه خارجی (مدل I/O یا مدل disk access) یک نوع مدل محاسبه ایده‌آل شده‌است که منظور آنالیز الگوریتم حافظه خارجی به کار می‌رود. این مدل یک ماشین انتزاعیمانند مدل ماشین RAM می‌باشد با این تفاوت که علاوه بر حافظه اصلی حافظه cache هم وجود دارد.

زمان اجرای یک الگوریتم در مدل حافظه خارجی را تعداد خواندن و نوشتن‌هایی که بر روی حافظه انجام می‌شود تعیین می‌کند. این مدل همچنین بیان می‌کند که خواندن و نوشتن از حافظه cache بسیار سریع تر از حافظه اصلی است. مدل حافظه خارجی نخستین بار از سوی الوک آگاروال و جفری ویتر در سال ۱۹۸۸ معرفی شد. این مدل کمی مرتبط با مدل cache-oblivious می‌باشد ولی الگوریتم‌ها در مدل حافظه خارجی ممکن است هم، اندازه بلاک و هم، اندازه حافظه cache را بدانند به همین دلیل گاهی از این مدل تحت عنوان مدل cache-aware یاد می‌کنند.

حافظه نهان سمت چپ M عنصر را در خود ذخیره می‌کند در حالی که حافظه خارجی (سمت راست) نامحدود است.

این مدل شامل یک پردازنده و حافظه داخلی می‌باشد و همچنین یک حافظه cache در این مدل وجود دارد که اندازه آن را M در نظر می‌گیریم. این cache به یک حافظه خارجی بدون محدودیت متصل است. هردو حافظهٔ داخلی و خارجی بهبلاک‌هایی با اندازه B تقسیم می‌شوند. یک عملیات ورودی/خروجی یا انتقال حافظه در واقع انتقال یک بلاک شامل B عنصر پیوسته از حافظه خارجی به حافظه داخلی می‌باشد و زمان اجرای این الگوریتم با استفاده از تعداد این عملیات‌ها بدست می‌آید.

الگوریتم

الگوریتم‌ها در مدل حافظه خارجی این مزیت را دارند که با بدست آوردن یک شیء از حافظهٔ خارجی می‌توان کل بلاک آن شیء را بدست آورد. پیدا کردن یک عنصر میان N عنصر در این مدل با استفاده از یک درخت بی امکان‌پذیر است؛ که در این درخت هر یک از عملیات پیدا کردن، درج کردن و حذف کردن در زمان $O(\log _{B}N)$

انجام می‌شود. مرتب‌سازی خارجی، یک نوع مرتب‌سازی است که روی حافظه خارجی صورت می‌گیرد. این مرتب‌سازی را می‌توان با استفاده از مرتب‌سازی تجمعی که مشابه مرتب‌سازی سریع است انجام داد. زمان این مرتب‌سازی برای مرتب کردن N عنصر

O({\frac {N}{B}}\log _{\frac {M}{B}}{\frac {N}{B}})

می‌باشد.

کاربردها

این مدل برای تحلیل و بررسی داده‌هایی که به دلیل حجم بالا در حافظه داخلی جا نمی‌شوند بسیار مناسب است. برای مثال در سیستم‌های جغرافیایی، به خصوص سیستم‌های مدلسازی ارتفاعات که حجم داده‌ها از چندین گیگابایت و حتی ترابایت نیز بیشتر می‌شود از مدل حافظه خارجی استفاده می‌شود.

موارد مشابه

منابع

↑ Vitter, J. S. (2001). "External Memory Algorithms and Data Structures: Dealing with MASSIVE DATA". ACM Computing Surveys. 33 (2): 209–271. CiteSeerX 10.1.1.42.7064. doi:10.1145/384192.384193
↑ Vitter, J. S. (2008). Algorithms and Data Structures for External Memory (PDF). Foundations and Trends in Theoretical Computer Science. Series on Foundations and Trends in Theoretical Computer Science. 2. Hanover, MA: Now Publishers. pp. 305–474. CiteSeerX 10.1.1.140.3731. doi:10.1561/0400000014. ISBN 978-1-60198-106-6.
↑ Zhang, Donghui; Tsotras, Vassilis J. ; Levialdi, Stefano; Grinstein, Georges; Berry, Damon Andrew; Gouet-Brunet, Valerie; Kosch, Harald; Döller, Mario; Döller, Mario; Kosch, Harald; Maier, Paul; Bhattacharya, Arnab; Ljosa, Vebjorn; Nack, Frank; Bartolini, Ilaria; Gouet-Brunet, Valerie; Mei, Tao; Rui, Yong; Crucianu, Michel; Shih, Frank Y. ; Fan, Wenfei; Ullman-Cullere, Mollie; Clark, Eugene; Aronson, Samuel; Mellin, Jonas; Berndtsson, Mikael; Grahne, Gösta; Bertossi, Leopoldo; Dong, Guozhu; et al. (2009). "I/O Model of Computation". Encyclopedia of Database Systems. Springer Science+Business Media. pp. 1333–1334. doi:10.1007/978-0-387-39940-9_752. ISBN: 978-0-387-35544-3
↑ Aggarwal, Alok; Vitter, Jeffrey (1988). "The input/output complexity of sorting and related problems". Communications of the ACM. 31 (9): 1116–1127. doi:10.1145/48529.48535
↑ Demaine, Eric(2002)cache-oblivious algorithms and data structures. Lecture Notes from the EEF Summer School on Massive Data Sets. Aarhus: BRICS.

پیوند به بیرون

[1] Vitter, J. S. (2001). "External Memory Algorithms and Data Structures: Dealing with MASSIVE DATA". ACM Computing Surveys. 33 (2): 209–271. CiteSeerX 10.1.1.42.7064. doi:10.1145/384192.384193

[2] Vitter, J. S. (2008). Algorithms and Data Structures for External Memory (PDF). Foundations and Trends in Theoretical Computer Science. Series on Foundations and Trends in Theoretical Computer Science. 2. Hanover, MA: Now Publishers. pp. 305–474. CiteSeerX 10.1.1.140.3731. doi:10.1561/0400000014. ISBN 978-1-60198-106-6.

[3] Zhang, Donghui; Tsotras, Vassilis J. ; Levialdi, Stefano; Grinstein, Georges; Berry, Damon Andrew; Gouet-Brunet, Valerie; Kosch, Harald; Döller, Mario; Döller, Mario; Kosch, Harald; Maier, Paul; Bhattacharya, Arnab; Ljosa, Vebjorn; Nack, Frank; Bartolini, Ilaria; Gouet-Brunet, Valerie; Mei, Tao; Rui, Yong; Crucianu, Michel; Shih, Frank Y. ; Fan, Wenfei; Ullman-Cullere, Mollie; Clark, Eugene; Aronson, Samuel; Mellin, Jonas; Berndtsson, Mikael; Grahne, Gösta; Bertossi, Leopoldo; Dong, Guozhu; et al. (2009). "I/O Model of Computation". Encyclopedia of Database Systems. Springer Science+Business Media. pp. 1333–1334. doi:10.1007/978-0-387-39940-9_752. ISBN: 978-0-387-35544-3

[:0-4] Aggarwal, Alok; Vitter, Jeffrey (1988). "The input/output complexity of sorting and related problems". Communications of the ACM. 31 (9): 1116–1127. doi:10.1145/48529.48535

[5] Demaine, Eric(2002)cache-oblivious algorithms and data structures. Lecture Notes from the EEF Summer School on Massive Data Sets. Aarhus: BRICS.