Выполнение планирования вычислений алгоритма на однородной вычислительной сети при известной структуре

Содержание

Введение

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

2. Анализ исходных данных

3. Описание используемой структуры ВС

4. Описание алгоритма решения задачи

4.1 Основные определения

4.2 Алгоритм построения нитей в сети G

4.3 Алгоритм уплотнения нитей

4.4 Алгоритм распределения вершин графа решаемой задачи на узлах вычислительной сети с одинаковой степенью вершин

5. Описание интерфейса программы

6. Результаты работы программы

Заключение

Введение

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

При этом эти алгоритмы-планировщики могут использовать различные критерии оптимизации. Например, для получения такого распределения, при котором максимально эффективно будут использоваться все процессоры ВС или для получения такого распределения, при котором заданный алгоритм будет решаться за минимальное время при минимизации числа процессоров.

Разработка подобных алгоритмов связана с рядом трудностей. В частности, необходимо проанализировать большое количество условий, учесть множество различных ситуаций, которые возникают при распределении операторов по нитям и нитей по процессорам ВС. Кроме того, необходимы точные исходные данные, такие как времена расчета отдельно взятых операторов, объем передаваемых данных между ними. Необходимо также знать времена передачи данных между процессорами в структуре ВС.