Пятнадцать человек на сундук мертвеца!

Как бы хорошо всем жилось, если бы всего было вдоволь! Не нужно было бы ни с кем делиться, и все были бы довольны.


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


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


chest
Очевидно, что при записи в память нужен эксклюзивный доступ к ней для того, кто пишет. Но и со чтением не все так хорошо. Это внешне может показаться, что потоки могут эффективно читать одновременно, ведь никакой ошибки не происходит. Однако, шина памяти работает намного медленнее, чем процессор, тем более несколько. И чтобы быть способной обслужить 10 процессоров, она должна быть в 10 раз быстрее них!


 


Как же сделать так, чтобы ситуация разрешилась? Есть несколько путей:




  1. При возможности, стараться меньше пользоваться оперативной памятью. К примеру, если что-то можно получить методом вычисления, то это может оказаться быстрее, чем из памяти в уже вычисленном виде.

  2. Обеспечить доступ процессоров к памяти в разное время. Таким образом нужно добиться, чтобы в один момент времени в ней был заинтересован только один процессор.

  3. Попытаться уместить все что нужно в кэш-память. Конечно, придется изрядно повозиться, ведь размер кэша очень ограничен.



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



Вариант 1 - отказ от использования памяти.



Что ж, внимательно посмотрев на задание можно увидеть, что формула довольно простая. Интересно проверить, насколько быстро она будет работать по сравнению с чтением из памяти?


Проверим, заменив вычисление суммы

s[k] += a1[k]

на это

seed = (a * seed + b) % m;

s[k] += seed - mean;


Отлично, программа стала работать в 2.5 раза медленнее на одном процессоре, и в 4 раза быстрее на 40! Конечно же, это можно еще ускорить, раскрыв цикл, к примеру, вот так:




seed1 = (a * seed1 + b) % m;

s[k] += seed - mean;

seed2 = (a * seed2 + b2) % m; 

s[k + 1] += seed2 - mean;


Что-ж, помогло, но этого недостаточно. Один процессор все равно не хочет давать большое ускорение, но уже есть прогресс - медленнее всего в 2 раза. Чтобы ускорить еще больше, вспомним, что под рукой есть процессор, поддерживающий SSE, тогда можно сделать следующее:



__m128 res;

s128[k/4] = _mm_add_ps(s128[k/4], _mm_sub_ps(seed128, mean128));						  

seed128 = _mm_add_ps(_mm_mul_ps(a128, seed128), b128);

res = _mm_div_ps(seed128, m128);

res = _mm_round_ps(res, _MM_FROUND_TO_ZERO);

res = _mm_mul_ps(res, m128);

seed128 = _mm_sub_ps(seed128, res);



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



Вариант 2 - распараллеливание доступа к памяти.


Как же применить это вариант к конкурсной задаче? Довольно сложно, как оказалось, просчет результата происходит быстрее, чем выдача элементов матрицы из памяти. Но это если использовать стандартный алгоритм перебора. Однако, существуют и другие, в числе которых, например, алгоритм, предложенный Такаока. Как оказалось, у него небольшая потребность в памяти и, как результат, прототип алгоритма показал коэффициент замедления меньше в 2 раза, по сравнению с алгоритмом перебора.



Вариант 3 - использование быстрой кэш-памяти.


Посмотрев еще раз на условие конкурса Acceler8 можно понять, что совсем необязательно хранить всю матрицу в памяти. Зная, что число уникальных символов не будет превышать m, можно хранить только эту уникальную последовательность. Такая последовательность по условию не превышает 20000 чисел, можно подсчитать, что она практически полностью умещается в кэш-память. Осталось только посчитать, как на основе массива выяснить значение искомого элемента в матрице.
Что же получается на выходе? Скорость работы с памятью на нескольких процессорах такая же, как и на одном, и нет большой константы вычисления, как в варианте 1. Выигрыш на 40 процессорах в 8 раз!



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


Reportez-vous à notre Notice d'optimisation pour plus d'informations sur les choix et l'optimisation des performances dans les produits logiciels Intel.