Содержание к диссертации
Введение
Глава 1. Постановка задачи, математическая модель и численная реализация . 29
Описание рассматриваемых задач 29
Математическая модель. Безразмерные уравнения Навье-Стокса и граничные условия 29
Численная реализация 32
Пространственная аппроксимация 32
Определение конвективного численного потока 36
Схема Роу 38
Кинетически-согласованная разностная схема Четверушкина 38
Поток повышенного порядка точности (MUSCL аппроксимация) 39
Определение диффузионного численного потока 41
Определение потоков на границе области 42
Аппроксимация по времени 43
Расчетный алгоритм 44
Глава 2. Последовательный алгоритм 49
Последовательный алгоритм ...49
Обработка нерегулярных сеток 51
Глава 3. Параллельные алгоритмы 56
Балансировка загрузки 56
Параллельный алгоритм для систем с общей памятью 66
Параллельный алгоритм для многопроцессорных систем с распределенной памятью 72
Распределенная обработка нерегулярных сеток 72
Параллельный алгоритм 80
Глава 4. Результаты расчетов 89
Расчет газодинамических течений 89
Эффективность параллельных алгоритмов 108
Заключение 119
Литература 120
- Математическая модель. Безразмерные уравнения Навье-Стокса и граничные условия
- Поток повышенного порядка точности (MUSCL аппроксимация)
- Обработка нерегулярных сеток
- Параллельный алгоритм для систем с общей памятью
Введение к работе
Актуальность темы. Широкомасштабное применение в телекоммуникационных системах (ТКС) правоохранительньж органов и других силовых структур средств вычислительной (микропроцессорной) техники обусловливает бурное развитие технологии пакетной передачи информации системами радиосвязи. В свою" очередь системы радиосвязи являются одним из основньж каналов утечки информации, поскольку защита информации в них затруднена из-за их протяженности и возможности доступа к передаваемым сигналам за пределами контролируемых зон объектов.
Применение методов криптографической защиты позволяет практически полностью исключить возможность прочтения и подмены информации. Однако криптографические методы не защищают от преднамеренных прицельных помех, использование которьж может полностью парализовать работу подразделений МВД и других силовых структур.
В свою очередь эффективность радиопротиводействия, основанного на создании ответных помех зависит от временной задержки момента прихода помехи относительно момента прихода сигнала (информационного пакета) в точку приема системы радиосвязи. Эта задержка обусловлена временными затратами на обнаружение и идентификацию излучения, настройку и включение передатчиков помех, а также на распространение радиоволн. Следствием влияния этих факторов является существование «эллипсов доступности» систем радиосвязи с фокусами в точках размещения их корреспондентов, находясь за пределами которьж средства помех (СП) не способны оказывать эффективное воздействие на сигналы по причине запаздывания помех.
Размеры «эллипса доступности», а, следовательно, и максимально возможные дистанции подавления, тем меньше, чем меньше время излучения сигнала и чем больше время реакции средств помех. Отсюда следует вывод, что посредством уменьшения длительности сигнала опасная зона (зона, в пределах которой может быть реализовано эффективное радиопротиводействие) может быть сокращена до размеров контролируемой (охраняемой) зоны, а использование в системах радиосвязи сигналов, имеющих время излучения меньше некоторого порогового значения, исключает всякую возможность их подавления.
С другой стороны уменьшение длительности информационных пакетов приведет к неизбежному увеличению времени передачи всего сообщения из-за наличия в каждом пакете служебных символов и защитных интервалов между пакетами. А увеличение времени передачи сообщения, в свою очередь, ведет к образованию очередей в системе связи и к несвоевременной доставке сообщений, т.е. за время, превышающее оперативную ценность передаваемой информации.
В этой связи представляется актуальным проведение исследования, направленного на
выявление зависимости защищенности передаваемой в системах радио
связи информации от параметров используемых сигналов, средсіВЛрвФИВрдей-
ствия и радиоэлектронной обстановки; , ~ZZr НАЦИОНАЛЬИМI
«&1
оценку эффективности регулирования длительности сигналов как меры защиты от разрушающего воздействия помех;
обоснование предложений по защите информации в каналах радиосвязи.
Объектом исследования являются системы пакетной радиосвязи перспективных телекоммуникационных систем.
Предметом исследования выступает управление длительностью информационных пакетов в системах пакетной радиосвязи.
Целью исследования является разработка предложений по организации противодействия преднамеренным прицельным помехам в системах пакетной радиосвязи посредством управления длительностью информационных пакетов.
Для достижения указанной цели в работе решены следующие научные задачи:
Выявлены особенности проявления угроз информационной безопасности пакетной радиосвязи и обоснованы предложения по организации противодействия им на основе управления временными параметрами передаваемьж сигналов.
Разработан комплекс моделей для исследования эффективности противодействия прицельным преднамеренным помехам, создаваемым в системах пакетной радиосвязи перспективных ТКС на основе управления длительностью информационных пакетов.
Оценена эффективность противодействия прицельным преднамеренным помехам, создаваемым в системах пакетной радиосвязи перспективных телекоммуникационных систем ОВД на основе управления длительностью информационных пакетов.
Обоснованы предложения по защите информации в системах пакетной радиосвязи перспективных телекоммуникационных систем ОВД.
Методы исследования. В работе использованы методы системного анализа, теории вероятностей и математической статистики, теории информационной безопасности, математического моделирования, а также методы оптимизации по количественным критериям.
Степень обоснованности научных положений, выводов и рекомендаций, сформулированных в диссертации, обеспечивается:
корректным использованием методов исследования и математического моделирования;
сопоставлением результатов с известными из публикаций частными случаями.
Научная новизна результатов, полученных в диссертации при решении перечисленных задач, состоит в следующем:
1. Разработана методология исследования эффективности защиты информации в системах пакетной радиосвязи в условиях взаимных и преднамеренных помех в части учета совокупности пространственно-временных характеристик конфликтного взаимодействия средств связи и средств помех. Это позволило оценить диапазоны варьирования длительностью информационньж пакетов (сообщений) обеспечивающие эффективную защиту информации от прицельных-преднамеренных помех, создаваемых различными способами.
2. Обоснованы рекомендации по повышению эффективности защиты информации (повышению достоверности и своевременности доставки сообщений) в системах пакетной радиосвязи перспективных ТКС ОВД на основе приспособления параметров сигналов (длительности передаваемых информационных пакетов) к параметрам средств радиопротиводействия и изменяющимся условиям РЭО.
Основные научные положения, выносимые на защиту:
Эффективность радиопротиводействия прицельным преднамеренным радиоэлектронным помехам (ответным помехам или помехам,, создаваемым в режиме «погони вслед за сигналом») зависит от пространственно-временньж параметров конфликта, определяющих временную задержку момента прихода помехи относительно момента прихода сигнала на текущей частоте в точку приема системы пакетной радиосвязи. Возможен выбор значений длительности передаваемьж информационньж пакетов (фрагментов), обеспечивающих доставку информации в точку приема в условиях преднамеренньж прицельньж помех с требуемыми достоверностью и своевременностью.
Рекомендации по совершенствованию средств радиосвязи, направленные на согласование значения длительности передаваемьж средствами связи сообщений (информационньж пакетов) с значениями параметров средств радиопротиводействия и радиоэлектронной обстановки (РЭО), позволяющие повысить эффективность защиты информации в системах пакетной радиосвязи перспективных телекоммуникационных систем ОВД, использующих сигналы малой длительности в условиях радиоэлектронного противодействия и изменяющейся РЭО.
Практическая значимость и результаты внедрения.
1. Разработанные в диссертации методики использованы
при разработке учебных пособий «Источники и каналы утечки информации» и «Защита информации в мобильных системах связи» для курсантов и слушателей образовательных учреждений высшего профессионального образования МВД России по специальности 075600 - Информационная безопасность телекоммуникационных систем.
в учебном процессе Воронежского института МВД России при разработке курса лекций по дисциплинам «Технические средства защиты информации», «Организация радиоэлектронной защиты в органах внутренних дел» и «Организация радиоэлектронной разведки в органах внутренних дел» - в части теоретических аспектов защиты информации в системах радиосвязи, использующих сигналы малой длительности и их разведки;
в учебном процессе Военного института радиоэлектроники МО РФ при разработке курса лекций по дисциплинам «Технические средства защиты информации» - в части теоретических аспектов радиопротиводействия системам радиосвязи, использующим сигналы малой длительности и их разведки;
в учебном процессе Московского государственного технического университета им. Н.Э. Баумана по подготовке, переподготовке и повышению квалификации специалистов в области защиты государственной тайны и противодейст-
вия техническим разведкам при изучении ими дисциплин, касающихся данной тематики.
Результаты диссертационнойработы внедрены в:
Воронежском институте Министерства внутренних дел РФ.
Военном институте радиоэлектроники Министерства обороны РФ;
5 Центральном научно-исследовательском испытательном институте Министерства обороны РФ;
Региональном учебно-научном центре «Безопасность» при Московском государственном техническом университете им. Н.Э. Баумана;
Отделе связи, специальной техники и автоматизации службы тыла аппарата ГУВД Воронежской области МВД России.
Внедрение результатов подтверждается соответствующими актами.
Апробация работы.
Основные методические и практические результаты исследований докладывались на следующих конференциях:
6-й Всероссийской научно-технической конференции «Информация и безопасность» - Москва 2003 г.;
Всероссийской научно-практической конференции «Современные проблемы борьбы с преступностью» - Воронеж 2003 г.;
2-й Всероссийской конференции «Обеспечение информационной безопасности. Региональные аспекты» - Сочи, 2003;
ГУ Всероссийской научно-практической конференции «Охрана, безопасность и связь» («Охрана- 2003») - Воронеж, 2003 г.
Всероссийской научно-практической конференции «Современные проблемы борьбы с преступностью» - Воронеж 2004 г.;
Публикации. По теме диссертационной работы опубликовано два учебных пособия, а также 10 научно-технических статей и докладов.
Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения и библиографического списка использованной литературы, изложенных на 141 страницах машинописного текста, содержащих 24 рисунка, 4 таблицы.
Математическая модель. Безразмерные уравнения Навье-Стокса и граничные условия
Обработка сеток большого размера (миллионы узлов) сопряжена с трудностями, связанными с нерегулярностью их структуры и непосредственно с обработкой больших объемов данных. Описание геометрии такой сетки не может целиком храниться в оперативной памяти одного вычислительного узла, и, следовательно, все действия, связанные с ее обработкой должны выполняться в распределенном режиме.
Распределенная обработка топологии сеток выполняется с использованием алгоритма двухуровневого распределенного хранения и обработки топологии нерегулярных сеток. Перед началом серии расчетов сетка делится на множество подобластей (микродоменов). Затем в соответствии с полученным разбиением производится перенумерация (изменение идентификаторов) узлов сетки и выделяется описание геометрии каждого микродомена. Далее топология сетки записывается в распределенном виде: описание общей структуры (граф микродоменов и их связей) и множество отдельных описаний микродоменов. Формат записи описаний отдельных подобластей определяется требованиями используемой для расчетов численной методики. В соответствии с выбранным алгоритмом численного моделирования микродомен задается набором данных, которых достаточно для автономного определения геометрических параметров контрольных объемов с центрами в узлах рассматриваемой подобласти.
Процедура подготовки расчета (параллельного выполнения вычислительных итераций) делится на несколько этапов. На этапе балансировки загрузки выполняется разбиение графа микродоменов на подобласти, в результате чего каждый процессор получает список обрабатываемых микродоменов. Далее происходит объединение микродоменов процессора в расчетную область: составляется список обрабатываемых элементов геометрической модели расчетной области процессора. Следующий этап заключается в локализации полученной расчетной области с учетом передаваемых и принимаемых данных (соответствующая перенумерация узлов) и одновременной инициализации буферов приема и передачи данных.
Использование алгоритмов распределенного хранения топологии сеток и предложенного алгоритма локализации данных позволяет снизить накладные расходы на подготовительной стадии и повысить эффективность параллельного алгоритма на этапе непосредственно моделирования. Сокращается время, затрачиваемое на балансировку загрузки: число элементов графа микродоменов на несколько порядков меньше числа узлов исходной сетки. Предлагаемый формат описания подобластей позволяет процессорам в параллельном режиме без обмена сообщениями считывать с диска описания микродоменов и объединять обрабатываемые подобласти, а также автономно инициализировать массивы приема и передачи данных. В результате локализации геометрической модели расчетной подобласти процессора на основе предлагаемого алгоритма ее дальнейшая обработка с алгоритмической точки зрения практически не отличается от обработки сетки целиком, т.е. исключаются неоднородности вычислительного алгоритма, связанные с обработкой данных, принадлежащих другим вычислительным узлам. Кроме того, на этапе выполнения вычислительных итераций прием данных осуществляется без промежуточной буферизации, которая часто встречается в реализациях параллельных алгоритмов, основанных на модели передачи сообщений.
В заключение описания параллельного алгоритма для вычислительных кластеров рассматриваются возможные варианты организации межпроцессорного обмена данными (периодичности обменов и объемов передаваемых данных) во время выполнения вычислительных итераций, и дается теоретическая оценка их эффективности с точки зрения производительности соответствующих параллельных программ. В четвертой главе содержатся результаты проведенных численных экспериментов, подтверждающие практическую значимость и эффективность разработанных в работе алгоритмов.
При помощи разработанного комплекса параллельных программ выполнено численное моделирование ряда задач газовой динамики с использованием нерегулярных сеток. Рассматриваются задачи о распаде произвольного разрыва, сверхзвуковом обтекании ступени в прямоугольном канале и моделирование внешнего обтекания сферы при малом числе Маха и различных числах Рейнольдса. Несмотря на то, что задачи о распаде произвольного разрыва и сверхзвуковом обтекании ступени в прямоугольном канале являются по сути одномерной и двумерной, соответственно, задачи рассматривались в пространственной постановке. В расчетах использованы квазиравномерные и нерегулярные тетраэдральные сетки, а также тетраэдральные сетки с прямоугольными элементами, полученные путем разбиения пространственных ортогональных решеток. Для задачи о распаде произвольного разрыва выполнена проверка сходимости к точному решению на последовательности сгущающихся сеток. Для остальных расчетов приводится сравнение полученных результатов с экспериментальными данными и результатами расчетов по другим методикам.
В качестве примера использования разработанного комплекса программ для выполнения научных исследований и производственных расчетов выполнено моделирование невязкого обтекания летательного аппарата сложной формы при нулевом угле атаки набегающего потока. По результатам расчета для обтекаемого тела определен коэффициент аэродинамического сопротивления.
Оценка эффективности предложенных в работе последовательного и параллельных алгоритмов моделирования задач газовой динамики выполнялась путем тестирования производительности разработанного на их основе комплекса программ. Модельные расчеты выполнялись с использованием нерегулярных тетраэдральных сеток, содержащих от 500 000 до 2 000 000 узлов. Для расчета в последовательном режиме дан пример возможной зависимости времени выполнения программы от порядка обработки элементов и нумерации узлов сетки. Запуск параллельных программ производился на различных многопроцессорных вычислительных системах с общей и распределенной памятью. Приведены результаты сравнения производительности параллельных программ для систем с общей и распределенной памятью по отношению к производительности последовательной программы, а также сравнительный анализ эффективности программы для систем с распределенной памятью при расчетах на большом числе процессоров (до 100) для двух различных вычислительных кластеров. На основании полученных в ходе тестирования производительности результатов делается оценка эффективности разработанных алгоритмов и программ.
В конце главы приводятся результаты по эффективности применения алгоритма двухуровневого распределенного хранения нерегулярных сеток при расчетах на многопроцессорных системах с распределенной памятью. В заключении диссертационной работы сформулированы основные выводы и приведены выносимые на защиту результаты.
Поток повышенного порядка точности (MUSCL аппроксимация)
Несмотря на то, что последовательная программа не дает возможности обрабатывать большие объемы данных, разработка эффективного последовательного алгоритма имеет большое практическое значение, В ходе разработки последовательного алгоритма и его дальнейшей программной реализации выполняется тестирование эффективности и проверяется корректность основных вычислительных модулей. Помимо этого последовательная программа в большинстве случаев является базовой точкой для оценки эффективности разрабатываемого параллельного программного обеспечения и правильности работы параллельных программ.
При распараллеливании на основе метода геометрического параллелизма какого-либо последовательного алгоритма расчетная область делится на непересекающиеся подобласти, относимые к обработке на различных процессорах. При этом в случае реализации однородных вычислительных алгоритмов на каждом процессоре решается отдельная подзадача, которая, по сути, мало чем отличается от обработки всей сетки в последовательном режиме. Единственное отличие состоит в необходимости обменов данными и, следовательно, синхронизации работы вычислительных узлов.
Разработанные в рамках диссертационной работы последовательный алгоритм и параллельный алгоритм моделирования для систем с общей памятью содержат в своей основе одну и ту же идею. Используемые в последовательной программе основные вычислительные модули (определение конвективных и диссипативных потоков через грань контрольного объема, вычисление узловых градиентов в узлах подобласти сетки) практически без изменений используются во всех реализациях вычислительного алгоритма, включая параллельную программу для систем с распределенной памятью. Такая универсальность во многом объясняется свойством однородности используемого вычислительного алгоритма.
Геометрия расчетной области задается координатами узлов расчетной сетки, и массивами описаний ее объемных (тетраэдров) и поверхностных элементов (граничных треугольников). Узлы сетки имеют одномерную нумерацию, т.е. каждый узел однозначно определяется некоторым целым положительным числом (идентификатором). Следует обратить внимание на то, что ориентация элементов объемной и поверхностной сеток (порядок перечисления вершин в описаниях тетраэдров и треугольников) не должен учитываться в описании геометрической модели. Разрабатываемое программное обеспечение должно самостоятельно на этапе определения необходимых для расчетов геометрических параметров восстанавливать ориентацию элементов в соответствии с определенными в расчетном алгоритме критериями.
В данной главе и далее при описании параллельных алгоритмов для простоты будем считать, что модельный расчет выполняется в следующем режиме: рассматривается система уравнений Навье-Стокса; расчет конвективного потока выполняется с повышенным порядком точности; интегрирование по времени осуществляется явным линейным методом первого порядка (схема Эйлера). В этом случае вычисление значений газодинамических переменных на новом слое по времени, т.е. выполнение основных вычислительных блоков расчетного алгоритма, происходит в следующей последовательности: вычисление шага по времени (метод конечных элементов); вычисление разностных градиентов (метод конечных элементов); определение конвективных потоков через внутренние грани контрольных объемов (метод конечных объемов); вычисление диссипативных потоков (метод конечных элементов); обработка граничных элементов (метод конечных объемов); вычисление значений газодинамических переменных на новом слое по времени. Дальнейшая реализация основных вычислительных блоков будет заключаться в последовательном вычислении расчетных величин по элементам сеток конечных объемов или конечных элементов в зависимости от положенного в основу соответствующего блока метода. При этом, как уже говорилось ранее, для снижения вычислительной сложности алгоритма обработка элементов должна выполняться только один раз. По проведенным оценкам используемый расчетный алгоритм и выбранные в дальнейшем алгоритмы реализации основных вычислительных модулей позволяют минимизировать число выполняемых в процессе работы вычислительных операций. Однако на практике реализация вычислительных алгоритмов с минимальным числом действий не всегда гарантирует минимальное время выполнения соответствующей программы. В качестве примера рассмотрим задачу простого суммирования элементов квадратной матрицы большого размера. Суммирование элементов можно выполнить двумя способами - суммируя элементы по строкам или по столбцам. Оба алгоритма содержат одинаковое число действий. Однако время выполнения их программных реализаций на практике будет различаться в разы в зависимости от способа выделения памяти под матрицу: по строкам или по столбцам. Это объясняется тем, что в случае совпадения алгоритмов суммирования и выделения памяти будет выполняться суммирование элементов, расположенных в оперативной памяти последовательно друг за другом. В противном случае будет реализован алгоритм произвольного доступа к памяти, время выполнения которого, естественно, намного выше.
Подобное развитие событий с большой вероятностью возможно при работе с нерегулярными сетками. В данном случае порядок доступа к памяти, а, следовательно, и время выполнения программной реализации алгоритма, при обработке элементов сетки напрямую связан с алгоритмом нумерации ее узлов, и при определенном стечении обстоятельств возможна ситуация, когда время выполнения расчета будет зависеть не столько от объема обрабатываемых данных, сколько от алгоритма нумерации. То есть, возможна ситуация, когда расчеты с использованием сеток существенно разного размера будут занимать одинаковое время. Естественно, что при наличии таких зависимостей тестирование эффективности и последующее сравнение параллельных программ с последовательной реализацией не будет давать объективных результатов. Следовательно, необходима разработка алгоритма, для которого зависимость нумерации узлов и времени выполнения соответствующей программы будет минимальна.
Часто для повышения эффективности какого-либо алгоритма и его реализации используется следующий прием: исходная задача делится на независимые подзадачи сравнительно малого размера, которые затем последовательно обрабатываются. Например, одним из эффективных решений для задачи сортировки массива является следующая последовательность действий [24]:
Обработка нерегулярных сеток
Одной из основных и наиболее трудоемких задач, решаемых при разработке параллельных алгоритмов, является проблема балансировки загрузки. Справедливо утверждение, что увеличение числа процессоров, между которыми распределена работа, уменьшает время решения многих задач (до некоторого числа процессоров). Однако, в случае использования систем с распределенной памятью, распределение работы между процессорами приводит к необходимости передачи между ними данных, что замедляет вычисления. Распределение вычислительной нагрузки между процессорами систем с общей памятью в большинстве случаев также представляет собой сложную задачу, так как зачастую ее наиболее эффективное решение основывается на знании архитектуры и технических характеристик конкретного вычислительного комплекса. При этом распределение работы может выполняться на самом низком уровне (например, параллельное выполнение витков циклов). В данной работе в параллельных алгоритмах для SMP и МРР систем применяются одинаковые методы деления расчетной области на параллельно обрабатываемые части, т.е. балансировки загрузки. Вариант распараллеливания для SMP систем на нижнем уровне некоторого последовательного алгоритма не рассматривается, так как не представляет методологического значения.
Поэтому в данном разделе для простоты будем считать, что распределение вычислительной нагрузки выполняется между процессорами систем с распределенной памятью или вычислительных кластеров.
Предварительная теоретическая оценка эффективности параллельных алгоритмов и последующая оценка эффективности программного обеспечения обычно выполняется с использованием понятий эффективности и ускорения параллельных алгоритмов. Ускорением параллельного алгоритма (SP) называют отношение времени выполнения алгоритма на одном процессоре ко времени выполнения алгоритма на системе из Р процессоров. Эффективностью параллельного алгоритма (ЕР) называют отношение его ускорения к числу процессоров, на котором это ускорение получено:
Очевидно, что в теории наилучшие значения Sp и Ер будут равны, соответственно, Р и 1. На практике иногда встречаются ситуации, когда при распараллеливании какого-либо алгоритма.Как правило, это говорит о выборе неоптимального последовательного алгоритма или его неэффективной программной реализации. В случае исключения возможности таких эффектов на системе из Р процессоров ту или иную задачу нельзя решить в Р раз быстрее, чем на однопроцессорной системе. Это объясняется следующими факторами: практически никакой параллельный алгоритм не позволяет на всех своих этапах эффективно использовать все процессоры системы; в любом параллельном алгоритме есть дополнительные затраты времени на обмен данными между процессорами; параллельный алгоритм всегда содержит некоторое количество дополнительных действий, связанных с управлением параллельной программой и синхронизацией ее частей. Согласно закону Амдаля [43], в общем виде ускорение, достигаемое на Р процессорах, может быть записано следующим образом: Т где 7 - время выполнения алгоритма на одном процессоре, td - общее время подготовки данных (синхронизация частей, обмен сообщениями между процессорами и т.д.), а - доля операций алгоритма, выполняемых в последовательном режиме. Очевидно, что эффективность и ускорение параллельного алгоритма напрямую зависят от качества балансировки загрузки. При фиксированном числе процессоров работу между ними можно распределить по-разному. В связи с этим встает задача определения такого распределения, при котором: все процессоры выполняют примерно одинаковый объем работы -загружены равномерно; объем передаваемых данных минимизирован. Несложно убедиться, что для многих задач эти требования являются противоречивыми. В общем случае, параллельную программу можно представить в виде некоторого взвешенного графа, вершины которого представляют собой элементарные задания, каждое из которых может быть выполнено любым процессором, а ребра - наличие связей между заданиями. При этом вес каждой вершины выбирается пропорциональным времени выполнения соответствующего задания, а веса ребер - пропорциональными объему передаваемых между заданиями данных. Таким образом, проблема балансировки загрузки сводится к задаче разрезания графа на заданное число частей так, чтобы суммарный вес разрезанных ребер был минимальным, а суммарные веса вершин, входящих в разрезанные части, примерно равны. Минимизация общего веса разрезанных ребер не всегда приносит наилучший результат. Например, при передаче большого количества коротких сообщений предпочтительнее минимизировать число разрезанных ребер, поскольку основное время при передаче короткого сообщения тратится на инициализацию самого процесса передачи данных. Другой возможностью является минимизация максимального трафика между парой процессоров. Также не всегда следует стремиться к равномерному распределению работ. Во многих случаях полезнее минимизировать объем работы, пришедшейся на самый загруженный процессор. Передачу данных целесообразно рассматривать как один из видов работы, суммируя общий объем выполняемой процессором работы с общим объемом передаваемых/принимаемых им данных, умноженным на подходящий коэффициент. При таком подходе задача сводится к равномерному распределению получившейся «совокупной» работы. Различают статическую и динамическую балансировки загрузки. Статическая балансировка выполняется перед началом вычислений. При этом делаются определенные предположения относительно времени выполнения частей программы (например, при решении уравнений газовой динамики с помощью явных однородных разностных схем предполагается, что время обработки одинаково для всех узлов разностной сетки) и объема передаваемых между процессорами данных. Динамическая балансировка загрузки используется, когда время выполнения различных частей программы или эффективная производительность процессорных узлов изменяется в ходе решения задачи. Простейшим алгоритмом динамической балансировки загрузки является метод «коллективного решения» [43].
Параллельный алгоритм для систем с общей памятью
В настоящее время пиковая производительность симметричных мультипроцессорных систем значительно уступает лидерам по данному показателю среди систем с распределенной памятью и в ближайшем будущем эта ситуация, скорее всего, не изменится. Однако на сегодняшний день существует широкий класс задач, для которых из-за сильной зависимости по данным до сих пор не найдены эффективные параллельные алгоритмы для МРР систем. Кроме того, современные вычислительные кластеры все чаще конструируются на основе объединения мультипроцессоров. В этом случае при разработке параллельных алгоритмов и программ может быть использован гибридный подход: программа представляет систему взаимодействующих между собой процессов, каждый из которых выполняется на отдельном мультипроцессоре и может в свою очередь порождать систему легковесных вычислительных процессов. Поэтому разработка эффективных параллельных алгоритмов моделирования для SMP систем имеет большое практическое значение.
Программирование для мультипроцессоров обычно выполняется в рамках модели параллелизма по управлению (в западной литературе используется другое название - модель разделения работы, work-sharing model). При этом в качестве модели выполнения используется модель общей памяти, в которой параллельная программа представляет собой систему нитей, взаимодействующих посредством общих переменных и примитивов синхронизации. Нить (по-английски "thread") - это легковесный процесс, имеющий с другими нитями общие ресурсы, включая общую оперативную память. Основная идея модели параллелизма по управлению заключается в расширении языка программирования специальными управляющими конструкциями - параллельными циклами и параллельными секциями. Создание и уничтожение нитей, распределение между ними витков параллельных циклов или параллельных секций (например, вызов процедур) автоматически выполняется компилятором. В настоящее время при разработке параллельных программ для SMP-систем чаще всего используются интерфейс POSIX [36] и технология программирования ОрепМР [15, 73]. POSIX-интерфейс организации нитей широко поддерживается практически на всех UNIX-системах. Согласно терминологии POSIX, любой UNIX-процесс состоит из нескольких нитей управления, которые имеют общее адресное пространство, но различные потоки команд и раздельные стеки. На практике применение этого интерфейса сопряжено с рядом серьезных проблем, так как работа с процессами выполняется на низком уровне, и механизм нитей изначально разрабатывался не для целей организации параллелизма. ОрепМР - это интерфейс прикладной программы, расширяющий последовательный язык программирования набором директив компилятора, вызовов функций библиотеки поддержки выполнения и переменных среды. Программа начинает свое выполнение как один процесс, называемый главной нитью. Главная нить выполняется последовательно, пока не встретится первая параллельная область программы, которая определяется парой директив. При входе в параллельную область главная нить порождает некоторое число подчиненных ей нитей, которые вместе с ней образуют текущую группу нитей. Все операторы программы, находящиеся в параллельной конструкции, включая и вызываемые изнутри нее процедуры, выполняются всеми нитями текущей группы параллельно, пока не произойдет выход из параллельной области или встретится одна из конструкций распределения работы. При выходе из параллельной конструкции все порожденные на входе в нее нити сливаются с главной нитью, которая и продолжает дальнейшее выполнение. В программе может быть произвольное число параллельных областей, причем допускается их вложенность. При параллельной области можно указать классы используемых в ней переменных (общие или приватные). Имеются директивы высокоуровневой синхронизации (критические секции, барьер и т.д.).
На первый взгляд распараллеливание какого-либо алгоритма с помощью данных средств выглядит достаточно привлекательно и просто. В общем случае оно заключается в добавлении управляющих конструкций и указании классов используемых переменных и обрабатываемых массивов в код последовательной программы. Но на практике разработка эффективного параллельного алгоритма для таких систем представляет очень сложную задачу. Во многом это связано с тем, что порождение параллельных процессов и их распределение по процессорам выполняется автоматически. В этом случае разработчику крайне трудно найти узкие места алгоритма и понять причины их возникновения. Помимо этого многое зависит от архитектуры конкретной вычислительной системы, ее текущих настроек и прочих обстоятельств, весьма отдаленно связанных непосредственно с разработкой алгоритма. Основной сложностью при разработке и реализации параллельных алгоритмов для мультипроцессоров является решение проблем одновременного доступа к данным и обработки критических секций. Критическими секциями называются те места алгоритма, где возможна одновременная модификациями несколькими нитями одной и той же ячейки памяти, что практически со 100% вероятностью приводит к возникновению ошибок в ходе выполнения соответствующей программы. Приведенные выше средства разработки параллельных программ позволяют решить эту проблему с помощью соответствующих директив в коде программы (ОрепМР) или с помощью использования семафоров (POSIX). Однако на практике необходимость частой обработки таких ситуаций сводит эффективность распараллеливания практически к нулю. Проблема одновременного доступа к данным усугубляется тем, что при одновременной работе несколькими нитями с одним блоком оперативной памяти должна поддерживаться когерентность кэшей процессоров, на которых эти нити выполняются. В современных системах с общей памятью когерентность кэшей процессоров поддерживается на аппаратном уровне, но отслеживание таких ситуаций так же негативно влияет на эффективность распараллеливания. Решением этих проблем может быть разработка алгоритма, в котором будут отсутствовать критические секции и будет сведена к минимуму возможность одновременной работы параллельных вычислительных процессов с пересекающимися областями оперативной памяти.
