МЕТОД ГЕНЕРАЦИИ СОЧЕТАНИЙДЛЯ ПАРАЛЛЕЛЬНЫХ ВЫЧИСЛЕНИЙНА ОСНОВЕ ОБРАТНОГО ЛЕКСИКОГРАФИЧЕСКОГО ПОРЯДКА

Результат исследований: Вклад в журналСтатьяНаучно-исследовательскаярецензирование

Аннотация

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

Отпечаток

parallel computing
limiting factor
method
experiment
software
productivity

ГРНТИ

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

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

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

Цитировать

@article{00b95fd9dc244bc1a5252b7bc23459ab,
title = "МЕТОД ГЕНЕРАЦИИ СОЧЕТАНИЙДЛЯ ПАРАЛЛЕЛЬНЫХ ВЫЧИСЛЕНИЙНА ОСНОВЕ ОБРАТНОГО ЛЕКСИКОГРАФИЧЕСКОГО ПОРЯДКА",
abstract = "Разработан параллельный алгоритм генерации комбинаторных объектов - сочетаний без повторений по три элемента. Основой алгоритма служит обратный лексикографический порядок следования сочетаний. Полученный алгоритм не содержит условных переходов и циклов, но использует функции извлечения корня и округления. Перспективной областью применения этого алгоритма является решение комбинаторных задач многопроцессорными системами с SIMD архитектурой, в частности, видеокартами. Разработанный алгоритм был проверен на практических задачах. В ходе вычислительного эксперимента было достигнуто значительное ускорение вычисления элементов сочетаний из их индексов относительно классических способов. Многопоточный эксперимент показал, что производительность алгоритма масштабируется, но лимитирующим фактором являются накладные расходы используемой программной среды. При использовании данного метода на видеокартах можно ожидать дальнейшего роста производительности. ·",
author = "Дубинин, {Иван Сергеевич} and Арапов, {Сергей Юрьевич} and Тягунов, {Андрей Геннадьевич}",
year = "2015",
language = "Русский",
pages = "40--46",
journal = "Вестник Санкт-Петербургского государственного университета технологии и дизайна. Серия 1: Естественные и технические науки",
issn = "2079-8199",
publisher = "Санкт-Петербургский государственный университет промышленных технологий и дизайна",
number = "4",

}

TY - JOUR

T1 - МЕТОД ГЕНЕРАЦИИ СОЧЕТАНИЙДЛЯ ПАРАЛЛЕЛЬНЫХ ВЫЧИСЛЕНИЙНА ОСНОВЕ ОБРАТНОГО ЛЕКСИКОГРАФИЧЕСКОГО ПОРЯДКА

AU - Дубинин, Иван Сергеевич

AU - Арапов, Сергей Юрьевич

AU - Тягунов, Андрей Геннадьевич

PY - 2015

Y1 - 2015

N2 - Разработан параллельный алгоритм генерации комбинаторных объектов - сочетаний без повторений по три элемента. Основой алгоритма служит обратный лексикографический порядок следования сочетаний. Полученный алгоритм не содержит условных переходов и циклов, но использует функции извлечения корня и округления. Перспективной областью применения этого алгоритма является решение комбинаторных задач многопроцессорными системами с SIMD архитектурой, в частности, видеокартами. Разработанный алгоритм был проверен на практических задачах. В ходе вычислительного эксперимента было достигнуто значительное ускорение вычисления элементов сочетаний из их индексов относительно классических способов. Многопоточный эксперимент показал, что производительность алгоритма масштабируется, но лимитирующим фактором являются накладные расходы используемой программной среды. При использовании данного метода на видеокартах можно ожидать дальнейшего роста производительности. ·

AB - Разработан параллельный алгоритм генерации комбинаторных объектов - сочетаний без повторений по три элемента. Основой алгоритма служит обратный лексикографический порядок следования сочетаний. Полученный алгоритм не содержит условных переходов и циклов, но использует функции извлечения корня и округления. Перспективной областью применения этого алгоритма является решение комбинаторных задач многопроцессорными системами с SIMD архитектурой, в частности, видеокартами. Разработанный алгоритм был проверен на практических задачах. В ходе вычислительного эксперимента было достигнуто значительное ускорение вычисления элементов сочетаний из их индексов относительно классических способов. Многопоточный эксперимент показал, что производительность алгоритма масштабируется, но лимитирующим фактором являются накладные расходы используемой программной среды. При использовании данного метода на видеокартах можно ожидать дальнейшего роста производительности. ·

UR - https://elibrary.ru/item.asp?id=25751229

M3 - Статья

SP - 40

EP - 46

JO - Вестник Санкт-Петербургского государственного университета технологии и дизайна. Серия 1: Естественные и технические науки

JF - Вестник Санкт-Петербургского государственного университета технологии и дизайна. Серия 1: Естественные и технические науки

SN - 2079-8199

IS - 4

ER -