Содержание
Введение
1. Постановка задачи
2. Анализ исходных данных
3. Описание используемой структуры ВС
4. Описание алгоритма решения задачи
4.1 Основные определения
4.2 Алгоритм построения нитей в сети G
4.3 Алгоритм уплотнения нитей
4.4 Алгоритм распределения вершин графа решаемой задачи на узлах вычислительной сети с одинаковой степенью вершин
5. Описание интерфейса программы
6. Результаты работы программы
Заключение
Введение В настоящее время увеличилась тенденция использования многопроцессорных систем для обработки данных. Для эффективного использования таких систем необходимо, во-первых, преобразовывать последовательные алгоритмы обработки данных в параллельные, а во-вторых, использовать специальные алгоритмы (планировщики), которые позволят распределить операторы параллельных алгоритмов по процессорам вычислительной сети. По своей сути, планировщик является частью основного алгоритма и служит для обеспечения эффективного выполнения основного алгоритма в условиях конкретной ВС.
При этом эти алгоритмы-планировщики могут использовать различные критерии оптимизации. Например, для получения такого распределения, при котором максимально эффективно будут использоваться все процессоры ВС или для получения такого распределения, при котором заданный алгоритм будет решаться за минимальное время при минимизации числа процессоров.
Разработка подобных алгоритмов связана с рядом трудностей. В частности, необходимо проанализировать большое количество условий, учесть множество различных ситуаций, которые возникают при распределении операторов по нитям и нитей по процессорам ВС. Кроме того, необходимы точные исходные данные, такие как времена расчета отдельно взятых операторов, объем передаваемых данных между ними. Необходимо также знать времена передачи данных между процессорами в структуре ВС.
Решение задачи создания таких алгоритмов и их последующее применение увеличит быстродействие обработки данных на многопроцессорных системах.
1. Постановка задачи Цель - найти оптимальный план распределения решаемой задачи по узлам вычислительной сети (ВС).
Для достижения этой цели необходимо разработать алгоритм распределения вершин информационного графа по процессорам заданной структуры вычислительной сети. В результате этого распределения исходная задача должна решаться за минимально возможное время на ВС. Число процессоров при этом должно быть минимизировано с учетом обеспечения решения задачи за минимальное время.
Далее необходимо реализовать полученный алгоритм в виде программы. Программа должна обеспечить:
1. Возможность получения матрицы следования для различных информационных графов. Это позволит лучше протестировать полученный алгоритм распределения.
2. Построение информационного графа решаемой задачи, по его заданной матрице следования.
3. Построение диаграммы размещения нитей на узлах ВС.
4. Построение временной диаграммы выполнения алгоритма.
2. Анализ исходных данных
Решаемые задачи представляются треугольными матрицами следования 40х40 со скалярными весами для ИГ с помощью датчика псевдослучайных чисел, где первые две строки - нулевые. ............
