Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
Компилятор теориясында, цикл алмасу – ұялы циклдарда қолданылатын екі итерациялық айнымалының ретін ауыстыру процесі. Ішкі циклда қолданылатын айнымалы сыртқы циклға, ал сыртқы циклда қолданылатын айнымалы ішкі циклға көшеді. Бұл көбінесе көп өлшемді массив элементтеріне жадта сақталған ретімен қол жеткізуді қамтамасыз ету үшін жасалады, бұл деректерге сілтеме жасаудың тиімділігін арттырады. Мысалы, келесі код фрагментін қарастырайық:
In compiler theory, loop interchange is the process of exchanging the order of two iteration variables used by a nested loop. The variable used in the inner loop switches to the outer loop, and vice versa. It is often done to ensure that the elements of a multi dimensional array are accessed in the order in which they are present in memory, improving locality of reference. For example, in the code fragment:
j үшін 0-ден 20-ға дейін
i үшін 0-ден 10-ға дейін
a[i,j] = i + j
for j from 0 to 20
for i from 0 to 10
a[i,j] = i + j
Цикл алмасу нәтижесінде:
loop interchange would result in:
i үшін 0-ден 10-ға дейін
j үшін 0-ден 20-ға дейін
a[i,j] = i + j
for i from 0 to 10
for j from 0 to 20
a[i,j] = i + j
Кейде мұндай түрлендіру массивке тағайындаудың автоматты векторылауы сияқты қосымша оңтайландыру мүмкіндіктерін тудыруы мүмкін.
On occasion, such a transformation may create opportunities to further optimize, such as automatic vectorization of the array assignments.
Бұрандалы алмасудың пайдалылығы
Бұрау алмасудың басты мақсаты – массив элементтеріне қатынауда процессордың кэшін тиімді пайдалану. Процессор массив элементіне алғаш рет қатынасқанда, жадтан кэшке деректердің толық блогын жүктейді. Бұл блок алғашқы элементтен кейін де бірнеше тікелей элементтерді қамтуы мүмкін, сондықтан келесі массив элементіне қатынасқанда ол тікелей кэштен алынады (бұл баяу негізгі жадтан алуға қарағанда жылдам). Егер цикл ішіндегі қатарласа орналасқан массив элементтері әртүрлі кэш блогынан алынса, кэш қателіктері туындайды, ал бұрау алмасу мұны болдырмауға көмектеседі. Бұрау алмасудың тиімділігі қолданылатын аппараттық құрылғының кэш моделіне және компилятор қолданатын массив моделіне байланысты, осы факторлар ескерілуі керек. C бағдарламалау тілінде массив элементтері бір қатарда жадта тікелей сақталады (a[1,1], a[1,2], a[1,3]) – қатар бойынша ретпен. Ал FORTRAN бағдарламалары бір бағандағы массив элементтерін (a[1,1], a[2,1], a[3,1]) баған бойынша ретпен сақтайды. Осылайша, бірінші мысалдағы итерациялық айнымалылардың реті C бағдарламасы үшін қолайлы, ал екінші мысал FORTRAN үшін тиімді. Оптимизациялайтын компиляторлар бағдарламашылардың дұрыс емес ретін анықтап, кэштің жақсы жұмыс істеуін қамтамасыз ету үшін ретті өзгерте алады.
The major purpose of loop interchange is to take advantage of the CPU cache when accessing array elements. When a processor accesses an array element for the first time, it will retrieve an entire block of data from memory to cache. That block is likely to have many more consecutive elements after the first one, so on the next array element access, it will be brought directly from cache (which is faster than getting it from slow main memory). Cache misses occur if the contiguously accessed array elements within the loop come from a different cache block, and loop interchange can help prevent this. The effectiveness of loop interchange depends on and must be considered in light of the cache model used by the underlying hardware and the array model used by the compiler. In C programming language, array elements in the same row are stored consecutively in memory (a[1,1], a[1,2], a[1,3]) ‒ in row major order. On the other hand, FORTRAN programs store array elements from the same column together (a[1,1], a[2,1], a[3,1]), using column major. Thus the order of two iteration variables in the first example is suitable for a C program while the second example is better for FORTRAN. Optimizing compilers can detect the improper ordering by programmers and interchange the order to achieve better cache performance.
Қауіпсіздік
Итерациялық айнымалыларды алмастыру әрқашан қауіпсіз болмайды, өйткені олардың орындалу ретіне қатысты нұсқаулар арасында тәуелділік болуы мүмкін. Компилятор циклдарды қауіпсіз алмастыра алатынын анықтау үшін тәуелділіктерді талдау қажет.
It is not always safe to exchange the iteration variables due to dependencies between statements for the order in which they must execute. To determine whether a compiler can safely interchange loops, dependence analysis is required.