PARALLEL.RU

Дискуссионный клуб по параллельным вычислениям
Текущее время: 22 сен 20 23:19

Часовой пояс: UTC + 4 часа [ Летнее время ]




Начать новую тему Ответить на тему  [ Сообщений: 26 ]  На страницу 1, 2  След.
Автор Сообщение
СообщениеДобавлено: 2 мар 09 17:13 
Не в сети

Зарегистрирован: 28 май 07 12:10
Сообщения: 47
Откуда: ИПС РАН
Добрый день !

Заранее извиняюсь, что вопрос не по параллельным вычислениям, но связан, по крайней мере, с высокопроизводительными вычислениями :D ...

Есть простейшая программа на С для перемножения матриц:

Код:
#include <stdio.h>
#include <time.h>
#include <malloc.h>

main ( int argc, char *argv[] )
{
 int   i, j, k;
 clock_t t1, t2;
 double elapsed_time;

 int    N = 10;

 float *a, *b, *c;

 if ( argc > 1 )
  N = atoi ( argv [ 1 ] );

 a = (float *) malloc ( N * N * sizeof ( float ) );
 b = (float *) malloc ( N * N * sizeof ( float ) );
 c = (float *) malloc ( N * N * sizeof ( float ) );

 for ( i = 0; i < N; i++ )
  for ( j = 0; j < N; j++ ) {
   a [ i * N + j ] = 0.99;
   b [ i * N + j ] = 0.33;
   c [ i * N + j ] = 0.0;
  }

 t1 = clock();

 for ( i = 0; i < N; i++ )
  for ( j = 0; j < N; j++ )
   for ( k = 0; k < N; k++ )
    c [ i * N + j ] += a [ i * N + k ] * b [ k * N + j ];

 t2 = clock();

 elapsed_time = ( (double) ( t2 - t1 ) ) / CLOCKS_PER_SEC;
 printf ( "%f\n", c [ (N - 1) * N + ( N - 1 ) ] );

 printf ( "N = %d Elapsed time = %lf\n", N, elapsed_time );

}


Беру процессор Intel Xeon X5365 (3.00 MHz),
беру компилятор gcc (v.4.1.2), транслирую как
> gcc -O3 ...
и запускаю для разных N - размера матриц.
Получаю такую картину (результаты в сек.):
N Time
---------------------
1000 5.08
1024 19.47
1500 20.66
1536 40.91
1600 21.60
2000 47.13
2048 491.80 (!!!)

Из нее видно, что при N кратном 2, наблюдается резкое падение
производительности (для N=2048 - вообще, катастрофическое).

Вопрос - с чем это может быть связано, и есть ли ключик для
gcc, позволяющий устранить эту проблему ?

Если использовать icc, то результаты разумны и ожидаемы:

N Time
---------------------
1000 0.53
1024 0.62
1500 3.40
1536 3.73
1600 4.22
2000 8.52
2048 9.37


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: 2 мар 09 18:34 
Не в сети

Зарегистрирован: 13 сен 08 18:39
Сообщения: 74
Откуда: Москва
А попробуйте N не прописывать в виде константы в коде, а брать из командной строки (т.е. чтобы эта константа не была известна на этапе компиляции), похоже, что у gcc какие-то проблемы с раскруткой циклов. Думаю, это поможет.

Если можно, хотелось бы узнать о результатах такого эксперимента )

_________________
Дмитрий О. Коломиец.
IBM // МГУ, физфак, каф. математики.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: 2 мар 09 18:44 
Не в сети

Зарегистрирован: 28 май 07 12:10
Сообщения: 47
Откуда: ИПС РАН
kolomiec писал(а):
А попробуйте N не прописывать в виде константы в коде, а брать из командной строки


Она и так берется из командной строки:
Код:
if ( argc > 1 )
  N = atoi ( argv [ 1 ] );


Или я что-то не понял ?


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: 2 мар 09 19:17 
Не в сети

Зарегистрирован: 13 сен 08 18:39
Сообщения: 74
Откуда: Москва
YurySerdyuk писал(а):
kolomiec писал(а):
А попробуйте N не прописывать в виде константы в коде, а брать из командной строки


Она и так берется из командной строки:
Код:
if ( argc > 1 )
  N = atoi ( argv [ 1 ] );


Или я что-то не понял ?


хм... да, действительно, не заметил сразу...

тогда предлагаю попробовать сделать так:

Код:
int N;
...
if ( argc > 1 )
{
    N = atoi ( argv [ 1 ] );
}
else
{
    N = 10;
}

_________________
Дмитрий О. Коломиец.
IBM // МГУ, физфак, каф. математики.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: 3 мар 09 13:18 
Не в сети

Зарегистрирован: 11 дек 02 19:37
Сообщения: 872
Откуда: НИВЦ МГУ
Насколько я могу видеть, всё гораздо проще. Вы просто "вываливаетесь" из кеша. При этом gcc не умеет оптимизировать работу с кешем, а intel делает это хорошо и сглаживает эффект.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: 3 мар 09 14:20 
Не в сети

Зарегистрирован: 13 сен 08 18:39
Сообщения: 74
Откуда: Москва
Serg_Zhum писал(а):
Насколько я могу видеть, всё гораздо проще. Вы просто "вываливаетесь" из кеша. При этом gcc не умеет оптимизировать работу с кешем, а intel делает это хорошо и сглаживает эффект.


Это было бы логично, если бы не изначальная постановка вопроса,
YurySerdyuk писал(а):
Из нее видно, что при N кратном 2, наблюдается резкое падение
производительности


скорее всего это значит, что на нечетных N такого нет.

Кроме того, разница во времени выполнения для N = 1000 и N = 1024 в 3.9 раза... многовато,
а между N = 2000 и N = 2048 в 10.4 раза, так вообще ненормально, потому как в последней паре случаев ни один из массивов a, b, c целиком в 4MB кэша не помещается (одной паре ядер доступно 4Mb L2 кэша, а всего 8MB).

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

Еще возможные варианты: в зависимости от ключиков интеловский компилятор может векторизовать эти вычисления с использоваеним SSE3 инструкций, плюс распараллелить выполнение этого кода, в результате чего, код будет выполняться на всех 4 ядрах процессора, плюс оптимизиовать предвыборку данных из памяти в кэш. Что, в общем, и может в сумме дать такой выигрыш в скорости по сравнению с gcc. Однако если мы, опять же, не получаем относительно нормальную картину для нечетных N... тогда дело в другом.

_________________
Дмитрий О. Коломиец.
IBM // МГУ, физфак, каф. математики.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: 3 мар 09 14:32 
Не в сети

Зарегистрирован: 28 май 07 12:10
Сообщения: 47
Откуда: ИПС РАН
Я в первом сообщении неправильно сформулировал условия при которых
происходит падение производительности (а форум не позволяет редактировать старые сообщения) -
на самом деле, она происходит когда размер матриц кратен 512:

N gcc icc
--------------------------------
500 0.25 0.05
512 0.86 0.05
520 0.29 0.06
1000 4.46 0.34
1024 12.5 0.35
1100 6.48 0.52
1500 20.42 3.44
1536 30.43 3.81
1600 21.04 4.36
2000 46.75 8.65
2048 446.61 9.46
2100 59.80 10.01

Использование декларации
int N;
ничего не дала.

Если дело в кэше, то это очень как-то мудрено
и неприемлемо - обратите внимание на результат
для N= 2048.
И есть ли точные ссылки на то, как работают с кэшем
gcc и icc?
Может есть всё-таки какие-нибудь ключики для gcc ?

И еще такой абстрактный вопрос -
получается, что искусство запуска Linpack тоже заключается
в правильном подборе размера матриц ?

Кстати, хочу также заметить, что данная проблема
с gcc проявляет себя на всех архитектурах -
Intel Xeon, Pentium IV, AMD Athlon, Power PC(Cell BE), ...


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: 3 мар 09 14:55 
Не в сети

Зарегистрирован: 13 сен 08 18:39
Сообщения: 74
Откуда: Москва
А можно те же значения прогнать для кода с ключиком -O2?

_________________
Дмитрий О. Коломиец.
IBM // МГУ, физфак, каф. математики.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: 3 мар 09 15:27 
Не в сети

Зарегистрирован: 5 мар 05 14:01
Сообщения: 74
YurySerdyuk писал(а):
Я в первом сообщении неправильно сформулировал условия при которых
происходит падение производительности (а форум не позволяет редактировать старые сообщения) -
на самом деле, она происходит когда размер матриц кратен 512:

Если дело в кэше, то это очень как-то мудрено
и неприемлемо - обратите внимание на результат
для N= 2048.

А не играет ли тут роль длина строки кэша?


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: 3 мар 09 16:24 
Не в сети

Зарегистрирован: 28 май 07 12:10
Сообщения: 47
Откуда: ИПС РАН
kolomiec писал(а):
А можно те же значения прогнать для кода с ключиком -O2?


Вы правы - это дало некотору важную информацию -

во-первых, для icc стал наблюдаться аналогичный эффект
(хотя, начиная только с N >= 1500 ):

Код:
$ icc -O2 -o mm_float2 mm_float2.c
mm_float2.c(25): (col. 3) remark: LOOP WAS VECTORIZED.

$ ./mm_float2 1000
N = 1000 Elapsed time = 4.390000
$ ./mm_float2 1024
N = 1024 Elapsed time = 4.990000
$ ./mm_float2 1100
N = 1100 Elapsed time = 6.260000
$ ./mm_float2 1500
N = 1500 Elapsed time = 19.310000
$ ./mm_float2 1536
N = 1536 Elapsed time = 26.370000
$ ./mm_float2 1600
N = 1600 Elapsed time = 20.100000
$ ./mm_float2 2000
N = 2000 Elapsed time = 45.230000
$ ./mm_float2 2048
N = 2048 Elapsed time = 433.930000
$ ./mm_float2 2100
N = 2100 Elapsed time = 55.620000

$ icc -O3 -o mm_float2 mm_float2.c
mm_float2.c(25): (col. 3) remark: LOOP WAS VECTORIZED.
mm_float2.c(34): (col. 3) remark: PERMUTED LOOP WAS VECTORIZED.

$ ./mm_float2 2000
N = 2000 Elapsed time = 8.650000
$ ./mm_float2 2048
N = 2048 Elapsed time = 9.470000
$ ./mm_float2 2100
N = 2100 Elapsed time = 10.050000

Хотя тут для -O3 включена дополнительная векторизация,
не совсем понятно как это влияет на выборку аргументов
из памяти.

Во-вторых, gcc отказывается векторизовать эту программу:

Код:
$ gcc -O3 -ftree-vectorize -ftree-vectorizer-verbose=5 -o mm_float2 mm_float2.c

mm_float2.c:25: note: not vectorized: number of iterations cannot be computed.
mm_float2.c:35: note: not vectorized: number of iterations cannot be computed.
mm_float2.c:35: note: vectorized 0 loops in function.


Так что проблема остается - можно ли заставить gcc избежать такого падения производительности?


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: 3 мар 09 17:16 
Не в сети

Зарегистрирован: 30 ноя 05 16:09
Сообщения: 130
Откуда: Ростов-на-Дону
Небольшие провалы в производительность вблизи
размерностей 1024 и 2048 наблюдаются и на фортране.
Причем, и на gfortran и на ifort. Их видно только, если
выводить не только время, но и прозводительность =
число_операций/время. Но эти провалы не очень велики.
Мне кажется, что Ваши проблемы связаны с конкретной
версией компилятора. Версия 4.1.X - очень сырая версия.
gfortran в ней вообще не работоспособен, и, видимо,
есть проблемы и с gcc. Мы работаем с 4.3.2 - пока все неплохо.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: 3 мар 09 17:33 
Не в сети

Зарегистрирован: 28 май 07 12:10
Сообщения: 47
Откуда: ИПС РАН
У меня нет под рукой самой свежей версии gcc,
но проблемы остаются, по меньшей мере, в gcc 4.3.0:

Код:
$ cat /proc/cpuinfo
processor       : 0
vendor_id       : AuthenticAMD
cpu family      : 6
model           : 6
model name      : AMD Athlon(TM) MP 2000+
stepping        : 2
cpu MHz         : 1666.788
cache size      : 256 KB


Код:
$ ./mm_float 1000
N = 1000 Elapsed time = 21.730000
$ ./mm_float 1024
N = 1024 Elapsed time = 72.650000
$ ./mm_float 1100
N = 1100 Elapsed time = 31.040000
$ gcc --version
gcc (GCC) 4.3.0 20080428 (Red Hat 4.3.0-8)


У Вас есть возможность прогнать код под gcc 4.3.2 ?


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: 3 мар 09 17:39 
Не в сети

Зарегистрирован: 30 ноя 05 16:09
Сообщения: 130
Откуда: Ростов-на-Дону
Хорошо, мы скомпилируем Вашу программу.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: 3 мар 09 17:43 
Не в сети

Зарегистрирован: 13 сен 08 18:39
Сообщения: 74
Откуда: Москва
Цитата:
Вы правы - это дало некотору важную информацию -

во-первых, для icc стал наблюдаться аналогичный эффект
(хотя, начиная только с N >= 1500 ):

$ icc -O2 -o mm_float2 mm_float2.c
mm_float2.c(25): (col. 3) remark: LOOP WAS VECTORIZED.
...
$ icc -O3 -o mm_float2 mm_float2.c
mm_float2.c(25): (col. 3) remark: LOOP WAS VECTORIZED.
mm_float2.c(34): (col. 3) remark: PERMUTED LOOP WAS VECTORIZED.

Хотя тут для -O3 включена дополнительная векторизация,
не совсем понятно как это влияет на выборку аргументов
из памяти.

Во-вторых, gcc отказывается векторизовать эту программу:

$ gcc -O3 -ftree-vectorize -ftree-vectorizer-verbose=5 -o mm_float2 mm_float2.c

mm_float2.c:25: note: not vectorized: number of iterations cannot be computed.
mm_float2.c:35: note: not vectorized: number of iterations cannot be computed.
mm_float2.c:35: note: vectorized 0 loops in function.

Так что проблема остается - можно ли заставить gcc избежать такого падения производительности?


Вот оно, похоже, в чем дело...
Могу ошибиться, но готов поставить, что ключeвой момент здесь вот в этой фразе:
Код:
mm_float2.c(34): (col. 3) remark: PERMUTED LOOP WAS VECTORIZED.

icc считает, что цикл тербует перестановки, и наиболее эффективным будет вот такой вариант:

Код:
for ( i = 0; i < N; i++ )
    for ( k = 0; k < N; k++ )
        for ( j = 0; j < N; j++ )
            c [ i * N + j ] += a [ i * N + k ] * b [ k * N + j ];

Такая перестановка дает на внутреннем цикле чтение элементов b из одной строки кэша, а не из разных как в оригинальном варианте. В одной строке кэша будут находится и элементы c.

Бьюсь об косяк, что такая перестановка поможет.
Просьба повторить эксперимент для gcc с -O3.

_________________
Дмитрий О. Коломиец.
IBM // МГУ, физфак, каф. математики.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: 3 мар 09 17:54 
Не в сети

Зарегистрирован: 28 май 07 12:10
Сообщения: 47
Откуда: ИПС РАН
Да, Вы правы -

Код:
$ gcc -O3 -o mm_float3 mm_float3.c
$ ./mm_float3 500
N = 500 Elapsed time = 1.210000
$ ./mm_float3 512
N = 512 Elapsed time = 1.290000
$ ./mm_float3 520
N = 520 Elapsed time = 1.360000


Вопрос исчерпан - спасибо.


Вернуться к началу
 Профиль  
 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 26 ]  На страницу 1, 2  След.

Часовой пояс: UTC + 4 часа [ Летнее время ]


Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 1


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Перейти:  
cron
Создано на основе phpBB® Forum Software © phpBB Group
Русская поддержка phpBB