Разработан параллельный алгоритм генерации комбинаторных объектов - сочетаний без повторений по три элемента. Основой алгоритма служит обратный лексикографический порядок следования сочетаний. Полученный алгоритм не содержит условных переходов и циклов, но использует функции извлечения корня и округления. Перспективной областью применения этого алгоритма является решение комбинаторных задач многопроцессорными системами с SIMD архитектурой, в частности, видеокартами. Разработанный алгоритм был проверен на практических задачах. В ходе вычислительного эксперимента было достигнуто значительное ускорение вычисления элементов сочетаний из их индексов относительно классических способов. Многопоточный эксперимент показал, что производительность алгоритма масштабируется, но лимитирующим фактором являются накладные расходы используемой программной среды. При использовании данного метода на видеокартах можно ожидать дальнейшего роста производительности. ·
Переведенное названиеMethod of generating combinations for parallel computing based on the reverse lexicographic order
Язык оригиналаРусский
Страницы (с-по)40-46
Число страниц7
ЖурналВестник Санкт-Петербургского государственного университета технологии и дизайна. Серия 1: Естественные и технические науки
Номер выпуска4
СостояниеОпубликовано - 2015

    Уровень публикации

  • Перечень ВАК

    ГРНТИ

  • 27.45.00 Комбинаторный анализ. Теория графов

ID: 1793262