\documentclass{cmi}
\usepackage{upgreek}
\usepackage{subcaption}

\begin{document}

\classify{УДК 004.272}
\author{И.И.~Кулагин, М.Г.~Курносов}
\title{ОПТИМИЗАЦИЯ ОБНАРУЖЕНИЯ КОНФЛИКТОВ В ПАРАЛЛЕЛЬНЫХ ПРОГРАММАХ С ТРАНЗАКЦИОННОЙ ПАМЯТЬЮ%
\protect\footnote{\noindent Статья рекомендована к публикации программным комитетом Международной научной конференции <<Параллельные вычислительные технологии --- 2016>>.}%
}

\maketitle{}

% оформление аннотации
\begin{abstract}%
В настоящее время активно развивается альтернативный подход к созданию масштабируемых и потокобезопасных параллельных программ для многопроцессорных систем с общей памятью --- технология транзакционной памяти (transactional memory). Ожидается, что она войдет в стандарт языка С++17. В данной работе предложен метод оптимизации обнаружения конфликтов (конкурентного доступа потоков к общим областям памяти), возникающих при выполнении параллельных программ на базе транзакционной памяти. Реализован модуль компилятора GCC для профилирования параллельных программ и адаптивной настройки параметров реализации транзакционной памяти под программу. Эффективность метода исследована на тестовых программах из пакета STAMP.

\keywords{программная транзакционная память, параллельное программирование, профилирование, компиляторы.}
\end{abstract}

%Верхние колонтитулы
\markboth{И.И.~Кулагин, М.Г.~Курносов}{Оптимизация обнаружения конфликтов в параллельных программах с транзакционной памятью\ldots}

% Заголовки разделов формируются при помощи команд  \section{}, \subsection{}, \subsubsection{}

\section*{Введение}
\label{sec-intro}
Синхронизация доступа к разделяемым ресурсам является одной из важных и сложных задач при разработке параллельных алгоритмов для многопоточных программ. Используя примитивы синхронизации (семафоры, мьютексы и др.), программист должен обеспечить не только корректность программы --- отсутствие взаимных блокировок (deadlock, livelock) и состояний гонок за данными (data race), но и минимизировать время ожидания доступа к критическим секциям (разделяемым ресурсам). Классические методы синхронизации, основанные на механизме блокировок, позволяют создавать в коде программы критические секции, выполнение которых возможно только одним потоком в каждый момент времени \cite{herlihy_shavit_the_art}. Такие примитивы синхронизации позволяют защитить участок кода программы, одновременно выполняющийся множеством потоков. 

Анализ многопоточных программ показывает, что при одновременном выполнении потоками одной критической секций в ней может происходить обращения по разным адресам памяти и, следовательно, возникновение состояния гонки данных маловероятно. Например, такая ситуация наблюдается, если в критическую секцию помещен код добавления элемента в хеш-таблицу (рис. \ref{hashtable_add.txt}). Если все потоки в один момент времени обратятся к функции для добавления нового элемента с хеш-кодом $i$, то с большой долей вероятности ключи $key$ будут иметь разные хеш-коды и, как следствие, каждый поток будет выполнять добавление нового узла в отдельный связный список $h[i]$. Здесь блокировка мьютексом всей функции является избыточной и неэффективной.

\code[10.5cm]{frame=single}{hashtable_add.txt}{Добавление пары $(key, value)$ в хеш-таблицу $h$}

Активно развиваются два альтернативных подхода к созданию потокобезопасных и масштабируемых многопоточных программ --- это \textit{неблокирующие алгоритмы и структуры данных} (lock-free data structures) \cite{hendler_shavit} и \textit{транзакционная память} (ТП, \textit{transactional memory})~\cite{kuznetcov, shavit_touitou}. Использование неблокирующих структур данных, как правило, требует глубокой переработки многопоточных программ и совместно используемых потоками объектов в памяти~\cite{hendler_shavit}.

Менее трудоемким и прозрачным для программиста видится использование технологии транзакционной памяти, основная идея которой заключается в защите от конкурентного доступа области памяти программы, а не участка кода, как в случае использования блокировок на базе мьютексов. Известны как программные реализации транзакционной памяти (software transactional memory --- STM): LazySTM, TinySTM, GCC TM, DTMC, RSTM, STMX, STM Monad, так и аппаратные реализации в процессорах (hardware transactional memory): Intel TSX, AMD ASF, Oracle Rock, IBM POWER8, IBM PowerPC A2.

В рамках \textit{программной транзакционной памяти} программисту предоставляются языковые конструкции или API для формирования в программе \textit{транзакционных секций} \\(transactional section) --- участков кода, в которых осуществляется защита совместно используемых областей памяти. Выполнение потоками таких секций осуществляется без их блокирования. На среду выполнения (runtime) ложатся задачи по контролю за корректностью выполнения транзакций. Если во время выполнения транзакции другие потоки одновременно с ней не модифицировали защищенную область памяти, то транзакция считается корректной, и она фиксируется. Если же два или более потока при выполнении транзакций обращаются к одной и той же области памяти и как минимум один из них выполняет операцию записи, то возникает \textit{конфликт} (аналог состояния гонки данных). Для его разрешения выполнение одной или нескольких транзакций может быть либо приостановлено (до завершения конфликтующей транзакции), либо прервано, а все модифицированные ими (их потоками) области памяти приведены в исходное состояние (на момент старта транзакции) – \textit{отмена транзакции и восстановление} (cancel and rollback).

Для того чтобы обнаруживать конфликты, runtime-система должна отслеживать попытки одновременного доступа к одной и той же области памяти. Это реализуется путем поддержки информации о состоянии защищаемых регионов памяти. Возможны два уровня гранулярности контролируемых областей: \textit{уровень программных объектов} (object-based STM) и \textit{уровень слов памяти} (word-based STM).

Уровень программных объектов подразумевает поддержку runtime-системой метаданных о состоянии каждого объекта программы. Например, объектов в С++-программе.

Для реализации уровня слов памяти в простейшем случае требуется каждый байт линейного адресного пространства процесса сопровождать метаданными, что является практически невозможным. Вместо этого линейное адресное пространство процесса разбивается на фиксированные блоки, каждый из которых сопровождается метаданными о состоянии (подход, подобный прямому отображению физических адресов на кеш-память процессора) \cite{felber_fetzer_marlier_riegel, riegel_felber_fetzer}. Это приводит к тому, что множеству областей памяти соответствуют одни метаданные, что является источником возникновения ложных конфликтов. \textit{Ложный конфликт} (false conflict)--- это ситуация, при которой два или более потока во время выполнения транзакции обращаются к разным участкам линейного адресного пространства, но отображаемым на одни и те же метаданные. Поэтому runtime-система воспринимает такую ситуацию как конфликт (data race), хотя на самом деле таковой отсутствует.

Ложные конфликты существенно снижают эффективность параллельных STM-программ. Поэтому остро стоит задача разработки алгоритмов обнаружения и сокращения числа ложных конфликтов в реализациях STM.

В данной работе предлагается метод оптимизации ложных конфликтов по результатам предварительного профилирования С/С++ STM-программы. Для чего разработан программный инструментарий, который позволяет выполнять профилирование STM-программ и варьировать параметры реализации runtime-библиотеки STM в компиляторе GCC (libitm).

Работа организована следующим образом. Раздел 1 вводит основные понятия связанные с программной транзакционной памятью, содержит примеры использования данного примитива синхронизации, описывает основные аспекты реализации STM в runtime-системах, а также содержит описание предложенного метода сокращения числа ложных конфликтов. Раздел 2 раскрывает детали реализации программного инструментария для оптимизации ложных конфликтов, возникающих при выполнении параллельных программ с транзакционной памятью. В разделе 3 показаны основные результаты экспериментального исследования предложенного метода оптимизации ложных конфликтов.

\section{Метод оптимизации обнаружения конфликтов}
\label{sec-method_opt}
Международным комитетом ISO по стандартизации языка C++, в рамках рабочей группы WG21, ведутся работы по внедрению транзакционной памяти в стандарт языка. Окончательное внедрение планируется в стандарт С++17. На сегодняшний день предложен черновой вариант спецификации поддержки транзакционной памяти в С++ \cite{luchango_maurer_moir}. Она реализована в компиляторе GCC, начиная с версии 4.8 и предоставляет ключевые слова \_\_transaction\_atomic, \_\_transaction\_relaxed для создания транзакционных секций, а также \_\_transaction\_cancel для принудительной отмены транзакции. 

Для выполнения транзакционных секций runtime-системой создаются транзакции. \textit{Транзакция} (transaction) --- это конечная последовательность операций транзакционного чтения/записи памяти. Операция \textit{транзакционного чтения} выполняет копирование содержимого указанного участка общей памяти в соответствующий участок локальной памяти потока. \textit{Транзакционная запись} копирует содержимое указанного участка локальной памяти в соответствующий участок общей памяти, доступной всем потокам.

Инструкции транзакций выполняются потоками параллельно (конкурентно). После завершения выполнения транзакция может быть либо \textit{зафиксирована} (commit), либо \textit{отменена} (cancel). Фиксация транзакции подразумевает, что все сделанные в рамках нее изменения памяти становятся необратимыми. При отмене транзакции ее выполнение прерывается, а состояние всех модифицированных областей памяти восстанавливается в исходное с последующим перезапуском транзакции (\textit{откат транзакции}, rollback).

Отмена транзакции происходит в случае \textit{обнаружения конфликта} --- ситуации, при которой два или более потока обращаются к одному и тому же участку памяти и как минимум один из них выполняет операцию записи.

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

На рис. \ref{transactional_section_exm.txt} представлен пример создания транзакционной секции, в теле которой выполняется добавление элемента в хэш-таблицу множеством потоков. После выполнения тела транзакционной секции каждый поток приступит к выполнению кода, следующего за ней, в случае отсутствия конфликтов. В противном случае поток повторно будет выполнять транзакцию до тех пор, пока его транзакция не будет успешно зафиксирована.

\code[10.5cm]{frame=single}{transactional_section_exm.txt}{Добавление пары $(key, value)$ в хеш-таблицу $h$}

Основными аспектами реализации транзакционной памяти в runtime-системах являются:
\begin{itemize}
\item политика обновления объектов в памяти;
\item стратегия обнаружения конфликтов;
\item метод разрешения конфликтов.
\end{itemize}

Политика обновления объектов в памяти определяет, когда изменения объектов в рамках транзакции будут записаны в память. Распространение получили две основные политики --- ленивая и ранняя. \textit{Ленивая} политика обновления объектов в памяти (lazy version management) откладывает все операции с объектами до момента фиксации транзакции. Все операции записываются в специальном журнале (redo log), который при фиксации используется для отложенного выполнения операций. Очевидно, что это замедляет операцию фиксации, но существенно упрощает процедуры ее отмены и восстановления. Примером реализаций ТП, использующих данную политику, являются RSTM-LLT \cite{rstm_proj} и RSTM-RingSW \cite{spear_strategy_for_cm, spear_ringstm}.

\textit{Ранняя политика обновления} (eager version management) предполагает, что все изменения объектов сразу записываются в память. В журнале отката (undo log) фиксируются все выполненные операции с памятью. Он используется для восстановления оригинального состояния модифицируемых участков памяти в случае возникновения конфликта. Эта политика характеризуется быстрым выполнением операции фиксации транзакции, но медленным выполнением процедуры ее отмены. Примерами реализаций, использующих раннюю политику обновления данных, являются GCC (libitm), TinySTM \cite{felber_fetzer_marlier_riegel}, LSA-STM \cite{riegel_felber_fetzer}, Log-TM \cite{kevin_bobba_logtm}, RSTM \cite{rstm_proj} и др.
 
Момент времени, когда инициируется алгоритм обнаружения конфликта, определяется \textit{стратегией обнаружения конфликтов}. При \textit{отложенной стратегии} (lazy conflict detection) алгоритм обнаружения конфликтов запускается на этапе фиксации транзакции \cite{spear_ringstm}. Недостатком этой стратегии является то, что временной интервал между возникновением конфликта и его обнаружением может быть достаточно большим. Эта стратегия используется в RSTM-LLT \cite{rstm_proj} и RSTM-RingSW \cite{rstm_proj, spear_strategy_for_cm, spear_ringstm}. 

\textit{Пессимистичная стратегия обнаружения конфликтов}(eager conflict detection) запускает алгоритм их обнаружения при каждой операции обращения к памяти. Такой подход позволяет избежать недостатков отложенной стратегии, но может привести к значительным накладным расходам, а также, в некоторых случаях, может привести к увеличению числа откатов транзакций. Стратегия реализована в TinySTM \cite{felber_fetzer_marlier_riegel}, LSA-STM \cite{riegel_felber_fetzer} и TL2 \cite{dice_shavit_tl2}. В компиляторе GCC (libitm) реализован комбинированный подход к обнаружению конфликтов --- отложенная стратегия используется совместно с пессимистической.

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

На сегодняшний день используются два уровня гранулярности: \textit{уровень программных объектов} (object-based STM) и \textit{уровень слов памяти} (word-based STM). Уровень программных объектов подразумевает отображение объектов модели памяти языка (объекты C++, Java, Scala) на метаданные runtime-библиотеки. При использовании уровня слов памяти осуществляется отображение блоков линейного адресного пространства процесса на метаданные. Метаданные хранятся в таблице, каждая строка которой соответствует объекту программы или области линейного адресного пространства процесса. В строке содержатся номер транзакции, выполняющей операцию чтения/записи памяти; номер версии  отображаемых данных; их состояние и др. Модификация метаданных выполняется runtime-системой с помощью атомарных операций процессора.

В данной работе рассматривается реализация программной транзакционной памяти в компиляторе GCC, использующая уровень слов памяти (в версиях GCC 4.8+ размер блока – 16 байт).

На рис. \ref{metadata_exm} представлен пример организации метаданных транзакционной памяти с использованием уровня слов памяти (GCC 4.8+). Линейное адресное пространство процесса фиксированными блоками циклически отображается на строки таблицы, подобно кешу прямого отображения. Выполнение операции записи приведет к изменению поля <<состояние>> соответствующей строки таблицы на <<заблокировано>>. Доступ к области линейного адресного пространства, у которой соответствующая строка таблицы помечена как <<заблокировано>>, приводит к конфликту. 

\fig{scale=0.8}{metadata_exm}{Таблица с метаданными GCC 4.8+ (word-based STM): $B = 16$, $S = 2^{19}$}

Основными параметрами транзакционной памяти с использованием уровня слов памяти являются число $S$ строк таблицы и количество $B$ адресов линейного адресного пространства, отображаемых на одну строку таблицы. От выбора этих параметров зависит число ложных конфликтов --- ситуаций аналогичных ситуации ложного разделения данных при работе кеша процессора. В текущей реализации GCC (4.8-5.1) эти параметры фиксированы \cite{felber_fetzen_riegel_dynamic_performance_tuning}. 

При отображении блоков линейного адресного пространства процесса на метаданные runtime-библиотеки возникают коллизии. Это неизбежно, так как размер таблицы метаданных гораздо меньше размера линейного адресного пространства процесса. Коллизии приводят к возникновению ложных конфликтов. \textit{Ложный конфликт} --- ситуация, при которой два или более потока во время выполнения транзакции обращаются к разным участкам линейного адресного пространства, но сопровождаемым одними и теми же метаданными о состоянии, и как минимум один поток выполняет операцию записи. Таким образом, ложный конфликт --- это конфликт, который происходит не на уровне данных программы, а на уровне метаданных runtime-библиотеки.

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

На рис. \ref{false_conf_exm} показан пример возникновения ложного конфликта в результате коллизии отображения линейного адресного пространства на строку таблицы. Поток 1 при выполнении операции записи над областью памяти с адресом $A1$ захватывает соответствующую строку таблицы. Выполнение операции чтения над областью памяти с адресом $A2$ потоком 2 приводит к возникновению конфликта, несмотря на то что операции чтения и записи выполняются над различными адресами. Последнее обусловлено тем, что 1 и 2 отображены на одну строку таблицы метаданных.

\fig{scale=0.8}{false_conf_exm}{Пример возникновения ложного конфликта при выполнении двух транзакций (GCC 4.8+)}

В работе \cite{zilles_rajwar_false_conf} для минимизации числа ложных конфликтов предлагается использовать вместо таблицы с прямой адресацией (как в GCC 4.8+), в которой индексом является часть линейного адреса, хеш-таблицу, коллизии в которой разрешаются методом цепочек. В случае отображения нескольких адресов на одну запись таблицы каждый адрес добавляется в список и помечается тэгом для идентификации (рис. 5). Такой подход позволяет избежать ложных конфликтов, однако накладные расходы на синхронизацию доступа к метаданным существенно возрастают, так как значительно увеличивается количество атомарных операций <<сравнение с обменом>> (compare and swap --- CAS).

\fig{scale=0.7}{metadata_chaining}{Хеш-таблица для хранения метаданных}

Авторами предложен метод, позволяющий сократить число ложных конфликтов в STM-программах. Предполагается, что метаданные организованы в виде таблицы с прямой адресацией. Суть метода заключается в автоматической настройке параметров $S$ и $B$ таблицы под динамические характеристики конкретной STM-программы. Метод включает три этапа.

\textbf{Этап 1}. Внедрение функций библиотеки профилирования в транзакционные секции. На первом этапе выполняется компиляция C/C++ STM-программы с использованием разработанного модуля анализа транзакционных секций и внедрения вызова функций библиотеки профилирования (модуль расширения GCC). В ходе статического анализа транзакционных секций STM-программ выполняется внедрение кода для регистрации обращений к функциям Intel TM ABI (\_ITM\_beginTransaction, \_ITM\_comitTransaction, \_ITM\_LU4, \_ITM\_WU4 и др.). Детали реализации модуля описаны ниже.

\textbf{Этап 2}. Профилирование программы. На данном этапе выполняется запуск STM-программы в режиме профилирования. Профилировщик регистрирует все операции чтения/записи памяти в транзакциях. В результате формируется протокол (trace), содержащий информацию о ходе выполнения транзакционных секций:
\begin{itemize}
\item адрес и размер области памяти, над которой выполняется операция;
\item временная метка (timestamp) начала выполнения операции.
\end{itemize}

\textbf{Этап 3}. Настройка параметров таблицы. По протоколу определяются средний размер $W$ читаемой/записываемой области памяти во время выполнения транзакций. По значению $W$ подбираются субоптимальные параметры $B$ и $S$ таблицы, с которыми STM-программа компилируется. Эксперименты с тестовыми STM-программами из пакета STAMP (6 типов STM-программ) позволили сформулировать эвристические правила для подбора параметров $B$ и $S$ по значению $W$. Значение параметра $S$ целесообразно выбирать из множества $\{2^{18}, 2^{19}, 2^{20}, 2^{21}\}$. Значение параметра $B$ выбирается следующим образом:
\begin{itemize}
\item если $\textit{W} = 1$ байт, то $\textit{B} = 2^{4}$ байт;
\item если $\textit{W} = 4$ байт, то $\textit{B} = 2^{6}$ байт;
\item если $\textit{W} = 8$ байт, то $\textit{B} = 2^{7}$ байт;
\item если $\textit{W} >= 64$ байт, то $\textit{B} = 2^{8}$ байт.
\end{itemize}

\section{Программный инструментарий для сокращения ложных конфликтов}
Авторами разработан программный инструментарий (STM false conflict optimizer) для оптимизации ложных конфликтов, возникающих при выполнении параллельных программ с транзакционной памятью. Инструментарий позволяет выполнять профилирование STM-программ. Информация, полученная в результате профилирования, предоставляет достаточно сведений о динамических характеристиках транзакционных секций для того, чтобы ответить на вопрос: <<Фиксации каких транзакций или операции над какими данными приводят к отмене других транзакций?>>. Кроме этого, разработанное программное средство позволяет определить значения субоптимальных значений параметров реализации runtime-системы ТП, а именно число строк таблицы метаданных о состоянии областей памяти и количество адресов линейного адресного пространства, отображаемых на одну строку таблицы.

\subsection{Функциональная структура пакета}
Программный инструментарий состоит из трех основных компонентов (рис. \ref{stm_fc_optimizer}):
\begin{itemize}
\item модуль внедрения функций библиотеки профилирования в код транзакционных секций ($tm\_prof\_analyzer$);
\item библиотека профилирования параллельной программы с транзакционной памятью ($libitm\_prof$);
\item модуль анализа протокола выполнения транзакционных секций, установки значений параметров реализации ($tm\_proto\_analyzer$).
\end{itemize}

\fig{scale=0.8}{stm_fc_optimizer}{Функциональная структура разработанного пакета; $1$ --- компиляция STM-программы; $2$ --- запуск STM-программы под управление профилировщика; $3$ --- обращение к функциям профилировщика}

\subsection{Внедрение функций профилировщика}
STM-компилятор осуществляет трансляцию транзакционных секций в последовательность вызовов функций runtime-системы поддержки TM~\cite{olszewski_cutler_judostm}. Компания Intel предложила спецификацию ABI для runtime-систем поддержки транзакционной памяти --- Intel~TM~ABI~\cite{intel_tm_abi}. Компилятор GCC, библиотека libitm, реализует этот интерфейс начиная с версии 4.8. На рис. \ref{gcc_transform_exm.txt} представлен пример трансляции компилятором GCC транзакционной секции в обращения к функциям Intel TM ABI.

\code[16cm]{frame=single}{gcc_transform_exm.txt}{Трансляция транзакционной секции компилятором GCC; код слева --- исходная транзакционная секция; код справа --- промежуточное представление трансформированной транзакционной секции}

В общем случае последовательность выполнения транзакции следующая: 
\begin{enumerate}
\item Создание транзакции (вызов \_ITM\_beginTransaction) и анализ ее состояния. Если состояние транзакции содержит флаг принудительной отмены, то выполнение продолжается с метки <L3>, т.е. осуществляется выход из транзакции, иначе выполнение тела транзакции начинается с метки <L2>.
\item  Выполнение транзакции. Если выполняется принудительная отмена транзакции, то в состоянии устанавливается флаг принудительной отмены (a\_abortTransaction) и управление передается метке <L1>.
\item Попытка фиксации транзакции (вызов \_ITM\_commitTransaction). В случае возникновения конфликта транзакция отменяется, в состояние транзакции записывается причина отмены и выполнение транзакции повторяется начиная с метки <L1>.
\end{enumerate}

Разработанный модуль $tm\_prof\_analyzer$ внедрения функций библиотеки профилирования выполнен в виде встраиваемого модуля компилятора GCC. Программист компилирует STM-программу с ключом $-fplugin=tm\_prof\_analyzer.so$. Модуль внедрения выполняет анализ промежуточного представления $GIMPLE$ транзакционных секций и добавляет функции регистрации обращений к функциям Intel TM ABI: регистрация начала транзакции и ее фиксации, транзакционное чтения/запись областей памяти.

На рис. \ref{tm_prof_analyzer_exm.txt} представлен пример внедрения вызовов функций библиотеки профилирования в транзакционную секцию. Функции с префиксом $tm\_prof\_$ выполняют регистрацию событий.

\code[16cm]{frame=single}{tm_prof_analyzer_exm.txt}{Встраивание в транзакционную секцию функций библиотеки профилирования; код слева --- исходная транзакционная секция; код справа --- промежуточное представление трансформированной транзакционной секции}

Во время выполнения STM-программы под управлением профилировщика ($libitm\_prof$), функции регистрации обращений к интерфейсам Intel TM ABI заносят в протокол адреса и размер областей памяти, над которыми выполняются операции, а также время начала выполнения операций. После завершения выполнения STM-программы формируется протокол выполнения программы, на основе которого модуль анализа ($tm\_proto\_analyzer$) осуществляет выбор субоптимальных параметров таблицы метаданных транзакционной памяти.

\section{Эксперименты}
Экспериментальное исследование проводилось на вычислительной системе, оснащенной двумя четырехъядерными процессорами Intel Xeon E5420. В данных процессорах отсутствует поддержка аппаратной транзакционной памяти (Intel TSX). В качестве тестовых программ использовались многопоточные STM-программы из пакета STAMP \cite{spear_strategy_for_cm, spear_ringstm, dice_shavit_tl2}. Число потоков варьировалось от 1 до 8. Тесты собирались компилятором GCC 5.1.1. Операционная система GNU/Linux Fedora 21 x86\_64. 

В рамках экспериментов измерялись значения двух показателей:
\begin{itemize}
\item время $t$ выполнения STM-программы;
\item количество $C$ ложных конфликтов в программе.
\end{itemize}

На рис.~\ref{fc_S_const}, ~\ref{fc_B_const}, ~\ref{time_B_const}, ~\ref{time_B_const} показана зависимость количества $C$ ложных конфликтов и времени $t$ выполнения теста от числа потоков при различных значениях параметров $B$ и $S$. Результаты приведены для программы genome из пакета STAMP. В ней порядка 10 транзакционных секций, реализующих операции над хеш-таблицей и связными списками. Видно, что увеличение значений параметров $S$ и $B$ приводит к уменьшению числа возможных коллизий (ложных конфликтов), возникающих при отображении адресов линейного адресного пространства процесса на записи таблицы. При размере таблицы $2^{21}$ записей, на каждую из которых отображается $2^{6}$ адресов линейного адресного пространства, достигается минимум времени выполнения теста genome, а также минимум числа ложных конфликтов. 

\begin{figure}
\centering
\begin{subfigure}{0.5\textwidth}
  \centering
  \includegraphics[width=0.8\linewidth]{fc_S_const}
  \caption{$S = 2^{19}$}
  \label{fc_S_const}
\end{subfigure}%
\begin{subfigure}{0.5\textwidth}
  \centering
  \includegraphics[width=0.8\linewidth]{fc_B_const}
  \caption{$B = 2^6$}
  \label{fc_B_const}
\end{subfigure}
\caption{Зависимость числа $C$ ложных конфликтов от числа $N$ потоков}
\label{fc_N}
\end{figure}

\begin{figure}
\centering
\begin{subfigure}{0.5\textwidth}
  \centering
  \includegraphics[width=0.8\linewidth]{time_S_const}
  \caption{$S = 2^{19}$}
  \label{time_S_const}
\end{subfigure}%
\begin{subfigure}{0.5\textwidth}
  \centering
  \includegraphics[width=0.8\linewidth]{time_B_const}
  \caption{$B = 2^6$}
  \label{time_B_const}
\end{subfigure}
\caption{Зависимость времени $t$ выполнения теста от числа $N$ потоков}
\label{time_N}
\end{figure}

Время выполнения теста genome удалось сократить в среднем на 20\% за счет минимизации числа ложных конфликтов.

\section*{Заключение}
\label{sec-conclusion}
Основным вкладом данной работы является метод оптимизации параметров внутренних структур данных runtime-библиотеки транзакционной памяти компилятора GCC (libitm) под конкретное приложение. Создан программный инструментарий сокращения числа ложных конфликтов в STM-программах. Программный инструментарий позволяет осуществлять инструментацию и профилирование параллельных STM-программ. Результаты профилирования показывают хронологию выполнения транзакций. В данной работе результаты профилирования используются только для выбора значений параметров реализации runtime-библиотеки транзакционной памяти, однако, они могут быть использованы и для других целей, например, для выбора политика обновления объектов в памяти и стратегии обнаружения конфликтов.

Предложенный метод был экспериментально исследован на тестовых программах из пакета STAMP. Эксперименты показали, что применяя разработанный метод, время выполнения теста genome удалось сократить на 20\% за счет минимизации числа ложных конфликтов.

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

\vspace{1em}
{\it Работа выполнена в СПбГЭТУ при финансовой поддержке Министерства образования и науки Российской Федерации в рамках договора № 02.G25.31.0149 от 01.12.2015 г.}

\begin{biblio}

\bibitem{herlihy_shavit_the_art}
Herlihy~М., Shavit~N. The Art of Multiprocessor Programming. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 2008. 508 p.

\bibitem{hendler_shavit}
Hendler~D.,~Shavit~N.,~Yerushalmi~L. A scalable lock-free stack algorithm // Proceedings of the sixteenth annual ACM symposium on Parallelism in algorithms and architectures. 2004. P. 206--215.

\bibitem{kuznetcov}
Кузнецов~С.Д. Транзакционная память. URL. \\www.citforum.ru/programming/digest/transactional\_memory/ (дата обращения: 21.06.2016).

\bibitem{shavit_touitou}
Shavit~N., Touitou~D. Software Transactional Memory // Proceedings of the fourteenth annual ACM symposium on Principles of distributed computing. Aug. 1995. New York, NY, USA, P. 204--213.

\bibitem{felber_fetzer_marlier_riegel}
Felber~P., Fetzer~C.,Marlier~P., Riegel~T. Time-based Software Transactional Memory // IEEE Transactions on Parallel and Distributed Systems. December 2010. Vol. 21, Issue 12,  P. 1793--1807.

\bibitem{riegel_felber_fetzer}
Riegel~T., Felber~P., Fetzer~C. A Lazy Snapshot Algorithm with Eager Validation // 20th International Symposium on Distributed Computing. 2006.

\bibitem{luchango_maurer_moir}
Luchango~V., Maurer~J., Moir~M. Transactional memory for C++. URL. http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2013/n3718.pdf (дата обращения: 21.06.2016).

\bibitem{rstm_proj}
Scott~M.L. Rochester Software Transactional Memory Runtime. URL. www.cs.rochester.edu/research/synchronization/rstm/ (дата обращения: 21.06.2016).

\bibitem{spear_strategy_for_cm}
Spear~M.F., Dalessandro~L., Marathe~V.J., Scott~M.L. A comprehensive strategy for contention management in software transactional memory // Proc. 14th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming. February 2009. P. 141--150.

\bibitem{kevin_bobba_logtm}
Moore~k.E., Bobba~J., Moravan~M.J., Hill~M.D., Wood~D.A. LogTM: Log-based transactional memory // Proceedings of the 12th International Symposium on High-Performance Computer Architecture. February 2006. P. 254--265. 

\bibitem{spear_ringstm}
Spear~M.F., Michael~M.M., Praun~C. RingSTM: scalable transactions with a single atomic instruction // Proceedings of the 20th Annual Symposium on Parallelism in Algorithms and Architectures. June 2008. P. 275--284.

\bibitem{dice_shavit_tl2}
Dice~D., Shalev~O., Shavit~N. Transactional locking II // Proceedings of the 20th International Symposium on Distributed Computing. September 2006. Vol. 4167, P. 194--208.

\bibitem{felber_fetzen_riegel_dynamic_performance_tuning}
Felber~P., Fetzer~C., Riegel~T. Dynamic performance tuning of word-based software transactional memory // Proceedings of the 17th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming. 2008. P. 237--246. 

\bibitem{zilles_rajwar_false_conf}
Zilles~C., Rajwar~R. Implications of false conflict rate trends for robust software transactional memory. URL http://zilles.cs.illinois.edu/papers/tm\_false\_conflicts.iiswc2007.pdf (дата обращения: 21.06.2016).

\bibitem{olszewski_cutler_judostm}
Olszewski~M., Cutler~J., Steffan~J.G. JudoSTM: A Dynamic Binary-Rewriting Approach to Software Transactional Memory // Proceedings of the 16th International Conference on Parallel Architecture and Compilation Techniques. 2007. P. 365--375.

\bibitem{intel_tm_abi}
Intel Corporation. Intel Transactional Memory Compiler and Runtime Application Binary Interface. URL. https://software.intel.com/sites/default/files/m/5/a/2/a/f/8097-Intel\_TM\_ABI\_1\_0\_1.pdf (дата обращения: 21.06.2016)

\end{biblio}

% Сведения об авторах (Ф.И.О.(полностью), степень, звание, кафедра (отдел), вуз, e-mail)

{Кулагин Иван Иванович,
Кафедра вычислительных систем,
Федеральное государственное бюджетное образовательное учреждение высшего образования <<Сибирский государственный университет телекоммуникаций и информатики>>,
ivan.i.kulagin@gmail.com}

{Курносов Михаил Георгиевич,
к.т.н.,
Федеральное государственное автономное образовательное учреждение высшего образования <<Санкт-Петербургский государственный электротехнический университет <<ЛЭТИ>> им. В.И. Ульянова (Ленина)>>,
mkurnosov@gmail.com}

{\phantom{eee} \hrule \vskip 4 pt}
\classify{} % Код MSC не нужен
%\classify{MSC 00000} % Коды MSC см. http://www.ams.org/msc/
\author{I.I.~Kulagin, {\rm  Federal State Institution of Higher Education <<Siberian State University of
Telecommunications and Information Science>> (Novosibirsk, Russian Federation)},\\ M.G.~Kurnosov, {\rm  Saint-Petersburg Electrotechnical University (Saint-Petersburg, Russian Federation)}}
\title{OPTIMIZATION OF CONFLICT DETECTION IN PARALLEL PROGRAMS WITH TRANSACTIONAL MEMORY}
\maketitle{}

\begin{abstract}%
    Transactional memory is a perspective abstraction for the creating
    a scalable parallel programs for multi-core systems. It will be 
    included in C++17. In this work, are proposed optimization method
    of conflicts detection, that accur in parallel programs with the 
    software transactional memory during execution. The autors have 
    implemented a module for GCC compiler for profiling parallel 
    programs with software transactional memory and a tool for adaptive 
    tuning runtime-library. The efficiency of method is investigated 
    on the STAMP benchmarks.

	\keywordsen{software transactional memory, parallel programming, profiling, compilers.}
\end{abstract}

\begin{biblio_lat}
%\itemsep -2pt

\bibitem{herlihy_shavit_the_art}
Herlihy~М., Shavit~N. The Art of Multiprocessor Programming. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 2008. 508 p.

\bibitem{hendler_shavit}
Hendler~D.,~Shavit~N.,~Yerushalmi~L. A scalable lock-free stack algorithm // Proceedings of the sixteenth annual ACM symposium on Parallelism in algorithms and architectures. 2004. P. 206--215.

\bibitem{kuznetcov}
Kuznetsov S.D. Transaktsionnaya pamat [Transactional Memory]. URL. http://citforum.ru/programming/digest/transactional\_memory/ (accessed: 21.06.2016). (in Russian)

\bibitem{shavit_touitou}
Shavit~N., Touitou~D. Software Transactional Memory // Proceedings of the fourteenth annual ACM symposium on Principles of distributed computing. Aug. 1995. New York, NY, USA, P. 204--213.

\bibitem{felber_fetzer_marlier_riegel}
Felber~P., Fetzer~C.,Marlier~P., Riegel~T. Time-based Software Transactional Memory // IEEE Transactions on Parallel and Distributed Systems. December 2010. Vol. 21, Issue 12,  P. 1793--1807.

\bibitem{riegel_felber_fetzer}
Riegel~T., Felber~P., Fetzer~C. A Lazy Snapshot Algorithm with Eager Validation // 20th International Symposium on Distributed Computing. 2006.

\bibitem{luchango_maurer_moir}
Luchango~V., Maurer~J., Moir~M. Transactional memory for C++. URL. http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2013/n3718.pdf (accessed: 21.06.2016).

\bibitem{rstm_proj}
Scott~M.L. Rochester Software Transactional Memory Runtime. URL. www.cs.rochester.edu/research/synchronization/rstm/ (accessed: 21.06.2016).

\bibitem{spear_strategy_for_cm}
Spear~M.F., Dalessandro~L., Marathe~V.J., Scott~M.L. A comprehensive strategy for contention management in software transactional memory // Proc. 14th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming. February 2009. P. 141--150.

\bibitem{kevin_bobba_logtm}
Moore~k.E., Bobba~J., Moravan~M.J., Hill~M.D., Wood~D.A. LogTM: Log-based transactional memory // Proceedings of the 12th International Symposium on High-Performance Computer Architecture. February 2006. P. 254--265. 

\bibitem{spear_ringstm}
Spear~M.F., Michael~M.M., Praun~C. RingSTM: scalable transactions with a single atomic instruction // Proceedings of the 20th Annual Symposium on Parallelism in Algorithms and Architectures. June 2008. P. 275--284.

\bibitem{dice_shavit_tl2}
Dice~D., Shalev~O., Shavit~N. Transactional locking II // Proceedings of the 20th International Symposium on Distributed Computing. September 2006. Vol. 4167, P. 194--208.

\bibitem{felber_fetzen_riegel_dynamic_performance_tuning}
Felber~P., Fetzer~C., Riegel~T. Dynamic performance tuning of word-based software transactional memory // Proceedings of the 17th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming. 2008. P. 237--246. 

\bibitem{zilles_rajwar_false_conf}
Zilles~C., Rajwar~R. Implications of false conflict rate trends for robust software transactional memory. URL http://zilles.cs.illinois.edu/papers/tm\_false\_conflicts.iiswc2007.pdf (accessed: 21.06.2016).

\bibitem{olszewski_cutler_judostm}
Olszewski~M., Cutler~J., Steffan~J.G. JudoSTM: A Dynamic Binary-Rewriting Approach to Software Transactional Memory // Proceedings of the 16th International Conference on Parallel Architecture and Compilation Techniques. 2007. P. 365--375.

\bibitem{intel_tm_abi}
Intel Corporation. Intel Transactional Memory Compiler and Runtime Application Binary Interface. URL. https://software.intel.com/sites/default/files/m/5/a/2/a/f/8097-Intel\_TM\_ABI\_1\_0\_1.pdf (accessed: 21.06.2016)

\end{biblio_lat}

%\begin{flushright}
%{ \it Поступила в редакцию 2 марта 2016 г.}
%\end{flushright}

\end{document}
