voeto.ru страница 1
скачать файл



САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

Математико-механический факультет


Кафедра системного программирования

Балансировка вычислений в библиотеке Threading Building Blocks

Дипломная работа студентки 544 группы

Вьюшковой Ксении Александровны

Научный руководитель

………………
/ подпись /

Ст. преп. кафедры системного программирования,
к.ф.-м.н. Вахитов А.Т.

Рецензент

………………
/ подпись /

Доцент кафедры вычислительной физики, к.ф.-м.н. Немнюгин С.А.

“Допустить к защите”
заведующий кафедрой,

………………

/ подпись /



д.ф.-м.н., проф. Терехов А.Н.

Санкт-Петербург

2010

ST. PETERSBURG STATE UNIVERSITY



Mathematics & Mechanics Faculty

Software Engineering Chair



Load balancing for the Threading Building Blocks

by

Ksenia Vyushkova



Master’s thesis

Supervisor

………………

Senior lecturer Vakhitov A.T.

Reviewer

………………

Associate professor Nemnugin S.A.

“Approved by”
Head of Department

………………

Professor A. N. Terekhov

St.Petersburg

2010


Оглавление

Введение 5

Постановка задачи 6

1. Многоядерные вычисления с использованием Threading Building Blocks 7

Библиотека Threading Building Blocks 7

Составные библиотеки 8

Планировщик заданий 9

Параллельное выполнение цикла for 10

Модель диапазона 11

Модель диапазона в двумерном пространстве 12

Алгоритмы подбора размера блока 12

2. Алгоритмы подстройки размера блока 12

Зависимость времени выполнения от размера блоков 12

Псевдоградиентный метод 14

Метод умножения размера блока на два 15

3. Экспериментальные результаты 16

Задача умножения вектора на число 16

Задача перемножения векторов 18

Задача умножения матриц 20

Заключение 23

Литература 24




Введение


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

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

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

Повышению эффективности работы параллельных программ посвящена моя дипломная работа.


Постановка задачи


В рамках данной дипломной работы изучаются возможности применения итеративных алгоритмов оптимизации для балансировки нагрузки при многоядерных вычислениях с использованием библиотеки Intel Threading Building Blocks.

Threading Building Blocks является разработкой компании Intel, впитавшей в себя ряд прогрессивных идей множества исследователей и является закономерным развитием таких моделей программирования, как STL, OpenMP, Cilk, JSR-166 (Java Concurrency utilities), ECMA .NET*. TBB является не просто компонентой, реализующей определенную функциональность, а системой поддержки исполнения параллельных программ, берущей на себя такие функции, как создание и управление потоками, распределение заданий и балансировка вычислений, обеспечение корректности синхронизации параллельных программ, оптимальная реализация базовых параллельных алгоритмов типа parallel reduce. TBB с 2007 года является продуктом с открытым кодом, что создает множество возможностей для исследований.

Параллельное выполнение цикла for в рамках модели TBB существенно зависит от величины блоков, на которые разбивается все множество итераций. Приведенный ниже график из (Threading Building Blocks Tutorial, 2008 [1]) показывает приблизительно выпуклую зависимость времени вычислений от величины стандартного блока. Это объясняется тем, что при слишком большом размере блока задания распределяются между ядрами сильно неравномерно, что вызывает итоговую задержку по времени из-за дисбаланса. При малых размерах блока возникает задержка из-за слишком больших усилий по поддержанию многопоточного выполнения задачи, так как с уменьшением размера блока число блоков возрастает.



Рисунок 1 Зависимость времени вычислений от величины блока (Threading Building Blocks Tutorial, 2008)

Для различных конфигураций компьютеров (2,4,8,16 ядер) график выглядит по-разному, и минимум времени достигается при разных размерах блока. Это обусловлено тем фактом, что в компьютерах различается производительность ядер, скорость работы шины, нагрузка на ядра со стороны операционной системы, размер кэш-памяти и другие параметры.

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

1. Многоядерные вычисления с использованием Threading Building Blocks

Библиотека Threading Building Blocks


Конструктивные компоненты Intel® Threading Building Blocks (Intel® TBB) [2] - это библиотека, упрощающая написание многопоточных приложений. Как стандартная библиотека шаблонов C++ (STL) расширяет возможности базового языка, так и Threading Building Blocks предлагает пользователям C++ дополнительные возможности абстрагирования для развертывания параллельных приложений. В библиотеке Threading Building Blocks разработчики используют привычные шаблоны C++ и стили кодировки, а библиотека отвечает за низкоуровневые детали многопоточности.

Многоядерность процессоров становятся все более актуальным вопросом, однако, даже написание при помощи существующих библиотек простого parallel_for является утомительной задачей. Написание эффективной масштабируемой программы еще более затруднительно. Масштабируемость подразумевает понятие того, что программа должна работать лучше при возрастании числа ядер процессора. Программы, использующие Threading Building Blocks, могут работать как на одноядерном процессоре, так и на многоядерных процессорах, причем, Threading Building Blocks помогает создавать приложения, производительность которых будет увеличиваться по мере увеличения количества ядер процессора. Кроме того, библиотека полностью поддерживает вложенность параллелизма – можно построить большие параллельные компоненты из маленьких параллельных компонент. При использовании библиотеки, нужно описывать задачи, а не потоки; библиотека сама распределяет задачи на потоки, что облегчает написание программ.

Таким образом, благодаря библиотеке Threading Building Blocks, разработчики получают преимущества в виде ускорения работы, масштабирования производительности и упрощения поддержки кода.

Составные библиотеки


Threading Building Blocks это коллекция компонент для параллельного программирования:

  • Базовые алгоритмы: parallel_for, parallel_reduce, parallel_scan

  • Более сложные алгоритмы: parallel_while, parallel_do, pipeline, parallel_sort

  • Контейнеры: concurrent_queue, concurrent_vector, concurrent_hash_map

  • Масштабируемое выделение памяти: scalable_malloc, scalable_free, scalable_realloc, scalable_calloc, scalable_allocator, cache_aligned_allocator

  • Взаимное исключение: mutex, spin_mutex, queuing_mutex, spin_rw_mutex, queuing_rw_mutex, recursive mutex

  • Атомарные операции: fetch_and_add, fetch_and_increment, fetch_and_decrement, compare_and_swap, fetch_and_store

  • Синхронизация: переносимая мелкозернистая глобальная отметка времени

  • Планировщик заданий: прямой доступ для контроля создания и активизации задач

Планировщик заданий


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

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

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

1. Взять задание, возвращенное методом execute предыдущего задания. Это правило не применяется, если метод execute возвращает NULL.

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

3. Украсть задание с вершины другой случайно выбранной очереди. Если выбранная очередь пуста, поток пробует снова применить это правило.

Результатом применения правила 2 является то, что выполняется самое молодое порожденное потоком задание, что обеспечивает выполнение “в глубину”, пока у потока не останется работы. При применении правила 3, происходит кража самого старого задания, порожденного другим потоком, что вызывает временное выполнение “в ширину”, которое превращает потенциальный параллелизм в действительный.

Параллельное выполнение цикла for


parallel_for – модель параллельного выполнения цикла for.

parallel_for представляет собой параллельное выполнение тела цикла(Body) по каждому значению диапазона(Range).

parallel_for рекурсивно делит диапазон на поддиапазоны до тех пор, пока функция is_divisible() не вернет false для каждого поддиапазона, и создает копии тела цикла для каждого поддиапазона. Для каждой пары тело цикла/поддиапазон parallel_for вызывает Body::operator() .

Когда есть свободные рабочие потоки, parallel_for выполняет итерации недетерминировано. Нельзя полагаться на какой-то определенный порядок выполнения. Однако, для эффективности parallel_for чаще всего выполняет работу последовательно.

Когда нет свободных рабочих потоков, parallel_for выполняет итерации слева направо, а именно: представим бинарное дерево, которое отражает рекурсивное деление диапазона, в котором каждая вершина, не являющаяся листом, изображает деление поддиапазона r конструктором деления Range(r, split()). Левый потомок представляет собой обновленное значение r, правый потомок - вновь сконструированный объект. Каждый лист дерева представляет собой неделимый поддиапазон. Метод Body::operator() вызывается для каждого листа слева направо.

В качестве параметров parallel_for использует blocked_range с указанием границ пространства итераций, тело цикла и partitioner, задающий алгоритм подбора размера блока.


Модель диапазона


blocked_range представляет собой полуоткрытый интервал [i, j), который можно рекурсивно поделить. Тип Value должен быть целым типом, указателем, или итератором случайного доступа в STL, главное, чтобы значение (j-i) можно было явно преобразовать к типу size_t.

blocked_range определяет размер блока(grainsize) типа size_t. blocked_range можно разделить на два поддиапазона, если размер диапазона превосходит размер блока. Оптимальный размер блока зависит от контекста, обычно он используется в шаблонах parallel_for, parallel_reduce, и parallel_scan. Слишком маленький размер блока может вызвать задержки из-за больших усилий по поддержанию многопоточного выполнения задачи. Слишком большой размер блока может ограничить параллелизм. Например, если размер блока настолько велик, что диапазон можно разделить только один раз, то максимально возможный параллелизм равен двум.

В классе определен метод is_divisible(), который возвращает True, если диапазон можно разделить, а именно, если размер диапазона больше, чем grainsize.

Модель диапазона в двумерном пространстве


Для пространств размерности два используется blocked_range2d.

blocked_range2d представляет полуоткрытый диапазон размерности два [i0,j0)x[i1,j1). Разделение диапазонов происходит по обеим осям. blocked_range2d является разделяемым до тех пор, пока его можно разделить хотя бы по одной оси.


Алгоритмы подбора размера блока


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

По умолчанию в алгоритмах parallel_for, parallel_reduce, и parallel_scan диапазон рекурсивно делится до тех пор, пока не останется делимых поддиапазонов(это определяется функцией is_divisible()). Алгоритм подбора размера блока решает, имеет ли смысл раннее прекращение деления диапазона.

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

auto_partitioner моделирует адаптивное поведение, при котором partitioner следит за действиями по “воровству заданий” в планировщике заданий для того, чтобы уменьшить количество разделений(split).


2. Алгоритмы подстройки размера блока

Зависимость времени выполнения от размера блоков


Параллельное выполнение цикла for в рамках модели TBB существенно зависит от величины блоков, на которые разбивается все множество итераций. Приведенный ниже график из (Threading Building Blocks Tutorial, 2008) показывает приблизительно выпуклую зависимость времени вычислений от величины стандартного блока. Это объясняется тем, что при слишком большом размере блока задания распределяются между ядрами сильно неравномерно, что вызывает итоговую задержку по времени из-за дисбаланса. При малых размерах блока возникает задержка из-за слишком больших усилий по поддержанию многопоточного выполнения задачи, так как с уменьшением размера блока число блоков возрастает.

Заметим, что при небольших значениях grainsize функция плавно убывает, тогда, как при больших значениях происходят скачки. Эти скачки объясняются тем, что, начиная с некоторого значения, размер блоков становится настолько велик, что не всем ядрам процессора хватает работы, и некоторые из них простаивают.



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

Таким образом, если на компьютере надо многократно выполнять некую задачу, то оптимально подобрать размер блока и использовать simple_partitioner.

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

Далее предложено два метода подбора оптимального размера блока для simple_partitioner.

Псевдоградиентный метод


Общий подход для поиска экстремума [3, 4, 5], используемый в алго­ритмах стохастической аппроксимации, может быть формализован следующим образом :

θn+1 = θn −αngnn), (1)

где {θn}— генерируемая алгоритмом последовательность оценок точки экстремума, gn — псевдоградиент(заменяющий градиент из метода Ньютона), который “в среднем” должен совпадать с гра­диентом и близок к нулю, когда его аргумент стремится к точке экстремума. Важными свойствами алгоритмов записанных в фор­ме (1) являются простота и рекуррентность, в силу которых они стали активно применяться в разных областях науки и техники.

В нашей задаче для простоты будем считать αn постоянной.

gnn) = F (θn+ß) -F (θn-ß)

, где F – время выполнения программы.


Метод умножения размера блока на два


В Intel Threading Building Blocks Tutorial [1] предлагается метод деления grainsize пополам. Предлагается установить значение grainsize равным некоторому завышенному значению и делить его пополам до тех пор, пока уменьшение времени работы не будет в пределах 5-10%. Но этот метод может дать неправильные результаты в случае, если значение grainsize попадет на правую часть графика. Ведь в таком случае уменьшение времени работы в пределах 5-10% еще не говорит о попадании в пологую оптимальную часть графика:



Рисунок 2 Попадание значения grainsize в неоптимальную часть графика

Предлагается модифицировать этот метод и идти не справа налево, а слева направо.

Так как график является логарифмическим, будем увеличивать grainsize в два раза, проходя постепенно значения от 1 до 228. Если в какой-то момент значение увеличится больше, чем на 20%, это будет означать, что работают не все ядра процессоров, а значит, минимум функции находится левее. В этом случае останавливаемся и ищем минимум значений.

3. Экспериментальные результаты


Для тестирования были выбраны задачи с постоянным количеством операций в итерации: задача умножения вектора на число, задача перемножения векторов и задача перемножения матриц.

При проведении исследования использовался двухъядерный процессор Intel Core 2 Duo.


Задача умножения вектора на число


Задача: умножение вектора на число в цикле от 1 до 10. Размерность вектора 1000000.



Рисунок 3 Зависимость времени вычислений от величины блока в задаче умножения вектора на число

Время выполнения программы без использования TBB: 96.367 msec.

Время выполнения с использованием auto_partitioner: 66.2773 msec.

Время выполнения с использованием simple_partitioner:



Grainsize

Time, msec

1

138,817

10

62,7167

100

49,9731

1000

46,9771

10000

49,6187

100000

54,2205

1000000

93,3387

10000000

93,1128

1E+08

93,3421

Метод умножения размера блока на два:

Step

Grainsize

Time, msec

1

1

138,492

2

2

99,2877

3

4

68,9502

4

8

57,9306

5

16

53,5078

6

32

49,2081

7

64

47,5245

8

128

47,1266

9

256

49,7027

10

512

47,155

11

1024

46,1632

12

2048

46,3127

13

4096

46,4042

14

8192

46,3509

15

16384

46,2697

16

32768

47,0509

17

65536

46,8881

18

131072

47,0626

19

262144

46,4736

20

524288

46,7366

21

1048576

91,5848

Итог: Grainsize = 1024

Псевдоградиентный метод:

α = 10

Step

Grainsize

Time, msec

1

780

46,345

2

748

46,7361

3

760

46,9321

Итог: Grainsize = 760

Выводы:



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

  • Ускорение по отношению ко времени работы программы с использованием auto_partitioner равно 29%.

Задача перемножения векторов


Задача: скалярное произведение двух векторов размерности 1000000.



Рисунок 4 Зависимость времени вычислений от величины блока в задаче перемножения векторов

Время выполнения программы без использования TBB: 84.4611 msec.

Время выполнения с использованием auto_partitioner: 54.2131 msec.

Время выполнения с использованием simple_partitioner:



Grainsize

Time, msec

1

131,232

10

53,7541

100

43,5519

1000

41,8683

10000

41,8532

100000

41,949

1000000

83,1433

10000000

79,2737

1E+08

82,6505

Метод умножения размера блока на два:

Step

Grainsize

Time, msec

1

1

173,557

2

2

91,883

3

4

66,0051

4

8

54,264

5

16

51,6439

6

32

45,4583

7

64

44,3506

8

128

43,5357

9

256

43,6081

10

512

43,6389

11

1024

42,4681

12

2048

42,2359

13

4096

42,5889

14

8192

42,7458

15

16384

46,3333

16

32768

46,1881

17

65536

44,4039

18

131072

42,385

19

262144

42,6334

20

524288

42,2851

21

1048576

83,6903

Итог: Grainsize = 2048

Псевдоградиентный метод:

α = 10

Step

Grainsize

Time, msec

1

794

44,1443

2

791

42,1411

3

790

41,9827

Итог: Grainsize = 790

Выводы:


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

  • Ускорение по отношению ко времени работы программы с использованием auto_partitioner равно 22%.

Задача умножения матриц


Задача: умножение двух матриц размерности 200 на 200.



Рисунок 3 Зависимость времени вычислений от величины блока в задаче умножения матриц

Время выполнения программы без использования TBB: 767.862 msec.

Время выполнения с использованием auto_partitioner: 471.524 msec.

Время выполнения с использованием simple_partitioner:



Grainsize

Time, msec

1

423,838

10

385,554

100

389,189

1000

719,807

10000

720,496

100000

720,496

1000000

724,408

10000000

722,913

1E+08

734,827

Метод умножения размера блока на два:

Step

Grainsize

Time, msec

1

1

425,659

2

2

403,034

3

4

387,417

4

8

387,084

5

16

387,674

6

32

387,065

7

64

401,042

8

128

392,288

9

256

398,244

10

512

728,6

Итог: Grainsize = 32

Псевдоградиентный метод:

α = 10

Step

Grainsize

Time, msec

1

433

384,574

2

478

390,157

3

403

388,269

4

373

397,883

5

186

390,589

6

204

390,565

Итог: Grainsize = 204

Выводы:


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

  • Ускорение по отношению ко времени работы программы с использованием auto_partitioner равно 17%.


Заключение


  1. Подтверждена возможность подстройки оптимального размера блока для алгоритма подбора размера блока simple_partitioner.

  2. Предложено два метода подбора размера блока: метод умножения размера блока на два и псевдоградиентный метод.

  3. Использование алгоритма подбора размера блока simple_partitioner с оптимальным значением размера блока на 20%-30% ускоряет работу программы по сравнения с алгоритмом подбора размера блока auto_partitioner в классе задач с постоянным количеством операций на итерации.

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

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


Литература


[1] Threading Building Blocks Tutorial, 2008 // http://www.threadingbuildingblocks.org/documentation.php

[2] J. Reinders, Intel Threading Building Blocks Outfitting C++ for Multi-core Processor Parallelism. O’Reilly. 2007. 303 p.

[3] Б.Т. Поляк, Введение в оптимизацию. М.: Наука. Главная редакция физико-математической литературы. 1983. 384 с.

[4] Граничин О.Н., Поляк Б.Т.,  Рандомизированные алгоритмы оценивания и оптимизации при почти произвольных помехах. М.: Наука. 2003. 291 с.



[5] А. Т. Вахитов, Л. С. Гуревич, Псевдоградиентный метод с возмущением на входе для нестационарной задачи безусловной оптимизации // Стохастическая     оптимизация     в     информатике. Вып. 4. СПб.:    Издательство С.-Петербургского  университета. 2008. – с.36 -47

скачать файл



Смотрите также:
Балансировка вычислений в библиотеке Threading Building Blocks
223.23kb.
Слово «компьютер» означает «вычислитель», т е. устройство для вычислений. Потребность в автоматизации обработки данных, в том числе вычислений, возникла очень давно
83.61kb.
Оценка целесообразности перехода предприятия к использованию облачных вычислений
67.4kb.
Положение о библиотеке
112.37kb.
NVidia cuda для распараллеливания вычислений с использованием графических процессоров. Обсуждаются особенности программной реализации технологии, в частности, использование потоковых процессоров и памяти видеоадаптера
181.72kb.
Исследования
75.08kb.
Это набор прикладных программ для выполнения задач и решения технических вычислений на основе языка программирования четвертого поколения
6.87kb.
Второй Международный научно-практический семинар
149.28kb.
С диссертацией можно ознакомиться в библиотеке Московской государственной академии делового администрирования по адресу: 124460, Москва, Зеленоград, кор
327.7kb.
Положение о библиотеке общеобразовательного учреждения
42.91kb.
Создание фонда электронных документов в библиотеке нии
101.05kb.
Разработка нового стахостического метода управления очередями заданий с использованием Марковских процессов для параллельных вычислений на кластере
122.44kb.