Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Кіріспе
Компьютерлік есептеуде сыртқы жад алгоритмдері немесе ядродан тыс алгоритмдер – компьютердің негізгі жадына бір мезгілде сыймайтын тым үлкен деректерді өңдеуге арналған алгоритмдер. Мұндай алгоритмдер баяу көлемді жадтан (қосымша жадтан), мысалы, қатты дискілерден немесе магниттік таспалардан деректерді тиімді алу және пайдалану үшін оңтайландырылуы керек, сондай-ақ жад компьютерлік желіде орналасқан кезде де. Сыртқы жад алгоритмдері сыртқы жад моделінде талданады.
In computing, external memory algorithms or out of core algorithms are algorithms that are designed to process data that are too large to fit into a computer's main memory at once. Such algorithms must be optimized to efficiently fetch and access data stored in slow bulk memory (auxiliary memory) such as hard drives or tape drives, or when memory is on a computer network. External memory algorithms are analyzed in the external memory model.
Үлгі
Сыртқы жад алгоритмдері сыртқы жад моделі (немесе I/O моделі, немесе дискіге қол жеткізу моделі) деп аталатын есептеудің идеалданған моделінде талданады. Сыртқы жад моделі – RAM машинасы моделіне ұқсас, бірақ негізгі жадқа қосымша кэшпен жабдықталған абстрактілі машина. Бұл модель оқу және жазу операциялары кэште негізгі жадтан әлдеқайда жылдам болатынын, сондай-ақ дискідегі оқу және жазу басын пайдаланып кездейсоқ оқудан гөрі, ұзын тізбектес блоктарды оқу жылдам болатынын көрсетеді. Сыртқы жад моделінде алгоритмнің орындалу уақыты жадқа қажетті оқу және жазу операцияларының санымен анықталады. Бұл модельді 1988 жылы Алок Аггарвал және Джеффри Виттер енгізді. Сыртқы жад моделі кэшті ескермейтін модельмен байланысты, бірақ сыртқы жад моделіндегі алгоритмдер блок өлшемін де, кэш өлшемін де біле алады. Осы себепті бұл модель кейде кэшті ескеретін модель деп те аталады. Модель M көлеміндегі ішкі жад немесе кэшке ие процессордан тұрады, ол шексіз сыртқы жадқа қосылған. Ішкі және сыртқы жад B көлеміндегі блоктарға бөлінеді. Бір кіріс/шығыс немесе жадты ауыстыру операциясы – сыртқы жадтан ішкі жадқа B тізбектес элементтен тұратын блокты жылжытудан тұрады, ал алгоритмнің орындалу уақыты осы кіріс/шығыс операцияларының санымен анықталады. Алгоритмдерге қатысты "ядродан тыс" термині 1971 жылы қолданыла бастады.
External memory algorithms are analyzed in an idealized model of computation called the external memory model (or I/O model, or disk access model). The external memory model is an abstract machine similar to the RAM machine model, but with a cache in addition to main memory. The model captures the fact that read and write operations are much faster in a cache than in main memory, and that reading long contiguous blocks is faster than reading randomly using a disk read and write head. The running time of an algorithm in the external memory model is defined by the number of reads and writes to memory required. The model was introduced by Alok Aggarwal and Jeffrey Vitter in 1988. The external memory model is related to the cache oblivious model, but algorithms in the external memory model may know both the block size and the cache size. For this reason, the model is sometimes referred to as the cache aware model. The model consists of a processor with an internal memory or cache of size M, connected to an unbounded external memory. Both the internal and external memory are divided into blocks of size B. One input/output or memory transfer operation consists of moving a block of B contiguous elements from external to internal memory, and the running time of an algorithm is determined by the number of these input/output operations. An early use of the term "out of core" with respect to algorithms appears in 1971.