Средства разработки приложений


Механизм контрольных точек


В среде 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