Speaker
Description
Развитие современных вычислительных систем направлено на увеличение количества вычислителей и ускорителей, в том числе и разнородных: матричных ускорителей, MIMD, SIMD и др., что требует модернизации вычислительных алгоритмов с учетом структуры компьютера. В докладе рассматривается матричная модификация метода муравьиных колоний (ACO) для решения дискретной параметрической задачи, поиска дискретных значений параметров, обеспечивающих оптимальные значения критериев. Значения критериев при этом определяются в результате работы аналитических или имитационных моделей также запускаемых на вычислителе. Для решения параметрической задачи в методе ACO применяется графовая структура данных, в которой для каждого значения каждого параметра выделяется одна вершина, а муравей-агент должен выбрать по одному значению для каждого параметра. Данная структура позволяет рассматривать работу ACO в виде матричных операций и эффективно применять матричные, SIMT и SIMD ускорители. Предложенная матричная модификация, работающая с оптимизированной графовой структурой, позволяет достичь ускорения от 13 до 22 раз по сравнению с оригинальным методом при выполнении на CPU. Во многом такое ускорение обусловлено работой современного оптимизирующего компилятора C++. Предложен алгоритм представления матричного ACO для SIMD ускорителя и гетерогенного вычислителя. Проведены исследования на ускорителе с применением технологии NVIDIA CUDA, ускорение составило от 7 до 20 раз. Применение технологий AVX и OMP позволило обеспечить ускорение до 35 раз, по сравнению с классической реализацией ACO. Для применения ACO на GPU с применением технологии CUDA требуется пересмотр алгоритма, разделение данных по типам памяти, правильное разделение на потоки и блоки, решения проблем синхронизации и передачи данных между CPU и GPU. Предложен алгоритм для гетерогенного вычислителя, выполняющего матричные преобразования на CPU и вычисление пути муравья-агента на GPU, который показал ускорение от 30 до 70 раз. Исследования проводились на различных GPU персональных компьютеров и на высокопроизводительном кластере РЭУ. Проведено теоретическое исследование эффективности применения гетерогенного матричного ACO на гетерогенном вычислителе, состоящем из наборов MIMD ядер и SIMD ускорителей. Предложен подход к определению предела теоретического ускорения алгоритма и оптимальная структура гетерогенного реконфигурируемого вычислителя. Предложены рекомендации по выбору эффективного параллельного алгоритма ACO с учетом времени и принципов взаимодействия, топологии вычислителя и времени выполнения вычислений в модели в процессе определения значения целевой функции.
