Я.Студент. Параллельные вычисления

[ algorithms yandex ]

31 Mar 2014

Я.Студент: Параллельные вычисления

Лекция Алексея Галахова в ИМКН УрФУ из цикла Я.Студент в УрФУ.

Последовательный алгоритм построить легко, но сделать параллельны алгоритм - это не просто добавить компьютеров.

Закон Дала

Производительность системы - количество операций в единицу времени.

С течением времени, прямая зависимость производительности системы от количества потоков достигает своего максимума и превращается в тождество.

  • t = fK,M(n)
  • Ω(g(n))={f(n): ∃ k>0 ∃ n_0 ∀ n>n _0: f(n) ≥ k * g(n) } т.е. если g(n) = n, то Ω(g(n)) = {n, 2n, 3n, … ,n², em} (неубывающие функции)
  • O(g(n)) = { . . . . . . f(n) ≤ k * g(n) }
  • Θ(g(n)) = Ω(g(n)) ∩ O(g(n))

Принято:

  • Писать не f принадлежит O(g(n)), а f(x)=O(g(n))

  • Вместо Ω и O обычно пользуются только Θ и называют ее O.

    Но мы же не они - поэтому будем пользоваться нормальными буквами.

Наращивание памяти

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

Тогда операция a + b = Ω(log(n)). Можно понять, что из младщих в старшие разряды можно переносить за логарифм, методом “разделяй и властвуй” В современных системах, n ≤ 256 (обычно 32 или 64)

Можно считать, что память M ≤ 2b, где b - размер регистра. То есть b = log(M). Тогда Ω(log(b)) = Ω(log(log(M))), и добавление памяти на компьютер, начиная с некоторого момента, будет уменьшать производительность компьютера, так как производительность операции, хоть и медленно, но зависит от размера памяти.

Наращивание числа процессоров

Сколько бы ни было процессоров - им необходимо общаться.

Пусть есть разделяемая память и несколько процессоров обращается к одной ячейке.

Случаи:

  • CREW (Concurent Read, Exclusive Write) - все ОК.
  • CRCW - значение вычисляется по некоему алгоритму (например логическое И/ИЛИ)
  • EREW - проще всего.
  • ERCW - нежизнеспособно.

На практике все процессоры - EREW (так электроникой устроено). Несмотря на то, что языки программирования подразумевают CREW, на нижнем уровне - все равно EREW - и из-за этого замедление.

Предложения Дейкстры

Для решения задач об обедающих философах, спящем парикмахере и.т.п

  • Семафоры

    Подвержены блокировкам

  • Токен

    Может быть неравномерно распределен - поэтому придуманы Сети Петри - схема перемещения токена по системе.

Производительность наращивания процессоров

Пусть есть входные данные x.

Выполнять будем на последовательной машине: x -> Ax -> BAx -> CBAx -> … -> y = FEDCBAx

Можем забыть про существование x, и взять сами действия: FEDCBA

Они:

  • Ассоциативны
  • Есть нейтральный элемент - тождественная операция

Множество операций - Группа.

Частично коммутирует. Например, если x - массив, и C = x[3]++, D = x[5]++, то C и D можно переставить.

FEDCBA - след програмы

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

Сокращаем цепочку, записывая C и D параллельно, тогда ассимптотическая скорость выполнения программы - наименьшая длина такой сокращенной цепочки.

Меньше этого времени алгоритм ускорить не получится!

Наращивание компьютеров

Если компьютеры соединены напрямую - все линейно, но обычно - несколько компьютеров объединены в сеть. Тогда возникает проблема выбора, на какой компьютер пойдут данные. То есть возникает Ω(Nlog(Pq)), где P - количество компьютеров, q - количество связей. И ассимптотой становится этот логарифм.

Пример 1

Алгоритм выбора наибольшего числа из массива. Компьютеры соединены в цепочку. (4 штуки) Передача между компьютерами по гусеничному алгоритму. (каждый - следующему)

Θ(N + 2K)

Если объединить сеть в кольцо - ничего не изменится (может двойка уйдет, или алогритм сделать устойчивым к обрыву), но принципиально ничего не изменится.

Если full-mesh, можно (при идеальном построении) получить Θ(N + log(K))

Пример 2

Сортировка.

Требуется разместить данные на машинах, и на машине с наименьшим номером должен быть наименьший элемент, а с наибольшим - наибольший.

Оказывается, можно построить хороший алгоритм сортировки.

  1. Каждая машина отсортирует внутри себя данные ( O(logN) )
  2. Выберем произвольную машину и посчитаем медиану на ней. ( O(logN) )
  3. Распределим медиану по сети ( O(logN) )
  4. Каждая машина поделит свои данные по этой медиане на две части и отдаст соседям (младшему и старшему)

В каком порядке отдавать?

Например, если представить номера машин в двоичном виде - то сначала те, у кого в младшем бите 1, потом те, у кого 0, потом в следующем бите 1, потом 0 и.т.д.

Это алгоритм ультрабыстрой сортировки.

Хорошая топология сети для такого алгоритма - гиперкуб. Тогда, например, тессеракт делим на два куба и передаем данные. Потом каждый куб делим на квадраты, потом квадраты на отрезки.

Fix

Пусть каждая машина передает не половину данных, а все свои данные.

После получения - слияние.

После слияния одна машина отбрасывает нижнюю половину, другая - верхнюю.

Этот алгоритм разбалансировкой не страдает, хоть и константа в два раза больше.

Недостатки

Пусть 1024 машины.

Придется делать 10-мерный куб.

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

Беда…….