Loop unrolling (original) (raw)
Le déroulage de boucle (loop unrolling) est une technique d'optimisation des boucles visant à en augmenter la rapidité d'exécution. Il s'agit de dupliquer le corps de la boucle de manière à éviter de répéter l'instruction de saut. Il est possible ensuite d'appliquer d'autres optimisations (allocation de registre, ordonnancement des instructions) au code après duplication. Cette technique est fréquemment utilisée par les compilateurs optimisants, et permet aussi de générer du code vectoriel à partir d'une boucle. * Portail de la programmation informatique
| Property | Value |
|---|---|
| dbo:abstract | Loop unrolling (manchmal auch Loop unwinding), das „Strecken zyklischer Rechenpläne“ oder „Strecken einer Schleife“, ist eine Optimierungsmethode, die die Laufzeit eines Computerprogramms auf Kosten der Größe seiner Programmdatei beschleunigen kann. Dabei wird eine Schleife * entweder durch eine äquivalente Schleife ersetzt, die mehrere Kopien des Schleifenrumpfes enthält und dafür eine geringere Anzahl an Durchläufen hat, * oder komplett aufgelöst, indem der Schleifenrumpf so oft aneinandergereiht wird, wie die ursprüngliche Anzahl Durchläufe war. Dadurch wird die Schleifenbedingung seltener oder gar nicht mehr überprüft. Es wird ferner oft ermöglicht, anschließend weitere Optimierungen des (entrollten) Schleifenrumpfes durchzuführen. Die Anzahl der Kopien des ursprünglichen Schleifenrumpfes wird Abrollfaktor (englisch unroll factor) genannt. Moderne Compiler versuchen Schleifen automatisch zu entrollen, falls auf Geschwindigkeit optimiert werden soll. Ist bekannt, auf welcher Architektur genau ein Programm später ausgeführt wird, kann eine manuelle Optimierung jedoch überlegen sein. Kommen die Wiederholungen durch Selbst-Aufrufe (Rekursionen) zustande, lassen sich durch Vervielfältigung des Prozedurrumpfes Prozeduraufrufe und -rücksprünge einsparen. In solchen Fällen spricht man von Recursion unrolling. (de) 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. (en) El Desenroscado de bucles (conocido en inglés como loop unrolling o Loop unwinding) es una técnica de optimización de bucles que intenta mejorar la velocidad de ejecución de un programa a costa de aumentar su tamaño binario (Situación de compromiso espacio-tiempo). Esta transformación puede hacerla manualmente el programador o un Compilador optimizador. El objetivo del desenroscado de bucles es incrementar la velocidad del programa al reducir (o eliminar) instrucciones que controlan el bucle, como aritmética de punteros o la verificación de final de bucle en cada iteración; reduciendo la penalización por ramificación además de “ocultar latencias, en particular, la espera de la lectura de datos de memoria”. Para eliminar esta sobrecarga en la computación, los bucles pueden ser reescritos como una repetición de sentencias similares independientes. (es) Le déroulage de boucle (loop unrolling) est une technique d'optimisation des boucles visant à en augmenter la rapidité d'exécution. Il s'agit de dupliquer le corps de la boucle de manière à éviter de répéter l'instruction de saut. Il est possible ensuite d'appliquer d'autres optimisations (allocation de registre, ordonnancement des instructions) au code après duplication. Cette technique est fréquemment utilisée par les compilateurs optimisants, et permet aussi de générer du code vectoriel à partir d'une boucle. * Portail de la programmation informatique (fr) ループ展開（ループてんかい、英語: Loop Unwinding）は、プログラムのサイズを犠牲に実行速度を最適化する（時間と空間のトレードオフ）、と呼ばれる手法の1つである。ループアンローリング（英語: Loop Unrolling）とも呼ぶ。プログラマが手動で行うこともあるし、コンパイラが行うこともある。 ループ展開の目的は、毎回の繰り返しごとに発生する「ループの終了」条件のテストを減少させる（もしくはなくす）事によって、実行速度を向上させることである。ループは、ループ自体を制御するためのオーバーヘッドがなくなるように、独立した命令ブロックの連続に書き換えることができる。 (ja) Lo srotolamento del loop (loop unrolling) è una tecnica di ottimizzazione utilizzata dai compilatori e dai microprocessori per migliorare l'esecuzione dei programmi. Questa tecnica fa parte delle tecniche di trasformazione dei loop e punta a velocizzare il programma riducendo le istruzioni che gestiscono il flusso del loop intervenendo sull'algebra dei puntatori e sui controlli di fine loop. Inoltre, raggruppa istruzioni eseguite in loop diversi in un singolo ciclo in modo tale da ridurre i salti nel codice effettuati durante l'esecuzione. Questa tecnica può essere utilizzata anche per rendere i programmi più facilmente parallelizzabili. Uno degli svantaggi principali del loop unrolling è il maggior uso dei registri del microprocessore ed un codice compilato più grande in termini di dimensioni. (it) Odwijanie pętli jest metodą optymalizacji oprogramowania powodującą przyspieszenie wykonania pętli. Polega na zmianie kodu programu przez kilkukrotne skopiowanie zawartości pętli i odpowiednie zmniejszenie liczby powtórzeń. Dzięki temu eliminuje się niepotrzebne sprawdzanie warunku zakończenia. Przykładowo pętla wykonująca 100 razy funkcję delete(x), również 100 razy sprawdzi warunek zakończenia x<100: for (int x = 0; x < 100; x++) { delete(x); } Można jednak nieznacznie wydłużyć kod powtarzając instrukcję delete(x) oraz zmniejszyć liczbę przejść przez pętlę, przez co wykona się kilkukrotnie mniej sprawdzeń x<100: for (int x = 0; x < 100; x += 5) { delete(x); delete(x+1); delete(x+2); delete(x+3); delete(x+4); } Użycie odwijania pętli zwiększa objętość programu, dlatego potrzebne jest znalezienie optymalnej liczby powtórzeń. Stosowanie odwijania pętli w programowaniu nie jest jednak konieczne ponieważ większość kompilatorów sama znajduje optymalną wersję odwinięcia i umieszcza ją w kodzie wynikowym. (pl) В программировании, размотка цикла (англ. loop unwinding) или раскрутка цикла (англ. loop unrolling) — техника оптимизации компьютерных программ, состоящая в искусственном увеличении количества инструкций, исполняемых в течение одной итерации цикла.В результате применения этой оптимизации увеличивается количество инструкций, которые потенциально могут выполняться параллельно, и становится возможным более интенсивное использование регистров, кэша данных и исполнительных устройств. (ru) 循环展开（Loop unwinding或loop unrolling），是一种牺牲程序的大小来加快程序执行速度的优化方法。可以由程序员完成，也可由编译器自动优化完成。 循环展开最常用来降低循环开销，为具有多个功能单元的处理器提供指令级并行。也有利于指令流水线的调度。 (zh) Розмотування циклу (англ. loop unrolling, loop unwinding) — спосіб, в який намагаються оптимізувати швидкодію програми за рахунок розміру двійкового файлу. Зміни в програмі може робити програміст або оптимізувальний компілятор. Метою розмотування циклу є збільшення швидкодії програми шляхом зменшення (або виключення) інструкцій контролю за циклом, таких як арифметика вказівників і перевірка на завершення циклу на кожній ітерації, зменшення витрат на галуження, а також «приховування латентності, особливо, затримку в читанні даних з пам'яті». Цикли можуть бути перезаписані як послідовності подібних незалежних інструкцій, і таким чином можуть бути усунені накладні витрати обчислення. (uk) |
| dbo:wikiPageExternalLink | http://www.cs.uh.edu/~jhuang/JCH/JC/loop.pdf https://web.archive.org/web/20081201132152/http:/www.nondot.org/~sabre/Mirrored/GraphicsProgrammingBlackBook/gpbb7.pdf http://www.agner.org/optimize/optimizing_assembly.pdf https://archive.org/details/optimizingcompil00rall |
| dbo:wikiPageID | 1052647 (xsd:integer) |
| dbo:wikiPageLength | 27360 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1089205230 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Don't_repeat_yourself dbr:Duff's_device dbr:Branch_predictor dbr:Branch_table dbr:Model_checking dbr:Z/Architecture dbr:Parallel_computing dbr:Readability dbr:C_(programming_language) dbc:Compiler_optimizations dbr:Just-in-time_compilation dbr:Space–time_tradeoff dbr:Formal_verification dbr:Base_address dbr:Machine_code dbr:Loop_fusion dbr:Assembly_language dbc:Articles_with_example_C_code dbc:Parallel_computing dbr:Binary_file dbr:Code_bloat dbr:Dot_product dbr:IBM/360 dbr:Michael_Abrash dbr:Optimizing_compiler dbr:Loop_splitting dbr:Macro_(computer_science) dbr:Inlining dbr:Pointer_arithmetic dbr:Instruction_level_parallelism dbr:Computational_overhead dbr:Loop_transformation |
| dbp:wikiPageUsesTemplate | dbt:Cite_book dbt:Distinguish dbt:Div_col dbt:Div_col_end dbt:Dubious dbt:Hatnote dbt:More_citations_needed dbt:Portal dbt:Reflist dbt:Snd dbt:Compiler_optimizations |
| dcterms:subject | dbc:Compiler_optimizations dbc:Articles_with_example_C_code dbc:Parallel_computing |
| gold:hypernym | dbr:Technique |
| rdf:type | owl:Thing dbo:TopicalConcept yago:WikicatCompilerOptimizations yago:Abstraction100002137 yago:Act100030358 yago:Action100037396 yago:Change100191142 yago:ChangeOfState100199130 yago:Cognition100023271 yago:Concept105835747 yago:Content105809192 yago:Event100029378 yago:Idea105833840 yago:Improvement100248977 yago:Optimization100260051 yago:PsychologicalFeature100023100 yago:YagoPermanentlyLocatedEntity yago:WikicatProgrammingConstructs |
| rdfs:comment | Le déroulage de boucle (loop unrolling) est une technique d'optimisation des boucles visant à en augmenter la rapidité d'exécution. Il s'agit de dupliquer le corps de la boucle de manière à éviter de répéter l'instruction de saut. Il est possible ensuite d'appliquer d'autres optimisations (allocation de registre, ordonnancement des instructions) au code après duplication. Cette technique est fréquemment utilisée par les compilateurs optimisants, et permet aussi de générer du code vectoriel à partir d'une boucle. * Portail de la programmation informatique (fr) ループ展開（ループてんかい、英語: Loop Unwinding）は、プログラムのサイズを犠牲に実行速度を最適化する（時間と空間のトレードオフ）、と呼ばれる手法の1つである。ループアンローリング（英語: Loop Unrolling）とも呼ぶ。プログラマが手動で行うこともあるし、コンパイラが行うこともある。 ループ展開の目的は、毎回の繰り返しごとに発生する「ループの終了」条件のテストを減少させる（もしくはなくす）事によって、実行速度を向上させることである。ループは、ループ自体を制御するためのオーバーヘッドがなくなるように、独立した命令ブロックの連続に書き換えることができる。 (ja) В программировании, размотка цикла (англ. loop unwinding) или раскрутка цикла (англ. loop unrolling) — техника оптимизации компьютерных программ, состоящая в искусственном увеличении количества инструкций, исполняемых в течение одной итерации цикла.В результате применения этой оптимизации увеличивается количество инструкций, которые потенциально могут выполняться параллельно, и становится возможным более интенсивное использование регистров, кэша данных и исполнительных устройств. (ru) 循环展开（Loop unwinding或loop unrolling），是一种牺牲程序的大小来加快程序执行速度的优化方法。可以由程序员完成，也可由编译器自动优化完成。 循环展开最常用来降低循环开销，为具有多个功能单元的处理器提供指令级并行。也有利于指令流水线的调度。 (zh) Loop unrolling (manchmal auch Loop unwinding), das „Strecken zyklischer Rechenpläne“ oder „Strecken einer Schleife“, ist eine Optimierungsmethode, die die Laufzeit eines Computerprogramms auf Kosten der Größe seiner Programmdatei beschleunigen kann. Dabei wird eine Schleife * entweder durch eine äquivalente Schleife ersetzt, die mehrere Kopien des Schleifenrumpfes enthält und dafür eine geringere Anzahl an Durchläufen hat, * oder komplett aufgelöst, indem der Schleifenrumpf so oft aneinandergereiht wird, wie die ursprüngliche Anzahl Durchläufe war. (de) El Desenroscado de bucles (conocido en inglés como loop unrolling o Loop unwinding) es una técnica de optimización de bucles que intenta mejorar la velocidad de ejecución de un programa a costa de aumentar su tamaño binario (Situación de compromiso espacio-tiempo). Esta transformación puede hacerla manualmente el programador o un Compilador optimizador. (es) 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. Loop unrolling is also part of certain formal verification techniques, in particular bounded model checking. (en) Lo srotolamento del loop (loop unrolling) è una tecnica di ottimizzazione utilizzata dai compilatori e dai microprocessori per migliorare l'esecuzione dei programmi. Questa tecnica fa parte delle tecniche di trasformazione dei loop e punta a velocizzare il programma riducendo le istruzioni che gestiscono il flusso del loop intervenendo sull'algebra dei puntatori e sui controlli di fine loop. Inoltre, raggruppa istruzioni eseguite in loop diversi in un singolo ciclo in modo tale da ridurre i salti nel codice effettuati durante l'esecuzione. Questa tecnica può essere utilizzata anche per rendere i programmi più facilmente parallelizzabili. (it) Odwijanie pętli jest metodą optymalizacji oprogramowania powodującą przyspieszenie wykonania pętli. Polega na zmianie kodu programu przez kilkukrotne skopiowanie zawartości pętli i odpowiednie zmniejszenie liczby powtórzeń. Dzięki temu eliminuje się niepotrzebne sprawdzanie warunku zakończenia. Przykładowo pętla wykonująca 100 razy funkcję delete(x), również 100 razy sprawdzi warunek zakończenia x<100: for (int x = 0; x < 100; x++) { delete(x); } for (int x = 0; x < 100; x += 5) { delete(x); delete(x+1); delete(x+2); delete(x+3); delete(x+4); } (pl) Розмотування циклу (англ. loop unrolling, loop unwinding) — спосіб, в який намагаються оптимізувати швидкодію програми за рахунок розміру двійкового файлу. Зміни в програмі може робити програміст або оптимізувальний компілятор. (uk) |
| rdfs:label | Loop unrolling (de) Desenroscado de bucles (es) Déroulage de boucle (fr) Srotolamento del loop (it) Loop unrolling (en) ループ展開 (ja) Odwijanie pętli (pl) Размотка цикла (ru) Розмотування циклу (uk) 循环展开 (zh) |
| owl:differentFrom | dbr:Stack_unwinding dbr:Loop_unswitching |
| owl:sameAs | freebase:Loop unrolling yago-res:Loop unrolling wikidata:Loop unrolling dbpedia-de:Loop unrolling dbpedia-es:Loop unrolling dbpedia-fa:Loop unrolling dbpedia-fr:Loop unrolling dbpedia-it:Loop unrolling dbpedia-ja:Loop unrolling dbpedia-pl:Loop unrolling dbpedia-ru:Loop unrolling dbpedia-sr:Loop unrolling dbpedia-tr:Loop unrolling dbpedia-uk:Loop unrolling dbpedia-zh:Loop unrolling https://global.dbpedia.org/id/oRad |
| prov:wasDerivedFrom | wikipedia-en:Loop_unrolling?oldid=1089205230&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:Loop_unrolling |
| is dbo:wikiPageRedirects of | dbr:Loop_unwinding dbr:Unroll_loops dbr:Unrolling_the_loop dbr:Loop_Unrolling |
| is dbo:wikiPageWikiLink of | dbr:Privatization_(computer_programming) dbr:Register_renaming dbr:Vbcc dbr:Don't_repeat_yourself dbr:Duff's_device dbr:Inline_expansion dbr:Zero-overhead_looping dbr:Matrix_multiplication_algorithm dbr:Eigen_(C++_library) dbr:Branch_table dbr:Copy-and-paste_programming dbr:Halide_(programming_language) dbr:Key_stretching dbr:Profile-guided_optimization dbr:Data-oriented_design dbr:WebCL dbr:Space–time_tradeoff dbr:Samplesort dbr:Find_first_set dbr:Harvard_Mark_I dbr:Haxe dbr:Software_pipelining dbr:Assembly_language dbr:Template_metaprogramming dbr:ILNumerics dbr:Intel_Fortran_Compiler dbr:Optimizing_compiler dbr:Lookup_table dbr:Loop_interchange dbr:Loop_optimization dbr:Loop_unwinding dbr:Explicitly_parallel_instruction_computing dbr:Polytope_model dbr:Trace_scheduling dbr:Unroll_loops dbr:Unrolling_the_loop dbr:Loop_Unrolling |
| is foaf:primaryTopic of | wikipedia-en:Loop_unrolling |