Разработка параллельных алгоритмов в методах оптимизации

ВВЕДЕНИЕ 3
ПОСТАНОВКА И РЕАЛИЗАЦИЯ СТАНДАРТНОГО И ПАРАЛЛЕЛЬНОГО АЛГОРИТМОВ РЕШЕНИЯ ТРАНСПОРТНОЙ ЗАДАЧИ 6
1.1. Формулировка транспортной задачи 6
1.2. Математическая модель транспортной задачи 7
1.3. Метод решения транспортной задачи 8
1.4 Алгоритмы решения транспортной задачи 13
1.5 Пример параллельного метода решения транспортной задачи 42
2. ВЕНГЕРСКИЙ АЛГОРИТМ.РЕШЕНИЕ ЗАДАЧ О НАЗНАЧЕНИЯХ 64
2.1. Венгерский алгоритм. Решение задач о назначениях 64
2.2 Параллельная реализация алгоритма 66
3. РЕШЕНИЕ ГРАДИЕНТНЫХ ЗАДАЧ 67
3.1 Метод градиентного спуска 67
3.2 Параллельный метод градиентного спуска 69
3.3 Решение систем линейных уравнений методом градиентного
спуска 71
3.4 Параллельный алгоритм нахождения решений систем уравнений методом
наискорейшего спуска 76
РЕЗУЛЬТАТЫ ИССЛЕДОВАНИЙ 78
ЗАКЛЮЧЕНИЕ 85
СПИСОК ЛИТЕРАТУРЫ 86
6. ПРИЛОЖЕНИЕ

Купить

Большое место в программировании занимают параллельные вычисления. В основном параллельное программное обеспечение разрабатывается только для конкретных архитектур вычислительных систем. При таком разнообразии параллельных вычислений, достаточно трудно выделить одну вычислительную систему для решения прикладных задач. Одним из главенствующих факторов в параллельных вычислениях является стоимость параллельных вычислительных систем. С одной стороны дороговизна параллельных вычислений тормозит развитие прикладных основ программирования, но с другой стороны эта область всё больше притягивает к себе внимание и дает толчок теоретическим исследованиям в этой области. Так же стоит заметить фактор - попытки уменьшить затраты на вычисления путём экспериментов и исследований. Но в любом случае следует ориентироваться на существующие стандарты в параллельных вычислениях.
Выделяют два типа параллелизма: крупноблочный и мелкозернистый.
Основными отличиями между данными типами параллелизма является отношение между числом команд, которые выполняются последовательно к числу обменов между процессорами. Алгоритмы, которые основаны на крупнозернистом параллелизме, обычно выполняют довольно небольшое число сложных вычислений, которые выполняются параллельно. При это стоит заметить, что обмен промежуточными результатами между процессорами также происходит довольно редко. В отличие от крупноблочного параллелизма, мелкозернистый параллелизм подразумевает большое количество параллельно выполняемых простых, довольно часто одинаковых, вычислений, обмен промежуточными результатами при этом происходит на каждом шаге. Мелкозернистый параллелизм нужен в тех случаях, когда работу программы нужно значительно убыстрить, при этом выделив повторяющиеся операции для передачи их параллельным процессам. Параллельные вычислительные системы принято называть многопроцессорными.
Приведём классификацию многопроцессорных систем: Векторно-конвейерные компьютеры. Они характеризуются наличием функциональных конвейерных устройств и набором векторных команд.
Массивно-параллельные компьютеры с распределенной памятью. Они представляют собой класс компьютеров, в которых соединение микропроцессоров осуществляется при помощи сетевого оборудования.
Параллельные компьютеры с общей памятью. На них вся оперативная память разделяется несколькими одинаковыми процессорами, обращающимися к общей дисковой памяти. При этом проблем с обменом данными между процессорами и синхронизацией их работы практически не возникает.
Кластерные компьютеры. Это класс, который представлен комбинацией предыдущих трёх классов.
Параллельные машины и параллельные вычисления создаются для ускорения решения задач большой размерности. При использовании свойств и методов конкретной задачи, существенно облегчается процесс её распараллеливания. Однако, не всегда распараллеленная задача будет иметь преимущество по скорости , относительно её обычного, непараллельного аналога. Как показывает практика, наиболее лучшим вариантом по эффективному решению задач служит комбинированный метод вычислений, который будет зависеть от входных данных конкретной задачи.
Наиболее распространённым методом распараллеливания является выделение наиболее часто повторяющейся операции. При этом, следует учитывать, с какими данными она будет производить операции, чтобы результат от этого не пострадал.
В данной работе описаны алгоритмы решения транспортной задачи( параллельный метод потенциалов и матричный способ), венгерский алгоритм (решение задачи о назначениях, параллельная и стандартная реализации), метод решения систем линейных алгебраических уравнений (4 стандартный и параллельный метод) и метод нахождения минимума при помощи градиентного спуска(стандартный и параллельный метод).
Предполагается, что описанные в данной работе алгоритмы будут выполнятся на модели массивно параллельных компьютеров.
При оценке трудоемкости параллельных алгоритмов будем использовать следующие критерии. Под временем исполнения алгоритма будет приниматься разница между таймером один, который засекается до начала исполнения программы, и таймером, который фиксирует время после завершения работы программы под вычислительной сложностью будет принимать число элементарных операций, которые будет исполнять алгоритм в течение его работы. Под ускорением будет принимать некоторый коэффициент, между непараллельным аналогом алгоритма и его параллельной реализацией.
Также стоит отметить, что кластеризация в наше время является проблемой актуальной, так как вычисления становятся все более громоздкими. Появляются новые зависимости в таких отраслях как химия, нефтегазовое дело, метеорология, где необходимо вычислять функции от нескольких десятков переменных и вычислять довольно быстро.

Купить