Сравнивайте с английским: нажмите на абзац — оригинал откроется в окне. Кнопка EN под абзацем показывает его прямо в тексте.
Содержание
Введение
Зависимость данных в информатике — это ситуация, когда оператор программы (инструкция) обращается к данным, полученным в результате выполнения предыдущего оператора. В теории компиляторов метод, используемый для выявления зависимостей данных между операторами (или инструкциями), называется анализом зависимостей.
A data dependency in computer science is a situation in which a program statement (instruction) refers to the data of a preceding statement. In compiler theory, the technique used to discover data dependencies among statements (or instructions) is called dependence analysis.
Истинная зависимость (читать после записи)
Истинная зависимость, также известная как зависимость потока или зависимость данных, возникает, когда инструкция зависит от результата предыдущей инструкции. Нарушение истинной зависимости приводит к конфликту "чтение после записи" (RAW). 1. A = 3 2. B = A 3. C = B
A true dependency, also known as a flow dependency or data dependency, occurs when an instruction depends on the result of a previous instruction. A violation of a true dependency leads to a read after write (RAW) hazard. 1. A = 3
2. B = A
3. C = B
Инструкция 3 истинно зависит от инструкции 2, поскольку конечное значение C зависит от инструкции, обновляющей B. Инструкция 2 истинно зависит от инструкции 1, поскольку конечное значение B зависит от инструкции, обновляющей A. Поскольку инструкция 3 истинно зависит от инструкции 2, а инструкция 2 истинно зависит от инструкции 1, инструкция 3 также истинно зависит от инструкции 1. Следовательно, параллелизм на уровне инструкций невозможен в данном примере.
Instruction 3 is truly dependent on instruction 2, as the final value of C depends on the instruction updating B. Instruction 2 is truly dependent on instruction 1, as the final value of B depends on the instruction updating A. Since instruction 3 is truly dependent upon instruction 2 and instruction 2 is truly dependent on instruction 1, instruction 3 is also truly dependent on instruction 1. Instruction level parallelism is therefore not an option in this example.
Зависимость от выхода (запись-после-записи)
Зависимость по результату возникает, когда порядок выполнения инструкций влияет на конечное значение переменной. Нарушение зависимости по результату приводит к конфликту записи после записи (WAW). В приведенном ниже примере существует зависимость по результату между инструкциями 3 и 1 — изменение порядка этих инструкций изменит конечное значение A, следовательно, они не могут быть выполнены параллельно. 1. B = 3 2. A = B + 1 3. B = 7 Как и антизависимости, зависимости по результату являются зависимостями по имени. То есть, они могут быть устранены путем переименования переменных, как показано в следующей модификации приведенного выше примера: 1. B2 = 3 2. A = B2 + 1 3. B = 7
An output dependency occurs when the ordering of instructions will affect the final output value of a variable. A violation of an output dependency leads to an write after write (WAW) hazard. In the example below, there is an output dependency between instructions 3 and 1 — changing the ordering of instructions in this example will change the final value of A, thus these instructions cannot be executed in parallel. 1. B = 3
2. A = B + 1
3. B = 7
As with anti dependencies, output dependencies are name dependencies. That is, they may be removed through renaming of variables, as in the below modification of the above example:
1. B2 = 3
2. A = B2 + 1
3. B = 7
Последствия
Обычные программы пишутся, исходя из предположения о последовательной модели выполнения. В этой модели инструкции выполняются одна за другой, атомарно (то есть в любой момент времени выполняется только одна инструкция) и в порядке, заданном программой. Однако зависимости между операторами или инструкциями могут препятствовать параллелизму — параллельному выполнению нескольких инструкций, будь то с помощью параллелизирующего компилятора или процессора, использующего параллелизм на уровне инструкций. Безответственное выполнение нескольких инструкций без учета связанных зависимостей может привести к риску получения неверных результатов, то есть к возникновению опасностей.
Conventional programs are written assuming the sequential execution model. Under this model, instructions execute one after the other, atomically (i. e., at any given point in time, only one instruction is executed) and in the order specified by the program. However, dependencies among statements or instructions may hinder parallelism — parallel execution of multiple instructions, either by a parallelizing compiler or by a processor exploiting instruction level parallelism. Recklessly executing multiple instructions without considering related dependences may cause danger of getting wrong results, namely hazards.
Актуальность в вычислительной технике
Зависимости данных актуальны в различных областях информатики, в частности, при проектировании процессоров, разработке компиляторов, параллельных вычислениях и конкурентном программировании.
Data dependencies are relevant in various areas of computing, particularly in processor design, compiler construction, parallel computing, and concurrent programming.
Конструкция процессора
Инструкционный конвейер: в процессорах с конвейером несколько инструкций выполняются параллельно на разных стадиях конвейера. При этом необходимо учитывать и обрабатывать зависимости данных между регистрами в конвейере процессора. Наиболее важными являются истинные зависимости, которые разрешаются, например, путем остановки конвейера или пересылки операндов. Выполнение вне порядка: современные процессоры часто выполняют инструкции не в исходном порядке для повышения производительности. При этом необходимо учитывать (в дополнение к зависимостям данных) зависимости по именам регистров, которые разрешаются, например, переименованием регистров или использованием таблицы результатов. Зависимости данных также актуальны для операций доступа к памяти и должны учитываться методами разрешения зависимостей по памяти, которые выполняют инструкции доступа к памяти (загрузки и сохранения) вне порядка программы.
Instruction pipelining: In pipelined processors, multiple instruction are executed in parallel in multiple pipeline stages. Thereby, data dependencies between registers must be respected and handled in the processor pipeline. Most relevant are true dependencies that are resolved e. g. by stalling the pipeline or operand forwarding. Out of order execution: Modern processors often execute instructions out of their original order to improve performance. Thereby, name dependencies between registers must be respected (in addition to data dependencies) and are resolved e. g. by register renaming or scoreboarding. Data dependencies are also relevant for memory accesses and must be respected by memory disambiguation techniques that execute memory access instructions (loads and stores) out of program order.
Конструкция компилятора
Зависимости данных важны для различных оптимизаций компилятора, например:
Data dependencies are relevant for various compiler optimizations, e. g.
Планирование инструкций: Компиляторы должны планировать инструкции таким образом, чтобы учитывать зависимости данных. Это критически важно в оптимизирующих компиляторах, которые переупорядочивают код для повышения производительности. Трансформации циклов: При оптимизации циклов компиляторам необходимо учитывать зависимости данных для применения таких преобразований, как разворачивание цикла, объединение или разбиение на блоки, не изменяя при этом семантику программы. Перемещение кода: Когда компилятор рассматривает возможность перемещения фрагмента кода, он должен убедиться, что зависимости данных не нарушаются.
Instruction scheduling: Compilers must schedule instructions in a way that respects data dependencies. This is crucial in optimizing compilers that rearrange code for better performance. Loop transformations: In optimizing loops, compilers need to consider data dependencies to apply transformations like loop unrolling, fusion, or tiling without changing the semantics of the program. Code motion: When a compiler considers moving a piece of code, it must ensure that data dependencies are not violated.