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

در مبحث محاسبات، الگوریتمهای حافظه خارجی (الگوریتم‌های خارج از هسته) به الگوریتم‌هایی می‌گویند که به منظور پردازش داده‌هایی طراحی می‌شوند که به دلیل حجم بالا، در حافظه اصلی رایانه گنجانده نمی‌شوند. این الگوریتم‌ها باید به گونه‌ای طراحی شوند که در بهترین زمان بتوانند به داده‌های درون حافظه‌های کمکی مانند هارد درایودسترسی داشته باشند و آن‌ها را استخراج کنند.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.384193Vitter, 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. الگوریتم‌های حافظه خارجی، در مدل حافظه خارجی بررسی می‌شوند.

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

زمان اجرای یک الگوریتم در مدل حافظه خارجی را تعداد خواندن و نوشتن‌هایی که بر روی حافظه انجام می‌شود تعیین می‌کند.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 این مدل همچنین بیان می‌کند که خواندن و نوشتن از حافظه cache بسیار سریع تر از حافظه اصلی است. مدل حافظه خارجی نخستین بار از سوی الوک آگاروال و جفری ویتر در سال ۱۹۸۸ معرفی شد.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 این مدل کمی مرتبط با مدل cache-oblivious می‌باشد ولی الگوریتم‌ها در مدل حافظه خارجی ممکن است هم، اندازه بلاک و هم، اندازه حافظه cache را بدانند به همین دلیل گاهی از این مدل تحت عنوان مدل cache-aware یاد می‌کنندDemaine, Eric(2002)cache-oblivious algorithms and data structures. Lecture Notes from the EEF Summer School on Massive Data Sets. Aarhus: BRICS. .
جایگزین=حافظه داخلی و خارجی|بندانگشتی|حافظه نهان سمت چپ M عنصر را در خود ذخیره می‌کند در حالی که حافظه خارجی (سمت راست) نامحدود است.
این مدل شامل یک پردازنده و حافظه داخلی می‌باشد و همچنین یک حافظه cache در این مدل وجود دارد که اندازه آن را M در نظر می‌گیریم. این cache به یک حافظه خارجی بدون محدودیت متصل است. هردو حافظهٔ داخلی و خارجی بهبلاک‌هایی با اندازه B تقسیم می‌شوند. یک عملیات ورودی/خروجی یا انتقال حافظه در واقع انتقال یک بلاک شامل B عنصر پیوسته از حافظه خارجی به حافظه داخلی می‌باشد و زمان اجرای این الگوریتم با استفاده از تعداد این عملیات‌ها بدست می‌آید.

 الگوریتم 
الگوریتم‌ها در مدل حافظه خارجی این مزیت را دارند که با بدست آوردن یک شیء از حافظهٔ خارجی می‌توان کل بلاک آن شیء را بدست آورد. پیدا کردن یک عنصر میان N عنصر در این مدل با استفاده از یک درخت بی امکان‌پذیر است؛ که در این درخت هر یک از عملیات پیدا کردن، درج کردن و حذف کردن در زمان  انجام می‌شود. مرتب‌سازی خارجی، یک نوع مرتب‌سازی است که روی حافظه خارجی صورت می‌گیرد. این مرتب‌سازی را می‌توان با استفاده از مرتب‌سازی تجمعی که مشابه مرتب‌سازی سریع است انجام داد. زمان این مرتب‌سازی برای مرتب کردن N عنصر  می‌باشد.

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

 موارد مشابه 
 مرتب‌سازی خارجی
 الگوریتم برخط
 الگوریتم جریان داده‌ها

 منابع 

 پیوند به بیرون 
 Out of Core SVD and QR
 Out of core graphics
 Scalapack design

رده:الگوریتم‌ها
رده:تحلیل الگوریتم‌ها
رده:الگوریتم‌های حافظه خارجی
رده:حافظه نهان
رده:مدل‌های محاسباتی