Оценка коммуникационной трудоемкости параллельных алгоритмов

Алгоритмы маршрутизации
Мультикомпьютеры
Выбор топологии вычислительной системы
Сбои в персональных компьютерах
Запись на диски и в файлы
Процессы и ресурсы
Балансировка вычислительной
нагрузки процессоров
Математическая статистика
Предел функции Интегрирование
Решение интегралов
Вычисление двойных и тройных интегралов
Курсовая на вычисление интеграла
Формула Тейлора для ФНП
Производная сложной ФНП
Интегрирование функций нескольких переменных
Геометрические свойства интеграла ФНП
Типовые задачи
Вычислить интеграл
Вычислить момент инерции
Вычислить повторный интеграл
Решения задачи Коши
Метод Эйлера
Оформление сборочного чертежа
Изображения
Способы преобразования чертежа
 Нанесение размеров
Аксонометрические проекции
Резьбы, резьбовые изделия
Разъемные соединения
Неразъемные соединения
Шероховатость поверхности
Сборочный чертеж
Деталирование чертежей
Решение задач по физике примеры
Электротехника
Оптика
Билеты к экзамену по физике
Теория электромагнитного поля
Элементы электрических цепей
Промышленная электроника
Цифровая электроника
Теоретические основы электротехники
Сопротивление материалов
Метод сечений
Перемещения и деформации
Общие принципы расчета конструкции
Моменты инерции сечения
Кручение бруса
Определение опорных реакций
Момент сопротивления
Метод начальных параметров
Косой изгиб
Внецентренное растяжение и сжатие
Теории прочности
Метод сил
Расчет на усталостную прочность
Задача Эйлера
Формула Ясинского
Определение прогиба и напряжений
Запас усталостной прочности
Основы теории упругости
Основы теории пластичности
Рождение абстрактного искусства
Художники эпохи Просвещения
Теоретическая механика

 

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

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

Время передачи данных между процессорами определяет коммуникационную составляющую (communication latency) длительности выполнения параллельного алгоритма в многопроцессорной вычислительной системе. При всем разнообразии выполняемых операций передачи данных при параллельных способах решения сложных научно-технических задач определенные процедуры взаимодействия процессоров сети могут быть отнесены к числу основных коммуникационных действий, которые или наиболее широко распространены в практике параллельных вычислений, или к которым могут быть сведены многие другие процессы приема-передачи сообщений. Операция передачи данных (одного и того же сообщения) от одного процессора всем остальным процессорам сети (one-to-all broadcast or single-node broadcast) является одним из наиболее часто выполняемых коммуникационных действий; двойственная операция передачи - прием на одном процессоре сообщений от всех остальных процессоров сети (single-node accumulation). Передача пакетов. Для топологии типа кольца алгоритм рассылки может быть получен путем логического представления кольцевой структуры сети в виде гиперкуба. Возможным широко распространенным примером операции множественной рассылки является задача редукции (reduction), определяемая в общем виде, как процедура выполнения той или иной обработки получаемых на каждом процессоре данных (в качестве примера такой задачи может быть рассмотрена проблема вычисления суммы значений, находящихся на разных процессорах, и рассылки полученной суммы по всем процессорам сети). Проведем более подробный анализ трудоемкости обобщенной рассылки для случая топологии типа гиперкуб. Способ получения алгоритма рассылки данных для топологии типа решетки-тора является тем же самым, что и в случае рассмотрения других коммуникационных операций. Частный случай обобщенной множественной рассылки есть процедура перестановки (permutation), представляющая собой операцию перераспределения информации между процессорами сети, в которой каждый процессор передает сообщение некоторому определенному другому процессору сети. Как результат, важным моментом является при организации параллельных вычислений умение логического представления разнообразных топологий на основе конкретных (физических) межпроцессорных структур. Установление соответствия между кольцевой топологией и гиперкубом может быть выполнено при помощи двоичного рефлексивного кода Грея G(i, N) (binary reflected Gray code), Для кластерных вычислительных систем (см. п. 1.3) одним из широко применяемых способов построения коммуникационной среды является использование концентраторов (hub) или переключателей (switch) для объединения процессорных узлов кластера в единую вычислительную сеть. Завершая анализ проблемы построения теоретических оценок трудоемкости коммуникационных операций, следует отметить, что для практического применения перечисленных моделей необходимо выполнить оценку значений параметров используемых соотношений Рассмотрим для первоначального ознакомления со способами построения и анализа параллельных методов вычислений сравнительно простую задачу нахождения частных сумм последовательности числовых значений Последовательный алгоритм суммирования

Математика , физика курсовая, информационные системы. Машиностроительное черчение