International Conference «Mathematical and Informational Technologies, MIT-2011»
(IX Conference «Computational and Informational Technologies for Science,
Engineering and Education»)

Vrnjacka Banja, Serbia, August, 27–31, 2011

Budva, Montenegro, August, 31 – September, 5, 2011

Polyakov A.   Молдованова О.В.   Карасев Б.И.  

Подходы к оптимизации контрольных точек восстановления параллельных программ

Reporter: Polyakov A.

     Распределенные вычислительные системы (ВС) являются важнейшим инструментом решения сложных научных, инженерных и экономических задач. Такие системы являются большемасштабными, количество процессорных ядер в их составе варьируется от десятков до сотен тысяч, а число узлов ввода-вывода (УВВ) – от нескольких десятков до сотен. Физически несколько процессорных ядер обычно располагаются на вычислительном узле (ВУ). При построении большемасштабных ВС используются высоконадежные компоненты, однако время между частичными отказами в них составляет в среднем несколько дней. Это ставит под сомнение осуществимость решения трудоемких задач, представленных параллельными программами (ПП) с количеством ветвей, близким к числу ядер в ВС.
     Основным подходом к обеспечению отказоустойчивости распределенных ВС является применение программ, обладающих свойством возобновляемости. Такие программы способны сохранять свое промежуточное состояние в контрольных точках (КТ). В случае отказа ресурсов ВС любая доступная КТ позволяет перезапустить (возобновить) исходную программу, начальное состояние которой будет соответствовать моменту создания этой КТ.
     Недостатком такого подхода является появление высоких накладных расходов, связанных с записью и хранением формируемых КТ. В работе рассматриваются алгоритмы, позволяющие снизить указанные накладные расходы за счет сжатия КТ на вычислительных узлах, на которых они создаются. Для сжатия КТ используется технология дельта-сжатия, а также алгоритмы, применяемые в программах-архиваторах.
     Разработан адаптивный алгоритм субоптимального выбора КТ, относительно которой будет выполняться дельта-сжатие. Целью оптимизации является: 1) минимизация объёма сжатой КТ; 2) уменьшение количества сжатых КТ, необходимых для формирования результирующей КТ.
     Создан алгоритм пакетного сжатия, совмещающий универсальное и дельта-сжатие, который обеспечивает субоптимальное время формирования результирующей КТ.
     Предложен параллельный алгоритм формирования результирующей КТ из набора дельта-сжатых, который выполняет поиск наиболее позднего целостного состояния параллельной программы.

Abstracts file: mit2011_short_v1.docx
Full text file: Polyakov_ExtThesis.pdf


To reports list

© 1996-2019, Institute of computational technologies of SB RAS, Novosibirsk