Критерии при векторизации
При генерации кода транслятор должен выбрать такую последовательность команд, которая, не нарушая заданной частичной упорядоченности вхождений, будет оптимальной с точки зрения некоторого критерия. При векторизации таким критерием является число вхождений, допускающих векторное выполнение. Например, во фрагменте цикла:
For i:=1 to n do
Begin
A[i]:=…;…
………………………….
…:=A[i+1]+…;
…………………………..
End;
первое и второе вхождения переменной массива А (а1 и а2) информационно независимы в рамках одной итерации. Поэтому при обычной, т. е. «поитерационной» реализации, генератор кода может выбрать любой порядок расположения вхождений a1 и a2 в теле цикла. Однако, при векторном выполнении вхождения a1 и a2 оказываются информационно-зависимыми, и для сохранения семантики программы вхождение a1 должно быть (векторно) выполнено раньше, чем a2.
Координатный метод заключается в отыскании такого порядка вхождений, при котором наибольшее число из них могут быть выполнены векторно. Для выявления и анализа информационных связей служит понятие итерационного смещения, которое характеризует межитерационную зависимость двух одноименных вхождений.
Так, для пары вхождений a1 и a2 в циклической структуре вида:
For i1:=n1 to m1 do
Begin
…………………………………..
For i2:=n2 to m2 do
Begin
…………………………………..
…………………………………….
……………………………………..
For ik:=nk to mk do
Begin
…a1…a2…
End;
……………………………………
…………………………………..
…………………………………..
End;
…………………………………..
End;
итерационное смещение представляет собой вектор: <аь а2> = = (аb…, аk), а;б{0, 0, +, —, >|<}, /-я компонента которого соответствующему по уровню вложенности циклу for fy: = ... Значение ai означает:
0 — вхождения a1 и а2 независимы на протяжении всего цикла по iy,
О — вхождения а1 и а2 обращаются к одной и той же ячейке памяти в течение одной итерации по if,
-{-(—) —вхождение а1 выполняемое на более ранней (поздней) итерации по ij обращается к той же ячейке памяти, что и а2, выполняемое на более поздней (ранней) итерации;
>)< — порядок, в котором вхождения а1 и а2 обращаются к одной и той же ячейке памяти меняется в течение цикла по ij, или неопределен.
Метки: векторизация, число вхождений, массивы, циклы, транслятор