Порахувати більше, щоб порахувати швидше.

Це може звучати дивно, але для того, щоб зменшити час розрахунків, часто слід збільшити загальний обсяг цих розрахунків. Тут я маю на увазі не «написати/згенерувати більше коду», як, наприклад, при розгортанні циклів при оптимізації -O3 у gcc (саме обчислень при цьому може стати менше за рахунок операції з лічильником циклу). Йдеться про отримання більшої кількості результатів обчислень, ніж це потрібно.

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

uint8_t responce(uint8_t val, uint8_t level)
{
    return val <= level ? val : (val+level)/2;
}

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

При моделюванні системи в octave такі обчислення з вектором вхідних значень можна записати як цикл з тілом, аналогічним наведеному вище C-коду:

function result = resp_if(val, level)
    for i=1:length(val)
        if val(i) <= level
            result(i) =  val(i);
        else
            result(i) = (val(i)+level)/2 ;
        end
    end
end

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

function result = resp_merge(val, level)
    val_2 = (val + level) / 2;
    result = merge(val <= level, val, val_2);
end

Можна також використати особливості саме цього алгоритму і закодувати обчислення так:

function result = resp_min(val, level)
    val_2 = (val + level) / 2;
    result = min(val, val_2);
end

Часи роботи для всіх варіантів отримаємо за допомогою випробувального стенда, який генерує вектор випадкових даних з нормальним розподілом та середнім значенням 0 і викликає по черзі всі методи, засікаючи час:

function perf_resp()
    v = randn(1,100000);
    t0 = clock();
    t1 = clock();
    r_if = resp_if(v, 0);
    t2 = clock();
    r_merge = resp_merge(v, 0);
    t3 = clock();
    r_max = resp_min(v, 0);
    t4 = clock();
    clock_cost = etime(t1, t0);
    printf("clock cost = %f\nif\t= %f\nmerge\t= %f\nmin\t= %f\n",
        clock_cost,
        etime(t2, t1) - clock_cost,
        etime(t3, t2) - clock_cost,
        etime(t4, t3) - clock_cost);
end

Різниця результатів вражає (час у секундах, від виклику до виклику міняється несуттєво):

clock cost = 0.000259
if         = 2.113846
merge      = 0.002457
min        = 0.001678

«Та ну, звісно, виписані на C бібліотечні функції роботи з векторами швидші за інтерпретований код»

Цікаво було б глянути на часи з JIT (ліньки перезбирати octave), але, на мій погляд, саме це використання вбудованих фунцій octave все одно краще розглядати не як протиставлення «інтерпретатор» — «C-код», а як «скалярний» — «векторний» процесор.

Виписану на C роботу з векторами можна вважати командами (віртуального) векторного процесора. У векторного розширення x86-ї архітектури є аналогічні команди (використано «SSE-шне» доповнення до «MMX-них» команд, показано через вбудовані функції компілятора GCC):

// val - 8-елементний вектор значень в діапазоні 0..255
// lev - 8-елементний вектор з копіями порогу
v8qi resp_min_mmx(v8qi val, v8qi lev)
{
    v8qi temp = __builtin_ia32_pavgb(val, lev);  // temp = (val+lev) / 2;
    return __builtin_ia32_pminub(val, temp);
}

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

«Та ну, звісно, векторний швидший, він непотрібні результати отримує одночасно з потрібними»

Але ж він таки рахує «зайве», саме про це й мова! Його від початку так зроблено, що він виконує однакові операції над вектором значень (SIMD є SIMD), а потім може об’єднати обчислення з різних гілок, відкинувши непотрібні результати. Для складнішої логіки вибору результатів є команди, якими можна зробити щось схоже на merge у octave — pcmp* створюють вектор-маску для елементів векторів (як оператори порівнювання в octave створюють вектор логічних значень, який потім іде на вхід селектора merge) і логічні команди pand, pandn, por дають можливість злити два вектори по масці.

«Але ж він таки на отримання зайвих результатів не витрачає додаткового часу»

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

Візьмемо частину тіла циклу обчислення CRC:

uint32_t foo(uint32_t d){
   uint32_t a = d << 1;
   return (d & 0x80000000) ? a ^ 0x04c11db7 : a;
}

Компілятор GCC для 32-бітного x86 (pentium-pro та пізніші) генерує наступний код:

1
2
3
4
5
6
7
8
foo:
    movl    4(%esp), %edx
    leal    (%edx,%edx), %ecx
    movl    %ecx, %eax
    xorl    $79764919, %eax
    testl   %edx, %edx
    cmovns  %ecx, %eax
    ret

Тут теж у рядках 3 та 5 обчислюються два результати, а потім у рядку 7 береться один з них. Ці два результати обчислюються не одночасно (навіть з урахуванням суперскалярності — тут мають паралелитися 5 та 6 рядки, у інших є залежності по даним). Але обчислити їх обидва і, за потреби, замінити один на другий командою conditional move вигідніше, ніж ламати конвеєр умовними переходами.

Для того, щоб уникати такого ламання, «старі» ARM-и у 32-бітовому наборі інструкцій мають поле умовного виконання команди. Cortex у наборі thumb2 має команду, яка «об-nop-лює» наступні команди по масці, згенерованій по бітам статусу операції. Такий собі умовний пропуск команди, але розтягнутий на декілька команд з можливістю вибору того, яка з них виконується/пропускається по прямій/інверсній умові. Тому команди для отримання обох результатів хоч і стоять послідовно, та виконуються з них лише потрібні при даному стані старшого біта:

1
2
3
4
5
6
7
8
9
10
foo:
    cmp r0, #0
    lsl r3, r0, #1
    itte    lt
    ldrlt   r0, .L4
    eorlt   r0, r3, r0
    movge   r0, r3
    bx  lr
.L4:
    .word   79764919

Тобто у реальному житті, де я зрідка щось нескладне моделюю в octave, а так основний час працюю зі звичайними «ембеддерськими» мікроконтролерами, — тема цієї публікації мене мало турбує :-)

Leave a Reply

[flagcounter image]