В информатике параллельная структура данных — это особый способ хранения и организации данных для доступа к ним нескольких вычислительных потоков (или процессов ) на компьютере.
Исторически такие структуры данных использовались на однопроцессорных машинах с операционными системами , которые поддерживали несколько вычислительных потоков (или процессов ). Термин параллелизм охватывал мультиплексирование /чередование операций потоков над данными операционной системой, хотя процессоры никогда не выдавали две операции, которые обращались к данным одновременно.
Сегодня, когда многопроцессорные компьютерные архитектуры, обеспечивающие параллелизм, становятся доминирующей вычислительной платформой (благодаря распространению многоядерных процессоров), этот термин стал в основном обозначать структуры данных, к которым могут обращаться несколько потоков, которые фактически могут получать доступ к данным одновременно, поскольку они работают на разных процессорах, которые взаимодействуют друг с другом. Параллельная структура данных (иногда также называемая общей структурой данных ) обычно считается находящейся в абстрактной среде хранения, называемой общей памятью , хотя эта память может быть физически реализована как «тесно связанная» или распределенная коллекция модулей хранения.
Параллельные структуры данных, предназначенные для использования в параллельных или распределенных вычислительных средах, отличаются от «последовательных» структур данных, предназначенных для использования на однопроцессорной машине, несколькими способами. [1] В частности, в последовательной среде указываются свойства структуры данных и проверяется, что они реализованы правильно, путем предоставления свойств безопасности . В параллельной среде спецификация также должна описывать свойства жизнеспособности , которые должна предоставлять реализация. Свойства безопасности обычно утверждают, что что-то плохое никогда не происходит, в то время как свойства жизнеспособности утверждают, что что-то хорошее продолжает происходить. Эти свойства можно выразить, например, с помощью линейной временной логики .
Тип требований к жизнеспособности, как правило, определяет структуру данных. Вызовы методов могут быть блокирующими или неблокирующими . Структуры данных не ограничиваются одним или другим типом и могут допускать комбинации, в которых некоторые вызовы методов являются блокирующими, а другие — неблокирующими (примеры можно найти в библиотеке программного обеспечения Java concurrency ).
Свойства безопасности параллельных структур данных должны охватывать их поведение, учитывая множество возможных чередований методов, вызываемых разными потоками. Довольно интуитивно понятно, как абстрактные структуры данных ведут себя в последовательной обстановке, в которой нет чередований. Поэтому многие основные подходы к аргументации свойств безопасности параллельной структуры данных (такие как сериализуемость , линеаризуемость , последовательная согласованность и согласованность в состоянии покоя [1] ) определяют свойства структур последовательно и сопоставляют их параллельные выполнения с набором последовательных.
Чтобы гарантировать свойства безопасности и жизнеспособности, параллельные структуры данных должны, как правило (хотя и не всегда), позволять потокам достигать консенсуса относительно результатов их одновременных запросов на доступ к данным и их изменение. Для поддержки такого соглашения параллельные структуры данных реализуются с использованием специальных примитивных операций синхронизации (см. примитивы синхронизации ), доступных на современных многопроцессорных машинах , которые позволяют нескольким потокам достигать консенсуса. Этот консенсус может быть достигнут блокирующим способом с использованием блокировок или без блокировок, в этом случае он является неблокирующим . Существует обширная теория по проектированию параллельных структур данных (см. библиографические ссылки).
Параллельные структуры данных значительно сложнее проектировать и проверять на корректность, чем их последовательные аналоги.
Основным источником этой дополнительной трудности является параллелизм, усугубляемый тем фактом, что потоки следует рассматривать как полностью асинхронные: они подвержены вытеснению операционной системой, ошибкам страниц, прерываниям и т. д.
На современных машинах на производительность влияют расположение процессоров и памяти, расположение данных в памяти, коммуникационная нагрузка на различные элементы многопроцессорной архитектуры. Кроме того, существует напряжение между правильностью и производительностью: алгоритмические усовершенствования, направленные на повышение производительности, часто затрудняют проектирование и проверку правильной реализации структуры данных. [2]
Ключевым показателем производительности является масштабируемость, измеряемая ускорением реализации. Ускорение — это мера того, насколько эффективно приложение использует машину, на которой оно работает. На машине с P процессорами ускорение — это отношение времени выполнения структур на одном процессоре к времени его выполнения на P процессорах. В идеале мы хотим линейного ускорения: мы хотели бы достичь ускорения P при использовании P процессоров. Структуры данных, ускорение которых растет с P, называются масштабируемыми . Степень, до которой можно масштабировать производительность параллельной структуры данных, определяется формулой, известной как закон Амдаля , и более уточненными ее версиями, такими как закон Густафсона .
Ключевой проблемой производительности параллельных структур данных является уровень конкуренции за память: накладные расходы на трафик в память и из памяти в результате того, что несколько потоков одновременно пытаются получить доступ к одним и тем же областям памяти. Эта проблема наиболее остра в реализациях с блокировкой, в которых доступ к памяти контролируется блокировками. Чтобы получить блокировку, поток должен неоднократно пытаться изменить эту область. На когерентном кэш- мультипроцессоре (в котором процессоры имеют локальные кэши, обновляемые аппаратно, чтобы поддерживать их соответствие последним сохраненным значениям) это приводит к длительному времени ожидания для каждой попытки изменить область и усугубляется дополнительным трафиком памяти, связанным с неудачными попытками получить блокировку.