Разделение и слияние циклов: оптимизации компилятора.
Loop fission and fusion
Оптимизация циклов в программировании: разделение (fission) для многоядерных процессоров и слияние (fusion) для повышения производительности и параллелизма.
Сравнивайте с английским: нажмите на абзац — оригинал откроется в окне. Кнопка EN под абзацем показывает его прямо в тексте.
Введение
В информатике, разделение цикла (или распределение цикла) — это оптимизация компилятора, при которой цикл разбивается на несколько циклов с одинаковым диапазоном индексов, при этом каждый из них выполняет только часть тела исходного цикла. Цель состоит в том, чтобы разбить большое тело цикла на более мелкие, чтобы улучшить использование локальности ссылок. Эта оптимизация наиболее эффективна на многоядерных процессорах, которые могут разделить задачу на несколько подзадач для каждого ядра. И наоборот, слияние циклов (или объединение циклов) — это оптимизация компилятора и преобразование цикла, которое заменяет несколько циклов одним. Другие преимущества слияния циклов заключаются в том, что оно позволяет избежать накладных расходов, связанных со структурами управления циклом, а также в том, что оно позволяет процессору параллелизировать тело цикла, используя параллелизм на уровне инструкций. Это возможно, когда между телами двух циклов отсутствуют зависимости по данным (это резко контрастирует с другим основным преимуществом слияния циклов, описанным выше, которое проявляется только при наличии зависимостей по данным, требующих промежуточного выделения памяти для хранения результатов). Если слияние циклов позволяет устранить избыточные выделения памяти, прирост производительности может быть значительным. Однако, по состоянию на clang 12.0.0 и gcc 11.1, это слияние циклов и удаление избыточных выделений памяти не происходит даже на самом высоком уровне оптимизации. Некоторые языки, специально предназначенные для численных вычислений, такие как Julia, могут иметь встроенную концепцию слияния циклов на высоком уровне, когда компилятор обнаруживает смежные поэлементные операции и объединяет их в один цикл. В настоящее время, для достижения того же синтаксиса в языках общего назначения, таких как C++, функции sin и оператор+ вынуждены пессимистично выделять массивы для хранения своих результатов, поскольку они не знают, в каком контексте они будут вызваны. В 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).