ЖУРНАЛ СТА 3/2009

РАЗ РА БОТ КИ / НАУ ЧНЫЕ ИССЛ Е ДОВ АНИЯ 76 www.cta.ru CTA 3/2009 фиком обмена между узлами вычисли- тельной системы, и его последователь- ное выполнение позволяет уменьшить время решения задачи до трёх раз по сравнению с классическим алгоритмом имитации отжига при сохранении, а во многих случаях даже при улучшении ка- чества получаемых расписаний. Парал- лельный алгоритм является масштаби- руемым по отношению к числу вычис- лительных узлов в системе и при реализации на рассматриваемой вычис- лительной системе позволяет достичь ускорения, близкого к теоретически воз- можному, получаемому в соответствии с законом Амдала. Распознавание аномального поведения динамических систем Распознавание аномального поведе- ния динамических систем производи- лось согласно алгоритму, основой кото- рого является разметка анализируемой фазовой траектории поведения системы аксиомами. Под аксиомой понимается бинарная функция, определённая в точке и некоторой её окрестности на фа- зовой траектории. Определение ано- мального поведения в работе наблюдае- мой системы ведётся не путём поиска эталонных траекторий в наблюдаемой фазовой траектории, а путём поиска раз- меток эталонных траекторий в ряду раз- метки. Это позволяет повысить устойчи- вость алгоритма распознавания к иска- жениям эталонных траекторий по времени и амплитуде в анализируемой фазовой траектории системы по сравне- нию с другими известными методами. Задача построения алгоритма распозна- вания нештатных ситуаций может быть сформулирована как задача обучения по прецедентам. В работе [3] предложен ал- горитм решения этой задачи. Однако для многих практических задач время обуче- ния является неприемлемо большим. Численные эксперименты показали, что при параллельной реализации алгоритма обучения на рассматриваемой вычисли- тельной системе удаётся добиться близ- кого к линейному ускорению обучения относительно числа используемых вы- числительных узлов. Реализация управляемого ковариационного адаптивного формирователя диаграмм Рассматривается задача формирования диаграммы направленности, встречаю- щаяся, например, в радиолокации или гидроакустике. Базовые шаги обработки информации включают временную сег- ментацию ряда, перекрытие и работу бы- строго преобразования Фурье (БПФ), формирование управляющей ковариа- ционной матрицы, инверсию ковариа- ционной матрицы, использующей факторизацию Холецкого, оценку адап- тивных векторов управления, формиро- вание адаптивных лучей во временной области, удаление перекрытия и конка- тенацию сегментов, чтобы сформировать непрерывную лучевую последователь- ность во времени. Предположим, что М – число при- ёмников, N – число отсчётов, F d – частота дискретизации. Для выполне- ния дискретного БПФ с двойным пе- рекрытием необходимо выполнить 10 . М . N . log N операций за время Т = N / F d . Необходимое быстродействие для БПФ составляет 10 . М . log N . F d . Необходимое быстродействие для на- копления матриц составляет 4 . М . М . F d . Необходимое быстродействие для об- ращения матриц один раз за М тактов составляет 4 . М . М . F d . Необходимое быстродействие для вы- числения статистик составляет 4 . М . М . F d . Суммарное быстродействие составляет М . F d . (10 . log N + 12 М ). Если принять М = 2000, N = 16 384, F d = 5000 Гц, то необходимое быстродей- ствие вычислительной системы для этой задачи должно составить 241,4 GFLOPS. Задача такой размерности решается предлагаемой вычислительной системой менее чем за 1 с, то есть с запасом для ре- шения задач вторичной обработки. З АКЛЮЧЕНИЕ В заключение можно отметить, что рассматриваемая масштабируемая уни- версальная мультипроцессорная система будет эффективно применяться для ре- шения наиболее трудных с вычислитель- ной точки зрения задач, требующих больших объёмов памяти и производи- тельности (моделирование естественных процессов в различных областях знаний, опережающее моделирование в про- изводственных АСУ, задачи реального масштаба времени в таких сферах при- менения, как радиолокация, гидроаку- стика, мониторинг космической обста- новки и т.д.). Система УМС обладает пониженным тепловыделением и может использо- ваться в производственных помещениях без предъявления каких-либо требова- ний к их обустройству. ● Л ИТЕРАТУРА 1. Немнюгин С., Стесик О. Параллельное про- граммирование для многопроцессорных вычислительных систем. – СПб. : БХВ-Пе- тербург, 2002. 2. Калашников А.В., Костенко В.А. Парал- лельный алгоритм имитации отжига для по- строения многопроцессорных расписаний // Известия РАН. Теория и системы управле- ния. – 2008. – № 3. – С. 101-110. 3. Костенко В.А., Коваленко Д.С. Метод по- строения алгоритмов распознавания, осно- ванных на идеях аксиоматического подхода // Научная сессия МИФИ-2007. IX Всерос- сийская научно-техническая конференция «Нейроинформатика-2007»: сб. трудов. – М. : МИФИ, 2009. Авторы– сотрудники компанииПРОСОФТ иОАО«НИИВКим. М.А. Карцева» Телефон: (495) 330-0929 E-mail: postoffice@niivk.ru Рис. 3. Фрагмент протокола вычислений * Total Execution 1 1944.32 [100.00%] 1953.88 [100.0%] *********************************************************************************** * *********************************************************************************** * Processor 12 Count CPU Time Wallclock Time *********************************************************************************** * ACCIF_EXCHANGE 17 0.00 [ 0.00%] 0.00 [ 0.0%] * File IO 184 7.79 [ 0.40%] 8.27 [ 0.4%] * Linear Solver 379 1772.79 [ 91.20%] 1773.98 [ 90.7%] * *********************************************************************************** * Total MPI Timings Count Total CPU Time Average WCT *********************************************************************************** * ACCIF_EXCHANGE 214 0.00 0.00 * MPI Barrier 15 0.82 [ 0.04%] 0.82 [ 0.0%] * MPI Communication 84782 109.91 [ 5.65%] 109.92 [ 5.6%] * Other 1 46.90 [ 2.41%] 55.15 [ 2.8%] * Thermochemistry 49 5.44 [ 0.28%] 5.45 [ 0.2%] *********************************************************************************** * Total Execution 1 1943.93 [100.00%] 1953.88 [100.0%] *********************************************************************************** * File IO 2208 141.88 14.26 * Linear Solver 4548 19904.51 1698.89 * MPI Barrier 180 17.55 1.54 * MPI Communication 988192 2145.46 180.32 * Other 12 543.93 52.66 * Thermochemistry 588 67.28 5.94 *********************************************************************************** * Total Execution 12 22823.97 1953.90 *********************************************************************************** © СТА-ПРЕСС