Визуализация «параллельного ускорения»  с помощью Cilkview

Создать новую статью

23.11.2009 12:00


В комплекте Cilk++ v.1.1 идет новое средство, которое помогает визуализировать производительность приложений – Cilkview. Cilkview запускает файл приложения и собирает данные о производительности заданных участков кода. Затем эти данные комбинируются с оценочными значениями работа/время (work/span), и на основании полученных результатов строится график.

Рассмотрим следующий параллельный алгоритм расчета чисел Фибоначчи:

int fib (int n) {
  int a, b;
  if (n < 2) return n;
  a = cilk_spawn fib(n - 1);
  b = fib(n - 2);
  cilk_sync;
  return a + b;
}

Направленный ациклический граф (НАГ), представляющий дерево вызовов fib(35), является двоичным деревом с множеством параллельных узлов, что является знаком широкого параллелизма. По функциям видно, что они сильно загружают процессор, а обращения к памяти ограничиваются страницей и имеют наивысшую локальность. Конечно, это ужасный способ расчета чисел Фибоначчи, но он хорошо подходит в качестве простого примера широкого класса алгоритмов, которые легко распараллеливаются. Чтобы позволить Cilkview составить прогноз об ускорении, необходимо в области вызова функции вставить следующий код:

  #include <cilkview.h>
  int cilk_main () {
    cilk::cilkview cv;
    cv.start();
    fib(35);
    cv.stop();
    cv.dump("fib-35");
    return 0;

start() и stop() показывают Cilkview интересующие нас участки кода. dump() ассоциирует собранные данные с меткой, которую будет использовать Cilkview при постройке графа. Теперь нужно скомпилировать программу и запустить Cilkview для постройки графа:

% cilkview ./fib

Cilkview исполняет программу на одном ядре, рассчитывая объем работы и потраченное время (work and span) в обозначенном участке кода. Чем круче наклон графика, тем более линейно ускорение алгоритма, вплоть до линии «теоретического предела» (Application Parallelism).  Теоретическое ограничение в данном случае не присутствует на графике, потому что в нашем примере оно слишком велико.

Cilkview сделал такой же прогноз в отношении данного алгоритма, что и мы. Более пологая линия соответствует реалистичному прогнозу производительности, - ускорение чуть меньше, и связано это с оверхедом Cilk++. Оба графика очень близки (почти неразличимы), следовательно Cilkview прогнозирует суперлинейное масштабирование алгоритма.

Чтобы проверить это, Cilkview может выполнить проверочные запуски. Для этого при запуске в командной строке необходимо указать опцию "-trials all". Никакого дополнительного кода не требуется:

% cilkview -trials all ./fib

Красными звездочками обозначены данные испытаний. По умолчанию Cilkview по одному разу запускает программу с количеством работников (workers) Cilk от 1 до n, где n – количество ядер. Приведенный график был получен на компьютере с 8 ядрами. Как и было предсказано, тестовые запуски масштабировались почти линейно. Некоторые вариации можно отнести за счет того, что с каждой конфигурацией было проведено только по одному тесту.

А что по поводу более распространенных алгоритмов, например, сортировки? Ниже приведен простой параллельный алгоритм quicksort:

void qsort (int *begin, int *end) {
  if (begin == end) return;
  --end; // end was one past the end of the range.
  int *middle = std::partition(begin, end, std::bind2nd(std::less(), *end));
  using std::swap;
  swap(*end, *middle);
  cilk_spawn qsort(begin, middle);
  qsort(++middle, ++end);
}

На первый взгляд кажется, что этот алгоритм также можно сильно распараллелить. Даже несмотря на то, что здесь много обращений к памяти, алгоритм quicksort хорошо работает с кэшем. Но нужно помнить, что в НАГ присутствует немалый последовательный узел в корне первой partition(). Таким образом, после рекурсивного вызова, каждый из дочерних процессов должен будет исполнять partition() на своем участке массива до того, как можно будет что-то делать параллельно. На самом деле бОльшая часть работы в quicksort делается в partition(), то есть последовательно. Анализ Cilkview наглядно это показывает:

На графике показана работа qsort над массивом из 10.000.000 целых чисел. Видно, что уровень идеального параллелизма (горизонтальная линия) достаточно низок и вместился в график. Результаты тестирования дают похожую картину:

Теперь рассмотрим следующий код параллельной процедуры memcpy:

void *parallel_memcpy (void *dst, void *src, size_t length) {
	size_t *idst = (size_t*)dst;
    size_t *isrc = (size_t*)src;
    
    size_t ilen = length / sizeof(size_t);
    size_t rem = ilen * sizeof(size_t);
    
    cilk_for (size_t i = 0; i < ilen; ++i){
    	idst[i] = isrc[i];
    }
    
    char *cdst = (char*)dst;
    char *csrc = (char*)src;
    
    for (size_t i = rem; i < length; ++i;) {
    	cdst[i] = csrc[i];
    }
    
    return dst;    
}

Очевидно, что здесь возможен очень «широкий» параллелизм. Вся работа выполняется в цикле cilk_for, автоматический выбор зерна должен сократить издержки скрытых cilk_spawn по отношению к объему работы, выполненному на каждой итерации. Концептуально в плане параллелизма memcpy() похожа на fib(). НАГ похож на граф fib() за исключением того, что здесь дерево сбалансировано. К сожалению, предсказание, основанное на данных work/span, абсолютно расходятся с данными тестов (parallel_memcpy() запускалась на массиве из 400 миллионов байт):

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

Последний, более удачный пример, - это параллельный алгоритм умножения матриц, разработанный Маттео Фриго и Мэфью Стиле (Matteo Frigo, Matthew Steele). Алгоритм задумывался как альтернатива другому, более интуитивному параллельному алгоритму умножения матриц, но который не очень эффективно использует кэш.

Конечно, алгоритм на самом деле не дает ускорения, превосходящего линейное, как это видно на графике в случае с 8 работниками. Это результат девиаций, ведь на каждом уровне запускается только один тест.

Cilkview идет в одном пакете вместе с Cilk++ v.1.1 как для Windows, так и для Linux. Данное средство включает и другие функции (например, можно инструментировать  разные участки кода, создавать файлы .csv, устанавливать количество ядер, для прогноза, и т.д.). Мы надеемся, что Cilkview поможет пользователям подтвердить или опровергнуть их интуитивные ожидания о возможностях параллельных алгоритмов. К тому же, он рисует прекрасные иллюстрации.

Дополнительные ресурсы по Cilk++

Данная статья является переводом блога Вилла Лейзерсона (Will Leiserson).
Оригинал доступен по адресу http://www.cilk.com/multicore-blog/bid/9769/Visualizing-Parallel-Speedup-with-Cilkview.