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

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

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

Варианты задания

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,
• вывод по результатам выплнения задания.