В информатике , А одновременно структура данных является частным способом хранения и организации данных для доступа нескольких вычислительных потоков (или процессов ) на компьютере.
Исторически такие структуры данных использовались на однопроцессорных машинах с операционными системами, которые поддерживали несколько вычислительных потоков (или процессов ). Термин « параллелизм» отражает мультиплексирование / чередование операций потоков с данными операционной системой, даже несмотря на то, что процессоры никогда не выполняли две операции, которые обращались к данным одновременно.
Сегодня, когда многопроцессорные компьютерные архитектуры, обеспечивающие параллелизм, становятся доминирующей вычислительной платформой (благодаря распространению многоядерных процессоров), этот термин стал обозначать в основном структуры данных, к которым могут обращаться несколько потоков, которые могут фактически обращаться к данным одновременно, потому что они работают на разных процессорах, которые обмениваются данными друг с другом. Параллельная структура данных (иногда также называемая совместно используемой структурой данных ) обычно считается находящейся в абстрактной среде хранения, называемой общей памятью , хотя эта память может быть физически реализована либо как «тесно связанная», либо как распределенная совокупность модулей хранения.
Основные принципы
Параллельные структуры данных, предназначенные для использования в параллельных или распределенных вычислительных средах, по-разному отличаются от «последовательных» структур данных, предназначенных для использования на однопроцессорной машине. [1] В частности, в последовательной среде задаются свойства структуры данных и проверяется, что они реализованы правильно, путем предоставления свойств безопасности . В параллельной среде спецификация также должна описывать свойства живучести, которые должна обеспечивать реализация. Свойства безопасности обычно утверждают, что что-то плохое никогда не происходит, а свойства живучести говорят, что что-то хорошее продолжает происходить. Эти свойства могут быть выражены, например, с помощью линейной временной логики .
Тип требований к живучести обычно определяет структуру данных. Вызов метода может быть блокирующим или неблокирующим . Структуры данных не ограничиваются одним или другим типом и могут допускать комбинации, в которых некоторые вызовы методов являются блокирующими, а другие - неблокирующими (примеры можно найти в программной библиотеке параллелизма Java ).
Свойства безопасности параллельных структур данных должны фиксировать их поведение с учетом множества возможных чередований методов, вызываемых разными потоками. Довольно интуитивно понятно указать, как абстрактные структуры данных ведут себя в последовательной настройке, в которой нет чередования. Поэтому многие распространенные подходы к аргументации свойств безопасности параллельной структуры данных (такие как сериализуемость , линеаризуемость , последовательная согласованность и статическая согласованность [1] ) определяют свойства структур последовательно и сопоставляют ее одновременное выполнение с набором последовательных.
Чтобы гарантировать свойства безопасности и живучести, параллельные структуры данных обычно (хотя и не всегда) должны позволять потокам достигать консенсуса в отношении результатов их одновременного доступа к данным и запросов на изменение. Для поддержки такого соглашения параллельные структуры данных реализуются с использованием специальных примитивных операций синхронизации (см. Примитивы синхронизации ), доступных на современных многопроцессорных машинах, которые позволяют нескольким потокам достигать консенсуса. Этот консенсус может быть достигнут блокирующим способом с использованием блокировок или без блокировок, и в этом случае он не блокируется . Существует обширная теория проектирования параллельных структур данных (см. Библиографические ссылки).
Дизайн и реализация
Параллельные структуры данных значительно труднее спроектировать и проверить как правильность, чем их последовательные аналоги.
Основным источником этой дополнительной трудности является параллелизм, усугубляемый тем фактом, что потоки следует рассматривать как полностью асинхронные: они подвержены вытеснению операционной системы, ошибкам страниц, прерываниям и т. Д.
На современных машинах расположение процессоров и памяти, расположение данных в памяти, коммуникационная нагрузка на различные элементы многопроцессорной архитектуры - все это влияет на производительность. Кроме того, существует противоречие между правильностью и производительностью: алгоритмические улучшения, направленные на повышение производительности, часто затрудняют проектирование и проверку правильной реализации структуры данных. [2]
Ключевым показателем производительности является масштабируемость, выраженная в ускорении реализации. Ускорение - это показатель того, насколько эффективно приложение использует машину, на которой оно запущено. На машине с P-процессорами ускорение - это отношение времени выполнения структур на одном процессоре к времени их выполнения на T-процессорах. В идеале нам нужно линейное ускорение: мы хотели бы достичь ускорения P при использовании P-процессоров. Структуры данных, скорость которых увеличивается с ростом P, называются масштабируемыми . Степень, в которой можно масштабировать производительность параллельной структуры данных, определяется формулой, известной как закон Амдала, и более усовершенствованными версиями, такими как закон Густафсона .
Ключевой проблемой, связанной с производительностью параллельных структур данных, является уровень конкуренции за память: накладные расходы на трафик в и из памяти в результате одновременных попыток нескольких потоков получить доступ к одним и тем же местам в памяти. Эта проблема наиболее остро стоит в реализациях блокировки, в которых блокировка управляет доступом к памяти. Чтобы получить блокировку, поток должен неоднократно пытаться изменить это местоположение. В мультипроцессоре с когерентным кешем (тот, в котором у процессоров есть локальные кэши, которые обновляются аппаратно, чтобы поддерживать их согласованность с последними сохраненными значениями), это приводит к длительному времени ожидания для каждой попытки изменить местоположение и усугубляется дополнительной памятью трафик, связанный с неудачными попытками получить блокировку.
Смотрите также
- Параллелизм Java (JSR 166)
- Java ConcurrentMap
Рекомендации
- ^ a b Марк Мойр и Нир Шавит (2007). « Параллельные структуры данных ». В Динеш Мета и Сартадж Сахни (ред.). «Справочник по структурам данных и приложениям»(1-е изд.). Чепмен и Холл / CRC Press. С. 47–14–47–30. Внешняя ссылка в
|chapter=
( помощь ) - ^ Грамоли, В. (2015). Больше, чем вы когда-либо хотели знать о синхронизации: Synchrobench, измеряющий влияние синхронизации на параллельные алгоритмы (PDF) . Материалы 20-го симпозиума ACM SIGPLAN по принципам и практике параллельного программирования. ACM. С. 1–10. Архивировано из оригинального (PDF) 10 апреля 2015 года.
дальнейшее чтение
- Нэнси Линч "Распределенные вычисления"
- Хагит Аттия и Дженнифер Уэлч «Распределенные вычисления: основы, моделирование и дополнительные темы, 2-е изд.»
- Дуг Ли , «Параллельное программирование на Java: принципы и шаблоны проектирования»
- Морис Херлихи и Нир Шавит , «Искусство многопроцессорного программирования»
- Маттсон, Сандерс и Массингил «Шаблоны для параллельного программирования»
Внешние ссылки
- Многопоточные структуры данных для параллельных вычислений, Часть 1 (Проектирование параллельных структур данных), Арпан Сен
- Многопоточные структуры данных для параллельных вычислений: Часть 2 (Проектирование параллельных структур данных без мьютексов) Арпан Сен
- libcds - библиотека C ++ безблокировочных контейнеров и схема безопасного восстановления памяти
- Synchrobench - библиотеки C / C ++ и Java и тесты для структур данных без блокировок, на основе блокировок, TM и RCU / COW.