Основными барьерами являются коммутативные и ассоциативные свойства графовых операций.Эти два свойства определяют, является ли алгоритм тривиально распараллеливаемым или нет.На странице, на которую вы ссылаетесь, авторы заявляют следующее:
Обновления являются коммутативными и ассоциативными, и, следовательно, допускают масштабируемую реализацию [7].
Фактически цитируемая статьяв [7] - докторская диссертация, которая довольно хорошо ее объясняет:
В основе подхода этой диссертации лежит правило масштабируемой коммутативности: в любой ситуации, когда несколько операций коммутируют, т. е. нет никакого способа различитьих порядок выполнения с использованием интерфейса - у них есть реализация, которая не конфликтует во время этих операций - означает, что ни одно ядро не записывает строку кэша, которая была прочитана или записана другим ядром.Эмпирически, бесконфликтные операции масштабируются, поэтому эта реализация масштабируется.Или, более кратко, всякий раз, когда операции интерфейса коммутируют, они могут быть реализованы способом, который масштабируется.Это правило имеет интуитивный смысл: когда операции коммутируют, их результаты (возвращаемые значения и влияние на состояние системы) не зависят от порядка.Следовательно, связь между коммутативными операциями не нужна, и ее устранение приводит к бесконфликтной реализации.На современных многоядерных системах с разделяемой памятью бесконфликтные операции могут выполняться полностью из кэшей для каждого ядра, поэтому производительность бесконфликтной реализации будет линейно масштабироваться с количеством ядер.
Например произведение декартовых графов является коммутативной и ассоциативной операцией, полученные вершины могут быть вычислены в любом порядке, что упрощает распараллеливание в этом случае.Однако большинству операций с графами не хватает одного или обоих этих свойств.