В работе представлен новый подход к параллельному созданию корневых деревьев. Предложены два рекурсивных алгоритма генерации корневых деревьев в частичном и полном лексикографических порядках. В случае одного процессора представленные алгоритмы генерируют каждое дерево в среднем за постоянное время. Первый алгоритм, основанный на традиционном перечислении по высоте для генерации корневых деревьев в частично лексикографическом порядке, не может обеспечить балансировку нагрузки для улучшения распределения вычислительных нагрузок между несколькими процессорами. Второй алгоритм может быть эффективно распараллелен в случае использования нескольких (2, 4, 9, 20, 48...) процессоров для достижения хорошей балансировки нагрузки, что значительно сокращает время вычислений.
Дьяков В.В. (науч. рук. Горшков К.С.) Сбалансированная по нагрузке рекурсивная генерация корневых деревьев // Сборник тезисов докладов конгресса молодых ученых. Электронное издание. – СПб: Университет ИТМО, [2020]. URL: https://kmu.itmo.ru/digests/article/4208