Расширенная индексная нотация

Показывать лекцию целиком

Презентацию к лекции Вы можете скачать здесь.

Язык программирования должен предоставлять разработчику удобное средство отображения параллелизма данных в задаче на параллельную архитектуру. Языком, располагающим удобными и разнообразными средствами работы с массивами, является Fortran. В C/C++ нет удобных средств работы с массивами. C/C++ - доминирующий язык разработки приложений.

Массивы – основная структура данных в вычислительных приложениях.

Расширенная индексная нотация – главное отличие Cilk^TM от Cilk^TM Plus.

Определение:

{<имя массива или указатель на него>[<нижняя граница значений индекса>:<длина>[: <шаг изменения индекса>]]}

Символ ":" является указанием на множество элементов массива (секцию или сечение массива).

Символ ":", используемый без указания длины и шага, является указанием на множество всех элементов массива.

Синтаксис расширенной индексной нотации отличается от синтаксиса сечений в Fortran!

Использование расширенной индексной нотации является сигналом компилятору выполнить векторизацию кода. Компилятор векторизует код с расширенной векторной нотацией, отображая его на целевую архитектуру.

Примеры:

A[:]      // Все элементы вектора A
B[3:5]      // Элементы с 3 по 5 массива B
C[:][7]      // Столбец 7 матрицы C
D[0:3:2]    // Элементы 0,2 и 4 массива D
E[0:5][0:4]    // 20 элементов с E[0][0] по E[5][4]

Большинство "стандартных" арифметических и логических операций C/C++ могут применяться к секциям массивов:

+, -, *, /, %, <,==,!=,>,|,,^,,||,!,-(unary), +(unary),++,--, +=, -=, *=, /=, *(p)

Операторы применяются ко всем элементам секции массива:

a[:] * b[:]      // поэлементное умножение
a[3:2][3:2] + b[5:2][5:2]   // сложение матриц 2x2

Операции могут выполняться с разными элементами параллельно.

Секции, используемые в качестве операндов, должны быть конформными (иметь одинаковые ранг и экстент):

a[0:4][1:2] + b[1:2]    // так не должно быть!

Скалярный операнд автоматически расширяется до секции необходимой формы:

a[:][:] + b[0][1]    // сложение b[0][1] со всеми элементами матрицы a

Оператор присваивания выполняется параллельно для всех элементов секции:

a[0:n] = b[0:n] + 1;

Ранги правой и левой частей должны совпадать. Допустимо использование скалярных величин:

a[:] = c;      // c заполняет массив a
e[:] = b[:][:];      // ошибка!

Допустимо пересечение правой и левой частей в операторе присваивания (в этом случае используются временные массивы):

a[1:s] = a[0:s] + 1;    // используется старое значение a[1:s-1]

Поэлементные векторные операции

Пример:

a[:]+b[:]

Пример. Сложение двух массивов

#include <iostream>
int main() {
   double a[4] = {1.,2.,3.,4.};
   double b[4] = {5.,7.,11.,13.};
   double c[4] = {0.,0.,0.,0.};

   std::cout << "Вывод a:\n" << a[:] << " ";
   std::cout << std::endl << std::endl;
   std::cout << "Вывод b:\n" << b[:] << " ";
   std::cout << std::endl << std::endl;

   std::cout << "Вывод c:\n" << c[:] << " ";
   std::cout << std::endl << std::endl;

   c[:] = a[:] + b[:];

   std::cout << "c = a + b:\n" << c[:] << " ";
   std::cout << std::endl << std::endl;
}

Пример. Операции с маской

#include <iostream>
int main() {
   bool x[4] = {0, 0, 1, 1};
   bool y[4] = {0, 1, 1, 0};
   double a[4] = {1.,2.,3.,4.};
   double b[4] = {5.,7.,11.,13.};
   double c[4] = {0.,0.,0.,0.};
   std::cout << "Вывод a:\n" << a[:] << " ";
   std::cout << std::endl << std::endl;

   std::cout << "Вывод b:\n" << b[:] << " ";
   std::cout << std::endl << std::endl;

   std::cout << "Вывод до c:\n" << c[:] << " ";
   std::cout << std::endl << std::endl;
   
   c[:] = x[:]  y[:] ? a[:] : b[:];
 
   std::cout << " Вывод после c:\n" << c[:] << " ";
   std::cout << std::endl << std::endl;
}

Пример. Реализация со встроенными функциями

#include <pmmintrin.h>
void foo(float* dest, short* src, long len, float a) {
   __m128 xmmMul = _mm_set1_ps(a);
   for(long i = 0; i < len; i+=8) {
    __m128i xmmSrc1i = _mm_loadl_epi64((__m128i*) src[i]);
    __m128i xmmSrc2i = _mm_loadl_epi64((__m128i*) src[i+4]);

    xmmSrc1i = _mm_cvtepi16_epi32(xmmSrc1i);
    xmmSrc2i = _mm_cvtepi16_epi32(xmmSrc2i);

    __m128 xmmSrc1f = _mm_cvtepi32_ps(xmmSrc1i);
    __m128 xmmSrc2f = _mm_cvtepi32_ps(xmmSrc2i);

    xmmSrc1f = _mm_mul_ps(xmmSrc1f, xmmMul);
    xmmSrc2f = _mm_mul_ps(xmmSrc2f, xmmMul);

    _mm_store_ps(dest[i], xmmSrc1f);
    _mm_store_ps(dest[i+4], xmmSrc2f);
   }
}

Сравнение машинных кодов для обеих реализаций

Интринсики (встроенные функции)

movq      (%rsi,%rax,2), %xmm1                          #9.18
movq      8(%rsi,%rax,2), %xmm2                         #10.18
pmovsxwd  %xmm1, %xmm1                                  #9.18
pmovsxwd  %xmm2, %xmm2                                  #10.18
cvtdq2ps  %xmm1, %xmm3                                  #12.25
cvtdq2ps  %xmm2, %xmm4                                  #13.25
mulps     %xmm0, %xmm3                                  #15.18
mulps     %xmm0, %xmm4                                  #16.18
movaps    %xmm3, (%rdi,%rax,4)                          #18.21
movaps    %xmm4, 16(%rdi,%rax,4)     ,                  #19.21
addq      $8, %rax                                      #5.34
cmpq      %rdx, %rax                                    #5.24
jl        ..B1.3        # Prob 82%                      #5.24

Индексная нотация

movq      (%rsi,%rcx,2), %xmm2                          #2.45
pmovsxwd  %xmm2, %xmm2                                  #2.45
cvtdq2ps  %xmm2, %xmm3                                  #2.45
mulps     %xmm1, %xmm3                                  #2.58
movaps    %xmm3, (%rdi,%rcx,4)                          #2.15
movq      8(%rsi,%rcx,2), %xmm4                         #2.45
pmovsxwd  %xmm4, %xmm4                                  #2.45
cvtdq2ps  %xmm4, %xmm5                                  #2.45
mulps     %xmm1, %xmm5                                  #2.58
movaps    %xmm5, 16(%rdi,%rcx,4)  ,                     #2.15
addq      $8, %rcx                                      #2.15
cmpq      %r8, %rcx                                     #2.15
jb        ..B1.15       # Prob 44%                      #2.15

Операции сбора/распределения данных

В качестве индекса массива можно использовать сечение массива. Элементы сечения в этом случае определят множество значений индекса.

Примеры:

a[b[0:s]] = c[:]    // a[b[0]]=c[0],a[b[1]]=c[1],… 
c[0:s] = a[b[:]]    // c[0]=a[b[0]],c[1]=a[b[1]],…

Компилятор при использовании таких конструкций генерирует машинный код операций сбора и распределения данных для соответствующей целевой архитектуры.

Пример использования операций распределения/сбора данных:

void fnc1(float *dest, float *src, unsigned int *ind_dest, unsigned int *ind_src, int len) {
   dest[ind_dest[0:len]] = src[ind_src[0:len]];
}

#include <iostream>
void foo(float *dest, float *src, unsigned int *ind_dest, unsigned int *ind_src, int len);

int main() {
   float x[5] = {1., 2., 3., 4., 5.};
   float y[5] = {0., 0., 0., 0., 0.};
   unsigned int y_ind[5] = {4,3,2,1,0};
   unsigned int x_ind[5] = {1, 3, 0, 2, 4};
   std::cout << "x: " << x[:] << " ";
   std::cout << std::endl << std::endl;
   std::cout << "y: " << y[:] << " ";
   std::cout << std::endl << std::endl;
   fnc1(y, x, y_ind, x_ind, 5);
   std::cout << "y: " << y[:] << " ";
   std::cout << std::endl << std::endl;
   return(0);
}

Операции линейного/циклического сдвига

Поддерживаются операции линейного и циклического ("ротация") сдвига.

Примеры:

b[:] = __sec_shift(a[:], shift_val, fill_value);
b[:] = __sec_rotate(a[:], shift_val);

Параметр shift_val определяет величину сдвига, а fill_value - значение, которым заполняются "освободившиеся" позиции массива a.

О многомерных массивах

Для работы с сечениями многомерных массивов компилятору необходимо "знать" форму массива.

В C/C++ есть следующие способы описания формы массива:

массив фиксированного размера:

float a[100][50];

динамический массив:

typedef int (*a2d)[10];    // указатель на вектор a2d *p;
p = (a2d) malloc(sizeof(int)*rows*10);
p[5][:] = 42;      // задать элементы 5-й строки
p[0:rows][:] = 42;    // задать все элементы массива
p[:][:] = 42;      // ошибка (размер строки должен быть задан явно)

Массивы как аргументы

Сечение массива можно использовать в качестве аргумента функции. Фактические и формальные аргументы должны быть согласованы.

Пример:

void saxpy_vec(int m, float a, float restrict x[m], float restrict y[m]) 
{
  y[:] += a * x[:];
}

cilk_for(int i = 0; i < n; i += 256)  
  saxpy_vec(112, 1.7, x[i],y[i]);

Примеры

Модификация подматрицы размером $$m \times n$$, начиная с элемента (i, j):

vx[i:m][j:n] += a*(U[i:m][j+1:n]-U[i:m][j:n]);

Использование элементной функции:

theta[0:n] = atan2(y[0:n],1.0);

Сбор/распределение данных:

w[0:n] = x[i[0:n]];
y[i[0:n]] = z[0:n];

Использование сечения массива в условном операторе (выполняются обе ветви):

if(a[0:n] < b[0:n]) 
  c[0:n] += 1;
else
  c[0:n] -= 1;

Умножение полиномов

Умножение полиномов $$c = a \cdot b$$:

$$\begin{tabular}{rrrrrrrrr|r} x^2 + 2x + 3 $\mathbf{b}$\\ x^2 + 4x + 5 $\mathbf{a}$\\ \hline 5x^2 + 10x + 15 \\ 4x^3 + 8x^2 + 12x \\ x^4 + 2x^3 + 3x^2 \\ \hline x^4 + 6x^3 + 16x^2 + 22x + 15 $\mathbf{c}$\\ \end{tabular} $$

Хранение коэффициентов:

Векторная реализация (сложность $$\Theta (n^2)$$):

void simple_mul( T c[], const T a[], const T b[], size_t n ) {
  c[0:2*n-1] = 0;
  for (size_t i=0; i<n; ++i) 
    c[i:n] += a[i]*b[0:n];
}

Алгоритм Карацубы

Алгоритм Карацубы (сложность $$\Theta (n^1^.^5)$$) – оптимален для n = 32 – 1024

$$K = x^\lfloor^n^/^2^\rfloor$$

$$a = a_1K + a_0$$

$$b = b_1K + b_0$$

Вычислить:

$$t_0 = a_0\cdot b_0$$

$$t_1 = (a_0 + a_1)\cdot(b_0 + b_1)$$

$$t_2 = a_1\cdot b_1$$

Тогда:

$$a\cdot b \equiv t_2K^2 + (t_1-t_0-t_2)K + t_0$$

Реализация с помощью сечений:

void karatsuba( T c[], const T a[], const T b[], size_t n ) {
 if( n<=CutOff ) {
    simple_mul( c, a, b, n );
 } else { 
    size_t m = n/2;
    karatsuba( c, a, b, m );      // t₀ = a₀ x b₀
    karatsuba( c+2*m, a+m, b+m, n-m );    // t2 = a₁ x b₁
    temp_space<T> s(4*(n-m));
    T *a_=s.data(), *b_=a_+(n-m), *t=b_+(n-m); 
    a_[0:m] = a[0:m]+a[m:m];      // a_ = (a₀+a₁)
    b_[0:m] = b[0:m]+b[m:m];      // b_ = (b₀+b₁)
    karatsuba( t, a_, b_, n-m );    // t1 = (a₀+a₁) x (b₀+b₁)
    t[0:2*m-1] -= c[0:2*m-1] + c[2*m:2*m-1];  // t = t₁-t₀-t₂
    c[2*m-1] = 0;
    c[m:2*m-1] += t[0:2*m-1];      // c = t₂K₂+(t₁-t₀-t₂)K+t₀
 }
}

Схема распараллеливания:

Занятие пройдено

Предыдущее занятие Занятие пройдено Следующее занятие

Вернуться к учебному плану

Расширенная индексная нотация

Поэлементные векторные операции

Сравнение машинных кодов для обеих реализаций

Операции сбора/распределения данных

Операции линейного/циклического сдвига

О многомерных массивах

Массивы как аргументы

Примеры

Умножение полиномов

Алгоритм Карацубы

Купить дополнительную попытку

Вы действительно хотите купить ещё одну попытку для прохождения тестирования?

Успешно!

Напишите нам, если у вас есть вопросы

Уважаемые пользователи ИНТУИТ!

Уважаемые пользователи ИНТУИТ!

Добро пожаловать на обновлённый сайт НОУ «ИНТУИТ»!