Почему важно учитывать степень вершин при анализе графовых алгоритмов?

Учёт степени вершин при анализе графовых алгоритмов важен по нескольким причинам:

• Балансировка параллельной нагрузки. www.dissercat.com istina.msu.ru Если обработка списков рёбер различных вершин графа осуществляется параллельно различными вычислительными устройствами, могут возникать задержки из-за простоя нитей, выделенных для обработки вершин с небольшой степенью, в то время как нити, выделенные для обработки вершин с большой степенью, ещё не завершили свою работу. istina.msu.ru Разбиение вершин на группы по степени позволяет производить эффективную балансировку параллельной нагрузки, выделяя на обработку вершин различных групп разные вычислительные мощности. www.dissercat.com
• Эффективная реализация алгоритмических абстракций. www.dissercat.com Для эффективной реализации выделенных алгоритмических абстракций реализация подмножества вершин автоматически должна отслеживать количество вершин, помещённых в данное подмножество, одновременно не позволяя поместить в подмножество вершины с дублирующимися номерами. www.dissercat.com
• Оптимизация работы с памятью. istina.msu.ru Косвенные обращения к памяти, неизбежно возникающие при запросах о состоянии вершин графа, являются одним из главных факторов, снижающих производительность графовых алгоритмов на современных вычислительных архитектурах. istina.msu.ru Хранение в смежных участках памяти информации о наиболее часто запрашиваемых вершинах графа (обычно с самой высокой степенью) позволяет решить эту проблему. istina.msu.ru