Развитие языковых средств SPMD-технологии для параллельного и сетевого решения задач планирования и управления

• Автор: Смирнова, Елена Викторовна
• Шифр специальности: 05.13.15, 05.13.13
• Научная степень: Кандидатская
• Год защиты: 2002
• Место защиты: Москва
• Количество страниц: 168 с. : ил

ОГЛАВЛЕНИЕ
ВВЕДЕНИЕ
1. Анализ сложности задач, решаемых в системе ж/д транспорта, и обоснование способов параллельной обработки и требований к производительности вычислительных средств 1
1.1 Характеристика сложности задач, решаемых на ж/д транспорте и выделение класса задач экспоненциальной сложности
1.2 Анализ традиционных методов решения класса сложных задач, использующих ограничения

1.2.1 Графический метод решения задачи линейного программирования

1.2.2 Симплекс-метод 1

1.3 Исследование возможности распараллеливания задач линейного и целочисленного программирования и обоснование схемы их решения

1.3.1 Алгоритм прямого перебора решения задачи линейного программирования

1.3.1.1 Общий алгоритм перебора

1.3.1.2 План параллельных вычислений

1.2.1.3 Сложность алгоритма прямого перебора
1.3.2 Параллельный аналог «симплекс-метода»
1.3.2.1 Общий алгоритм симплекс-метода
1.3.2.2 Сложность алгоритма
1.3.2.3 План параллельных вычислений
1.3.3 Алгоритмы целочисленного программирования
1.3.3.1 Метод ветвей и границ
1.3.3.2 Параллельный алгоритм решения задач целочисленного программирования методом ветвей и границ
1.3.3.3 План параллельных вычислений

1.4 SPMD-технология и возможность ее применения для решения сложных задач
Выводы
2. Разработка системы команд и операций в среде ОС Windows для ВС типа SPMD
2.1 Разработка требований к архитектуре ВС, предназначенной для решения сложных задач планирования и управления
2.2 Разработка ассемблера (системы команд) ВС на основе SPMD-технологии - приставки к ПК
2.3 Основы методики монопрограммирования. Экспериментальное программирование задач
2.3.1 Векторная операция свертки
2.3.2 Распараллеливание по одномерному опорному массиву
2.4 Анализ полноты системы команд на основе экспериментального программирования
Выводы
3. Исследование возможности применения языков высокого уровня при реализации SPMD-технологии
3.1 Средства поддержки параллельности в ЯВУ для многопроцессорных

3.1.1 Способы отражения параллелизма в последовательных языках программирования
3.1.2 Средства поддержки параллельности Фортрана 90 и HPF
3.1.3 Средства поддержки параллельности НРС++
3.1.4 Команды и операции процессора для SPMD - технологии следуют тенденциям языкового развития
3.2 Исследование возможности реализации SPMD - технологии программирования на языке Java
3.2.1 Обоснование применения языка Java для организации параллельных вычислений

3.2.2 Модель параллельного программирования Java
3.2.3 Реализация языковой поддержки SPMD - технологии с помощью средств Java
3.2.4 Методика разработки параллельных программ на основе SPMD-технологии на языке Java
Выводы
4.Эффективность ВС на основе SPMD-технологии
4.1 Исследование функционирования ВС
4.2 Разработка тест-программы для оценки производительности ВС
Выводы
Заключение
Литература

В результате решения первой же подсистемы трёх уравнений (п = 3) системы (15) получаем координаты вершины Е многогранника X

|<72 = 0 -> £(13,8,4), г(Е) = 592 (16)
[ Постараемся «сместиться» в ту вершину, смежную вершине Е, т.е. соединённую с ней ребром (в одну из вершин А, Д X, Е), в которой целевая функция А имеет максимальное значение, превышающее Е(Е).
Рёбра, исходящие из вершины, определяются подсистемами п-1 плоскостей, пересекающихся в этой вершине, т.е. образующими её.

В данном случае подсистема ( определяет несуществующее реб-
[д2 =
ро. Пока мы знаем это только по рисунку. Подсистема |?| ^определяет ребро
ЕА, подсистема ^2 ° определяет ребро ЕЕ. А вот рёбра ЕЬ и ЕЕ мы пока не

знаем, т.к. не знаем (формально, а не по рисунку!) все плоскости (плоскость д5), пересекающиеся в Е. Это значит, что из каждой вершины в общем случае исходят не менее п рёбер, а сколько в действительности, - предстоит уточнить. (Представьте себсХ- огранённый бриллиант.)
Значит, Тогда выясним всё множество граней, образующих вершину Е, подстановкой её координат во все другие уравнения (15), и испытывая на получение тождества [38]. Находим д5(13,8,4) = 0. Добавляем д5 в (16), полагаем полностью известным число р = 4 граней, образующих вершину Е. Т.е. вместо (16) получаем