Calculate more to calculate faster.
Це може звучати дивно, але для того, щоб зменшити час розрахунків, часто слід збільшити загальний обсяг цих розрахунків. Тут я маю на увазі не «написати/згенерувати більше коду», як, наприклад, при розгортанні циклів при оптимізації -O3 у gcc (саме обчислень при цьому може стати менше за рахунок операції з лічильником циклу). Йдеться про отримання більшої кількості результатів обчислень, ніж це потрібно.
Візьмемо для прикладу такий алгоритм: якщо вхідна величина не перевищує заданий поріг, то видати її значення на вихід без змін, інакше взяти напівсуму входу та порогу. Мовою C алгоритм запишеться так:
{
return val <= level ? val : (val+level)/2;
}
Цей, на перший погляд надуманий, алгоритм використовується у реальному проекті для формування необхідної характеристики передачі. Повторений декілька разів підряд з порогами, що збільшуються, він дає таку апроксимацію:
При моделюванні системи в octave такі обчислення з вектором вхідних значень можна записати як цикл з тілом, аналогічним наведеному вище C-коду:
Але такий код працює набагато довше, ніж інший, який спочатку виконує “довгу” гілку умовного оператора для кожного елемента вхідного вектора, затим вибирає на вихід потібне значення:
val_2 = (val + level) / 2;
result = merge(val <= level, val, val_2);
end
Можна також використати особливості саме цього алгоритму і закодувати обчислення так:
Часи роботи для всіх варіантів отримаємо за допомогою випробувального стенда, який генерує вектор випадкових даних з нормальним розподілом та середнім значенням 0 і викликає по черзі всі методи, засікаючи час:
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
Різниця результатів вражає (час у секундах, від виклику до виклику міняється несуттєво):
if = 2.113846
merge = 0.002457
min = 0.001678
«Та ну, звісно, виписані на C бібліотечні функції роботи з векторами швидші за інтерпретований код»
Цікаво було б глянути на часи з JIT (ліньки перезбирати octave), але, на мій погляд, саме це використання вбудованих фунцій octave все одно краще розглядати не як протиставлення «інтерпретатор» — «C-код», а як «скалярний» — «векторний» процесор.
Виписану на C роботу з векторами можна вважати командами (віртуального) векторного процесора. У векторного розширення x86-ї архітектури є аналогічні команди (використано «SSE-шне» доповнення до «MMX-них» команд, показано через вбудовані функції компілятора GCC):
// 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 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, а так основний час працюю зі звичайними «ембеддерськими» мікроконтролерами, — тема цієї публікації мене мало турбує 🙂
українська
english