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