ДС18в08-оптимизация (1238911), страница 2
Текст из файла (страница 2)
Арифм.Результаты операцийЧтениеАдр.ЗаписьАдр.Дан.ФункциональныеустройстваДан.КэшданныхИсполнение28Суперскалярный процессор¢¢¢¢Определение: суперскалярный процессор можетвыбирать и исполнять несколько команд за такт.Инструкции выбираются из последовательного потокакоманд и обычно планируются динамически.Преимущество: без затрат на программирование,суперскалярный процессор может использоватьпараллелизм команд, который есть в большинствепрограммБольшинство современных ЦП - суперскалярныеIntel: начиная с Pentium (1993)29Конвейерные функциональные устройстваСтадия 1long mult_eg(long a, long b, long c) {long p1 = a*b;long p2 = a*c;long p3 = p1 * p2;return p3;}Стадия 2Стадия 3ВремяСтадия 1Стадия 2Стадия 312a*ba*ca*b34567p1*p2a*ca*bp1*p2a*cp1*p2§ Вычисления делятся на стадии§ Результат одной стадии передаётся на следующую§ Стадия i может начать новое вычисление как только результатпередан стадии i+1§ Например, 3 умножения завершаются за 7 циклов, а не за 930Процессор микроархитетуры Haswell¢Несколько команд могут выполняться параллельно2 загрузки с вычислением адресов1 выгрузка с вычислением адресов4 целочисленных операции2 умножения с плавающей точкой1 сложение с плавающей точкой1 деление с плавающей точкой¢Некоторые команды занимают > 1 такта, но могут бытьконвейеризованыКомандаЗагрузка / ВыгрузкаЦелочисленное умножениеЦелочисленное делениеУмножение с плавающей точкойСложение с плавающей точкойДеление с плавающей точкойЗадержка Тактов/выборку41313-303-3051313-153-1531x86-64 компиляция Combine4¢Внутренний цикл (Вариант: целочисленное умножение).L519:imull# t = t * d[i]addq $1, %rdxcmpq %rdx, %rbpjg.L519Тип данных# Цикл:(%rax,%rdx,4), %ecx# i++# Сравнение length:i# If >, goto LoopintdoubleОперациясложениеумножениесложениеумножениеCombine41.273.013.015.01Предел по задержке1.003.003.005.0032Combine4 = последовательныевычисления (OP = *)¢1 d0*((((((((1 * d[0]) * d[1]) * d[2]) * d[3])* d[4]) * d[5]) * d[6]) * d[7])d1*Вычисления (length=8)¢d2*Последовательная зависимость§ Быстродействие определяется задержкой OPd3*d4*d5*d6*d7*33Разворачивание циклов (2x1)void unroll2a_combine(vec_ptr v, data_t *dest){int length = vec_length(v);int limit = length-1;data_t *d = get_vec_start(v);data_t x = IDENT;int i;/* Учёт 2-х элементов за раз */for (i = 0; i < limit; i+=2) {x = (x OP d[i]) OP d[i+1];}/* Учёт оставшихся элементов */for (; i < length; i++) {x = x OP d[i];}*dest = x;}¢Выполняет в 2 раза больше работы за итерацию34Эффект разворачивания цикловТип данныхintdoubleОперациясложениеумножениеCombine41.273.013.015.01Разворачивание 2х1.013.013.015.01Предел по задержке1.003.003.005.00¢сложение умножениеПомогло с целочисленным умножением§ Достигнут предел по задержке¢Остальные не улучшились.
Почему?§ Остаётся последовательная зависимостьx = (x OP d[i]) OP d[i+1];35Разворачивание цикловс изменением порядка операций (2x1a)void unroll2aa_combine(vec_ptr v, data_t *dest){int length = vec_length(v);int limit = length-1;data_t *d = get_vec_start(v);data_t x = IDENT;int i;/* Учёт 2-х элементов за раз */for (i = 0; i < limit; i+=2) {x = x OP (d[i] OP d[i+1]);}/* Учёт оставшихся элементов */for (; i < length; i++) {x = x OP d[i];Сравните с предыдущим}x = (x OP d[i]) OP d[i+1];*dest = x;}¢¢Может ли это изменить результат вычислений?Да, для плавающей точки.
Почему?36Эффект переупорядоченияТип данныхОперацияintdoubleсложение умножение сложениеумножениеCombine41.273.013.015.01Разворачивание 2х1.013.013.015.01Разворачивание 2х, сизменением порядка1.011.511.512.51Предел по задержке1.003.003.005.00Предел по выборке0.501.001.000.50¢Почти 2-кратное ускорение int *, double +, double *§ Причина: нарушение последовательной зависимостиx = x OP (d[i] OP d[i+1]);§ Почему это происходит?2 ФУ для double *2 ФУ для загрузки4 ФУ для int +2 ФУ для загрузки37Переупорядоченные вычисленияx = x OP (d[i] OP d[i+1]);¢§ Операции следующей итерациимогут начинаться раньше (нетзависимости)d0 d11*Что изменилось:d2 d3**¢§ N элементов, D тактов задержкиd4 d5**Быстродействие в целомd6 d7на операцию§ Должно быть (N/2+1)*D тактов:CPE = D/2***38Разворачивание циклов с раздельныминакопителями (2х2)void unroll2a_combine(vec_ptr v, data_t *dest){long length = vec_length(v);long limit = length-1;data_t *d = get_vec_start(v);data_t x0 = IDENT;data_t x1 = IDENT;int i;/* Учёт 2-х элементов за раз */for (i = 0; i < limit; i+=2) {x0 = x0 OP d[i];x1 = x1 OP d[i+1];}/* Учёт оставшихся элементов */for (; i < length; i++) {x0 = x0 OP d[i];}*dest = x0 OP x1;}¢Другой вариант переупорядочивания39Эффект раздельных накопителейТип данныхОперацияintdoubleсложение умножениесложение умножениеCombine41.273.013.015.01Разворачивание 2х1.013.013.015.01Разворачивание 2х, сизменением порядка1.011.511.512.51Разворачивание 2х, 2накопителя0.811.511.512.51Предел по задержке1.003.003.005.00Предел по выборке0.501.001.000.50¢Int + задействует 2 устройства загрузкиx0 = x0 OP d[i];x1 = x1 OP d[i+1];¢2-кратное ускорение для int *, double +, double *40Раздельные накопителиx0 = x0 OP d[i];x1 = x1 OP d[i+1];1 d01 d1**d2*операций¢Быстродействие в целом§ N элементов, D тактов*d6Что изменилось:§ Два независимых “потока”d3d4*¢d5**d7**задержки на операцию§ Должно быть (N/2+1)*D тактов:CPE = D/2§ CPE совпадает с ожидаемым!Что теперь?41Разворачивание и разделение¢Идея§ Можно развернуть до любой степени L§ Можно накапливать K результатов параллельно§ L должно быть кратно K¢Ограничения§ Не получится превзойти ограничения пропускной способностиисполнительных устройств§ Большие накладные расходы для малых длин§ Последовательное завершение итераций42Разворачивание и разделение: double *¢Вариант§ Intel Haswell§ Умножение double§ Предел по задержке: 5.00.
Предел по выборке: 0.50НакопителиFP *Кратность разворачиваниz LK1234681015.015.015.015.015.015.015.012346810122.512.512.511.251.26121.670.840.880.630.510.5243Разворачивание и разделение: int +¢Вариант§ Intel Haswell§ Сложение int§ Предел по задержке: 1.00. Предел по выборке: 1.00НакопителиInt +Кратность разворачивания LK1234681011.271.011.011.011.011.011.012346810120.810.690.540.691.24120.740.560.560.540.540.5644Достижимое быстродействиеТип данныхОперацияintdoubleсложение умножениесложение умножениеЛучшая версия0.541.011.010.52Предел по задержке1.003.003.005.00Предел по выборке0.501.001.000.50¢¢Ограничено только пропускной способностьюисполнительного устройства42-кратное ускорение исходного, неоптимизированного кода45Программирование с AVX2Регистры YMMn 16 штук по 32 байтаn 32 однобайтных целыхn 16 16-битных целыхn 8 32-биных целыхn 8 ЧПТ одинарной точностиn 4 ЧПТ двойной точностиn 1 ЧПТ одинарной точностиn 1 ЧПТ двойной точности46Команды SIMDn Одинарная точностьvaddsd %ymm0, %ymm1, %ymm1%ymm0++++++++%ymm1n Двойная точностьvaddpd %ymm0, %ymm1, %ymm1%ymm0++++%ymm147Используя векторные инструкцииТип данныхОперацияintdoubleсложение умножениесложение умножениеСкалярный оптимум0.541.011.010.52Векторный оптимум0.060.240.250.16Предел по задержке0.503.003.005.00Предел по выборке0.501.001.000.50Векторная выборка0.060.120.250.12¢Использование команд SSE§ Параллельные операции над несколькими элементами данных§ Детали OPT:SIMD на сайте:http://csapp.cs.cmu.edu/public/waside.html48Об условных переходах¢Проблема§ Устройство Управления (командами) должно работать опережаяИсполнительное Устройство и порождать операции так, чтобыпоследнее было эффективно загружено и не простаивало.404663: mov404668: cmp40466b: jge40466d: mov$0x0,%eax(%rdi),%rsi4046850x8(%rdi),%raxИсполнениеКуда дальше?.
. .404685:repz retq§ Когда попадается условный переход, нет возможности надёжноопределить, откуда продолжать выборку команд49Конструкция современного ЦПУправлениеАдресаУправлениевыборкойУстройствозавершенияБлокрегистровКэшкомандДекодирование КомандыкомандОперацииИзменения регистровПредсказание верно?ПереходАрифм.Арифм. Арифм.Результаты операцийЧтениеАдр.ЗаписьАдр.Дан.ФункциональныеустройстваДан.КэшданныхИсполнение50Результат условного перехода§ Когда попадается условный переход, нет возможности надёжноопределить откуда продолжать выборку команд§ Переход произошёл: передача управления на цель перехода§ Переход на произошёл: продолжение со следующей по коду командой§ Невозможно решить пока результат не будет выдан функциональнымустройством «Переход»404663:404668:40466b:40466d:movcmpjgemov$0x0,%eax(%rdi),%rsi4046850x8(%rdi),%raxПереход есть.
. .404685:Перехода нетrepz retq51Предсказание переходов¢Идея§ Допустим условный переход произойдёт§ Начнём исполнять команды по предсказанному адресу§404663:404668:40466b:40466d:Но не будем изменять значения регистров и памятиmovcmpjgemov$0x0,%eax(%rdi),%rsi4046850x8(%rdi),%raxПереход есть. . .404685:repz retqПродолжениеисполнения52Предсказание перехода в цикле401029:40102d:401031:401034:vmulsdaddcmpjne(%rdx),%xmm0,%xmm0$0x8,%rdx%rax,%rdxi = 98401029Положимдлину вектора = 100Предсказание успешно401029:40102d:401031:401034:vmulsdaddcmpjne(%rdx),%xmm0,%xmm0$0x8,%rdx%rax,%rdxi = 99401029401029:40102d:401031:401034:vmulsdaddcmpjne(%rdx),%xmm0,%xmm0$0x8,%rdx%rax,%rdxi = 100401029401029:40102d:401031:401034:vmulsdaddcmpjne(%rdx),%xmm0,%xmm0$0x8,%rdx%rax,%rdxi = 101401029Предсказание ошибочноЧтение из ИсполнениеошибочногоместаВыборка53Отмена ошибки предсказания401029:40102d:401031:401034:401029:40102d:401031:401034:vmulsdaddcmpjnevmulsdaddcmpjne(%rdx),%xmm0,%xmm0$0x8,%rdx%rax,%rdxi = 98401029(%rdx),%xmm0,%xmm0$0x8,%rdx%rax,%rdx401029i = 99Положимдлину вектора = 100Предсказание успешноПредсказание ошибочно401029:40102d:401031:401034:vmulsdaddcmpjne(%rdx),%xmm0,%xmm0$0x8,%rdx%rax,%rdx401029i = 100Отмена401029:40102d:401031:401034:vmulsdaddcmpjne(%rdx),%xmm0,%xmm0$0x8,%rdx%rax,%rdxi = 101i = 10140102954Исправление ошибки предсказания401029:40102d:401031:401034:401036:.
. .401040:¢vmulsdaddcmpjnejmp(%rdx),%xmm0,%xmm0$0x8,%rdxi=%rax,%rdx401029401040vmovsd %xmm0,(%r12)99перехода нет совсемперезагрузкаконвейераПотери быстродействия§ Много тактов на современных процессорах§ Может быть основным ограничителем быстродействия55Достижение высокого быстродействия¢¢Хороший компилятор и флагиНе делайте глупостей§ Следите за скрытыми алгоритмическими неэффективностями§ Пишите дружелюбный к компилятору кодСледите за помехами оптимизации:обращениями к процедурам и в память§ Тщательно анализируйте самые внутренние циклы (где делаетсябольшая часть работы)§¢Подстраивайте код под машину§ Используйте параллелизм команд§ Избегайте непредсказуемых переходов§ Пишите код дружелюбный к кэшу (продолжение следует…)56.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
