Циклдарды бөлу және біріктіру: Компиляторлық оптимизациялар

Цикл бөлу және біріктіру – компиляторлардың оптимизациясы. Локальды жадты жақсарту, көп ядролы процессорларда өнімділікті арттыру мақсатымен циклдар өзгертіледі.

Кіріспе

Компьютерлік ғылымда циклдың бөлінуі (немесе циклдың таралуы) — бұл компилятордың оптимизациясы, онда цикл бірдей индекс диапазонында бірнеше циклға бөлінеді, әрқайсысы бастапқы цикл денесінің тек бір бөлігін орындайды. Мақсаты – үлкен цикл денесін кішірек бөліктерге бөліп, деректерге сілтеме жасаудың тиімділігін арттыру. Бұл оптимизация көп ядролы процессорларда ең тиімді, себебі олар бір тапсырманы әр процессор үшін бірнеше тапсырмаға бөле алады. Керісінше, циклдың біріктірілуі (немесе циклдың жабысуы) — компилятордың оптимизациясы және циклды түрлендіру, ол бірнеше циклды бір циклға алмастырады. Циклдың біріктірілуінің тағы бір артықшылығы — ол цикл басқару құрылымдарының қосымша шығындарын болдырмайды, сонымен қатар цикл денесін процессормен параллельдетуге мүмкіндік береді, нұсқаулар деңгейінде параллелизмді пайдалана отырып. Бұл екі цикл денесі арасында деректерге тәуелділік болмаған жағдайда мүмкін (бұл жоғарыда сипатталған циклдың біріктірілуінің басқа бір маңызды артықшылығына қарама-қарсы келеді, ол тек деректерге тәуелділік болғанда ғана пайда болады, олар нәтижелерді сақтау үшін аралық бөлуді қажет етеді). Егер циклдың біріктірілуі артық бөлінуді жойса, өнімділік айтарлықтай артуы мүмкін. Алайда, clang 12.0.0 және gcc 11.1 нұсқаларында бұл циклдың біріктірілуі және артық бөлінуді жою тіпті ең жоғары оптимизация деңгейінде де жүргізілмейді. Сандық есептеуге бағытталған кейбір тілдер, мысалы, Julia, циклдың біріктірілуі концепциясын жоғары деңгейде енгізген болуы мүмкін, онда компилятор жақын орналасқан элементтік операцияларды анықтап, оларды бір циклға біріктіреді. Қазіргі уақытта, C++ сияқты жалпы мақсаттағы тілдерде осы синтаксиске қол жеткізу үшін sin және operator+ функциялары өз нәтижелерін сақтау үшін массивтерді пессимистік түрде бөлуі керек, себебі олар қандай контексттен шақырылатындығын білмейді. Бұл мәселені C++-да қажетсіз уақытша бөлінуді жою үшін компиляторға сүйенбейтін басқа синтаксис қолдану арқылы шешуге болады (мысалы, оператор+= немесе std::transform сияқты орынды операциялар үшін функциялар мен жүктемелерді пайдалану).

In computer science, loop fission (or loop distribution) is a compiler optimization in which a loop is broken into multiple loops over the same index range with each taking only a part of the original loop's body. The goal is to break down a large loop body into smaller ones to achieve better utilization of locality of reference. This optimization is most efficient in multi core processors that can split a task into multiple tasks for each processor. Conversely, loop fusion (or loop jamming) is a compiler optimization and loop transformation which replaces multiple loops with a single one. Other benefits of loop fusion are that it avoids the overhead of the loop control structures, and also that it allows the loop body to be parallelized by the processor by taking advantage of instruction level parallelism. This is possible when there are no data dependencies between the bodies of the two loops (this is in stark contrast to the other main benefit of loop fusion described above, which only presents itself when there are data dependencies that require an intermediate allocation to store the results). If loop fusion is able to remove redundant allocations, performance increases can be large. However, as of clang 12.0.0 and gcc 11.1, this loop fusion and redundant allocation removal does not occur even on the highest optimization level. Some languages specifically targeted towards numerical computing such as Julia might have the concept of loop fusion built into it at a high level, where the compiler will notice adjacent elementwise operations and fuse them into a single loop. Currently, to achieve the same syntax in general purpose languages like C++, the sin and operator+ functions must pessimistically allocate arrays to store their results, since they do not know what context they will be called from. This issue can be avoided in C++ by using a different syntax that does not rely on the compiler to remove unnecessary temporary allocations (e. g., using functions and overloads for in place operations, such as operator+= or std::transform).