Поиск мест создания консистентных контрольных

on

1. Введение. Контрольная точка (КТ) — информация о состоянии задачи, которая позволяет продолжить ее выполнение с данного момента времени. Механизм контрольных точек для параллельных программ применяется для обеспечения отказоустойчивости, а также для того, чтобы предоставить возможности более гибкого планирования задач в параллельной вычислительной системе . Создание контрольных точек для параллельных программ, использующих библиотеку MPI, имеет свою специфику: кроме состояния каждой ветви как последовательной программы в контрольную точку входит состояние коммуникационной среды, также невозможно одновременно сохранить состояние всех ветвей параллельной программы. В силу этого для обеспечения корректного восстановления из контрольной точки вводятся ограничения на состояние задачи в момент создания контрольной точки. Контрольная точка называется консистентной, если при восстановлении из нее не будет потеряно или продублировано ни одно сообщение. Рассмотрим механизм создания контрольных точек для параллельной МР1-программы (библиотека libcheckpoint). Эта библиотека обеспечивает создание консистентных контрольных точек, если в момент создания контрольной точки выполнены следующие условия (в дальнейшем будем называть их критериями консистентносгпи). 1. Ни один процесс не заблокирован в состоянии ожидания сообщения. 1 Работа выполнена при поддержке Российского фонда фундаментальных исследований, проект № 05-01-00719-а. ВБСТН. МОСК. УН-ТА. СЕР. 15. ВЫЧИСЛ. МАТЕМ. И КИБЕРН. 2007. № 3 47 2. Ни одно сообщение не находится в буферах MPI и в коммуникационных каналах. (Все сообщения отправлены; все операции по приему сообщений завершены, т.е. содержимое сообщения скопировано в буфер программы.) Кроме того, библиотека libcheckpoint требует явного указания мест создания контрольных точек в исходном коде программы (при этом выбранные места должны удовлетворять критерию консистент-ности). Выбор таких мест может быть осуществлен вручную программистом, так как в некоторых задачах это сделать достаточно просто: критериям консистентности обычно удовлетворяет окончание внешней итерации, состояние после выполнения групповой операции MPI, затрагивающей все процессы, и т.п. В данной статье будет рассмотрен подход, позволяющий автоматически выявлять места в параллельной программе, в которых возможно создание консистентных контрольных точек, в тех ситуациях, когда выявление таких мест вручную затруднительно. Этот подход основан на анализе трассы параллельной программы. 2.Детерминированность MPI-программ. Так как наш подход основывается на такой статической характеристике задачи, как ее трасса, мы должны сделать предположения о том, что трасса исследуемой задачи не изменяется от запуска к запуску или изменяется контролируемым образом. Источником недетерминированности для последовательной программы является ее взаимодействие с окружением. Поскольку каждая ветвь параллельной программы представляет собой последовательную программу, ее недетерминированность (т.е. различие трассы программы от запуска к запуску) может быть обусловлена: 1)) обращением к недетерминированным вызовам MPI; 2)) зависимостью от входных данных; 3)) другими причинами (например, использование датчика псевдослучайных чисел, взаимодействие с другими процессами, минуя средства MPI, и т.п.). Мы не будем рассматривать программы, в которых недетерминированность обусловлена третьим пунктом. Разрабатываемый нами подход может быть применен к некоторым задачам, трасса которых изменяется в зависимости от входных данных, а недетерминированность, связанная с вызовом MPI-функций, может быть проанализирована. Отметим, что в стандарте MPI отдельно отмечены источники потенциальной недетерминированности: ими являются неблокирующие операции и получение сообщения без указания отправителя или тега (MPI_ANY_TAG и MPLANYJ50URCE). Необходимо заметить, что такие потенциально недетерминированные вызовы могут оказаться детерминированными, например вызов функции получения сообщения без указания отправителя при условии, что только одно сообщение может быть получено в данный момент. Для сообщений, отправленных от одного процесса к другому с одним тегом, порядок сохраняется (FIFO). Под отсутствием зависимости трассы MPI-программы от входных данных понимается не отсутствие изменений в результатах работы программы и не отсутствие изменений в содержимом передаваемых через MPI сообщений, а неизменность последовательности событий отправки и приема сообщений. 3.Причинно-следственные зависимости. Введем некоторые термины. Момент отправки сообщения — момент вызова одной из функций семейства MPI_{,B,S,R,l}send. Нам не важен фактический момент отправки сообщения, так как он произойдет заведомо раньше, чем завершится соответствующий ему прием сообщения, а в промежутке времени между отправкой сообщения и его приемом контрольная точка создаваться не может. Момент приема сообщения — момент возврата из функции MPI_Recv или соответствующей для MPI_Irecv функции, сообщающей об успешном приеме сообщения. Действие параллельной программы — это операция по приему или отправке сообщения (мы не рассматриваем внутренние действия, такие, как вычисления, так как они не влияют на выбор места создания контрольной точки). Определим понятие причинно-следственного предшествования между двумя действиями. 1.. Два действия одного процесса причинно-следственно предшествуют, если одно следует за другим (во времени). 2.. Действие по отправке сообщения одного процесса причинно-следственно предшествует соответствующему ему действию по приему этого сообщения в другом процессе. 1.48 ВЕСТН. МОСК. УН-ТА. СЕР. 15. ВЫЧИСЛ. МАТЕМ. И КИБЕРН. 2007. № 3 3. Два любых других действия причинно-следственно предшествуют, если существует цепочка действий, начинающаяся с первого действия и заканчивающаяся последним, такая, что два любых соседних действия в этой цепочке причинно-следственно предшествуют друг другу в смысле пунктов 1 и 2. Обозначим отношение причинно-следственного предшествования между действиями символом «- «. Причинно-следственное предшествование на множестве действий является отношением частичного порядка. Действительно, оно антирефлексивно (очевидно), транзитивно (следует из пункта 3 определения). Отношение причинно-следственного предшествования очень удобно при анализе параллельных программ, оно позволяет сформулировать простое необходимое условие консистентности, обнаружить соответствующие друг другу операции по приему и отправке сообщений, а также проводить анализ потенциально недетерминированных мест в параллельных программах. Однако выявление данного отношения является сложной задачей, поэтому при анализе используется еще одно понятие — векторный таймер. Показания компьютерных часов на узлах паралелльного компьютера невозможно синхронизировать с точностью, необходимой для упорядочения событий в параллельной программе. Так как нет необходимости точно измерять промежутки времени между событиями, а достаточно лишь определить их порядок, применяют подходы, не использующие системных часов. Например, одним из таких подходов являются часы Лампорта . Рассмотрим более сложный механизм, находящийся в непосредственной связи с причинно-следственным предшествованием. Каждая ветвь г параллельной программы поддерживает внутренние часы Тг, являющиеся целочисленным вектором длины п, где п — количество ветвей программы. В начале выполнения программы в каждой ветви часы инициализируются значением . Перед выполнением действия по отправке сообщения ветвь с номером i увеличивает компоненту Т\ своего таймера на единицу: Т\ = Т\ + 1. К каждому отправляемому сообщению ветвь прикрепляет текущее показание часов. При получении сообщения ветвь j получает также показания часов отправителя Т1 и устанавливает свои часы в значение Т3к = max(Tj?,T?) V/e 6 {l…n}, а затем увеличивает «свою» компоненту часов: Т3 = Т3 + 1. На множестве показаний часов (на множестве целочисленных векторов длины п) можно определить отношение частичного порядка » » : J 1. Описание такого рода векторных часов и примеры их использования для анализа параллельных программ можно найти, например, в работах . Будем называть показаниями часов, соответствующими действию параллельной программы, показания часов ветви, выполнившей действие после выполнения данного действия. Тогда имеют место следующие два утверждения. Утверждение 1. Пусть имеет место цепочка действий, причинно-следственно предшествующих друг другу: а — Ъ — … — с, тогда соответствующие им показания часов связаны соотношением Та ТЬ … Тс. Утверждение 2. Пусть есть цепочка показаний часов, соответствующих действиям в параллельной программе, связанных соотношением Та Тъ … Тс, тогда соответствующие им действия причинно-следственно предшествуют: а — b — … — с. Из этих двух утверждений вытекает, что а — Ь Та Тъ. Следовательно, данное определение таймера удовлетворяет условиям часов Лампорта, описанным в . 4. Алгоритм поиска мест создания консистентных контрольных точек. Для поиска возможных мест создания консистентных контрольных точек достаточно зафиксировать действия параллельной программы. Поэтому трассой параллельной программы мы будем называть просто последовательность действий параллельной программы. Для каждого действия в трассе должен быть записан тип действия, номер ветви, в которой оно произошло, таймер, связанный с данным действием. Также записывается дополнительная информация о действии, позволяющая улучшить анализ: момент времени, когда действие произошло (относительно ветви, выполнившей действие), место в исходном коде программы, откуда произошло обращение к данной функции MPI, и т.п. п-ч ВЕСТН. МОСК. УН-ТА. СЕР. 15. ВЫЧИСЛ. МАТЕМ. И КИБЕРН. 2007. № 3 49 Для определения места создания контрольной точки в параллельной программе необходимо указать момент создания контрольной точки в каждой ветви программы. Контрольные точки могут быть поставлены между любыми двумя действиями в параллельной программе. На п актике создание контрольной точки может осуществляться непосредственно до или после действия (напомним, что под действием понимается прием, отправка сообщения и т.п.). Такая комбинация из те выбранных мест создания контрольной точки (по одному в каждой ветви) может быть оценена с точки зрения удовлетворения требований, сформулированных в разделе 1, а также с точки зрения других критериев, таких, как: •·удобство для программиста исходной задачи: контрольные точки во всех ветвях создаются на одной и той же строчке исходного кода программы, при каждом входе на строчку может быть создана контрольная точка; •·эффективность: ожидаемое время синхронизации (время, которое потребуется для того, чтобы все ветви программы достигли места создания контрольной точки) является малым; •·интервал между контрольными точками: временной интервал между выбранными контрольными точками удовлетворяет требованиям, которые пользователь предъявил перед анализом. Сформулируем необходимые требования к месту контрольной точки (из раздела 1), выразив их в терминах трассы параллельной программы. Пусть контрольная точка в ветви г создается после действия а; и перед действием 6^. При вызове функции создания контрольной точки будет выполнена синхронизация, т.е. программа будет приостановлена до тех пор, пока все ветви не сделают вызова функции создания контрольной точки. Такой вызов они могут сделать только тогда, когда все действия а; завершатся; отметим, что в этот момент действия Ъ{ еще заведомо не выполнятся. Запишем необходимое условие создания контрольной точки: Vfc,/e {1,…,п} : (ЧУЬкЭта запись означает, что действие, предшествующее созданию контрольной точки, не может причинно-следственно следовать за действием в любой ветви программы, которое будет выполнено после создания контрольной точки. Пусть, например, ау У b3. Тогда контрольная точка не может быть создана до того, как произойдет действие а\, но оно не может иметь место до того, как будет выполнено действие Ь3, которое произойдет только после создания контрольной точки. Данная ситуация является тупиковой. Достаточным условием возможности создания контрольной точки в выбранных местах является завершенность всех операций по передаче и приему сообщений. Так, если все операции завершены, то ни один процесс не может быть заблокирован в состоянии получения сообщений и все отправленные сообщения должны быть получены (коммуникационные каналы и буферы MPI пусты). Рассмотрим алгоритм поиска возможных мест создания контрольных точек. В тексте алгоритма будут использованы следующие обозначения: те — количество ветвей (процессов) в параллельной задаче; ej — действие, непосредственно следующее за действием ej в ветви j. Алгоритм 1. Поиск возможных мест создания консистентных контрольных точек с использованием трассы МР1-програжмы. 1.. Рассмотрим все возможные наборы действий длины те, в которых все действия произошли в разных ветвях: {ej, е2,…, е„}. При этом пусть действие е; произошло в ветви г. 2.. Если для Vi ? {1,…, те} в паре (е^, е;) оба действия являются детерминированными, а для набора действий {ei,e2,…, е„} выполненено достаточное условие консистентности2 контрольной точки, то контрольную точку можно создать в данном месте выполнения параллельной программы (в ветви г контрольную точку можно создать между действиями е,- и ег). Рассмотрим некоторые способы ускорения работы данного переборного алгоритма. Утверждение 3. Если для набора действий Е\ — {(е^ , e8l), (e,-2, ej2),…, (е^, е^)} не выполнено необходимое условие консистентности, тогда для V-E/2 : Е\ С Е% необходимое условие также не выполнено, т. е. набор Е\ не может входить ни в одно возможное место создания контрольной точки. Доказательство очевидно, поэтому здесь не приводится. Для анализа завершенности действий введем дополнительные функции от действий: 2В момент времени непосредственно после завершения действий е\, ег, . . ,еп все операции по приему-передаче сообщений завершены. 50 ВЕСТН. МОСК. УН-ТА. СЕР. 15. ВЫЧИСЛ. МАТЕМ. И КИБЕРН. 2007. № 3 starts(e) возвращает пару (ranks-start, ranks-complete), где ranksstart — множество номеров процессов, которые начали действие (всегда один элемент — номер текущего процесса); ranks-complete — множеств номеров процессов, в которых должно произойти действие, связанное с данным, которое завершит данную операцию; completes(e) возвращает пару (ranks start, ranks-complete), где ranksstart — множество номеров процессов, которые должны выполнить действие, связанное с данным, чтобы данное действие могло завершиться; a ranks -complete — множество номеров процессов, которые завершают действие (всегда один элемент — номер текущего процесса). Вышеприведенные понятия рассматривают набор действий в нескольких ветвях параллельной программы как отражение одной MPI-операции в трассе программы. Такие действия можно найти по одинаковому передаваемому вместе с сообщением таймеру Т. Эти отношения определяются таким образом, что для множества действий Ех, соответствующего одной MPI-операции, идентифицируемой передаваемым значением таймера Т, выполняется следующее условие: М starts(