Форум программистов, компьютерный форум, киберфорум
Наши страницы
Evg
Войти
Регистрация
Восстановить пароль
Рейтинг: 3.56. Голосов: 9.

Влияние конвейера на скорость исполнения кода

Запись от Evg размещена 02.05.2012 в 17:53
Обновил(-а) Evg 27.07.2014 в 15:51

1. Предисловие

Одно из стандартных заблуждений начинающих программистов заключается в том, что многие думают, что чем короче исходник программы, тем быстрее программа будет работать. На самом деле для больших проектов первоочередным показателем является грамотное проектирование программы, а не количество строк кода. Но это всего лишь лирическое отступление, которое упомянуто к слову. В статье речь пойдёт немного о другом.

Ещё одним из стандартных заблуждений является то, что если написать программу на ассемблере, то программа будет работать быстрее. В данной статье я не буду рассматривать какую-то большую программу, а рассмотрю лишь коротенькую функцию, которая выполняет весьма простое действие. При этом всё равно возникает подсознательное ощущение, что фрагмент кода будет работать быстро, если количество операций в нём минимизировать.

Чисто на всякий случай. Кода речь идёт об intel'овских процессорах, то имеются в виду процессоры с intel'овской системой команд, коими, помимо процессоров Intel, являются и процессоры AMD

2. Постановка простой задачи

В качестве постановки задачи я просто напишу коротенькую функцию, глядя на которую легко понять, что она делает.

C
1
2
3
4
5
6
7
8
void
copy (int *dst, const int *src, unsigned long length)
{
  unsigned long i;
 
  for (i = 0; i < length; i++)
    dst[i] = src[i] + 1023;
}
Здесь всё понятно. На вход функции подаются два указателя на массив и размер массивов, далее поэлементно выполняется операция сложения. На языке Си программа написана предельно просто и что-то короче написать уже нельзя. Можно посмотреть выдачу ассемблерного текста из-под компилятора. Я использую gcc, а потому для получения ассемблерного текста я запускаю "gcc t.c -O3 -S" и смотрю итоговый файл t.s:

Код:
copy:
	pushl	%ebp
	movl	%esp, %ebp
	movl	16(%ebp), %ecx
	pushl	%esi
	movl	8(%ebp), %esi
	pushl	%ebx
	movl	12(%ebp), %ebx
	testl	%ecx, %ecx
	je	.L5
	xorl	%edx, %edx
	.p2align 4,,15
.L4:
	movl	(%ebx,%edx,4), %eax
	addl	$1023, %eax
	movl	%eax, (%esi,%edx,4)
	incl	%edx
	cmpl	%edx, %ecx
	jne	.L4
.L5:
	popl	%ebx
	popl	%esi
	popl	%ebp
	ret
"Горячий" (т.е. наиболее часто исполняемый) фрагмент кода, который представляет собой полезные действия внутри цикла, находится между метками .L4 и .L5. Здесь на вид тоже всё предельно просто и ясно. Читаем из памяти значение (src[i]), прибавляем нему 1023, записываем в память результат (dst[i]), увеличиваем на 1 счётчик цикла, сравниваем счётчик с верхней границей цикла и затем условный переход на начало цикла.

Указанный "горячий" фрагмент кода является определяющим с точки зрения скорости работы, т.к. он будет исполняться часто, а потому паровоз операций, который стоит до цикла и после цикла на скорость работы программы не оказывают практически никакого влияния. Потому что эти операции будут работать только один раз за один вызов функции, против, условно говоря, нескольких тысяч исполнений операций, находящихся внутри цикла. Таким образом, глядя на ассемблерный код, дело выглядит так, что компилятор построил его самым оптимальны образом и сокращать тут просто нечего.

Ну а теперь вопрос: а можно ли как-то ускорить этот код?

3. Каким образом происходит исполнение в процессоре

В учебниках по ассемблеру обычно рассказывают только то, что делает та или иная машинная операция. Но довольно редко уделяется внимание тому, а каким же образом происходит выполнение операций в процессоре. И это вполне логично: мы имеем последовательность машинных команд на входе и имеем однозначный результат в виде значений в регистрах и в памяти на выходе, а каким образом это достигается - это дело процессора. Но на самом деле есть целая куча тонкостей, на хорошее понимание которых может потребоваться несколько лет. В данном разделе я ограничусь лишь поверхностным описанием тех сведений, которые необходимы для последующего понимания статьи. Кто-то эти моменты знает, а кто-то о них ещё не задумывался

Все процессоры содержат исполнительное устройство - конвейер. Я видел в книгах, что про это немного рассказывают, но лишь для общего понимания. Современные процессоры имеют несколько конвейеров, которые могут исполнять команды параллельно. Можно две операции выполнять параллельно, или нельзя, решает аппаратура в процессе декодирования операции. Т.е., к примеру, если есть операция чтения из памяти в регистр %eax и операция инкрементации регистра %ebx, то эти две операции аппаратура может исполнять параллельно, поскольку они не конфликтуют по ресурсам. Но вот если бы вторая операция была операцией инкрементирования регистра %eax, то параллельное исполнение было бы невозможным: сначала нужно дождаться загрузки значения из памяти в %eax и только потом значение регистра инкрементировать.

Есть ещё один момент, которому тоже нечасто уделяют внимание - это время исполнения операций. Простые операции типа целочисленного сложения-вычитания или битовой арифметики исполняются за один такт на любом более-менее приличном процессоре. Более сложные операции типа умножения или деления, как правило, исполняются несколько тактов (причём на разных процессорах время исполнения может сильно различаться). Связано это со сложным устройством апаратных элементов, которые исполняют данные операции. Операции чтения из памяти на любом современном высокоскоростном процессоре исполняется несколько тактов. Точной причины этого я не знаю, но есть некоторый минимальный порог времени, требуемый для прочтения данных из транзисторной матрицы: нужно вычислить, из какого места нужно данные прочитать, а потом ещё и прочитать сами данные. Дальше эти данные через шину нужно передать на процессор. На всех железках процессор и память представляют физически разведённые друг от друга устройства на общей плате. Чтение из памяти может исполняться несколько десятков или даже сотен машинных тактов. Именно из-за этого в современных процессорах присутсвует кэш (и даже не один), который физически находится на процессоре или очень близко к нему, а потому имеет более короткое время доступа к данным, но ограниченный размер памяти. И даже в тех случаях, когда данные оказываются в кэше первого уровня, их чтение занимает порядка трёх машинных тактов

На этом данный раздел можно закончить. Мне кажется, что для общего понимания данных сведений вполне достаточно

4. Что происходит при исполнении нашей тестовой программы

FIXME Данный раздел получился очень сложным для восприятия. Надо как-то его более внятно переписать

Посмотрим, как исполняется на процессоре наша тестовая программа. Для удобства ещё раз приведу ассемблерный код "горячего" участка

Код:
.L4:
	movl	(%ebx,%edx,4), %eax
	addl	$1023, %eax
	movl	%eax, (%esi,%edx,4)
	incl	%edx
	cmpl	%edx, %ecx
	jne	.L4
Что здесь происходит. Сначала исполняется операция чтения из памяти (строка 2), которая требует 3 такта на исполнение (а может и больше, это всё нужно смотреть в описании процессора). Далее идёт операция сложения в регистре %eax (строка 3). Эта операция не может начать исполняться, пока не загрузится значение из памяти, а потому аппаратура вхолостую прощёлкает два пустых такта в ожидании данных из памяти. Далее идёт операция записи в память (строка 4), которая записывает в память результат вычисления, а потому она должна дождаться исполнения операции сложения (из строки 3). Далее идёт операция инкрементации счётчика (строка 5). Инкрементировать счётчик можно только после того, как мы исполним операцию записи в память (из строки 4), которая использует регистр %edx. Реально аппаратура умеет справляться с такими зависимостями и на пальцах исполняется что-то типа: прочитать текущее значение %edx, параллельно исполнить операцию записи в память и операцию прибавления единицы (без записи результата) и после того, как будет вычислен адрес для записи в память, записать результать прибавления единицы в регистр. Затем идёт операция сравнения (строка 6), которая должна дождаться исполнения операции инкрементации (из строки 5) и в конце выполняется условный переход, который благодаря механизму предсказания переходов начнёт выполняться не дожидаясь результата сравнения и уже потом сделать контрльную проверку того, что переход исполнен по делу. Предсказание переходов - это отдельная огромная тема, которую здесь не хочется затрагивать более подробно. Итого с учётом того, что две операции удалось поставить на параллельное исполнение, а операцию перехода аппаратура сделала заранее, то в грубой прикидке одна итерация цикла будет исполняться 6 тактов. При этом будет задействован один конвейер + немного второй. И это при том, что современные Intel'ы имеют 4 конвейра, которые при исполнении данного участка кода будут простаивать. Потактно исполнение будет выглядеть примерно так:

Код:
1. Исполняем "movl (%ebx,%edx,4), %eax"
2. Ждём
3. Ждём
4. Исполняем "addl $1023, %eax"
5. Исполняем "movl %eax, (%esi,%edx,4)" и "incl %edx"
6. Исполняем "cmpl %edx, %ecx" и "jne .L4"
Потактно расписанная схема является очень условной. Есть много тонкостей при работе с конвейером типа того, что на самом деле конвейер разбит на несколько стадий: декодирование, чтение входных аргументов, исполнение, запись результатов и целая куча промежуточных стадий. Те операции, которые исполняются один такт, на самом деле проводят в конвейере несколько тактов. Но в то время, когда первая операция проходит через вторую стадию конвейера, вторая операция уже попадает на первую стадию. Мне не хотелось бы загромождать статью такими особенностями, чтобы не загородить ими основную мысль, а потому следует к моим словам относиться как к чему-то очень общему, а не детальным подробностям

5. Переписываем программу под параллельное исполнение

При вычислении выражения "dst[i] = src[i] + 1023", как мы уже выяснили, практически ничего нельзя распараллелить по разным конвейерам, т.к. все операции цепочкой зависят друг от друга. Но если посмотреть, как исполняется не одна итерация цикла, а весь цикл, то легко можно заметить, что две соседние итерации цикла являются полностью независимыми. Т.е. при вычислении двух операторов "dst[0] = src[0] + 1023" и "dst[1] = src[1] + 1023" нету той цепочной зависимости, о которой писалось в разделе 4. А потому нашу функцию можно переписать по другому:

C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void
copy (int *dst, const int *src, unsigned long length)
{
  unsigned long i;
 
  for (i = 0; i < length; i += 2)
    {
      int a, b, c, d;
      a = src[i];
      b = src[i+1];
      c = a + 1023;
      d = b + 1023;
      dst[i] = c;
      dst[i+1] = d;
    }
}
Данный код по количеству строк выглядит гораздо более громоздким. Математически он делает ровно то же самое, что и предыдущий вариант (на самом деле это справедливо только для чётного количества итераций, но на текущий момент это не важно): количество итераций цикла уменьшилось вдвое, но при этом вдвое увеличилось количество значащих операций в одной итерации. И кажется, что такой код является избыточным. Но если вспомнить те проблемы с распараллеливанием, о которых писалось в разделе 4, то здесь можно увидеть качественные изменения. Ассемблерный текст, соответствующий "горячему" участку данного кода, выглядит следующим образом:

Код:
.L4:
	movl	4(%ebx,%ecx,4), %edx
	movl	(%ebx,%ecx,4), %eax
	addl	$1023, %edx
	addl	$1023, %eax
	movl	%eax, (%esi,%ecx,4)
	movl	%edx, 4(%esi,%ecx,4)
	addl	$2, %ecx
	cmpl	%ecx, %edi
	ja	.L4
Мы читаем два значения из памяти (строки 2 и 3) в разные регистры, а потому их можно исполнить параллельно. Далее мы проводим операции сложения (строки 4 и 5) над разными регистрами, а потому их можно исполнить паралельно. Затем мы два значения записываем в память (строки 6 и 7) в разные адреса, а потому их тоже можно исполнить параллельно. Далее идёт хвостик с инкрементацией счётчика и условным переходом на начало цикла, который исполнится ровно так же, как и в "простом" варианте программы. В итоге за одну итерацию нашего оптимизированного цикла мы исполняем две итерации исходного цикла, но время исполнения будет меньше за счёт того, что нам часть вычислений удалось раскидать по двум конвейерам для параллельного вычисления. Если расписать по тактам, то будет что-то типа того:

Код:
1. Исполняем "movl 4(%ebx,%ecx,4), %edx" и "movl (%ebx,%ecx,4), %eax"
2. Ждём
3. Ждём
4. Исполняем "addl $1023, %edx" и "addl $1023, %eax"
5. Исполняем "movl %eax, (%esi,%ecx,4)", "movl %edx, 4(%esi,%ecx,4)" и "addl $2, %ecx"
6. Исполняем "cmpl %ecx, %edi" и "ja .L4"
Т.е. мы получаем как бы те же самые 6 тактов (но уже на две исходные итерации), что и в "простой" реализации. В конце раздела 4 я оговорил, что расписывание по тактам является очень условным. В данном случае это имеет ещё бОльшую роль. Раскидываени по тактам следует рассметривать как логическое. Реально конвейеры будут работать немного не так (хотя бы потому, что начало процесса декодирования каждой отдельной машинной команды делается строго последовательно). Оптимизированный код будет работать быстрее, но не в два раза.

6. Результаты замеров

В заключение статьи осталось померить тот выигрыш, который даёт нам оптимизированный вариант кода по сравнению с "простым". Итоговый вариант программы, на которой я проводил замеры, приведён ниже. Важные моменты, связанные с методикой измерения, отмечены в комментариях. Внутри функции copy имеются две реализации под макросом. По умолчанию работает "простой" вариант, при замене "#if 1" на "#if 0" будет работать оптимизированный вариант

C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
 
void
copy (int *dst, const int *src, unsigned long length)
{
 unsigned long i;
 
#if 1
  /* "Простой" вариант */
  for (i = 0; i < length; i++)
    dst[i] = src[i] + 1023;
#else
  /* Оптимизированный вариант */
  for (i = 0; i < length; i += 2)
    {
      int a, b, c, d;
      a = src[i];
      b = src[i+1];
      c = a + 1023;
      d = b + 1023;
      dst[i] = c;
      dst[i+1] = d;
    }
#endif
}
 
/* Вызов функции делаем через указатель, чтобы не было inline-подстановки.
 * На результат это практически не влияет, но без inline'а проще глазками
 * смотреть ассемблерный текст */
void (*copy_ptr)(int*, const int*, unsigned long) = copy;
 
/* Размер массива */
#define N 100000
 
/* Количество циклов копирования, входящих в задачу.
 * Казалось бы, что два параметра N и LOOP являются избыточными,
 * но это только кажется. Если сравнить 100 циклов по 1 мегабйту
 * и 1 цикл на 100 мегабайт, то мы получим разные результаты.
 * В первом случае объём обработанных данных, условно говоря, целиком
 * умещается в кэш, а во втором случае - нет. В первом случае будет
 * маленькая нагрузка на подсистему памяти, обслуживающую виртуальную
 * адресацию, а во втором случае - большая. Мы хотим померить "чистое"
 * время работы цикла, но не скорость работы подсистемы памяти */
#define LOOP 100000
 
/* Количество повторений задачи. Параметр тоже может показаться избыточным.
 * Но если увеличить значение N таким образом, чтобы оно заведомо превышало
 * размер кэша, (и в соответсвующее число раз уменьшить значение LOOP,
 * чтобы общее время работы было примерно такое же) то по результирующей
 * печати времени исполнения можно увидеть, что COUNT себя оправдывает.
 * В этом случае первые один-два запуска задачи будут работать на то,
 * чтобы "раскрутилась" подсистема памяти (и время работы будет иметь выброс),
 * а остальные запуски задачи уже будут давать более-менее справедливые
 * результаты */
#define COUNT 5
 
int
main (void)
{
 clock_t t1, t2;
 unsigned i, j;
 
 int *src = malloc (sizeof (int) * N);
 int *dst = malloc (sizeof (int) * N);
 
 for (i = 0; i < COUNT; i++)
   {
     t1 = clock();
     for (j = 0; j < LOOP; j++)
       copy_ptr (dst, src, N);
     t2 = clock();
 
     printf("time: %.03f\n", ((double)(t2 - t1))/CLOCKS_PER_SEC);
   }
 
 return 0;
}
Замеры проводились на разных машинах с разными процессорами, под управлением разных операционных систем, с применением разных компиляторов. Из-за того, что процессоры работают с разной скоростью, на каждой машине я подгонял значение макроса LOOP с тем, чтобы "обычный" вариант работал порядка 10 секунд. Сделано это исключительно ради удобства, чтобы глядя на цифры можно было сразу оценить в целом влияние кработы конвейера на разных процессорах.

Результаты получились следующие:

Код:
Процессор: Intel Core2 Q9400, 2.66 ГГц
ОС: linux
Компилятор: gcc-4.1.2
Опции компилятора: -m32 -O3

"Обычный" вариант:
time: 10.270
time: 10.050
time: 10.140
time: 10.100
time: 10.120

Оптимизированный вариант:
time: 8.940
time: 8.960
time: 9.080
time: 8.950
time: 8.980
Код:
Процессор: AMD Athlon 64 X2, 2.8 ГГц
ОС: windows
Компилятор: borland builder 2007
Опции компилятора: те, что по умолчанию стоят в режиме RELEASE, 32-битный режим

"Обычный" вариант:
time: 10.015
time: 10.000
time: 10.000
time: 10.015
time: 10.000

Оптимизированный вариант:
time: 8.799
time: 8.798
time: 8.799
time: 8.798
time: 8.783
Код:
Процессор: Sun UltraSPARC-III+, 1.2 ГГц
ОС: solaris
Компилятор: Sun cc
Опции компилятора: -xarch=v8plusb -xO4 (32-битный режим)

"Обычный" вариант:
time: 10.020
time: 10.030
time: 10.020
time: 10.040
time: 10.030

Оптимизированный вариант:
time: 8.830
time: 8.830
time: 8.840
time: 8.840
time: 8.840
Код:
Процессор: TI UltraSparc IIi, 400 МГц
ОС: linux
Компилятор: gcc-4.2.4
Опции компилятора: -m32 -mcpu=ultrasparc3 -O3

"Обычный" вариант:
time: 10.310
time: 10.310
time: 10.310
time: 10.310
time: 10.320

Оптимизированный вариант:
time: 8.340
time: 8.340
time: 8.340
time: 8.330
time: 8.340
7. Заключение

Первым делом хочется сказать, что пример, рассматриваемый в данной статье - это всего лишь демонстрационный пример, на котором можно пощупать, как работает многоконвейерный процессор. Ни в коем случае данный пример не стОит рассматривать как рекомендацию к самостоятельному переписыванию циклов в подобном стиле. Компилятор, надлежащим образом настроенный, справится с задачей лучше, чем среднестатистический программист (см. этот, этот и этот посты в комментариях). Построить код лучше компилятора сможет разве что эксперт, хорошо понимающий работу конвейера

FIXME Что-то ещё хотел сказать

8. Ссылки на темы, где обсуждался данный вопрос
Всего комментариев 38
Комментарии
  1. Старый комментарий
    Аватар для grizlik78
    Внесём немного разнообразия в результаты
    Подкрутил только значение LOOP до 160000
    Код Code
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    
    Процессор: Intel Core2 E6600, 2.4 ГГц
    ОС: linux (64 бита)
    Компилятор: gcc-4.5.3
    Опции компилятора: -O3
     
    "Обычный" вариант:
    time: 10.030
    time: 10.030
    time: 10.020
    time: 10.040
    time: 10.030
     
    Оптимизированный вариант:
    time: 10.080
    time: 10.070
    time: 10.070
    time: 10.210
    time: 10.130
    Видимо всё от того, что компилятор сам разворачивает "простой" цикл с использованием SSE (смотрел в листинг).
    Запись от grizlik78 размещена 02.05.2012 в 18:28 grizlik78 вне форума
  2. Старый комментарий
    Аватар для Evg
    О как. У меня Intel'овские компиляторы 32-битные (т.е. под i686, а не x86-64). У тебя, видимо, компилятор 64-битный. Ради интереса запусти компиляцию и исполнение в режиме 32.

    В итоге получается, что у меня пример не совсем удачный (из-за того, что для компилятора он оказался слишком простым)
    Запись от Evg размещена 02.05.2012 в 19:57 Evg вне форума
  3. Старый комментарий
    Аватар для grizlik78
    Да, в 32-битном режиме картинка заметно другая. LOOP не стал менять, результаты на той же машине в той же системе.
    Код Code
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    
    Процессор: Intel Core2 E6600, 2.4 ГГц
    ОС: linux (64 бита)
    Компилятор: gcc-4.5.3
    Опции компилятора: -O3 -m32
     
    "Обычный" вариант:
    time: 13.340
    time: 13.360
    time: 13.340
    time: 13.360
    time: 13.360
     
    Оптимизированный вариант:
    time: 9.140
    time: 9.160
    time: 9.140
    time: 9.160
    time: 9.400
    По умолчанию в этом режиме SSE не используется. Если его разрешить, то результаты становятся ровнее
    Код Code
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    
    Процессор: Intel Core2 E6600, 2.4 ГГц
    ОС: linux (64 бита)
    Компилятор: gcc-4.5.3
    Опции компилятора: -O3 -m32 -msse -msse2 -msse3 -mssse3
     
    "Обычный" вариант:
    time: 10.000
    time: 10.020
    time: 10.000
    time: 10.020
    time: 10.000
     
    Оптимизированный вариант:
    time: 9.100
    time: 9.240
    time: 9.100
    time: 9.120
    time: 9.180
    Наглядно развевается миф, что 64-битные программы работают быстрее Хотя в специальных случаях они действительно быстрее.
    Запись от grizlik78 размещена 02.05.2012 в 20:34 grizlik78 вне форума
  4. Старый комментарий
    Аватар для Evg
    Цитата:
    Сообщение от grizlik78 Просмотреть комментарий
    Наглядно развевается миф, что 64-битные программы работают быстрее
    Такой коротенький пример - не показатель. Он не предназначен, для того, чтобы сравнивать скорость работы на разных архитектурах.
    Запись от Evg размещена 02.05.2012 в 21:41 Evg вне форума
    Обновил(-а) Evg 02.05.2012 в 21:57
  5. Старый комментарий
    Аватар для grizlik78
    Вообще-то это была шутка.
    Запись от grizlik78 размещена 02.05.2012 в 22:19 grizlik78 вне форума
  6. Старый комментарий
    Аватар для grizlik78
    Цитата:
    при замене "#if 0" на "#if 1" будет работать оптимизированный вариант
    Тут получилось расхождение с кодом. На самом деле наоборот, при замене с "#if 1" на "#if 0"
    Запись от grizlik78 размещена 02.05.2012 в 22:28 grizlik78 вне форума
  7. Старый комментарий
    Аватар для Evg
    Поправил
    Запись от Evg размещена 02.05.2012 в 22:41 Evg вне форума
  8. Старый комментарий
    Аватар для Vourhey
    Стандартный метод оптимизации разворачиванием цикла. Так как длина массива заранее задана, то то же самое можно сделать через опции:
    -funroll-loops --param max-unroll-times=2
    (для gcc)
    ну и если развернуть до 4-х (max-unroll-times=4), то на моей машине работает еще быстрее.
    А вообще, странно, но, блин, у меня даже до краев оптимизнутый код работает медленее чем у вас неоптимизированные - 14.5 секунд, это минимум с циклом развернутым до 4-х. До 2-х - 16.5, обычный - ~17. Бида...
    Запись от Vourhey размещена 05.05.2012 в 02:33 Vourhey вне форума
  9. Старый комментарий
    Аватар для Vourhey
    gcc. Если указать опцию -march=native, то оптимизированный вариант кода работает в 2 раза медленней неоптимизированного. Обычный вариант - ~9 секунд, оптимизированный - ~16.5. Не все йогурты одинаково полезны... С ней он цикл без указания unroll-опций разворчивает до 8 (если включен -O3). Тестирую на AMD Phenom(tm) II X4 955 Processor
    Запись от Vourhey размещена 05.05.2012 в 02:51 Vourhey вне форума
  10. Старый комментарий
    Аватар для Evg
    Vourhey, у меня основной целью было показать, что размер кода - не показатель скорости исполнения, а так же хотя бы на каком-то ощутимом примере дать людям понять, как наличие нескольких конвейеров влияет на исполнение. Просто конвейер - это такая штука, которым не умею пользоваться даже многие среди тех, кто на ассемблере программирует (ибо слишком специфичная вещь). По-честному нужно было демонстрировать при помощи ассемблера, а не компилятора, но всяких разных ассемблеров слишком много, а потому тут аккуратно свести концы с концами было бы сложно.

    То, что у компилятора есть опции - это хорошо, но в реальной жизни они, как правило, сильно помогают только в частных случаях, а в общем случае только увеличивают время компиляции, но практически не ускоряют код. Это так называемые опции пиковых оптимизаций. По-хорошему к ним должна прилагаться методичка страниц на 500 с описанием, в каких случаях от каждой конкретной опции будет хороший эффект. Да и задача статьи состояла немного в другом

    Цитата:
    Сообщение от Vourhey Просмотреть комментарий
    А вообще, странно, но, блин, у меня даже до краев оптимизнутый код работает медленее чем у вас неоптимизированные - 14.5 секунд, это минимум с циклом развернутым до 4-х. До 2-х - 16.5, обычный - ~17. Бида...
    Так мы подгоняли параметр LOOP под каждый конкретный процессор, чтобы обычный вариант работал 10 секунд (чтобы сравнивать было удобнее)
    Запись от Evg размещена 05.05.2012 в 09:22 Evg вне форума
  11. Старый комментарий
    Аватар для Vourhey
    Да, это понятно, какая основная цель. Просто тот, кто потом прочитает, будет и это иметь ввиду. А то можно неприятный эффект получить неожиданно при компиляции с различными опциями.
    Запись от Vourhey размещена 05.05.2012 в 11:00 Vourhey вне форума
  12. Старый комментарий
    Мне кажется, что оптимизированный вариант будет быстрее даже на одном конвейере, так как позволяет совместить первый такт ожидания загрузки одного регистра с началом загрузки другого и инкремент одного регистра с тактом ожидания загрузки регистра. Обычный цикл при трёх тактах загрузки тратил 6 тактов? Значит на две итерации 12 тактов плюс как минимум по такт на сравнение и переход, и того 14, из них 4 такта ожидание, а оптимизированный ждёт всего 1 такт на две исходные итерации, что даёт 11 тактов, три такта экономии.
    Запись от размещена 05.05.2012 в 12:00
  13. Старый комментарий
    Аватар для Evg
    В случае одного конвейера бонусы будут следующие:
    - в два раза меньше переходов, чем в обычном варианте
    - две подряд операции чтения из памяти, а потому ожидание результата (т.е. щёлканье вхолостую конвейера) будет практически то же самое количество тактов, но это количество тактов потеряется на двух итерациях, вместо одной

    Т.е. и вправду тут эффект будет даже на одном конвейере
    Запись от Evg размещена 05.05.2012 в 12:35 Evg вне форума
  14. Старый комментарий
    Аватар для DenQ
    Спасибо! Очень познавательно.
    Запись от DenQ размещена 08.07.2012 в 02:20 DenQ вне форума
  15. Старый комментарий
    Аватар для talis
    Спасибо большое, подписываюсь на блог!
    Запись от talis размещена 11.07.2012 в 19:48 talis вне форума
  16. Старый комментарий
    Аватар для Kastaneda
    Буквально пару месяцев глубоко "варюсь" в этой теме, хочу дополнить:
    Цитата:
    Т.е., к примеру, если есть операция чтения из памяти в регистр %eax и операция инкрементации регистра %ebx, то эти две операции аппаратура может исполнять параллельно, поскольку они не конфликтуют по ресурсам. Но вот если бы вторая операция была операцией инкрементирования регистра %eax, то параллельное исполнение было бы невозможным: сначала нужно дождаться загрузки значения из памяти в %eax и только потом значение регистра инкрементировать.
    Честно говоря лень описывать это своими словами, поэтому просто скопипастил кусок статьи с wasm'а.

    Переименование регистров.

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

    В результате получаем шедевры, в которых вся программа использует один-два регистра с зависимостью по данным чуть ли не в каждой паре команд. Это сильно тормозило бы работу классического конвейера.

    Чтобы исправить ситуацию был разработан механизм переименования регистров, который позволял устранить все зависимости по данным, кроме реально существующих.

    Суть механизма в том, что процессор имеет больше регистров, чем доступно программисту. Каждый раз, когда команда прямо или косвенно пишет в регистр, ей выделяется новый физический регистр. Имеется также таблица отображения логических (видимых программисту) регистров на физические (видимые только процессору). Когда команде выделяется новый физический регистр, обновляется таблица – логический регистр, на который ссылалась команда, ставится в соответствие выделенному физическому регистру.

    При определении операндов команды имена логических регистров преобразуются в имена физических, после чего, значения последних заносятся в поля операндов микрооперации. Микрооперации работают только с физическими регистрами.

    Как можно увидеть, после декодирования команды N которая пишет в логический регистр R, все прочие команды, использующие в качестве операнда R будут обращаться к физическому регистру, выделенному для команды N. При этом, если какая-то команда после N будет писать в тот же логический регистр ей будет выделен новый регистр и все команды после нее будут использовать уже новый регистр. Это лучше показать на примере.
    1Команда пишет в R0 
    С этого момента R0 соответствует выделенному для команды регистру PHY0  
    2Команда читает из R0 
    Читает из PHY0  
    3Команда пишет в R0 
    С этого момента R0 соответствует выделенному для команды регистру PHY1  
    4Команда читает из R0 
    Читает из PHY1  


    Эффект от этого такой: по таблице видно, что команды стали независимы. Если команды, работающие с логическим R0, зависят друг от друга и их нельзя выполнять параллельно, то микрооперации, «разведены» по PHY0 и PHY1 и независимы, их можно выполнять параллельно.

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


    И еще
    C
    1
    
    for (i = 0; i < length; i += 2)
    должно же быть
    C
    1
    
    for (i = 0; i < length - 1; i += 2)
    Запись от Kastaneda размещена 08.09.2012 в 18:43 Kastaneda вне форума
  17. Старый комментарий
    Аватар для talis
    Kastaneda, не понял, а как тогда процессор определяет, значение какого физического регистра хочет получить команда, когда она читает из eax? Например, при syscall по int 80h, если мне не изменяет склероз, номер вызова мы пишем в eax. Сначала я что-то там в eax суммировал, оно пошло в PHY0, потом в eax же я кинул какой-нибудь 23h, оно пошло в PHY1, и сделал int 80h. Откуда int знает, что 23h в eax идёт ему, а не параллельно выполняемому суммированию?
    Запись от talis размещена 09.09.2012 в 12:52 talis вне форума
  18. Старый комментарий
    Аватар для Kastaneda
    Цитата:
    Сначала я что-то там в eax суммировал, оно пошло в PHY0, потом в eax же я кинул какой-нибудь 23h, оно пошло в PHY1, и сделал int 80h. Откуда int знает, что 23h в eax идёт ему, а не параллельно выполняемому суммированию?
    Ну можно предположить, что add это суммирование (понятно, что результат нужен), а mov тут понятно, что старое значение регистра тебе уже не нужно, значит новое значение нужно для следующей операции.
    Честно говоря тонкостей этого процесса я не знаю, похоже есть какая-то система, разруливающая подобные ситуации.
    Может Evg что-нибудь прояснит?
    Запись от Kastaneda размещена 09.09.2012 в 16:20 Kastaneda вне форума
  19. Старый комментарий
    Аватар для Evg
    Смысл переименования регистров примерно следующий

    Есть следующий фрагмент кода:

    Code
    mov 1 -> %eax
    st %eax -> [mem1]
    mov 2 -> %eax
    st %eax -> [mem2]
    В параллель тут ничего нельзя исполнить, т.к. всё завязано на один и тот же регистр %eax. Однако процессор в момент исполнения переделывает этот код во что-то типа:

    Code
    mov 1 -> %eax-2
    st  %eax-2 -> [mem1]
    mov 2 -> %eax
    st  %eax -> [mem2]
    Где %eax-2 - некий фиктивный (внутренний) регистр процессора, который пользователю по системе команд недоступен. А такой код уже можно распараллелить: сначала одновременно исполняются два mov'а, а затем два store'а. Переименовывание происходит для первой связки операций, но не для второй, т.к. ещё не известно, каким макаром далее используется регистр %eax, а в данной группе из 4 операций заведомо известно, что после первого store'а значение регистра %eax некритично. Процессор занимается подобными переименованиями лишь на небольшом фрагменте кода

    Всё это делается аппаратно и незаметно для пользовательской программы. Т.е. программа на самом деле и не знает, есть ли вообще такой механизм в процессоре. Думаю, что на всяких облегчённых версиях процессоров для нетбуков такого механизма нету, дабы упростить процессор и уменьшить энергопотребление
    Запись от Evg размещена 09.09.2012 в 20:32 Evg вне форума
  20. Старый комментарий
    Аватар для snake32
    Цитата:
    Где %eax-2 - некий фиктивный (внутренний) регистр процессора, который пользователю по системе команд недоступен.
    Вот те раз, а я как наивная дура думал что кодируя асм инструкции фактически касаюсь пальцами физических регистров ЦП. Уже даже регистры виртуальные!

    Не по теме:

    Может мы уже все в матрице

    Запись от snake32 размещена 17.09.2012 в 19:25 snake32 вне форума
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2019, vBulletin Solutions, Inc.
Рейтинг@Mail.ru