Питання Чому швидше обробляти сортований масив, ніж несортований масив?


Ось фрагмент коду C ++, який виглядає дуже своєрідним. З якоїсь дивної причини, сортування даних чудесним чином робить код майже в шість разів швидшим.

#include <algorithm>
#include <ctime>
#include <iostream>

int main()
{
    // Generate data
    const unsigned arraySize = 32768;
    int data[arraySize];

    for (unsigned c = 0; c < arraySize; ++c)
        data[c] = std::rand() % 256;

    // !!! With this, the next loop runs faster
    std::sort(data, data + arraySize);

    // Test
    clock_t start = clock();
    long long sum = 0;

    for (unsigned i = 0; i < 100000; ++i)
    {
        // Primary loop
        for (unsigned c = 0; c < arraySize; ++c)
        {
            if (data[c] >= 128)
                sum += data[c];
        }
    }

    double elapsedTime = static_cast<double>(clock() - start) / CLOCKS_PER_SEC;

    std::cout << elapsedTime << std::endl;
    std::cout << "sum = " << sum << std::endl;
}
  • Без std::sort(data, data + arraySize);, код триває 11,54 секунди.
  • За відсортованими даними код виконується в 1,93 секунди.

Спочатку я думав, що це може бути лише аномалією мови або компілятора. Тому я спробував це в Java.

import java.util.Arrays;
import java.util.Random;

public class Main
{
    public static void main(String[] args)
    {
        // Generate data
        int arraySize = 32768;
        int data[] = new int[arraySize];

        Random rnd = new Random(0);
        for (int c = 0; c < arraySize; ++c)
            data[c] = rnd.nextInt() % 256;

        // !!! With this, the next loop runs faster
        Arrays.sort(data);

        // Test
        long start = System.nanoTime();
        long sum = 0;

        for (int i = 0; i < 100000; ++i)
        {
            // Primary loop
            for (int c = 0; c < arraySize; ++c)
            {
                if (data[c] >= 128)
                    sum += data[c];
            }
        }

        System.out.println((System.nanoTime() - start) / 1000000000.0);
        System.out.println("sum = " + sum);
    }
}

З дещо подібним, але менш екстремальним результатом.


Моя перша думка полягала в тому, що сортування вводить дані в кеш, але потім я думав, наскільки нерозумно це тому, що масив був тільки створений.

  • Що відбувається?
  • Чому швидше обробляти сортований масив, ніж несортований масив?
  • Код підсумовує деякі незалежні умови, і порядок не має значення.

21674
2018-06-27 13:51


походження


Тільки для запису. У Windows / VS2017 / i7-6700K 4 ГГц немає різниці між двома версіями. Для обох випадків це займає 0.6s. Якщо кількість ітерацій у зовнішньому циклі збільшується в 10 разів, час виконання також збільшується в 10 разів до 6 с у обох випадках. - mp31415
@ user194715: будь-який компілятор, який використовує a cmov або інша безвідмовна реалізація (наприклад, автоматична векторизація з pcmpgtd) буде мати продуктивність, яка не залежить від даних будь-якого процесора. Але якщо він розгалужений, він буде залежати від сортування на будь-якому ЦП з нездійсненним спекулятивним виконанням. (Навіть високопродуктивні процесори на замовлення використовують галузеве передбачення, щоб уникнути вилучення / декодування бульбашок у відведених гілках, штраф за пропущення менше). - Peter Cordes
Woops ... re: Meltdown and Spectre - KyleMit
@ KyleMit це має щось пов'язане з обома сторонами? Я багато не читав обох - mohitmun
@mohitmun, обидва ці недоліки безпеки вписуються в широку категорію вразливостей, класифікованих як "Атаки цільової ін'єкції" - KyleMit


Відповіді:


Ви жертви передбачення галузі невдача


Що таке галузевий прогноз?

Розглянемо залізничний вузол:

Licensed Image Зображення Механізму, через Wikimedia Commons. Використовується під CC-By-SA 3.0 ліцензія

Тепер ради аргументу, припустімо, це ще в 1800-х роках - перед великою відстані або радіозв'язку.

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

Потяги важкі і мають велику інерцію. Тому вони вічно починають і сповільнюють роботу.

Чи є кращий спосіб? Ви вгадайте, в якому напрямку поїзд поїде!

  • Якщо ви здогадалися, це продовжується.
  • Якщо ви здогадалися неправильно, капітан зупиниться, підтримує та кричить на вас, щоб перевернути перемикач. Тоді він може перезапустити інший шлях.

Якщо ви здогадалися щоразу, поїзд ніколи не доведеться зупинятися.
Якщо ви здогадалися неправильно занадто часто, поїзд буде витрачати багато часу на зупинку, резервне копіювання та перезапуск.


Розглянемо if-statement: На рівні процесора це галузева інструкція:

image2

Ви процесор, і ви бачите філію. Ви не знаєте, яким чином він піде. Що ти робиш? Ви припиняєте виконання та зачекайте, доки попередні інструкції не будуть завершені. Тоді ви продовжуєте вказувати правильний шлях.

Сучасні процесори складні і мають довгі трубопроводи. Тому вони вічно "змиваються" і "уповільнюються".

Чи є кращий спосіб? Ви вгадаєте, в якому напрямку піде галузь!

  • Якщо ви здогадалися, ви продовжуєте виконувати.
  • Якщо ви здогадалися, ви повинні пролити трубопровід і повернути назад до гілки. Тоді ви можете перезапустити інший шлях.

Якщо ви здогадалися щоразу, виконання ніколи не доведеться зупинятися.
Якщо ви здогадалися неправильно занадто часто, Ви витрачаєте багато часу на припинення, відкат і перезавантаження.


Це прогнозування галузі. Я визнаю, що це не найкраща аналогія, оскільки поїзд міг просто сигналізувати напрямок із прапором. Але в комп'ютерах процесор не знає, в якому напрямку гілка піде до останнього моменту.

Отже, як би ви стратегічно здогадалися звести до мінімуму кількість разів, коли поїзд повинен зробити резервну копію та йти на інший шлях? Ви дивитеся на минулу історію! Якщо поїзд йде на 99% часу, то ви припускаєте, що залишилося. Якщо він чергується, то ви чергуєте свої здогади. Якщо це відбувається один раз кожні 3 рази, ви припускаєте те ж саме ...

Іншими словами, ви намагаєтесь визначити схему і дотримуватися її. Це більш-менш, як працює предикатори гілки.

Більшість програм мають добре віддані філії. Отже, сучасні прогнозування галузей, як правило, досягають> 90% ударів. Але коли стикаються з непередбачуваними галузями, що не мають впізнаваних візерунків, прогностичні фактори галузі практично марні.

Подальше читання: Стаття "Прогнозу гілки" на Вікіпедії.


Як натякнули зверху, винуватцем є це якщо-заява:

if (data[c] >= 128)
    sum += data[c];

Зверніть увагу, що дані рівномірно розподілені між 0 і 255. Коли дані сортуються, приблизно перша половина ітерацій не буде вводитися в if-statement. Після цього всі вони ввійдуть в if-statement.

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

Швидка візуалізація:

T = branch taken
N = branch not taken

data[] = 0, 1, 2, 3, 4, ... 126, 127, 128, 129, 130, ... 250, 251, 252, ...
branch = N  N  N  N  N  ...   N    N    T    T    T  ...   T    T    T  ...

       = NNNNNNNNNNNN ... NNNNNNNTTTTTTTTT ... TTTTTTTTTT  (easy to predict)

Проте, коли ці дані є повністю випадковими, прогнозувач галузі виявляється марним, оскільки він не може передбачити випадкові дані. Таким чином, імовірно, буде близько 50% неправильного прогнозування. (не краще, ніж випадкові здогадки)

data[] = 226, 185, 125, 158, 198, 144, 217, 79, 202, 118,  14, 150, 177, 182, 133, ...
branch =   T,   T,   N,   T,   T,   T,   T,  N,   T,   N,   N,   T,   T,   T,   N  ...

       = TTNTTTTNTNNTTTN ...   (completely random - hard to predict)

Так що може бути зроблено?

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

Замінити:

if (data[c] >= 128)
    sum += data[c];

з:

int t = (data[c] - 128) >> 31;
sum += ~t & data[c];

Це виключає гілку і замінює його деякими побічними операціями.

(Зауважте, що це хак не є строго еквівалентним оригіналу if-statement.Але в цьому випадку це дійсно для всіх вхідних значень data[].)

Тести: Core i7 920 @ 3,5 ГГц

C ++ - Visual Studio 2010 - випуск x64

//  Branch - Random
seconds = 11.777

//  Branch - Sorted
seconds = 2.352

//  Branchless - Random
seconds = 2.564

//  Branchless - Sorted
seconds = 2.587

Java - Netbeans 7.1.1 JDK 7 - x64

//  Branch - Random
seconds = 10.93293813

//  Branch - Sorted
seconds = 5.643797077

//  Branchless - Random
seconds = 3.113581453

//  Branchless - Sorted
seconds = 3.186068823

Спостереження:

  • З філією: Існує величезна різниця між відсортованими та несортованими даними.
  • З хаком: Різниця між відсортованими та несортованими даними не існує.
  • У випадку C ++ хакер насправді трохи повільніше, ніж у галузі, коли дані сортуються.

Загальне правило полягає в тому, щоб уникнути залежного від розгалуження даних у критичних циклах. (наприклад, у цьому прикладі)


Оновлення:

  • GCC 4.6.1 with -O3 або -ftree-vectorize на x64 здатний генерувати умовний крок. Отже, немає різниці між відсортованими та несортованими даними - обидва є швидкими.

  • VC ++ 2010 не може генерувати умовні рухи для цієї гілки навіть під /Ox.

  • Intel Compiler 11 робить щось чудесне. Це обмінюється двома циклами, тим самим піднімаючи непередбачувану гілку до зовнішньої петлі. Таким чином, він не тільки імунітет помилкових прогнозів, він також вдвічі швидше, ніж будь-які VC ++ та GCC можуть генерувати! Іншими словами, ICC скористався тестовим циклом, щоб перемогти тест ...

  • Якщо ви надаєте компілятору Intel невід'ємний код, він просто виправляє його векторизовано ... і так само швидко, як і в галузі (з обмінником циклу).

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


28593
2018-06-27 13:56



@Mysticial Щоб уникнути переміщення хакі можна написати щось на зразок int t=-((data[c]>=128)) щоб створити маску. Це також має бути швидше. Було б цікаво дізнатися, чи є компілятор достатньо розумним, щоб вставити умовний крок чи ні. - Mackie Messer
@phonetagger Подивіться на це питання: stackoverflow.com/questions/11276291/... Компілятор Intel наблизився до того, щоб повністю позбутися зовнішнього циклу. - Mysticial
@Novelocrat Тільки половина цього правильна. Переведення 1 в знак-біт, коли він дорівнює нулю, дійсно є UB. Це тому, що це підписане переповнення цілих. Але перенесення 1 з знакового біта - це IB. Правильне зміщення мінус-цілі числа з позначкою - IB. Ви можете перейти до аргументу, що цей C / C ++ не вимагає, щоб верхній біт був індикатором знака. Але деталі реалізації IB. - Mysticial
@Mysticial Дуже дякую за посилання. Це виглядає багатообіцяючим. Я поїду хоч це. Останній запит. Вибачте, але будь ласка, не заперечуйте, могли б ви сказати мені, як це можна зробити int t = (data[c] - 128) >> 31; sum += ~t & data[c]; замінити оригінал if-condition вище? - Unheilig
Граматика в мене хоче, щоб я думав, що це слід читати "... жертва прогнозування гілки не вдаєтьсяуре"а не просто" ... жертва прогнозування галузі не змогла ". - jdero


Прогноз галузі.

За допомогою сортованого масиву - умова data[c] >= 128 є першим false для смуги значень, потім стає true для всіх пізніших значень. Це легко передбачити. За допомогою несортованого масиву ви сплачуєте вартість розгалуження.


3640
2018-06-27 13:54



Чи передбачає прогнозування відгалуження на сортованих масивах та масивах з різними моделями? Наприклад, для масиву -> (10, 5, 20, 10, 40, 20, ...) наступний елемент у масиві з шаблону - 80. Чи буде цей тип масиву збільшуватись завдяки передбаченню гілки котрий наступний елемент є 80, якщо шаблон слідувати? Чи це, як правило, тільки допомагає у сортованих масивах? - Adam Freeman
Отже, в основному все, що я умовно дізнався про великі, - поза вікном? Краще брати витрати на сортування, ніж вартість розгалуження? - Agrim Pathak
@AgrimPathak Це залежить. Для не надто великого вводу алгоритм з вищою складністю швидше, ніж алгоритм з меншою складністю, коли константи менші для алгоритму з вищою складністю. Де точка беззбитковості може бути важко передбачити. Крім того, порівняйте це, місцевість важлива. Великий-О важливий, але це не єдиний критерій виконання. - Daniel Fischer
Коли відбувається прогнозування відгалуження? Коли мова знає, що масив сортується? Я маю на увазі ситуацію масиву, яка виглядає так: [1,2,3,4,5, ... 998,999,1000, 3, 10001, 10002]? Чи буде це затуманити 3 збільшення часу роботи? Чи буде це до тих пір, поки не розсортований масив? - Filip Bartuzi
@FilipBartuzi Branch прогнозування відбувається в процесорі нижче рівня мови (але мова може запропонувати способи, щоб повідомити компілятору те, що імовірно, тому компілятор може виділяти код, який підходить для цього). У вашому прикладі нестандартний 3 призведе до помилкового прогнозування (для відповідних умов, де 3 дає інший результат, ніж 1000), і, таким чином, обробка цього масиву, ймовірно, займе пару десятків або сотні наносекунд довше, ніж відсортований масив, навряд чи коли-небудь помітний. Які витрати часу - це високий рівень помилок, одна помилка в прогнозуванні на 1000 не дуже багато. - Daniel Fischer


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

Тепер, якщо ми подивимося на код

if (data[c] >= 128)
    sum += data[c];

ми можемо визнати сенс цього конкретного if... else... гілка повинна додавати щось, коли умова задовольняється. Цей тип галузі можна легко перетворити в a умовний рух твердження, яке буде складено у умовному інструкції переміщення: cmovl, в x86 система Отже, відгалужується галузь і, таким чином, штраф від передбачуваної податкової гілки.

В C, таким чином C++, заяву, яке скомпільуватиметься безпосередньо (без будь-якої оптимізації) у умовну інструкцію переміщення в x86, є трійковим оператором ... ? ... : .... Таким чином, ми переписамо вищенаведене твердження в еквівалентне:

sum += data[c] >=128 ? data[c] : 0;

Підтримуючи читабельність, ми можемо перевірити коефіцієнт прискорення.

На Intel Core i7-2600K @ 3,4 ГГц та режим випуску Visual Studio 2010, еталон (формат скопійовано з Mysticial):

x86

//  Branch - Random
seconds = 8.885

//  Branch - Sorted
seconds = 1.528

//  Branchless - Random
seconds = 3.716

//  Branchless - Sorted
seconds = 3.71

x64

//  Branch - Random
seconds = 11.302

//  Branch - Sorted
 seconds = 1.830

//  Branchless - Random
seconds = 2.736

//  Branchless - Sorted
seconds = 2.737

Результат є надійним у кількох тестах. Ми отримуємо великий прискорення, коли результат відділення непередбачуваний, але ми трохи страждаємо, коли це передбачувано. Фактично, при використанні умовного переміщення продуктивність однакова незалежно від шаблону даних.

Тепер давайте подивимось детальніше, дослідивши x86 збірка вони генерують. Для простоти ми використовуємо дві функції max1 і max2.

max1 використовує умовну гілку if... else ...:

int max1(int a, int b) {
    if (a > b)
        return a;
    else
        return b;
}

max2 використовує трійковий оператор ... ? ... : ...:

int max2(int a, int b) {
    return a > b ? a : b;
}

На машині x86-64 GCC -S генерує збірку нижче.

:max1
    movl    %edi, -4(%rbp)
    movl    %esi, -8(%rbp)
    movl    -4(%rbp), %eax
    cmpl    -8(%rbp), %eax
    jle     .L2
    movl    -4(%rbp), %eax
    movl    %eax, -12(%rbp)
    jmp     .L4
.L2:
    movl    -8(%rbp), %eax
    movl    %eax, -12(%rbp)
.L4:
    movl    -12(%rbp), %eax
    leave
    ret

:max2
    movl    %edi, -4(%rbp)
    movl    %esi, -8(%rbp)
    movl    -4(%rbp), %eax
    cmpl    %eax, -8(%rbp)
    cmovge  -8(%rbp), %eax
    leave
    ret

max2 використовує набагато менше коду завдяки використанню інструкції cmovge. Але справжня користь - це max2 не включає галузевих стрибків, jmp, що призведе до значного штрафу за ефективність, якщо прогнозований результат неправильний.

Тож чому умовне рух працює краще?

У типовому x86 процесор, виконання інструкції ділиться на кілька етапів. Приблизно, ми маємо різні апаратні засоби для вирішення різних етапів. Тому нам не доведеться чекати завершення однієї інструкції, щоб розпочати новий. Це називається трубопроводів.

У галузевому випадку наступна інструкція визначається попередньою, тому ми не можемо провести конвеєр. Ми повинні чекати або передбачити.

У випадку умовного переміщення команда умовного руху виконання розподілена на кілька етапів, але на попередніх етапах, як Fetch і Decode не залежить від результату попередньої інструкції; лише останні етапи потребують результату. Таким чином, ми чекаємо частки часу виконання одного інструкції. Ось чому умовна версія переміщення є повільною, ніж гілка, коли передбачення легко.

Книга Комп'ютерні системи: перспектива програміста, друге видання це детально пояснює. Ви можете перевірити розділ 3.6.6 для Умовні інструкції щодо переміщення, цілу главу 4 для Архітектура процесора, а також розділ 5.11.2 для спеціального лікування для Шляхи передбачення філій і помилкових прогнозів.

Іноді деякі сучасні компілятори можуть оптимізувати наш код для збірки з більшою продуктивністю, іноді деякі компілятори не можуть (цей код використовує нативний компілятор Visual Studio). Знаючи різницю в продуктивності між гілкою та умовним рухом, коли непередбачувана може допомогти нам написати код з кращою продуктивністю, коли сценарій стає настільки складним, що компілятор не може оптимізувати їх автоматично.


2961
2018-06-28 02:14



Там немає рівня оптимізації за замовчуванням, якщо ви не додасте -O до командних рядків GCC. (І ви не можете мати найгірший англійський ніж мій;) - Yann Droneaud
Мені важко повірити, що компілятор може оптимізувати трійковий оператор краще, ніж це може бути еквівалентне if-statement. Ви показали, що GCC оптимізує трійковий оператор до умовного руху; ви ні показано, що це не робить точно такої ж думки для if-statement. Фактично, згідно з Містичним вище, GCC робить оптимізувати if-statement до умовного руху, що зробить цю відповідь повністю неправильною. - BlueRaja - Danny Pflughoeft
@WiSaGaN Код не демонструє нічого, тому що ваші два частини коду компілюють до того самого машинного коду. Критично важливо, щоб люди не розуміли, що як-то оператор if в вашому прикладі відрізняється від термінара у вашому прикладі. Це правда, що ви володієте подібністю у вашому останньому абзаці, але це не виключає того факту, що решту прикладу є шкідливим. - Justin L.
@WiSaGaN Мій низький потік, безсумнівно, перетвориться на оновлення, якщо ви зміните вашу відповідь, щоб видалити оманливу інформацію -O0 приклад і показати різницю в оптимізований asm на двох ваших тестах. - Justin L.
@UpAndAdam На момент тестування VS2010 не може оптимізувати вихідну гілку в умовний рух, навіть якщо вказати високий рівень оптимізації, тоді як gcc може. - WiSaGaN


Якщо вам цікаво ще більше оптимізацій, які можна зробити для цього коду, подумайте про це:

Починаючи з оригінальної петлі:

for (unsigned i = 0; i < 100000; ++i)
{
    for (unsigned j = 0; j < arraySize; ++j)
    {
        if (data[j] >= 128)
            sum += data[j];
    }
}

За допомогою циклу обміну ми можемо безпечно змінити цей цикл на:

for (unsigned j = 0; j < arraySize; ++j)
{
    for (unsigned i = 0; i < 100000; ++i)
    {
        if (data[j] >= 128)
            sum += data[j];
    }
}

Тоді ви можете побачити, що if умовний постійний протягом всього виконання i петлі, щоб ви могли піднімати if з:

for (unsigned j = 0; j < arraySize; ++j)
{
    if (data[j] >= 128)
    {
        for (unsigned i = 0; i < 100000; ++i)
        {
            sum += data[j];
        }
    }
}

Потім ви бачите, що внутрішній цикл може бути згорнуто в одне єдине вираження, припускаючи, що модель з плаваючою точкою дозволяє це (/ fp: швидко викидається, наприклад)

for (unsigned j = 0; j < arraySize; ++j)
{
    if (data[j] >= 128)
    {
        sum += data[j] * 100000;
    }
}

Це 100 000 разів швидше, ніж раніше


2026
2017-07-03 02:25



Якщо ви хочете обдурити, ви можете також взяти множення поза циклу і зробити суму * = 100000 після петлі. - Jyaif
@ Майкл - Я вважаю, що цей приклад насправді є прикладом петлі-інваріантні підйому (LIH), а НЕ петлі підкачки. У цьому випадку вся внутрішня петля не залежить від зовнішньої петлі, і тому її можна підняти з зовнішньої петлі, після чого результат просто множиться на суму i однієї одиниці = 1е5. Це не має значення для кінцевого результату, але я просто хотів встановити запис прямо, оскільки це така часто відвідувана сторінка. - Yair Altman
Хоча не в простому дусі обміну петель, внутрішнього if на цьому моменті можна перетворити на: sum += (data[j] >= 128) ? data[j] * 100000 : 0; який компілятор може зменшити до cmovge або еквівалент. - Alex North-Keys
Зовнішня петля полягає в тому, щоб зробити час, достатній для внутрішнього циклу, для профілю. Так чому б ви петлі заміни. Зрештою, цей цикл буде видалено в будь-якому випадку. - saurabheights
@saurabheights: Невірне запитання: чому компілятор НЕ циклу обмін. Microbenchmarks важко;) - Matthieu M.


Безперечно, деякі з нас будуть зацікавлені в способах ідентифікації коду, який є проблематичним для прогнозувача гілок процесора. Інструмент Valgrind cachegrind має симулятор прогнозування гілки, активований за допомогою --branch-sim=yes прапор Виконуючи це з прикладів у цьому питанні, число зовнішніх циклів зменшується до 10000 і складається з g++, дає такі результати:

Сортовано:

==32551== Branches:        656,645,130  (  656,609,208 cond +    35,922 ind)
==32551== Mispredicts:         169,556  (      169,095 cond +       461 ind)
==32551== Mispred rate:            0.0% (          0.0%     +       1.2%   )

Без сортування:

==32555== Branches:        655,996,082  (  655,960,160 cond +  35,922 ind)
==32555== Mispredicts:     164,073,152  (  164,072,692 cond +     460 ind)
==32555== Mispred rate:           25.0% (         25.0%     +     1.2%   )

Свердління в лінійний вивід, вироблений компанією cg_annotate ми бачимо за циклом, про який йде мова:

Сортовано:

          Bc    Bcm Bi Bim
      10,001      4  0   0      for (unsigned i = 0; i < 10000; ++i)
           .      .  .   .      {
           .      .  .   .          // primary loop
 327,690,000 10,016  0   0          for (unsigned c = 0; c < arraySize; ++c)
           .      .  .   .          {
 327,680,000 10,006  0   0              if (data[c] >= 128)
           0      0  0   0                  sum += data[c];
           .      .  .   .          }
           .      .  .   .      }

Без сортування:

          Bc         Bcm Bi Bim
      10,001           4  0   0      for (unsigned i = 0; i < 10000; ++i)
           .           .  .   .      {
           .           .  .   .          // primary loop
 327,690,000      10,038  0   0          for (unsigned c = 0; c < arraySize; ++c)
           .           .  .   .          {
 327,680,000 164,050,007  0   0              if (data[c] >= 128)
           0           0  0   0                  sum += data[c];
           .           .  .   .          }
           .           .  .   .      }

Це дозволяє вам легко визначити проблему лінії - в несортованій версії if (data[c] >= 128) лінія викликає 164 050 007 неправильно прогнозованих умовних гілок (Bcm) за моделлю предшественника гілки cachegrind, тоді як у відсортованій версії він лише викликає 10 006.


Крім того, в Linux ви можете використовувати підсистему лічильників продуктивності для виконання того ж завдання, але з власною продуктивністю, використовуючи лічильники процесора.

perf stat ./sumtest_sorted

Сортовано:

 Performance counter stats for './sumtest_sorted':

  11808.095776 task-clock                #    0.998 CPUs utilized          
         1,062 context-switches          #    0.090 K/sec                  
            14 CPU-migrations            #    0.001 K/sec                  
           337 page-faults               #    0.029 K/sec                  
26,487,882,764 cycles                    #    2.243 GHz                    
41,025,654,322 instructions              #    1.55  insns per cycle        
 6,558,871,379 branches                  #  555.455 M/sec                  
       567,204 branch-misses             #    0.01% of all branches        

  11.827228330 seconds time elapsed

Без сортування:

 Performance counter stats for './sumtest_unsorted':

  28877.954344 task-clock                #    0.998 CPUs utilized          
         2,584 context-switches          #    0.089 K/sec                  
            18 CPU-migrations            #    0.001 K/sec                  
           335 page-faults               #    0.012 K/sec                  
65,076,127,595 cycles                    #    2.253 GHz                    
41,032,528,741 instructions              #    0.63  insns per cycle        
 6,560,579,013 branches                  #  227.183 M/sec                  
 1,646,394,749 branch-misses             #   25.10% of all branches        

  28.935500947 seconds time elapsed

Це також може робити анотацію вихідного коду з розбиранням.

perf record -e branch-misses ./sumtest_unsorted
perf annotate -d sumtest_unsorted
 Percent |      Source code & Disassembly of sumtest_unsorted
------------------------------------------------
...
         :                      sum += data[c];
    0.00 :        400a1a:       mov    -0x14(%rbp),%eax
   39.97 :        400a1d:       mov    %eax,%eax
    5.31 :        400a1f:       mov    -0x20040(%rbp,%rax,4),%eax
    4.60 :        400a26:       cltq   
    0.00 :        400a28:       add    %rax,-0x30(%rbp)
...

Побачити підручник з продуктивності для більш детальної інформації.


1690
2017-10-12 05:53



Це страшно, у несортованому списку має бути 50% шансів натиснути додавання. Як-небудь прогнозування галузі має лише 25% пропускної спроможності, як це може бути краще, ніж 50% не вистачає? - TallBrianL
@ tall.b.lo: 25% з усіх галузей - є два філії в петлі, один для data[c] >= 128 (який має 50% пропускну спроможність, як ви пропонуєте), і один для стану циклу c < arraySize яка має рейтинг ~ 0%. - caf


Я просто прочитав це питання і його відповіді, і я відчуваю, що відповідь відсутній.

Загальноприйнятий спосіб уникнути прогнозування гілок, який я виявив особливо добре працювати в керованих мовах, - це пошук за таблицею, а не використання гілки (хоча я і не тестував це в цьому випадку).

Цей підхід працює взагалі, якщо:

  1. Це невеликий стіл і, ймовірно, кешуватиметься в процесорі
  2. Ви використовуєте речі досить щільно, і / або процесор може попередньо завантажувати дані

Передумови і чому

Pfew, так що, чорт це те, що мається на увазі?

З точки зору процесора ваша пам'ять повільна. Щоб компенсувати різницю у швидкості, вони будуються в пару кеш-пам'яті у вашому процесорі (L1 / L2 cache), які компенсують це. Так що уявіть, що ви робите свої приємні розрахунки і з'ясуєте, що вам потрібна частина пам'яті. Процесор отримає операцію "завантаження" та завантажує частину пам'яті в кеш-пам'ять, а потім використовує кеш для виконання інших обчислень. Оскільки пам'ять є відносно повільною, це "навантаження" сповільнить вашу програму.

Як і прогнозування галузі, це було оптимізовано в процесорах Pentium: процесор прогнозує, що йому потрібно завантажити певний фрагмент даних і намагатися завантажити його в кеш-пам'ять, перш ніж операція фактично потрапить до кеша. Як ми вже бачили, прогнозування галузі іноді йде жахливо неправильно - у гіршому випадку потрібно повернутись і фактично чекати навантаження на пам'ять, що триватиме назавжди (Іншими словами: якщо не вдається прогнозувати галузь погано, навантаження на пам'ять після прогання гілки просто жахливо!)

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

Перше, що нам потрібно знати - це те, що є маленький? Хоча менше, як правило, краще, велике правило полягає в тому, щоб дотримуватися таблиць довідки, які мають розмір <= 4096 байт. Як верхня межа: якщо ваш таблиця пошуку більше 64K, це, мабуть, варто переглянути.

Побудова таблиці

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

У цьому випадку:> = 128 означає, що ми можемо зберегти значення, <128 означає, що ми звільнимося від нього. Найпростіший спосіб зробити це - це використання "І": якщо ми будемо тримати це, ми І це з 7FFFFFFF; якщо ми хочемо позбутися від неї, ми І це з 0. Зауважте також, що 128 - це потужність від 2, так що ми можемо йти вперед і зробити таблицю з цілими числами 32768/128 і заповнити її одним нулем і багато 7FFFFFFFF's

Керовані мови

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

Ну, не точно ... :-)

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

for (int i=0; i<array.Length; ++i)
   // Use array[i]

У цьому випадку для компілятора очевидно, що граничне умова ніколи не потрапить. Принаймні, компілятор Microsoft JIT (але я очікую, що Java виконує подібні речі) помітить це і зніме перевірку взагалі. WOW - це означає, що немає гілки. Аналогічним чином, він буде мати справу з іншими очевидними випадками.

Якщо ви зіткнулися з проблемами при пошуку в керованих мовах - ключовим є додавання a & 0x[something]FFFдо функції пошуку, щоб зробити граничну перевірку передбачуваною - і подивитись, як це відбувається швидше.

Результат цього випадку

// Generate data
int arraySize = 32768;
int[] data = new int[arraySize];

Random rnd = new Random(0);
for (int c = 0; c < arraySize; ++c)
    data[c] = rnd.Next(256);

//To keep the spirit of the code in-tact I'll make a separate lookup table
// (I assume we cannot modify 'data' or the number of loops)
int[] lookup = new int[256];

for (int c = 0; c < 256; ++c)
    lookup[c] = (c >= 128) ? c : 0;

// Test
DateTime startTime = System.DateTime.Now;
long sum = 0;

for (int i = 0; i < 100000; ++i)
{
    // Primary loop
    for (int j = 0; j < arraySize; ++j)
    {
        // Here you basically want to use simple operations - so no
        // random branches, but things like &, |, *, -, +, etc. are fine.
        sum += lookup[data[j]];
    }
}

DateTime endTime = System.DateTime.Now;
Console.WriteLine(endTime - startTime);
Console.WriteLine("sum = " + sum);

Console.ReadLine();

1160
2018-04-24 06:26



Ви хочете обійти галузь-предиктор, чому? Це оптимізація. - Dustin Oprea
Оскільки жодна гілка не краща, ніж гілка :-) У багатьох ситуаціях це просто набагато швидше ... якщо ви оптимізуєте, це напевно варто спробувати. Вони також використовують його досить багато в f.ex. graphics.stanford.edu/~seander/bithacks.html - atlaste
Загалом таблиці пошуку можуть бути швидкими, але чи пройшли тести для цього конкретного стану? У вашому коді ви все ще матимете галузевий стан, лише зараз він переміщено до частини генерації таблиць пошуку. Ви як і раніше не отримаєте вашу продуктивність - Zain Rizvi
@ Zain, якщо ви дійсно хочете знати ... Так: 15 секунд з гілкою та 10 з моєю версією. Незважаючи на це, це корисна техніка, щоб знати в будь-якому випадку. - atlaste
Чому ні sum += lookup[data[j]] де lookup це масив із 256 записами, перший з яких - нуль, а останні - рівними індексу? - Kris Vandermotten


Коли дані розподіляються між 0 і 255, коли сортування сортується, навколо першої половини ітерацій не буде вводитись if-задання (the if заява ділиться нижче).

if (data[c] >= 128)
    sum += data[c];

Питання в тому, що робить вищезгадане твердження не виконуваним у певних випадках, як у випадку сортованих даних? Ось іде "галузь прогностичного". Предикатор гілки - це цифрова схема, яка намагається вгадати, в якій гілці (наприклад, an if-then-else структура) піде до того, як це відоме напевно. Мета прогностичного філіалу полягає в тому, щоб поліпшити потік в трубопроводі інструкцій. Прогностичні фактори відіграють вирішальну роль у досягненні високої ефективної продуктивності!

Давайте зробимо якусь наклейку, щоб зрозуміти її краще

Виконання а if-твердження залежить від того, чи має його стан передбачуваний характер. Якщо умова завжди відповідає дійсності або завжди є помилковим, логіка передбачення галузі у процесорі підберуть шаблон. З іншого боку, якщо модель непередбачувана, то if-зтвердження буде набагато дорожче.

Давайте вимірюємо продуктивність цього циклу з різними умовами:

for (int i = 0; i < max; i++)
    if (condition)
        sum++;

Ось таймінг циклу з різними вірно-фальшивими візерунками:

Condition            Pattern                 Time (ms)

(i & 0×80000000) == 0    T repeated          322

(i & 0xffffffff) == 0    F repeated          276

(i & 1) == 0            TF alternating    760

(i & 3) == 0            TFFFTFFF…          513

(i & 2) == 0            TTFFTTFF…          1675

(i & 4) == 0            TTTTFFFFTTTTFFFF… 1275

(i & 8) == 0            8T 8F 8T 8F …     752

(i & 16) == 0            16T 16F 16T 16F … 490

А "поганий"Вірно-фальшивий візерунок може зробити if-виведення до шести разів повільніше, ніж "добре"Шаблон! Звичайно, який зразок хороший, а який поганий залежить від точних інструкцій, створених компілятором і конкретним процесором.

Отже, немає жодних сумнівів щодо впливу галузевих прогнозів на продуктивність!


1035
2018-02-15 07:24



Ви не показуєте терміни "випадкового" шаблону TF. - Mooing Duck
@ MooingDuck ", тому що це не буде мати жодних змін - це значення може бути будь-яким, але він все ще буде в межах цих порогів. Так чому показувати випадкове значення, коли ви вже знаєте межі? Хоча я погоджуюсь, що ви можете показати це заради повноти, і "просто за це". - cst1992
@ cst1992: зараз його найповільніший час - це TTFFTTFFTTFF, який, здається, моєму людському оку, досить передбачуваний. Випадково за своєю суттю непередбачуване, тому цілком можливо, що це буде повільніше, і, отже, за межами показаних тут. OTOH, це може бути те, що TTFFTTFF ідеально потрапляє на патологічну справу. Не можу сказати, оскільки він не показував таймінгів випадковим чином. - Mooing Duck
@MooingDuck Для людського ока "TTFFTTFFTTFF" є передбачуваною послідовністю, але тут мова йде про поведінку інтелектуального інтегратора, вбудованого в процесор. Покажчик філії не є розпізнаванням шаблону рівня AI; це дуже просто. Коли ви просто чергові гілки, це не передбачає добре. У більшості кодів філії подібні майже весь час; Розглянемо цикл, який виконує тисячу разів. Відгалуження в кінці циклу повертається до початку циклу 999 разів, а потім у тисячний час робить щось інше. Зазвичай дуже простий гігантський предиктор працює добре. - steveha
@steveha: Я думаю, ви робите припущення про те, як працює прогностичний фактор процесора, і я не погоджуюсь з цією методологією. Я не знаю, наскільки просунута ця галузь, але я, здається, думаю, що це набагато просунутий, ніж ви. Ви, ймовірно, правильні, але вимірювання, безумовно, буде добре. - Mooing Duck


Один із способів уникнути помилок прогнозування галузі - побудувати таблицю пошуку та індексувати його за допомогою даних. Стефан де Брюін обговорив це у своїй відповіді.

Але в даному випадку ми знаємо, що значення знаходяться в діапазоні [0, 255], і ми тільки дбаємо про значення> = 128. Це означає, що ми можемо легко витягнути один біт, який покаже нам, хочемо чи ні значення: шляхом переміщення дані до правих 7 біт, нам залишилося 0 біт або 1 біт, і ми хочемо лише додати значення, коли маємо 1 біт. Давайте називати це біт "рішення біт".

Використовуючи значення 0/1 біт рішення як індекс у масив, ми можемо зробити код, який буде однаково швидким, чи сортуються дані чи не сортуються дані. Наш код завжди додаватиме значення, але коли біт рішення буде 0, ми додамо значення десь нам не хвилює. Ось код:

// Test
clock_t start = clock();
long long a[] = {0, 0};
long long sum;

for (unsigned i = 0; i < 100000; ++i)
{
    // Primary loop
    for (unsigned c = 0; c < arraySize; ++c)
    {
        int j = (data[c] >> 7);
        a[j] += data[c];
    }
}

double elapsedTime = static_cast<double>(clock() - start) / CLOCKS_PER_SEC;
sum = a[1];

Цей код втрачає половину надбудови, але ніколи не має помилки прогнозування галузі. Це надзвичайно швидше для довільних даних, ніж версія з фактичним оператором if.

Але в моєму тестуванні явний таблиць пошуку було трохи швидше, ніж це, можливо, тому що індексування в таблицю пошуку було трохи швидше, ніж переміщення біт. Це показує, як мій код встановлюється та використовує таблицю пошуку (незважаючи на неї lut для "LookUp Table" у коді). Ось код C ++:

// declare and then fill in the lookup table
int lut[256];
for (unsigned c = 0; c < 256; ++c)
    lut[c] = (c >= 128) ? c : 0;

// use the lookup table after it is built
for (unsigned i = 0; i < 100000; ++i)
{
    // Primary loop
    for (unsigned c = 0; c < arraySize; ++c)
    {
        sum += lut[data[c]];
    }
}

У цьому випадку таблиця пошуку становила лише 256 байт, тому вона добре підходить в кеш-пам'яті, і все було швидко. Ця техніка не буде працювати добре, якщо дані були 24-бітними значеннями, і ми хотіли, щоб половина з них ... таблиця пошуку була б занадто великою, щоб бути практичною. З іншого боку, ми можемо об'єднати дві методики, показані вище: спочатку зсуньте біти, потім індексуйте таблицю пошуку. Для 24-бітового значення, для якого ми хочемо отримати лише значення верхньої половини, ми могли б потенційно змістити дані прямо на 12 біт, і залишити 12-бітним значенням для індексу таблиці. 12-бітний індекс таблиці містить таблиці з 4096 значень, які можуть бути практичними.

EDIT: одна річ, яку я забув вкласти.

Техніка індексації в масив, замість використання if твердження, можна використовувати для визначення того, який покажчик використовувати. Я бачив бібліотеку, яка реалізувала бінарні дерева, і замість того, щоб мати два названих покажчика (pLeft і pRight або будь-який інший) мав довжину-2 масив покажчиків і використовував метод "рішення бит", щоб вирішити, який слід слідувати. Наприклад, замість:

if (x < node->value)
    node = node->pLeft;
else
    node = node->pRight;

ця бібліотека зробить щось на кшталт:

i = (x < node->value);
node = node->link[i];

Ось посилання на цей код: Червоні чорні дерева, Вітчизняний конфезцій


963
2017-07-22 08:29



Правильно, ви також можете просто використовувати біт безпосередньо і помножити (data[c]>>7 - де теж тут обговорюється); Я навмисно залишив це рішення, але, звичайно, ви правильні. Просто невелика примітка: Великий палець для таблиць для пошуку - якщо він вміститься в 4 Кб (через кешування), він буде працювати - бажано зробити таблицю якомога меншою. Для керованих мов я б підштовхнув це до 64 Кб, для мов низького рівня, як C + + і C, я, мабуть, переглянемо (це тільки мій досвід). З тих пір typeof(int) = 4, Я б намагався дотримуватися максимум 10 біт. - atlaste
Я думаю, що індексування з значенням 0/1, швидше за все, буде швидше, ніж ціле множення, але я думаю, якщо продуктивність критично, ви повинні його проаналізувати. Я згоден з тим, що невеликі довідкові таблиці важливі для уникнення тиску кешу, але ясно, що якщо у вас є більший кеш, ви можете піти з більшим таблицею пошуку, тож 4 ​​КБ - це більша частина правил. Я думаю, ти мав на увазі sizeof(int) == 4? Це буде вірно для 32-розрядних. Мій дворічний мобільний телефон має 32 КБ кеша L1, тому навіть таблиця пошуку 4K може працювати, особливо якщо значення пошуку були байтом, а не int. - steveha
Можливо я щось втратив, крім у вас j дорівнює 0 або 1 методу, чому ти не просто помножиш свою цінність на j перед тим як додати його, а не використовувати індексацію масиву (можливо, слід помножити на 1-j а не j) - Richard Tingle
@steveha мультиплікація повинна бути швидшою, я спробував подивитися це в книжках Intel, але не міг знайти його ... так чи інакше, тестування також дає мені такий результат тут. - atlaste
@steveha P.S .: ще одна можлива відповідь буде int c = data[j]; sum += c & -(c >> 7); що не вимагає множення взагалі. - atlaste


У відсортованому випадку ви можете робити краще, ніж покладатися на успішне прогнозування галузі або будь-який бездоганний трюк порівняння: повністю видалити гілку.

Дійсно, масив розподіляється в суміжній зоні з data < 128 і інший з data >= 128. Тому ви повинні знайти точку розділу з дихотомічним пошуком (використовуючи Lg(arraySize) = 15 порівняння), потім виконуйте пряме накопичення з цього моменту.

Щось на зразок (неперевірено)

int i= 0, j, k= arraySize;
while (i < k)
{
  j= (i + k) >> 1;
  if (data[j] >= 128)
    k= j;
  else
    i= j;
}
sum= 0;
for (; i < arraySize; i++)
  sum+= data[i];

або трохи більш заплутаною

int i, k, j= (i + k) >> 1;
for (i= 0, k= arraySize; i < k; (data[j] >= 128 ? k : i)= j)
  j= (i + k) >> 1;
for (sum= 0; i < arraySize; i++)
  sum+= data[i];

Ще швидший підхід, що дає приблизний Рішення для сортованих або несортованих: sum= 3137536; (якщо взяти дійсно рівномірний розподіл, 16384 зразків з очікуваним значенням 191,5) :-)


883
2017-07-24 07:57



sum= 3137536 - розумний. Очевидно, це не питання питання. Питання полягає в тому, щоб пояснити дивовижні характеристики продуктивності. Я схильний говорити про те, що це доповнення std::partition замість std::sort цінний. Хоча фактичне питання поширюється не лише на синтетичний еталон. - sehe
@DeadMG: це дійсно не стандартний дихотомічний пошук для даної ключі, а пошук для індексу розділення; це вимагає єдиного порівняння на ітерацію. Але не покладайтеся на цей код, я не перевірив його. Якщо ви зацікавлені в гарантованому правильному виконанні, дайте мені знати. - Yves Daoust


Вищезазначена поведінка відбувається через передбачення галузі.

Щоб зрозуміти передбачення галузі, потрібно спочатку зрозуміти Інструкція по трубопроводу:

Будь-яка команда розбита на послідовність кроків, тому різні етапи можуть виконуватися одночасно паралельно. Ця методика відома як інструкція конвеєр, і це використовується для збільшення пропускної здатності в сучасних процесорах. Щоб зрозуміти це краще, будь ласка, перегляньте це наприклад, у Вікіпедії.

Як правило, сучасні процесори мають досить довгі трубопроводи, але для зручності давайте розглянемо ці 4 кроки.

  1. IF - Отримати інструкцію з пам'яті   
  2. Ідентифікатор - декодування інструкції   
  3. EX - Виконайте інструкцію   
  4. WB - Напишіть назад до регістру процесора

4-х етапний трубопровід загалом на 2 інструкції. 4-stage pipeline in general

Повертаючись до вищезазначеного питання, розглянемо наступні інструкції:

                        A) if (data[c] >= 128)
                                /\
                               /  \
                              /    \
                        true /      \ false
                            /        \
                           /          \
                          /            \
                         /              \
              B) sum += data[c];          C) for loop or print().

Без прогнозу гілки, відбудеться наступне:

Для виконання інструкції B або інструкції C процесору доведеться зачекати, доки команда A не дійде до етапу EX у трубопроводі, оскільки рішення про перехід до інструкції B або інструкції C залежить від результату інструкції A. Отже, трубопровід буде виглядати так.

коли, якщо умова повертає істину: enter image description here

Коли умова повертає помилково: enter image description here

В результаті чекання результату інструкції А, загальні цикли ЦП, витрачені у вищезгаданому випадку (без прогнозу гілки, для істинної і невірної) становить 7.

Так що ж таке прогнозування галузі?

Прогноз гілки спробує вгадати, яким чином гілка (структура if-then-else) піде, перш ніж це відоме напевно. Це не буде чекати інструкції А, щоб досягти стадії ЕК трубопроводу, але це буде вгадати рішення і перейти до цієї інструкції (B або C у нашому прикладі).

У випадку правильної умові, трубопровід виглядає приблизно так: enter image description here

Якщо пізніше буде виявлено, що припущення було неправильним, то частково виконуються інструкції відкидаються, і трубопровід починається з правильної гілки, вносячи затримку. Час, витрачений у випадку неправильного прогнозування філії, дорівнює кількості стадій у конвеєрі з етапу завантаження до стадії виконання. Сучасні мікропроцесори, як правило, мають досить довгі трубопроводи, так що затримка з помилками прогнозу становить від 10 до 20 тактових циклів. Чим довше трубопровід, тим більша потреба в хорошому прогнозування галузі.

У коді OP, вперше, коли умовний, прогнозувач гілки не має ніякої інформації, щоб підготувати прогноз, таким чином, він вперше буде випадковим чином вибрати наступну інструкцію. Пізніше в циклі для циклу, він може базувати прогноз на історію. Для масиву, відсортованого в порядку зростання, є три можливості:

  1.  Всі елементи менше, ніж 128
  2.  Всі елементи більше 128
  3.  Деякі початкові нові елементи менше 128, а пізніше вони стають більше 128

Давайте припустимо, що предиктор завжди буде вважати справжню гілку на першому ході.

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

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

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


697
2017-07-03 15:35



як виконуються дві інструкції разом? це зроблено з окремими ядрами процесора, або інструкція з конвеєра інтегрована в єдине ядро ​​процесора? - M.kazem Akhgary
@ М.КаземАкгарі Все це в одному логічному ядрі. Якщо вам це цікаво, це добре описано, наприклад, в Інструкція розробника програмного забезпечення Intel - Sergey.quixoticaxis.Ivanov


Офіційний відповідь буде від

  1. Intel - уникнення витрат філій на помилки
  2. Intel - Реорганізація філій і циклів для запобігання помилковим прогнозам
  3. Наукові статті - галузі прогнозування комп'ютерної архітектури
  4. Книги: Дж. Л. Хеннессі, Д.А. Паттерсон: Архітектура комп'ютера: кількісний підхід
  5. Статті в наукових публікаціях: Т.Я. Єх, Ю.Н. Патт багато зробив на галузевих прогнозах.

Ви також можете побачити з цього прекрасного схема чому галузевий прориктор збивається з розуму.

2-bit state diagram

Кожен елемент у вихідному коді - це випадкове значення

data[c] = std::rand() % 256;

тому предиктор буде змінювати сторони як std::rand() удар

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



612
2017-10-11 21:05