Автоматический выбор наиболее эффективных реализаций алгоритмов

Аннотация

Предложен подход к прогнозированию времени распределенных высокопроизводительных вычислений, не требующий проведения экспериментов на всех целевых вычислительных системах. Выбор оптимального алгоритма производится по информации об асимптотической сложности оцениваемых алгоритмов на основе использования методов машинного обучения. Предложенный в работе подход позволяет значительно сократить как количество экспериментов, так и размерность задач, которые решаются при оценке производительности вычислительной системы. Оценка времени выполнения алгоритмов по параметрам вычислительной системы позволяет определить, насколько вычислительная система эффективна при решении определенного класса задач без проведения экспериментов на ней. Возможно быстрое уточнение прогноза по минимальному числу экспериментов с малоразмерными задачами на целевой вычислительной системе. Предложенное решение может применяться и при автоматической настройке библиотеки перед ее использованием (подобно автоматической настройке в библиотеке ATLAS (Automatically Tuned Linear Algebra Software)). Выполнен сравнительный анализ результатов предсказания времени решения ряда задач на 84 вычислительных системах. Использование случайного леса в сочетании с методом наименьших квадратов показывает, что средняя относительная ошибка оценки времени выполнения составляет 17% при обучении на данных, соответствующих задачам малой размерности, и 9% при обучении на данных из всего диапазона изменения параметров алгоритма тестовой выборки. Полученные оценки позволяют выполнять выбор наиболее эффективной реализации алгоритма более чем в 80% случаев, а потери времени от ошибочного выбора не превосходят 6%.