Вычислительная математика и вычислительные системы

Заказать  курсовую Заказать курсовую, контрольную, диплом

Продажа косметики

Женская одежда

 

Занимайтесь онлайн 
        с опытными репетиторами

Занимайтесь онлайн
с опытными репетиторами

Приглашаем к сотрудничеству преподователей

Приглашаем к сотрудничеству преподователей

Готовые шпаргалки, шпоры

Готовые шпаргалки, шпоры

Отчет по практике

Отчет по практике

Сервис для выполнения любых видов студенческих работ

Сервис для выполнения любых видов студенческих работ

Студенческий файлообменник Студенческий файлообменник

Закажите реферат

Закажите реферат

Биржа студенческих   работ. Контрольные, курсовые, рефераты.

Средства безопасности
Windows Server
Многопроцессорные
вычислительные системы
Вычислительная математика
Учебно-практическая задача
Итегралы вычисление
площади и обьема
Теория электрических цепей
Машиностроительное черчение
Оформление чертежей
Пpавила изобpажения пpедметов
Способы преобразования чертежа
 Нанесение размеров
Аксонометрические проекции
Резьбы, резьбовые изделия
Разъемные соединения
зубчатые передачи
Шероховатость поверхности
Эскизы
Сборочный чертеж
Деталирование чертежей
Вспомогательная сетка
Обозначение материалов
Масштаб
Уклон и конусность
Правила нанесения размеров
Шрифты чертежные
Геометрические построения
Метод проекций
Многогранники
Решение метрических задач
Решение задач по физике примеры
Оформление сборочного
чертежа спецификация
Начертательная геометрия
Комплексный чертеж
Законы проекционной связи
Кривая линия общего вида
Поверхность вращения
Построить сечение пирамиды
Метод концентрических сфер
Частный случай теоремы Г.Монжа
Метод центрального проецирования
Замена плоскостей проекций
Метод совмещения плоскостей
Персональный компьютер
Система ввода/вывода
и системные файлы
Первоначальная загрузка
Дисковые структуры
Общий объем дискового пространства
Сохранение данных
Адаптер клавиатуры

Технические характеристики

Вычислительные системы

 

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

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

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

Время передачи данных между процессорами определяет коммуникационную составляющую (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) для объединения процессорных узлов кластера в единую вычислительную сеть. Завершая анализ проблемы построения теоретических оценок трудоемкости коммуникационных операций, следует отметить, что для практического применения перечисленных моделей необходимо выполнить оценку значений параметров используемых соотношений Рассмотрим для первоначального ознакомления со способами построения и анализа параллельных методов вычислений сравнительно простую задачу нахождения частных сумм последовательности числовых значений Последовательный алгоритм суммирования

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

Пути достижения параллелизма

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

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

Одним из наиболее распространенных способов классификации ЭВМ является систематика Флинна (Flynn), в рамках которой основное внимание при анализе архитектуры вычислительных систем уделяется способам взаимодействия последовательностей (потоков) выполняемых команд и обрабатываемых данных. Мультикомпьютеры (системы с распределенной памятью) уже не обеспечивают общий доступ ко всей имеющейся в системах памяти (no-remote memory access or NORMA). При организации параллельных вычислений в МВС для организации взаимодействия, синхронизации и взаимоисключения параллельно выполняемых процессов используется передача данных между процессорами вычислительной среды. Временные задержки при передаче данных по линиям связи могут оказаться существенными (по сравнению с быстродействием процессоров) и, как результат, коммуникационная трудоемкость алгоритма оказывает существенное влияние на выбор параллельных способов решения задач. Высокопроизводительный вычислительный кластер

Моделирование и анализ параллельных вычислений При разработке параллельных алгоритмов решения задач вычислительной математики принципиальным моментом является анализ эффективности использования параллелизма, состоящий обычно в оценке получаемого ускорения процесса вычисления (сокращения времени решения задачи). Операции алгоритма, между которыми нет пути в рамках выбранной схемы вычислений, могут быть выполнены параллельно Модель вычислительной схемы алгоритма G совместно с расписанием Hp может рассматриваться как модель параллельного алгоритма Ap(G, Hp), исполняемого с использованием p процессоров Показатели эффективности параллельного алгоритма

Параллельные численные методы для решения типовых задач вычислительной математики

Каскадная схема суммирования

Параллелизм алгоритма суммирования становится возможным только при ином способе построения процесса вычислений, основанном на использовании ассоциативности операции сложения. Получение асимптотически ненулевой эффективности может быть обеспечено, например, при использовании модифицированной каскадной схемы. В новом варианте каскадной схемы все проводимые вычисления подразделяется на два последовательно выполняемых этапа суммирования Вернемся к исходной задаче вычисления всех частных сумм последовательности значений и проведем анализ возможных способов последовательной и параллельной организации вычислений. Вычисление всех частных сумм на скалярном компьютере может быть получено при помощи того же самого обычного последовательного алгоритма суммирования при том же количестве операций Умножение матрицы на вектор Выбор параллельного способа вычислений. Выполним анализ информационных зависимостей в алгоритме умножения матрицы на вектор для выбора возможных способов распараллеливания. Оценка показателей эффективности алгоритма. Выбор параллельного способа вычислений. Выбор топологии вычислительной системы. Другой возможный способ организации параллельных вычислений может состоять в построении конвейерной схемы для операции умножения строки матрицы на вектор (скалярного произведения векторов) путем расположения всех имеющихся процессоров в виде линейной последовательности (линейки). Результат умножения следующих строк будет происходить после завершения каждой очередной итерации конвейера (напомним, итерация каждого процессора включает выполнение операций умножения и сложения) Следует отметить, что размер матрицы может оказаться не кратным количеству процессоров и тогда строки матрицы не могут быть разделены поровну между процессорами. В соответствии с характером выполняемых межпроцессорных взаимодействий в предложенной вычислительной схеме в качестве возможной топологии МВС может служить организация процессоров в виде звезды Макрооперационный анализ алгоритмов решения задач При построении параллельных способов выполнения матричного умножения наряду с рассмотрением матриц в виде наборов строк и столбцов широко используется блочное представление матриц. Для организации параллельных вычислений предположим, что процессоры образуют логическую прямоугольную решетку размером Состояние блоков на каждом процессоре в ходе выполнения итераций этапа вычислений Сортировка является одной из типовых проблем обработки данных, и обычно понимается как задача размещения элементов неупорядоченного набора значений При детальном рассмотрении способов упорядочивания данных, применяемых в алгоритмах сортировки, можно обратить внимание, что многие методы основаны на применении одной и той же базовой операции "сравнить и переставить" (compare-exchange), состоящей в сравнении той или иной пары значений из сортируемого набора данных и перестановки этих значений, если их порядок не соответствует условиям сортировки Алгоритм пузырьковой сортировки, общая схема которого представлена в начале данного раздела, в прямом виде достаточно сложен для распараллеливания – сравнение пар значений упорядочиваемого набора данных происходит строго последовательно. Следует отметить, что в приведенном примере последняя итерация сортировки является избыточной – упорядоченный набор данных был получен уже на третьей итерации алгоритма. В общем случае выполнение параллельного метода может быть прекращено, если в течение каких-либо двух последовательных итераций сортировки состояние упорядочиваемого набора данных не было изменено. Детальное описание алгоритма Шелла может быть получено, например, в [7]; здесь же отметим только, что общая идея метода состоит в сравнении на начальных стадиях сортировки пар значений, располагаемых достаточно далеко друг от друга в упорядочиваемом наборе данных. При кратком изложении алгоритм быстрой сортировкиосновывается на последовательном разделении сортируемого набора данных на блоки меньшего размера таким образом, что между значениями разных блоков обеспечивается отношение упорядоченности (для любой пары блоков существует блок, все значения которого будут меньше значений другого блока). Эффективность параллельного метода быстрой сортировки, как и в последовательном варианте, во многом зависит от успешности выбора значений ведущих элементов. Среди множества этих процедур может быть выделен некоторый определенный набор типовых алгоритмов обработки графов Охватывающим деревом (или остовом) неориентированного графа  называется подграф  графа , который является деревом и содержит все вершины из . Оценим возможности для параллельного выполнения рассмотренного алгоритма нахождения минимально охватывающего дерева. Итерации метода должны выполняться последовательно и, тем самым, не могут быть распараллелены. Задача поиска кратчайших путей на графе состоит в нахождении путей минимального веса от некоторой заданной вершины   до всех имеющихся вершин графа.

Курс лекций по персональному компьютеру http://istdiz.ru/ Найдём производную функции http://rugrafi.ru/ Информатика, черчение, математика