Содержание к диссертации
Введение
ГЛАВА 1. Средства и методы разработки систем поддержки принятия оперативных решений 11
1.1. Основные области применения систем поддержки принятия оперативных решений 13
1.2. Особенности и направления исследований в области создания систем поддержки принятия оперативных решений 18
1.3. Исследование методов обеспечения работы систем поддержки принятия оперативных решений в режиме реального времени 21
1.3.1. Параллелизм на уровне задач, подзадач и программных модулей 23
1.3.2. Параллельное выполнение циклических конструкций 26
1.3.3. Механизмы распараллеливания на уровне правил и внутри правил 30
1.3.4. Использование синхронизирующих примитивов . 31
1.3.5. Спецификация взаимодействующих процессов 33
1.3.6. Дисциплина обработки правил 35
1.3.7. Хранение информации 37
1.4. Интеллектуализация человеко-машинного взаимодействия 38
1.5. Подготовка информации для системы поддержки принятия оперативных решений в подсистеме настройки 39
ВЫВОДЫ 41
ГЛАВА 2. Информационное обеспечение системы поддержки принятия оперативных решений 43
2.1. Методы обработки информации в системе поддержки принятия оперативных решений 46
2.2. Структура информационного обмена в системе поддержки принятия оперативных решений 49
2.3. Информационная модель объекта управления 51
2.4. Информационная модель внешней среды 60
2.5. Задачи системы поддержки принятия оперативных решений в системе обеспечения безопасного функционирования объектов хранения и уничтожения химического оружия 64
2.6. Иллюстрация информационной модели технологического процесса гидролиза люизита 73
ВЫВОДЫ 80
ГЛАВА 3. Принципы построения программных средств системы поддержки принятия оперативных решений и компьютерного тренажёрного комплекса 82
3.1. Этапы проектирования системы поддержки принятия оперативных решений 82
3.2. Структура функциональной части системы поддержки принятия оперативных решений 84
3.2.1. Блок обработки и анализа данных 84
3.2.2. Блок генерации планов действий оператора 87
3.2.3. Блок оценки и выбора оптимального плана 93
3.2.4. Блок моделирования 96
3.2.5. Блок взаимодействия с источниками знаний 98
3.3. Человеко-машинное взаимодействие в системе поддержки принятия оперативных решений 99
3.3.1. Модуль презентации 100
3.3.2. Монитор ошибок 102
3.3.3. Модуль адаптивной поддержки 104
3.4. Компьютерный тренажёрный комплекс на основе системы поддержки принятия оперативных решений 106
3.4.1. Структура компьютерного тренажерного комплекса 106
3.4.2. Функциональная структура программного обеспечения рабочих мест ПО
3.4.3. Информационная модель процесса обучения 114
ВЫВОДЫ 119
ГЛАВА 4. Средства и методы автоматического распараллеливания и векторизации вычислений для обеспечения режима реального времени 121
4.1. Автоматическое распараллеливание языковых конструкций 123
4.1.1. Универсальный метод распараллеливания циклических конструкций 123
4.1.1.1. Определения и обозначения 124
4.1.1.2. Обоснование метода распараллеливания 126
4.1.1.3. Декомпозиция циклов 131
4.1.2. Метод линейного преобразования 138
4.1.3. Распараллеливание нетесногнездовых и не вложенных циклов 144
4.1.4. Распараллеливание циклов с переменными границами 149
4.2. Векторизация повторяющихся вычислений 152
4.2.1. Векторизация вычислений в случае матрицы линейного преобразования в каноническом виде 155
4.2.2. Векторизация в случае матрицы линейного преобразования не в каноническом виде 166
4.2.3. Векторизация в случае произвольных шагов изменения параметров цикла 172
ВЫВОДЫ 181
ГЛАВА 5. Реализация результатов исследований 183
5.1. Система производственного экологического мониторинга объекта хранения и уничтожения химического оружия 184
5.2. Компьютерный тренажёрный комплекс для обучения операторов, управляющих технологическим процессом уничтожения химического оружия 190
5.3. Система-ассистент экипажа перспективного летательного аппарата 194
5.4. Блок автоматического распараллеливания и векторизации 201
Выводы 201
Заключение 203
Литература
- Исследование методов обеспечения работы систем поддержки принятия оперативных решений в режиме реального времени
- Структура информационного обмена в системе поддержки принятия оперативных решений
- Структура функциональной части системы поддержки принятия оперативных решений
- Универсальный метод распараллеливания циклических конструкций
Введение к работе
Актуальность темы диссертации. Сложность решаемых задач, большой объем поступающей информации, короткое время на принятие решений и ответственность за принятые решения приводят в отдельных случаях к несоответствию возможностей человека-оператора требованиям эффективно осуществлять процесс оперативного управления человеко-машинными комплексами. В связи с этим в настоящее время все шире используются компьютерные системы поддержки принятия оперативных решений (СППОР), предназначенные для оказания помощи операторам в преодолении возникающих проблем управления сложными техническими объектами.
Перед СППОР ставятся очень широкие задачи, которые не всегда могут быть формализованы и решены традиционными математическими методами:
• анализ больших объемов неполной и противоречивой информации;
• генерация и оценка вариантов решений по управлению объектом в режиме реального времени;
• выбор наилучших путей, ведущих к достижению необходимого результата;
• предупреждение оператора в случае неудовлетворительного состояния объекта управления (технологического процесса) и др.
Поэтому возникла необходимость в исследовании вопросов, связанных с интеграцией в СППОР, работающей в режиме реального времени, традиционных математических методов с эвристическими моделями и методами.
Можно выделить три основных подхода к обеспечению режима реального времени в СППОР. Один из них заключается в использовании (разработке) специализированных механизмов обработки знаний, другой - в увеличении скорости вычислений за счет максимального их распараллеливания. Третий подход связан с разработкой методов создания человеко-машинного взаимодействия, в значительной степени сокращающих потери времени при общении человека-оператора с системой.
Важным аспектом обеспечения быстрого и точного взаимодействия оператора с СППОР является его уровень понимания принципов, заложенных в систему, возможностей и методов работы СППОР, знаний и умения использовать предлагаемые интерфейсы. Поэтому для обеспечения полноценного использования СППОР в режиме реального времени структура программного обеспечения СППОР должна быть разработана с учётом необходимости обучения операторов на компьютерном тренажёрном комплексе (КТК). В этом случае из разработанных модулей программного обеспечения можно сконфигурировать как СППОР для работы с реальным объектом, так и КТК для компьютерного тренинга операторов.
Важность задач, стоящих перед СППОР, отсутствие комплексной методологии и эффективных программных инструментов их решения, определяют актуальность теоретических и прикладных исследований диссертационной работы, решающей крупную научную проблему комплексной поддержки принятия оперативных решений в реальном времени при управлении сложным техническим объектом.
Целью диссертационной работы является разработка и исследование методов построения и архитектуры СППОР для эффективного управления в реальном времени сложными техническими объектами. Полученные в работе результаты направлены на создание информационного, математического, программного и методического обеспечения СППОР.
Методы исследования. Проведённые теоретические и прикладные исследования базируются на использовании методов обработки знаний, целочисленного программирования, методов поиска и принятия решений, теории выбора и многокритериальной оптимизации.
Научная новизна. В результате проведённых исследований получены следующие научные результаты:
- разработана и исследована методика создания программного обеспечения СППОР, обеспечивающая эффективную поддержку принятия оперативных решений в режиме реального времени;
- разработана и исследована архитектура программного обеспечения СППОР и показана её специфика;
- разработана методика построения информационной модели объекта управления на основе предложенных типов данных;
- предложена методика организации человеко-машинного взаимодействия в СППОР и разработана обобщённая структура программного обеспечения интерфейса оператора, которая может являться основой разработки интерфейсных модулей для конкретных СППОР;
- разработана и исследована методика построения компьютерного тренажёрного комплекса на основе программного обеспечения СППОР, содержащего стандартные и уникальные (создаваемые в каждом проекте) компоненты;
- разработаны и обоснованы методы автоматического распараллеливания и векторизации вычислений для обеспечения режима реального времени в СППОР при использовании многопроцессорных вычислительных систем, позволяющие осуществить распараллеливание исходных программных конструкций, которые не распараллеливаются другими известными методами; доказана эквивалентность преобразований циклических программных конструкций к последовательно-параллельному виду для различных методов распараллеливания и векторизации.
Достоверность научных положений, выводов и практических рекомендаций, полученных в диссертационной работе, подтверждена обоснованием и анализом разработанных методов и структур программного обеспечения, доказательствами правильности преобразования программных конструкций, а также результатами практического использования предложенных в диссертационной работе методов, алгоритмов и программных средств.
Практическая ценность и реализация результатов. Разработанные в диссертации методы, алгоритмы и программные средства систем поддержки принятия оперативных решений позволят повысить качество принимаемых решений при управлении сложным техническим объектом, облегчить взаимодействие операторов с автоматизированными системами управления, повысить уровень безопасности эксплуатации объекта управления.
Практическая ценность полученных результатов подтверждается их использованием в следующих системах:
- система производственного экологического мониторинга объекта хранения и уничтожения химического оружия;
- компьютерный тренажёрный комплекс для обучения операторов автоматизированной системы управления технологическим процессом (АСУ ТП) объекта хранения и уничтожения химического оружия;
- прототип системы поддержки принятия решений экипажем перспективного летательного аппарата (ЛА) для решения задач группового пилотирования;
- блок автоматического распараллеливания и векторизации для многопроцессорных вычислительных комплексов.
Диссертационная работа выполнена в рамках плановой тематики Института проблем управления им. В.А. Трапезникова РАН.
Апробация работы. Основные положения диссертационной работы докладывались и представлялись на следующих конференциях, форумах, семинарах, совещаниях: третья международная промышленная ярмарка MIIF-2004 (Москва, 2004); четвёртая международная конференция и выставка CAD/CAM/PDM-2004 (Москва, 2004); вторая международная конференция «Параллельные вычисления и задачи управления» (Москва, 2004); третья научно-техническая конференция «Перспективы использования новых технологий и научно-технических решений в изделиях ракетно- космической техники разработки ГКНПЦ им. М.В. Хруничева» (Москва, 2003); четвёртый международный форум «Высокие технологии XXI века» (Москва, 2003); вторая международная конференция по проблемам управления (Москва, 2003); двадцать шестой международный семинар- презентация по ПТК, промышленным контроллерам, техническим и программным средствам АСУТП, SCADA-системам, приборам и средствам автоматизации (Москва, 2002); научно-техническое совещание «Компьютерное моделирование и оптимизация технологических процессов электротермических производств» (Санкт-Петербург, 2002); всероссийская научно-практическая конференция «Ресурсосберегающие проекты и технологии» (Москва, 2001); международная конференция «Параллельные вычисления и задачи управления» (Москва, 2001); международная конференция и выставка CAD/CAM/PDM-2001 (Москва, 2001); девятая международная конференция «Проблемы управления безопасностью сложных систем» (Москва, 2001); научно-техническое совещание «Компьютерное моделирование при оптимизации технологических процессов электротермических производств» (Санкт-Петербург, 2000); восьмая международная конференция «Проблемы управления безопасностью сложных систем» (Москва, 2000); международная конференция «Идентификация систем и задачи управления» (SICPRO) (Москва, 2000); международная научно-практическая конференция "Теория активных систем" (Москва, 1999); юбилейная международная конференция по проблемам управления (Москва, 1999); межведомственный научно- практический семинар «Проблемы и технологии создания и использования космических систем и комплексов на базе малых КА и орбитальных станций» (Москва, 1998); научно-техническое совещание «Компьютерные методы в управлении электротермическими режимами рудотермических печей» (Санкт-Петербург, 1998); межведомственный научно-практический семинар ГКНПЦ им. М.В. Хруничева «Новые задачи, пути совершенствования перспективных средств РКТ и технологии их создания» (Москва, 1997); научно-практическая конференция с международным участием «Проблемы информатики» (Самара, 1991); научно-практическая школа-семинар «Программное обеспечение ЭВМ: индустриальная технология, интеллектуализация разработки и применения» (Ростов-на-Дону, 1988); третье всесоюзное совещание «Высокопроизводительные вычислительные системы» (Таллин, 1988); восьмой всесоюзный семинар «Параллельное программирование и высокопроизводительные системы» (Киев, 1988); шестая всесоюзная школа «Многопроцессорные вычислительные системы» (Москва, 1985); пятая всесоюзная школа-семинар «Параллельное программирование и высокопроизводительные системы» (Киев, 1982); всесоюзное совещание «Высокопроизводительные вычислительные системы» (Тбилиси, 1981); всесоюзное научно-техническое совещание «Проблемы создания и использования высокопроизводительных машин» (Кишинёв, 1979).
Публикации. Основные результаты научных исследований по теме диссертации содержатся в 66 публикациях, в их числе 19 публикаций в ведущих научных журналах и изданиях перечня Высшей аттестационной комиссии.
Структура и объём диссертации. Работа состоит из введения, пяти глав, заключения, содержит 229 страниц текста, 30 рис., 2 табл., список литературы из 236 названий.
Исследование методов обеспечения работы систем поддержки принятия оперативных решений в режиме реального времени
В настоящее время накоплен значительный опыт в исследованиях по применению параллельной обработки информации для ускорения выполнения приложений. Распараллеливание вычислений создаётся, в основном, на основе подходов, основанных на моделях параллелизма данных и параллелизма задач.
Основная идея подхода, основанного на параллелизме данных, заключается в применении одной операции сразу к нескольким элементам массива данных. Разные части массива обрабатываются на векторном процессоре или на разных процессорах параллельного компьютера. Векторизация или распараллеливание в этом случае чаще всего выполняются во время трансляции. При этом программист может задавать опции векторной или параллельной оптимизации транслятору, директивы параллельной компиляции.
Метод программирования, основанный на параллелизме задач, основан на разбиении исходной задачи на несколько относительно самостоятельных подзадач. Каждая подзадача выполняется на своём процессоре. Подзадачи могут обмениваться результатами своей работы. Такой обмен осуществляется вызовом процедур специализированной библиотеки. Примерами специализированных библиотек являются библиотеки MPI (Message Passing Interface) и PVM (Parallel Virtual Machines).
Выделим следующие основные средства разработки параллельных программ [232]: коммуникационные библиотеки и интерфейсы параллельного программирования (АСЕ, ARCH, ВІР, BLACS, BSPlib, CVM, Counterpoint, FM, Gala, GA, HPVM, ICC, JIAJIA, KELP, LPARX, MPI, MPL, OOMPI, OpenMP, P4, Para++, Prosphoms, PVM,Quarks, ROMIO, ShMem, SVMlib, TOOPS, Treadmarks). специализированные параллельные языки и расширения традиционных языков программирования (C-DVM, А++/Р++, СС++, Charm/Charm++, Cilk, НРС, Maisie, Mentat, mpC, MPC++, Parsec, pC++, sC++, uC++, Fortran-DVM, Cray MPP Fortran, F-, Fortran 90/95, Fortran D95, Fortran M, Fx, HPF, Opus, Vienna Fortran, НОРМА, ABCL, Adl, Ada, Concarrent Clean, Erlang, Linda, Modula-3, NESL, Occam, Orca, Parallaxis, Phantom, Sisal, SR, ZPL); специализированные параллельные библиотеки (ATLAS, Aztec, BlockSolve95, Distributed Parallelization at CWP, DOUG, GALOPPS, JOSTLE, NAMD, P-Sparslib, PIM, ParMETIS, PARPACK, PBLAS, PETSc, PGAPack, PLAPACK, ScaLAPACK, SPRNG); средства автоматического распараллеливания (BERT 77, FORGExplorer, КАР, PIPS, VAST/Parallel и другие); интегрированные среды прототипирования, разработки и отладки параллельных программ (CODE, HeNCE, GRADE, TRAPPER, EDPEPPS, Reactor, DEEP, Converse).
Распараллеливание обработки информации открывает большие возможности повышения производительности СППОР, но приводит к необходимости создания соответствующего программного обеспечения и его адаптации.
Так как СППОР содержат модули числовой и символьной обработки информации, то можно выделить следующие уровни параллелизма, характерные для этих систем [48, 118,178]: параллелизм на уровне задач, подзадач и программных модулей; параллелизм на уровне циклических конструкций; параллелизм на уровне правил и внутри правил.
Параллелизм на уровне задач, подзадач и программных модулей Известные механизмы организации выполнения и взаимодействия параллельно-последовательных фрагментов (подзадач, процессов) одной задачи традиционно реализуются программными средствами операционных систем. Идеологически эти механизмы «с точки зрения» операционной системы аналогичны аппарату управления задачами в мультипрограммном режиме, причём на операционную систему возлагаются дополнительные функции по организации связей между подзадачами, по анализу иерархической подчинённости подзадач, условий их инициации и завершения в рамках единого комплекса взаимосвязанных программ. Как и при управлении задачами, в процессе подготовки подзадач к их решению операционная система создаёт большое число таблиц с информацией, необходимой для выполнения подзадачи: таблицы управления подзадачей (со статической или динамической информацией о типе подзадачи, её текущем состоянии, приоритете, требуемом объёме памяти и пр.), таблицы потребления системных ресурсов, перекодировки логических наименований устройств в физические адреса, блоки управления файлами и пр., хотя некоторые таблицы могут быть общими для задачи в целом.
Такая организация управления параллельно-последовательными фрагментами задачи приводит к тому, что обработка в операционной системе каждого обращения к аппарату подзадач (обычно - с прерыванием подзадачи) требует выполнения от нескольких сот до нескольких тысяч машинных команд. Выполнение этих команд и простои подзадач составляют основную часть «накладных расходов» на организацию выполнения каждого фрагмента и задачи в целом.
Структура информационного обмена в системе поддержки принятия оперативных решений
Информационное ядро системы включает информационную модель объекта управления и информационную модель внешней среды (Рис. 2.2). Необходимость использования экспертных знаний обуславливает включение в информационное ядро типовой модели базы знаний. Кроме того, в информационном ядре системы хранится протокол работы системы.
Информационное ядро системы представляет собой полномасштабный сервер данных, реализуемый на основе современных СУБД, обеспечивающий необходимый уровень доступа, защиты и управления данными.
В функции информационного ядра помимо традиционных для СУБД функций обеспечения требуемой скорости поиска и извлечения данных, защиты целостности информационных структур, защиты данных от несанкционированного использования, обеспечения синхронизации при совместном доступе к данным, обеспечения архивирования и восстановления данных после сбоев, входят также специфические функции СППОР, например, обеспечение контроля своевременного обновления данных всех информационных моделей с требуемой частотой. Кроме того, некоторые алгоритмы обработки информации эффективнее и надежнее реализовать на информационном сервере, используя возможности СУБД. Так, например, на основе механизма, реализующего обработку данных непосредственно в момент записи или изменения в базе данных, можно эффективно реализовать проверку выхода параметров информационной модели объекта управления за границы диапазона допустимых, предаварийных или аварийных значений, в случае, если граничные значения указанных диапазонов являются параметрами информационной модели объекта управления.
Все блоки функциональной части системы имеют доступ к нужной информации информационного ядра системы. Функциональная часть системы будет рассмотрена в главе 3.
Предлагаемая в данной работе типовая информационная модель объекта управления базируется на определении пяти типов данных [79].
Первый тип данных - активный элемент - введен для отображения дискретных управляющих воздействий оператора на объект управления. Активный элемент характеризуется двумя дискретными величинами -«состояние» и «команда», принимающими значения из конечных наборов допустимых значений. Пусть D t{tm) - состояние активного элемента / в момент времени tm =t0+mAt, т=1,2,..., D"(tm) - последняя команда, поданная на активный элемент / до момента времени tm, і = 1,...,/, I - число активных элементов. Обозначим конечное множество состояний активного элемента / через , , а конечное множество команд для активного элемента / через Dt .Тогда D;(OeD ,DXtm)ED .
Активный элемент сопоставляется устройству с дискретным управлением, которое может находиться в конечном числе состояний. Состояние устройства может быть изменено оператором при помощи автоматизированной системы управления объектом. Команда вводится оператором в автоматизированную систему управления объектом и отображается в информационной модели объекта управления СППОР.
Помимо изменения оператором, состояние устройств с дискретным управлением может изменяться системой автоматической противоавариинои защиты. Для моделирования системы автоматической противоавариинои защиты введен второй тип данных — автоматическая блокировка. Автоматическая блокировка характеризуется условием срабатывания -логическим условием над переменными информационной модели, булевской переменной активности/неактивности блокировки и выполняемым действием. Автоматическая блокировка может быть включена или отключена оператором. Она считается активной, если выполнено связанное с ней условие срабатывания и блокировка включена. Если автоматическая блокировка активна, то выполняется действие, определяемое условием срабатывания. Действие заключается в подаче команд на одно или несколько устройств с дискретным управлением. В случае активности автоматической блокировки команды, подаваемые в результате выполнения соответствующего действия, не могут быть изменены оператором.
Структура функциональной части системы поддержки принятия оперативных решений
Блок обработки и анализа данных сообщает об изменениях в параметрах, которые могут представлять интерес для оператора, описывает отдельные аспекты возникшей ситуации, даёт оценку ситуации в зависимости от состояния объекта управления и внешней среды.
Параметры задачи обработки и анализа состояния объекта управления можно разбить на три основные группы: параметры объекта управления; параметры внешней среды (например, в случае экологического мониторинга окружающей среды это уровни концентрации загрязняющих веществ в природных средах, метеопараметры и др.); выходные параметры, отражающие основные свойства системы управления.
При оценке ситуации в блоке обработки и анализа данных осуществляется контроль важных событий, вычисляются необходимые дополнительные атрибуты к исходной информации об объекте управления и внешней среде, непрерывно (в реальном времени) производится оценка безопасности текущей ситуации.
Примерами важных событий, возникающих в технологическом процессе уничтожения люизита, являются: увеличение уровня (веса) люизита после сигнализации максимального уровня (веса); повышение давления в химическом реакторе гидролиза люизита выше предельно-допустимого значения при дозировке люизита; повышение температуры в химическом реакторе гидролиза люизита при дозировке люизита выше предельно допустимого значения; остановка мешалки химического реактора гидролиза люизита в ходе проведения процесса гидролиза люизита; превышение максимального уровня реакционной массы в химическом реакторе гидролиза люизита; сигнализация о снижении расхода азота до минимального значения на линии подачи в химический реактор гидролиза люизита; снижение расхода раствора щёлочи на орошение колонны ниже нормативного значения; отключение рабочего насоса.
Блок обработки и анализа данных содержит процедуры и критерии для выбора наиболее эффективного алгоритма обработки конкретного типа данных из некоторого множества имеющихся алгоритмов. Алгоритм обработки, эффективный для одного типа данных может быть не эффективным для данных другого типа. Например, специалисты по аналитической химии не всегда могут выбрать из большого числа потенциально пригодных методов обработки данных алгоритм, подходящий для конкретного типа данных. С другой стороны, специалисты по обработке данных не могут предложить универсального алгоритма обработки, одинаково пригодного для любого случая из-за большого разнообразия типов данных.
Необходимо учитывать нечёткость, неполноту и противоречивость исходной информации, которые могут быть связаны как с недостаточным количеством произведённых измерений (например, в случае отказа измерительной аппаратуры), так и с задержкой получения информации, неисправностью каналов связи и др.
Блок генерации планов действий оператора генерирует планы действий по управлению объектом на основе анализа его состояния, выполненного блоком обработки и анализа данных.
Под действиями оператора будем понимать команды по управлению оборудованием (включение/выключение двигателей, открытие/закрытие клапанов, изменение параметров регулирования, включение/отключение блокировок и т.д.).
Так, для снижения давления в химическом реакторе гидролиза люизита при дозировке люизита в зависимости от причины возникновения производственных неполадок и аварийных ситуаций действиями оператора могут быть: остановка процесса дозировки люизита закрытием клапана на приёме люизита из мерника в реактор гидролиза люизита; проверка положения клапана на линии выхода абгазов гидролиза люизита после теплообменника; при необходимости - дистанционное открытие клапана; проверка работоспособности предохранительного клапана, осуществляющего сброс избыточного давления; при необходимости -переключение на резервный предохранительный клапан; проверка перепада давления на входе и выходе абгазов из фильтра; при давлении, превышающем допустимую величину, остановка процесса; переход на резервный фильтр; проверка задания регулировки работы регулирующего клапана подачи люизита; при необходимости - корректировка задания, уменьшение скорости изменения уровня в мернике и т.д.
Универсальный метод распараллеливания циклических конструкций
СППОР реального времени должна своевременно и предсказуемо реагировать на внешние возмущения, то есть своевременно обрабатывать события. Реакция на событие должна уложиться в пределы определённого лимита времени. Для эффективного выполнения функций систем, основанных на знаниях и работающих в режиме реального времени, необходимо ориентироваться, в частности, на максимально параллельную обработку информации.
Идеи параллельных и распределённых вычислений в настоящее время получили самое широкое распространение. Высокопроизводительные компьютеры, в которых реализованы многопоточные, параллельные и распределённые вычисления, создают новые возможности и проблемы для разработчиков программного обеспечения для этих компьютеров. Разрабатываются специальные программные средства для того, чтобы максимально использовать все преимущества параллельности аппаратной части компьютеров. В числе этих программных средств - блоки автоматического распараллеливания и векторизации.
Ускорение обработки данных на параллельных компьютерных архитектурах может быть получено, в частности, за счёт осуществления последовательно-параллельного выполнения: выборки потока данных из памяти, исходя из типа вычислителя и типа памяти (общая, распределённая, комбинированная); вычислений, исходя из типа вычислителя; записи результатов в память, исходя из типа вычислителя и типа памяти.
Данная постановка задачи может быть ориентирована, например, на: часто синхронизируемую систему с возможностями быстрого обмена информацией между процессорами; системы, в которых обмен информацией между процессами затруднён; возможно пересекающиеся, но автономные участки — параллельные ветви, которые могут выполняться независимо друг от друга.
При управлении сложными объектами с помощью автоматизированных систем управления должна быть обеспечена возможность поиска приемлемого решения на основе СППОР в условиях жёстких временных ограничений. Число анализируемых параметров может достигать многих тысяч, что не позволяет провести качественный анализ информации на основе последовательной её обработки. Поэтому естественным образом возникает задача распараллеливания процесса обработки информации в СППОР.
Наибольшее ускорение выполнения программ по сравнению с другими типами распараллеливания даёт распараллеливание циклических конструкций. Поэтому этому направлению распараллеливания уделяется всё внимание в этой главе работы.
Векторизация - один из способов получения программ для вычислительных систем с векторным процессором. В узком смысле векторизация сводится к выявлению частей программы, которые могут быть представлены в виде последовательности векторных команд. В более широком смысле под векторизацией можно понимать обнаружение длинных серий однотипных операций в программе. Данные, к которым применяются эти операции, образуют «регулярные выемки» из памяти (т.е. адресация может быть задана совокупностью векторных команд).
Большое превышение скорости векторной обработки над скалярной приводит к увеличению роли векторизации для повышения производительности современных вычислительных систем. Поэтому в состав многих высокопроизводительных вычислительных систем входят векторизующие компиляторы.
Выделим две разновидности векторизации: ручную и автоматическую. Ручное преобразование программы к векторному виду выполняется самим программистом и обычно нежелательно для пользователя. Автоматический векторизатор - это программа, входящая в математическое обеспечение вычислительной системы. В ряде векторизаторов используется комбинация указанных способов, а именно: сочетание автоматической векторизации с подсказками пользователя. В данной работе рассматриваются методы автоматической векторизации, связанные с методами автоматического распараллеливания циклических конструкций [6, 84].
Ниже описывается подход, позволяющий взглянуть с общих позиций на методы распараллеливания циклических конструкций, основанные на совмещении вычислений, не пересекающихся по входам-выходам [6]. По сравнению с методами гиперплоскости и координат [207] существенно ослабляются ограничения на форму индексных выражений в исходном цикле. Из-за более общего вида условий, накладываемых на итерации, выполняемые одновременно, появляется возможность распараллеливать циклы, которые не распараллеливаются другими известными методами. Кроме того, показано, как применить переупорядочивание операторов внутри цикла (применяемое в методе координат) при распараллеливании по гиперплоскостям, т.е. объединены преимущества методов гиперплоскостей и координат. Усилены результаты метода декомпозиции [205] путём разрыва некоторых информационных зависимостей в теле цикла.
