Читайте также:
|
В задании в качестве исходных данных для архитектуры ВС дана информация о циркулянте {49, 1, 3, 4, 5, 7}. Эта циркулянта представлена на рисунке 15.
Рисунок 15 – Схематическое представление циркулянты {49, 1, 3, 4, 5, 7}
Для показанной на рисунке 15 циркулянты строится матрица дистанций (см. таблицу 3 в приложении 5.1), в которой расстояния указываются в минимальном числе промежуточных связей между соответствующими вычислительными модулями. Минимальная сумма расстояний от любого ВМ циркулянты до других ВМ равна 116 ед. То есть эта сумма является постоянной величиной, не зависящей от номера ВМ в циркулянте. Таким образом, отдать предпочтение каким-либо конкретным ВМ в составе циркулянтной ВС не представляется возможным. Тем не менее, очевидно, что ВМ для размещения 9 нитей должны быть выбраны среди всего множества ВМ циркулянтной ВС так, чтобы расстояния между ВМ внутри группы были минимальны.
Таким образом, первую нить можно разместить в любом ВМ (например, в 0-ом), а последующие нити – на минимально возможном расстоянии от первой. Так, расстояние от нитей 2 и 3, размещённых соответственно на 48 и 1 ВМ составит единицу от первой нити, размещённой на нулевой ВМ. Аналогично на единичном расстоянии от первой нити будут находиться 4 и 5 нити, размещённые на ВМ 3 и 46 соответственно. 6 и 7 нити целесообразно разместить на 4 и 45 ВМ соответственно, тогда как 8 и 9 нити разместятся на 5 и 44 ВМ. Таким образом, нити с 2 по 9 находятся на минимальном (единичном) расстоянии от первой нити. Расстояние между ними также минимально возможным в силу конструктивным особенностей ВС типа циркулянта {49, 1, 3, 4, 5, 7}. На рисунке 16 представлено распределение нитей по ВМ ВС структуры циркулянта {49, 1, 3, 4, 5, 7} (см. также таблицу 4 в приложении 5.2).
Рисунок 16 - Распределение нитей по вычислительным модулям ВС структуры циркулянта {49, 1, 3, 4, 5, 7}
Заключение
Выполненная работа показала, что в принципе под любой параллельный алгоритм может быть сформирована своя вычислительная система, наиболее оптимальная с точки зрения распределения временных и иных ресурсов. Использование предельно формализованного механизма проектирования ВС позволяет создать её с минимальными временными затратами, также инструментарий позволяет проводить быстрый анализ спроектированной системы на оптимальность параметров.
Так, в процессе проектирования были решены задачи:
- нахождение ранних сроков окончания выполнения операторов;
- построение нитей решения задачи в соответствии с заданной граф-схемой;
- распределение нитей по ВС, с учетом времени передачи между операторами и между процессорами.
Результаты работы показали корректность алгоритма распределения программных модулей по узлам ВС и оптимальность его выходных данных. Данный алгоритм применим для различных топологий ВС и для неограниченного количества операторов, что позволяет решать многие классы существующих сложных вычислительных задач. На основании проведённых проектировочных исследований можно утверждать, что алгоритм распределения программных модулей по узлам ВС является универсальным.
Список используемой литературы
1. Руденко Ю.М., Волкова Е.А. Вычислительные системы. Москва, НИИ РЛ МГТУ им. Н.Э.Баумана, 2010.
2. Корнеев В.В. Параллельные вычислительные системы, Издательство НГТУ, 1999.
3. Хорошевский В.Г. Архитектура вычислительных систем, МГТУ им. Н.Э. Баумана, 2008.
4. Руденко Ю.М. Новый подход к изображению схем алгоритмов для вычислительных систем. Информатика и системы управления в ХХ1 веке. Сборник трудов №7 молодых учёных, аспирантов, и студентов – М,: МГТУ им. Н.Э. Баумана, 2009. 167–181 с.
5. Руденко Ю.М. Построение плана выполнения параллельных алгоритмов на базе граф-схем. Аэрокосмические технологии. Научные материалы МНТК – 2009.Реутов – Москва 2009. 179-181с.
6. Руденко Ю.М. Учёт зависимостей программных модулей по данным и последовательностям их выполнения при параллельных вычислениях. Известия высших учебных заведений. Поволжский регион. Технические науки. № 3 (11), 2009. 67–75 с.
ПРИЛОЖЕНИЕ 1
Алгоритм построения нитей
1. Просматриваем матрицу SDR по строкам сверху вниз. Если просмотрены все строки, то – конец алгоритма.
2. Если в i-й строке найдено одно число, то вес i-й вершины модифицируется к виду: рi:=pi+qj,i. Если в i-й строке найдено несколько чисел, то веса вершин модифицируются следующим образом: рj:=pj+qi,j,j={ 
}, где,j – множество столбцов, в которых найдены числа,qi,j– множество весов дуг, принадлежащихi-й строке.
3. Используя модифицированные веса, с помощью алгоритма 6.1.1 вычисляем ранние сроки окончания выполнения операторов.
4. Вычисленные ранние сроки окончания выполнения операторов служат основой для построения диаграммы загрузки ВМ. Каждая строка диаграммы может служить нитью для загрузки в процессор.
Дата добавления: 2015-11-14; просмотров: 50 | Нарушение авторских прав
| <== предыдущая страница | | | следующая страница ==> |
| Определение ранних сроков окончания выполнения операторов | | | Алгоритм распределения программных модулей по узлам Вычислительной сети. |