=Paper=
{{Paper
|id=Vol-1482/288
|storemode=property
|title=Оптимальное сохранение контрольных точек на локальные устройства хранения
(Optimal checkpointing to the local storage device)
|pdfUrl=https://ceur-ws.org/Vol-1482/288.pdf
|volume=Vol-1482
}}
==Оптимальное сохранение контрольных точек на локальные устройства хранения
(Optimal checkpointing to the local storage device)==
https://ceur-ws.org/Vol-1482/288.pdf
Суперкомпьютерные дни в России 2015 // Russian Supercomputing Days 2015 // RussianSCDays.org
Оптимальное сохранение контрольных точек на локальные
устройства хранения*
А.А. Бондаренко, М.В. Якобовский
ИПМ им. М.В. Келдыша РАН
Рассматривается техника обеспечения отказоустойчивости, основанная на сохране-
нии контрольных точек на локальные устройства хранения. В работе предлагается
разделение отказов на два вида: легкие и тяжелые отказы. Для данного разделения
отказов получено время оптимального периода сохранения контрольных точек. Для
рассмотренных примеров характерно, что в случае среднего времени между отказами
менее часа использование средств разделения на легкие и тяжелые отказы позволяет
сократить время вычислений более чем на 10%.
Введение
Для обеспечения отказоустойчивости в высокопроизводительных вычислительных систе-
мах наиболее используемыми являются методы восстановления из контрольных точек [1], в
частности, основанные на координированном протоколе, когда периодически состояние при-
ложения (вычислительной системы) записывается в надежное устройство хранения. Если воз-
никает отказ, то записанные данные используются для восстановления системы и/или прило-
жения к предыдущему “хорошему” состоянию. Однако для будущих экзафлопсных вычисли-
тельных систем применение подобной техники сталкивается с рядом трудностей [2], к ним от-
носят высокую частоту отказов и большие накладные расходы при сохранении контрольных
точек. В результате нескольких независимых исследований [3,4, 5] было предсказано, что по-
тенциальные экзафлопсные вычислительные системы будут тратить более 50% своего времени
на чтение или запись контрольных точек. Такие опасения побудили исследователей к разработ-
кам новых методов, в том числе повышающих масштабируемость техник сохранения кон-
трольных точек.
Один из подходов, уменьшающих накладные расходы работы с контрольными точками,
состоит в том, чтобы предоставить пользователю возможность самому реализовать в приложе-
нии различные техники отказоустойчивости, в том числе варьировать объем и содержание кон-
трольных точек. На данный момент стандарт MPI, позволяющий реализовывать методы обес-
печения отказоустойчивости на уровне пользователя, находится в разработке [6]. Программная
реализация этого стандарта уже разрабатывается в рамках проекта Open-MPI [7]. Однако сроки
появления пригодных к эксплуатации реализаций нового стандарта MPI в настоящее время не
определены.
В данной работе рассматривается применение метода сохранения контрольных точек на
локальные устройства хранения на уровне пользователя согласно [8]. Авторов работы интере-
сует эффективность рассматриваемого метода сохранения контрольных, если будут доступны
средства работы с легкими и тяжелыми отказами (определение ниже). Общая задача исследо-
вания заключается в определении границ применимости метода сохранения контрольных точек
при работе на экзафлопсных вычислительных системах. Эта сложная задача, включающая в
себя моделирование работы текущих и будущих вычислительных систем. Цель данной работы
заключается в определении оптимального периода сохранения контрольных точек на локаль-
ные устройства хранения.
В первой части статьи описываются рассматриваемые виды отказов в вычислительных сис-
темах. Во второй части приведена модель сохранения контрольных точек и определен опти-
мальный период сохранения контрольных точек в рамках рассматриваемых видов отказов.
*
Работа выполнена при поддержке Российского фонда фундаментальных исследований по гранту
13-01-12073 офи_м.
288
Суперкомпьютерные дни в России 2015 // Russian Supercomputing Days 2015 // RussianSCDays.org
1. Легкие и тяжелые отказы
Пусть MPI-процессы координированно сохраняют контрольные точки в локальную память,
которой может быть оперативная память, HDD или SSD диск. Тогда, при отказе хотя бы одного
вычислительного узла, MPI-процессы, запущенные на других узлах, не смогут получить доступ
к контрольным точкам, расположенным в локальной памяти отказавшего. Таким образом, вос-
становление процесса вычислений будет невозможно. Для выхода из такого положения следует
обеспечить избыточность хранения локальных контрольных точек в системе за счет их дубли-
рования в памяти различных вычислительных узлов. Такое дублирование может быть органи-
зованно, например, согласно схема сохранение описанной в [8]. В рамках данной схемы для
каждого MPI-процесса определяются номера MPI-процессов, в локальную память которых
должны быть сохранены копии исходных контрольных точек.
Значение сохранения контрольных точек в локальные устройства хранения отражает про-
гноз работ [9, 10]: «… более чем 83% отказов в системах петафлопсного уровня могут быть
восстановлены с использованием локальных контрольных точек, в то время как оставшиеся
17%, включающие сложные ошибки или потерю вычислительного узла, требуют использова-
ния доступной согласованной глобальной контрольной точки».
Проведем разделении отказов на легкие и тяжелые, в зависимости от расположения данных
необходимых для восстановления. Данное разделение возможно как для схемы сохранения
контрольных точек представленной в [8], так и для двухуровневой схемы сохранения кон-
трольных точек [11].
После легкого отказа для восстановления расчетов каждому MPI-процессу достаточно дан-
ных записанных на соответствующем ему локальном устройстве хранения. Отметим, что к
легким отказам, можно отнести, кратковременные сбои, сбои в коммуникационном обору-
довании, которые могут быть решены, например, его перезагрузкой.
После тяжелого отказа для восстановления расчетов некоторым MPI-процессам понадобят-
ся данные записанные на недоступных ему локальных устройствах хранения. В этом случае
эти MPI-процессы должны осуществить запрос необходимых данных у соответствующих
MPI-процессов, через стандартный протокол обмена данных. К тяжелым отказам относятся
сбои в локальных устройствах хранения, сбои в центральных процессорах и прочее.
Самая простая и применяемая в практике модель для описания вероятности отказов меха-
нического и электрического оборудования – экспоненциальное распределение [12]. Для обору-
дования должно быть известно – среднее время между отказами, тогда функция распределе-
ния примет вид
Отметим, что среднее время между легкими и тяжелыми отказами будут различаться. Так, на-
пример, средняя продолжительность безотказной работы сокета составляет около 50 лет [13], а
одного процессора около 125 лет [14].
2. Оптимизация периода сохранения контрольных точек
В работе [14] предложена модель описывающая сохранение контрольных точек по коорди-
нированному протоколу, причем контрольные точки сохраняются через одинаковые интервалы,
после того как фиксированная часть работы будет сделана. Отметим, что место сохранения
контрольных точек, распределенная файловая система или локальные устройства хранения,
является не существенным для модели и отражается лишь на значении параметров модели.
Приведем описание модели представленной в [14]. Весь расчет разбит на периоды продол-
жительностью , каждый из них включает в себя сохранение контрольной точки продолжи-
тельностью . Для учета асинхронного сохранения контрольных точек, введен параметр ,
. Примем, что на протяжении сохранения контрольной точки длительностью , про-
водятся вычисления в объеме . Таким образом, объем вычислений будет потерян
на организацию сохранения контрольной точки. Значение соответствует сохранению с
289
Суперкомпьютерные дни в России 2015 // Russian Supercomputing Days 2015 // RussianSCDays.org
блокировкой, а означает, что процесс сохранения выполняется одновременно с вычисле-
ниями.
При возникновении отказа необходимо произвести восстановление системы, а именно, оп-
ределение функционирующих элементов системы, перезагрузку некоторых элементов системы,
восстановление параллельной среды выполнения программы и прочее, обозначим – время
необходимое на эти действия. После этого каждый MPI-процесс должен прочитать и произве-
сти восстановление расчетов из соответствующей части глобальной контрольной точки, что
займет время .
В работе [14] представлен вывод общего времени выполнения приложения. Используя этот
результат, представим общее время выполнения приложения на вычислительной системе, в ко-
торой аппаратные и программные средства позволяют различать и обрабатывать как легкие, так
и тяжелые отказы. Пусть время выполнения параллельного приложения – время без учета
накладных расходов на реализацию методов отказоустойчивости и на обработку самих отказов,
а – общее время выполнения приложения с учетом времени на сохранение контрольных
точек и обработку отказов. Представим как сумму – времени выполнения приложе-
ния с учетом сохранения контрольных точек и – времени потерь на обработку отказов.
Для каждого периода вычисления занимают , а также во время сохранения кон-
трольной точки выполняется вычисления . То есть общий объем работы в период равен
. Таким образом, получаем зависимость от .
.
Пусть средние времена между двумя отказами составляют величины , где соответ-
ствует легкому отказу, соответствует тяжелому отказу. Тогда среднее число отказов каж-
дого вида во время вычислений равно . Для каждого отказа необходимо учитывать и .
Также надо учитывать время на выполнение работы , которая была уже сделана в процессе
предыдущей итерации сохранения контрольных точек, но не была сохранена в последнюю кон-
трольную точку.
Считаем, что с вероятностью отказ произойдет во время вычислений (не сохранения
контрольной точки) и потери времени при этом в среднем составят . А с вероятностью
отказ произойдет во время сохранения контрольной точки и потери времени при этом в сред-
нем составят . Мы пренебрегаем вероятностью того, что отказ произойдет во
время восстановления системы после другого отказа.
Для каждого отказа потери составят
.
Таким образом, получаем
.
Общее время выполнения приложения составит
(1)
Из этого уравнения получаем оптимальное значение для периода сохранения контрольных
точек
(2)
290
Суперкомпьютерные дни в России 2015 // Russian Supercomputing Days 2015 // RussianSCDays.org
3. Оценка времени выполнения программ в среде с внедренными
средствами обеспечения отказоустойчивости
Проведем сравнение времени выполнения программы в среде, учитывающей легкие и тя-
желые отказы, и среде с однородными отказами. В работе [14] для случая однородных отказов
приведены следующие формулы
(3)
(4)
Пусть есть две программы и время их выполнения без средств обеспечения отказоустойчи-
вости составляет 12 и 24 часа. Таким образом, . Согласно работе [14]
примем следующие значения параметров: мин, мин.
Время восстановления из контрольных точек после тяжелого отказа примем равным
мин. Аналогично время восстановления для однородных отказов: мин.
Время восстановления из контрольных точек после легкого отказа должно быть меньше,
чем после тяжелого отказа, мы будем рассматривать два значения мин и мин.
Пусть , а среднее время между отказами будет принимать значение от 0.5 часа до 3 ча-
сов.
Рис.1. Оценка время выполнения программы в среде поддерживающей обеспечение отказоустойчи-
вости. Параметры: мин, мин, мин, мин,
Согласно формулам (1-4) вычислим время выполнения программ. Результаты представле-
ны на рисунках 1 и 2. Из них следует, что использование средств обеспечения отказоустойчи-
вости, поддерживающих разделение отказов на легкие и тяжелые, позволит существенно со-
кратить время работы программ особенно для частых отказов. В данной работе рассмотрен уз-
291
Суперкомпьютерные дни в России 2015 // Russian Supercomputing Days 2015 // RussianSCDays.org
кий диапазон значений параметров характеризующих вычислительные системы и средства
обеспечения отказоустойчивости. Более подробная оценка значений параметров будущих вы-
числительных систем и анализ границ применимости данного подхода является задачей буду-
щих исследований.
Рис. 2. Оценка время выполнения программы в среде поддерживающей обеспечение отказоустойчи-
вости. Параметры: мин, мин, мин, мин,
Заключение
Для системы позволяющей работать с легкими и тяжелыми отказами и для приложений,
использующих схему сохранения контрольных точек на локальные устройства хранения, полу-
чены формулы полного времени выполнения приложения и времени уходящего на работу с от-
казами. Для некоторого диапазона значений параметров роботы вычислительных систем полу-
чено, что использование средств обеспечения отказоустойчивости, поддерживающих работу с
легкими и тяжелыми отказами, позволит существенно сократить время работы приложения.
Для рассмотренных примеров характерно, что в случае среднего времени между отказами ме-
нее часа использование средств разделения на легкие и тяжелые отказы позволяет сократить
время вычислений более чем на 10%.
Основным направлением дальнейших исследований является определение границ приме-
нимости техники сохранения контрольных точек на локальные устройства хранения экзаф-
лопсных вычислительных систем. Подобные оценки границ применимости метода, позволят
выявить необходимость или отсутствие таковой в развитии рассматриваемого метода и разра-
ботки аппаратных и программных средств позволяющих его реализовать.
Литература
1. Elnozahy E. N. M., Alvisi L., Wang Y.-M., Johnson D. B. A survey of rollback-recovery protocols
in message-passing systems. ACM Comput. Surv. 2002. Vol. 34, No 3, P. 375–408.
292
Суперкомпьютерные дни в России 2015 // Russian Supercomputing Days 2015 // RussianSCDays.org
2. Kogge P.M. ExaScale Computing Study: Technology Challenges in Achieving Exascale Systems
— Tech. Report TR-2008-13. — Univ. of Notre Dame, CSE Dept. — 2008. / P.M. Kogge, et al.
URL: http://www.cse.nd.edu/Reports/2008/TR-2008-13.pdf (accessed: 25.07.2014).
3. Elnozahy, E., Plank, J. Checkpointing for Petascale systems: a look into the future of practical
rollback-recovery. Dependable and Secure Computing, IEEE Transactions on 1, 2. Apr. 2004,
P. 97–108.
4. Oldfield R. A., Arunagiri S., Teller P. J., Seelam S., Varela M. R., Riesen R., Roth P.C. Modeling
the impact of checkpoints on next-generation systems. In 24th IEEE Conference on Mass Storage
Systems and Technologies. Sept. 2007, pp. 30–46.
5. Schroeder B., Gibson G. A. Understanding failures in petascale computers. Journal of Physics:
Conference Series. 2007. Vol. 78, No 1.
6. Fault Tolerance Research Hub [Электронный ресурс] Режим доступа: http://fault-
tolerance.org/ulfm/ulfm-specification (дата обращения: 1.06.2015).
7. Fault Tolerance Research Hub [Электронный ресурс] Режим доступа: http://fault-
tolerance.org/2014/11/15/tutorial-sc14-fault-tolerance-for-hpc-theory-and-practice/ (дата обра-
щения: 1.06.2015).
8. Бондаренко, А.А. Якобовский М.В. Обеспечение отказоустойчивости высокопроизводи-
тельных вычислений с помощью локальных контрольных точек // Вестник Южно-
Уральского государственного университета. Серия «Вычислительная математика и инфор-
матика». 2014. Том. 3, No. 3. С. 20–36.
9. Dong X., Muralimanohar N., Jouppi N., Xie Y., A Case Study of Incremental and Background
Hybrid In-Memory Checkpointing // Proceedings of the 2010 Exascale Evaluation and Research
Techniques Workshop (Pittsburgh, PA, USA March 13 – 14, 2010), ACM, 2010. P. 119–147.
10. Dong X., Muralimanohar N., Jouppi N., Kaufmann R., Xie Y., Leveraging 3D PCRAM technolo-
gies to reduce checkpoint overhead for future exscale systems // Proceedings of the Conference on
High Performance Computing Networking, Storage and Analysis (Portland, Oregon USA Novem-
ber 14-20, 2009). ACM, 2009. P. 57-68.
11. Vaidya, N.H. A Case for Two-Level Distributed Recovery Schemes // Proceedings of the ACM
SIGMETRICS Joint International Conference on Measurement and Modeling of Computer Sys-
tems (Ottawa, Canada, May 15-19 1995) ACM, 1995. P. 64–73.
12. Dongarra J. Herault T. Robert Y. Fault tolerance techniques for high-performance computing.
http://www.netlib.org/lapack/lawnspdf/lawn289.pdf (дата обращения: 1.06.2015).
13. Ferreira K., Stearley J., Laros J. H. I., Oldfield R., Pedretti K., Brightwell R., Riesen R., Bridges
P. G., Arnold D.. Evaluating the Viability of Process Replication Reliability for Exascale Systems.
In Proc. of the ACM/IEEE SC Conf., 2011
14. Aupy G., Benoit A.,Herault T., Robert Y., Dongarra J. Optimal Checkpointing Period: Time vs.
Energy // High Performance Computing Systems. Performance Modeling, Benchmarking and
Simulation: 4th International Workshop, PMBS 2013, November 18, 2013, Denver, CO, USA,
Proceedings. Springer. 2014.
293
Суперкомпьютерные дни в России 2015 // Russian Supercomputing Days 2015 // RussianSCDays.org
Optimal checkpointing to the local storage device
Aleksey Bondarenko and Mikhail Iakobovski
Keywords: Parallel computation, checkpoints, fault tolerance
We consider the fault tolerance technique based on saving checkpoint files on the local node.
We are proposing a division of failures into two kinds: light and heavy failures. For this
separation we obtain the optimal checkpoint interval. Examples show that if MTBF is less
than an hour then tools working with light and heavy failures reduce the computation time by
more than 10%.