Новая формула проверит эффективность параллельных алгоритмов без суперкомпьютера

Доктор физико-математических наук, профессор Леонид Соколинский вывел формулу, которая поможет математикам и программистам оценить эффективность параллельных алгоритмов. Четыре года ученый работал в Лаборатории суперкомпьютерного моделирования ЮУрГУ над выводом этой формулы. Результаты исследования были опубликованы в высокорейтинговом журнале Journal of Parallel and Distributed Computing (Q1).

Параллельные алгоритмы для суперкомпьютера

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

«Современная наука, экономика и промышленность требуют решения оптимизационных задач огромной вычислительной сложности. Например, задача оптимизации работы всех светофоров в городе таким образом, чтобы можно было максимально избежать скопления транспорта и пробок. Для ее решения математику и программисту нужно написать сложный алгоритм и разделить его на параллельные части, которые выполняются на разных процессорах. И это очень непросто. Чем больше в суперкомпьютере процессоров, тем сложнее придумать алгоритм, который эти тысячи, десятки тысяч и миллионы процессоров сможет эффективно использовать. Однако если параллельный алгоритм не очень хорошо спроектирован, то он окажется неэффективным даже на суперкомпьютере», – говорит профессор Соколинский.

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

Экономия времени и средств

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

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

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

Южно-Уральский государственный университет – это университет цифровых трансформаций, где ведутся инновационные исследования по большинству приоритетных направлений развития науки и техники. В соответствии со стратегий научно-технологического развития РФ университет сфокусирован на развитии крупных научных междисциплинарных проектов в области цифровой индустрии, материаловедения и экологии.

Исследования в области новых технологий в числе приоритетов Уральского межрегионального научно-образовательного центра мирового уровня (УМНОЦ) «Передовые производственные технологии и материалы», созданного объединенными усилиями УрФУ, ЮУрГУ, КГУ, Уральского отделения РАН и промышленных корпораций Челябинской, Свердловской и Курганской областей.