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