«2 ТРУДЫ ИНФОРМАЦИОННЫЕ Кольского научного центра РАН ТЕХНОЛОГИИ 5/2013 (18) выпуск 4 СОДЕРЖАНИЕ Стр. Введение.. 9 В.А. Путилов Средства информационного мониторинга и А.В. Маслобоев моделирования глобальной безопасности ...»

Работа выполнена при финансовой поддержке РФФИ (проекты №№ 11-08-00641, 12-07-00550-а, 12-07-00689-а, 13-07-00318-а), ОНИТ РАН (проект 2.3 в рамках текущей Программы фундаментальных научных исследований) и Президиума РАН (проект 4. Программы № 16).

набора пересекающихся интервалов.

Данная работа посвящена рассмотрению программной реализации алгоритмов логико-вероятностного анализа таких систем с использованием методов АК [8, 9]. Эти методы базируются на представленных ниже теоремах о метрических свойствах АК-объектов.

Теорема 1. Мера некоторой компоненты С-кортежа равна сумме мер значений, формирующих эти компоненту.

Например, пусть в пространстве X1 X2, где X1 = {a, b, c, d}, X2 = {1, 2, 3, 4}, задан С-кортеж C1 = [{a,b,c}{1, 2, 3}]. Обозначим первую компоненту этого С-кортежа как x1, а вторую – x2. Тогда (x1) = (a) + (b) + (c), а (x2) = (1) + (2) + (3).

Теорема 2. Если каждая компонента C-кортежа имеет конечную меру, то мерой C-кортежа является произведение мер его компонент.

Пользуясь результатами предыдущего примера вычислим меру (С1):

(С1) = (x1) * (x2).

Из представленных теорем непосредственно следует.

Теорема 3. Мера ортогональной C-системы равна сумме мер содержащихся в ней C-кортежей.

Из теоремы 3 вытекает, что мера произвольной D-системы может быть вычислена, если преобразовать ее дискретное представление в ортогональную C-систему. Для произвольной C-системы, используя соотношения АК, можно разработать алгоритм преобразования такой C-системы в ортогональную. Но во многих случаях проще вычислить дополнение этой C-системы, преобразовать полученную D-систему в ортогональную C-систему и вычислить меру исходной C-системы, используя соотношение:

где (C) – мера исходной C-системы, (U) – мера универсума, ( C ) – мера АК-объекта, дополнительного к исходному.

Мера универсума для множества атрибутов {X1, X2,..., Xn} вычисляется как произведение (X1) (X2)... (Xn).

Отметим следующие очевидные свойства АК-объектов, погруженных в вероятностное пространство или в любое другое нормированное пространство, в котором мера каждого атрибута равна 1:

1) мера полной компоненты в C-кортежах и C-системах равна 1;

2) мера любого частного универсума равна 1;

3) мера любого АК-объекта есть число в интервале [0, 1];

4) мера пустого АК-объекта равна 0;

5) для АК-объекта A мера его дополнения равна 1 – (A);

6) для пары (A, B) АК-объектов (A B) = (A) + (B) – (A B);

7) в любом АК-объекте после элементаризации мера каждой компоненты равна сумме мер соответствующих квантов, содержащихся в этой компоненте [4].

Далее рассматриваются особенности программной реализации алгоритмов логико-вероятностного анализа в АК.

Программная реализация разработанных алгоритмов Алгоритм расчета вероятностной меры для компоненты С-системы.

Блок-схема данного алгоритма приведена на рис. 1.

Рис. 1. Блок-схема алгоритма расчета вероятностной меры Пример 1. Пусть есть некоторый домен D = {1,2,3,4,5,6} и для его элементов определено вероятностное распределение.

Вероятностное распределение для значений домена D Необходимо посчитать вероятность для компонент следующего С-кортежа С1= [{a,b,c} {a,c,e} {a,b,c,d,e,f}]. Первую компоненту обозначим x1={a,b,c}, вторую - x2= {a,c,e}, третью x3 = {a,b,c,d,e,f}, соответственно.

Тогда: P(x1)=p[1]+p[2]+p[3]=0.1+0.1+0.15=0.35;

P(x2)=p[1]+p[3]+p[5]=0.1+0.15+0.2=0.45;

P(x3)=p[1]+p[2]+p[3]+p[4]+p[5]+p[6]=0.1+0.1+0.15+0.15+0.2+0.2=1.

Рассмотрим по шагам обработку элемента x2.

Элементы, содержащиеся в x2, могут быть представлены в виде битового вектора b = (1, 0, 1, 0, 1, 0). Элементами, содержащимися в компоненте, считаются те элементы, для которых соответствующий бит установлен в единицу. В процессе перебора идёт просмотр всех значений битового вектора с обработкой тех, для которых установлен необходимый бит.

Последовательность действий алгоритма тогда будет выглядеть таким образом: P = 0. Номер элемента Выход из цикла, результат: P = 0.45.

Алгоритм расчета вероятностной меры для всей С-системы.

На рис 2. представлена блок-схема алгоритма подсчета вероятностной меры для всей С-системы.

Назначением алгоритма является определение вероятности, которая соответствует некоторому событию, описанному с помощью некоторой ортогональной С-системы Выполнение алгоритма состоит из последовательного вычисления вероятностей всех включенных в систему строк. Конечный результат равен сумме вероятностей всех строк. Вероятность каждой строки, в свою очередь, равна произведению вероятностей всех входящих в неё элементов.

Пример 2. Пусть есть некоторая система A, определённая в схеме U = D1 D2, для которой определено вероятностное пространство (табл. 1 и 2).

Вероятностное распределение для значений домена D Вероятность каждой компоненты будет равна:

Вероятность всей системы тогда будет равна:

(0.1*0.35)+(0.25*0.6)+(0.55*0.4) = 0.405.

Результирующая вероятность PS = Рис. 2. Проведение процедуры ЛВА над отдельной С-системой Пример расчета надежности системы со многими состояниями С помощью представленного ранее алгоритма можно выполнять сравнение надёжности различных вариантов конфигурации технической системы и осуществлять выбор между несколькими вариантами действий.

';

Очевидно, что каждое множество состояний системы, которым соответствует некоторый выбор может быть представлен с помощью АК-объекта, в котором в качестве строк будут некоторые случаи или множества случаев, а в качестве столбцов – координаты ситуационного вектора.

Каждой такой системе сопоставляется некоторая вероятность, вычисляемая методами логико-вероятностного анализа и означающая “предпочтительность” прецедента (варианта выбора).

Процедура выбора между предоставленными вариантами тогда будет следующей:

1 Выделение случаев и построение на их основе С-систем, описывающие множества случаев, которым они соответствуют.

2 Определение числовых значений, соответствующих степени истинности каждого значения лингвистических переменных.

3 Процедура логико-вероятностного анализа для каждой системы 4 Сравнение получившихся значений; выбор прецедента с максимальным значением.

Рассмотрим летательный аппарат [10], состояния которого описаны некоторым вектором, составленным из переменных, каждая из которых определена на конечном множестве значений (табл. 3).

Пусть каждому значению каждой переменной соответствует некоторое значение вероятности, причем, все значения переменной образуют полную группу событий (табл. 4).

Вероятностные пространства для лингвистических переменных Используем имеющиеся данные, чтобы осуществить выбор между вариантами d1 и d2 и сравнить получившиеся в результате значения.

Предпочтительным будет вариант с наибольшим значением получившейся вероятности.

В табл. 5 представлены расчеты, обосновывающие выбор в пользу прецедента d1, на основе представленных ранее алгоритмов ЛВА.

Использование метода ЛВА при анализе прецедентов Основные классы и методы Программная реализация использует библиотеку созданную ранее.

Библиотека предоставляет базовые операции над АК-объектами и включает в себя следующие возможности и элементы [11]:

cтруктуры данных для хранения АК-объектов;

алгоритмы, реализующие операции над АК-объектами;

возможность чтения и записи используемых данных в xml-файл.

Основные классы библиотеки:

akDomain, akIDomain — классы для представления АК-домена;

akAttribute — класс для представления АК-атрибута;

akComponent — класс для представления компоненты;

akColumn — контейнер для хранения значений столбца некоторой системы;

akScheme — класс для представления АК-схемы;

akCSystem, akDSystem, akISystem — классы для хранения АК-систем;

akMain — контейнер, используемый для хранения всех используемых в программе АК-объектов.

Методы библиотеки:

cоздание, удаление, редактирование используемых в библиотеке классов;

операции объединения, пересечения, дополнения, минимализации АКсистем;

операция ортогонализации АК-систем;

обработка сложных составных операций над АК-объектами.

Для реализации методов ЛВА и хранения значения вероятностей событий были созданы классы, позволяющие осуществлять хранение и обработку метрических (вероятностных) характеристик АК-объектов. Диаграмма классов разработанного программного модуля представлена на рис. 3.

Рис. 3. Диаграмма классов разработанного программного модуля Основные классы разработанной библиотеки:

AttributeChancesContainer — контейнер, описывающий вероятности одной отдельной системы событий. Каждый экземпляр класса сопоставлен некому экземпляру класса akAttribute;

akSchemeChancesContainer— контейнер, соответствующий некоторому вероятностному распределению и содержащий в себе несколько экземпляров AttributeChancesContainer. Каждому экземпляру класса сопоставлен экземпляр akScheme. Содержит в себе непосредственно алгоритм подсчёта вероятности некоторой C-системы для заданного вероятностного распределения;

ChancesMetaContainer — контейнер, хранящий в себе все экземпляры akSchemeChancesContainer. Обычно существует только один экземпляр контейнера, который соответствует экземпляру класса akMain.

Также был разработан класс akIntervalBounds. Класс содержит в себе основные методы работы с интервальными доменами, также его цель состоит в хранении всех взаимоотношений между интервальными АК-объектами: класс хранит все домены и атрибуты, получающиеся при квантовании. Так как при квантовании одного и того же домена или атрибута получаются всегда идентичные домены/атрибуты, это предоставляет возможность вместо создания новых объектов использовать старые. Описание соответствий реализовано с помощью STL-контейнера «map», что позволяет быстро находить потенциально возможные для повторного использования АК-объекты или же убеждаться в факте их отсутствия.

COM-интерфейсы, разработанного модуля Система допускает возможность использования своих функций внешними программами посредством встроенных COM-интерфейсов.

Допускается, что внешняя программа-клиент может формировать XMLфайлы с данными о вероятностных пространствах и используемых АК-объектах, или знает об их расположении и содержании.

Интерфейс AKAutomation Интерфейс AKAutomation является объектом OLE автоматизации и предоставляет функции работы с АК-объектами и ЛВА в общем виде.

Взаимодействие с интерфейсом осуществляется с помощью трёх основных методов:

OpenAKFile(BSTR filename) — является командой серверу открыть файл с описанием используемых АК-объектов, расположенный по адресу filename;

OpenChancesFile(BSTR filename) — является командой серверу открыть файл с описанием используемых вероятностных пространств, расположенный по адресу filename;

ProcessSystem(BSTR SystemName, BSTR ProbabilitySpaceName) — команда серверу произвести вероятностный анализ системы с именем SystemName в вероятностном пространстве с названием ProbabilitySpaceName.

Интерфейс AKDetailedAutomation Интерфейс AKDetailedAutomation также является объектом OLE автоматизации и предоставляет функции работы с АК-объектами и ЛВА.

Взаимодействие осуществляется с помощью следующих функций:

NewFile() — создать новый пустой документ на сервере;

CreateDomain(BSTR name, long domtype) — создаёт домен с именем name, тип домена передаётся в параметре domtype;

AddElementToDomain(BSTR domname, VARIANT element) — добавляет в домен с названием domname элемент element, так как домены могут содержать элементы разных типов данных, передача с помощью встроенного типа Variant;

CreateAttribute(BSTR name, BSTR domname) — создаёт атрибут с названием name над доменом с названием domname;

CreateScheme(BSTR name) — создаёт схему с названием name;

AddAttributeToScheme(BSTR schemename, BSTR attributename) — добавляет в схему с названием schemename атрибут с названием attributename.

CreateCSystem(BSTR name, BSTR scmname) — создаёт С-систему с названием name в схеме scmname;

CreateDSystem(BSTR name, BSTR scmname — создаёт D-систему с названием name в схеме scmname;

AddRowToSystem(BSTR systemname) — добавляет строку в систему;

SetComponent(BSTR systemname, long row, long column, BSTR bitset) — устанавливает значение элемента столбца column строки row системы systemname в значение битового массива, переданном в строке bitset;

DeleteDomain(BSTR name) — удаляет домен name;

DeleteAttribute(BSTR name) — удаляет атрибут name;

DeleteScheme(BSTR name) — удаляет схему name;

DeleteSystem(BSTR name) — удаляет систему name;

NewOperation(BSTR expr, BSTR result) — осуществляет выполнение выражения, описанного с помощью строки expr, записывает результат в систему result;

CreateProbabilitySpace(BSTR name, BSTR schemename) — создаёт вероятностное пространство с именем name над схемой schemename;

SetChance(BSTR ProbabilitySpaceName, BSTR AttributeName, int Element, double Value) — в вероятностном пространстве ProbabilitySpaceName в атрибуте AttributeName присваивает элементу с номером Element значение Value;

ProcessSystem(BSTR SystemName, BSTR spacename) — осуществляет процедуру ЛВА над системой SystemName с помощью вероятностного пространства spacename.

Пользовательский интерфейс Интерфейс приложения представляет собой оконное приложение с возможностями проводить различные операции с АК-объектами (рис. 4 а,б).

В ходе работы над приложением в интерфейс были добавлены следующие возможности (рис. 5):

cопоставление элементам доменов значений вероятностей;

логико-вероятностный анализ событий, представленных С-системами;

квантование интервальных доменов.

Рис. 4а. Вкладки для работы с атрибутами, схемами и системами Рис. 4б. Вкладки для работы с атрибутами, схемами и системами Для работы с вероятностными распределениями предусмотрена отдельная вкладка в главном окне. Вкладка содержит кнопки для создания и удаления вероятностного пространства, кнопки для сохранения и загрузки вероятностных пространств из файла, список выбора вероятностного пространства, список выбора атрибута выбранного вероятностного пространства и таблицу для редактирования значений вероятностей.

Рис. 5. Вкладка для работы с вероятностными распределениями Логико-вероятностный анализ систем осуществляется в отдельной вкладке главного окна. Вкладка содержит список для выбора схемы, в которой будут находиться системы и вероятностные пространства, списки для выбора систем, кнопку для проведения вероятностной оценки систем.

Рис. 6. Вкладка для проведения вероятностного анализа Из рис. 6 видно, что одну и ту же С-систему можно погрузить в различные вероятностные пространства. С другой стороны, созданную вероятностную схему можно использовать для расчета нескольких С-систем, что обеспечивает поддержку многовариантных расчетов.

Заключение В процессе работы над приложением выполнены следующие задачи:

разработаны и реализованы классы для представления вероятностей систем, узлы которых могут находиться во многих состояниях;

реализован алгоритм квантования доменов, значения которых заданы как система пересекающихся интервалов;

разработан и запрограммирован алгоритм пересчёта компонент АК-объектов с учётом квантования доменов;

реализованы алгоритмы унифицированного метода расчёта надёжностей структурно-сложных систем;

cоздан эргономичный пользовательский интерфейс, позволяющий использовать вышеперечисленные возможности;

разработан COM-интерфейс для доступа к функциям программы из внешних приложений.

Таким образом, разработанная система может быть использована как самостоятельно, так и в качестве внешнего программного модуля (сервера), предоставляющего функции работы с АК-объектами и методы ЛВА для других программных приложений.

Литература 1. Рябинин, И.А. Надежность и безопасность структурно-сложных систем. / И.А. Рябинин. – СПб., Политехника, 2000. – 248 с.

2. Рябинин, И.А. Логико-вероятностные методы исследования надежности структурно-сложных систем. / И. А. Рябинин, Г. Н.Черкесов. – М,. Радио и связь, 1981. – 264 с.

3. Соложенцев, Е.Д. Сценарное логико-вероятностное управление риском в бизнесе и технике / Е.Д. Соложенцев. – СПб., Издательский дом "Бизнеспресса", 2004. – 432 с.

4. Кулик, Б.А. Алгебраический подход к интеллектуальной обработке данных и знаний / Б.А. Кулик, А.А. Зуенко, А.Я. Фридман. – СПб.: Изд-во Политехн.

ун-та, 2010. – 235 с.

5. Зуенко, А.А. Матрицеподобные вычисления в задачах удовлетворения ограничений /А.А. Зуенко // Шестая Всероссийская мультиконференция по проблемам управления, 30 сентября – 5 октября 2013 г., г. Геленджик, с. Дивноморское: материалы мультиконференции в 4 т. – Ростов-на-Дону: Изд-во Южного федерального университета, 2013. -Т.1. – C.30-34.

6. Зуенко, А.А. Реализация комбинированных методов логико-семантического анализа с использованием алгебры кортежей / А.А. Зуенко, Б.А. Кулик, А.Я. Фридман // Тринадцатая национальная конференция по искусственному интеллекту с международным участием, 16-20 октября 2012г., г. Белгород:

труды конференции. - Белгород: Изд-во БГТУ, 2012. -Т.2. - С.67-75.

7. Кулик, Б.А. Вероятностная логика на основе алгебры кортежей. / Б. А. Кулик // Известия РАН. Теория и системы управления. 2007. – № 1. – С.118-127.

8. Kulik, B. Modified Reasoning by Means of N-Tuple Algebra / B. Kulik, A. Zuenko, A. Fridman // Pattern Recognition and Information Processing (PRIP'2011): Proceedings of the 11th International Conference, 18-20 May, Minsk, Republic of Belarus). – Minsk: BSUIR, 2011. – P.271-274.

9. Kulik, B. Logical Analysis of Intelligence Systems by Algebraic Method / B. Kulik, A. Fridman, A. Zuenko // Cybernetics and Systems 2010: Proceedings of Twentieth European Meeting on Cybernetics and Systems Research (EMCSR 2010). - Vienna, Austria, 2010. – P.198-203.

10. Федунов, Б.Е. Вывод по прецеденту в базах знаний бортовых интеллектуальных систем / Б.Е. Федунов, М.Д. Прохоров // Искусственный интеллект и принятие решений, 2010. – Вып. 3. – С.63-72.

11. Зуенко, А.А. Реализация библиотеки АК-объектов / А.А. Зуенко, С.В. Баженов // Труды Кольского научного центра РАН. Информационные технологии. – Вып. 3. –4/2012(11). - Апатиты: Изд-во КНЦ РАН, 2012. –С.207-217.

Сведения об авторе Зуенко Александр Анатольевич - к.т.н, научный сотрудник, е-mail: [email protected] Alexander A. Zouenko - Ph.D. (Tech. Sci.), Researcher УДК 004. С.С. Ковалёв, М.Г. Шишаев ФГБУН Институт информатики и математического моделирования технологических процессов

КНЦ РАН

Кольский филиал ПетрГУ

ИДЕНТИФИКАЦИЯ СПАМ-РАССЫЛОК НА ОСНОВЕ МАРШРУТНОЙ

ИНФОРМАЦИИ СООБЩЕНИЙ

Аннотация В статье предложена концепция идентификации источников рассылок почтового спама в сети Интернет (ботнетов), с помощью кластеризации множества получаемых сообщений, на основе содержащейся в них маршрутной информации. Дано описание используемой меры сходства объектов и алгоритма кластеризации и обоснована их применимость в контексте поставленной задачи.

Ключевые слова:

кластеризация, e-mail, спам, меры сходства, информационная безопасность.

S.S. Kovalev, M.G. Shishaev

IDENTIFICATION OF SPAM CAMPAIGNS ON THE BASIS OF MESSAGES

ROUTING INFORMATION

Abstract This article proposes the method for identification of sources of email spam campaigns (botnets) by means of clustering the set of received messages based on their routing information. There were described similarity measure and clustering algorithm which applicable for this task.

Key words:

сlustering, e-mail, spam, similarity measures, information security.

Введение Будучи одним из самых простых и дешёвых способов массового распространения информации, спам является как мощным маркетинговым средством, так и излюбленным инструментом мошенников и киберпреступников. Интернет-сервисы, в первую очередь электронная почта, предоставляя широчайшие возможности для коммуникаций, давно являются привлекательной средой для распространения спама: по статистике, спам составляет от 60% до 80% почтового трафика [1, 2]. В лучшем случае спам оказывается неприятностью, отнимающей у человека время на его прочтение и удаление, однако он может быть причиной и куда более серьёзного ущерба.

Сейчас сервисы Интернет-коммуникаций активно используется в личной, рабочей и финансовой сфере жизни человека. Многие критически важные коммуникации в них осуществляются именно через электронную почту, что вызывает доверие к получаемой с её помощью информации и вынуждает обращать на неё повышенное внимание. Этим активно пользуются мошенники, рассылая сообщения, заставляющие пользователя непреднамеренно загружать вредоносное программное обеспечение, компрометировать свои личные данные или перечислять злоумышленникам денежные средства. Кроме того, спам наносит урон и владельцам почтовых сервисов, подрывая их репутацию и вынуждая их тратить большие ресурсы на защиту пользователей.

Задача фильтрации почтового спама не нова, однако статистика показывает, что существующие её решения не всегда эффективны. В последние годы отмечен бурный рост числа пользователей Интернет-сервисов [3], что создаёт благодатную почву для получения высоких прибылей от распространения спама. Этот факт мотивирует распространителей спама изобретать всё новые средства обхода существующих фильтров, провоцируя этим «гонку вооружений» между средствами распространения спама и средствами его блокировки.

Одним из главных и самых распространённых на сегодняшний день инструментов киберпреступников являются ботнеты – группы сетевых узлов, на которых скрытно функционирует программное обеспечение, объединяющее эти устройства в логическую сеть под управлением некоторого «командного центра» и использующее их ресурсы для выполнения различных задач. Сегодня ботнеты могут состоять из сотен тысяч заражённых вредоносным программным обеспечением обычных компьютеров [4], или мобильных устройств (смартфонов и планшетов), подключенных к сети Интернет [5-6]. Большие вычислительные ресурсы и распределённая структура ботнетов обеспечивают их «живучесть» при обнаружении и блокировке отдельных их членов, что делает их идеальным средством распространения спама и позволяет производить спамрассылки очень больших объёмов.

В этой работе предложена технология борьбы с почтовым спамом посредством идентификации ботнетов, используемых для его распространения.

Ключевая идея этой технологии заключается в определении принадлежности сетевых узлов-источников сообщений электронной почты к определённым ботнетам на основе анализа содержащейся в этих сообщениях маршрутной информации. Применение такой технологии позволит блокировать нежелательные и вредоносные сообщения, отправленные узлами ботнетов, повышая тем самым устойчивость спам-фильтра к попыткам его обхода.

Описание технологии Идея использования содержащейся в сообщениях электронной почты маршрутной информации для идентификации принадлежности их источников к определённому ботнету основана на том очевидном факте, что на всех узлах ботнета работает однотипное программное обеспечение, реализующее общие алгоритмы осуществления рассылок. Этот факт обусловливает наличие в маршрутной информации рассылаемых узлами ботнета сообщений общих характерных признаков. При этом вследствие того, что изменение инфраструктуры и логики работы ботнета является дорогостоящим и трудоемким процессом, такие признаки будут многократно повторяемы и неизменны в течение длительного времени, что даёт возможность их эффективного использования для автоматической идентификации этих ботнетов и фильтрации рассылаемых ими сообщений.

Предлагаемая технология идентификации ботнетов на основе маршрутной информации почтовых сообщений строится на решении трёх основных задач:

1. Подготовка исходных данных. Накапливается обучающая выборка – коллекция образцов почтовых сообщений, содержащая большое количество примеров, как спама, так и легитимных сообщений. Каждое сообщение из этой выборки представляется в виде вектора значений определённых характеристик, извлечённых из содержащейся в них маршрутной информации (характеристического вектора);

2. Кластеризация обучающей выборки. Производится кластеризация множества полученных характеристических векторов для обнаружения в обучающей выборке подмножеств образцов сообщений, имеющих схожую маршрутную информацию;

3. Идентификация ботнета. Полученные кластеры подвергаются анализу на предмет выявления среди них таких, которые содержат сообщения, потенциально исходящие от некоторого ботнета. Характеристики маршрутной информации образцов сообщений, составляющих найденные «ботнет-кластеры», в дальнейшем используются для блокировки рассылаемых посредством ботнетов сообщений.

Очевидно, что ключевой задачей, в наибольшей степени, влияющей на получаемый результат, является задача кластеризации обучающей выборки. Эта задача сводится к разбиению исходного множества объектов (образцов сообщений) на подмножества таким образом, что элементы одного подмножества существенно отличаются по некоторому набору свойств от элементов всех других подмножеств. Успешное решение задачи кластеризации основывается на решении двух основных проблем:

выбор способа определения меры сходства между объектами множества (метрики);

выбор алгоритма кластеризации.

Этот выбор критичен, поскольку непосредственно влияет на качество получаемого в результате кластеризации результата и зависит в первую очередь от природы используемых данных.

Природа используемых данных и мера сходства Объекты обучающей выборки представляют собой векторы значений характеристик, описывающих маршрутную информацию сообщения электронной почты. Используемые характеристики и типы их значений перечислены в табл.

Используемые характеристики и типы их значений Географическая принадлежность IP-адреса узла из первого Категориальный заголовка Received Наличие reverse DNS узла из первого заголовка Received Категориальный Максимальное время перехода между узлами маршрута Числовой Наличие узлов маршрута, принадлежащих абонентским Логический подсетям операторов связи Наличие узлов маршрута, которые являются открытыми Логический прокси-серверами Из табл. видно, что объекты пространства данных являются гетерогенными – представляют собой точки в многомерном пространстве данных с неоднородными измерениями, соответствующими характеристикам объекта.

Ключевой проблемой вычисления сходства между гетерогенными объектами данных является тот факт, что типы атрибутов различны по своей природе, обладают различными свойствами, и к ним не может быть применена единая метрика. Как следствие, возникает необходимость решения двух задач:

1. Определение используемой метрики для каждого типа характеристик и вычисление сходства пары объектов по каждой из характеристик отдельно.

2. Объединение полученных значений сходства объектов по каждой из характеристик в общее значение меры сходства объектов.

Метрика для каждого типа атрибутов может вычисляться различными способами в зависимости от специфики предметной области. Чтобы сделать возможным последующее объединение полученных значений сходства объектов по каждой из характеристик, необходимо чтобы эти значения лежали в одном диапазоне, то есть требуется нормализация области значений всех измерений пространства данных. Нормализация представляет собой отдельную проблему, особенно сложную в случае с категориальными измерениями.

В [7] авторы предложили метрику Value Difference Metric (VDM), которая учитывает информацию о классовой принадлежности объектов данных.

При использовании метрики VDM сходство значений атрибута считается тем больше, чем теснее их корреляция с заданным классом. Для значений x и y атрибута a эта метрика определяется как где С – число классов в рассматриваемой предметной области;

P(c|xa) – условная вероятность того, что при условии принадлежности объекта к классу c значение атрибута x будет равно a;

q – константа (обычно берётся равной 1 или 2).

Очевидно, что в контексте идентификации источников спама при вычислении сходства значений характеристик рассматриваемых классов будет два: «спам» и «не спам».

Общая мера сходства объектов будет определяться как где A, B – объекты данных;

t – компонент характеристического вектора.

Ключевое достоинство метрики VDM заключается в возможности объединить сходства объектов по каждому компоненту характеристического вектора без необходимости нормализации областей их значений, поскольку при вычислении значения меры сходства используется вероятностное представление корреляции с классами (в виде условной вероятности принадлежности объекта к классу). Кроме того, вычисление сходства компонентов характеристического вектора как степени тесноты корреляции с заданным классом обеспечивает единый смысл меры сходства для каждого компонента независимо от его типа.

Таким образом, метрика VDM решает проблемы вычисления сходства гетерогенных объектов данных и может быть использована для вычисления сходства маршрутной информации сообщений из обучающей выборки.

Метод кластеризации на основе поиска k-сетей Перед изложением предлагаемого алгоритма кластеризации, множества образцов сообщений из обучающей выборки, необходимо ввести следующие определения.

G = (V, E) – неориентированный граф;

V = {v1, v2, …, vn} – множество вершин в G;

E = {e1, e2, …, em} – множество рёбер в G;

|G| - количество вершин в G;

degG(v) – степень вершины v в G;

G[S] = (S, E S S) – подграф, индуцированный множеством вершин Определение 1. Подмножество вершин S V называют кликой, если все вершины в нём попарно смежные.

Определение 2. Подмножество вершин S V называют k-сетью (k-plex) [8], если degG[S](v) > |S| - k для любой вершины v из S.

Иными словами, любая вершина в k-сети является смежной всем, кроме k – 1 других вершин. Таким образом, 1-сеть является кликой, а при k > 1 – релаксацией клики. Так, граф, изображённый на рис. 1a является кликой, а на рис. 1b – 2-сетью.

Определение 3. Клика (k-сеть) является максимальной, если она не является подграфом другой клики (k-сети).

Для выявления в обучающей выборке подмножеств образцов сообщений со схожей маршрутной информацией требуется произвести кластеризацию исходного множество образцов сообщений таким образом, чтобы в результирующих кластерах попарное значение меры сходства любых его членов было наибольшим.

Добиться отыскания удовлетворяющих поставленным требованиям кластеров можно с помощью алгоритмов кластеризации, построенных на теории графов. В их основе лежит представление рассматриваемого множества объектов в виде графа с последующим извлечением из него подграфов, обладающих заданными характеристиками. Эти подграфы и будут представлять искомые кластеры.

Очевидным алгоритмом кластеризации с помощью графов, находящим удовлетворяющие поставленным условиям кластеры, является алгоритм на основе поиска клик:

1) Для всех образцов сообщений в обучающей выборке попарно вычисляется значение меры сходства маршрутной информации.

2) Множество образцов сообщений представляется в виде полного неориентированного взвешенного графа, в котором вершинами являются образцы сообщений, а веса рёбер между ними равны значению меры их сходства.

3) Из графа удаляются все рёбра, вес которых не достигает некоторого заданного порогового значения.

4) В оставшемся графе находятся максимальные клики, которые и будут являться искомыми кластерами.

Нахождение клик – идеальная ситуация, когда в найденных кластерах попарное значение меры сходства между любыми членами кластера не будет превышать заданного порогового значения. Однако на практике это требование может оказаться чрезмерно строгим и привести к обнаружению или очень малого количества групп, или большого количества групп, состоящих из очень маленького числа членов, которые будут неинформативны и бесполезны.

Во избежание такой ситуации требование поиска максимальных клик предлагается смягчить и вместо поиска максимальных клик предлагается использовать поиск k-сетей. Тогда будут найдены такие группы образцов сообщений, для любого члена которых сходство маршрутной информации со всеми остальными членами группы кроме k – 1 находится в пределах заданного порогового значения. Это предложение основано на том предположении, что если значение меры сходства маршрутной информации пары образцов сообщений не достигает заданного порогового значения, то при малых значениях k (k = 2, 3) косвенно их восприятие спама всё равно можно считать сходным на основании наличия большого числа общих схожих образцов. Такой подход позволит определять в обучающей выборке сообщений большие и информативные кластеры, характеристики которых потенциально могут описывать некоторый ботнет.

Поиск максимальных клик в графе – хорошо известная задача, одним из самых популярных алгоритмов решения которой является алгоритм БронаКербоша [9]. Для поиска максимальных k-сетей в графе может быть применён модифицированный алгоритм Брона-Кербоша, описанный в [10].

Заключение В данной работе предложена концепция идентификации ботнетовисточников рассылок почтового спама с помощью кластеризации обучающей выборки сообщений, на основе, содержащейся в них маршрутной информации.

Такой подход потенциально обеспечивает большую эффективность в сравнении с методами идентификации спама, основанными на рассмотрении собственно тела письма как объекта идентификации. Эта эффективность обусловлена тем фактом, что характеристики источника нежелательных рассылок существенно более стабильны во времени по сравнению с параметрами спам-корреспонденции как таковой.

В рамках работы были проанализированы и определены требования, к используемым для осуществления кластеризации способу вычисления меры сходства, между объектами и алгоритму кластеризации. В результате было предложено использование метрики VDM и алгоритма кластеризации на основе поиска k-сетей в графе как полностью удовлетворяющие предъявленным требованиям. В дальнейших исследованиях необходимо экспериментально оценить применимость предложенной технологии в реальных условиях и оценить достигаемую с её помощью эффективность блокировки рассылок спама. Также необходимо определить оптимальные значения k в алгоритме кластеризации на основе поиска k-сетей для достижения как можно более качественной кластеризации.

Литература 1. Спам во втором квартале 2013 г. - Режим доступа:

http://www.securelist.com/ru/analysis/208050806/Spam_vo_vtorom_kvartale_ 2. Спам в третьем квартале 2013 г. - Режим доступа:

http://www.securelist.com/ru/analysis/208050817/Spam_v_tretem_kvartale_ 3. Internet Usage Statistics. -Режим доступа: http://www.internetworldstats.com/stats.htm 4. The World’s Biggest Botnets. - Режим доступа:

http://www.darkreading.com/management/the-worlds-biggest-botnets/ 5. The Most Sophisticated Android Trojan. - Режим доступа:

http://www.securelist.com/en/blog/8106/The_most_sophisticated_Android_Trojan 6. В России нашли крупнейшую в мире сеть заражённых смартфонов на Android. - Режим доступа:

http://www.cnews.ru/top/2013/09/20/v_rossii_nashli_krupneyshuyu_v_mire_set_z arazhennyh_smartfonov_na_android_ 7. Cover, T. Nearest neighbor pattern classification / T. Cover, P. Hart //IEEE Transactions on Information Theory.- 1967. - Vol. 13. – С.21-27.

8. Seidman, S.B. A graph-theoretic generalization of the clique concept / S.B.

Seidman, B.L. Foster / Journal of Mathematical Sociology. - 1978. - Vol. 6. – С.139-154.

9. Bron, C. Algorithm 457 — Finding all cliques of an undirected graph / C. Bron, J. Kerbosh //Comm. of ACM, 16, 1973. – Р.575-577.

10. Wu, B. A parallel algorithm for enumerating all the maximal k-plexes / B. Wu, X. Pei //PAKDD'07 Proceedings of the 2007 international conference on Emerging technologies in knowledge discovery and data mining, 2007. – С.476-483.

Сведения об авторах Ковалёв Сергей Сергеевич – стажер-исследователь, е-mail: [email protected] Sergey S. Kovalev - Probationer-researcher Шишаев Максим Геннадьевич – д.т.н., заведующий лабораторией, е-mail: [email protected] Maksim G. Shishaev - Dr. of Sci (Tech), Head of laboratory УДК 004. А.С. Неведров, А.Г. Олейник ФГБУН Институт информатики и математического моделирования технологических процессов

КНЦ РАН

Кольский филиал ПетрГУ

ОРГАНИЗАЦИЯ РАСПРЕДЕЛЕННОЙ ИСПОЛНИТЕЛЬНОЙ СРЕДЫ

ДЛЯ ПОВЫШЕНИЯ ЭФФЕКТИВНОСТИ МОДЕЛИРОВАНИЯ СЛОЖНЫХ

ПРОИЗВОДСТВЕННЫХ ПРОЦЕССОВ

Аннотация В работе рассмотрены вопросы организации исполнительной среды обработки информации и моделирования при исследовании и поддержке управления производственными процессами обогащения минеральных полезных ископаемых. Основное внимание уделено сервис-ориентированной архитектуре исполнительной среды.

Ключевые слова:

компьютерное моделирование, производственный процесс, распределенная среда, сервис-ориентированная архитектура.

A.S. Nevedrov, A.G. Oleynik

ORGANIZATION OF THE DISTRIBUTED EXECUTION ENVIRONMENT

TO IMPROVE THE EFFICIENCY OF COMPLEX INDUSTRIAL PROCESSES

MODELING

Abstract The paper deals with the organization of the executive environment for information processing and modeling in the investigation and the control support of the industrial mineral dressing processes. The focus is on service-oriented architecture of the executive environment.

Key words:

сomputer modeling, industrial process, distributed environment, service-oriented architecture.

Введение В рамках использования средств компьютерного моделирования для разработки и совершенствования аппаратов и технологических схем обогащения полезных ископаемых, а также оперативного управления производственными процессами обогащения, отдельное внимание должно уделяться вопросу эффективной организации исполнительной среды моделирования. В зависимости от целей моделирования приоритетные требования к его реализации различны. Так на «исследовательском» этапе, целью которого является определение эффективных конструкций аппаратов, режимов и схем разделения минеральных компонентов, приоритетным требованием будет точность моделей, обеспечивающая необходимую детальность представления объекта исследования, а быстродействие моделей – второстепенным. Модели, интегрируемые Работа выполнена при поддержке гранта РФФИ №12-07-98800-р_север_а «Разработка моделей и информационной технологии прогнозирования параметров производственных процессов обогащения руд».

в контур оперативного управления производственными процессами, напротив, должны отвечать жестким временным ограничениям на получение результата, точность которого предъявляются более мягкие требования. На сегодняшний день существует целый ряд инструментальных средств компьютерного моделирования и инженерных расчетов, позволяющих использовать различные математические методы для создания моделей обогатительных процессов [1].

Так для исследования конструкций и режимов функционирования разделительных аппаратов активно применяются инструментальные средства, реализующие методы вычислительной гидро-аэродинамики (CFD-пакеты). Они обеспечивают возможность построения моделей, детально отражающих движение минеральных частиц в объеме разделительных аппаратов, но являются довольно ресурсоемкими. Для повышения скорости вычислений многие инструментальные средства данной категории имеют встроенные механизмы распараллеливания на основе MPI (Message Passing Interface). К другой категории относятся модели, основанные на использовании метода системной динамики. Такие модели предназначены не для изучения деталей процессов разделения, а обеспечивают «укрупненную» имитацию разделительного процесса с целью оперативной оценки влияния вариабельности его параметров на значения характеристик выходных продуктов, или других контролируемых показателей. Модели данного типа позволяют достаточно быстро получить результат варианта вычислительного эксперимента, что делает их перспективными с точки зрения использования в контуре оперативного управления производственными процессами обогащения. Системно-динамическая модель может быть создана как для отдельного разделительного аппарата, так и для их комплекса, или всей схемы обогащения в целом. Аналогичными свойствами, с точки зрения оперативности получения результата, обладают средства Steadystate моделирования. Они реализуют одношаговый метод анализа (без зависимости от времени), который позволяет получить решения по усредненным характеристикам, используя эмпирические формулы.

Пути повышения скорости расчетов при моделировании производственных процессов В исследованиях рассматривались два механизма ускорения расчетов, выполняемых моделями обогатительных процессов и аппаратов. Первый распараллеливание вычислений. Второй – выбор состава и структуры исполнительной среды из некоторого набора доступных программных и аппаратных ресурсов, обеспечивающих наиболее эффективную реализацию конкретного вычислительного эксперимента. Очевидно, что наибольший эффект дает решение, в рамках которого эти два варианта используются совместно.

Современные технологии предоставляют различные варианты аппаратной поддержки параллельных вычислений. Использование многопоточных графических процессоров (GPU - Graphical Processing Unit) позволяет реализовать высокопроизводительные параллельные вычисления на персональном компьютере. Подобные экономичные решения используются в мировой практике в качестве аппаратной платформы для симуляции различных процессов и выполнения инженерных расчетов высокой размерности. Эффективным, с точки зрения производительности, является использование специализированных многопроцессорных вычислительных кластеров. Но данный вариант имеет ограниченное применение из-за высокой стоимости аппаратного решения.

Учитывая общий уровень развития телекоммуникационных систем, глобальной информационной инфраструктуры и рост популярности облачных вычислений (от англ. cloud computing) [2], перспективным является использование существующих в облаках программных и аппаратных ресурсов при решении различных задач в области исследования процессов обогащения. Очевидно, что далеко не все задачи конкретного исследования могут быть решены на основе их использования, но обращение к ним может существенно сократить объем необходимых авторских разработок. Для обращения к представленным в облаках программным разработкам предлагаются технологии, получившие в «облачной» терминологии название SaaS (от англ. Software-as-a-Service) Программное обеспечение как услуга. Они обеспечивают потребителю возможность использовать ресурсы облака, обращаясь к ним через клиентские устройства, в результате чего собственная программно-аппаратная база клиента может быть существенно упрощена. Для организации уровня SaaS наиболее подходящей является сервис-ориентированная архитектура, согласно которой каждый программный компонент представляется в виде сервиса с четко определенным интерфейсом. Это позволяет взаимодействовать гетерогенным программным средствам, доступ к возможностям которых осуществляется с помощью адаптера (обычно, web-сервиса), который обрабатывает поступающие запросы и вызывает соответствующие методы.

Типовыми требованиями, предъявляемыми к распределенным системам, имеющим сервис-ориентированную архитектуру, относятся:

открытость, обеспечиваемая использованием проверенных стандартов в различных механизмах системы;

масштабируемость системы за счет поддержки возможности добавления новых ресурсов (инструментов);

интероперабельность системы по отношению к гетерогенным слабо связанным ресурсам;

отказоустойчивость системы в рамках проведения вычислительного эксперимента, подразумевающая возможность корректного продолжения эксперимента при отключении отдельных ресурсов во время их использования для вычислений;

обеспечение «прозрачного» использования ресурсов с точки зрения пользователя;

предоставление единого формата спецификации интерфейсов ресурсов и средств для создания таких описаний;

поддержка различных режимов вызова ресурсов и служб;

обеспечение безопасного доступа к ресурсам за счет применения соответствующих политик доступа к ресурсам, авторизации и аутентификации пользователей.

Архитектура распределенной системы обработки информации С учетом указанных требований была разработана архитектура распределенной системы организации вычислительного эксперимента (рис.1).

Основным компонентом системы является Модуль управления заданиями (МУЗ), выполняющий функции определения, планирования и мониторинга заданий, поступающих от пользователей системы. Данный модуль принимает от пользователя задание (спецификацию исполнительной среды), подбирает конкретных исполнителей на каждый этап задания и помещает готовые для выполнения задания в очередь, ожидая доступности исполнителей. После успешного запуска задания МУЗ отслеживает его состояние и информирует пользователей о ходе выполнения.

За регистрацию, контроль и мониторинг исполнителей отвечает Модуль управления исполнителями (МУИ). Данный модуль отслеживает состояние исполнителей и предоставляет данные для МУЗ при планировании и в ходе выполнения задания. В соответствии с описанием задания, полученного из МУЗ, вызываются требуемые удаленные сервисы-исполнители, представляющие собой агрегат адаптера с инструментальным средством.

Рис. 1. Схема сервис-ориентированной распределенной системы организации Для предоставления доступа пользователям к возможностям системы и выдачи прав на использование тех или иных исполнителей отдельно выделен Модуль управления пользователями (МУП). Пользователям предоставляются следующие возможности:

формирование нового задания с передачей в систему входных данных;

отслеживание состояния созданных заданий;

просмотр промежуточных и конечных результатов;

отмена выполняющихся заданий.

Все данные о пользователях, заданиях, промежуточных результатах и исполнителях хранятся в Базе данных системы. Входные данные для заданий и все результаты хранятся на сервере и передаются исполнителям по требованию.

Учитывая то, что при решении конкретной задачи моделирования или обработки данных может потребоваться обращение к большому числу ресурсов, распределенная система строится с использованием стиля REST (Representational State Transfer) [3]. Данный стиль имеет следующие важные особенности:

все используемые сущности являются ресурсами и имеют уникальный адрес;

для взаимодействия компонентов системы (запросы GET, PUT, POST, DELETE) используется HTTP-протокол.

Согласно этому Исполнитель характеризуется своим адресом в сети (URI - Uniform Resource Identifier) и спецификацией интерфейса, содержащей описание анонсируемых методов и формата передаваемых параметров. Для соблюдения соглашения о платформонезависимости адаптеров взаимодействие осуществляется посредством передачи сообщений в формате расширяемого языка разметки XML (eXtensible Markup Language,) с помощью HTTPпротокола. Спецификация такого сообщения описывается в виде XML Schema, что позволяет проводить проверку содержимого на корректность. Взаимодействие сервера с исполнителями возможно в двух вариантах:

исполнитель, после выполнения своей части задания, передает результат обратно на сервер, а сервер в свою очередь полученные данные передает следующему исполнителю;

исполнители в соответствии со спецификацией задания взаимодействуют непосредственно друг с другом, минуя сервер, что позволяет не затрачивать время на передачу результатов через сервер в задачах, в которых время критично.

В любом случае сервер опрашивает исполнителей для отслеживания сбоев в ходе выполнения заданий. При возникновении сбоя (потеря связи, ошибка выполнения и другие) МУЗ корректирует задание, подбирая с помощью МУИ альтернативных исполнителей. Подбор исполнителей производится с учетом следующих критериев:

наличие прав доступа;

коэффициент доступности исполнителя (основан на времени);

загруженность узла, на котором размещен исполнитель;

локализация узла в сети (для уменьшения трафика в случае прямого взаимодействия исполнителей).

Схема реализации адаптера Адаптер представляет собой web-сервис (рис.2), построенный на базе сервера приложений с открытым кодом GlassFish. Для взаимодействия сервера с адаптером используются следующие HTTP-запросы:

GET job_id– получение состояния указанного задания;

POST job_id – запуск указанного задания;

DELETE job_id – отмена указанного задания;

GET INFO – получение описания методов.

Адаптер реализован с использованием языка Java и библиотеки Jersey – реализация открытой спецификации JAX-RS (Java API for RESTful Web Services). Ниже, в качестве примера представлена функция getStatusById для обработки запроса состояния задания используется:

@Path("service") public class Service { @GET @Path("{job_id}") @Produces(MediaType.APPLICATION_XML) public int getStatusById(@PathParam("job_id") long id) { Job curr_job = Data.findJobById(id);

if (curr_job == null) { throw new RuntimeException("can't find job with id = " + id);

return curr_job.status;

Аналогичным образом реализуются и другие обработчики поступающих запросов к адаптеру. Запрос POST инициирует запуск исполнителя: адаптер по номеру задания запрашивает с сервера файлы и передает их исполнителю на вход. По завершению работы выходные данные передаются обратно на сервер, а также меняется состояние исполнителя и задания.

Использование HTTP-протокола позволяет включить стандартные коды ошибок для описания исключительных событий (недоступность адаптера, ошибки в работе), а также SSL (Secure Sockets Layer) для обеспечения безопасного взаимодействия элементов системы.

Заключение Сервис - ориентированный подход облегчает реализацию распределенных систем за счет инкапсулирования функциональности гетерогенных приложений (исполнителей) в сервисах. Обеспечение прозрачности достигается за счет четко определенного интерфейса и стандартных протоколов взаимодействия. Использование стиля REST позволяет воспользоваться возможностями протокола HTTP и обеспечить масштабируемость всей системы. Кроме того, построение адаптеров на языке Java дает возможность объединить в системе приложения на различных платформах.

Литература 1. Неведров, А.С. Об инструментальных средствах определения эффективных режимов обогащения минеральных руд / А.С. Неведров, А.Г. Олейник // Информационные ресурсы России, 2011. -№5 (123). - С.35-38.

2. Gillam, Lee. Cloud Computing: Principles, Systems and Applications / Editors:

Nick Antonopoulos, Lee Gillam. - L.: Springer, 2010. - 379 p.

3. Fielding, Roy Thomas. Architectural Styles and the Design of Network-based Software Architectures / Doctoral dissertation, University of California, Irvine, 2000. -Режим доступа:http://www.ics.uci.edu/~fielding/pubs/dissertation/top.htm.

Сведения об авторах Неведров Алексей Сергеевич - программист, e-mail: [email protected] Alexey S. Nevedrov - Programmer Олейник Андрей Григорьевич - д.т.н., зам. директора института, e-mail: [email protected] Andrey G. Oleynik - Dr. of Sci. (Tech), Deputy director УДК 65.011.56, 62. И.Е. Кириллов, И.Н. Морозов, А.Г. Олейник ФГБУН Институт информатики и математического моделирования технологических процессов

КНЦ РАН

Кольский филиал ПетрГУ

РАЗРАБОТКА МОДЕЛЕЙ ЭКСПРЕСС-АНАЛИЗА ОБОГАТИТЕЛЬНЫХ

ПРОЦЕССОВ НА ОСНОВЕ НЕЙРОСЕТЕЙ И НЕЧЕТКОЙ ЛОГИКИ

Аннотация В статье рассмотрены подходы к построению моделей экспресс-анализа и прогнозирования производственных процессов обогащения минерального сырья. Особенности объекта исследования дают основания считать перспективным применение для моделирования методов нечеткой логики и нейронных сетей. Представлены основные аспекты создания моделей обогатительных процессов с использованием указанных методов.

Ключевые слова:

технологический процесс, компьютерное моделирование, нечеткая логика, нейронная

DEVELOPMENT OF MODELS BASED ON NEURAL NETWORKS AND FUZZY

LOGIC FOR EXPRESS ANALYSIS OF ORE-DRESSING PROCESSES

Abstract The article considers the approaches to the construction of models for express analysis and forecasting of manufacturing processes of minerals concentration. The investigation subject properties suggest that applications of fuzzy logic and neural networks methods for simulation are promising. The basic aspects of models creating by using these methods are presented.

Key words:

manufacturing process, computer simulation, fuzzy logic, neural network.

Введение Внедрение на предприятиях автоматизированных систем оперативного диспетчерского управления и сбора данных (supervisory control and data acquisition – SCADA - систем) открывает принципиально новые возможности получения эмпирической информации об обогатительных процессах. На использование данных оперативного мониторинга производственных процессов обогащения ориентирована технология их оперативного прогнозирования, основные аспекты которой представлены в работе [1]. Технология предполагает интеграцию в действующие на промышленных предприятиях SCADA-системы специализированных средств компьютерного моделирования с целью оперативного прогнозирования технологических показателей производственного процесса. Одной из ключевых задач технологии является определение формальных связей между компонентами пространства входов и компонентами пространства выходов процесса [2]. Решение данной задачи осложняется Работа выполнена при поддержке гранта РФФИ №12-07-98800-р_север_а «Разработка моделей и информационной технологии прогнозирования параметров производственных процессов обогащения руд».

многомерностью и гетерогенностью этих пространств. Вместе с этим, большие объемы данных мониторинга параметров производственных процессов, предоставляемые SCADA-системами, дают основания считать, что положительные результаты могут быть получены в результате применения методов Data Mining [3], позволяющим не только выявить неявные взаимосвязи в данных, но и существенно снизить размерность задачи. Перспективным, также, может быть применение в рамках рассматриваемой технологии методов нечеткой логики [4] и нейронных сетей [5] для построения моделей экспресс-анализа и прогнозирования параметров производственного процесса по данным текущего мониторинга. Это предположение подтверждается тем, что аппарат нечеткой логики уже включается в библиотеки ряда SCADA-систем, таких как:

LABVIEW DSC, DELTAV, SIMATIC WINCC, TRACE MODE и других.

Способности нейронных сетей к прогнозированию напрямую следуют из их способности к обобщению и выделению скрытых зависимостей между входными и выходными данными. После обучения сеть способна предсказать будущее значение некой последовательности на основе нескольких предыдущих значений и/или каких-то существующих в настоящий момент факторов.

Схема применение аппарата нечеткой логики для построения моделей процессов обогащения В работе [2] предложен вариант формального представления многоэтапного технологического процесса обогащения (рис. 1).

Рис. 1. Схема формального представления многоэтапного На схеме использованы следующие обозначения:

Pi – аппарат или этап технологической схемы PG;

X – множество входных воздействий, влияющих на объект управления. В данное множество в качестве элементов включаются как внешние входы PG, так и входы отдельных аппаратов Pi. Входами могут быть как контролируемые воздействия (управление), так и неуправляемы воздействия (возмущения).

Возмущения в некоторых случаях измеримы, а в других - нет, и могут быть оценены лишь в словесной форме (большое, маленькое и т.д.);

Y – множество выходов, которое, аналогично множеству X, объединяет выходы всей схемы PG и выходы отдельных аппаратов Pi. Все выходы считаются потенциально контролируемыми, хотя на практике, как правило, контролируется только часть из них.

Далеко не все связи между входными сигналами и выходами могут определяться в виде классических передаточных функций W(p). Это обусловлено размерностью задачи и степенью изученности исследуемого объекта. Зная о наличии некоторого параметра (фактора) не всегда удается его измерить или оценить достаточно точно. Однако если предполагается его значимое влияние на динамику процесса, данный параметр должен быть включен в рассмотрение.

При невозможности точной (количественной) оценки параметру может быть задана нечеткая (лингвистическая) оценка.

Априорно принятым положением реализуемого подхода к разработке технологии оперативного прогнозирования обогатительных процессов является наличие неявного взаимного влияния технологических параметров процесса на характеристики продуктов разделения. Поэтому анализ начинается с рассмотрения ситуации, когда предполагается значимое влияние не только характеристик исходного сырья, но и всех технологических параметров на характеристики выходов процесса. Модель процесса представляется в виде направленного графа, узлами которого являются параметры, а дуги обозначают их влияние друг на друга. Подобное представление технологического процесса является неким подобием нейросети, в узлах которой находятся функции, осуществляющие преобразование сигналов. При этом часть функций представляется в виде «классических» передаточных функций W(p), а часть – в виде «нечетких передаточных функций». Важной особенностью «нечетких передаточных функций» является их способность не только преобразовывать сигналы, но и осуществлять настройку передаточных функций узлов описанных с помощью W(p). Данная особенность реализует свойство адаптивности модели, которое является весьма полезным с учетом динамичности свойств процесса.

Для реализации нечетких передаточных функций для соответствующих параметров вводятся нечеткие функций принадлежности (ФП). Начальная картина функций принадлежности формируется путем разбиения наблюдаемого (или - теоретического) интервала вариабельности параметра на конечное число небольших отрезков и сопоставление каждому из них нечеткой ФП. Следует отметить, что использование большого количества нечетких ФП может сильно замедлить процесс вычисления. Поэтому изначально заданные интервалы разбиения диапазонов варьирования параметров следует, по возможности, укрупнить для снижения размерности задачи. Наличие больших объемов данных мониторинга обогатительного процесса позволяет установить соответствие между большинством интервалов значений выходного параметра и интервалами значений входов, при которых получен данный выход. Сокращение числа интервалов может осуществляться как на основе анализа имеющихся данных мониторинга, так и на основе экспертных рекомендаций. Формирование базы и верификация лингвистических правил отображения комбинаций нечетких значений входов в значения выходов также формируется с использованием данных мониторинга.

В режиме прогнозирования в модель подается вектор, определяющий текущую ситуацию, который фаззифицируется и передается на обработку системе правил. Результаты нечеткого вывода дефазифицируются, в результате чего определяются значения вектора выходов. Существует несколько алгоритмов осуществления операции фаззификации и заполнения базы знаний.

Однако вопрос выбора формы ФП в литературных источниках практически не освещен. В качестве перспективного подхода к обоснованию выбора формы ФП планируется реализовать алгоритмы оценки скорости и ускорения (т.е. 1-й и 2-й производных) изменения значений параметров технологического процесса обогащения.

Разработка модели технологического процесса на основе использования нейросетей Нейронные сети успешно применяются для синтеза систем управления динамическими объектами [5]. Нейросети обладают рядом свойств, которые определяют перспективность их использования в качестве аналитического аппарата систем управления. В контексте рассматриваемой задачи это, прежде всего, способность к обучению на примерах. Наличие больших объемов данных мониторинга, в которых представлены взаимосвязанные измерения и входов, и выходов исследуемой системы, позволяет обеспечить нейросеть репрезентативными обучающими выборками. Другими важными свойствами является способность нейросети адаптироваться к изменению свойств объекта управления и внешней среды, а также высокая устойчивость к «сбоям»

отдельных элементов сети в силу изначально заложенного в ее архитектуру параллелизма. Способности нейронной сети к прогнозированию напрямую следуют из ее способности к обобщению и выделению скрытых зависимостей между входными и выходными данными. После обучения сеть способна «предсказать» будущие значения выходов на основе нескольких предыдущих значений и текущих данных мониторинга.

В рамках проводимых исследований наиболее перспективным представляется использование сетей встречного распространения. Сети данного типа имеют, в общем случае, существенно меньшее время обучения, чем сети обратного распространения. Поэтому такая сеть может более оперативно отреагировать на изменения условий протекания процесса обогащения, связанные с флуктуациями характеристик исходного сырья, технологических параметров или износом оборудования. В неройсети встречного распространения объединены два хорошо известных алгоритма: самоорганизующаяся карта Кохонена [6] и звезда Гроссберга [7]. Их объединение приводит к росту «обобщающих» способностей сети и позволяет получать правильный выход даже при неполных или незначительно искаженных входных данных Анализ возможностей использования нейронных сетей для создания моделей экспересс-анализа производственных процессов обогащения проводился на примере процесса флотационного обогащения апатито-нефелиновых руд, реализуемого на обогатительной фабрике АНОФ-2 ОАО «Апатит».

В результате анализа технологической схемы флотационного отделения, с учетом полученных ранее результатов исследования и уже принятыми в рамках данного проекта концептуальными принципами технологии моделирования производственных процессов обогащения минеральных руд была определена структура нейросетевой модели. Используемые в модели параметры классифицированы на три группы: контрольные показатели, управляющие параметры и индикаторы. К контрольным показателям относятся характеристики входных и выходных продуктов технологической схемы. В модели рассматривается 15 контрольных параметров. К управляющим относятся те параметры, на которые можно воздействовать с целью изменения условий реализации обогатительного процесса и, как следствие, значений контрольных показателей.

В качестве управляющих параметров в модели рассматривались уровни пульпы, расход воздуха и собирателя во флотомашинах ОК-38, а также уровень, расход воздуха в аэратор и расход промывной воды в колонной флотомашине и др.

Общее число задействованных в модели управляющих параметров - 30. К индикативным относятся те параметры, на которые нельзя повлиять, но которые свидетельствуют об изменениях контрольных показа-телей. К ним относятся:

плотность слива, плотность пульпы в линии циркуляции, температура в пульподелителе, уровень pH в контактом чане и др. Всего рассматривалось индикативных параметров.

На рис. 2 представлена структура сети встречного распространения в обобщенном виде.

Рис. 2. Сеть с встречным распознаванием без обратных связей Созданная модель представляет собой стандартную трехслойную (02) нейросеть встречного распространения. Нейроны слоя 0 служат точками разветвления и не выполняют вычислений. Каждый нейрон 0-го слоя связан с каждым нейроном слоя 1 (слой Кохонена). Аналогично, нейроны слоя 1 связаны с нейронами слоя 2 (слом Гроссберга). С каждой связью ассоциирован собственный вес. Веса wi связей слоев 0 и 1 образуют матрицу весов W, а веса VJ связей нейронов слоев 1 и 2 – матрицу весов V. Настройка значений весов производится в режиме обучения сети, когда в модель подаются априорно известные вектора входов X и выходов Y (рис. 1). В режиме прогнозирования в модель подается формируемый на основе текущих данных мониторинга входной вектор X, а выходной вектор Y генерируется сетью.

Выход каждого нейрона слоя является просто суммой взвешенных входов. В результате сравнительной оценки взвешенных сумм входов нейронов Кохонена определяется «победитель» – нейрон, для которого это значение максимально. Выходу данного нейрона присваивается значение «1», а выходам остальных нейронов слоя Кохонена – «0». Слой Гроссберга функционирует по аналогичной схеме – его выходы определяются взвешенной суммой соответствующих входов от слоя Кохонена. Но, так как только у одного нейрона слоя Кохонена на выходе устанавливается значение «1», то фактически каждый нейрон слоя Гроссберга лишь выдает величину веса, который связывает этот нейрон с единственным ненулевым нейроном Кохонена. По сути, слой Кохонена классифицирует входные векторы в сходные группы, обеспечивая, тем самым, определение областей многомерного пространства входов, отображающихся в малую окрестность одной и той же «точки» пространства выходов. Это достигается с помощью настройки весов слоя Кохонена, обеспечивающей активацию одного и того же нейрона данного слоя соответствующими векторами входов. Перед началом обучения всем весам сети присваиваются некоторые случайные значения. В процессе обучения весовые векторы изменяются, «отслеживая» небольшую группу входных векторов. Обучение заканчивается, когда на выходе нейросети формируется требуемая картина выходов. Обучение слоя Гроссберга осуществляется путем корректировки лишь тех весов, которые ассоциированы с нейроном Кохонена, имеющим ненулевой выход. Величина коррекции веса пропорциональна разности между весом и требуемым выходом нейрона Гроссберга, с которым он соединен.

Использование нейросетевой модели предполагает априорную классификацию состояний системы (обогатительного процесса) на конечное число вариантов. С каждым состоянием, при котором имеет место нарушение регламентных характеристик процесса, связан набор корректирующих воздействий, предполагающих конкретные изменения управляющих пара-метров. Для классификации могут быть использованы как экспертные оценки, так и формальные методы классификации из категории методов Data Mining, например – факторный и кластерный анализ. В качестве основного критерия классификации используются значения выходных векторов Y. Для определения текущего состояния процесса производится сравнение выхода нейросетевой модели и хранимых в информационной базе системы векторов, определяющих выделенные состояния обогатительного процесса. Если в базе указано, что идентифицированному состоянию соответствует нарушение регламентных характеристик, то система извлекает из базы рекомендации по корректировке состояния. При наличии соответствующего исполнительного механизма запуск на выполнение корректирующих воздействий может быть автоматизирован.

Разработанная нейросетевая модель процесса флотации была реализована и исследована в среде Matlab [8]. На рис. 3 показан общий вид нейросетевой модели, а на рис. 4 представлен фрагмент внутренней структуры элемента блока Custom Neural Network.

На вход каждого из элементов нейросети подаются все контролируемые входные параметры. Весовые коэффициенты подбирались в процессе автоматического обучения на заранее заданных выборках реальных данных, полученных SCADA-системой в результате мониторинга производственного процесса. В ходе серии вычислительных экспериментов модель была настроена и обеспечила синтез выходных векторов, соответствующих контрольной выборке данных реального производственного процесса.

Рис. 3. Укрупненный вид нейросетевой модели в среде Matlab Рис. 4. Структура элемента блока Custom Neural Network Заключение Большие объемы данных, получаемые в результате функционирования SCADA-систем, обеспечивает возможность создания и практического применения моделей экспресс-анализа и прогнозирования производственных процессов обогащения минерального сырья. Принимая во внимание многомерность задач, гетерогенность параметров и наличие существенной неопределенности в зависимостях между параметрами реальных производственных процессов, для построения моделей предлагается использовать методы Data Mining, нечеткой логики и нейронных сетей. На основе указанных математических методов созданы и протестированы на реальных данных мониторинга модели экспрессанализа обогатительных схем, используемых на ОАО «Апатит». Доказано, что созданные модели позволяют получить результаты, адекватные задачам оперативного управления производственными процессами. Наиболее рациональным для прогнозирования многостадийных обогатительных схем представляется вариант комбинированных решений, предполагающий совместное использование моделей различных типов для различных состояний обогатительного процесса или различных компонентов (аппаратов) обогатительной схемы.

Литература 1. Олейник, А.Г. Информационная технология поддержки оперативного управления процессами обогащения руд /А.Г. Олейник // Фундаментальные и прикладные исследования, разработка и применение высоких технологий в промышленности и экономике: сборник статей Четырнадцатой международной научно-практ. конф., 4-5 декабря 2012 г., г. С-Петербург / под ред. А.П.

Кудинова. – СПБ.: Изд-во Политехн. Ун-та, 2012. -Т.2. – С.84- 2. Олейник, А.Г. Схема оперативного прогнозирования производственных процессов обогащения руд / А.Г. Олейник, Л.П. Ковалева // Труды Кольского научного центра РАН. Информационные технологии. – Апатиты: Изд-во КНЦ РАН. - 4/2011(7). -Вып. 2. - С.211-219.

3. Чубукова, И. А. Data Mining: учебное пособие /И.А. Чубукова. - 2-е изд., испр. - М.: Интернет-Университет Информационных Технологий; БИНОМ.

Лаборатория знаний, 2008. - 382 с.

4. Тэрано, Т. Прикладные нёчеткие системы / Т. Тэрано, К. Асаи, М. Сугэно.

- М.: Мир, 1993. - 368 c.

5. Чернодуб, А.Н. Обзор методов нейроуправления / А.Н. Чернодуб, Д.А. Дзюба // Проблемы программирования. -2011.-№ 2. - С.79 -94.

6. Kohonen Т. Self-organization and associative memory /Т. Kohonen // 2d ed.

-New-York, Springer-Verlag, 1988. - 312 р.

7. Grossberg, S. Some networks that can learn, remember and reproduce any number of complicated space-time patterns /S. Grossberg // Journal of Mathematics and Mechanics, 1969. -Vol. 19, № 1, - Р.53-91.

8. MathWorks. - Режим доступа: http://www.mathworks.com Сведения об авторах Кириллов Иван Евгеньевич - к.т.н., младший научный сотрудник, e-mail: [email protected] Ivan E. Kirillov - Ph. D. (Tech), Junior researcher Морозов Иван Николаевич - к.т.н., младший научный сотрудник, e-mail: [email protected] Ivan N. Morozov - Ph. D. (Tech), Junior researcher Олейник Андрей Григорьевич - д.т.н., зам. директора института, e-mail: [email protected] Andrey G. Oleynik - Dr. of Sci. (Tech), Deputy director УДК 004. Д.В. Рябов, А.В. Вицентий ФГБУН Институт информатики и математического моделирования технологических процессов

КНЦ РАН

Кольский филиал ПетрГУ

АНАЛИЗ ВЫЧИСЛИТЕЛЬНЫХ ВОЗМОЖНОСТЕЙ GPU TESLA C

Аннотация В работе представлены результаты исследования вычислительных возможностей систем на основе графических процессоров общего назначения.

Рассматриваются методы и средства реализации алгоритмов, вычисляемых на графическом процессоре.

Ключевые слова:

моделирование, ресурсоемкость, графические процессоры, CUDA.

D.V. Ryabov, A.V. Vicentiy

EXPLORING COMPUTATIONAL CAPABILITIES OF GPU TESLA C

Abstract In this paper the results of the systems based on general-purpose graphics processors computing capabilities research are presented. The calculated on the GPU algorithms methods and means of implementation are considered.

Key words:

modeling, resource-demand, graphical processor, CUDA.

Введение На протяжении последних лет спрос на продукцию обогащения апатитнефелиновых руд подвергается постоянному изменению под воздействием различных рыночных факторов. В современных условиях жесткой конкуренции на мировых рынках горно-обогатительные комбинаты стремятся постоянно совершенствовать технику и технологии переработки рудного сырья с получением товарной продукции требуемого качества и высокой рентабельностью [1]. Изучение обогатительных процессов в условиях реально действующих аппаратов затруднено по экономическим причинам, поэтому моделирование обогатительных процессов с целью их совершенствования - одна из приоритетных задач на сегодняшний день. При этом необходимо использовать компьютерные модели, более или менее адекватно отражающие макрокартину гидродинамических потоков в аппаратах. Решение задачи отчасти облегчается наличием компьютерных программ, позволяющих создавать модели разнообразных физических процессов в условиях реальной геометрии [1].

В основе большинства существующих инженерных методик расчетов компонентов и характеристик схем обогащения лежат упрощенные эмпириические модели гидродинамических явлений и процессов, опирающиеся на Работа выполнена при поддержке РФФИ, проект № 12-07-98800 р_север_а «Разработка моделей и информационной технологии прогнозирования параметров производственных процессов обогащения руд».

обширные данные теоретических, лабораторных и натуральных исследований.

Недостатком моделей данного типа является сложность, а порой и невозможность адекватного учета влияния новых, не отработанных экспериментально конструктивных решений. Современный уровень развития технических и программных средств моделирования обеспечивает возможность практической реализации моделей более адекватно отражающих процессы разделения минеральных компонентов. В частности эффективным инструментом решения расчетных задач, связанных с гидродинамикой многофазных процессов, к которым относятся процессы разделения минеральных компонентов происходящих в обогатительных аппаратах, являются CAE (Computer-Aided Engineering) – системы и CFD-программы (Computational fluid dynamics), представляющие собой инструментальные средства вычислительной гидро-динамики [1].

В качестве математического аппарата для построения таких моделей используется аппарат многофазного многоскоростного континуума (ММК).

Вычислительный эксперимент над CFD-моделями, основанными на ММК представлений движения вещества в разделительном аппарате, приближается по своим качествам к натурному эксперименту [2].

В результате проведенных исследований установлено, что модели обогатительных процессов и аппаратов, а также процедуры анализа больших объемов данных мониторинга обладают высокой вычислительной сложностью.

На этапах разработки и исследования этих моделей и технологий возможно использование специализированных высокопроизводительных компьютеров.

Но, так как разрабатываемая технология ориентирована на интеграцию средств прогнозирования процессов обогащения в действующие системы оперативного управления и мониторинга, в качестве аппаратной платформы при ее практической реализации предполагается использование рабочих станций на базе типовых персональных компьютеров. Добиться необходимой производительности в таком случае можно за счет использования многопоточных процессоров для универсальных высокопроизводительных вычислений. На основе предварительных оценок [3] в 2012 г. была выбрана и закуплена за счет средств гранта плата TCSC2050-PB на основе CUDA NVIDIA TESLA C стоимостью 57001 руб. В 2013 г. проведены исследования по оценке соответствия заявленных производителем и фактических показателей производительности вычислительной системы на базе данного устройства. Также проведены сравнительные исследования производительности такой системы с производительностью систем, использующих только серийный центральный процессор.

Общая характеристика графических процессоров общего назначения Графические процессоры изначально нацелены на решение узкого круга задач, связанного с компьютерной обработкой графических данных. В связи с этим архитектуры GPU и CPU существенно отличаются друг от друга. Так, к примеру, в видеочипах от NVIDIA основной блок представляет собою мультипроцессор с сотнями ядер, и несколькими тысячами регистров. Графические процессоры от NVIDIA так же оснащены несколькими видами памяти:

локальная, разделяемая общая, константная, а так же глобальная память, доступная всем мультипроцессорам на чипе. Общая модель мультипроцессоров NVIDIA СUDA представлена на рис. 1. Полное описание программной и аппаратной модели CUDA содержится в работе [4].

Обобщим основные отличия между архитектурами центрального и графического процессоров. CPU создан для последовательного исполнения одного потока инструкций с максимальной производительностью, а GPU спроектирован таким образом, чтобы единовременно исполнять как можно большее число параллельных потоков.

В итоге можно сказать, что в отличие от современных центральных процессоров, являющихся универсальными вычислительными устройствами, одинаково эффективно справляющимися с большинством задач, графические процессоры имеют куда более узкую направленность. GPU спроектирован таким образом, чтобы максимально эффективно решать задачу обработки множественных данных. И если в CPU разработчики были вынуждены пожертвовать производительностью ради достижения максимальной унифицированности, то в GPU значительно большее число транзисторов на чипе работает по прямому назначению – обработке массивов данных. Но небольшие блоки управления исполнением и кэш-памяти накладывают значительные ограничения на структуру алгоритмов исполняемых на GPU Рассмотрим вычислительные ресурсы системы, которые будут использованы для исследований, представленных в данной работе. Основу аппаратной части составляет графический процессор для универсальных высокопроизводительных вычислений NVIDIA TESLA C2050 со специализированным программным обеспечением, центральный процессор Intel i3-2125 и оперативная память DDR3 объемом 4Gb. Подробно о характеристиках семейства сопроцессоров NVIDIA TESLA описано в статье [3].

Исследование методов и средств реализации алгоритмов, вычисляемых на графических процессорах общего назначения на языке программирования CUDA В связи с кардинальными архитектурными отличиями центрального и графического процессора стоит задача исследования аппаратных ограничений реализуемых вычислительных алгоритмов на графических процессорах общего назначения, методов их реализации и возможность оптимизации с точки зрения производительности.

Для этих исследований был выбран алгоритм умножения матриц, который является одной из основных задач матричных вычислений. Данный алгоритм является массивно-параллельным и идеально подходит для исследования вычислительных способностей и методов программирования графических процессоров общего назначения.

При выполнении вычислительного эксперимента были реализованы следующие алгоритмы:

параллельный алгоритм умножения матриц на GPGPU с использованием прямого доступа к глобальной памяти графического процессора;

параллельный алгоритм умножения матриц на GPGPU с использование кэширования данных средствами программируемой разделяемой памяти графического процессора;

параллельные алгоритмы умножения матриц с использованием универсальных сторонних библиотек, реализующих вычисления на GPGPU.

При реализации вышеуказанных алгоритмов использовался язык программирования С++, С, CUDA в среде быстрой разработки приложений Visual Studio 2008 Express. Компиляция исходного кода для вычислений на графическом процессоре выполнялась средствами компилятора NVIDIA NVCC, входящим в состав NVIDIA CUDA SDK. Для сравнительного анализа времени выполнения алгоритмов на центральном и графическом процессорах использовалась технология OMP [5], а так же свободно распространяемые библиотеки BLAS и Eigen.

С помощью вышеуказанных алгоритмов были проведены следующие исследования:

исследование влияния разбиения процесса вычисления на множество потоков и блоков ядра GPGPU на общую производительность графического процессора и время выполнения алгоритма;

исследование влияния оптимизации алгоритмов с точки зрения производительности посредством использования разделяемой памяти GPGPU;

исследование методов реализации алгоритмов на GPGPU и их влияние на время выполнения вычислений.

Проведенные эксперименты позволили сделать следующие выводы:

архитектурные особенности графических процессоров общего назначения накладывают значительные ограничения на круг решаемых задач и методы реализации алгоритмов, вычисляемых на графическом процессоре;

алгоритмы, реализующие вычисления на графических процессорах общего назначения, требуют оптимизации для получения наилучших результатов с точки зрения производительности;

реализация алгоритмов, реализующих вычисления на графических процессорах общего назначения, требует глубоких знаний архитектуры графического процессора, на котором выполняются вычисления для получения наибольшего прироста производительности по сравнению с центральным процессором;

экспериментально доказано преимущество с точки зрения производительности низкоуровневого программирования на языке CUDA над универсальными библиотеками, реализующими вычисления на GPGPU.

Исследование вычислительных способностей графических процессоров общего назначения в среде MatLab В связи с тем, что реализация алгоритмов, вычисляемых на GPGPU, средствами языка программирования CUDA является трудоемким процессом и требует от программиста глубоких знаний как низкоуровневого программирования, так и архитектуры графического процессора, были проведены исследования вычислительных способностей систем на основе графических процессоров общего назначения в среде MatLab.

MatLab (сокращение от англ. «Matrix Laboratory») - пакет прикладных программ для решения задач технических вычислений и одноимённый язык программирования, используемый в этом пакете. MATLAB широко используется инженерными и научными работниками, позволяет абстрагироваться от программной реализации алгоритмов и сосредоточить внимание непосредственно на моделировании.

В связи с необходимостью использования параллельного выполнения алгоритмов среда MatLab позволяет выполнять параллельные вычисления, используя дополнение Parallel Computing Toolbox. Parallel Computing Toolbox позволяют использовать многоядерные процессоры, графические процессоры (GPU) и кластеры для выполнения вычислительно-сложных расчётов и расчётов с большими объёмами данных. Подробно о программном продукте MatLab и Parallel Computing Toolbox написано на сайте производителя [6].

Для исследований встроенных GPU функций MatLab были написаны функции, позволяющий сравнить производительность графического процессора NVIDIA TESLA C2050 с центральным процессором Intel i3-2125.

Реализованные функции в автоматическом режиме выполняют вычисления над числами с одинарной и двойной точности. Объем данных максимально возможный из доступной оперативной памяти как центрального, так и графического процессоров. Сравнение проводилось по трем встроенным функциям, реализующим массивно-параллельные алгоритмы. А именно: умножение матриц, деление матриц и алгоритм БПФ (быстрое преобразование Фурье).

Результаты эксперимента показывают, что производительность графического процессора в среде MatLab резко уменьшается, по сравнению с алгоритмами, написанными на чистом языке CUDA, в то время как производительность центрального процессора практически не уменьшается. Данный эксперимент наглядно показывает, что среда MatLab, используя встроенные GPU функции, не позволяет достичь максимальной производительности графического процессора, обещанной производителем.

Вычислительный эксперимент, оценивающий производительность центрального и графического процессоров для задачи решения системы линейных уравнений, показал, что центральный процессор уступает графическому в производительности более чем в 2 раза. При этом производительность уменьшилась приблизительно в 5 раз относительно алгоритма умножения матриц и в 8 раз относительно максимальной, заявленной производителем графического процессора. Такое замедление, прежде всего, обусловлено тем, что данный алгоритм требует частого обращения к разным ячейкам данных (случайный доступ к оперативной памяти) тем самым замедляя работу арифметических операций графического процессора. При этом производительность центрально процессора осталась на одном и том же уровне. Гистограмма сравнения производительности графического и центрального процессоров, при выполнении задачи деления матриц в среде MatLab, представлена на рис. 2.

Рис. 2. Сравнение производительности CPU и GPU на примере В табл. представлены результаты исследования производительности графического и центрального процессора при применении некоторых встроенных GPU функций MatLab R2012b.

Результаты исследования встроенных GPU функций MatLab R2012b Процессор Исследование методов реализации алгоритмов, вычисляемых на графическом процессоре в среде MatLab R2012b MatLab R2012b позволяет выполнять алгоритмы на GPU четырьмя способами:

использование встроенных GPU функций;

использование интерфейса GPU array;

выполнение пользовательских функций на элементах GPU array (функция arrayfun);

вызов CUDA ядер непосредственно в MatLab (*.ptx объектных файлов).

Ранее рассматривались некоторые встроенные GPU функции MatLab, но для ряда задач таких функций попросту может не быть. Одной из таких задач является задача построения фрактала Мандельброта.

Так как алгоритм, решающий данную задачу, является массивнопараллельным и может быть реализован несколькими способами, появляется задача выбора метода реализации этого алгоритма в среде MatLab. В данном исследовании рассмотрены все возможные методы реализации алгоритма построения фрактала Мандельброта в среде Matlab и проведена оценка производительности и сложности каждого из методов.

Для сравнения производительности центрального и графического процессоров, был реализован алгоритм, выполняющий вычисления только на центральном процессоре. Простейшим методом преобразования данного алгоритма является хранение и вычисление множества Мандельброта на графическом процессоре. При этом алгоритм остается неоптимизированным с точки зрения параллельности, но при этом дает лучшие результаты, чем центральный процессор, что связано с более быстрым процессом выполнения простейших математических операций. В данном случае данные передаются на графический процессор посредством встроенной функции gpyArray.

Преимуществом данного способа является минимальное изменение исходного кода, а недостатком является производительность, которая намного ниже, чем в других методах, рассмотренных далее.

Методом параллельной оптимизации алгоритмов в среде MatLab для графических процессоров является выполнение пользовательской функции над каждым элементом массива данных. Как и в предыдущем случае, данные передаются на графический процессор посредством функции gpuArray, а вычисления над каждым элементом выполняется функцией arrayfun, которая выполняет пользовательскую функцию, непосредственно выполняющую математические операции. Данный метод подразумевает значительное изменение вычислительно алгоритма и кода программы, но при этом дает большой выигрыш в производительности.

Третий способ оптимизации алгоритмов для графических процессоров является непосредственный вызов CUDA ядра из среды MatLab. При использовании данного метода первостепенным является написания CUDA ядра на языке программирования CUDA и его компиляция в объектный PTX файл средствами компилятора NVCC компании NVIDIA.

При использовании данного метода среда MatLab выполняет второстепенные задачи, такие как инициализация начальных условий, конфигурирование и вызов ядра, а так же графическое отображение полученного множества Мандельброта. Данный метод является оптимальным с точки зрения производительности, но сложен в реализации, так как требует знаний языков программирования C и CUDA, знания аппаратно-программной технологии CUDA, а также знания архитектуры и особенностей графического процессора.

С помощью реализованных алгоритмов, описанных выше, был проведен эксперимент по построению фрактала Мандельброта различными методами.

Размерность комплексной плоскости бралась 1000х1000 ячеек, максимальное количество итераций 500. Производительностью будем считать время построения множества Мандельброта. Результаты эксперимента приведены на рис. 3. На графике видно, что абсолютно все алгоритмы, реализованные для вычислений на графическом процессоре, имеют значительный выигрыш относительно вычислений выполняемых на CPU. При этом оптимизация алгоритмов для GPU является неотъемлемой для повышения производительности.

Рис. 3. Время (в сек.) построения фрактала Мандельброта Заключение В ходе проведенной работы были изучены существующие технологии программирования графического ускорителя, а так же проведен сравнительный анализ архитектуры центрального и графического процессоров. На основе проведенных исследований были сделаны выводы о целесообразности использования графического процессора для решения ряда задач общего назначения.

Реализация простейшего алгоритма умножения матриц с использованием технологии CUDA программирования графических процессоров общего назначения показала, что несмотря на более чем десятикратный выигрыш во времени исполнения алгоритма на GPU по сравнению с CPU, данный подход является нецелесообразным из-за больших временных затрат, связанных с подготовкой данных и получением результатов вычислений.

Проведенные исследования доказали важность оптимизации алгоритма умножения матриц и конфигурирования вычисляющего ядра графического процессора под каждую модель и архитектуру графического процессора общего назначения.

Реализация алгоритмов умножения матриц с использованием универсальных сторонних библиотек, выполняющих вычисления на графических процессорах, показала выигрыш во времени исполнения алгоритма на GPU по сравнению с CPU, но оказалась проигрышной по сравнению с алгоритмом, оптимизированным для модели GPGPU NVIDIA TESLA C2050 написанном на языке CUDA.

Технология программирования графических процессоров NVIDIA CUDA изначально проектировалась с целью предоставить разработчикам инструмент для программирования алгоритмов решающих задачи общего назначения на GPU. Реализация алгоритмов перемножения матриц показала, что использование данной технологии способно значительно сократить время их выполнения на входных данных больших размерностей.

Исследования вычислительных способностей систем на основе графических процессоров общего назначения в среде MatLab показали, что скорость выполнении алгоритмов напрямую зависит от метода обращения к вычисляемым данным, следствием чего является понижение производительности в задачах с произвольным доступом к памяти. Также экспериментально было доказано преимущество низкоуровневого программирования на языке CUDA над встроенными возможностями и функциями MatLab R2012b Parallel Computing Toolbox.

Литература 1. Бирюков, В.В. Применение системы Femlab для моделирования гидродинамики течений в обогатительных аппаратах / В.В. Бирюков, А.Г. Олейник // Информационные ресурсы России. – 2007. – № 3 (97). – С.30-32.

2. Разработка моделей разделительных аппаратов с использованием математического аппарата ММК / В.В. Бирюков и др. // Труды Кольского научного центра РАН. Информационные технологии. –Апатиты: Изд-во КНЦ РАН, 4/2012(11). –Вып.3. – С.124-133.

3. Вицентий, А.В. Ограничения данных при реализации процедур декларативных моделей прогнозирования параметров производственных процессов обогащения / А.В. Вицентий // Труды Кольского научного центра РАН.

Информационные технологии. –Апатиты: Изд-во КНЦ РАН, 4/2012(11).

–Вып.3–С.134-140.

4. Nvidia Cuda Programming Guide / The Nvdia Corporation, 2008. -111 с.

5. OpenMP Architecture Review Board. –Режим доступа: http://openmp.org/wp/ 6. Matlab The Language of Technical Computing.

– Режим доступа: http://www.mathworks.com/products/matlab/ Сведения об авторе Рябов Дмитрий Валерьевич – aспирант, программист, е-mail: [email protected] Dmitriy V. Ryabov - Post-graduate, Programmer Вицентий Александр Владимирович - к.т.н., научный сотрудник, е-mail: [email protected] Alexander V. Vicentiy - Ph.D. (Tech. Sci.), Researcher УДК 502. В.В. Бирюков, А.А. Петров ФГБУН Горный институт Кольского научного центра РАН

ИНФОРМАЦИОННОЕ ОБЕСПЕЧЕНИЕ РАЗРАБОТКИ И ОПТИМИЗАЦИИ

ТЕХНОЛОГИЧЕСКИХ ПРОЦЕССОВ СОХРАНЕНИЯ И ОСВОЕНИЯ РУДНЫХ

И ТЕХНОГЕННЫХ МЕСТОРОЖДЕНИЙ