Параллелизм вычислений

Параллелизм можно представить в виде классификации форм параллельной обработки транзакций.

Классификация различных форм параллелизма схематично изображена на рис. 3.4. Прежде всего можно выделить межтранзакционную и внутритранзакционную формы параллелизма.

Межтранзакционный параллелизм подразумевает параллельное выполнение множества независимых транзакций над одной и той же базой данных. Данный вид параллелизма присутствует уже в однопроцессорных системах в виде так называемого многопользовательского режима и основан на перекрытии задержек ввода-вывода. Межтранзакционный параллелизм позволяет су-

Формы параллелизма вычислений

Рис. 3.4. Формы параллелизма вычислений

щественно увеличить суммарную производительность системы баз данных в режиме OLTP. Этот вид параллелизма также должен поддерживаться и в параллельной системе баз данных (наряду с внутритранзакционным параллелизмом), так как в противном случае получим очень плохое соотношение цена—производительность для режима OLTP. Для сокращения времени выполнения сложных транзакций необходимо использовать внутритран-закционный параллелизм.

Внутритранзащионный параллелизм предполагает параллельное выполнение транзакции. Этот вид параллелизма может быть реализован либо в форме межзапросного параллелизма, либо в форме внутризапросного параллелизма.

Межзапросный (.межоператорный) параллелизм предполагает параллельное выполнение SQL-операторов, принадлежащих одной и той же транзакции. Степень межзапросного параллелизма, однако, определяется как количеством SQL-операторов (запросов), составляющих данную транзакцию, так и ограничениями предшествования между отдельными SQL-операторами.

Межзапросный параллелизм не поддерживается большинством современных систем управления базами данных (СУБД), так как это потребует от программиста явной спецификации межзапросных зависимостей с помощью некоторых специальных языковых конструкций.

Внутризапросный (внутриоператорный) параллелизм предполагает параллельное выполнение 50Ь-оператора (запроса). Данная форма параллелизма характерна для реляционных систем баз данных, так как реляционные операции над наборами кортежей по своей природе хорошо приспособлены для эффективного распараллеливания. Внутризапросный параллелизм реализуется оптимизатором запросов прозрачным для пользователя образом. Для каждого запроса оптимизатор генерирует план выполнения запроса, который представляется в виде дерева (ациклического ориентированного графа), узлы которого соответствуют реляционным операциям, дуги — потокам данных между операциями, а в качестве листьев фигурируют отношения. Внутризапросный параллелизм может реализовываться либо в виде межоперационного параллелизма, либо в виде внутриоперационного параллелизма.

Межоперационный параллелизм предполагает параллельное выполнение реляционных операций, принадлежащих одному и тому же плану запроса, и может реализовываться либо в виде горизонтального параллелизма, либо в виде вертикального параллелизма.

Горизонтальный (кустовой) параллелизм предполагает параллельное выполнение независимых поддеревьев дерева, представляющего план запроса. Основная проблема, связанная с кустовым параллелизмом, заключается в том, чтобы два подплана одного плана начали генерировать выходные данные в определенное время и в правильном темпе. При этом время далеко не всегда означает одинаковое время, например для входных потоков операции хэш-соединения, а правильный темп далеко не всегда означает одинаковый темп, например для случая, когда входные потоки соединения слиянием имеют различные размеры. В силу указанных причин кустовой параллелизм редко используется на практике. В научных публикациях кустовой параллелизм исследовался главным образом в контексте оптимизации запросов с мультисоединениями.

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

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

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

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

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

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

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

 
< Пред   СОДЕРЖАНИЕ     След >