Циклды ашу (loop unrolling) – бағдарлама жылдамдығын арттыру тәсілі. Код көлемін ұлғайту арқылы цикл басқару нұсқауларын азайтады, бірақ қазіргі процессорларда тиімсіз болуы мүмкін.
Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
Циклдік трансформация техникасы
Loop transformation technique
Циклді ашу, сондай-ақ циклді жаю деп те аталады, бұл бағдарламаның орындалу жылдамдығын оның бинарлық көлемі есебінен оңтайландыруға бағытталған циклдік трансформация әдісі, бұл кеңістік-уақыт айырбасы деп аталады. Трансформацияны бағдарламашы немесе оңтайландырушы компилятор қолмен жүзеге асыруы мүмкін. Қазіргі заманғы процессорларда циклді ашу көбінесе нәтижесіз болады, себебі код көлемінің ұлғаюы кэштен деректердің жоғалуына әкелуі мүмкін; cf. Даффтың құрылғысы. Циклді жаюдың мақсаты – циклді басқаратын нұсқауларды азайту немесе жою арқылы бағдарламаның жылдамдығын арттыру, мысалы, көрсеткіш арифметикасы және әр итерациядағы «цикл соңы» тексерулері; тармақталу салдарынан туындайтын кешігулерді азайту; сондай-ақ жадтан деректерді оқу кешігуі сияқты жасырын кідірістерді жою. Бұл есептеу шығындарын жою үшін циклдар ұқсас тәуелсіз операторлардың қайталама тізбегі ретінде қайта жазылуы мүмкін. Циклді ашу белгілі бір формалды тексеру техникаларының, әсіресе шектелген модельді тексерудің бір бөлігі болып табылады.
Loop unrolling, also known as loop unwinding, is a loop transformation technique that attempts to optimize a program's execution speed at the expense of its binary size, which is an approach known as space–time tradeoff. The transformation can be undertaken manually by the programmer or by an optimizing compiler. On modern processors, loop unrolling is often counterproductive, as the increased code size can cause more cache misses; cf. Duff's device. The goal of loop unwinding is to increase a program's speed by reducing or eliminating instructions that control the loop, such as pointer arithmetic and "end of loop" tests on each iteration; reducing branch penalties; as well as hiding latencies, including the delay in reading data from memory. To eliminate this computational overhead, loops can be re written as a repeated sequence of similar independent statements. Loop unrolling is also part of certain formal verification techniques, in particular bounded model checking.
Артықшылықтар
"Тығыз" циклдердегі қосымша шығындар көбінесе массивтегі келесі элементке көрсеткішті немесе индексті жылжыту нұсқауларынан (көрсеткіш арифметикасы), сондай-ақ "цикл аяқталуы" тексерулерінен тұрады. Егер оңтайландырылатын компилятор немесе ассемблер әрбір жеке сілтемеленген массив айнымалысына қадамдарды алдын ала есептей алса, оларды тікелей машиналық код нұсқауларына енгізуге болады, демек, орындалу кезінде қосымша арифметикалық операциялар қажет болмайды. Бағдарлама көлемінің ұлғаюынан туындаған өнімділік төмендеуін орындалатын нұсқаулардың азаюы толықтыра алса, айтарлықтай пайда алуға болады. Тармаққа байланысты кешігу азаяды. Циклдегі операторлар бір-біріне тәуелсіз болса (яғни, циклде ертерек орындалған операторлар келесі операторларға әсер етпесе), операторлар параллель түрде орындалуы мүмкін. Массив элементтерінің саны компиляция уақытында белгісіз болса (мысалы, Дафф құрылғысындай), динамикалық түрде жүзеге асырылуы мүмкін. Оңтайландырылатын компиляторлар кейде бұл өзгертуді автоматты түрде немесе сұраныс бойынша жасайды.
The overhead in "tight" loops often consists of instructions to increment a pointer or index to the next element in an array (pointer arithmetic), as well as "end of loop" tests. If an optimizing compiler or assembler is able to pre calculate offsets to each individually referenced array variable, these can be built into the machine code instructions directly, therefore requiring no additional arithmetic operations at run time. Significant gains can be realized if the reduction in executed instructions compensates for any performance reduction caused by any increase in the size of the program. Branch penalty is minimized. If the statements in the loop are independent of each other (i. e. where statements that occur earlier in the loop do not affect statements that follow them), the statements can potentially be executed in parallel. Can be implemented dynamically if the number of array elements is unknown at compile time (as in Duff's device). Optimizing compilers will sometimes perform the unrolling automatically, or upon request.
Кемшіліктер
Бағдарламалық кодтың көлемінің артуы, әсіресе кіріктірілген қосымшалар үшін жағымсыз болуы мүмкін, сонымен қатар нұсқаулар кэшінің қателіктерінің көбеюіне әкелуі мүмкін, бұл өнімділікке кері әсер етеді. Егер оптимизациялайтын компилятор бұл өзгерісті автоматты түрде жасамаса, кодты түсіну қиындауы мүмкін. Егер цикл ішіндегі код функцияларды шақыратын болса, циклды ашу мен функцияны ішкі кодқа енгізуді бірге қолдану мүмкін болмайды, себебі кодтың көлемі тым артық көбеюі мүмкін. Сондықтан, бұл екі оңтайландырудың арасында таңдау жасау қажет болуы мүмкін. Сонымен қатар, уақытша айнымалыларды сақтау үшін бір итерацияда қолданылатын регистрлердің саны артуы мүмкін, бұл өнімділікті төмендетуі мүмкін, бірақ бұл мүмкін болатын оптимизацияларға байланысты. Көбінесе өте кішкентай және қарапайым код болмаса, тармақтарды қамтитын ашылған циклдар рекурсиядан да баяу жұмыс істейді.
Increased program code size, which can be undesirable—particularly for embedded applications—can also cause an increase in instruction cache misses, which may adversely affect performance. Unless performed transparently by an optimizing compiler, the code may become less readable. If the code in the body of the loop involves function calls, it may not be possible to combine unrolling with inlining, since the increase in code size might be excessive. Thus, there can be a trade off between the two optimizations. Possible increased register usage in a single iteration to store temporary variables, which may reduce performance, though much will depend on possible optimizations. Apart from very small and simple code, unrolled loops that contain branches are even slower than recursions.
Статикалық/қолмен бұранданы ашу
Қолмен (немесе статикалық) циклды ашу, бағдарламашының циклды талдап, оның қайталануларын циклдің жұмысын азайтатын нұсқаулар тізбегіне түрлендіруімен жүзеге асырылады. Бұл компилятор жасап беретін динамикалық ашудан өзгеше.
Manual (or static) loop unrolling involves the programmer analyzing the loop and interpreting the iterations into a sequence of instructions which will reduce the loop overhead. This is in contrast to dynamic unrolling which is accomplished by the compiler.
Динамикалық ақтау
Бұрауды ашудың пайдасы көбінесе массивтің өлшеміне байланысты болады, ал ол көбінесе орындалу уақытына дейін белгісіз болуы мүмкін. JIT компиляторлары (мысалы) "стандартты" бұрау тізбегін шақыруға немесе әрбір элемент үшін жеке нұсқаулардың (салыстырмалы түрде қысқа) тізбегін жасауға шешім қабылдай алады. Бұл икемділік – циклды ашу контекстінде статикалық немесе қолмен оңтайландыруға қарағанда уақытында оңтайландырудың бір артықшылығы. Мұндай жағдайда, n-нің салыстырмалы түрде кіші мәндерінде үнемдеу әлі де маңызды болуы мүмкін, бұл бағдарламаның көлемін (стандартты кітапхананың бір бөлігі ретінде бір рет қосылуы мүмкін) өте азға (болса да) ұлғайтуды қажет етеді. Ассемблер тілінде бағдарламалайтындар (оның ішінде оңтайландырушы компиляторларды жазатындар) да тиімді тармақ кестелеріне ұқсас әдіс қолданып, динамикалық циклды ашу әдісінен пайда көре алады. Бұл жағдайда, егер белгілі бір массивтегі сілтемелі кез келген өрістің максималды ығысқануы машиналық нұсқаулармен көрсетілетін максималды ығысқанудан кем болса, артықшылық ең жоғары болады (егер одан асып кетсе, құрастырушы ескертеді).
Since the benefits of loop unrolling are frequently dependent on the size of an array—which may often not be known until run time—JIT compilers (for example) can determine whether to invoke a "standard" loop sequence or instead generate a (relatively short) sequence of individual instructions for each element. This flexibility is one of the advantages of just in time techniques versus static or manual optimization in the context of loop unrolling. In this situation, it is often with relatively small values of n where the savings are still useful—requiring quite small (if any) overall increase in program size (that might be included just once, as part of a standard library). Assembly language programmers (including optimizing compiler writers) are also able to benefit from the technique of dynamic loop unrolling, using a method similar to that used for efficient branch tables. Here, the advantage is greatest where the maximum offset of any referenced field in a particular array is less than the maximum offset that can be specified in a machine instruction (which will be flagged by the assembler if exceeded).