Кіріспе
Кэш өлшеміне қарамастан тиімді I/O алгоритмі. Есептеулерде кэшке бейімделген алгоритм (немесе кэштен тәуелсіз алгоритм) – процессор кэшінің мүмкіндіктерін пайдаланатын, бірақ кэш өлшемі (немесе кэш жолдарының ұзындығы және т.б.) нақты параметр ретінде берілмейтін алгоритм. Оптималды кэшке бейімделген алгоритм – кэшті оптималды түрде пайдаланатын (асимптотикалық жағынан, тұрақты шамаларды ескермейтін) кэшке бейімделген алгоритм. Осылайша, кэшке бейімделген алгоритм әртүрлі кэш өлшемдері бар бірнеше машинада немесе әртүрлі деңгейдегі, әртүрлі өлшемдегі кэштері бар жад иерархиясында өзгеріссіз жақсы жұмыс істеуге арналған. Кэшке бейімделген алгоритмдер нақты циклдық плиткалаумен салыстырылады, ол берілген кэш үшін оптималды өлшемдегі блоктарға проблеманы бөліп шығарады. Матрица көбейту, матрица транспозициясы, сұрыптау және басқа да бірнеше проблемалар үшін оптималды кэшке бейімделген алгоритмдер белгілі. Кейбір жалпы алгоритмдер, мысалы, Cooley-Tukey FFT, параметрлердің белгілі бір таңдауы бойынша кэшке бейімделген. Бұл алгоритмдер тек асимптотикалық жағынан ғана оптималды болғандықтан (тұрақты шамаларды ескермейтін), абсолюттік жағынан оптималды өнімділікке қол жеткізу үшін машинаға қатысты қосымша баптау қажет болуы мүмкін. Кэшке бейімделген алгоритмдердің мақсаты – осындай баптаудың қажетті көлемін азайту. Әдетте, кэшке бейімделген алгоритм рекурсивті «бөліп жеңу» алгоритмімен жұмыс істейді, онда проблема кішірек және кішірек кіші-мәселелерге бөлінеді. Соңында, кэш өлшеміне қарамастан, кэшке сыятын кіші-мәселенің өлшеміне жетеді. Мысалы, матрица көбейтудің оптималды кэшке бейімделген түрі, әрбір матрицаны төрт кіші-матрицаға рекурсивті бөліп, кіші-матрицаларды тереңдік бойынша көбейту арқылы қол жеткізіледі. Нақты машинаны баптау кезінде, төменгі деңгейде нақты кэш өлшемдеріне бағытталған циклдық плиткалауды қолданатын, бірақ әйтпесе кэшке бейімделген алгоритмді пайдаланатын гибридті алгоритм қолданылуы мүмкін.
In computing, a cache oblivious algorithm (or cache transcendent algorithm) is an algorithm designed to take advantage of a processor cache without having the size of the cache (or the length of the cache lines, etc.) as an explicit parameter. An optimal cache oblivious algorithm is a cache oblivious algorithm that uses the cache optimally (in an asymptotic sense, ignoring constant factors). Thus, a cache oblivious algorithm is designed to perform well, without modification, on multiple machines with different cache sizes, or for a memory hierarchy with different levels of cache having different sizes. Cache oblivious algorithms are contrasted with explicit loop tiling, which explicitly breaks a problem into blocks that are optimally sized for a given cache. Optimal cache oblivious algorithms are known for matrix multiplication, matrix transposition, sorting, and several other problems. Some more general algorithms, such as Cooley–Tukey FFT, are optimally cache oblivious under certain choices of parameters. As these algorithms are only optimal in an asymptotic sense (ignoring constant factors), further machine specific tuning may be required to obtain nearly optimal performance in an absolute sense. The goal of cache oblivious algorithms is to reduce the amount of such tuning that is required. Typically, a cache oblivious algorithm works by a recursive divide and conquer algorithm, where the problem is divided into smaller and smaller subproblems. Eventually, one reaches a subproblem size that fits into the cache, regardless of the cache size. For example, an optimal cache oblivious matrix multiplication is obtained by recursively dividing each matrix into four sub matrices to be multiplied, multiplying the submatrices in a depth first fashion. In tuning for a specific machine, one may use a hybrid algorithm which uses loop tiling tuned for the specific cache sizes at the bottom level but otherwise uses the cache oblivious algorithm.
Тарих
Кэшсіз алгоритмдер идеясы (және атауы) Чарльз Э. Лейзерсонның 1996 жылы пайда болған, ал алғаш рет 1999 жылы Массачусетс технология институтында Харальд Прокоп магистрлік диссертациясында жариялаған. Бұрынғы көптеген жұмыстар болған, олар көбінесе нақты проблемаларды талдаған; олар Фриго және т.б. 1999 ж. еңбектерінде егжей-тегжейлі талқыланған. Алғашқы мысалдардың ішінде Синглтонның 1969 жылғы рекурсивті Жылдам Фурье түрлендіруі, Аггарвал және т.б. 1987 жылғы ұқсас идеялары, Фригоның 1996 жылғы матрица көбейту және LU ыдырауы, сондай-ақ Тод Велдхуйзеннің 1996 жылғы Blitz++ кітапханасындағы матрицалық алгоритмдері бар.