8970

только работа с переменной в левой части оператора присваивания, при этом вычисления в правой части не обязаны быть атомарными.

3. Построение графиков зависимости времени выполнения последовательного и параллельных (редукция, критическая секция и директива atomic) алгоритмов от количества интервалов разбиения (N). Анализ эффективности параллельного алгоритма.

3.1.Добавьте в проект все три модификации параллельного алгоритма, а также последовательный алгоритм.

3.2.Выполните замеры времени выполнения всех алгоритмов только для параллельного фрагмента кода и соответсвующего фрагмента в последоветельном алгоритме.

3.3.Проведите 5 экспериментов, изменяя количество интервалов разбиения, таким образом, чтобы время выполнения алгоритмов составляло не менее 20 секунд. При выполнении параллельных алгоритмов используйте все доступные операционной системе ядра. Каждый поток должен выполняться на одном процессоре (ядре). Результаты экспериментов занесите в Таблицу 2.

Количество ядер составляет _________шт.

3.4.Вычислите ускорение (Sp = T1 / Tp) и эффективность (Ep = Sp / p) параллельных алгоритмов и внесите результаты вычислений в таблицу 2. По данным таблицы 2 постройте графики зависимостей ускорения и эффективности от количества интервалов разбиения разместив их как показано в Лабораторной работе №2 на рис. 12.

3.5.На основе полученных данных сформулируйте вывод об эффективности параллельных алгоритмов.

ЛАБОРАТОРНАЯ РАБОТА № 4

Тема: Создание консольного многопоточного Windows-приложения, выполняющего перемножение матрицы на вектор для систем с общей памятью.

Цель работы: Изучение директив, предназначенных для распределения работы по потокам на примере параллельных циклов и параллельных секций.

Лабораторная работа состоит из трёх последовательно выполняемых заданий.

1.Написать последовательную программу перемножения квадратной матрицы

A(N,N) на вектор B(N).

2.Написать параллельную программу на основе технологии OpenMP, распараллелив операции по перемножению элементов матрицы и вектора (реализовать в двух вариантах: через директиву распараллеливания цикла по виткам - pragma omp for и директиву создания отдельных секций - pragma omp sections).

3.Построить графики зависимости времени выполнения последовательного и параллельного алгоритмов от количества элементов N массивов А и В. Проанализировать эффективность параллельного алгоритма.

Пояснения к выполнению работы

1. Написание последовательной программы перемножения квадратной матрицы A(N,N) на вектор B(N).

1.1.Создать пустой проект консольного Windows – приложения в среде Visual С++ (см. Лабораторная работа №1).

1.2.Написать код, включающий в себя:

-инициализацию элементов матрицы А и вектора В произвольными значениями, например, A aij , aij i j, B bi ,bi i .

-вывод на экран значений элементов массивов А и В.

-вычисление результирующего вектора С.

-вывод на экран результатов вычислений в виде таблицы.

Алгоритм перемножения матрицы A(N,N) на вектор B(N) представлен на блок-схеме (рис. 15). В связи с тем, что нумерация элементов массива на языке Си начинается с нуля, циклы для массива размером N в приведённой блок-схеме организованы от нуля до N-1.

1.3. Запустить программу.

Начало

Ввод размера N массивов. Coздание массивов A и B

Организация двойного цикла по номеру строки i и по номеру столбца j от 0

Инициализация матрицы A(aij=i*j) и вектора B(bi=i)

Вывод элементов массивов A и

B на экран

Организация двойного цикла по номеру строки i и по номеру столбца j от 0

Вычисление результирующего вектора С

C[i]=C[i]+A[i][j]*B[j] – суммирование по индексу j

Организация цикла по номеру строки i от 0 до N-1

Вывод элементов вектора С на экран

Конец

Рис. 15. Блок-схема алгоритма перемножения матрицы A на вектор B.

2. Написание параллельной программы на основе технологии OpenMP, распараллелив операции по перемножению элементов матрицы и вектора (реализовать в двух вариантах: через директиву распараллеливания цикла по виткам - pragma omp for и директиву создания отдельных секций - pragma omp sections).

2.1.Модифицируйте программу, написанную в Задании 1, добавив в неё директиву, создающую параллельную область: #pragma omp parallel. Укажите видимость общих и локальных переменнных для потоков через опции shared и private. Массивы А, В и С должны быть объявлены как общие.

2.2.Добавьте директиву #pragma omp for для распараллеливания циклов так чтобы разные потоки вычисляли разные части вектора С.

2.3.Для распределения элементов массивов через параллельные секции используйте директиву # pragma omp sections. Эта директива определяет набор независимых секций кода, каждая из которых выполняется своей нитью (потоком). Если количество нитей (потоков) больше количества секций, то часть нитей (потоков) для выполнения данного блока секций не будет задействована. Если количество нитей (потоков) меньше количества секций, то некоторым (или всем) нитям (потокам) достанется более одной секции. Пример использования параллельных секций показан ниже:

#pragma omp parallel

{

#pragma omp sections

{

#pragma omp section

{

//код первой секции

}

#pragma omp section

{

//код второй секции

}

#pragma omp section

{

//код третьей секции

}

}

}

3. Построение графиков зависимости времени выполнения последовательного и параллельного алгоритмов от количества элементов N массивов А и В. Анализ эффективности параллельного алгоритма.

3.1. Добавьте в проект оба варианта параллельного алгоритма, а также последовательный алгоритм.

3.2.Выполните замеры времени выполнения всех алгоритмов только для параллельного фрагмента кода и соответсвующего фрагмента в последоветельном алгоритме.

3.3.Проведите 5 экспериментов, изменяя размер массивов A и B, таким образом, чтобы время выполнения алгоритмов составляло не менее 20 секунд. При выполнении параллельных алгоритмов используйте все доступные операционной системе ядра. Каждый поток должен выполняться на одном процессоре (ядре). Результаты экспериментов занесите в Таблицу 3.

Количество ядер составляет _________шт.

3.4.Вычислите ускорение (Sp = T1 / Tp) и эффективность (Ep = Sp / p) параллельных алгоритмов и внесите результаты вычислений в таблицу 3. По данным таблицы 3 постройте графики зависимостей ускорения и эффективности от количества элементов массивов, разместив их как показано в Лабораторной работе №2 на рис. 12.

3.5.На основе полученных данных сформулируйте вывод об эффективности параллельных алгоритмов.

Начало

Ввод размера N матриц

Организация двойного цикла по номеру строки i и по номеру столбца j

Инициализация матриц A[i][j]=B[i][j]=i*j

Вывод эл-тов матриц A и B на экран

Организация двойного цикла по номеру строки i и по номеру столбца j

от 0 до N-1

С[i][j]=0

Организация цикла по k от 0 до N-1

Вычисление результирующей матрицы С

С[i][j]=С[i][j]+А[i][k]*В[k][j]

Организация двойного цикла по номеру строки i и по номеру столбца j

от 0 до N-1

Вывод эл-тов матрицы С на экран

Конец

Рис. 16. Блок-схема алгоритма перемножения матриц A и B.

2.Написание параллельной программы на основе технологии OpenMP, выбрав наиболее оптимальный алгоритм распараллеливания операций по перемножению матриц.

Проанализируйте эффективность разных методов распараллеливания алгоритмов из Лабораторных работ №№ 2 – 4 и напишите наиболее оптимальный на Ваш взгляд параллельный алгоритм перемножения двух квадратных матриц, модифицировав соответствующим образом программу, написанную в Задании 1.

3.Построение графиков зависимости времени выполнения последовательного и параллельного алгоритмов от размера матриц А и В и числа процессов. Анализ эффективности параллельного алгоритма.

3.1.Добавьте в проект реализацию параллельного и последовательного алгоритмов.

3.2.Выполните замеры времени выполнения всех алгоритмов только для параллельного фрагмента кода и соответсвующего фрагмента кода в последоветельном алгоритме.

3.3.Проведите 5 экспериментов, изменяя размер массивов A и B, таким образом, чтобы время выполнения алгоритмов составляло не менее 20 секунд. При выполнении параллельных алгоритмов используйте все доступные операционной системе ядра. Каждый поток должен выполняться на одном процессоре (ядре). Результаты экспериментов занесите в Таблицу 4.

Количество ядер составляет _________шт.

3.4.Вычислите ускорение (Sp = T1 / Tp) и эффективность (Ep = Sp / p) параллельных алгоритмов и внесите результаты вычислений в таблицу 4. По данным таблицы 4 постройте графики зависимостей ускорения и эффективности от количества элементов массивов, разместив их как показано в Лабораторной работе №2 на рис. 12.

3.5.На основе полученных данных сформулируйте вывод об эффективности параллельного алгоритма.

ПРИЛОЖЕНИЕ 1. Сводный перечень некоторых директив OpenMP

ПРИЛОЖЕНИЕ 2. Сводный перечень параметров (опций) директив OpenMP