Оптимизация алгоритма Singular Spectrum Analysis для ARM процессоров мобильных устройств

В настоящей работе рассматривается оптимизация вычислительных алгоритмов, используемых в распространенных методах анализа временных рядов. В качестве примера рассматривается метод Singular Spectrum Analysis, также известный как метод «Гусеница», реализованный и оптимизированный для процессоров, используемых в популярных сегодня смартфонах и планшетах. Для оптимизации были учтены рекомендации производителя процессоров - были использованы векторные регистры, произведена развертка вложенных циклов в наборы последовательных операций, а также подобран оптимальный набор флагов компиляции. Это позволило значительно увеличить производительность используемых алгоритмов, одним из которых является широко известный метод вращений Якоби. Данный метод используется для поиска собственных значений и собственных векторов матриц и является наиболее ресурсоемким в методе «Гусеница». Авторам статьи удалось увеличить скорость работы данного метода до 20 процентов в зависимости от размера окна («лага») исследуемого временного ряда, требуемой точности вычислений и других параметров, зависящих от условий конкретной задачи. В статье приведены описание и результаты вычислительного эксперимента, в рамках которого алгоритм метода «Гусеница» был реализован на языке программирования Objective C и представлены сравнительные результаты работы оптимизированного и неоптимизированного алгоритмов.

SSA algorithm optimization for ARM mobile processors

The present research dwells upon the optimization of the computing algorithms used in widespread methods of time series analysis. The "Singular Spectrum Analysis" method is considered as an example. This method is also known as the "Caterpillar" method, realized and optimized for the processors used in smartphones and tablets that are popular today. The recommendations of the producer of processors were taken into account for analysis - also there were used vector registers, there were made the evolvement of the home loops in sets of consecutive operations, and also the optimal set of compilation markers/flags is picked up. All of this allowed to considerably increase the productivity of the used algorithms - one of which isthe wide-spread Jacobi eigenvalue method. This method is used for search of eigenvalues and eigenvectors of a real symmetric matrix. This method is the most resourceintensive in the Caterpillar method. The authors of article managed to increase the work speed of this method to 20 percent depending on the size of a window of the studied time series, the demanded accuracy of calculations and the other parameters depending on the conditions of a specific task. In the research there are given the description and results of computing experiment, within which the algorithm of the Caterpillar method was realized in the Objective C computer language. There is also presented the comparative work results of the optimized and non-optimized algorithms.