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

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

17
1534

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

В изпълняваните от процесорите кодове често се срещат условни преходи (операторите 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.

17
ДОБАВИ КОМЕНТАР

avatar
4 Коментари
13 Отговори на коментарите
0 Последователи
 
Коментарът с най-много реакции
Най-горещият коментар
  Абонирай се  
нови стари оценка
Извести ме за
saentist
saentist

И така доказваме, че на програмист не трябва да му се дава машина по-млада от 15 години.

Ани
Ани

Това се наблюдава във всички боклуци на Майкрософт от ерата на XP насам. Кодът вече е толкова сбъгясан и задръстен от ненужни простотии ,телеметрия умишлено вградени софтуерни бомби ,че едно 90% от времето на работа на процесора отиват нахалост във изчисления на абсолютно ненужен и безмислен код ,писан умишлено за забавяне на системите и всичко това е за да се купува нов хардуер. Оптимизацията вече отдавна е мъртва и на ниво НУЛА!

Некав
Некав

Седни напиши 2 реда код и тогава давай акъли. Знам, че 80% от колегите ми не стават, но не си мисли, че лесно се прави операционна система. Като не ти харесва, седни напиши една ОС и като си готова след 40 години, дай да я видим. А ако пишеше код, евентуално щеше да си чувала, че много вложени branch statement-и са лоша практика. И накрая, това е проблем на процесора.

Ани
Ани

Я, един от калпавите списвачи се обади засегнат на чест .Добре ,че новият хардуер е мощен та да може с хиляди ядра и нишки да ви побере и изчисли цялата прототия и некомпетентност подскачайки от ядро на ядро все някога работата бива свършена.Какво тук значи някаква си ефективност и надеждност.И всичко това без потребителя да се усети, колко неграмотия има в офиса и в софтуената сапунена опера изобщо наричана за благозувие индустрия.Не ме вълнува като крайна потребитрелка кое е лоша практика бе Муньо. Искам надежден софтуер ,а моят софтуер е бил винаги платен т.е платила съм на Мърльовци правени по… Виж още »

Ремонт Инверторни Електрожени
Ремонт Инверторни Електрожени

Напълно подкрепям позицията на Ани.

Некав
Некав

Ти изглеждаш по- засегната. Ще ти го кажа така – ако искаш качество в строителството, ще си купиш от Артекс. Ако искаш каквото и да е, ще си вземеш ново строителство в Надежда. Ако искаш да ти направят софтуер за нещо, ще си го поръчаш и качеството ще отговаря на цената. Всъщност, имаш избор и в ОС-ите. Има такива, оптимизирани за малък обхват хардуер, купи си от тях. Всъщност, ти не можеш да си позволиш качество. Едно е да си вземеш пералня за 400 лв, друго е за 4000 лв. А в днешни дни качество се предлага основно в индустриален… Виж още »

Ани
Ани

Ти изобщо разбра ли ,че един бъгав Win може да те убие на масата при операция или да се простиш с око при операция на око например ако бъгаво написан софтуер започне да цикли и не се предсказват правилно и вярно преходите на конвейра следва краш,син екран, затлачване 100% натоварване на CPU и горене на енергия без смисъл.Бързо забрави ‘индустриалното качество’ на бозата, заради която вируси криптираха метра и транспортна инфраструктура в цял свят. А контролерите в ядрените централи на Иран те също ли се водят масов софтуер.А проблемите с разнасянето на нишки по всички ядра напред назад от Win… Виж още »

tv entertainment
tv entertainment

Представете си щом телефони с по 4..6 и компютри с по 8 GB RAM лагват, бавят, забиват и се саморестартират спонтанно – за какво качество и алгоритми на работа на софтуера, за какво познаване на хардуера и т. н. става въпрос..!!!

Кольо
Кольо

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

haha
haha

Напълно съм съгласен с Ани , но грубият език – лошо

Некав
Некав

Много филми си гледала. Ползвал съм всичко от Win 95, Както и OS X 10.4, както и от debian 5 насам, както съм работил и с MicroC/OS2. Работя с двата най- известни cloud-а. Откакто знам какво правя, не съм имал проблеми, при това дълги години. Страдаш от проблеми със ЗКУ, специфично МТЮ. Виждам, че хейтиш програмистите, но това си е твой проблем. Да, много стават такива, защото си мислят, че 2 до 10к в момент са пари, но дефакто ако не вадиш 200к долара годишно не си богат, а те така и не стигат и половината. Същото е и при… Виж още »

Кольо
Кольо

поръчай си ти майкрософт да ти напишат софтуер, ама не става нае. Освен ако не извадиш милиони долари, пък и като ОС-ма е скапана и да си платиш на малка софтуерна фирма за читава програмка, това не поправя самата ОС-ма, която си остава все тъй осрана.

Некав
Некав

Като ти е осрана, виждам че разбираш, направи по- добра. Хайде, бай Иване, действай!

Ьнфк
Ьнфк

Ани, прегледай си хормоните…
За всяко нещо си има подходяща ОС.
Тези, които твърдите че нещо изобщо не става сте коне с капаци…

Некав
Некав

Виждаме ънфкд симптоми, като поставяме нея диагнозата „синдром на ЗКУ“, дължащо се на МТЮ. Трудно се лекува.

Зоро
Зоро

На мен програмисти са ми казвали, че въобще не се мъчат да оптимизират кода. Компилаторите и интерпретаторите се занимават с това.

Освен това – времето на програмистите е скъпо, а хардуерът е евтин. По-изгодно е да се купи допълнително RAM отколкото да се остави един програмист (струващ 50 лв на час) да оптимизира код в продължение на седмица.

Некав
Некав

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