Два слова о параллельной обработке связанных списков

Предлагаю отказаться от последовательных связанных списков в пользу древовидных структур для всех случаев использования неупорядоченных данных при их паралельной обработке.

Связанный список – это динамическая структура данных, которая используется для хранения линейной коллекции данных (как правило неупорядоченных). Простейшая вариация такого списка предполагает только наличие «головного» указателя, ссылающегося на первый элемент списка. Каждый элемент состоит из данных и указателя на «следующий» элемент коллекции. Если этот указатель нулевой (NULL или соответствующий эквивалент), то это является индикатором того, что данный элемент – последний в списке. Для предоставления более быстрого доступа к требуемому элементу в списке могут использоваться дополнительные указатели. Примером такого указателя может быть «концевой» указатель, ссылающийся на последний элемент. С его помощью можно увеличить скорость выполнения операций добавления элементов в конец списка.

Для чего можно применять такой список и чем хуже обычный массив? Связанные список не предоставляет произвольного доступа к любому элементу в списке, однако позволяет добавлять новые элементы, удалять или переупорядочивать существующие за время О(1). И здесь нету никаких ограничений на количество элементов в списке, кроме, разумеется, естественных ограничений доступной памяти в системе. Таким образом, учитывая ограничения по доступу и перемещению данных, массивы и связанные списки взаимодополняемые структуры. Разработчики программного обеспечения вправе сами решать какая из структур лучше походит для применения в той или иной ситуации.

А имеет ли смысл использовать связанные списки в наши дни, с приходом эпохи параллельных вычислений? Дэн Гроссман из университета Вашингтона, говорит: «Нет». Впервые я услышал об этом заявлении от коллеги, который готовил презентацию с професором Гроссманом на конференции SIGCSE. Суть заявления сводится к тому, что везде где может использоваться связанный список, его использование можно заменить на использование дерева. Давайте попробуем разобраться насколько данная идея имеет смысл.

Связанный список последовательная структура данных которая очень хорошо подходит для последовательной обработки данных. Дерево отлично вписывается в идиому параллелизма fork-join, о которых я писал в своих предыдущих публикациях (прим. переводчика – см. публикации Клэя на http://drdobbs.com). Как и в случае со связанным списком, дерево может динамически изменять свою структуру. Время необходимое на добавление нового элемента не будет постоянным, однако в случае с упорядоченным деревом оно не превысит О (log n), что намного лучше алгоритма со сложностью  O (n), когда имеется два указателя и их необходимо переместить в самый конец списка для добавления нового элемента. А что по поводу других операций, для которых может применяться связанный список? Могут ли эти операции также успешно использовать вместо списка дерево при параллельных вычислениях? Ниже представлены некоторые операции над связанным списком подбного рода и примеры того, как они могут быть «сэмулированны» с использованием дерева.

Обработка всех элементов. В последовательном процессе, для обработки каждого элемента в связанном списке, необходимо начинать с «головного» элемента, выполнять над ним требуемые операции, передвинуть указатель на следующий элемент и повторять данный процесс до тех пор пока не будут выполнены требуемые операции над последним элементом списка. Если в выполняемые операции не вовлечены другие элементы списка, то операции над элментами можно выполнять паралельно в разных потоках или процессах. Если данные упорядочены в виде дерева, то в таком случае до или после обработки текущего элемента можно параллельно в отдельном потоке выполнить обработку дочерних узлов текущего элемента. Как только некоторое пороговое количество активных отоков достигнуто, новые потоки перестают создаваться до тех пор пока запущеные процессы обработки не будут завершены.

В целях улучшения баланса загрузки системы при обработке элементов, дерево имеет смысл делать также максимально сбалансированным. Если потоки создаются на одном и том же уровне дерева, то каждый поток сможет обработать одинаковое количество элементов. Существует большое количество видов сбалансированного дерева, которые могут использоваться для подобных задач. В открытом доступе можно найти много справочных материалов, которые в деталях описывают возможные варианты. При выборе того или иного типа дерева необходимо учитвыать набор операций, которые необходимо осуществлять над будущей структурой данных и также держать в голове информацию о том, могут ли паралельные потоки обращаться к различным элементам дерева параллельно.

Поиск. В данном случае, я имею ввиду неупорядоченный поиск. (Если у вас есть отсортированные данные, то в таком случае одного потока будет более чем достаточно для того, что бы спустится вниз до требуемого элемента, создание отдельных потоков в этом случае выглядит более чем избыточным). Для бинарного дерева существует три алгоритма поиска: preorder, inorder и postorder. Все они являются рекурсивными, а значит этот процесс можно оптимизировать с использованием нескольких параллельных потоков. Если вы не знакомы с данными алгоритмами, настоятельно рекомендую с ними ознакомится.

В другом случае необходимо найти уникальный элемент в коллекции данных. Здесь наиболее сложным моментом при реализация параллельного поиска будет необходимость проинформировать задействованные в поиске потоки о том, что поиск завершен, остановить их выполнение и убедится в том, что все потоки поиска ожидающие запуска не будут активированны. С другой стороны, если поиск должен быть полным, то есть в результате его выполнения может быть найдено несколько копий желаемого элемента, останавливать потоки при находжении первого элемента не требуется.

Эмуляция очереди или стека. И в первом и во втором случае, вставка и удаление данных осуществляется по общему принципу. Подобно тому, как связанный список используется для эмуляции очереди или стека, при использовании дерева для подобных задач необходимо убедится что когда несколько потоков пытаются вставить или удалить некоторый элемент, то доступ к структуре дерева должен быть таким, что бы гарантировать, что данные не будут потеряны, повреждены или продублированы в процессе выполнения данных операций. (Я надеюсь что все это я мог бы и не рассказывать, так как вы и так все это знаете и без меня.)

Как и с эмуляцией стека и обыкновенной очереди, очередь с приоритетами может быть реализована посредством структуры «кучи» (еще одна структура данных о которой можно почитать на досуге) на дереве. Непосредственная реализация обыкновенной очереди и стека будет незначительно сложнее, если ее осуществлять на базе дерева. Стоит учесть, что параллельное выполнение потоков на данных структурах может быть недетерминированным (в то время как вывод - детерминированным). Даже если мы используем связанный список для стека с параллельным вычислением, из-за самой природы параллелизма, порядок обработки элементов в нем в большинстве случаев будет неопределенным (если алгоритм требует некоторой упорядоченности при обработке элементов стека, о параллельных вычислениях придется забыть). Итак, поскольку у нас есть методы для безопасной вставки и удаления элементов данных, их можно приспособить к работе с любыми реализациями деревьев.

Смог ли я убедить вас в том что имеет смысл отказаться от последовательных связанных списков в пользу древовидных структур для всех видов неупорядоченных данных в случаях, когда допустима их параллельная обработка? По крайней мере я убедил в этом себя. Это выглядит хорошей идеей и я выделил для себя агрументы описанные выше, но у меня еще не было возможности использовать эту идею на практике. Поэтому мне было бы интересно узнать о наличии каких-либо операций над данными, которые традиционно используются при работе со связанными списками, и которые не могут быть реализованы в случаях использования деревьев. Первое что пришло мне в голову – списки упорядоченные по частоте использования (frequency ordered list). Однако, эта структура базируется на последовательном доступе к элементам и последовательном упорядочевании запросов поиска. А вы можете назвать методы/алгоритмы доступа к списку, которые могут выполнятся параллельно, но требующие последовательного связанного списка или такой структуры данных, которая не могла бы быть реализована с использованием дерева?

By Clay Breshears, January 17, 2012