Содержание

Алимов Н. А., Ерофеева В. А. , Шалымов Д. С. (СПбГУ, ИПМАШ) Анализ возможностей методов классификации для автоматизации работы дефибриллятора                            3

Амелин К. С., Амелина Н. О., Дерюгин Д. Е., Иванский Ю. В. (СПбГУ, ИПМАШ) Экспериментальный стенд для исследования процесса адаптации планера с “перьями” к изменениям турбулентного потока              31

Барковский Е. А. Реализация менеджера памяти в work-stealing балансировщике                  56

Сазонов А. М. (ИПМИ КарНЦ РАН) Оптимальное управление двумя очередями, работающими по принципу настраиваемых очередей  66

 

САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

СТОХАСТИЧЕСКАЯ ОПТИМИЗАЦИЯ В ИНФОРМАТИКЕ

Издается с 2005 года

ТОМ 13

Выпуск 1

Издательство С.-Петербургского университета

2 0 1 7

УДК 519.712

БКК 32.811.7

С82

Ответственный редактор д. ф.-м. н., проф. О. Н. Граничин

Редакционная коллегия: Б. Т. Поляк (ИПУ РАН),

А. В. Соколов (ИПМИ КарНЦ РАН),

П. С. Щербаков (ИПУ РАН)

С82 Стохастическая оптимизация в информатике. Том 13 (Вып. 1) / Под ред. О. Н. Граничина — СПб.:

Издательство С.-Петербургского университета, 2017. — 80 с. ISSN 1992–2922

Издание выпускается ежегодно (том 1, ненумерованный, вышел в 2005 г., тома (вып.) 2–12 — в 2006–16 гг.) и содержит научные работы по стохастической оптимизации, особо выделяя приложения в информатике. Первый выпуск двенадцатого тома составлен из поступивших в редколлегию рукописей и материалов одноименной регулярной серии семинаров для студентов, аспирантов и научных работников, проводившихся в 2016–17 г. на математико-механическом факультете С.-Петербургского университета под руководством профессора кафедры системного программирования О. Н. Граничина. Выпуск опубликован при поддержке гранта РФФИ №16-07-00890-а.

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

ББК 32.811.7

© Авторы статей, 2017

 

Анализ возможностей методов классификации для автоматизации работы дефибриллятора[1]

Н. А. Алимов, В. А. Ерофеева, Д. С. Шалымов[2]

Санкт-Петербургский государственный университет Институт проблем машиноведения РАН alimov.nsm@gmail.com victoria@grenka.net dmitry.shalymov@gmail.com

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

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

       1.      Введение

Фибрилляция желудочков является одним из самых распространенных случаев нарушения работы сердца, приводящим к внезапной сердечной смерти. Выживаемость для пациентов, подверженных риску смерти такого рода, довольно низка (от 10% до 20%) [8]. Пациенты зачастую умирают из-за того, что вовремя не получают лечения. Появление автоматических внешних дефибрибриляторов позволяет своевременно провести реанимационные действия, восстановив сердечный ритм посредством нанесения удара.


Основой работы автоматических дефибрилляторов является анализ электрокардиограмм и принятие решения на его основе. В последнее время широко распространены исследования, направленные на повышение точности алгоритмов анализа сердечного ритма. В работе [10] для выделения характеристик ритма при его анализе авторы используют вариационную модовую декомпозицию (англ. Variational Mode Decomposition) с последующей классификацией на основе метода опорных векторов (англ. Support Vector Machine). В работе [19] предложен композитный алгоритм, объединяющий анализатор динамики изменения наклонов ритма с цифровым фильтром, для разделения ритма на две группы — с возможностью нанесения удара дефибриллятором и без нее соответственно. В [12] авторами предложено использование статистических методов для классификации ритма трех типов (нормальный синусовый, фибрилляция желудочков, желудочковая тахикардия) с предварительным выделением признаков на основе временной и частотной областей, а также изменений наклонов ритма. Работа [13] направлена на выявление наиболее информативных признаков для процедуры классификации на основе метода адаптивного порога для определения различных пиков ритма. Классификация ритмов на основе использования нейронной сети рассматривалась в [9]. В работе [4] авторы исследуют применимость сверточных нейронных сетей для выявления желудочковой тахикардии, отмечая, что фиксированный набор признаков может быть неприменим в классификации реальных случаев из-за высокой вариабельности ритма между различными пациентами.

Большинство работ основывается на анализе небольшого числа открытых баз данных электрокардиограмм, позволяя сделать вывод о том, что получение данных, особенно значительного для процедуры классификации размера, для этой задачи весьма затруднителено. Тем не менее, на сегодняшний день получили свое развитие методы, применимые к выборкам малого размера [6]. Преимуществом этих методов также является устойчивость к внешним помехам в наблюдениях [1,2,14], которые зачастую присутствуют в электрокардиограммах. В работах [15,16] рассматриваемые методы успешно апробированы на задаче в области механики.

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

       2.        Постановка задачи

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

Начало сердечного цикла в здоровом сердце происходит в синоатриальным узле, расположенном в правом предсердии. Действуя подобно естественному кардиостимулятору, синоатриальный узел инициирует импульс с регулярными интервалами от 60 до 100 раз в минуту. Электрический импульс распространяется через междольные пути, активируя (деполяризуя) предсердия, что заставляет их сокращаться и перекачивать кровь в желудочки. Атриовентрику-

Рис. 1: Проводящая система сердца.

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

Электрическая активность сердца, регистрируемого электродами, расположенными на поверхности тела, называется электрокардиограммой или ЭКГ. На рисунке 2 показана запись ЭКГ нормального ритма сердца, называемого нормальным синусовым ритмом. Он состоит из Р-волны, QRS-комплекса и Т-волны, вызванной деполяризацией предсердий, деполяризацией желудочков и реполяризацией желудочков соответственно. Реполяризация предсердий отмечается комплексом QRS.

Внезапное прекращение механической активности сердца, под-

Рис. 2: ЭКГ синусового ритма в норме.

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

Наиболее частой причиной внезапной сердечной смерти является проявление фатальных желудочковых аритмий: фибрилляции желудочков (ФЖ) и желудочковой тахикардии (ЖТ), представленных на рисунке 3. В период фибрилляции желудочки быстро деполяризуются и реполяризуются, сердце нарушает свою скоординированную работу и возможность эффективно прокачивать кровь. Единственный действенный способ прекратить фибрилляцию желудочков и восстановить сердечный ритм — дефибрилляция, полученная через передачу электрического удара в сердце. Фибрилляция желудочков обусловлена быстрым повторным возбуждением миокардиальных волокон с неэффективным сокращением желудочка. Условие фибрилляции идентифицируется отсутствием комплексов QRS на ЭКГ. Дефибрилляция деполяризует миокард и заканчивает нерегулярные сокращения, возвращая работу сердца к нормальному регулярному ритму в случае успеха.

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

Рис. 3: ЭКГ синусового ритма в норме.

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

Требуется по набору тестовых данных построить классификатор, относящий сформированный до момента времени t ритм работы сердца человека к одному из классов — ударный/неударный (shockable/non-shockable), максимизируя при этом вероятность положительного исхода применения процедуры дефибрилляции.

       3.        Описание данных

В большинстве работ, посвященных рассматриваемой тематике, используются две открытые базы данных [5]:

    Creighton University Ventricular Tachyarrhythmia Database (CUDB) содержит 35 одноканальных записей, каждая из которых составляет около 8 минут. Путем сегментации каждой записи на множество коротких эпизодов по 10 секунд каждый была создана база данных, содержащая группы электрокардиограмм с ударными ритмами (фибрилляция желудочков и желудочковая тахикардия) и неударными (синусовый ритм, суправентрикулярная тахикардия, асистолия и другие) [11].

    MIT-BIH Malignant Ventricular Arrhythmia Database (VFDB) включает в себя 22 двухканальные записи длительностью 35 минут. Сигналы аналогично разделены на ударные (трепетание и фибрилляция желудочков, желудочковая тахикардия) и неударные группы [7].

Проблема указанных баз данных состоит в том, что на их основе можно построить классификацию типа ритма, но при этом нет никаких сведений об исходе применения процедуры дефибрилляции. Для решения этой проблемы была собрана собственная база данных, содержащая 170 записей по 9 секунд каждая. Каждая запись была отнесена к одному из двух классов — ROAE и NoROAE (дефибрилляция помогла и не помогла соответственно). На основе полученных записей было сформировано 19 признаков, перечисленных в таблице 1.

Таблица 1: Описание признаков.

Признак

Единица измерения

Расшифровка

 

та

MA

mV

Средняя амплитуда: среднее значение абсолютной величины сигнала

WA

mV

Амплитуда волны: среднее значение различий между пиком и следующим минимальным

AmpMax

mV

Максимальное          значение сигнала

AmpMin

mV

Минимальное значение сигнала

 

PTT

mV

Peak-To-Trough: разница между максимумом и

минимумом

PPA

 

Peak-Peak Amplitude: 4-х секундная трассировка ЭКГ разделяется на четыре сегмента по одной секунде каждый. Для каждого сегмента находится разница между максимальным и минимальным значениями. Вычисляется среднее четырех значений, полученных на предыдущем шаге.

MS

mV/s

Средний наклон

MedS

mV/s

Медиана наклона

AMSA

mV Hz

Amplitude Spectrum Area: сумма абсолютных значений произведений между амплитудой спектральной плотности и соответствующей частотой

absAMSA

mV Hz

abs Amplitude Spectrum Area: абсолютное значение суммы прозведений между амплитудой спектральной плотности и соответствующей частотой

PSA

mV 2 Hz

Power Spectral Analysis: сумма абсолютных значений произведений между удельной мощностью спектра и соответствующей

частотой

ENRG

mV 2

Energy: интеграл от удельной мощности спектра

CF

Hz

Centroid Frequency: частота “центра масс” удельной мощности спектра

 

частоты F такое, что 95% энергии сигнала ниже F

SMF

dB

Spectral Flatness Measure: отношение геометрического и среднего арифметического

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

4. Сравнительный анализ методов машинного обучения для задачи автоматизации дефибриллятора

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

Accuracy score. Применительно к многоклассовой классификации, метрика отражает точность классификации для каждого отдельного класса или для всех классов вместе взятых. Если все предсказанные системой значения класса соответствуют истинным, то точность равна единице, в ином случае нулю. Пусть yˆi — предсказанное значение класса для i-го набора данных и yi соответствующее истинное значение, тогда доля корректных прогнозов от общего размера выборки nsamples определяется как:

accuracy,

samples i=0

где 1(x) — функция-индикатор события.

AUC score. Агрегированная характеристика качества классификации, вычисляемая как площадь под кривой ошибок (ROCкривая). Кривая ошибок, в свою очередь, отражает зависимость доли верных положительных классификаций от доли ложных положительных классификаций при варьировании порога решающего правила.

Confusion matrix. Матрица неточностей (англ. Confusion Matrix) строится на основе подсчета количества раз, когда система приняла верное и неверное решение относительно истинного значения класса принадлежности (true positives (tp) — истино-положительное решение; true negatives (tn) — истино-отрицательное решение; false positives (fp) — ложно-положительное решение; false negatives (fn) — ложно-отрицательное решение), а именно: Оценка системы

 

Class 0

Class 1

Class 0

True negatives (tn)

False positives (fp)

Class 1

False negatives (fn)

True positives (tp)

В бинарной классификации под терминами “положительное решение” и “отрицательное решение” понимается оценка принадлежности входных данных к определенному классу на основе решения классификатора, а под “истинным решением” — класс, заданный человеком. В этом контексте, можно определить характеристики точности (precision), полноты (recall) и F-меры (F-measure) следующим образом:

precision ,

recall ,

Fβ = (1 + β2)β2 · precision×+ recall. precision              recall

В анализе методов машинного обучения применительно к задаче автоматизации дефибриллятора в работе использовались следующие методы: метод ближайших соседей (Nearest Neighbors) [20], дерево принятия решений (Decision Tree) [21], метод случайного леса (Random Forest) [3], нейронные сети (Neural Net) [22], AdaBoostSAMME [17], наивный байесовский классификатор (Naive Bayes) [18], метод опорных векторов (RBF SVM) [23]. При проведении процедуры обучения использовался скользящий контроль (англ. CrossValidation) с разбивкой на четыре блока.

4.1. Метод ближайших соседей (Nearest Neighbors) Значения метрик точности, полноты и F-меры:

                                             precision      recall     f1-score      support

No ROAE0.931.000.96310

ROAE0.830.170.2830 avg / total0.920.920.90340

Значения метрик Accuracy score и AUC score для каждого блока k скользящего контроля (k = 1...4):

                                                        k1                     k2                     k3                     k4

Accuracy score0.90690.93020.91660.9404 AUC score0.74430.81730.73190.8265


Рис. 4: Матрица неточностей для метода ближайших соседей.

4.2. Дерево принятия решений (Decision Tree) Значения метрик точности, полноты и F-меры:

                                             precision      recall     f1-score      support

No ROAE0.950.950.95310

ROAE0.530.530.5330 avg / total0.920.920.92340

Значения метрик Accuracy score и AUC score для каждого блока k скользящего контроля (k = 1...4):

                                                        k1                     k2                     k3                     k4

Accuracy score0.90690.87200.91660.8809 AUC score0.72430.73070.68830.8766 Рис. 5: Матрица неточностей для дерева принятия решений.

4.3. Метод случайного леса (Random Forest) Значения метрик точности, полноты и F-меры:

                                             precision      recall     f1-score      support

No ROAE0.940.990.96310


ROAE0.820.300.4430 avg / total0.930.930.92340

Значения метрик Accuracy score и AUC score для каждого блока k скользящего контроля (k = 1...4):

                                                        k1                     k2                     k3                     k4

Accuracy score0.94180.96510.92850.9523 AUC score0.86050.92060.79030.9397 Рис. 6: Матрица неточностей для метода случайного леса.

        4.4.             Нейронная сеть (Neural Net)

Значения метрик точности, полноты и F-меры:

                                             precision      recall     f1-score      support


No ROAE0.920.990.96310

ROAE0.670.130.2230 avg / total0.900.920.89340

Значения метрик Accuracy score и AUC score для каждого блока k скользящего контроля (k = 1...4):

                                                        k1                     k2                     k3                     k4

                                                  0.9069     0.9418    0.9166      0.9285

                                                    0.7676     0.7708     0.6289     0.5510


Рис. 7: Матрица неточностей для нейронной сети.

                               4.5.          AdaBoost-SAMME

Значения метрик точности, полноты и F-меры:

                                                                     precision      recall      f1-score      support

No ROAE0.950.970.96310

ROAE0.600.500.5530 avg / total0.920.930.92340

Значения метрик Accuracy score и AUC score для каждого блока k скользящего контроля (k = 1...4):

                                                                                k1                     k2                     k3                     k4

                                                                          0.9186    0.9302    0.9285      0.9285

                                                                            0.7820     0.7884     0.7012     0.8571

Рис. 8: Матрица неточностей для метода AdaBoost-SAMME.

4.6. Наивный байесовский классификатор (Naive Bayes) Значения метрик точности, полноты и F-меры:

                                                                     precision      recall      f1-score      support

No ROAE0.970.910.94310

ROAE0.430.670.5230 avg / total0.920.890.90340

Значения метрик Accuracy score и AUC score для каждого блока k скользящего контроля (k = 1...4):

                                                                                k1                     k2                     k3                     k4

                                                                          0.9186    0.8837    0.8928      0.8690

                                                                            0.7812     0.9038     0.8218     0.9053

Рис. 9: Матрица неточностей для наивного байесовского классификатора.

                               4.7.               Метод опорных векторов (RBF SVM)

Значения метрик точности, полноты и F-меры:

                                                                     precision      recall      f1-score      support

No ROAE0.911.000.96310

ROAE1.000.030.0630 avg / total0.920.910.88340

Значения метрик Accuracy score и AUC score для каждого блока k скользящего контроля (k = 1...4):

                                                                                k1                     k2                     k3                     k4

Accuracy score         0.9069   0.9069   0.9285   0.9166 AUC score0.8525 0.8669  0.7235 0.9721


Рис. 10: Матрица неточностей для метода опорных векторов.

            4.8.            Анализ полученных результатов

Результаты применения методов машинного обучения к задаче классификации электрокардиограмм показывают, что на их основе возможно провести автоматизацию работы дефибриллятора. Тем не менее, выбор конкретного метода классификации затруднителен из-за низких показателей точности по классу ROAE вследствие довольно малой выборки относительно второго класса. В рассматриваемом случае наиболее перспективным представляется использование методов машинного обучения, способных к обучению на выборках малого размера. В дальнейшем также возможна интеграция системы классификация с основной работой дефибриллятора. Приведем одну из возможных архитектур на примере дефибриллятора Physio Control LIFEPAK 12 (см. Рис. 11). Для синхронизации данных в этом случае можно использовать программу от производителя устройства — CODE-STAT. Для соединения дефибриллятора с компьютером следует использовать кабель LIFEPAK Monitor to PC (версия для USB).

Рис. 11: Схема взаимодействия классификатора с дефибриллятором.

            5.         Программное обеспечение

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

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

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

2.    Добавление алгоритмов. Реализована возможность загружать алгоритмы, написанные на языке Python в виде скрипта в определҷнном виде.

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

4.    Нахождение наилучший алгоритм из представленных. Реализован поиск наилучшего алгоритма для представленных данных.

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

            5.1.          Архитектура системы

Основные элементами архитектуры системы являются:

    cтруктура базы данных;

    взаимодействие клиента и сервера;

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

    способ осуществления анализа и обработки результатов.

Структура базы данных

Разработана структура базы данных, представленная на Рис. 12.

Рис. 12: Структура базы данных.

Клиент-серверное взаимодействие

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

Хранение моделей

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

Анализ и результаты классификации

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

            5.2.           Программная реализация

При написании кода использовался паттерн MVC (Model-ViewController). Код хорошо продокументирован, в некоторых местах даны необходимые пояснения в виде комментариев.

Клиентская сторона

Основной клиентский код был написан на JavaScript и Angular JS (первая версия).

Серверная сторона

Для реализации серверной части были использованы:

    язык программирования Python;

    микрофреймворк Flask;

    библиотека машинного обучения и анализа данных scikit-learn;

    библиотеки scipy, numpy, matplotlib для языка Python;

    база данных SQLite;

    библиотека для языка Python Keras.

Программный интерфейс

Примеры реализациии программного интерфейса представлены на рисунках 13, 14, 15, 16, 17, 18.

Рис. 13: Главная страница.

Рис. 14: Создание нового проекта.

Рис. 15: Загрузка данных.

Рис. 16: Добавление алгоритма.

Рис. 17: Выбор алгоритма.

Рис. 18: Результаты анализа данных.

            6.       Заключение

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

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

Список литературы

[1]      Граничин О.Н. Введение в методы стохастической оптимизации и оценивания. Учебное пособие. - СПб.: Изд-во С.-Петерб. университета, 2003, 131с.

[2]      Сенов А.А., Граничин О.Н. Идентификация параметров линейной регрессии при произвольных внешних помехах в наблюдениях // В сб. трудов XII Всероссийское совещание по проблемам управления (ВСПУ-2014), Россия, Москва, ИПУ РАН, 16-19 июня 2014. 2014. С. 2708–2719.

[3]      Breiman L. Random Forests // Machine Learning. 2001. Vol. 45. No. 1. P. 5–32.

[4]      Chandra B. S., Sastry C. S., Jana S. Subject-specific detection of ventricular tachycardia using convolutional neural networks // Computing in Cardiology Conference (CinC). 2016. P. 53 – 56.

[5]      Goldberger A.L., Amaral L.A.N., Glass L., Hausdorff J.M., Ivanov

P.Ch., Mark R.G., Mietus J.E., Moody G.B,. Peng C.-K., Stanley H.E. PhysioBank, PhysioToolkit, and PhysioNet: Components of a New Research Resource for Complex Physiologic Signals. 2000. Vol. 101. Issue 23. P. 215–220.

[6]      Car´e A., Csaji B.C., Campi M.C., Weyer. E. Finite-Sample System Identification: An overview and a new correltation method // IEEE Control Systems Letters. 2017. Vol. 2. Issue 1. P. 61–66.

[7]      Greenwald S.D. Development and analysis of a ventricular fibrillation detector // M.S. thesis, MIT Dept. of Electrical Engineering and Computer Science. 1986.

[8]      Mattioni T., Kanaan N., Riggio O., et al. Performance of an automatic external cardioverter-de brillator algorithm in the discrimination of supraventricular from ventricular tachycardia // The American journal of cardiology. 2003. Vol. 91. Issue 11. P. 1323–1326.

[9]      Ming Y., Guang Z., Taihu W., Biao G., Liangzhe L., Chunchen W., Dan W., Feng C. Detection of shockable rhythm using multiparameter fusion identification and BP neural network // 2nd IEEE International Conference on Computer and Communications (ICCC). 2016. P. 798 – 802.

[10]   Nguyen M.N., Nguyen B.V., Kim K. Shockable Rhythm Diagnosis for Automated External Defibrillators Using a Modified Variational Mode Decomposition Technique // IEEE Transactions on Industrial Informatics. 2017. Vol. PP. No. 99.

[11]   Nolle F.M., Badura F.K., Catlett J.M., Bowser R.W., Sketch M.H. CREI-GARD, a new concept in computerized arrhythmia monitoring systems // Computers in Cardiology. 1986. Vol. 13. P. 515–518.

[12]   Ramakrishnan S., Akshaya V., Kishor S., Thyagarajan T. Real Time Implementation of Arrhythmia Classification Algorithm using Statistical Methods // Trends in Industrial Measurement and Automation (TIMA). 2017. P. 1–4.

[13]   Ramakrishnan S., Yogeswaran R. Design and Analysis of Feature Extraction Algorithm for ECG signals using Adaptive Threshold Method // Trends in Industrial Measurement and Automation (TIMA). 2017. P. 1–8.

[14]   Senov A., Amelin K., Amelina N., Granichin O. Exact confidence regions for linear regression parameter under external arbitrary noise // In: Proc. of the 2014 American Control Conference (ACC), 4-6 June, 2014, Portland, USA.

[15]   Volkova M.V., Granichin, Petrov Y.V., Volkov G.A. Dynamic fracture tests data treatment based on the randomized approach // Advances in Systems Science and Applications (ASSA), 2017, no. 3, pp. 35-43.

[16]   Volkova M., Granichin O., Petrov Yu., Volkov G. Sign-perturbed sums approach for data treatment of dynamic fracture tests // In:

Proc. of the 56th IEEE Conference on Decision and Control, December 12-15, 2017, Melbourne, Australia.

[17]   J. Zhu, H. Zou, S. Rosset, T. Hastie Multi-class AdaBoost // Statistics and Its Interface. 2009. Vol. 2. No. 3. P. 349–360.

[18]   H. Zhang The Optimality of Naive Bayes // Proc 17th International Florida Artificial Intelligence Research Society Conference. 2004.

[19]   Zhang F., Li P., Jiang F., Lai D. A shockable rhythm detection algorithm for automatic external defibrillators by combining a slope variability analyzer with a band-pass digital filter // 2014 IEEE Workshop on Electronics, Computer and Applications. 2014. P. 828 – 831.

[20]   Nearest Neighbors. URL: http://scikit-learn.org/stable/modules/ generated/sklearn.neighbors.KNeighborsClassifier.html

[21]   Decision       Tree.       URL:      http://scikit-

learn.org/stable/modules/generated/ sklearn.tree.DecisionTreeClassifier.html

[22]   Neural          Net.        URL:      http://scikit-learn.org/stable/modules/ generated/sklearn.neural_network.MLPClassifier.html

[23]   Support        Vector    Machines.             URL:      http://scikitlearn.org/stable/modules/svm.html

 

Экспериментальный стенд для исследования процесса адаптации планера с “перьями” к изменениям турбулентного потока[3]

Амелин К. С., Амелина Н. О., Дерюгин Д. Е., Иванский Ю. В.[4]

Санкт-Петербургский государственный университет,

Институт проблем машиноведения РАН

{konstantinamelin, ngranichina, deryugin.denis, ivanskiy.yuriy}@gmail.com

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

Ключевые слова: метод скоростного градиента, мультиагентные технологии, переходный процесс, самолет с «перьями», турбулентность.

            1.      Введение

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

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

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

Как было показано в [1,2,3,4], ряд природных явлений имеет смысл рассматривать как процессы с переменной структурой пространства состояний. Изменение структуры пространства состояний приводит к изменению внутренней структуры системы, а взаимодействие элементов системы, в свою очередь, приводит к изменению системы в целом [5]. При рассмотрении турбулентности в жидкостях, газах, мультифазовых и пластических потоках окружение может рассматриваться в качестве подобной системы [6,7]. Примером таких систем может служить практически любая биологическая система. О динамическом формировании структур можно говорить и в рамках социологии, психологии и экономики [8].

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

Мультиагентные системы могут быть использованы для эффективного решения широкого спектра проблем, связанных с возмущениями и нестационарными системами [10]. Эффективность решения достигается заменой большой и сложной модели набором простых локальных моделей. Согласованное поведение некоторой подгруппы агентов приводит к уменьшению размерности пространства состояний [11,12]. Возмущения внешней среды могут приводить к нарушению согласованности в поведении некоторых групп агентов, что будет соответствовать увеличению размерности пространства состояний.

В последнее десятилетие проблемы взаимодействия в распределенных системах управления все больше привлекает внимание исследователей [13,14,15,16]. Этот интерес обусловлен растущим количеством прикладных областей, связанных с управлением в распределенных электрических сетях, межпроцессорным взаимодействием, беспроводными, транспортными и промышленными сетями, сетями датчиков, БПЛА, координацией мобильных роботов и

т. п.

В [17] предлагалось использовать мультиагентную систему для решения проблем, связанных с движением в турбулентном потоке. Эта задача не имеет аналитического решения, и в настоящее время используются различные упрощенные модели, а значит, использование мультиагентного подхода может оказаться эффективным.

В этой статье рассматривается математическая модель и устройство экспериментального стенда для исследования процесса адаптации планера с “перьями” к изменениям турбулентного потока.

            2.          Синхронизация перьев самолета

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

            2.1.             Формализация постановки задачи

Будем считать, что самолет движется прямолинейно в горизонтальной плоскости и поверхность его крыла состоит из n конечных элементов (“перьев”) a1,a2,...,ai,...,an. Здесь и далее верхний индекс i,i N = {1,2,...,n} обозначает номер “пера” i, а не степень. “Перья” могут изменять свои углы наклона αi к поверхности крыла в определенных границах от значения αдо α+ и поворачиваться в плоскости крыла на угол βi в диапазоне от βдо β+. Эти наклоны и повороты позволяют изменять вертикальную и продольную составляющие возмущающих сил, действующих на “перо”.

Для каждого i = 1,2,...,n будем использовать следующие обозначения: f0i — интегральная сила

f,

действующая на i-е перо в ламинарном потоке ветра до момента времени t1, приложенная к центру пера и направленная перпендикулярно его поверхности,

— величина силы f0i,

 — угол наклона пера i до момента времени t1, i0 — угол поворота пера i до момента времени t1,

 — вертикальная проекция силы, действующей на i-е перо:

,

 — продольная проекция силы, действующей на i-е перо:

, fi — интегральная возмущающая сила

fi(t) = ∫ f(r,t)dr,

ai

действующая на i-е перо в момент времени t t1, приложенная к центру пера и направленная перпендикулярно его поверхности, fi — величина силы fi, αi(t) — угол наклона пера i в момент времени t, βi(t) — угол поворота пера i в момент времени t, zi — вертикальная проекция силы fi, xi — продольная проекция силы fi,

r — интегральное отклонение воз-

мущающей силы fi от стационарного значения f0i при ламинарном обтекании.

Заметим, что при изменении углов αi(t) и βi(t) естественно изменяются векторы fi, а также величины zi и xi, которые равны соответственно zi = ficos(αi) и xi = fisin(αi)cos(βi). Кроме того, в силу введенных обозначений имеем

(1)

                                                                                                                              .        (2)

О п р е д е л е н и е 1. Будем говорить, что “перья” синхронизированы в момент времени t, если совпадают все отклонения  для всех i,j N.

В ламинарном потоке при сохранении углов

все “перья” синхронизированы, так как 0 ∀i,j N.

Л е м м а 1. Если начиная с некоторого момента времени t1 + τ все “перья” самолета синхронизированы, то суммарные вращательные моменты вокруг оси движения (продольной оси) и вертикальной оси равны нулю.

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

эффициентывсех остальных парbi,j = (bi,jj,i), у которых нет связи между собой, опре-: ∑jNi bi,j = 1. Полагая bi,j = 0 для

делим симметричную матрицу смежности B = [bi,j]. В дальнейшем потребуются следующие понятия из теории графов и обозначения: 1n n-мерный вектор из единиц, GB — неориентированный граф связей с матрицей смежности B; взвешенная степень узла iграфа GB — сумма элементов i-й строки матрицы B : di(B) = n=1 i,j;diag{di(B)} — диагональная матрица из взвешенных стеb j

пеней узлов; dmax(B) — максимальная взвешенная степень узла графа GB; L(B) = (diag{di(B)} − B) — Лапласиан графа GB; ·T — операция транспонирования вектора или матрицы; B— Евкли-

дова норма: B∥ = √∑i j(bi,j)2; Tr(B) — след матрицы B (сумма диагональных элементов); λ2(B) — вещественная часть второго по абсолютной величине собственного числа матрицы B; λmax(B) — вещественная часть максимального по абсолютной величине собственного числа матрицы B. Граф GBsg называется подграфом графа GB, если bi,jsg bi,j для всех i,j N. Говорят, что граф GB содержит остовное дерево, если существует дерево Gtr, являющееся подграфом GB. Так как L(B)c1n = 0 при любом c, то любой вектор из одинаковых констант является собственным вектором матрицы Лапласиана L(B), соответствующим нулевому собственному значению. Если граф GB содержит остовное дерево, то кратность нулевого собственного значения матрицы Лапласиана L(B) равна единице (см. [13] или [14]) и, следовательно, |λ2(B)| > 0. Вектор из всех первых двух проекций отклонений моментов ,

обозначим D , и опреде-

лим качество выравнивания отклонений с помощью функционала Лапласа [19]

                                .                      (3)

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

Приведенные выше рассуждения обосновывают следующую формализованную постановку задачи: Требуется при переходе самолета на некотором интервале времени [t1,t2] от равномерного прямолинейного полета в условиях ламинарного обтекания потоком воздуха к полету в зоне турбулентности в условиях возмущений выбрать для каждого “пера” i N такие законы изменения углов наклона αi и поворота βi

                                                α˙i(t) = uiα(t), β˙i(t) = uiβ(t),                                      (4)

которые обеспечили бы для функционала качества Q(D(t)), начиная с некоторого момента времени t1 + τ, выполнение целевого условия

                                                             |Q(D(t))| ≤ ε                                                   (5)

для задаваемого достаточно малого параметра ϵ > 0 при достаточно большом значении t2 > t1 + τ.

2.2.      Использование метода скоростного градиента и оценка времени переходного процесса

Для описания процесса выравнивания сил воспользуемся принципом скоростного градиента (Speed-Gradient Principle, SG) [20,21]. Согласно этому принципу все физические системы эволюционируют по наискорейшему пути в направлении термодинамического равновесия, которому соответствует максимальное значение энтропии. В рамках алгоритма скоростного градиента максимальному приращению энтропии отвечает минимальное значение функционала качества Q. Следуя общей схеме алгоритма скоростного градиента [21], выведем формулы для оптимального закона управления (4). Для Q˙ имеем

                        .               (6)

Из вида (3) функционала Q и свойств Лапласиана графа GB выводим

            ,         (7)

а из (1)-(2) получаем

(8)

(9)

(10)

В соответствии с принципом скоростного градиента надо выбрать такие законы изменения для α˙i и β˙i, чтобы все слагаемые в суммах в (6), умноженные на , были отрицательными. Для этого при условии fi = 0̸ можно взять

(11)

(12)

с некоторым параметром (коэффициентом усиления) γ > 0.

Последние соотношения (11), (12) вместе с (7)–(10) позволяют выписать закон управления.

Если fi = 0, то α˙i = β˙i = 0, иначе

(13)

Т е о р е м а 1. Пусть ε > 0 и для k = 1,2 обозначим через Dk(t1+) предел Dk(t) при t t1 справа. Если граф GB содержит остовное дерево и выполнены сделанные выше предположения, тогда закон управления (13)–(14) обеспечивает достижение цели управления (5) за время не более, чем

где

.

З а м е ч а н и е 1. Важно подчеркнуть мультиагентную природу протокола управления (13)–(14), в котором управляющие сигналы для наклона и поворота “перьев” генерируются только на основании данных о своем состоянии и о состоянии соседних “перьев”.

З а м е ч а н и е 2. Характерное время процесса определяется обратной величиной коэффициента усиления 1и может быть сделано сколь угодно малым. Но в реальной физической системе параметр γ не может быть выбран произвольно большим, так как его выбор будет зависеть от скорости срабатывания датчиков давления и реализации соответствующих команд управления поворотами и наклонами “перьев”.

З а м е ч а н и е 3. Еще одной важной особенностью протокола управления (13)–(14) является то, что в нем нет явной “привязки” к моменту времени t1, при котором изменяется структура набегающего потока. Этот факт “снимает” необходимость решения традиционно сложной задачи “о разладке” (см., например, [22]). Углы наклона “перьев” начинают автоматически изменяться по обратной связи при нарушении согласованности моментов возмущающих сил. Это позволяет легко распространить полученные результаты, используя тот же протокол управления (13)–(14), на случай многократного изменения структуры турбулентного потока в моменты времени t1,t2,...,tm,... при выполнении дополнительного условия: maxm>0{tm+1 tm} >> τ.

3. Экспериментальный стенд для исследования процесса адаптации планера с «перьями» к изменениям турбулентного потока

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

3.1.      Упрощенная математическая модель турбулентного потока

Турбулентный поток действует не постоянно, а возникает в некоторый момент времени. Таким образом, давление воздуха на различные участки поверхности описывается следующим образом. До момента времени t1 на поверхность воздействует ламинарный поток, т. к. pk = wk, где wk — центрированные помехи, соответствующие неточному измерению давления. В момент времени t1 возникает возмущение, которое действует до момента времени t2, после которого может либо вернуться ламинарный поток воздуха, либо появиться турбулентный поток с новыми параметрами. Можно предположить, что турбулентный поток формирует конечное число возмущений, каждое из которых может быть представлено как нормально распределенное с некоторыми коэффициентами.

Таким образом, давление в точке x в момент времени t может быть выражено как

 (16)

3.2. Программная реализация фреймворка для работы с МАС

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

Рис. 1: Роботизированные элементы и связь между ними.

Для проведения экспериментов был разработан фреймворк (см. Рис. 2) на языке Python, позволяющий обрабатывать данные о работе системы, строить графики и визуализировать состояние системы в реальном времени.

Фреймворк состоит из двух основных модулей.


Рис. 2: Фрейморк для работы с мультиагентными системами.

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

    Модель случайных воздействий в каждой точке пространства.

    Упрощенная модель турбулентного потока (16).

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

    Протокол локального голосования из [23].

    Алгоритм для выравнивания давления, предложенный в [2].

    Алгоритм (1), (13), который после дискретизации принимает вид

 ,

где Pr[α+](·) — проектор в интервал [α+], γ — размер шага,  — начальные условия, −1), ¯ im = ri(fmi −1 sin(αmi −1) −  и отправляют сигнал на исполнительный механизм, исполнительный механизм его принимает и устанавливает постоянный угол наклонана весь следующий интервал времени [tm,tm+1].

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

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

                3.3.          Стенд для испытаний

Для проверки обоснованности рассматриваемой новой постановки задачи и работоспособности нового алгоритма разработан экспериментальный стенд, позволяющий проводить реальные физические эксперименты [24].

Экспериментальный стенд выполнен в виде крыла самолета с двояковыпуклым профилем Eppler, на который могут воздействовать разнообразные потоки ветра. Размах крыла 1 m при хорде 0,5 m. Почти вся поверхность крыла покрыта пластинами (“перьями”) с датчиками давления. Количество пластин — n = 100 шт. Размер одной пластины 60 mm × 60 mm.

Пластины равномерно размещены по поверхности со смещением каждого ряда относительно друг друга на 30 mm. Таким образом у каждой пластины имеется максимум шесть соседей. Для измерения давления используется чувствительный аналоговый датчик давления (барометр), который показывает как увеличение давления, так и разряжение на поверхности пластины. Угол наклона пластин αi

Рис. 3: Фрагмент стенда моделирования.

может меняться с помощью приводов (см. Рис. 3) с целью изменения давления воздуха на них. Сбор данных и генерирование сигнала управления ШИМ выполняются с помощью отладочных плат STM32F3DISCOVERY. Задачу управления каждой пластиной, сбор данных с датчиков и взаимодействие с соседями осуществляет микрокомпьютер Arduino Micro, с возможной скоростью обновления данных каждые 0,001 сек. Для управления сервоприводом используется ШИМ с постоянным уровнем напряжения 5 В, постоянной частотой импульсов в 50 Гц и переменной длительностью рабочей части импульса от 0,9 мс до 2 мс, где 1,5 мс является средним положением сервопривода, а отработка из крайнего в крайнее положение занимает 0,1 сек и представляет собой поворот движущейся части на 60 град. Поворот пластин пока не реализован. Сбор данных со всех плат Arduino Micro происходит на отладочных платах Arduino Mega 2560 R3. Одна плата Arduino 2560 обеспечивает взаимодействие с 14 платами Arduino Micro. В стенде используется 7 плат Mega. В экспериментах исследуется топология связи, при которой каждый элемент связан с шестью соседями. В дополнение на пластинах установлены светодиоды для индикации статуса достижения синхронизации. Для обеспечения разнообразных потоков ветра используется шесть вентиляторов общей мощностью в 500 Вт.

Такт работы микроконтроллера выбран h = 0,03 сек. За это время все микрокомпьютеры собирают данные с датчиков f¯mi = fi(tm)

Рис. 4: Соединение платы с сервоприводом.

(здесь и далее моменты времени tm = t1+h(m−1),m = 1,2,...), отправляют и принимают данные от соседей, обрабатывают данные по алгоритму.

Передача данных между микрокомпьютерами формируется посредством цифровых портов. В один и тот же момент каждый микрокомпьютер, после расчетов, отправляет информацию на шесть соседей с одного порта и принимает шесть сигналов с шести других портов. Для передачи информации был разработан протокол, основанный на двоичной системе, в котором давление на датчик имеет градацию от 0 до 10, а начало сообщения содержит три нуля. В связи с этим пластинка перемещается на угол от 0 до 30 град. с шагом в 3 град., что соответствует вращению сервопривода на угол от 0 до 45 град. с шагом в 4,5 град. Задержка отработки сигнала на исполнительных механизмах: поворот подвижной части механизма (качалки) на 60 град. происходит за 0,1 сек., на 4,5 град. за 0,0075 сек.

Вся информация от плат Arduino дублируется в главном компьютере для профилировки и визуализации результатов. На теку-

Рис. 5: Отладочная плата STM32F3DISCOVERY.

щем этапе проекта исследуются работоспособность алгоритма (17) при различных выбираемых пользователем параметрах γ и bi,j. Проведенные эксперименты показывают достаточно высокую скорость протекания переходных процессов, обеспечивающих синхронизацию отклонений моментов возмущающих сил относительно оси по направлению движения самолета. На данный момент выявлена достаточно сильная дискретизация работы исполнительных механизмов, что сказывается на перераспределении. Протокол дорабатывается для увеличения числа ступеней в 3 раза.

                4.          Моделирование работы алгоритма

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

Рис. 6: Движение в ламинарном потоке (математическая модель) (t < t0).

    Размер шага γ.

    Отрезок [αk;αk+], в пределах которого изменяется α.

    Топологию системы (т.е. матрицу связей B).

    Соотношение сил ламинарного и турбулентного потоков.

На Рис. 9, 10, 11, 12 изображены графики изменения функционала качества (3) с течением времени.

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

На Рис. 9, 10, 11, 12 наблюдается колебание значений функционала качества при управлении системой элементов крыла по алгоритму (17). Этот эффект наблюдается даже при неизменных внешних условиях. Роботизированные устройства продолжают периодически менять свое положение, и не наблюдается сходимость к близким значениям отклонения давления от давления в ламинарном потоке на элементах крыла. При уменьшении шага колебания

Рис. 7: Воздействие турбулентного потока (математическая модель) (t = t0).

уменьшаются, но время сходимости алгоритма вырастает пропорционально. Было сделано предположение, что это происходит изза центральных элементов на крыле: из-за малого значения плеча возрастает управление (так как длина плеча rk находится в знаменателе). Изменение структуры крыла с полностью покрытого “перьями” на два региона с элементами по краям крыла (при использовании половина от общего числа датчиков) привело к стабилизации (см. Рис. 13, 14).

                5.       Заключение

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

Рис. 8: Балансировка нагрузки (математическая модель) (t0 < t < t1).

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

Список литературы

[1]      Granichin   O.,           Khantuleva          T. Hybrid systems and randomized

Рис. 9: Изменение значений функционала качества с течением времени при.

measuring in nonequilibrium processes // Differential Equations and Control Processes. 2004. Vol. 3. P. 35–43.

[2]      Granichin O., Khantuleva T., Amelina N. Adaptation of aircraft’s wings elements in turbulent flows by local voting protocol // IFACPapersOnLine. 2017. Vol. 50. No. 1. P. 1904–1909.

[3]      Граничин О.Н. Как действительно устроены сложные информационно-управляющие системы? // Стохастическая оптимизация в информатике. 2016. Т. 12. Вып. 1. С. 3–19.

[4]      Граничин О.Н., Хантулева Т.А Адаптация элементов крыла (“перьев”) самолета в турбулентном потоке с помощью мультиагентного протокола // Автоматика и телемеханика. 2017. № 10. С. 168–

188.

Рис. 10: Изменение значений функционала качества с течением времени при.

[5]      Синай Я.Г. Построение кластерной динамики для динамических систем статистической механики // Вестник Московского университета. Серия 1. Математика. Механика. 1974. Т. 29. № 1. С. 152–

158.

[6]      Khantuleva T.A., Meshcheryakov Yu.I. Nonequilibrium processes in condensed media. Part 2. Structural instability induced by shock loading // Physical Mesomechanics. 2016. Vol. 19. No. 1. P. 69–76.

[7]      Meshcheryakov Yu.I., Khantuleva T.A. Nonequilibrium processes in condensed media: Part 1. Experimental studies in light of nonlocal transport theory // Physical Mesomechanics. 2015. Vol. 18. No. 3. P. 228–243.

[8]      Boccaletti S. et al. Complex networks: Structure and dynamics // Physics reports. 2006. Vol. 424. No. 4. P. 175–308.

Рис. 11: Изменение значений функционала качества с течением времени при.

[9]      Зубарев Д.Н. Неравновесная статистическая термодинамика. — М.: Наука. 1971. 416 с.

[10]   Yong-Zheng S., Jiong R. Leader-follower consensus problems of multiagent systems with noise perturbation and time delays // Chinese Physics Letters. 2008. Vol. 25. No. 9. P. 3493.

[11]   Utkin V.I. Sliding Modes in Control and Optimization — SpringerVerlag Berlin, Heidelberg. 1992. 286 p.

[12]   Емельянов С.В. Системы автоматического управления с переменной структурой. — Москва: Наука. 1967. 335 с.

[13]   Chebotarev P.Yu., Agaev R.P. Coordination in multiagent systems and Laplacian spectra of digraphs // Automation and Remote Control. 2009. Vol. 70. No. 3. P. 469–483.

Рис. 12: Изменение значений функционала качества с течением времени при.

[14]   Lewis F.L. et al. Cooperative Control of Multi-Agent Systems: Optimal and Adaptive Design Approaches (Communications and Control Engineering). — London: Springer. 2014. 307 p.

[15]   Olfati-Saber R., Murray R.M. Consensus problems in networks of agents with switching topology and time-delays // IEEE Transactions on Automatic Control. 2004. Vol. 49. No. 9. P. 1520–1533.

[16]   Ren W., Beard R.W., Atkins E.M. Information consensus in multivehicle cooperative control // IEEE Control Systems. 2007. Vol. 27. No. 2. P. 71–82.

[17]   Granichin O., Khantuleva T. Local voting protocol for the adaptation of airplane’s “feathers” in a turbulence flow // Proc. of the 2017 American Control Conference. 2017. P. 5684–5689.

Рис. 13: Изменение значений функционала качества с течением времени при использовании всей поверхности крыла.

[18]   Хантулева Т.А. Нелокальная теория неравновесных процессов переноса. — СПб.: Изд-во СПбГУ. 2013.

[19]   Olfati-Saber R., Fax J., Murray R. Consensus and cooperation in networked multi-agent systems // Proceedings of the IEEE. 2007. Vol. 95. No. 1. P. 215–233.

[20]   Khantuleva T.A., Shalymov D.S. Modelling non-equilibrium thermodynamic systems from the speed-gradient principle // Philos. Trans. R. Soc. A. 2017. Vol. 375. Is. 2088. P. 2016220.

[21]   Фрадков А.Л. Исследование физических систем при помощи обратных связей // Автоматика и телемеханика. 1999. №. 3. C. 213–

230.

[22]   Kalmuk A., Granichin O., Granichina O., et al. Detection of abrupt changes in autonomous system fault analysis using spatial adaptive

Рис. 14: Изменение значений функционала качества с течением времени при использовании половины элементов по краям крыла.

estimation of nonparametric regression // Proc. of the 2016 American Control Conference. 2016. P. 6839–6844.

[23]   Granichin O., Khantuleva T., Granichina O. Local voting protocol for the adaptation of airplane’s “feathers” in a turbulence flow // Proc.

of the 2017 American Control Conference. 2017. P. 5684–5689.

[24]   Граничин О.Н., Амелин К.С., Амелина Н.О. Заявка на изобретение “Аэродинамическое крыло летательного аппарата с адаптивно изменяющейся поверхностью”. №2016147133/20(075649) от

30.11.2016.

 

 

 

Реализация менеджера памяти в work-stealing балансировщике[5]

Е. А. Барковский[6]

barkevgen@gmail.com

В работе описывается менеджер памяти, реализованный в экспериментальном work-stealing балансировщике задач. Менеджер разработан на основе математических моделей оптимального управления work-stealing деками. В менеджере реализованы и проанализированы следующие методы управления памятью: оптимальное деление; деление пополам. Также, работа экспериментального менеджера сравнивается с работой стандартного менеджера памяти.

Ключевыеслова: оптимальное управление, work-stealing деки, менеджеры памяти.

                1.      Введение

Стратегии балансировки параллельных вычислений на многоядерной архитектуре разделяют на статические и динамические. Статическая балансировка используются когда известно практически все про выполняемые задачи. В этом случае можно заранее определить оптимальное расписание задач (например, минимизировать среднее время решения), но такие задачи считаются NPполными и встречаются достаточно редко. При динамической балансировке балансировщик во время работы использует некую относительно простую стратегию, которая дает результат близкий к оптимальному. Одна из таких стратегий балансировки называется “work-stealing” – процессоры, ставшие пустыми, пытаются перехватить часть работы у других процессоров. Этот метод реализован в большом числе систем, например: Cilk [1]; TBB [2]; TPL [3]; X10 [4] и другие.

В этом методе балансировки нагрузки каждый процессор решает ряд задач, указатели на которые хранятся в деке этого процессора. Когда процессор создает новую задачу, он добавляет указатель на нее в свой дек; когда процессору нужна задача, он берет указатель из вершины дека. Если процессор узнает, что его дек пуст, он перехватывает указатели на задачи у другого процессора. Первые две операции выполняются как в LIFO-стеке, а перехват происходит из основания дека – как в FIFO-очереди. Т.е. мы работаем (в терминологии Д. Кнута) с деком с ограниченным входом [5]. В [6] рассматривался перехват одного элемента, в [7] – половины элементов.

В предыдущих работах мы предлагали математические модели последовательного циклического представления work-stealing деков, где каждый дек расположен в отдельном участке памяти и на каждом шаге дискретного времени с ними происходят операции с заданными вероятностями [8,9]. В этой статье будет описана и проанализирована одна из реализаций вышеупомянутых моделей и методов, как менеджера памяти встроенного в work-stealing балансировщик задач.

На практике, для работы с деками в виде циклических массивов часто используются классические методы работы с кучей в трансляторах C/C++. Для каждого дека из кучи запрашивается массив. Когда он становится достаточно большой, то запрашивается новый массив, например, в два раза больший – туда копируются элементы дека, а старый массив отдается в список свободных блоков кучи. Если же наоборот, дек стал достаточно мал, то те же действия производятся с массивом, меньшим старого в два раза. Мы же в этой статье рассматриваем задачу поиска оптимальных альтернативных методов управления памятью для деков, в предположении, что известны некоторые их вероятностные характеристики.

                2.         Математическая модель

Приведем постановку задачи математической модели [9], на основе которой был разработан менеджер памяти.

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

Рис. 1: Область блуждания

мяти, выделенное первому деку, тогда m s – количество памяти, выделенное второму деку.

Пусть x и y текущие длины первого и второго дека соответственно. В качестве математической модели мы рассматриваем случайное блуждание по двухмерной целочисленной решетке в области −1 ≤ x s + 1, −1 ≤ y m s + 1 (Рис. 1).

Некоторые вероятностные характеристики операций, производимых над деками, заранее известны:

    включение элемента в первый дек с вероятностью p1;

    включение элемента во второй дек с вероятностью p2;

    включение элементов параллельно в оба дека – p12;

    исключение элемента из первого дека с вероятностью q1;

    исключение элемента из второго дека с вероятностью q2; Таблица 1: Оптимальное разбиение памяти, перехват одного элемента

Входные данные

Среднее время до переполнения

(m = 100)

оптимальное

разделение

 

разделение

пополам (s = 50)

Задача перемножения матриц

p1 = 0.071, p2 = 0.108, q1 = 0.071, q2 = 0.108, p12 = 0.014, q12 = 0.014, pq12 = 0.013, pq21 = 0.013

11549 (s = 46)

11345

    исключение элементов параллельно из обоих деков – q12;

    включение в первый дек и исключение из второго – pq12;

    включение во второй дек и исключение из первого – pq21;

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

p1 +p2 +p12 +q1 +q2 +q12 +pq12 +pq21 +r = 1. Как только дек становится пустым, он начинает перехватывать элементы у другого дека. Соответственно, исключение элемента из пустого дека не является аварийной ситуацией.

Блуждание начинается в начале координат. Прямые x = s + 1 и y = m s + 1 образуют два поглощающих экрана – когда процесс попадает на эти экраны память переполняется и программа аварийно прекращается; Прямые x = −1, y = −1 образуют два отражающий экрана. Введение данных экранов позволяет установить процесс перехвата элемента. Формально деки попадают на экраны, но фактически – в область 1 ≤ x < s, 1 ≤ y < ms. Для случая перехвата одного элемента: если процесс находится на точках (x,−1) или (−1,y), он перейдет на точки (x − 1,1) или (1,y − 1).

Здесь в качестве критерия оптимальности рассматривается максимальное среднее время до переполнения памяти (т.е. до попадания на прямые x = s + 1 и y = m s + 1).

В таблице 1 приведены некоторые результаты вычислений. Исходными данными являются оценки вероятностей (по частоте) работы системы при решении задачи перемножения матриц. Они были получены в результате экспериментов с разработанным workstealing балансировщиком задач [10].

                3.           Реализация балансировщика задач

Кратко опишем принцип работы экспериментального work-stealing балансировщика [10], в который был встроен менеджер памяти.

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

Например, задачу для вычисления чисел Фибоначчи можно записать (на псевдокоде) следующим образом:

1        function          fib (n)

2        i f n < 2 then

3        return n;

4        end i f

5

6          x = spawn fib (n -         1) ;

7          y = spawn fib (n -         2) ;

8          sync ;

9          return x + y ;

10       end function

При выполнении fib(n), задача создаст две подзадачи: fib(n−1) и fib(n − 2). Созданные подзадачи будет помещены в очередь потока и могут быть украдены и выполнены другими потоками. Для того, чтобы дождаться завершения подзадач, вызывается функция sync, которая передает управление балансировщику, позволяя ему выполнять другие задачи, пока у родительской не завершатся все подзадачи. Задачи для выполнения поток сначала извлекает из своей очереди, а, когда они заканчиваются, начинает красть из очереди случайно выбранного потока.

Так как над очередью задач могут выполняться операции добавления и извлечения только ее владельцем, а операция перехвата другими потоками, то в реализациях балансировщиков используют очереди с двумя концами, т. н. деки (double ended queues).

В одной из последних и наиболее цитируемых работ [11] предложена реализация деков на основе циклического массива, с неблокирующими синхронизациями операций и с возможность динамического изменения размера. Относительно других реализаций, она нуждаются в меньших накладных расходах на выполнение операций и по использованию памяти. Работающие версии можно встретить в балансировщиках задач в библиотеке Intel TBB и в языке

Rust.

На языке C++ 11 был реализован work-stealing балансировщик задач, работающий по описанному выше алгоритму и использующий реализацию деков из [11]. (Исходные коды и реализация на сайте https://github.com/rkuchumov/staccato.)

                4.           Реализация менеджера памяти

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

Стоит отметить, что в исходной версии work-stealing балансировщика начальные размеры деков были одинаковы и равны степеням двойки.

В следующих таблицах приведены некоторые результаты экспериментов с менеджером памяти. В качестве теста использовалась задача перемножения матриц. Исходными данными являются: Размер перемножаемых квадратных матриц; Размер памяти, отведенный для хранения указателей на задачи; Размеры деков; Среднее время решения задач в секундах (для каждого размера матриц проводилось 30 экспериментов).

Все исследования проводились на процессоре Intel Pentium N3710 1.60GHz, 4 CPU, 32 L1, с Linux 4.4.0. Расчеты проводились на двух ядрах процессора.

Таблица 2: Среднее время решения задачи, оптимальное деление памяти

Размер матриц

Память

Дек 1

Дек 2

Время

256

104

50

54

5,699

512

118

56

62

45,599

1024

132

63

69

366,153

Таблица 3: Среднее время решения задачи, деление памяти пополам

Размер матриц

Начальные значения

После преполнения

Время

память

дек 1

дек 2

память

дек 1

дек 2

256

104

52

52

106

52

54

5,683

512

118

59

59

121

59

62

45,504

1024

132

66

66

135

66

69

366,106

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

Таблица 2. При методе “оптимальное деление” каждому деку выделяется минимальное количество памяти, требуемое для решения задачи без переполнений. Если разделить размер первого дека на общий объем памяти, то можно получить процент памяти выделенный первому деку. Для всех рассмотренных размеров перемножаемых матриц этот процент примерно равен 48, что близко к теоретически полученному значению – 46 (таб. 1).

Таблица 3. При методе “деление пополам” каждому деку выставлялись одинаковые количества памяти, в результате чего один из деков переполнялся. Чтобы не прекращать работу системы, деку выделялось большее количество памяти. Соответственно, общий объем требуемой памяти также увеличивался.

Так, для размера матрицы 1024, начальные размеры деков были равны 66 (132/2). В процессе работы второй дек переполнился и его размер увеличился до 69, что привело к увеличению общей памяти до 135.

В таблице 4 среднее время работы сравнивается между двумя Таблица 4: Среднее время решения задачи при различных менеджерах памяти

Размер матриц

Память

Дек 1

Дек 2

Время

Экспериментальная реализация

 

256

104

50

54

5,699

512

118

56

62

45,599

1024

132

63

69

366,153

Стандартная реализация

 

256

128

64

64

5,678

512

128

64

64

45,478

1024

192

64

128

363,058

реализациями менеджеров памяти:

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

“Стандартная реализация” – это вариант менеджера, использующийся в балансировщике по умолчанию. В нем декам выделяются одинаковые начальные размеры равные степеням двойки. При переполнении дек увеличивается в два раза.

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

Например, пусть мы решаем задачу перемножения квадратных матриц размером 1024:

Допустим, у нас имеется ограниченная память в 132 байта и размер указателя равен 1 байту. При переполнении дека работа прекращается. В таком случае, чтобы решить задачу нам требуется выделить первому деку 63 байта, а второму – 69. Если мы выделим обоим декам половину памяти – 66 байтов (таб. 3), то второй дек переполнится и задача не выполнится. То же произойдет, если мы выделим обоим декам 64 байта (таб. 4).

                5.       Заключение

Описанный в статье менеджер памяти имеет как преимущества, так и недостатки.

С одной стороны, использование менеджера (при использовании метода оптимального деления памяти) обеспечивает выполнение задач на меньших размерах памяти. С другой стороны, среднее время решения задач увеличивается.

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

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

Список литературы

[1]      Blumof R.D., Joerg C.F., Kuszmaul B.C., Leiserson C.E., Randall K.H., Zhou Y. Cilk: an efficient multithreaded runtime system // Journal of Parallel and Distributed Computing. 1996. Vol. 37. No. 1. P 55–69.

[2]      Marochko               A.            TBB       scheduler              clandestine           evolution.            

Intel.            2010      [Online].                Available:     https://software.intel.com/enus/blogs/2010/12/09/tbb-scheduler-clandestine-evolution.

[3]      Leijen D., Schulte W., Burckhardt S. The design of a task parallel library // ACM SIGPLAN Notices. 2009. Vol. 44. No. 10. P 227–242.

[4]      Tardieu O., Wang H., Lin H. A work-stealing scheduler for X10’s task parallelism with suspension // ACM SIGPLAN Notices. 2012. Vol. 47. No. 8. P 267–276.

[5]      Knuth D. The art of computer programming, vol. 1. — AddisonWesley. 2001.

[6]      Blumofe R.D., Leiserson C.E. Scheduling multithreaded computations by work stealing // Journal of the ACM. 1999. No. 46. P 720–748.

[7]      Hendler D., Shavit N. Non-blocking steal-half work queues // ACM Symposium on Principles of Distributed Computing. 2002. P 280–289.

[8]      Барковский Е.А. Математические модели и методы оптимального управления Work-stealing деками в общей памяти // Стохастическая оптимизация в информатике. 2015. Т. 11. № 1. С. 55–64.

[9]      Барковский Е.А., Кучумов Р.И., Соколов А.В. Оптимальное управление двумя work-stealing деками в общей памяти при различных стратегиях перехвата работы // Программные системы: Теория и приложения. 2017. № 1. С. 83–103.

[10]   Кучумов Р.И. Реализация и анализ work-stealing планировщика задач // Стохастическая оптимизация в информатике. 2016. Т. 12. № 1. С. 20–39.

[11]   Chase D., Lev Y. Dynamic circular work-stealing deque // ACM Symposium on Parallelism in Algorithms and Architectures. 2005. P 21–28.

 

 

Оптимальное управление двумя очередями, работающими по принципу настраиваемых очередей[7]

А. М. Сазонов[8],

Институт прикладных математических исследований Карельского научного центра Российской академии наук, Петрозаводск, РФ, sazonov@cs.karelia.ru

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

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

                1.      Введение

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

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

Одна из распространенных стратегий обслуживания это настраиваемые очереди (Custom Queues) [1], или взвешенные очереди в терминологии [2]. Механизм настраиваемых очередей разработан для того, чтобы можно было предоставить всем классам трафика какой-то минимум пропускной способности. Под весом данного класса понимается процент предоставляемой классу трафика пропускной способности от полной пропускной способности выходного интерфейса.

CQ обрабатывает трафик, ориентируясь на количество пакетов или байтов, которые надо отправить. Очереди обслуживаются по алгоритму round-robin – часть пакетов обрабатывается и пересылается для каждой очереди. Если очередь пуста, то маршрутизатор будет посылать пакеты из следующей очереди.

В [4] - [8] предлагались математитческие модели и алгоритмы оптимального управления FIFO-очередями. В [9] была предложена математическая модель и решалась задача оптимального управления для настраиваемой очереди, представленной в виде двух очередей в случае их последовательного циклического представления. В качестве критерия оптимальности рассматривается минимальная доля потерянных элементов при бесконечном времени работы очередей. В данной работе предолжена имитационная модель этого процесса, проведено ее сравнивнение с математической моделью, а также проанализирована разработанная имитационная модель для настраиваемой очереди, представленной в виде двух очередей в случае их представления друг за другом. Такой метод был предложен в [10] для представления FIFO-очередей. В [11] этот метод представления FIFO-очередей анализировался для случая, когда включения происходят на нечетных шагах времени, а исключения – на четных. Задача оптимального управления двумя настраиваемыми очередями для случая, когда включения происходят на нечетных шагах, а исключения – на четных, была решена в [12].

2. Постановка задачи для последовательного циклического представления

Пусть в памяти размером в n единиц мы работаем с двумя последовательными циклическими очередями, работающими по принципу настраиваемых очередей, с элементами фиксированного размера, и каждой очереди выделен размер памяти. На каждом шаге дискретного времени происходят операции включения или исключения элементов в одну из очередей с заданными вероятностями. Исключение элементов происходит одновременно из обеих очередей во время так называемого цикла просмотра очередей. Количество исключаемых элементов из первой очереди равно c1, из второй – c2. Заметим, что в этой задаче мы не можем выбирать параметры c1 и c2 произвольно, т.к. они зависят от длительности цикла просмотра очередей в рассматриваемом сетевом устройстве t и скорости выходного трафика v (c1 + c2 = vt). Например, если t = 2 сек., а v = 100 Мбит/сек., то c1 + c2 = 200 Mбит. Это значит, что в зависимости от вероятностных характеристик очередей мы можем менять веса очередей, но сумма весов определяется характеристиками сети и устройства.

Будем искать такие c1, c2, чтобы вероятность потери в стационарном режиме в обеих очередях Ploss была минимальной. Шаги цикла просмотра очередей объединяем в один, чтобы обеспечить марковость процесса.

Пусть p1 и p2 – вероятности включения элемента в первую и вторую очереди соответственно, q – вероятность исключения из обеих очередей. Введем вероятность операции, не изменяющей длины очередей (например, чтение): r. Соответственно, p1 +p2 +q +r = 1.

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

    включение в первую очередь с вероятностью p1;

    включение во вторую очередь с вероятностью p2;

    исключение из первой очереди c1 и из второй очереди c2 элементов с вероятностью q;

    отсутствие событий с вероятностью r.

3. Математическая модель для последовательного циклического представления

Обозначим через x и y текущие длины первой и второй очередей соответственно. В качестве математической модели рассматриваем случайное блуждание в двумерном пространстве по целочисленной решетке в области 0 ≤ x k, 0 ≤ y k.

Определим схему переходов между состояниями. Пусть (x, y) – текущее состояние процесса, тогда блуждание в области 0 ≤ x k, 0 ≤ y k можно описать следующим образом:

r

(x,y) −→ (x,y)

x < k x = k

y < k y = k

Необходимо минимизировать число потерянных элементов при переполнении очередей. Иначе говоря, нужно найти такое c1 (c2 = vt c1), чтобы стационарная вероятность потери Ploss была минимальной. Таким образом, в случае двух очередей данная задача может быть рассмотрена как одномерный случай задачи целочисленного программирования, где функция критерия оптимальности задается алгоритмически.

Представим случайное блуждание в виде конечной регулярной марковской цепи с переходной матрицей P. Общее количество состояний в цепи N = (k + 1) · (k + 1).

Далее, согласно вышеуказанной схеме переходов составляется матрица переходных вероятностей P = P(c1,c2). При составлении матрицы для каждого конкретного состояния определяются те состояния, в которые процесс переходит при выполнении допустимых операций, и вычисляются соответствующие вероятности переходов.

Следующим шагом является решение уравнения αP = α, где α – предельный вектор для полученной марковской цепи.

Элемент вектора αi – это средняя доля времени, которое процесс проводит в состоянии i. Поскольку моменты прихода не зависят от числа элементов в очереди, для вычисления стационарной вероятности потери, нужно просуммировать элементы вектора α, соответствующие состояниям, когда первая очередь максимально заполнена, умножив их на p1, и элементы вектора α, соответствующие состояниям, когда вторая очередь максимально заполнена, умножив их на p2. При введенной нумерации это будут элементы с номерами k + (k + 1) · j, j = 0,..,k и последние k элементов вектора. Получаем все возможные вероятности потери в зависимости от c1,c2.

                                             k                                                                                N

                             Ploss(c1,c2) = ∑αk+(k+1)·j(c1,c2) · p1 + ∑ αj(c1,c2) · p2                                (1)

                                           j=0                                                                           j=Nk

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

Для проверки результатов была реализована имитационная модель данного процесса.

4.     Имитационная модель для представления друг за другом

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

Обозначим, x, y – текущие длины очередей, z – расстояние от головы первой очереди до хвоста второй. Потери происходят, если первая очередь догоняет вторую (z = 0) или вторая догоняет первую (x + y + z = n).

Определим схему переходов между состояниями. Пусть (x,y,z) – текущее состояние процесса. Тогда:

r

(x,y,z) −→ (x,y,z)

В качестве имитационной модели рассмотрим случайное блуждание по кругу по часовой стрелке, при этом:

1.    с вероятностью p1 увеличивается на 1 размер первой очереди, уменьшается на 1 расстояние между очередями;

2.    с вероятностью p2 увеличивается на 1 размер второй очереди;

3.    с вероятностью q уменьшается на c1 размер первой очереди и на c2 размер второй очереди, увеличивается на c2 расстояние между очередями;

4.    с вероятностью r процесс остается на месте.

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

Таблица 1: Сравнение вероятностей потерь для математической и имитационной модели

q

p1

p2

r

c1

c2

Ploss (матем.)

Ploss (имитац.)

0.1

0.2

0.4

0.3

2

6

0.017181547

0.017416110

0.1

0.2

0.5

0.2

1

7

0.046325628

0.046472030

0.1

0.3

0.2

0.4

6

2

0.004156068

0.004443540

0.1

0.3

0.3

0.3

4

4

0.014469843

0.014889290

0.1

0.3

0.4

0.2

3

5

0.041542893

0.041802270

0.1

0.3

0.5

0.1

3

5

0.089529228

0.089206010

0.1

0.4

0.1

0.4

7

1

0.009562229

0.009967280

0.1

0.4

0.3

0.2

5

3

0.041542893

0.041850260

0.2

0.2

0.4

0.2

1

7

0.000169100

0.000177550

0.2

0.3

0.4

0.1

3

5

0.000337448

0.000322020

0.3

0.1

0.2

0.4

1

7

0.000000002

0.000000003

0.3

0.3

0.2

0.2

7

1

0.000000318

0.000000370

0.3

0.3

0.3

0.1

4

4

0.000000921

0.000000850

                5.           Некоторые примеры численного анализа

В таблице 1 приведены значения вероятностей потерь для математической и имитационной моделей последовательного циклического представления при оптимальных значениях c1, c2. Так как аналитическое решение не было получено, нам нужно решать задачу для отдельных n, v, t. В данном примере используются значения n = 40, v = 8, t = 1. Используемые здесь вероятности являются теоретическими – для большей наглядности результатов. На практике, эти вероятности могут быть получены в результате предварительных статистических исследований.

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

Таблица 2: Сравнение вероятностей потерь для последовательного представления в памяти и представления друг за другом

q

p1

p2

r

c1

c2

Ploss (послед.)

Ploss (др. за др.)

0.1

0.2

0.4

0.3

2

6

0.017416110

0.016987100

0.1

0.2

0.5

0.2

1

7

0.046472030

0.045772260

0.1

0.3

0.2

0.4

6

2

0.004443540

0.004149240

0.1

0.3

0.3

0.3

4

4

0.014889290

0.014531450

0.1

0.3

0.4

0.2

3

5

0.041802270

0.041109970

0.1

0.3

0.5

0.1

3

5

0.089206010

0.088837330

0.1

0.4

0.1

0.4

7

1

0.009967280

0.008331470

0.1

0.4

0.3

0.2

5

3

0.041850260

0.041156220

0.2

0.2

0.4

0.2

1

7

0.000177550

0.000147900

0.2

0.3

0.4

0.1

3

5

0.000322020

0.000285870

0.3

0.1

0.2

0.4

1

7

0.000000003

0.000000001

0.3

0.3

0.2

0.2

7

1

0.000000370

0.000000360

0.3

0.3

0.3

0.1

4

4

0.000000850

0.000000760

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

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

                6.       Заключение

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

Список литературы

[1]      Cisco Systems Cisco IOS 12.0 Quality of Service. Cisco Press. 1999.

[2]      Олифер В.Г., Олифер Н.А. Компьютерные сети. Принципы, технологии, протоколы: Учебник для вузов. СПб.: Питер, 2010.

[3]      Танненбаум Э., Уэзеролл В. Компьютерные сети (5-е издание). СПб.: Питер, 2012. 960 с.

[4]      Аксенова Е.А., Драц А.В., Соколов А.В. Оптимальное управление n FIFO-очередями на бесконечном времени // Информационноуправляющие системы. 2009. № 6. С. 46–54.

[5]      Драц А.В., Соколов А.В. Математический анализ процесса работы с M FIFO-очередями // Стохастическая оптимизация в информатике. 2012. Т. 8. № 2. С. 75–82.

[6]      Барковский Е.А., Соколов А.В. Оптимальное управление двумя параллельными FIFO-очередями на бесконечном времени // Информационно-управляющие системы. 2015. № 5. С. 65–71.

[7]      Aksenova E.A., Sokolov A.V. The Optimal Implementation of Two FIFO-Queues in Single-Level Memory // Applied Mathematics. 2011. Vol. 2. P. 1297–1302.

[8]      Sokolov A.V., Drac A.V. The Linked List Representation of n LIFO-Stacks and/or FIFO-Queues in the Single-Level Memory // Information Processing Letters. 2013. Vol. 13. P. 832–835.

[9]      Сазонов А.М., Соколов А.В. Математическая модель оптимального управления настраиваемой очередью из двух последовательных циклических FIFO-очередей в общей памяти //

Информационно-управляющие системы. 2017. № 4. С. 44–50. DOI:

10.15217/issn1684-8853.2017.4.44

[10]   Соколов А.В. Математические модели и алгоритмы оптимального управления динамическими структурами данных. Петрозаводск: ПетрГУ, 2002. 216 с.

[11]   Барковский Е.А., Соколов А.В. Модель управления двумя параллельными FIFO-очередями, двигающимися друг за другом в общей памяти // Информационно-управляющие системы. 2016.

№ 1(80). С. 65–73. DOI: 10.15217/issn1684-8853.2016.1.65 (РИНЦ), http://www.i-us.ru/article1034

[12]   Барковский Е.А. Оптимальное управление двумя очередями, работающими по принципу настраиваемых очередей // Стохастическая оптимизация в информатике. 2016. №2 С .1–14 [13] Кемени Дж., Снелл Дж. Конечные цепи Маркова. Наука. 1960.

ABSTRACTS

Machine Learning Algorithms for Detection of Shockable Rhythms in Automated Defibrillators[9]

N. A. Alimov, V. A. Erofeeva, D. S. Shalymov, 2017.

St. Petersburg State University

Institute of Problems of Mechanical Engineering RAS alimov.nsm@gmail.com victoria@grenka.net dmitry.shalymov@gmail.com

Key words: pattern recognition, classification algorithms, machine learning, electrocardiograms, automated defibrillator.

Recently, the automation of a resuscitation process attracts more and more researchers due to the low level of survival rate in the cases of sudden cardiac arrest. Such condition mainly occurs when the heart’s electrical activity becomes chaotic. In such cases it is required to deliver a shock by a defibrillator to restore the heart’s normal activity as soon as possible. The defibrillators may be installed at public places, for example airports and supermarkets, to reduce the time before the resuscitation procedure begins. Nevertheless, the competence of a person delivering the shock may also be critical. Therefore, the automatic resuscitation procedure is more preferable. It is possible to apply machine learning methods to improve the survival rate. The goals of this paper are analyzing the existing classification methods and their validation on the real data, as well as the development of software for algorithm testing.

Bibliogr.: 23 refs.

Test Bench for Research of Adaptation Process of Planner with “Feathers” to the Changes in a Turbulent Airflow [10]

Amelin K. S., Amelina N. O., Deryugin D. E., Ivanskiy Y. V.

St. Petersburg State University

Institute of Problems of Mechanical Engineering RAS {konstantinamelin, ngranichina, deryugin.denis, ivanskiy.yuriy}@gmail.com

Key words: fast gradient descent method, multiagent systems, transition process, airplane with “feathers”, turbulence.

The article considers the operation of the bench simulating the wing of an aircraft with movable elements (“feathers”), under conditions of turbulent air flow. By rotating the movable elements in two planes, depending on the characteristics of the air flow over the wing element, the effect of the chatter is reduced. By using the feedback mechanism between adjacent wing elements, a transient process is implemented. The transition happens from an unbalanced state in which the difference in pressure deviations from their values in the laminar flow differs greatly in different parts of the wing, to a finite number of clusters with the same pressure deviation, and then to synchronization of all wing elements and final equalization of the pressure difference. Synchronization is implemented by using a multi-agent algorithm based on the fast gradient method. In the article the mathematical model of a wing with moving elements is described, the problem formulation of synchronization of wing elements is presented, the synchronization algorithm is given, the element base of the used sensors is listed, the results of simulation experiments are analyzed.

Bibliogr.: 24 refs.

An Implementation of the Memory Manager in the Work-Stealing Load Balancer[11]

E. A. Barkovsky barkevgen@gmail.com

Key words: optimal control, work-stealing deques, memory managers.

In this paper we describe the memory manager, implemented in the experimental work-stealing load balancer. The manager is based on the mathematical models of optimal control of work-stealing deques. The following methods of memory control are implemented in the manager and analyzed: optimal partition; partition in half. Also, the work of experimental and standard managers is compared.

Bibliogr.: 11 refs.

Optimal Control of Two Queues, Working on the Principle of Custom Queues [12]

A. M. Sazonov

Petrozavodsk sazonov@cs.karelia.ru

Key words: data structures, custom queues, random walks, regular Markov chains.

In this paper we propose the mathematical model and a way of solving for the problem of optimal partitioning of shared memory for the custom queue. It is done in the form of two queues (the case of their sequential cyclic representation). It is also considered the imitation model for “One after another” representation.

Bibliogr.: 13 refs.

Содержание

Алимов Н. А., Ерофеева В. А. , Шалымов Д. С. (СПбГУ, ИПМАШ) Анализвозможностей методов классификаци

Амелин К. С., Амелина Н. О., Дерюгин Д. Е., Иванский Ю. В. (СПбГУ, ИПМАШ)Экспериментальный стенд для

Барковский Е. А. Реализация менеджера памяти в work-stealingбалансировщике 56

Сазонов А. М. (ИПМИ КарНЦ РАН) Оптимальное управление двумяочередями, работающими по принципу наст

           Abstracts                                                                                                                                                                                76

Alimov N. A., Erofeeva V. A., Shalymov D. S. (SPb) Machine learningalgorithms for detection of shockable rhythms in

Amelin K. S., Amelina N. O., Deryugin D. E., Ivanskiy Y. V. (SPb) Test bench for research of adaptation process of p

Barkovsky E. A. (Petrozavodsk) An Implementation of the memory managerin the work-stealing load balancer 78

Sazonov A. M. (Petrozavodsk) Optimal control of two queues, workingon the principle of custom queues 79


                                                                    Н а у ч н о е        и з д а н и е

Стохастическая оптимизация в информатике

Том 13

Выпуск 1

Печатается без издательского редактирования

Обложка художника Е. А. Соловьевой Оригинал–макет О. Н. Граничина

Подписано в печать 1.12.17. Формат 60 × 84/16.

Бумага офсетная. Печать офсетная.

Усл. печ. л. 5. Тираж 100 экз.

Заказ №

Издательство СПбГУ. 199004, С.-Петербург, В.О., 6-я линия, 11/21

Тел. (812) 328–96–17; факс (812) 328–44–22

E-mail: editor@unipress.ru www.unipress.ru

По вопросам реализации обращаться по адресу:

С.-Петербург, В.О., 6-я линия, д. 11/21, к. 21

Телефоны: 328–77–63, 325–31–76

E-mail: post@unipress.ru

Типография Издательства СПбГУ

199061, С.-Петербург, Средний пр., 41



[1] Работа выполнена при поддержке РНФ, проект №16-19-00057.

[2] ©Н. А. Алимов, В. А. Ерофеева, Д. С. Шалымов, 2017.

[3] Работа выполнена при поддержке РНФ, проект №16-19-00057.

[4] ©Амелин К. С., Амелина Н. О., Дерюгин Д. Е., Иванский Ю. В., 2017

[5] Работа выполнена при поддержке РФФИ, проект №15-01-03404-а.

[6] ©Е. А. Барковский, 2017

[7] Работа выполнена при поддержке РФФИ, проект №15-01-03404-а.

[8] ©А. М. Сазонов, 2017

[9] ©N. A. Alimov, V. A. Erofeeva, D. S. Shalymov, 2017

[10] ©Amelin K. S., Amelina N. O., Deryugin D. E., Ivanskiy Y. V., 2017

[11] ©E. A. Barkovsky, 2017

[12] ©A. M. Sazonov, 2017