Суперскалярный стековий процесор: оптимізація


Продовження серії статей, які розбирають ідею суперскалярного процесора з
OoO і фронтендом стекової машини. Тема даної статті — оптимізація звернень до пам'яті.

Попередні статті:
1 — опис роботи на лінійному шматку
2 — виклик функцій, зберігаємо регістри
3 — виклик функцій, погляд зсередини


Досі ми не звертали уваги на слабке місце всіх стекових машин — надлишкові звернення до пам'яті.

У самому справі, коли наївний кодо-генератор стекової машини хоче отримати значення змінної 'a', він пише інструкцію 'push a'. Можливостей послатися на вже обчислене вираз або його шматок стековий процесор не надає.

Для регістрових процесорів компілятор вирішує цю проблему введенням тимчасових змінних з можливим розміщенням їх у регістрах. Варто придумати подібний механізм і для нашої зовні без-реєстрової архітектури.

Втім, вигадувати щось майже нічого і не треба, «все вже вкрадено до нас»©.
  • введемо апарат закладок (bookmarks)
  • закладка — реєстр, до якого компілятор може звертатися за номером, номери регістра і закладки збігатися не зобов'язані, хоча, це спростило б життя
  • компілятор для кожної функції визначає число закладок, якими він збирається розташовувати
  • при старті функції під закладки виділяється необхідна кількість регістрів, звільнити їх не можна аж до завершення функції
  • закладки потрапляють всередину регістрового вікна і на них діє механізм FILL/SPILL
  • якщо компілятор вважає обчислене значення цінним, то встановлює закладку, наприклад, інструкцією 'bmk 1', що означає: значення на вершині стека відтепер вважається закладкою з номером 1. Чи відбувається при цьому копіювання значення в регістр закладки N1 або підміняється регістр, який відповідає за цю закладку, не важливо, деталі реалізації
  • згодом, коли компілятор потрібно значення з цієї закладки, він може його використовувати, наприклад, так: 'add_bmk 1', тобто значення з вершини стека буде просуммировано зі значенням закладки 1 і заміщено цим значенням
  • з точки зору бекенду процесора, буде породжений старий добрий моп підсумовування двох регістрів в третій
  • виникає необхідність другої лінійки арифметичних і логічних інструкцій (add->add_bmk, mul->mull_bmk, cmp->cmp_bmk), але воно того варте
  • або більш загальний варіант — будь-який з аргументів або результат трьох(двох)-адресної інструкції може бути закладкою
  • можна собі уявити і динамічне виділення закладок, без виділення максимальної їх кількості в цілях оптимізації кількості використаних регістрів, але це (на перший погляд) виглядає занадто жорстоким по відношенню до заліза
В результаті у компілятора є два умовно нових ресурсу для оптимізації.

Перший — виявлення і розміщення закладок, число яких може бути досить великим, воно не обмежено числом наявних реєстрів за відсутністю таких. За великим рахунком це еквівалент локальних змінних, розміщених в «швидкому» стек.

Другий — еквівалентне перетворення виразів до вигляду, в якому максимально проявляється внутрішній паралелізм. Компілятор намагається зменшити висоту дерев виразів за рахунок зростання вшир.

Ну і не забудемо про традиційні техніки оптимізації, які не орієнтовані на регістри та їх розподіл.

Для того, щоб розібратися, як це може бути реалізовано, поглянемо на ті
можливості, які надає нам асемблер LLVM. Не збираємося ж ми насправді ігнорувати весь накопичений у цій області «культурний шар».

LLVM
int a(int m, int n)
{
if (m == 0)
return n + 1;
if (n == 0)
return a(m - 1, 1);
return a(m - 1, a(m, n - 1));
}

отриманий LLVM asm; Function Attrs: nounwind readnone
define i32 @a(i32 %m, i32 %n) #0 {
%1 = icmp eq i32 %m, 0
br i1 %1, label %tailrecurse._crit_edge, label %.lr.ph

tailrecurse._crit_edge:; preds = %tailrecurse.backedge, %0
%n.tr.lcssa = phi i32 [ %n, %0 ], [ %n.tr.be, %tailrecurse.backedge ]
%2 = add nsw i32 %n.tr.lcssa, 1
ret i32 %2

.lr.ph:; preds = %0, %tailrecurse.backedge
%n.tr2 = phi i32 [ %n.tr.be, %tailrecurse.backedge ], [ %n, %0 ]
%m.tr1 = phi i32 [ %4, %tailrecurse.backedge ], [ %m, %0 ]
%3 = icmp eq i32 %n.tr2, 0
%4 = add nsw i32 %m.tr1, -1
br i1 %3, label %tailrecurse.backedge, label %5

; <label>:5; preds = %.lr.ph
%6 = add nsw i32 %n.tr2, -1
%7 = tail call i32 @a(i32 %m.tr1, i32 %6)
br label %tailrecurse.backedge

tailrecurse.backedge:; preds = %5, %.lr.ph
%n.tr.be = phi i32 [ %7, %5 ], [ 1, %.lr.ph ]
%8 = icmp eq i32 %4, 0
br i1 %8, label %tailrecurse._crit_edge, label %.lr.ph
}
Тут ми бачимо одні лише інструкції потоку управління, місць, де могла б проявитися специфіка стекової машини немає (якщо не вважати за таку обчислення +-1).

А як щодо «бабочки» FFT, (це вже скоріше з області data flow)?
фрагмент FFT
for (n = 1; n <= LogN; n++)
{
  rw = Rcoef[LogN — n];
  iw = Icoef[LogN — n];
  if (Ft_Flag == FT_INVERSE) iw = -iw;
  in = ie >> 1;
  ru = 1.0;
  iu = 0.0;
  for (j = 0; j<in; j++)
  {
    for (i = j; i < N; i += ie)
    {
      io = i + in;
      rtp = Rdat[i] + Rdat[io];
      itp = Idat[i] + Idat[io];
      rtq = Rdat[i] — Rdat[io];
      itq = Idat[i] — Idat[io];
      Rdat[io] = rtq * ru — itq * iu;
      Idat[io] = itq * ru + rtq * iu;
      Rdat[i] = rtp;
      Idat[i] = itp;
    }
    sr = ru;
    ru = ru * rw — iu * iw;
    iu = iu * rw + sr * iw;
  }
  ie >>= 1;
}


Тіло самого вкладеного циклів асемблері LLVM
( clang -c b.c -O3 --target=xcore -emit-llvm -S -o b_o3.ll ) виглядає так:
отриманий асемблер LLVM.lr.ph21:; preds = %.preheader19, %.lr.ph21
%i.020 = phi i32 [ %76, %.lr.ph21 ], [ %j.025, %.preheader19 ]
%57 = add nsw i32 %i.020, %54
%58 = getelementptr inbounds double* %Rdat, i32 %i.020
%59 = load double* %58, align 4, !tbaa !1
%60 = getelementptr inbounds double* %Rdat, i32 %57
%61 = load double* %60, align 4, !tbaa !1
%62 = fadd double %59, %61
%63 = getelementptr inbounds double* %Idat, i32 %i.020
%64 = load double* %63, align 4, !tbaa !1
%65 = getelementptr inbounds double* %Idat, i32 %57
%66 = load double* %65, align 4, !tbaa !1
%67 = fadd double %64, %66
%68 = fsub double %59, %61
%69 = fsub double %64, %66
%70 = fmul double %ru.023, %68
%71 = fmul double %iu.024, %69
%72 = fsub double %70, %71
store double %72, double* %60, align 4, !tbaa !1
%73 = fmul double %ru.023, %69
%74 = fmul double %iu.024, %68
%75 = fadd double %74, %73
store double %75, double* %65, align 4, !tbaa !1
store double %62, double* %58, align 4, !tbaa !1
store double %67, double* %63, align 4, !tbaa !1
%76 = add nsw i32 %i.020, %ie.028
%77 = icmp slt i32 %76, %N
br i1 %77, label %.lr.ph21, label %._crit_edge22


У вигляді графа залежностей між інструкціями це виглядає так:

Навскидку, кожна вершина дерева з якої виходить більше одного ребра є кандидатом на звання закладки. Принаймні в тому, що стосується обчислень з плаваючою точкою.

У всякому разі, реалізація описаної архітектури в LLVM не виглядає безнадійним заходом.

Дот-файл, раптом знадобиться:
fft.dotdigraph graphname {
L000 [label="%54"];
L001 [label="%Rdat"];
L002 [label="%Idat"];
L003 [label="%ru.023"];
L004 [label="%iu.024"];
L005 [label="%i.020"];

L02 [label="%57 = add nsw i32 %i.020, %54"];
L03 [label="%58 = getelementptr double* %Rdat, i32 %i.020"];
L04 [label="%59 = load double* %58"];
L05 [label="%60 = getelementptr double* %Rdat, i32 %57"];
L06 [label="%61 = load double* %60"];
L07 [label="%62 = fadd double %59, %61"];
L08 [label="%63 = getelementptr double* %Idat, i32 %i.020"];
L09 [label="%64 = load double* %63"];
L10 [label="%65 = getelementptr double* %Idat, i32 %57"];
L11 [label="%66 = load double* %65"];
L12 [label="%67 = fadd double %64, %66"];
L13 [label="%68 = fsub double %59, %61"];
L14 [label="%69 = fsub double %64, %66"];
L15 [label="%70 = fmul double %ru.023, %68"];
L16 [label="%71 = fmul double %iu.024, %69"];
L17 [label="%72 = fsub double %70, %71"];
L18 [label=«store double %72, double* %60»];
L19 [label="%73 = fmul double %ru.023, %69"];
L20 [label="%74 = fmul double %iu.024, %68"];
L21 [label="%75 = fadd double %74, %73"];
L22 [label=«store double %75, double* %65»];
L23 [label=«store double %62, double* %58»];
L24 [label=«store double %67, double* %63»];

L005->L02; L000->L02; L005->L03; L001->L03;
L03->L04; L001->L05; L02->L05; L05->L06; L04->L07;
L06->L07; L002->L08; L005->L08; L08->L09; L002->L10;
L02->L10; L10->L11; L09->L12; L11->L12; L04->L13;
L06->L13; L09->L14; L11->L14; L003->L15; L13->L15;
L004->L16; L14->L16; L15->L17; L16->L17; L17->L18;
L003->L19; L14->L19; L004->L20; L13->L20; L19->L21;
L20->L21; L10->L22; L21->L22; L07->L23; L03->L23;
L08->L24; L12->L24; L05->L18;
}


Епілог
Ось ми і підійшли до попереднього фінішу.
Розібралися чому потрібно нова архітектура, запропонували варіант рішення.
Спочатку стояло питання, а чи відповідає ця архітектура поставленим вимогам.
І тепер можемо відповісти, так, принаймні у тієї невеликої частини, яку вдалося перевірити, ми отримали
  • очікуване спрощення апаратної частини
  • зовні непомітну масштабованість за кількістю регістрів
  • а також і за кількістю функціональних пристроїв
  • потенційне спрощення компіляторів
На перший (аматорський) погляд, не видно принципові проблеми, що перешкоджають реалізації такої архітектури в «залозі».

Ми навмисно не розглядали такі речі, як:
  • обчислення з плаваючою точкою, потрібен для них окремий стек, ...
  • збереження стану процесора при перемиканні контексту
  • переривання
  • ...
Все це питання важливі, але менш принципові.
А на даний момент автор вважає свою задачу виконаною.

Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.