Грешното прогнозиране на условните преходи може многократно да увеличи времето за изпълнение на програмата

Оригиналът е на Даниел Лемире (Daniel Lemire)

17
1710

Съвременните процесори са суперскаларни – тоест, могат да изпълняват няколко инструкции едновременно. Има чипове, които могат да обработват от четири до шест инструкции наведнъж. И освен това, тези процесори могат да изпълняват тези инструкции в различен ред – често срещано е да се започне да се работи с инструкциите, които са много по-назад в кода.

В изпълняваните от процесорите кодове често се срещат условни преходи (операторите if–then). Тези разклонения на кода са познати и като условни преходи, при които процесорът или изпълнява инструкциите към които сочи условният преход или продължава със следващата инструкция.

При суперскаларното изпълнение на процесорните инструкции е трудно и сложно да се работи с почти едновременните условни преходи. Ето защо, в процесорите се вграждат специализирани блокове за прогнозиране изпълнението на условните преходи. Тоест, процесорът се опитва да предскаже какво ще се случи в бъдеще. Когато забележи условен преход, този блок на процесора се опитва да отгатне по кой път ще продължи програмата.

Този метод при повечето случаи работи удивително добре. Така например, повечето цикли са реализирани именно чрез условни преходи. В края на всяка итерация процесорът трябва да предскаже дали ще се изпълни следващата итерация. Често пъти за процесора е по-безопасно да предположи, че цикълът ще продължава вечно. В този случай чипът грешно ще прогнозира само едно завъртане на цикъла.

Има и редица други подобни примери, които са добре известни. Ако е необходим достъп до елементите на масив, то повечето програмни езици преди осъществяването на достъпа до значенията на масива добавят „контрол на границите“ (bound checking) – скрита проверка за правилността на индекса. Ако индексът е неверен, генерира се грешка, а в противен случай кодът се изпълнява по стандартния начин. Проверките на границите са предсказуеми и при обикновена стандартна ситуация всички операции за достъп са правилни. Тоест, повечето процесори почти идеално предсказват ситуации от подобен тип.

Какво се случва, когато е трудно да се предскаже условния преход

В самия процесор, всички инструкции които той е успял да изпълни, но напразно, понеже прогнозирането на условния преход е било погрешно, трябва да бъдат отменени и тези изчисления трябва да бъдат започнати отново. Логично е да се очаква, че за всяка грешка при предсказването на прехода, процесорът заплаща с над 10 цикъла. И това изоставане може многократно да увеличи времето за изпълнение на някои програми.

Нека да разгледаме късче несложен код, с който записваме случайни числа във външен масив:

while (howmany != 0) {
    out[index] =  random();
    index += 1;
    howmany--;
}

Подходящото случайно число се генерира средно за 3 цикъла. Тоест общата латентност на генератора за псевдослучайни числа може да е около 10 цикъла. Но нашият процесор е суперскаларен – тоест едновременно могат да се извършват няколко изчисления на случайни числа. Следователно можем да генерираме ново случайно число не за 10, а на всеки 3 цикъла.

Нека малко да променим тази функция по такъв начин, че в масива да се записват само нечетните случайни числа:

while (howmany != 0) {
    val = random();
    if( val is an odd integer ) {
      out[index] =  val;
      index += 1;
    }
    howmany--;
}

Може твърде наивно да си помислим, че тази функция може да бъде по-бърза. И наистина, средно взето, трябва да се записва само едно вместо две цели числа. Но в кода има добавен условен преход, като за проверката дали едно цяло число е четно е достатъчно да се провери само един бит.

Направих бенчмарк тестове на тези две функции, написани на C++ и изпълнявани на процесор от фалилията Skylake:

  • Запис на всички случайни числа: 3,3 цикъла за integer
  • Запис само на нечетните случайни числа: 15 цикъла за integer

Интересно, втората функция работи пет пъти по-дълго!

Може да се справим с това? Да. Трябва само да премахнем условния преход. Нечетното цяло число може да бъде характеризирано и по друг начин. Бихме могли да приложим побитово логическо И със значение на аргумента 1. Хитростта тук е, че инкрементрирането на индекса на масива с единица ще се извършва само ако случайното цяло число е нечетно:

while (howmany != 0) {
    val = random();
    out[index] = val;
    index += (val bitand 1);
    howmany--;
}

Хитро решение – в новата версия на функцията винаги записваме случайно число в масива, дори и когато това не се налага. Но така или иначе следващото нечетно случайно число ще изтрие предишното значение в масива, ако то е било четно. На пръв поглед, това си е чиста загуба на ресурси. Но този подход ни избавя от възможността за погрешно прогнозиране на условния преход.

На практика производителността стана почти същата като при първоначалния сорс код и е много по-добра в сравнение с версията с проверката на условие. Ето какво показва бенчмаркът:

  • Запис на всички случайни числа: 3,3 цикъла с масив от цели числа
  • Запис само на нечетни случайни числа: 15 цикъла при integer
  • С премахнат условен преход: 3,8 цикъла за integer

Би ли могъл компилаторът да реши същия проблем самостоятелно? Общо взето, отговорът е отрицателен. Някои компилатори наистина имат опции за напълно изключване на условните преходи, дори и когато в сорс кода има if-then оператори. Така например, условните преходи в понякога могат да бъдат заменени с условно преместване (conditional move), както и с някои други аритметични трикове. Но тези трикове съвсем не са безопасни за използване в компилаторите.

От всичко казано дотук можем да направим очевидния извод, че условните преходи съвсем не са някакъв незначителен проблем, а напротив – оказват огромно влияние на производителността на софтуера, както и косвено на консумираната електрическа енергия от страна на алгоритмите.

Ето го и сорс кода в моето хранилище на Github.

Проектирането и създаването на бенчмаркове е сложна задача: новите процесори се учат да прогнозират резултатите от условните преходи

Вече видяхме, че по-голямата част от изпълнението на дадена програма може да се дължи на невярно предсказани условни преходи. Моят бенчмарк записва в масив 64 милиона случайни целочислени числа. Когато пробвах да записвам само нечетните числа производителността рязко спадна.

Защо използвам точно 64 милиона цели числа, а не например 2000? Или 3501? Ако направим само един тест, то това няма да има значение. Но какво ще стане, ако направим множество тестове? Веднага ще видим, че броят на грешно прогнозираните условни преходи бързо започва да клони към нулата. Ето какви са показателите на процесора Intel Skylake:

Брой тестове Вярно предсказани условни преходи (Intel Skylake)
1 48%
2 38%
3 28%
4 22%
5 14%

Както виждаме от показаните по-долу графично изображение, машинното обучение, заложено в чипа, продължава и по-нататък. Постепенно делът на погрешно прогнозираните разклонения на кода пада до около 2%.

Тоест, ако продължим да измерваме времето, за което се изпълнява една и съща задача, то ще видим, че то става все по-малко, понеже процесорът се учи по-добре да прогнозира резултата. Качеството на това машинно обучение зависи от конкретния модел процесор, като е съвсем логично да предположим, че по-новите процесори ще се учат да прогнозират по-добре.

А как стоят нещата с новите процесори на AMD? Най-новите сървърни процесори на AMD успяват почти идеално да прогнозират и предскажат условните преходи – само след 9 теста погрешността пада до около 0,1%:

Брой тестове Вярно предсказани условни преходи (AMD Rome)
1 52%
2 18%
3 6%
4 2%
5 1%
6 0,30%
7 0,15%
8 0,15%
9 0,10%

 

Но това идеално прогнозиране на процесорите AMD Rome започва да намалява, ако в същия алгоритъм броят на значенията бъде увеличен от 2000 на 10 000 и тогава се налага да се направят повече тестове, след което погрешността отново слиза до 0,1%

Какъв извод можем да направим? Навярно не си струва и няма смисъл да се създават бенчмарк тестове с разклонения в кода с малък брой интерации. Или може би трябва да бъдат направени нови бенчмарк тестове, които показват колко бързо се учи да прогнозира блокът в процесорите, който служи за предсказване осъществяването на условните преходи.

Благодаря на Уел Ърван за предоставените данни за процесора AMD Rome.

0 0 гласа
Оценете статията
Абонирай се
Извести ме за
guest
17 Коментара
стари
нови оценка
Отзиви
Всички коментари