© Георгиевский Анатолий, 6.09.2009

Нитки и ветки (GThread)

В статье приводятся примеры использования библиотеки Glib для создания многопотоковых (multi-thread) программ. Приводятся результаты оптимизации производительности программы за счет использования многопотоковости и многозадачности.

Glib - кросс-платформенная библиотека, содержащая множество инструментов для работы с объектами на языке С. Кроме всего прочего в комплект входит интерфейс для работы с нитками-ветаками (библиотека gthread).

Нити процессов

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

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

Задачи в операционной системе переключаются крайне редко, обычно это происходит с частотой 1кГц по таймеру или по событиям ввода-вывода. На однопотоковом процессоре (одноядерном, без HT) одновременно запущенные процессы будут выполняться всё равно последовательно. Если время исполнения нитей существенно велико, то управление будет передаваться от одного к другому процессу по таймеру. Техника нитей безусловно выигрышна, когда нить обработки данных отделена от процесса ввода-вывода. В этом случае можно заниматься обработкой данных во время ожидания ввода-вывода.

Существуют объективные причины, почему даже при наличии в процессоре нескольких ядер не удается исполнять нити параллельно. Например, в архитектуре Numa (Non-unified memory architecture) адресное пространство оперативной памяти физически разделено между процессорами. В многоядерных архитектурах существует проблема синхронизации кеш-памяти, которая своя у каждого ядра, поскольку нити должны работать с общим сегментом данных. Эффективность загрузки процессорных ядер многопотоковыми задачами будет сильно зависеть от операционной системы. Иными словами, совмем не очевидно, что использование нитей процессов может ускорить работу программы за счет параллельного исполнения.

Инициализация нитей процессов

Система нитей должна быть однократно инициализирована. Чтобы случайно не инициализировать нити дважды в разных модулях программы используется такой метод:

#include <glib.h>
 . . .
if (!g_thread_supported ()) g_thread_init (NULL);

Последовательное исполнение нитей процессов

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

#define JOINABLE TRUE
GThread *thread_ref = g_thread_create(func, data, 
		JOINABLE, NULL);
 . . .
// дождаться завершения нити 
g_thread_join(thread_ref)

Функция g_thread_create асинхронно запускает пользовательскую функцию func с параметром data и помечает её как "наращиваемую нить". Параметр JOINABLE означает, что после завершения процесса объект GThread не будет удален и его можно использовать для определения активности процесса.

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

Результат работы первого процесса можно передать во второй процесс по команде return data; так же как из обычной функции. Функция g_thread_join возвращает указатель на результат работы асинхронного процесса.

Работа со списком активных процессов

GList * thread_list = NULL;
 . . .
GThread *thread_ref = g_thread_create(func, data, 
		JOINABLE, NULL);
// добавить ссылку на процесс в список
thread_list = g_list_append(thread_list, thread_ref);

Барьеры. Завершение нитей процессов по списку

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

while (thread_list)
{// проходим по всем ниткам и ждем завершения
    g_thread_join((GThread*)thread_list->data);
    thread_list = thread_list->next;
}

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

Переплетнние ниток

см. Блокировки и Атомарные операции

Клубок ниток (GThreadPool)

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

Пример программы

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

#define MAX_THREADS 4 // число активных процессов
// создать клубок ниток, задает функцию для обработки блоков
GThreadPool * pool = g_thread_pool_new((GFunc)mv_predict, 
		context, MAX_THREADS, FALSE, NULL);
 . . .
for (block=0; block < NUM_BLOCKS; block++)
{// добавить в очередь данные для обработки блока
	g_thread_pool_push(pool, predicate[block], NULL);
}
 . . .
// дождаться завершения выполнения всех процессов
g_thread_pool_free(pool, FALSE/*immediately*/, TRUE/*wait*/);

Переход к многопотоковой асинхронной обработке видится очень простым. Фактически мы заменили вызов функции обработки в цикле на формирование очереди в цикле. До преобразования код выглядил так:

for (block=0; block < NUM_BLOCKS; block++)
{
	mv_predict(predicate[block], context);
}

Компиляция кода

Для сборки проекта необходимо добавить в Makefile пути поиска файлов-заголовков и библиотеку gthread

CFLAGS = $(shell pkg-config gthread-2.0 --cflags)
LDLIBS = $(shell pkg-config gthread-2.0 --libs)

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

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

На Pentium 4 2.4GHz под Windows 2000 время работы составило 4.59 с. И никакого ускорения при увеличении количества нитей не наблюдалось.

На Intel Core 2 Duo E7400 @ 2.80Ghz под Windows XP
нитоквремя исполнения
1
3,47
2
1.92
3
1.91
4
1.98
8
2.34

Измерение времени работы программы производилось на платформе Intel Core 2 Duo E7200 @ 2,53GHz под GNU/Linux (в системе зарегистрировано 2-а ядра)
нитоквремя исполнения
1
3,37
2
3,28
3
3,10
4
3,17
8
3,36
16
3,57

Измерение времени работы программы производилось на платформе Dual Intel Xeon @ 2.8GHz под GNU/Linux (в системе зарегистрировано 4-е процессора, два процессора с HT)
нитоквремя исполнения
1
2,65
2
2.10
3
1.93
4
1.98
6
1.97
8
2.10
16
3.19

Измерение времени работы программы производилось на платформе Dual AMD Opteron 250 @ 2.4GHz под GNU/Linux (в системе зарегистрировано 2-а процессора)
нитоквремя исполнения
1
3.15
2
2.71
3
2.33
4
2.30
8
2.40
16
3.58

Измерение времени работы программы производилось на платформе Intel(R) Xeon(R) CPU E5410 @ 2.33GHz GNU/Linux (в системе зарегистрировано 4-е ядра)
нитоквремя исполнения
1
2,17
2
1.93
3
1.94
4
1.95
8
2.04
16
4,04

Измерение времени работы программы производилось на платформе Dual Intel(R) Xeon(R) CPU E5410 @ 2.33GHz GNU/Linux (в системе зарегистрировано 8-м процессоров, 2 процессора с 4-я ядрами)
нитоквремя исполненияускорение
1
2.46
x1.00
2
1.56
x1.58
3
1.40
x1.76
4
1.34
x1.84
5
1.29
x1.91
6
1.26
x1.95
7
1.27
x1.94
8
1.35
x1.82
16
1,93
x1.27

Параллельное исполнение задач

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

> команда1 & команда2 & команда3 

В таблицe приведены данные для разного количества задач, каждая задача использует четыре нитки исполнения. Тестирование проводилось на платформе Dual Intel(R) Xeon(R) CPU E5410 @ 2.33GHz (8 ядер)
задач х
ниток
время исполнениявремя на задачуускорение
1х4
1,34
1.34
x1.84
2х4
1.32
0.66
x3.73
4х4
1.40
0.35
x7.03
6х4
1,93
0.32
x7.69
8х4
2,45
0.31
x7.94

Результаты для платформы Dual AMD Opteron 250 @ 2,40GHz. Каждая задача запускала 4 нитки
задач х
ниток
время исполнениявремя на задачуускорение
1х4
2.30
2.30
x1.37
2х4
3.14
1.57
x2.00

Результаты для платформы Intel Core 2 Duo E7200 @ 2,53GHz. Каждая задача запускала 3 нитки
задач х
ниток
время исполнениявремя на задачуускорение
1х3
3,10
3,10
x1,09
2х3
4,35
2,18
x1,56
2х2
4,33
2,16
x1,56

Выводы

  • Использование множества веток процессов может ускорить исполнение программы. Ускорение зависит от архитектуры процессора и не превышает 2-х раз. Использование ниток ведет к более эффективной загрузке ядра.
  • Существенное превыщение числа активных ниток-процессов над числом ядер ведет к заметному замедлению работы программы
  • Гораздо большую производительность можно получить при параллельном запуске задач. Ускорение может быть пропорционально числу ядер.
  • Наиболее эффективная загрузка вычислительных рессурсов происходит, когда количество задач равняется числу физических ядер, при этом максимальная производительность достигается при том же количестве ниток, что и для одного задания.
  • Платформа Dual Intel E5410 на порядок быстрее плтаформы Intel Core 2 Duo на параллельных задачах и более чем в 20 раз быстрее однозадачного Pentium 4.



GThreads - поддержка нитей процессов в библиотеке glib. В библиотеке также реализован механизм слежения за нитками в клубке.
PThreads - POSIX Thread.
GObject - объектная модель для использования в языке С.
Mutex - механизм блокировок реализованный в библиотеке glib.
MPI - интерфейс обмена сообщениями

(6.09.2009)