Задания к лабораторной работе по многопоточному программированию

Требования к отчету по лабораторной работе приведены в конце страницы.

Внимание! Разработанные программы, решающие дифференциальные уравнения, должны демонстрировать работоспособность в "неграфическом" режиме для пространственных сеток размерностью не менее 10000000 узлов для тысяч временных слоев. Это, в частности, означает, что недопустимо хранение в ОП всех результатов для всех временных слоев (шагов интегрирования). В качестве прототипа таких программ имеет смысл взять пример.

Внимание! Для обеспечения высокой производительности параллельных программ необходимо минимизировать накладные расходы, связанные с порождением и завершением потоков управления. А это значит, что потоки, многократно реализующие одну и ту же функцию (например, исключающие ненулевые элементы в строке/столбце в прямом ходе метода Гаусса), должны запускаться однократно.

1**. Разработать, используя средства многопотокового программивания, параллельную программу имитационного моделирования (микромини-GPSS) систем массового обслуживания в режиме, приближенном к режиму реального времени (здесь не имеется в виду режим реального времени, поддерживаемый ОС).
Допустимые элементы СМО - генератор транзакций (ГТ), обслуживающий аппарат (ОА), очередь (ОЧ), разветвитель (РВ). Каждый элемент имеет 1 вход (кроме ГТ). Каждый выход элемента может быть нагружен только на один вход другого (единственного) элемента. Точки соединения элементов друг с другом называются узлами. К узлу может быть подключено любое количество выходов элементов, но только один вход. Для выходов элементов узел играет роль соединителя (объединителя в один поток) транзакций.
Все параметры времени являются целыми числами, задающими количество секунд. Случайные величины имеют равномерный закон распределения от заданного минимального значения до заданного максимального значения.
Узлы СМО (точки соединения элементов друг с другом) нумеруются строго последовательными целыми числами, начиная с 0. Транзакции помечаются целыми положительными числами (0 играет роль признака отсутствия транзакции в узле). Методические указания. 2**. Разработать, используя средства многопотокового программирования, параллельную программу асинхронного двоичного моделирования логических схем с учетом задержек распространения сигналов на элементах.
Допустимые элементы: 2И, 2И-НЕ, 2ИЛИ, 2ИЛИ-НЕ, НЕ, ГС (генератор логического сигнала). Важно, что все элементы имеют только один выход, однако сигнал с этого выхода может поступать на входы многих элементов. Монтажное ИЛИ недопустимо. Единственным параметром всех элементов является целочисленная задержка распространения сигнала на элементе (в секундах !!!). ГС в качестве параметра принимает список (неопределенной длины) моментов переключения сигнала, начиная с уровня логического нуля.

Методические указания.



3*. Разработать, используя средства многопотокового программирования, параллельную программу решения методом Гаусса системы линейных алгебраических уравнений (СЛАУ), матрица коэффициентов которой имеет блочно-диагональный с окаймлением вид. В качестве тестовых использовать реальные матрицы из хранилища или самостоятельно генерировать тестовую СЛАУ описанным ниже способом. Размер диагонального блока, ширина окаймления, количество параллельно выполняющихся потоков - аргументы программы. Количество диагональных блоков матрицы равно количеству потоков управления. См. также замечание. При реализации обратного хода метода Гаусса недопустимо приведение матрицы к диагональному виду! Программа должна демонстрировать ускорение по сравнению с последовательным вариантом.

4*. Разработать, используя средства многопотокового программирования, параллельную программу решения методом Гаусса системы линейных алгебраических уравнений без учета разреженности матрицы коэффициентов. Параллельные потоки (их количество - аргумент программы) ведут исключение элементов в прямом ходе по столбцам. В качестве тестовых использовать реальные матрицы из
хранилища или самостоятельно генерировать тестовую СЛАУ описанным ниже способом. См. также замечание. При реализации обратного хода метода Гаусса недопустимо приведение матрицы к диагональному виду! Программа должна демонстрировать ускорение по сравнению с последовательным вариантом. Предусмотреть возможность диагностического вывода структуры матрицы коэффициентов в течение прямого хода метода Гаусса. Отчет должен содержать подробное (иллюстрированное картинками) описание использованного способа распараллеливания и синхронизации.

5*. Разработать, используя средства многопотокового программирования, параллельную программу решения методом Гаусса системы линейных алгебраических уравнений без учета разреженности матрицы коэффициентов. Параллельные потоки (их количество - аргумент программы) ведут исключение элементов в прямом ходе по строкам. В качестве тестовых использовать реальные матрицы из
хранилища или самостоятельно генерировать тестовую СЛАУ описанным ниже способом. См. также замечание. При реализации обратного хода метода Гаусса недопустимо приведение матрицы к диагональному виду! Программа должна демонстрировать ускорение по сравнению с последовательным вариантом. Предусмотреть возможность диагностического вывода структуры матрицы коэффициентов в течение прямого хода метода Гаусса. Отчет должен содержать подробное (иллюстрированное картинками) описание использованного способа распараллеливания и синхронизации.

6. Разработать, используя средства многопотокового программирования, параллельную программу решения одномерной нестационарной краевой задачи методом конечных разностей (МКР) с использованием явной вычислительной схемы.

Дан цилиндрический стержень длиной L и площадью поперечного сечения S. Цилиндричекая поверхность стержня теплоизолирована. На торцевых поверхностях стержня слева и справа могут иметь место граничные условия первого, второго или третьего родов. Распределение поля температур по длине стержня описывается уравнением теплопроводности

dT/dt = aT*d2T/dx2+gT

, где

aT=lambda/(CT*p) - коэффициент температуропроводности;

lambda - коэффициент теплопроводности среды;

CT - удельная теплоемкость единицы массы;

p - плотность среды;

gT=GT/(CT*p) - приведенная скорость взаимного превращения тепловой энергии в другие виды энергии, в нашем случае gT=0.

В явной вычислительной схеме МКР для аппроксимации производной температуры по времени в узле, принадлежащем i-ому временному и j-ому пространственному слоям, используется "разница вперед":

dT/dt|ij = (Ti+1j-Ti j)/ht
, где ht - шаг дискретизации по оси времени.

Для аппроксимации второй производной температуры по пространственной координате x используется "центральная разница":

d2T/dx2|ij = (Tij +1-2*Tij+Tij-1)/hx 2
, где hx - шаг дискретизации по пространственной координате.

Тогда алгебраизированное уравнение теплопроводности для узла, принадлежащего i-ому временному и j-ому пространственному слоям, принимает следующий вид (gT=0):

(Ti+1j-Tij)/ht = aT*(Tij+1-2*Tij+Ti j-1)/h2x

Такой вид уравнения позволяет в явном виде выразить единственную неизвестную:

Ti+1j = aT*(Ti j+1-2*Tij+Ti j-1)*ht/h2x+Tij

Что, в свою очередь, дает возможность просто организовать вычислительный процесс в виде "цикл в цикле" (без деталей, связанных с граничными условиями различного рода):

for (i=0; i<n; i++)
  for (j=0; j<m; j++)
    Ti+1j = ...
Напомним, что значения T0j известны из начальных условий. Здесь n=Tкон/ht, m - количество пространственных слоёв расчетной сетки.

Требуется разработать параллельную программу, в которой каждый поток управления ответственнен за расчеты для "полосы" расчетной сетки шириной в m/N пространственных узлов, где N - число потоков управления. Программа должна демонстрировать ускорение по сравнению с последовательным вариантом. Предусмотреть визуализацию результатов посредством утилиты gnuplot. При этом утилита gnuplot должна вызываться отдельной командой после окончания расчета.

Методические указания.
 


7*. Разработать, используя средства многопотокового программирования, параллельную программу решения одномерной нестационарной краевой задачи методом конечных разностей с использованием неявной вычислительной схемы. Постановка задачи описаны выше.

В неявной вычислительной схеме МКР для аппроксимации производной температуры по времени в узле, принадлежащем i-ому временному и j-ому пространственному слоям, используется "разница назад":

dT/dt|ij = (Tij-Ti-1 j)/ht
, где ht - шаг дискретизации по оси времени.

Для аппроксимации второй производной температуры по пространственной координате x используется "центральная разница":

d2T/dx2|ij = (Tij +1-2*Tij+Tij-1)/hx 2
, где hx - шаг дискретизации по пространственной координате.

Тогда алгебраизированное уравнение теплопроводности для узла, принадлежащего i-ому временному и j-ому пространственному слоям, принимает следующий вид (gT=0):

(Tij-Ti-1j)/ht = aT*(Tij+1-2*Tij+Ti j-1)/h2x

Это уравнение содержит три неизвестные Tij-1, Tij и Tij+1, относящиеся к текущему (i-ому) временному слою. Для отыскания всех неизвестных Tij, j=1...m, для каждого временного слоя необходимо решать систему линейных алгебраических уравнений вида:
Tij+1-(2+b)*Tij +Tij-1=b*Tij
, где b=h2x/(aT*ht).

Примечание. Использование неявной вычислительной схемы связано с решением системы ЛАУ на каждом временном слое. Следовательно, распараллеливание решения краевой задачи неявным методом сводится к распараллеливанию решения системы ЛАУ методом Гаусса. Распараллеливание же метода Гаусса проще всего реализуется в ситуации, когда матрица коэффициентов системы имеет блочно-диагональный с окаймлением вид. Матрица же коэффициентов автоматически получит такой вид, если нумерацию узлов расчетной сетки вести по такой простой схеме: сначала "внутренние" узлы всех фрагментов, на которые разбивается стержень, а в последнюю очередь - "соединительные" узлы. Кстати, сказанное выше справедливо и для метода прогонки (поскольку этот метод - частный случай метода Гаусса). См. также замечание. Программа должна демонстрировать ускорение по сравнению с последовательным вариантом. Обеспечить возможность запуска программы для произвольного числа потоков управления N и произвольного количества пространственных слоев m (допустимо, чтобы m было кратно N).

8. Разработать, используя средства многопотокового программирования, параллельную программу решения двумерной нестационарной краевой задачи методом конечных разностей с использованием явной вычислительной схемы. Объект моделирования - прямоугольная пластина постоянной толщины. Подробности постановки подобной задачи даны
выше. Возможны граничные условия первого и второго рода в различных узлах расчетной сетки. Количество потоков, временной интервал моделирования и количество (кратное 8) узлов расчетной сетки - параметры программы. См. также замечание. Программа должна демонстрировать ускорение по сравнению с последовательным вариантом. Предусмотреть визуализацию результатов посредством утилиты gnuplot. При этом утилита gnuplot должна вызываться отдельной командой после окончания расчета.

9*. Разработать, используя средства многопотокового программирования, параллельную программу решения двумерной стационарной краевой задачи методом конечных разностей. Объект моделирования - прямоугольная пластина постоянной толщины. Возможны граничные условия первого и второго рода в различных узлах расчетной сетки. Количество потоков и количество узлов (кратное 8) расчетной сетки - параметры программы. Подробности постановки задачи выяснить у преподавателя. Предусмотреть визуализацию результатов посредством утилиты gnuplot. При этом утилита gnuplot должна вызываться отдельной командой после окончания расчета.
Примечание. Распараллеливание решения стационарной краевой задачи сводится к распараллеливанию решения системы ЛАУ методом Гаусса (или его частным случаем - методом прогонки). Распараллеливание метода Гаусса проще всего реализуется в ситуации, когда матрица коэффициентов системы имеет
блочно-диагональный с окаймлением вид. Матрица же коэффициентов автоматически получит такой вид, если нумерацию узлов расчетной сетки вести по такой простой схеме: сначала "внутренние" узлы всех фрагментов, на которые разбивается пластина, а в последнюю очередь - "соединительные" узлы. См. также замечание. Программа должна демонстрировать ускорение по сравнению с последовательным вариантом.

10. Разработать многопотоковый вариант программы моделирования лифтовой системы (см. задание 8 из лаб. работы 1). При этом модели БН, ЛП и ЛГ выполняются в рамках отдельных потоков программы.

11. Разработать многопотоковый вариант программы моделирования распространения электрических сигналов в линейной цепочке RC-элементов (см. рис. ниже). Метод формирования математической модели - узловой. Метод численного интегрирования - явный Эйлера. Внешнее воздействие - источники тока и напряжения. Количество потоков, временной интервал моделирования и количество (кратное 8) элементов в цепочке - параметры программы. Программа должна демонстрировать
ускорение по сравнению с последовательным вариантом. Предусмотреть визуализацию результатов посредством утилиты gnuplot. При этом утилита gnuplot должна вызываться отдельной командой после окончания расчета.

Примечание. Узловой метод для формирования математической модели системы использует второй закон Кирхгофа - сумма токов в узле равна нулю. В данном задании для каждого j-ого узла цепочки уравнение баланса токов имеет вид
IRлев-IRправ-IC=0 или (Vij-1-Vij)/R-(Vij-Vij+1)/R-C*dVij/dt=0, где i - номер временного шага, V - потенциал узла.
В явном методе Эйлера для аппроксимации производной по времени используется выражение dVij/dt=(Vi+1j-Vij)/h, где h - шаг численного интегрирования.
В неявном методе Эйлера аппроксимация иная - dVij/dt=(Vij-Vi-1j)/h.

12*. Разработать многопотоковый вариант программы моделирования распространения электрических сигналов в линейной цепочке RC-элементов (см. рисунок и примечание выше). Метод формирования математической модели - узловой. Метод численного интегрирования - неявный Эйлера. Внешнее воздействие - источники тока и напряжения. Количество потоков, временной интервал моделирования и количество (кратное 8) элементов в цепочке - параметры программы. Программа должна демонстрировать
ускорение по сравнению с последовательным вариантом. Предусмотреть визуализацию результатов посредством утилиты gnuplot. При этом утилита gnuplot должна вызываться отдельной командой после окончания расчета.
Примечание. Использование неявного метода Эйлера связано с решением системы ЛАУ на каждом временном шаге. Следовательно, распараллеливание решения задачи численного интегрирования неявным методом сводится к распараллеливанию решения системы ЛАУ методом Гаусса. Распараллеливание же метода Гаусса проще всего реализуется в ситуации, когда матрица коэффициентов системы имеет
блочно-диагональный с окаймлением вид. Матрица же коэффициентов автоматически получит такой вид, если нумерацию узлов расчетной сетки вести по такой простой схеме: сначала "внутренние" узлы всех фрагментов, на которые разбивается цепочка элементов, а в последнюю очередь - "соединительные" узлы. См. также замечание.

13. Разработать многопотоковый вариант программы моделирования распространения электрических сигналов в двухмерной прямоугольной сетке RC-элементов (одномерный аналог которых представлен на рис. выше). Метод формирования математической модели - узловой. Метод численного интегрирования - явный Эйлера. Внешнее воздействие - источники тока и напряжения. Количество потоков, временной интервал моделирования и количество (кратное 8) элементов в сетке - параметры программы. Программа должна демонстрировать
ускорение по сравнению с последовательным вариантом. Предусмотреть визуализацию результатов посредством утилиты gnuplot. При этом утилита gnuplot должна вызываться отдельной командой после окончания расчета.

14*. Разработать многопотоковый вариант программы моделирования распространения электрических сигналов в двухмерной прямоугольной сетке RC-элементов (одномерный аналог которых представлен на рис. выше). Метод формирования математической модели - узловой. Метод численного интегрирования - неявный Эйлера. Внешнее воздействие - источники тока и напряжения. Количество потоков, временной интервал моделирования и количество (кратное 8) элементов в сетке - параметры программы. Программа должна демонстрировать
ускорение по сравнению с последовательным вариантом. Предусмотреть визуализацию результатов посредством утилиты gnuplot. При этом утилита gnuplot должна вызываться отдельной командой после окончания расчета.
Примечание. Использование неявного метода Эйлера связано с решением системы ЛАУ на каждом временном шаге. Следовательно, распараллеливание решения задачи численного интегрирования неявным методом сводится к распараллеливанию решения системы ЛАУ методом Гаусса. Распараллеливание же метода Гаусса проще всего реализуется в ситуации, когда матрица коэффициентов системы имеет
блочно-диагональный с окаймлением вид. Матрица же коэффициентов автоматически получит такой вид, если нумерацию узлов расчетной сетки вести по такой простой схеме: сначала "внутренние" узлы всех фрагментов, на которые разбивается сетка, а в последнюю очередь - "соединительные" узлы. См. также замечание.

15*. Разработать многопотоковый вариант программы моделирования распространения электрических сигналов в линейной цепочке LC-элементов (см. рис. ниже). Метод формирования математической модели - узловой. Метод численного интегрирования - неявный Эйлера. Внешнее воздействие - источники тока и напряжения. Количество потоков, временной интервал моделирования и количество (кратное 8) элементов в цепочке - параметры программы. Программа должна демонстрировать
ускорение по сравнению с последовательным вариантом. Предусмотреть визуализацию результатов посредством утилиты gnuplot. При этом утилита gnuplot должна вызываться отдельной командой после окончания расчета.
Примечание. Использование неявного метода Эйлера связано с решением системы ЛАУ на каждом временном шаге. Следовательно, распараллеливание решения задачи численного интегрирования неявным методом сводится к распараллеливанию решения системы ЛАУ методом Гаусса. Распараллеливание же метода Гаусса проще всего реализуется в ситуации, когда матрица коэффициентов системы имеет
блочно-диагональный с окаймлением вид. Матрица же коэффициентов автоматически получит такой вид, если нумерацию узлов цепочки элементов вести по такой простой схеме: сначала "внутренние" узлы всех фрагментов, на которые разбивается цепочка элементов, а в последнюю очередь - "соединительные" узлы. См. также замечание.


16*. Разработать многопотоковый вариант программы моделирования распространения электрических сигналов в двухмерной прямоугольной сетке LC-элементов (одномерный аналог которых представлен на рис. выше). Метод формирования математической модели - узловой. Метод численного интегрирования - неявный Эйлера. Внешнее воздействие - источники тока и напряжения. Количество потоков, временной интервал моделирования и количество элементов в сетке - параметры программы. Программа должна демонстрировать
ускорение по сравнению с последовательным вариантом. Предусмотреть визуализацию результатов посредством утилиты gnuplot. При этом утилита gnuplot должна вызываться отдельной командой после окончания расчета.
Примечание. Использование неявного метода Эйлера связано с решением системы ЛАУ на каждом временном шаге. Следовательно, распараллеливание решения задачи численного интегрирования неявным методом сводится к распараллеливанию решения системы ЛАУ методом Гаусса. Распараллеливание же метода Гаусса проще всего реализуется в ситуации, когда матрица коэффициентов системы имеет
блочно-диагональный с окаймлением вид. Матрица же коэффициентов автоматически получит такой вид, если нумерацию узлов сетки вести по такой простой схеме: сначала "внутренние" узлы всех фрагментов, на которые разбивается сетка, а в последнюю очередь - "соединительные" узлы. См. также замечание.

17*. Разработать многопотоковый вариант программы моделирования распространения электрических сигналов в линейной цепочке RLC-элементов (см. рис. ниже). Метод формирования математической модели - узловой. Метод численного интегрирования - неявный Эйлера. Внешнее воздействие - источники тока и напряжения. Количество потоков, временной интервал моделирования и количество элементов в цепочке - параметры программы. Программа должна демонстрировать
ускорение по сравнению с последовательным вариантом. Предусмотреть визуализацию результатов посредством утилиты gnuplot. При этом утилита gnuplot должна вызываться отдельной командой после окончания расчета.
Примечание. Использование неявного метода Эйлера связано с решением системы ЛАУ на каждом временном шаге. Следовательно, распараллеливание решения задачи численного интегрирования неявным методом сводится к распараллеливанию решения системы ЛАУ методом Гаусса. Распараллеливание же метода Гаусса проще всего реализуется в ситуации, когда матрица коэффициентов системы имеет
блочно-диагональный с окаймлением вид. Матрица же коэффициентов автоматически получит такой вид, если нумерацию узлов цепочки элементов вести по такой простой схеме: сначала "внутренние" узлы всех фрагментов, на которые разбивается цепочка элементов, а в последнюю очередь - "соединительные" узлы. См. также замечание.


18*. Разработать многопотоковый вариант программы моделирования распространения электрических сигналов в двухмерной прямоугольной сетке RLC-элементов (одномерный аналог которых представлен на рис. выше). Метод формирования математической модели - узловой. Метод численного интегрирования - неявный Эйлера. Внешнее воздействие - источники тока и напряжения. Количество потоков, временной интервал моделирования и количество элементов в сетке - параметры программы. Программа должна демонстрировать
ускорение по сравнению с последовательным вариантом. Предусмотреть визуализацию результатов посредством утилиты gnuplot. При этом утилита gnuplot должна вызываться отдельной командой после окончания расчета.
Примечание. Использование неявного метода Эйлера связано с решением системы ЛАУ на каждом временном шаге. Следовательно, распараллеливание решения задачи численного интегрирования неявным методом сводится к распараллеливанию решения системы ЛАУ методом Гаусса. Распараллеливание же метода Гаусса проще всего реализуется в ситуации, когда матрица коэффициентов системы имеет
блочно-диагональный с окаймлением вид. Матрица же коэффициентов автоматически получит такой вид, если нумерацию узлов сетки элементов вести по такой простой схеме: сначала "внутренние" узлы всех фрагментов, на которые разбивается сетка, а в последнюю очередь - "соединительные" узлы. См. также замечание.

19. Разработать, используя средства многопотокового программирования, параллельную программу решения уравнения струны методом конечных разностей с использованием явной вычислительной схемы. Количество потоков, временной интервал моделирования и количество (кратное 8) узлов расчетной сетки - параметры программы.
Уравнение струны имеет следующий вид:

d2z/dt2 = a2*d2z/dx2+f(x,t)

, где t - время, x - пространственная координата, вдоль которой ориентирована струна, z - отклонение (малое) точки струны от положения покоя, a - фазовая скорость, f(x,t) - внешнее "силовое" воздействие на струну.
Предусмотреть возможность задания ненулевых начальных условий и ненулевого внешнего воздействия. Программа должна демонстрировать
ускорение по сравнению с последовательным вариантом. Предусмотреть визуализацию результатов посредством утилиты gnuplot. При этом утилита gnuplot должна вызываться отдельной командой после окончания расчета.

20*. Разработать, используя средства многопотокового программирования, параллельную программу решения уравнения струны методом конечных разностей с использованием неявной вычислительной схемы. Количество потоков, временной интервал моделирования и количество (кратное 8) узлов расчетной сетки - параметры программы.
Уравнение струны имеет следующий вид:

d2z/dt2 = a2*d2z/dx2+f(x,t)

, где t - время, x - пространственная координата, вдоль которой ориентирована струна, z - отклонение (малое) точки струны от положения покоя, a - фазовая скорость, f(x,t) - внешнее "силовое" воздействие на струну.
Предусмотреть возможность задания ненулевых начальных условий и ненулевого внешнего воздействия. Программа должна демонстрировать
ускорение по сравнению с последовательным вариантом. Предусмотреть визуализацию результатов посредством утилиты gnuplot. При этом утилита gnuplot должна вызываться отдельной командой после окончания расчета.
Примечание. Использование неявной вычислительной схемы связано с решением системы ЛАУ на каждом временном слое. Следовательно, распараллеливание решения краевой задачи неявным методом сводится к распараллеливанию решения системы ЛАУ методом Гаусса. Распараллеливание же метода Гаусса проще всего реализуется в ситуации, когда матрица коэффициентов системы имеет
блочно-диагональный с окаймлением вид. Матрица же коэффициентов автоматически получит такой вид, если нумерацию узлов расчетной сетки вести по такой простой схеме: сначала "внутренние" узлы всех фрагментов, на которые разбивается струна, а в последнюю очередь - "соединительные" узлы. Кстати, сказанное выше справедливо и для метода прогонки (поскольку этот метод - частный случай метода Гаусса). См. также замечание.

21. Разработать, используя средства многопотокового программирования, параллельную программу решения уравнения прямоугольной мембраны методом конечных разностей с использованием явной вычислительной схемы. Количество потоков, временной интервал моделирования и количество (кратное 8) узлов расчетной сетки - параметры программы.
Уравнение мембраны имеет следующий вид:

d2z/dt2 = a2*(d2z/dx2+d2z/dy2)+f(x,y,t)

, где t - время, x, y - пространственные координаты, z - отклонение (малое) точки мембраны от положения покоя, a - фазовая скорость, f(x,y,t) - внешнее "силовое" воздействие на мембрану перпендикулярное ее плоскости.
Предусмотреть возможность задания ненулевых начальных условий и ненулевого внешнего воздействия. Программа должна демонстрировать
ускорение по сравнению с последовательным вариантом. Предусмотреть визуализацию результатов посредством утилиты gnuplot. При этом утилита gnuplot должна вызываться отдельной командой после окончания расчета.

22*. Разработать, используя средства многопотокового программирования, параллельную программу решения уравнения прямоугольной мембраны методом конечных разностей с использованием неявной вычислительной схемы. Количество потоков, временной интервал моделирования и количество (кратное 8) узлов расчетной сетки - параметры программы.
Уравнение мембраны имеет следующий вид:

d2z/dt2 = a2*(d2z/dx2+d2z/dy2)+f(x,y,t)

, где t - время, x, y - пространственные координаты, z - отклонение (малое) точки мембраны от положения покоя, a - фазовая скорость, f(x,y,t) - внешнее "силовое" воздействие на мембрану перпендикулярное ее плоскости.
Предусмотреть возможность задания ненулевых начальных условий и ненулевого внешнего воздействия. Программа должна демонстрировать
ускорение по сравнению с последовательным вариантом. Предусмотреть визуализацию результатов посредством утилиты gnuplot. При этом утилита gnuplot должна вызываться отдельной командой после окончания расчета.
Примечание. Использование неявной вычислительной схемы связано с решением системы ЛАУ на каждом временном слое. Следовательно, распараллеливание решения краевой задачи неявным методом сводится к распараллеливанию решения системы ЛАУ методом Гаусса. Распараллеливание же метода Гаусса проще всего реализуется в ситуации, когда матрица коэффициентов системы имеет
блочно-диагональный с окаймлением вид. Матрица же коэффициентов автоматически получит такой вид, если нумерацию узлов расчетной сетки вести по такой простой схеме: сначала "внутренние" узлы всех фрагментов, на которые разбивается мембрана, а в последнюю очередь - "соединительные" узлы. Кстати, сказанное выше справедливо и для метода прогонки (поскольку этот метод - частный случай метода Гаусса). См. также замечание.

23. Разработать программу, моделирующую в реальном времени работу поточной линии, состоящей из N станков и обрабатывающей заготовки M типов.
Каждая заготовка последовательно проходит обработку на всех станках линии. Времена обработки заготовок каждого типа (в секундах) на каждом станке линии задаются в виде прямоугольной матрицы размером NxM в конфигурационном файле line.cnf. Первые 2 строки этого файла содержат числа N и M.
Программа реализуется N+1 потоком управления. Корневой поток порождает N потоков-"станков", передавая им информацию о временах обработки заготовок разного типа. Далее этот поток читает со стандартного ввода последовательность номеров типов заготовок и передает её на вход первого потока-"станка". Потоки-"станки" имитируют обработку заготовок с помощью функции sleep() и передают номера типов обработанных заготовок потокам-приёмникам.
Предусмотреть вывод информации о ходе обработки заготовок.
Некоторые из возможных модификаций задания:

24. Разработать программу, моделирующую в реальном времени работу кооператива подвижных манипуляторов (ПМ) и блока управления (БУ) ими.
БУ реализуется в качестве головного (корневого) потока и воспринимает со стандартного ввода команды создания/уничтожения ПМ и управления ими. ПМ реализуются в рамках отдельных вновь порождаемых (и убиваемых) потоков. ПМ существуют в прямоугольном дискретном поле размером NxM и могут передвигаться в нем в 4-х направлениях с временными затратами T секунд на клетку. При достижении границы поля ПМ останавливается. ПМ информируют о смене своего положения, например, выдавая на стандартный вывод (что неправильно, почему?) строку "кто: откуда=>куда".
БУ читает со стандартного ввода команды пользователя (синтаксис придумать самостоятельно), позволяющие создавать/уничтожать ПМ, задавать их направление и "скорость" движения (количество ПМ не ограничено).
Некоторые из возможных модификаций задания:
25. Разработать программу, реализующую обработку строк текста и функционирующую в рамках 3-х потоков управления.
Поток 0 (корневой) порождает 2-ух потомков (напрямую или опосредованно, решать вам) и организует передачу строк символов в последовательности "поток-0 => поток-1 => поток-2".
Поток 0 получает строку символов латинского алфавита со стандартного ввода и передаёет ее в неизменном виде потоку 1.
Поток 1 умеет преобразовывать полученную от потока 0 строку символов различными способами:
Поток 2 умеет преобразовывать полученную от потока 1 строку символов следующими способами: Основная функциональноcть потока 0 - считывание со стандартного ввода строк латинского текста и передача их (строк) потоку 1. Однако сигнал SIGINT (Ctrl/C) переводит поток 0 в состояние однократного чтения со стандартного ввода команды перехода потока 1 или 2 к новому способу обработки поступающих к нему строк текста (синтаксис команд придумать самостоятельно).
Обязательно обеспечить индикацию результатов работы каждого потока в правильной временной последовательности.

26. Разработать программу, реализующую обработку текстовых файлов и функционирующую в рамках 3-х потоков.
Корневой поток является управляющим и принимает в качестве аргументов имена 2-х файлов. В начале своей работы он порождает 2 потока, передавая каждому по одному имени файла.
Первый порожденный поток осуществляет побайтное считывание файла и вывод с небольшой задержкой прочитанных байт (по одному на строке) в верхнем регистре на стандартный вывод.
Второй порожденный поток осуществляет побайтное считывание файла и вывод с небольшой задержкой прочитанных байт (по одному на строке) в нижнем регистре на стандартный вывод.
Порожденные потоки функционируют параллельно.
Управляющий поток считывает со стандартного ввода строки, содержащие имена новых текстовых файлов и заставляет порожденные потоки немедленно переходить на обработку новых файлов по следующей схеме: второй порожденный поток переходит к обработке файла, ранее обрабатываемого первым потоком; первый порожденный поток начинает обрабатывать файл, имя которого ему передает управляющий поток.

Представлении матриц в языке С

Отмечается повальное использование студентами в программах на языке С для представления прямоугольных матриц конструкций вида
double matrix[N][M];
где N и M - константы.
Этот способ кажется удобным в программировании, поскольку позволяет адресоваться к элементам матрицы "естественным" способом - matrix[i][j]. Однако необходимо осознавать, что такому представлению присущ ряд серьёзных недостатков.
Поэтому в лабораторных работах рекомендуется для хранения прямоугольных матриц размером NxM использовать одномерный массив:
double *matrix;
. . .
matrix = (double *) calloc (N*M, sizeof(double));
Для доступа к элементу в i-ой строке и j-ом столбце матрицы применяется конструкция matrix[M*i+j].

Генерация тестовой системы ЛАУ

При невозможности использования готовых матриц коэффициентов из хранилища матрицу коэффициентов и вектор правых частей системы ЛАУ можно сгенерировать самостоятельно по следующей простой схеме.
  1. Положить равными 1 все элементы вектора неизвестных X (это впоследствии облегчит контроль правильности решения системы ЛАУ).
  2. Присвоить всем элементам матрицы коэффициентов A случайные значения из диапазона, скажем, -1,0 ... 1,0.
  3. Рассчитать значения всех элементов вектора правых частей B путем перемножения A и X (при единичном векторе X перемножение сводится к суммированию элементов строк A).
Внимание! Размерность генерируемых систем не должна быть "игрушечной", количество неизвестных должно превышать 1000.

Система ЛАУ со структированной матрицей коэффициентов

Матрица называется блочно-диагональной с окаймлением, если она имеет следующий вид.
A110... 0A1N
0A22... 0A2N
......... ......
00... AN-1,N-1AN-1,N
AN1AN2... AN,N-1ANN
Решение методом Гаусса системы ЛАУ с матрицей коэффициентов такой структуры может быть легко распараллелено.
Во-первых, очевидно, что независимо друг от друга может быть выполнено приведение к верхнетреугольному виду в прямом ходе Гаусса диагональных блоков A11 ... AN-1,N-1 во всех горизонтальных лентах матрицы (кроме последней).
Во-вторых, параллельно (и это менее очевидно) может быть выполнено исключение элементов блоков нижнего окаймления AN1 ... AN,N-1 в том же прямом ходе Гаусса.
В-третьих, очевидно, что после прямого и обратного хода Гаусса по самой нижней ленте системы ЛАУ, возможно независимое выполнение обратного хода по каждой оставшейся ленте.

Эффект от распараллеливания

Параллельные программы, предназначенные для решения вычислительных задач (систем алгебраических и дифференциальных уравнений), должны продемонстрировать сокращение времени решения.
Для этого, во-первых, необходимо замерять время выполнения программ. Здесь полезной может оказаться команда time (1). Однако эта команда выдаёт время выполнения программы целиком, нас же больше интересует "чистое" время решения без накладных расходов, связанных с генерацией тестовых матриц, вводом-выводом, подготовкой данных для gnuplot и т.п. Поэтому для определения времени исполнения отдельных этапов вычислительного процесса имеет смысл использовать функцию gettimeofday, обеспечивающую точность замера в 1 мкс. Кроме того удобно обложить #ifdef'ами все фрагменты текста программы, не связанные непосредственно с целевыми вычислениями.
Во-вторых, для выявления эффекта от распараллеливания необходимо кроме параллельной версии программы иметь и последовательный вариант. В некоторых заданиях (например, связанных с МКР) запуск программы в рамках одного потока или одного процесса MPI даёт временные затраты почти сопоставимые с затратами последовательной версии. В других (в первую очередь это относится к решению системы ЛАУ с блочно-диагональной матрицей коэффициентов) последовательную версию программы приходиться создавать специально. При многопотоковом программировании параллельная программа легко превращается в последовательную просто поочерёдным запуском потоков, в случае же MPI-программы ситуация более сложная.
Внимание. Существует тонкий момент в оценке эффекта от распараллеливания при решении системы ЛАУ с блочно-диагональной матрицей коэффициентов. Дело в том, что увеличение (напр., удвоение) количества параллельно исполняемых потоков/процессов приводит к уменьшению количества элементов в диагональных блоках (в 4 раза), а, следовательно, и к уменьшению общего числа ненулевых элементов в матрице коэффициентов. А это снижение общего числа ненулевых элементов само по себе (без учёта параллельности) обеспечивает ускорение решения (в идеале, в 4 раза).

Содержание отчета