نمایش مبدأ برای الگوریتم حافظه خارجی

در مبحث [[محاسبات]]، [[الگوریتم]]<nowiki/>های حافظه خارجی (الگوریتم‌های خارج از هسته) به الگوریتم‌هایی می‌گویند که به منظور پردازش داده‌هایی طراحی می‌شوند که به دلیل حجم بالا، در [[حافظه اصلی]] رایانه گنجانده نمی‌شوند. این الگوریتم‌ها باید به گونه‌ای طراحی شوند که در بهترین زمان بتوانند به داده‌های درون حافظه‌های کمکی مانند [[درایو دیسک سخت|هارد درایو]]<nowiki/>دسترسی داشته باشند و آن‌ها را استخراج کنند.<ref>[[:en:Jeffrey_Vitter|Vitter]], J. S. (2001). "External Memory Algorithms and Data Structures: Dealing with MASSIVE DATA". ''ACM Computing Surveys''. '''33''' (2): 209–271. [[سیتی‌سیر|CiteSeerX]] [https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.42.7064 10.1.1.42.7064]. [[نشانگر دیجیتالی شیء|doi]]:[[doi:10.1145/384192.384193|10.1145/384192.384193]]</ref><ref>Vitter, J. S. (2008). ''[http://www.ittc.ku.edu/~jsv/Papers/Vit.IO_book.pdf 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 [https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.140.3731 10.1.1.140.3731]. doi:[[doi:10.1561/0400000014|10.1561/0400000014]]. [[شماره استاندارد بین‌المللی کتاب|ISBN]] <bdi>[[:en:Special:BookSources/978-1-60198-106-6|978-1-60198-106-6]]</bdi>.</ref> الگوریتم‌های حافظه خارجی، در مدل حافظه خارجی بررسی می‌شوند.

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

زمان اجرای یک الگوریتم در مدل حافظه خارجی را تعداد خواندن و نوشتن‌هایی که بر روی حافظه انجام می‌شود تعیین می‌کند.<ref>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:[[doi:10.1007/978-0-387-39940-9_752|10.1007/978-0-387-39940-9_752]]. [[شماره استاندارد بین‌المللی کتاب|ISBN]]: <bdi>[[:en:Special:BookSources/978-0-387-35544-3|978-0-387-35544-3]]</bdi></ref> این مدل همچنین بیان می‌کند که [[سواد|خواندن و نوشتن]] از حافظه cache بسیار سریع تر از حافظه اصلی است. مدل حافظه خارجی نخستین بار از سوی الوک آگاروال و جفری ویتر در سال ۱۹۸۸ معرفی شد.<ref name=":0">Aggarwal, Alok; Vitter, Jeffrey (1988). "[https://hal.inria.fr/inria-00075827 The input/output complexity of sorting and related problems]". [[:en:Communications_of_the_ACM|''Communications of the ACM''.]] '''31''' (9): 1116–1127. doi:[[doi:10.1145/48529.48535|10.1145/48529.48535]]</ref> این مدل کمی مرتبط با مدل cache-oblivious می‌باشد ولی الگوریتم‌ها در مدل حافظه خارجی ممکن است هم، اندازه بلاک و هم، اندازه حافظه cache را بدانند به همین دلیل گاهی از این مدل تحت عنوان مدل cache-aware یاد می‌کنند<ref>[[اریک دمین|Demaine]], Eric(2002)[http://erikdemaine.org/papers/BRICS2002/paper.pdf cache-oblivious algorithms and data structures]. Lecture Notes from the EEF Summer School on Massive Data Sets. Aarhus: BRICS. </ref>.
[[پرونده:External memory (fa).png|جایگزین=حافظه داخلی و خارجی|بندانگشتی|حافظه نهان سمت چپ M عنصر را در خود ذخیره می‌کند در حالی که حافظه خارجی (سمت راست) نامحدود است.]]
این مدل شامل یک [[واحد پردازش مرکزی|پردازنده]] و حافظه داخلی می‌باشد و همچنین یک حافظه [[حافظه نهان (رایانش)|cache]] در این مدل وجود دارد که اندازه آن را M در نظر می‌گیریم. این cache به یک حافظه خارجی بدون محدودیت متصل است. هردو حافظهٔ داخلی و خارجی به[[بلاک|بلاک‌هایی]] با اندازه B تقسیم می‌شوند. یک عملیات [[ورودی/خروجی]] یا انتقال حافظه در واقع انتقال یک بلاک شامل B عنصر پیوسته از حافظه خارجی به حافظه داخلی می‌باشد و زمان اجرای این الگوریتم با استفاده از تعداد این عملیات‌ها بدست می‌آید.<ref name=":0"/>

== الگوریتم ==
الگوریتم‌ها در مدل حافظه خارجی این مزیت را دارند که با بدست آوردن یک شیء از حافظهٔ خارجی می‌توان کل بلاک آن شیء را بدست آورد. پیدا کردن یک عنصر میان N عنصر در این مدل با استفاده از یک [[درخت بی]] امکان‌پذیر است؛ که در این درخت هر یک از عملیات پیدا کردن، درج کردن و حذف کردن در زمان <math>O(\log_{B}N)</math> انجام می‌شود. [[مرتب‌سازی خارجی]]، یک نوع مرتب‌سازی است که روی حافظه خارجی صورت می‌گیرد. این مرتب‌سازی را می‌توان با استفاده از مرتب‌سازی تجمعی که مشابه [[مرتب‌سازی سریع]] است انجام داد. زمان این مرتب‌سازی برای مرتب کردن N عنصر <math>O(\frac N B \log_{\frac M B} \frac N B)</math> می‌باشد.

== کاربردها ==
این مدل برای تحلیل و بررسی داده‌هایی که به دلیل حجم بالا در حافظه داخلی جا نمی‌شوند بسیار مناسب است.<ref name=":0"/> برای مثال در سیستم‌های جغرافیایی، به خصوص سیستم‌های مدلسازی ارتفاعات که حجم داده‌ها از چندین گیگابایت و حتی ترابایت نیز بیشتر می‌شود از مدل حافظه خارجی استفاده می‌شود.

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

== منابع ==
{{پانویس}}

== پیوند به بیرون ==
* [http://www.tau.ac.il/~stoledo/Bib/Pubs/pp01-qr.pdf Out of Core SVD and QR]
* [http://cis.poly.edu/chiang/Vis02-tutorial4.pdf Out of core graphics]
* [http://www.netlib.org/utk/people/JackDongarra/pdf/ooc-scalapack.pdf Scalapack design]

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