Механизм контрольных точек
В среде ParJava реализован инструмент “CheckPoints”, реализующий механизм контрольных точек, который позволяет существенно сократить объемы сохраняемых данных и время на их сохранение.
Реализация механизма контрольных точек для параллельной программы является нетривиальной задачей. Параллелизм усложняет процесс установки точек останова, т. к. сообщения порождают связи между отдельными процессами, и приходится обеспечивать так называемые консистентные состояния. Состояние двух процессов называется неконсистентным, если при передаче сообщения одного процесса другому, может возникнуть состояние, когда первый процесс еще не послал сообщение, а во втором уже сработала функция получения сообщения. Если в таком состоянии поставить точку останова, то восстановив впоследствии контекст задачи, мы не получим ее корректной работы.
Пользователь указывает в программе место сохранения данных с помощью директивы EXCLUDE_HERE. В контрольной точке 1 (рис. 4) не сохраняются данные, которые будут обновлены до своего использования («мертвые» переменные). В контрольной точке 2 не сохраняются данные, которые используются только для чтения до этой контрольной точки. Результатом будет значительное уменьшение размеров сохраняемых данных в контрольной точке и уменьшение накладных расходов на их сохранение.
Рис. 4. Контрольные точки
Вначале граф потока управления G=(N, E) разбивается на подграфы G?. Корнем каждого подграфа G? является директива EXCLUDE_HERE. Подграф включает все пути, достижимые из этой директивы, не проходящие через другую директиву EXCLUDE_HERE.
Для каждого подграфа вычисляются 2 множества переменных: DE(G?) - множество переменных, которые «мертвы» на каждой директиве EXCLUDE_HERE в G? и RO(G?) - множество переменных, предназначенных только-для-чтения по всему подграфу G?.
Для нахождения множеств DE(G?) и RO(G?) используется консервативный анализ потока данных. В каждом состоянии S в программе вычисляются два множества характеризующие доступ к памяти: use[S] – множество переменных, которые могут быть использованы вдоль некоторого пути в графе, и def[S] – множество переменных, которым присваиваются значения до их использования вдоль некоторого пути в графе, начинающегося в S, или множество определений переменных.
Ячейка памяти l является «живой» в состоянии S, если существует путь из S в другое состояние S? такой, что l
use[S?] и для каждого S?? на этом пути l
def[S??].
Ячейка l является элементом DE(G?), если l «мертвая» во всех операторах сохранения контрольных точек в G?. Ячейка памяти l является ячейкой только-для-чтения в операторе S, если l
use[S]. Поэтому l RO(G?) тогда и только тогда, когда lgen[S] для всех S в G?. Эти определения консервативны, поскольку они ищут все возможные пути через граф потока управления, тогда как некоторые из них могут никогда не достигнуть выполнения в программе. Анализ «живых» переменных обычно выражается в виде уравнений потока данных, по одному на каждое состояние в программе. Мы дадим уравнение потока данных, которое позволит нам определить DE(G?) и RO(G?) для каждого подграфа G? в программе. Каждое из этих уравнений может быть решено обычным итеративным методом. Для достижения нашей цели уравнение потока данных характеризуем его функцией обновления. Такая функция ассоциируется с каждым состоянием S. Определим in[S] как множество мертвых переменных в точке непосредственно перед блоком S, а out[S] – такое же множество в точке, непосредственно следующей за блоком S. Вычисляем множество мертвых переменных в направлении обратном графу потока управления. Система уравнений выглядит следующим образом: out[S] = ?S? in[S?] in[S] = FS, где out[S] = ?S? DEAD[S?] – это пересечение множества мертвых переменных для всех состояний S?, которые являются преемниками S в G, а FS – это функция обновления, которая в нашем случае равна FS = out[S] 
gen[S] – use[S] и свидетельствует о переменных, которые мертвы непосредственно перед S и тех переменных, которые стали мертвыми после S, плюс о тех, в которые производилась запись в состоянии S, минус любые ячейки, с которых происходило чтение в S. При следующем запуске эти массивы и параметры загружаются, и по ним полностью восстанавливается контекст прерванной задачи.
