Приватизация (компьютерное программирование)

Приватизация — это метод, используемый в программировании с общей памятью для обеспечения параллелизма путем удаления зависимостей, возникающих в разных потоках параллельной программы . Зависимости между потоками возникают в результате одновременного чтения или записи переменной двумя или более потоками. Приватизация дает каждому потоку частную копию, поэтому он может читать и записывать его независимо и, следовательно, одновременно. ^{[ 1 ]}

Каждый параллельный алгоритм определяет, является ли переменная общей или частной. Многие ошибки в реализации могут возникнуть, если переменная объявлена как общая, но алгоритм требует, чтобы она была частной, или наоборот. ^{[ 2 ]}

Традиционно распараллеливающие компиляторы могли применять приватизацию только к скалярным элементам. Чтобы использовать параллелизм, возникающий на итерациях внутри параллельной программы ( параллелизм на уровне цикла ), выросла потребность в компиляторах, которые также могут выполнять приватизацию переменных массива. ^{[ 3 ]} Большинство современных компиляторов могут выполнять приватизацию массива с дополнительными возможностями и функциями для повышения производительности параллельной программы в целом. Примером может служить распараллеливающий компилятор Polaris. ^{[ 4 ]}

Описание

Мультипроцессор с общей памятью — это «компьютерная система, состоящая из нескольких независимых процессоров, которые выполняют разные потоки команд». ^{[ 4 ]} Модель программирования с общей памятью наиболее широко используется для разработки параллельных процессоров. ^{[ 1 ]} Эта модель программирования начинается с определения возможностей параллелизма внутри фрагмента кода и последующего отображения этих параллельных задач в потоки.

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

Область действия переменной

Следующий шаг в модели группирует задачи в более крупные задачи, поскольку обычно задач больше, чем доступных процессоров. Обычно количество потоков выполнения, которым назначаются задачи, выбирается меньшим или равным количеству процессоров, при этом каждый поток назначается уникальному процессору. ^{[ 1 ]}

Сразу после этого шага необходимо проанализировать использование переменных в задачах. Этот шаг определяет, должна ли каждая переменная быть общей для всех или частной для каждого потока. ^{[ 1 ]} Этот шаг уникален для программирования с общей памятью. (Альтернативой является передача сообщений , в которой все переменные являются частными.) ^{[ 1 ]}

В зависимости от поведения переменные подразделяются на следующие категории:

Только для чтения : когда переменная читается только всеми параллельными задачами.
Чтение/запись без конфликтов : когда переменная читается, записывается или и то и другое только одной задачей. Если переменная не является скалярной, разные элементы могут читаться/записываться разными параллельными задачами.
Конфликт чтения/записи : когда переменная записывается задачей и может быть прочитана другой. Если переменная не скалярная, разные элементы читаются/записываются разными параллельными задачами.

Как следует из их определения, переменные, конфликтующие при чтении/записи, создают зависимости между различными потоками выполнения и, следовательно, препятствуют автоматическому распараллеливанию программы. Двумя основными методами, используемыми для устранения этой зависимости, являются приватизация и сокращение . В сокращении каждому потоку предоставляется копия переменной R/W Conflicting для работы с ней и получения частичного результата, который затем объединяется с копиями других потоков для получения глобального результата. ^{[ 1 ]} Другой метод, похожий на приватизацию, называется расширением , при котором скалярная переменная расширяется в массив, что позволяет каждому потоку обращаться к другому элементу массива. ^{[ 5 ]} Если расширяемая переменная является массивом, то расширение добавляет к массиву еще одно измерение. ^{[ 6 ]}

Приватизация

Зависимости — потенциальные конфликты между различными потоками во время выполнения — препятствуют распараллеливанию, и эти конфликты возникают, когда у нас есть переменные, конфликтующие при чтении/записи. Одним из способов устранения этих конфликтов является приватизация. Основной принцип предполагает создание частной копии переменной для каждого потока, а не совместное использование одного экземпляра. При этом категория переменной меняется с «Конфликт чтения/записи» на «Чтение/запись без конфликта».

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

Есть две ситуации, в которых переменную можно назвать приватизируемой :

Когда переменная записывается до того, как она будет прочитана той же задачей в последовательном порядке исходной программы. В этом случае, если задача записывала данные в свою частную копию, а не в общую, конфликт/зависимость будет устранена. Причина этого в том, что последовательный порядок программы гарантирует, что значение будет записано той же задачей, устраняя любые конфликты, которые могут возникнуть при обращении других потоков к той же переменной. См. § Пример 1 .
Когда переменная читается до того, как она будет записана той же задачей. Разница здесь в том, что задача пытается прочитать значение, полученное на предыдущем этапе вычислений в другой задаче. Но если бы каждая задача записывала данные в свою собственную частную копию, любые конфликты или зависимости были бы решены во время выполнения, поскольку все они считывали бы заранее известное значение, а затем записывали бы свои правильные значения в свои собственные копии. См. § Пример 2 .

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

Ограничения

Иногда переменную нельзя ни приватизировать, ни уменьшить, чтобы устранить конфликт чтения/записи. В этих случаях переменную «Конфликт чтения/записи» необходимо обновлять разными задачами в разные моменты времени. См. § Пример 3 .

Эту проблему иногда можно решить, изменив область параллелизма для исследования другой параллельной области. Это может дать хорошие результаты, так как часто после повторного анализа кода некоторые переменные, конфликтующие при чтении/записи, могут измениться на неконфликтные при чтении/записи. ^{[ 1 ]} Если переменная по-прежнему вызывает конфликты, последним средством является объявление ее общей и защита ее доступа с помощью некоторой формы взаимного исключения , а также обеспечение синхронизации, если доступ к переменной должен происходить в определенном порядке для обеспечения корректности.

Массивы

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

Применительно к скалярным переменным дополнительное пространство и накладные расходы, возникающие при создании дополнительных частных копий для каждого потока, относительно невелики, поскольку скаляры малы. ^{[ 1 ]} Однако применить приватизацию к массивам, матрицам или другим составным типам гораздо сложнее.

При работе с массивами компилятор пытается проанализировать поведение каждого элемента массива отдельно и проверить порядок его чтения и записи. Если каждый элемент записывается до того, как он будет прочитан в той же итерации, этот массив можно приватизировать. Для этого компилятору необходимо дополнительно проанализировать массив, чтобы объединить его обращения в секции. Более того, компилятор должен иметь дополнительные функции, чтобы иметь возможность манипулировать элементами массива и работать с ними. Например, некоторые выражения массива могут иметь символические термины, следовательно, чтобы иметь возможность приватизировать такой массив, компилятору необходимо иметь некоторые расширенные функции символьной манипуляции . ^{[ 5 ]}

Примеры

Пример 1

Переменную можно приватизировать, если каждая задача будет записывать в нее данные перед чтением. В этом случае не имеет значения, делают ли это другие потоки. В приведенном ниже коде переменная x используется для замены трех разных пар переменных. Поскольку в него всегда записывается перед чтением, его можно приватизировать.

//Sequential Code:

x = a;
a = b;
b = x;

x = c;
c = d;
d = x;

x = e;
e = f;
b = x;

Этот код невозможно сделать параллельным без приватизации x. С x приватизирован, он может работать в трёх разных потоках, каждый со своим собственным x:

//Parallel Code:

//Thread 1:
x[1] = a;
a = b;
b = x[1];

// Thread 2:
x[2] = c;
c = d;
d = x[2];

// Thread 3:
x[3]= e;
e = f;
b = x[3];

Пример 2

Приватизация возможна, когда значение переменной известно до ее использования – даже если она записана другой задачей. Код ниже демонстрирует это. Переменная x записывается в середине каждой задачи, но это значение можно вычислить при компиляции программы. Делая x Private и определяя его в начале каждой задачи, код можно запускать параллельно:

//Sequential Code:
x = 1;
y = x * 3;
x = 4;
z = y/x;

a = x * 9;
x = 3;
b = a/x;

c = x * 1;
x = 11;
d = c/x;

Чтобы сделать приведенный выше последовательный код параллельным, необходимо добавить несколько строк кода, чтобы x могут быть приватизированы:

//Parallel Code
//Thread 0:
x[0] = 1;
y = x[0] * 3;
x[0] = 4;
z = y/x[0];

//Thread 1:
x[1] = 4;
a = x[1] * 9;
x[1] = 3;
b = a/x[1];

//Thread 2:
x[2] = 3;
c = x[2] * 1;
x[2] = 11;
d = c/x[2];

Из-за дополнительного кода этот короткий пример может не привести к значительному ускорению. Но в реальной жизни, с более длинным кодом, этот метод может значительно повысить производительность.

Пример 3

Провал приватизации — это когда переменная записывается в одной задаче, а читается в другой, а значение заранее не известно. Примером является суммирование элементов массива. Сумма является общей переменной и читается/записывается на каждой итерации цикла.

В последовательном коде это работает нормально. Но если бы каждая итерация выполнялась в другом потоке, сумма была бы рассчитана неправильно. В этом случае приватизация не работает. sum не может быть сделан закрытым, поскольку он полагается на свое значение из предыдущей итерации.

//Sequential Code:

sum = 0;
for (i = 0; i < 100; i++)
    sum += a[i];

Частично эту проблему можно решить путем развертывания цикла . Поскольку не имеет значения, в каком порядке добавляются элементы , цикл можно разбить на произвольное количество частей:

// Thread 0:
sum[0] = 0;
for (i[0] = 0; i[0] < 100; i[0] += 3)
    sum[0] += a[i[0]];

// Thread 1:
sum[1] = 0;
for (i[1] = 1; i[1] < 100; i[1] += 3)
    sum[1] += a[i[1]];

// Thread 2:
sum[2] = 0;
for (i[2] = 2; i[2] < 100; i[2] += 3)
    sum[2] += a[i[2]];

// "Master" thread:
wait_for_all(thread[0], thread[1], thread[2]);
sum = sum[0] + sum[1] + sum[2];

OpenMP

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

Учитывая последовательный код:

  do i = 10, N - 1
       x = (b(i) + c(i))/2
       b(i) = a(i + 1) + x
  enddo

Для каждой итерации цикла x записывается, а затем считывается. Потому что x является всего лишь скалярной переменной, цикл не может выполняться параллельно, поскольку он будет перезаписан в разных потоках, и b(i) не всегда будет присвоено правильное значение. ^{[ 2 ]}

Эквивалентный распараллеленный код с использованием приватизации:

  !$omp parallel do shared(a, b) private(x)
  do i = 10, N - 1
       x = (b(i) + c(i))/2
       b(i) = a(i + 1) + x
  enddo

Потому что x объявляется частным, каждый поток получает свою копию, и зависимость удаляется. ^{[ 2 ]}

Сравнение с другими методами

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

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

По сравнению с сокращением, приватизация требует одного этапа моделирования: просто проанализировать код для определения приватизируемых переменных. С другой стороны, для сокращения требуются два шага: идентификация переменной сокращения и последующее распараллеливание оператора сокращения. ^{[ 7 ]} Наблюдая за каждым из двух методов, легко определить, какой тип накладных расходов каждый из них добавляет к параллельной программе; сокращение увеличивает накладные расходы на вычисления, а приватизация увеличивает объем памяти, потребляемой программой. ^{[ 5 ]}

По сравнению с расширением, приватизация требует меньших затрат памяти. Объем памяти, необходимый для приватизации, пропорционален количеству процессоров, а при расширении — количеству итераций. ^{[ 5 ]} Поскольку количество задач обычно превышает количество процессоров, объем памяти, необходимый для расширения, намного больше, чем для приватизации.

Изменение области параллелизма можно выполнить для исследования другой параллельной области. Иногда это может существенно изменить поведение переменных. Таким образом, повторный анализ кода и выполнение этого метода часто могут изменить переменные, конфликтующие при чтении/записи, на неконфликтные. ^{[ 1 ]}

См. также

Ссылки

^ Jump up to: ^а ^б ^с ^д ^и ^ж ^г ^час ^я Солихин, Ян (2015). Основы параллельной многоядерной архитектуры . Чепмен и Холл/CRC. ISBN 978-1-4822-1118-4 . ^{[ необходимы страницы ]}
^ Jump up to: ^а ^б ^с Чандра, Рохит (2001). Пенроуз, Дениз (ред.). Параллельное программирование в OpenMP (PDF) . Морган Кауфманн . стр. 48, 74, 143. ISBN. 978-1-55860-671-5 .
^ Гупта, М. (1 апреля 1997 г.). «О приватизации переменных для параллельного выполнения данных». Материалы 11-го Международного симпозиума по параллельной обработке . стр. 533–541. CiteSeerX 10.1.1.50.2508 . дои : 10.1109/IPPS.1997.580952 . ISBN 978-0-8186-7793-9 . S2CID 17389658 .
^ Jump up to: ^а ^б Сезе, Луис Х. (01 января 2011 г.). «Мультипроцессоры с общей памятью». В Падуе, Дэвид (ред.). Энциклопедия параллельных вычислений . Спрингер США. стр. 1810–1812. дои : 10.1007/978-0-387-09766-4_142 . ISBN 978-0-387-09765-7 .
^ Jump up to: ^а ^б ^с ^д Падуя, Дэвид (1 января 2011 г.). «Распараллеливание, автоматическое». В Падуе, Дэвид (ред.). Энциклопедия параллельных вычислений . Спрингер США. стр. 1442–1450 - в перефразировании Брюса Лиза. дои : 10.1007/978-0-387-09766-4_197 . ISBN 978-0-387-09765-7 .
^ Ту, Пэн; Падуя, Дэвид (12 августа 1993 г.). «Приватизация автоматического массива». В Банерджи, Утпал; Гелернтер, Дэвид ; Николау, Алекс; Падуя, Дэвид (ред.). Языки и компиляторы для параллельных вычислений . Конспекты лекций по информатике. Шпрингер Берлин Гейдельберг. стр. 500–521. CiteSeerX 10.1.1.3.5746 . дои : 10.1007/3-540-57659-2_29 . ISBN 978-3-540-57659-4 .
^ Ю, Хао; Раухвергер, Лоуренс (1 января 2014 г.). «Методы распараллеливания адаптивного сокращения». Международная конференция ACM по суперкомпьютерам, юбилейный том, 25 лет . Нью-Йорк, штат Нью-Йорк, США: ACM. стр. 311–322. дои : 10.1145/2591635.2667180 . ISBN 978-1-4503-2840-1 . S2CID 52865514 .

[Solihin-1] Jump up to: ^а ^б ^с ^д ^и ^ж ^г ^час ^я Солихин, Ян (2015). Основы параллельной многоядерной архитектуры . Чепмен и Холл/CRC. ISBN 978-1-4822-1118-4 . ^{[ необходимы страницы ]}

[Chandra-2] Jump up to: ^а ^б ^с Чандра, Рохит (2001). Пенроуз, Дениз (ред.). Параллельное программирование в OpenMP (PDF) . Морган Кауфманн . стр. 48, 74, 143. ISBN. 978-1-55860-671-5 .

[3] Гупта, М. (1 апреля 1997 г.). «О приватизации переменных для параллельного выполнения данных». Материалы 11-го Международного симпозиума по параллельной обработке . стр. 533–541. CiteSeerX 10.1.1.50.2508 . дои : 10.1109/IPPS.1997.580952 . ISBN 978-0-8186-7793-9 . S2CID 17389658 .

[Ceze-4] Jump up to: ^а ^б Сезе, Луис Х. (01 января 2011 г.). «Мультипроцессоры с общей памятью». В Падуе, Дэвид (ред.). Энциклопедия параллельных вычислений . Спрингер США. стр. 1810–1812. дои : 10.1007/978-0-387-09766-4_142 . ISBN 978-0-387-09765-7 .

[Padua-5] Jump up to: ^а ^б ^с ^д Падуя, Дэвид (1 января 2011 г.). «Распараллеливание, автоматическое». В Падуе, Дэвид (ред.). Энциклопедия параллельных вычислений . Спрингер США. стр. 1442–1450 - в перефразировании Брюса Лиза. дои : 10.1007/978-0-387-09766-4_197 . ISBN 978-0-387-09765-7 .

[6] Ту, Пэн; Падуя, Дэвид (12 августа 1993 г.). «Приватизация автоматического массива». В Банерджи, Утпал; Гелернтер, Дэвид ; Николау, Алекс; Падуя, Дэвид (ред.). Языки и компиляторы для параллельных вычислений . Конспекты лекций по информатике. Шпрингер Берлин Гейдельберг. стр. 500–521. CiteSeerX 10.1.1.3.5746 . дои : 10.1007/3-540-57659-2_29 . ISBN 978-3-540-57659-4 .

[7] Ю, Хао; Раухвергер, Лоуренс (1 января 2014 г.). «Методы распараллеливания адаптивного сокращения». Международная конференция ACM по суперкомпьютерам, юбилейный том, 25 лет . Нью-Йорк, штат Нью-Йорк, США: ACM. стр. 311–322. дои : 10.1145/2591635.2667180 . ISBN 978-1-4503-2840-1 . S2CID 52865514 .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]