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

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

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

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

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

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

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

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

منابع

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

الگوریتم‌ها
تحلیل الگوریتم‌ها
حافظه (رایانه)
حافظه نهان
مدل‌های محاسباتی