Для решения задач с ограниченными неопределённостями и неоднозначностями в данных в последние десятилетия всё более широко применяются методы интервального анализа, математической дисциплины, возникшей около полувеканазад из необходимости учёта погрешностей расчётов на цифровых ЭВМ.
В последние годы интервальный анализ «перерос» задачи, которые вызвали его появление на свет, и успешно применяется не только для корректной обработки ошибок вычислений на ЭВМ с конечной разрядной сеткой, но и для решения задач с неточными входными данными (заданными в некоторых диапазонах), а также для решения ряда трудных традиционных математических задач, которые плохо поддаются другим методам.
Характерной чертой методов интервального анализа является рассмотрение отрезков вещественной прямой --- интервалов --- как целостных объектов, что естественно вызывает необходимость их оформления в виде отдельного типа данных со своими специфическими арифметическими и теоретико-множественными операциями, отношениями и т.п. Один из популярных путей воплощения в жизнь этой идеи --- создание на основе существующих языков программирования высокого уровня библиотек, реализующих интервальный тип данных и операции с ним. Такие библиотеки получили в последнее время большое распространение в качестве базового средства для реализации интервальных алгоритмов на ЭВМ.
В работе представлен сравнительный обзор двух наиболее популярных интервальных библиотек:
Автор приводит обзор возможностей и сравнение библиотек, делая основной упор на сравнении их производительности, которая измерялась временем исполнения тестового пакета из 10 специально подобранных программ. Тестирование осуществлялось в ОС семейства Linux, с компиляторами семейства GNU GCC, Intel C/C++/Fortran, на 4 различных компьютерных платформах: IA32 (Intel Prescott), IPF (Intel Itanium 2), EM64T (Intel Nocona), AMD64 (AMD Opteron).
В рамках данной работы предлагается сравнение производительности ИА указанных выше библиотек; введем обозначения для ИА соответствующих библиотек: filib++, boost.org.
1.2 Тонкости функционирования ИА: Режимы округленияИнтервалы на языке высокого уровня описываются специальным типом данных, в простейшем случае представляющем собой сложный тип данных (класс или запись) состоящую из 2 чисел базового типа, задающего границы интервала. В качестве базового типа, как правило, выступает вещественный тип одинарной или двойной точности, реже допускаются интегральные типы данных или типы, определенные пользователем. Выполнение операций {+, -, *, /} над интервальным типом реализовано согласно правилам ИА. Отдельным моментом программной реализации интервальных объектов является механизм округления, задействованный при вычислении интервальных арифметических операций.
Рассмотрим сложение двух интервалов: a=[a1,a2] и b=[b1,b2]. Результат сложения: с=[c1,c2]=[a1+b1,a2+b2]. Для того, чтобы результирующий интервал с включал в себя истинный (математический) результат сложения интервалов a,b необходимо, чтобы при вычислении с1=(a1+b1) ЭВМ производило округление в сторону –БЕСКОНЕЧНОСТИ, а при вычислении с2=(a2+b2) в сторону +БЕСКОНЕЧНОСТИ.
Необходимо сделать некоторое замечание относительно процедуры округления.Процедуру округления можно производить аппаратно или программно. Программное реализация предполагает эмуляцию процесса округления средствами языка, что, как правило, есть более затратная по времени процедура, нежели аппаратное округления с помощью процессора. За аппаратное округление в рамках семейства Intel-P6 отвечает регистр MXCSR. MXCSR – это регистр состояния и управления, он используется для установки флагов обнаружения арифметических исключений, флагов режимов обработки арифметических исключений, режима округления, режима flush-to-zero и для просмотра флага состояния. Поле управления округлением (RC) регистра MXCSR (биты 13 и 14) управляет, как округляется результат инструкции с плавающей точкой. Поддерживается четыре режима округления: округление до ближайшего, до меньшего или равного, до большего или равного, и в сторону нуля. Режимом по умолчанию является «округление до ближайшего». Смена режима округления – это достаточно дорогостоящая операция, требующая перезаписи всего регистра MXCSR.
Итак, для выполнения операции сложения двух интервалов необходимо выполнить последовательность из 6 действий:
Действия 1,6 необходимы для того, чтобы выполнение интервальных операций не влияло на выполнение остальных арифметических операций в программе.
1.3 filib++
В библиотеке filib++ существует 7 режимов округления, из которых:
Данный режим округления используется по умолчанию. Для округления используются все 6 шагов Схемы 1
native_directedРежим функционирует так же как «native_switched», за исключением того, что пропущены шаги 1,6 Схемы 1, за счет чего скорость выполнения интервальных арифметических операций, потенциально, должна быть выше. Но, из-за того, что пропущены шаги 1,6 Схемы 1, в данном режиме не происходит сохранения текущего режима округления, иными словами, выполнение арифметических действий над интервалами влияет на выполнение других численных операций в программе.
native_onesided_switchedВ данном режиме пропущен шаг 4 Схемы 1, что, потенциально, позволяет увеличить скорость выполнения операций ИА. Округление в сторону +? осуществляется следующим образом: +БЕСКОНЕЧНОСТИ (a2+b2)=-[-БЕСКОНЕЧНОСТИ (-(a2+b2))].
native_onesided_globalДанный режим аналогичен предыдущему, за исключением того, что, дополнительно, пропущены шаги 1,6 Схемы 1. Данный режим, так же как и режим «native_directed» влияет на выполнение других численных операций в программе.
Режимы программного округленияРежимы «multiplicative», «pred_succ_rounding» используются в случае, когда архитектура не поддерживает аппаратное округление.
В рамках данного тестирования от filib++ native_onesided_global как наиболее быстрый среди других режимов библиотеки.
1.4 IA of boost.orgВ библиотеке стоит выделить два основных режима:
Для точных вычислений интервалов над типами «float», «double» следует использовать режим «rounded_math». Интервальный тип задается классом «boost::numeric::interval
Для быстрой работы с «широкими» интервалами без слежения за округлением и точностью следует использовать «save_state_nothing
Итак, задачей автора было сравнить производительность ИА 2-х интервальных; производительность характеризовалась временем исполнения тестового пакета состоящего из 10 программ.
Тестирование проводилось в 4 различных тестовых средах:В таблицах результатов тестов, время выполнения каждого теста для одного из режимов берется за базовое и время выполнения тестов на других режимов вычисляться относительно базового. Знаком «(+)» отмечен лучший результат по данному Тесту среди всех режимов. Стоит сразу отметить, что режим «boost.org Fast mode, double» не производит смену мод округления в процессе выполнения интервальных операций, находясь тем самым в «другой» весовой категории, чем все остальные режимы (теоретически, данный режим обеспечивает меньшую точность, чем все остальные режимы данного тестирования).
2.2. Результаты на IA32| Test # | filib++ Native one_sided global, double, Extended,gcc |
filib++ Native one_sided global, double, Extended,icc |
boost.org Standard mode, double,gcc –O3 |
boost.org Standard mode, double,icc –O3 |
boost.org Fast mode, double,gcc –O3 |
boost.org Fast mode, double, icc –O3 |
| Test1 | 100% | 104.98% | 100.13% | 100.83% | 92.21%(+) | 119.67% |
| Test2 | 100% | 120.71% | 101.03% | 100.9% | 90.38%(+) | 95.77% |
| Test3 | 100% | 116.89% | 99.68% | 96.98% | 90.23%(+) | 99.62% |
| Test4 | 100% | 98.98% | 101.02% | 98.35% | 90.41%(+) | 90.16% |
| Test5 | 100% | 89.87% | 92.38% | 92.99% | 81.83%(+) | 85.49% |
| Test6 | 100% | 69.99% | 200.24% | 197.70% | 4.86% | 3.42%(+) |
| Test7 | 100% | 25.61% | 33.43% | 26.32% | 21.38% | 20.2%(+) |
| Test8 | 100% | 65.47% | 69.78% | 66.56% | 57.86% | 57.92%(+) |
| Test9** | 100% | 67.48% | 196.33% | 193.23% | 9.56% | 7.07%(+) |
| Test10** | 100% | 66.99% | 193.27% | 190.12% | 10.4% | 7.72%(+) |
| Average: | 100% | 82.98% | 118.73% | 116.4% | 54.91% | 58.70% |
Процессоры на основе архитектур EM64T (старое название - IA-32e) и AMD64 (старое название - х86-64) представляют собой 32-разрядные процессоры с поддержкой 64-разрядного расширения (в компиляторах Intel называемый режим 32e). Они рассчитаны на поддержку как 32-разрядной адресации, так и 64-разрядной прямой адресации больших объемов оперативной памяти (в рамках 32-разрядной адресации максимально возможный объем оперативной памяти равен 4Гбайтам). Процессоры с данной архитектурой полностью поддерживают функционирование в режиме IA-32 и обладают возможность работать в режиме IA-32e. В рамках режима IA-32 процессор может работать в защищенном режиме (16 бит), в режиме реальной адресации (32 бита), режиме виртуальных 8086. Режим IA-32e может использоваться только в среде 64-разрядных ОС.
Аббревиатура IPF расшифровывается как Itanium Processor Family. Семейство процессоров Itanium представляет собой 64-рязрядные процессоры, поэтому, в рамках данного тестирования, компиляция и запуск тестов на IPF платформе будет только происходить в родном, 64-разрядном режиме.
2.4 Результаты на EM64T| Test # | boost.org Standard mode, double,gcc –O3, -m32 |
boost.org Standard mode, double,gcc –O3, -m64 |
boost.org Fast mode, double,gcc –O3, -m32 |
boost.org Fast mode, double, gcc –O3, -m64 |
| Test1 | 100% | 76.32% | 97.33% | 75.67%(+) |
| Test2 | 100% | 79.13% | 104.1% | 78.74%(+) |
| Test3 | 100% | 75.28% | 96.19% | 74.75%(+) |
| Test4 | 100% | 78.83% | 103.66% | 78.60%(+) |
| Test5 | 100% | 78.36% | 102.61% | 76.14%(+) |
| Test6 | 100% | 7.3% | 2.88% | 1.92%(+) |
| Test7 | 100% | 133.29% | 79.42% | 62.02% |
| Test8 | 100% | 89.61% | 98.54% | 74.42%(+) |
| Test9** | 100% | 7.67% | 5.10% | 3.73% |
| Test10** | 100% | 8.16% | 5.50% | 4.29% |
| Average: | 100% | 63.4% | 69.53% | 53.03% |
| Test # | boost.org Standard mode, double,icc –O3, -32 |
boost.org Standard mode, double,icc –O3, -32e |
boost.org Fast mode, double,icc –O3, -32 |
boost.org Fast mode, double, icc –O3, -32e |
| Test1 | 112.27% | 86.85% | 114.08% | 86.8% |
| Test2 | 116.42% | 89.48% | 118.45% | 88.92% |
| Test3 | 123.27% | 85.20% | 109.76% | 85.95% |
| Test4 | 120.89% | 89.75% | 115.26% | 89.02% |
| Test5 | 114.78% | 90.49% | 117.65% | 87.11% |
| Test6 | 97.44% | 8.02% | 1.95% | 1.58% |
| Test7 | 91.02% | 152.9% | 69.61% | 54.56(+) |
| Test8 | 111.86% | 101.06% | 108.85% | 82.95% |
| Test9** | 101.49% | 8.46% | 5.07% | 2.98%(+) |
| Test10** | 100.7% | 8.95% | 4.33% | 3.42%(+) |
| Average: | 109.01% | 72.12% | 76.50% | 58.33% |
| Test # | boost.org Standard mode, double,gcc –O3, -m32 |
boost.org Standard mode, double,gcc –O3, -m64 |
boost.org Fast mode, double,gcc –O3, -m32 |
boost.org Fast mode, double, gcc –O3, -m64 |
| Test1 | 100% | 75.96% | 94.38% | 75.44% |
| Test2 | 100% | 79.2% | 98.84% | 78.85% |
| Test3 | 100% | 81.85% | 98.98% | 77.70% |
| Test4 | 100% | 80.2%(+) | 100.42% | 81.05% |
| Test5 | 100% | 84.27% | 100.6% | 80.64% |
| Test6 | 100% | 222.88% | 65.25% | 103.39% |
| Test7 | 100% | 168.17% | 84.35% | 68.44% |
| Test8 | 100% | 90.91% | 95.58% | 75.01% |
| Test9** | 100% | 176.03% | 118.6% | 73.11% |
| Test10** | 100% | 129% | 70.08% | 58.72% |
| Average: | 100% | 118.85% | 92.71% | 77.24% |
| Test # | boost.org Standard mode, double,icc –O3, -32 |
boost.org Standard mode, double,icc –O3, -32e |
boost.org Fast mode, double,icc –O3, -32 |
boost.org Fast mode, double, icc –O3, -32e |
| Test1 | 95.75% | 77.07% | 93.01% | 75.18%(+) |
| Test2 | 99.52% | 79.81% | 97.61% | 78.72%(+) |
| Test3 | 99.66% | 80.49% | 97.62% | 77.63%(+) |
| Test4 | 102.19% | 82.89% | 101.63% | 82.89% |
| Test5 | 101.28% | 83.85% | 100.78% | 80.14% |
| Test6 | 91.95% | 226.69% | 51.69%(+) | 48.73% |
| Test7 | 91.51% | 168.44% | 55.84% | 49.20%(+) |
| Test8 | 97.91% | 96.42% | 93% | 74.27%(+) |
| Test9** | 99.82% | 251.05% | 80.31% | 65.54% |
| Test10** | 79% | 137.38% | 111.82% | 51.12%(+) |
| Average: | 95.86% | 128.41% | 88.33% | 68.34% |
На сегодняшний день, процессорные 64-разрядные процессорные решения набирают все большую популярность. Интервальные вычисления весьма критичны к архитектуре процессора, в том плане, что качественное повышения скорости выполнения интервальных вычислений откроет новые горизонты применения интервального подхода. Скорость интервальных вычислений, в частности, зависит от оптимальности интервальных алгоритмов по отношении к существующим реализациям интервальных библиотек, функционированию современных компиляторов (насколько компиляторы способны сформировать «хороший» машинный код для специфичных интервальных программных конструкций) и от того насколько процессор может взять на себя выполнение примитивных интервальных операций (к примеру, векторизация интервальных вычислений, способность с наименьшими затратами переключать моды округлений).
В этом плане, интересно сравнение производительности интервальных библиотек на родственных решениях от Intel и AMD: на процессорах EM64T Nocona и AMD64 Opteron. Сравнение, которое будет приведено ниже, не претендует на полноту и объективность и является лишь почвой для размышлений. Сравнение будет производится по результатам тестов «boost.org Standard mode». Из Таблиц 6,7 видно, что производительность режима “boost.org Standard mode, double” лучше на AMD64 Opteron чем на EM64T, на обоих режимах, 32 и 32е.
| Test # | boost.org Standard mode, double,icc –O3, 32, EM64T |
boost.org Standard mode, double,icc –O3, 32, Opteron |
| Test1 | 100% | 71.23%(+) |
| Test2 | 100% | 70.48%(+) |
| Test3 | 100% | 63.77%(+) |
| Test4 | 100% | 67.30%(+) |
| Test5 | 100% | 69.85%(+) |
| Test6 | 100% | 3.08%(+) |
| Test7 | 100% | 104.70% |
| Test8 | 100% | 71.54%(+) |
| Test9** | 100% | 4.44%(+) |
| Test10** | 100% | 4.98%(+) |
| Average: | 100% | 53.14% |
| Test # | boost.org Standard mode, double,icc –O3, 32, EM64T |
boost.org Standard mode, double,icc –O3, 32, Opteron |
| Test1 | 100% | 74.07%(+) |
| Test2 | 100% | 73.31%(+) |
| Test3 | 100% | 74.14%(+) |
| Test4 | 100% | 73.76%(+) |
| Test5 | 100% | 73.65%(+) |
| Test6 | 100% | 92.40%(+) |
| Test7 | 100%(+) | 114.62% |
| Test8 | 100% | 78.23%(+) |
| Test9** | 100%(+) | 136.95% |
| Test10** | 100% | 98.67%(+) |
| Average: | 100% | 88.98% |
| Test # | filib++ Native one_sided global, double, Extended,gcc |
filib++ Native one_sided global, double, Extended,icc |
boost.org Standard mode, double,gcc –O3 |
boost.org Standard mode, double,icc –O3 |
boost.org Fast mode, double,gcc –O3 |
boost.org Fast mode, double, icc –O3 |
|
| Test1 | 100% | 96.34% | 96.76% | 96.76% | 97.02% | 90.57%(+) | |
| Test2 | 100% | 96.52% | 97.73% | 96.89% | 97.76% | 90.77%(+) | |
| Test3 | 100% | 94.91% | 95.39% | 95.09% | 96.02% | 88.70%(+) | |
| Test4 | 100% | 96.28% | 96.58% | 96.43% | 96.65% | 90.33%(+) | |
| Test5 | 100% | 90.18% | 91.60% | 92.10% | 88.91% | 83.91%(+) | |
| Test6 | 100% | 18.49% | 47.81% | 39.20% | 12.33% | 9.05%(+) | |
| Test7 | 100% | 26.46% | 45.89% | 39.06% | 15.07% | 9.16%(+) | |
| Test8 | 100% | 65.44% | 73.36% | 71.88% | 60.8% | 54.81%(+) | |
| Test9** | 100% | 20.00% | 43.35% | 36.49% | 26.58% | 15.97%(+) | |
| Test10** | 100% | 19.97% | 43.07% | 35.60% | 26.61% | 16.22%(+) | |
| Average: | 100% | 64.74% | 73.15% | 69.95% | 61.78% | 54.95% |