Макро-структуры типа «цикл» в многопоточных программах на языке С++

Макро-структуры типа «цикл» в многопоточных программах на языке С++

Мельников С. В.

Аннотация

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

Ключевые слова: программирование, многопоточность, диссипативные макро-структуры.

В последнее время в литературе все большее внимание в программировании уделяется параллелизму [1,2,3,4]. Это в первую очередь обусловлено наступлению предела масштабирования производительности вычислительного устройства общего назначения (ядра процессора). Производители процессоров пытаются компенсировать это увеличивая количество вычислительных устройств в одном корпусе (увеличения количества ядер в процессоре).

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

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

A X + D

A + B + 2X + Y —3X + D + E

A + B + X —Y + D + E X D

где A, B, X, Y, D, E — объекты некоторых типов. Каждое правило, в соответствии с которым трансформируются объекты выполняется в контексте отдельного потока. Подобного рода трансформации могут осуществляться в широком классе программ, не обязательно написанных на объектно-ориентированных языках С++, Java, Delphi, и др.

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

void R3() {

Molecule A, B, X;

if (StA.try_pop(A)){ if (StB.try_pop(B)) { if (StX.try_pop(X)) { StY.push(Molecule()); StD.push(Molecule()); StE.push(Molecule()); } else {

StA.push(A); StB.push(B);

}

} else

StA.push(A);

}

}

Каждое правило запускается в контексте отдельного потока (англ. thread) выполнения исполняемого кода. Для стабильности результатов можно применить привязку (англ. affinity) потоков к физическим вычислительным ядрам с помощью интерфейса операционной системы (например, для Windows функция SetThreadAffinityMask). Дополнительно запускаются потоки, обеспечивающие наполнение очередей объектами типов A и B. Несколько выполняющихся потоков команд, выполняющих преобразования - используют глобальные очереди объектов, т.е. используется модель вычислительной системы с общей памятью.

Реализация выполнена на языке C++ с применением библиотеки Intel Threading Building Blocks (сокращенно TBB) [4]. Хранилища объектов A, B, X, Y, D, E представляют собой объекты параметризованного класса tbb::concurrent_ bounded_queue<T>. Параметризация класса с помощью шаблонов (англ. generics) языка С++ позволяет производить эффективные оптимизации времени компиляции (англ. compile-time optimization). Класс concurrent_bounded_queue является потокобезопасным (англ. thread safety). Потоковая безопасность реализована с применением атомарных блокировок, а не событий синхронизации режима ядра, что крайне положительно сказывается на производительности. Для компиляции модели, представляющей собой программу на языке С++, был применен компилятор Intel C++ 12, обеспечивающий максимальное быстродействие исполняемого бинарного кода [5].

Анализ работы модели проводился в среде компьютерной алгебры MathCad. Тестирование проводилось на ЭВМ с процессором AMD Phenom II 9550, имеющим четыре вычислительных ядра. Во время работы программы записывалось количество объектов X и Y, существующих в системе и характеризующих ее состояние. В результате тестового выполнения была получена следующая траектория состояния системы в фазовом пространстве:

Технические науки

Рис. 1. Траектория системы в фазовом пространстве

На Рис. 1 по оси абсцисс показано количество объектов типа X, существующих в системе; по оси ординат - количество объектов У На графике видны макро-циклы количества объектов X и У Данные циклы не могут быть объяснены псевдослучайными флуктуациями работы планировщика операционной системы.

Для дальнейшего анализа был построен график зависимости количества объектов X и У (ось ординат; сплошная и пунктирная линии, соответственно), от времени (ось абсцисс) (см. Рис. 2, Рис. 3):

Рис. 2. Зависимость количества объектов X, Y от времени

Рис. З. Зависимость количества объектов X, Y от времени

На графике хорошо видны возникшие большие макроциклы концентраций и сменяющие их последовательности малых циклов. Демонстрируемое системой поведение можно назвать динамическим хаосом, что показывает возникновение математического хаоса еще в одном классе динамических систем — в информационных системах [3].

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

Список использованных источников

1. Anthony Williams, "C++ Concurrency in Action: Practical Multithreading", Manning Publications, 2012

2. Peter Pacheco, "An Introduction to Parallel Programming", Morgan Kaufmann, 2011

3. Мельников C.B. Диссипативные структуры типа «цикл» в ПО, существующем в режиме многопоточного выполнения исполняемого программного кода. II Современные проблемы науки и образования - 2012.-№6. (приложение «Технические науки»). - C. 10

4. Intel Threading building blocks home page II http:ll threadingbuildingblocks.org/

5. Principle Technologies, Performance comparison of Intel C++ Compiler 9.1 for Linux and GNU gcc 4.1.1 on AMD- and Intel-processor-based systems, Test report, June 2006

Всероссийский журнал научных публикаций

№ 3(18) 2013

29