Распределение задач с помощью нитей по процессорам вычислительной системы заданной структуры - Курсовая работа

Многопроцессорные системы с каждым годом все шире используются крупными компаниями и научными учреждениями для обработки и хранения больших массивов данных. Так, вычислительные кластеры применяются преимущественно для решения сложных инженерных и научных задач: расчет параметров конструкции ракеты-носителя для обеспечения заданных параметров надежности; прогнозирование развития биологических и химических реакций, разработка лекарства против рака и пр. В последние годы многопроцессорные системы стали входить и в жизнь массового пользователя: современные программы (например, трехмерные игры) предъявляют высокие требования к скорости обработки данных (видеоданных), для чего целесообразно использовать несколько процессоров или процессорных ядер, работающих параллельно. Итак, современный персональный компьютер представляет собой простейшую разновидность многопроцессорной системы. 2. использовать специальные алгоритмы (планировщики), которые позволят распределить операторы параллельных алгоритмов по процессорам ВС наиболее оптимальным образом.Имеется параллельная система, для которой необходимо подготовить план и схему решения поставленной задачи, т.е. ответить на следующие вопросы о том, в какой последовательности будут выполняться программные модули, на каких процессорах, как происходит обмен данными между процессорами, каким образом минимизировать время выполнения поставленной задачи. Имеется класс задач, для решения которых необходимо спроектировать параллельную вычислительную систему, минимизирующую время решения поставленной задачи, при минимальных затратах на ее проектирование. При создании параллельных вычислительных систем учитываются различные аспекты их эксплуатации, такие как множественность решаемых задач, частоту их решения, требования к времени решения и т.д., что приводит к различным структурным схемам построения таких систем. Система, представленная множеством описаний W={K,A}, где K - описание конструкций ВС, А - описание алгоритма работы множества вычислительных модулей, называется вычислительной. В конструкцию К должны быть заложены следующие принципы: а) параллелизм при обработке информации, т.е. организация вычислений одновременно на множестве вычислительных модулей М с организацией в случае необходимости обмена данными через сеть S;Вес вершины (P) - время расчета вершины на i-ом процессоре. Степень вершины (Vi) - количество узлов, находящиеся от i-ой вершины на минимальном расстоянии. Время старта вершины (ST) - время старта расчета вершины в существующем разбиении вершин между процессорами. Время финиша вершины (FT) - время финиша расчета вершины в существующем разбиении вершин между процессорами.При построении плана распределения операторов по ВМ вычислительной системы с распределенной памятью для информационной граф-схемы возникают определенные трудности, связанные с передачей информации через транзитные ВМ. Сущность метода заключается в том, что на первом этапе создаются нити без учета обмена информацией между ВМ. Вначале получаем модифицированные веса вершин в виде pm,j=pj qj,i ,где pj - вес j-й вершины, qj,i - вес дуги, исходящей из j-й вершины. Дополнительно к преимуществу структуры общей шины данная структура обладает тем достоинством, что обмен информацией между процессорами не требует дополнительных операций, а осуществляется благодаря доступу процессора к памяти.Основным инструментом анализа граф-схем алгоритмов служит матрица следования, а также различные ее модификации. Использование матрицы следования вместо матриц смежности объясняется удобством размещения и анализа граф-схем. …, n}.Матрица S - квадратная - количество строк и столбцов совпадает с количеством вершин граф-схемы. В матрице S i - ой вершине графа G ставятся в соответствие i - ые столбец и строка этой матрицы.Имея эти величины, можно построить планы выполнения операторов с учетом распределения операторов по ВМ. На основе граф-схемы алгоритма можно определить: 1) Частичную упорядоченность выполнения алгоритма. .m, где - время начала выполнения j-ого оператора, pj - время выполнения j-ого оператора, полученное при минимальном времени решения задачи Т=Тк. По алгоритму, приведенному в Приложении 2, определим ранние сроки окончания выполнения операторов и построим диаграмму (рисунок 4). С помощью матрицы следования с указанными весами дуг и вершин модифицированные веса вершин можно вычислить следующим образом: если в i-й строке найдено одно число, то вес i-й вершины модифицируется к виду: рі:=pi qji;если в i-й строке найдено несколько чисел, то веса вершин модифицируются к виду pj:=pj qi,j, j={ }, где j - номера столбцов, в которых найдены числа,qi,j-множество весов дуг, принадлежащихі-й строке.В задании в качестве исходных данных для архитектуры ВС дана информация о циркулянте {49, 1, 3, 4, 5, 7}. Эта циркулянта представлена на рисунке 15. Для показанной на рисунке 15 циркулянты строится матрица дистанций (см. таблицу 3 в приложении 5.1), в которой расстояния указываются в минимальном числе промежуточных связей между

Оглавление

Введение

1.Теоретическая часть

1.1Понятие о современных вычислительных системах

1.2 Структура ВС типа «Циркулянт»

2. Основные определения, необходимые для разработки алгоритма распределения программных модулей по вычислительным модулям вычислительной сети

3. Распределение операторов по ВМ вычислительной системы с распределенной памятью для информационно-логической граф-схемы

3.1 Построение матрицы следования ИЛГ

3.2 Определение ранних сроков окончания выполнения операторов

3.3 Распределение нитей на структуре типа циркулянта

Заключение

Список используемой литературы

Приложение

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

В последние годы многопроцессорные системы стали входить и в жизнь массового пользователя: современные программы (например, трехмерные игры) предъявляют высокие требования к скорости обработки данных (видеоданных), для чего целесообразно использовать несколько процессоров или процессорных ядер, работающих параллельно. Итак, современный персональный компьютер представляет собой простейшую разновидность многопроцессорной системы.

Для эффективного использования многопроцессорных систем необходимо: 1. преобразовывать последовательные алгоритмы обработки данных в параллельные;

2. использовать специальные алгоритмы (планировщики), которые позволят распределить операторы параллельных алгоритмов по процессорам ВС наиболее оптимальным образом.

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

При этом алгоритмы-планировщики могут использовать различные критерии оптимизации: - минимизация времени выполнения задачи;

- минимизация числа процессоров для заданного времени выполнения задачи;

- обеспечение максимальной эффективности использования процессоров ВС;

- прочие.

Сложность разработки планировщика связана с некоторыми сложностями: - анализ большого количества условий;

- рассмотрение множества различных ситуаций, которые возникают при распределении операторов по нитям и нитей по процессорам ВС;

- работа с большим количеством исходных данных.

Разработка и совершенствование алгоритмов-планировщиков увеличит быстродействие обработки данных на многопроцессорных системах.

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