Практическое задание 3

Цель: изучить особенности взаимодействия ядер в многоядерной системе через общую память.

Постановка задачи

Реализовать примитив синхронизации "барьер" в системе с общей памятью.

Варианты задания
  1. глобальный "линейный" барьер,
  2. локальная синхронизация между "соседними" потоками,
  3. глобальный "древовидный" барьер с учётом отображения потоков на ядра и сокеты.

Тестирование проводить на модельной задаче, реализующей вычисления по схеме двумерного синхронного клеточного автомата с полем размером M×N (например, игра "Жизнь", различные фильтры обработки изображений, реализация явной разностной схемы, ...). Распараллеливание задачи выполнить путём 1D-декомпозиции поля. Для распараллеливания использовать какое-либо средство многопоточного программирования (OpenMP, POSIX Threads, ...). При собственной реализации барьера в случае необходимости следует использовать volatile переменные и атомарные операции.

Следует провести тестирование при следующих размерах массива M×N:

  • Половина размера кэша L1 (~64×32),
  • Половина размера кэша L2 (~128×128),
  • Половина размера кэша L3 (~512×256),
  • В 10 раз больше размера кэша L3 (~2048×1024).

Кроме того, используемые для синхронизации переменные следует располагать в памяти тремя способами (здесь tid - номер потока):

  • плотная упаковка (объявление: int h[128][1], обращение: h[tid][0]),
  • каждая переменная в отдельной кэш-строке (объявление: int h[128][64], обращение: h[tid][0]),
  • каждая переменная на отдельной странице памяти (объявление: int h[128][4096], обращение: h[tid][0]).

В качестве оценки производительности использовать время (минимальное и среднее), затраченное на синхронизацию на одной итерации.

Для каждого размера поля M×N определить наилучший способ расположения переменных в памяти, а также сравнить результаты со "стандартной" реализацией барьера в используемой библиотеке многопоточного программирования. В результате должно получиться: 4 (размер массива) × ( 3 (расположение внутренних переменных) + 1 (библиотечная реализация) ) = 16 оценок времени.

Отчёт

Отчёт высылайте преподавателю на почту. В отчет необходимо включить:

  • Фамилию И.О.,
  • постановку задачи,
  • листинг программы на Си,
  • фрагмент кода на ассемблере вашей функции-барьера в одном из вариантов,
  • характеристики вычислительной системы, использованной при тестировании,
  • полученные оценки времён в таблице, лучшие параметры для каждого размера M×N,
  • вывод по результатам выплнения задания.