Binary delta optimization of parallel program checkpoints.pdf Распределенные вычислительные системы (ВС) являются основным инстру-ментом высокопроизводительной обработки информации [1]. Современные ВС[2] являются большемасштабными, они формируются из десятков и сотен тысячвычислительных ядер и обладают производительностью от TeraFLOPS доPetaFLOPS.Согласно статистическим данным [3 - 5], среднее время безотказной работы(ƒ−1) вычислительных узлов (ВУ) распределенных ВС лежит в промежутке 104 -106 ч (ƒ - интенсивность потока отказов одного ВУ). Но даже при использованиитаких высоконадежных компонентов время между частичными отказами (отказа-ми отдельных ВУ) в большемасштабных ВС в среднем составляет несколькодней. Это ставит под вопрос осуществимость решения трудоемких задач, пред-ставленных параллельными программами с количеством ветвей, близким к числуузлов ВС.Для обеспечения отказоустойчивости распределенных ВС используют аппара-турную или (и) программную избыточность. Аппаратурная избыточность предпо-лагает одновременное использование альтернативных элементов в структуре рас-пределенной ВС для решения одной задачи (см. например, технологии RAID,Channel Bonding и т. п.). Программная избыточность предполагает формированиеслужебной информации, которая может быть применена для устранения послед-ствий частичных отказов ресурсов ВС. Наиболее распространенной реализациейданного подхода является периодическое сохранение промежуточных состоянийпараллельных программ (ПП) в контрольных точках (КТ) восстановления. ТакиеКТ используются для перезапуска ПП в случае отказов ресурсов ВС.Для формирования распределенной КТ параллельной программы каждый про-цесс, входящий в ее состав, сохраняет свое состояние в локальной КТ. Целостнойраспределенной КТ [6] называется набор локальных КТ, позволяющих сформиро-вать допустимое состояние ПП. Существует два основных подхода к созданиюраспределенных КТ: синхронный (координированный) и асинхронный. При син-хронном подходе все процессы ПП сохраняют свое состояние одновременно, чтогарантирует целостность КТ, но приводит к повышенной нагрузке на системуввода-вывода распределенной ВС. При асинхронном подходе каждый процесссоздает КТ независимо от других. Поэтому при восстановлении необходимо вы-полнять поиск целостного состояния программы на основе набора локальных КТ,созданных в различные моменты времени. При этом возможно возникновение«эффекта домино», когда происходит запуск ПП из начального состояния.Анализ существующих средств отказоустойчивого выполнения параллельныхпрограмм показывает, что для создания распределенных КТ, как правило, исполь-зуется синхронный подход [7 - 9]. В связи с вышесказанным актуальной являетсязадача снижения накладных расходов, вносимых средствами отказоустойчивостиВС, за счет уменьшения объема локальных КТ. Для решения данной проблемыможет быть использована технология дельта-сжатия [10 - 12], обеспечивающаяисключение фрагментов состояния параллельной программы, сохраненных впредшествующих КТ. Применение дельта-сжатия для уменьшения объема и вре-мени создания КТ будем называть дельта-оптимизацией.В работе проведен анализ существующих алгоритмов дельта-сжатия, а такжепредложен новый адаптивный подход к дельта-оптимизации, сочетающий пре-имущества известных видов дельта-сжатия.1. Применение дельта-сжатия для оптимизацииконтрольных точек восстановления параллельных программМетоды и алгоритмы, реализуемые в параллельных программах, характеризу-ются различным использованием доступной памяти. Например, многие итераци-онные методы лишь частично модифицируют обрабатываемые данные в процессеработы. Поэтому КТ часто содержат дублирующуюся информацию, исключениекоторой может значительно снизить объемы передаваемых и хранимых данных.Различают два вида дельта-сжатия: инкрементное и дифференциальное. Пер-вое предусматривает сохранение фрагментов текущей КТ, измененных относи-тельно предыдущей КТ (рис. 1, а), второе - сохранение фрагментов текущей КТ,модифицированных относительно некоторой базовой КТ (рис. 1, б).a бРис. 1. Контрольные точки: а - инкрементные; б - дифференциальные; - фрагменты,которые сохраняются в подсистеме ввода-вывода; - фрагменты 5, которые не сохраня-ются в подсистеме ввода-выводаПреимуществом дифференциального дельта-сжатия является то, что для фор-мирования результирующей КТ требуется только базовая КТ и одна дифференци-альная КТ (ДКТ). Это делает возможным сокращение объемов хранимых данныхза счет удаления устаревших дифференциальных КТ.Инкрементные КТ (ИКТ), по сравнению с дифференциальными, формируютсяотносительно более актуального состояния и в большинстве случаев будут иметьменьший объем. С другой стороны, данный подход характеризуется большим (посравнению с ДКТ) временем формирования результирующей КТ и необходимо-стью хранить все созданные ИКТ.Существуют два основных подхода к реализации дельта-сжатия КТ: странич-ный [12] и основанный на хешировании [10, 11]. Первый имеет ряд ограничений,связанных с размером страницы памяти и аппаратурными возможностями про-цессора. Второй подход является более универсальным, он использует хеш-функции с малой вероятностью коллизии для обнаружения измененных фрагмен-тов КТ. В данной работе рассмотрены алгоритмы, относящиеся к подходам, осно-ванным на хешировании.Пусть Kl - КТ, созданная в момент времени l = {1, 2, ..., L}, а Kli, i = 1, …, S(Kl)- i-й байт Kl, где S(X) - размер структуры данных Х в байтах. Разобьем Kl на Rблоков, размер каждого из которых определяется применяемым подходом:Bl = {Blj | Blj = (Klz, Kl(z+1), …, Kl(z+m)), 11ji i z d−= = ƒ , m = dj}, (1)где d = {d1, d2, …, dR} - размеры соответствующих блоков. Для каждого блока jвычисляется хеш-код glj, совокупность gl хеш-кодов всех блоков КТ Kl будем на-зывать ее сигнатурой:gl = {glj | glj = h(Blj)}. (2)В выражении (2) h - хеш-функция, ставящая в соответствие набору байт про-извольной длины набор фиксированной длины, равной ƒ байт. При этом ƒ

Скачать электронную версию публикации