Санкт-Петербург

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

---

Альманах научных работ молодых ученых 
XLVII научной и учебно-методической конференции Университета ИТМО. Том 1 
165 
Рис. 1. Зависимость времени, затрачиваемого на решение задачи идентификации модели 
погрешностей, от количества ФК в банке: учет стационарного характера модели ошибок (A); 
вынесение вычислений ковариационного канала ФК (B) 
Основным языком реализации алгоритма был выбран язык Python. Python широко 
используется в сфере выполнения научных расчетов. Основанием для этого служит наличие 
специализированного пакета NumPy, предназначенного в первую очередь для работы с 
матричными вычислениями. В своей работе пакет NumPy опирается на реализацию 
библиотеки базовых операций линейной алгебры (Basic Linear Algebra Subroutines, BLAS) на 
языках С или Fortran, что дает существенное ускорение по сравнению с нативной 
реализацией на Python. Для сравнения использовались следующие специализированные 
функции: dot – классическое перемножение двух матриц; linalg.multi_dot – перемножение 
нескольких матриц с автоматическим определением наиболее оптимального порядка 
операций; matmul – перемножение матриц, хранящихся в многомерных массивах, без 
необходимости их перебора в цикле. Поскольку функция matmul позволила избавиться от 
вычислений в циклах, она показала наиболее высокую эффективность (рис. 2, а). 
Использование функции multi_dot, напротив, замедлило работу алгоритма, что объясняется в 
первую очередь малыми размерностями перемножаемых матриц (не более 10), что не дает в 
полной мере воспользоваться преимуществами данной функции. 
а 
б 
Рис. 2. Зависимость времени, затрачиваемого на решение задачи идентификации модели 
погрешностей, от количества ФК в банке при: варьировании специализированных функций 
(а) и распараллеливании расчета банка ФК (б) 
Следует отметить, что вычисление параметров ФК в банке может осуществляться 
параллельно. Этому также способствует широкое распространение многоядерных 
процессоров, позволяющих выполнять единовременно независимо друг от друга несколько 

---

Альманах научных работ молодых ученых 
XLVII научной и учебно-методической конференции Университета ИТМО. Том 1 
166 
вычислительных процессов [5]. Потенциальный выигрыш от использования такого подхода 
пропорционален количеству доступных ядер процессора. Язык Python накладывает 
серьезные ограничения на использование многопоточности, тем не менее, пакет 
Multiprocessing предоставляет возможность распараллеливания работы алгоритма на уровне 
процессов, однако это приводит к дополнительным временным издержкам при 
межпроцессорном взаимодействии с памятью (рис. 2, б). 
Другим перспективным направлением использования аппаратных возможностей для 
ускорения работы видится эксплуатация вычислительных ресурсов графических 
процессоров. Аппаратная реализация графических процессоров традиционно ориентирована 
на обработку графических данных, что подразумевает вычислительно эффективную 
реализацию операций над матрицами и массивами, а также арифметических операций с 
плавающей запятой [5], что согласуется с основными ресурсоемкими операциями 
рассматриваемого алгоритма.