Архив статей журнала
В статье предлагается алгоритм поиска целочисленного решения, использующий идею округления координат точки оптимального нецелочисленного решения и построения луча, направленного вглубь области допустимого решения. Алгоритм основан на итеративном процессе округления координат точки в направлении построенного луча. В ходе исследования обнаружено, что движение в сторону направления луча без перебора всех возможных вариантов упрощает алгоритм и позволяет избежать ветвления. Это выделяет данный подход из других существующих на данный момент открытых методов, таких как методы отсечений и ветвей и границ. В процессе работы осуществлялись описание и экспериментальная проверка данного алгоритма и возможности его применения при разных конфигурациях области допустимых решений. Теоретическая значимость исследования заключается в разработке нового алгоритма, который не требует выполнения симплекс-метода на каждом этапе и на каждом шаге использует луч вместо плоскости, что предотвращает рост пространственной сложности задачи по сравнению с другими методами. В ходе исследования стало видно, что предложенный алгоритм имеет ограничения, однако основная идея доказала свою работоспособность, и в дальнейшем планируется развивать ее.
Работа посвящена повышению эффективности выполнения современных расчетных приложений на высокопроизводительных вычислительных системах. В качестве инструмента повышения эффективности рассматривается векторизация программного кода. С ее помощью однотипные скалярные операции объединяются в векторные аналоги, кратно повышая производительность. Целевой платформой являются современные микропроцессоры Intel, для которых поддержан уникальный набор векторных инструкций AVX 512. Предлагается подход к векторизации газодинамического решателя, использующего метод погруженных границ и противопотоковую схему Steger-Warming в трехмерном виде. Решатель обладает сложным программным контекстом, автоматическая векторизация которого невозможна. Рассматриваются реализация решателя, а также подходы к организации кода и приведению его к виду, пригодному для автоматической векторизации компилятором icc. Для обеспечения автоматического применения векторизации к программному коду решателя были применены три основных эквивалентных преобразования. Во-первых, вычисления, одинаковые для всех итераций проведения расчетов, включая матричные операции, были локализованы и вынесены на этап подготовки вычислений. Во-вторых, основные функции решателя были организованы в виде плоских циклов, а структуры данных представлены в виде наборов массивов. В-третьих, к гнездам циклов была применена оптимизация расщепления по условию, с помощью которой можно уменьшить степень разветвленности управления внутри тела цикла. Данные преобразования позволяют компилятору автоматически применять векторизацию кода. В результате выполненной работы достигнуто ускорение решателя в три раза за счет векторизации при вычислениях на вещественных числах двойной точности.