Abstract

Рассматривается техника обеспечения отказоустойчивости, основанная на сохранении контрольных точек на локальные устройства хранения. В работе предлагается разделение отказов на два вида: легкие и тяжелые отказы. Для данного разделения отказов получено время оптимального периода сохранения контрольных точек. Для рассмотренных примеров характерно, что в случае среднего времени между отказами менее часа использование средств разделения на легкие и тяжелые отказы позволяет сократить время вычислений более чем на 10%.

-

Оптимальное сохранение контрольных точек на локальные устройства хранения* 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 ]. Весь расчет разбит на периоды продолжительностью , каждый из них включает в себя сохранение контрольной точки продолжительностью . Для учета асинхронного сохранения контрольных точек, введен параметр , . Примем, что на протяжении сохранения контрольной точки длительностью , проводятся вычисления в объеме . Таким образом, объем вычислений будет потерян на организацию сохранения контрольной точки. Значение соответствует сохранению с блокировкой, а означает, что процесс сохранения выполняется одновременно с вычислениями.

При возникновении отказа необходимо произвести восстановление системы, а именно, определение функционирующих элементов системы, перезагрузку некоторых элементов системы, восстановление параллельной среды выполнения программы и прочее, обозначим – время необходимое на эти действия. После этого каждый MPI-процесс должен прочитать и произвести восстановление расчетов из соответствующей части глобальной контрольной точки, что займет время .

В работе [ 14 ] представлен вывод общего времени выполнения приложения. Используя этот результат, представим общее время выполнения приложения на вычислительной системе, в которой аппаратные и программные средства позволяют различать и обрабатывать как легкие, так и тяжелые отказы. Пусть время выполнения параллельного приложения – время без учета накладных расходов на реализацию методов отказоустойчивости и на обработку самих отказов, а – общее время выполнения приложения с учетом времени на сохранение контрольных точек и обработку отказов. Представим как сумму – времени выполнения приложения с учетом сохранения контрольных точек и – времени потерь на обработку отказов.

Для каждого периода вычисления занимают , а также во время сохранения контрольной точки выполняется вычисления . То есть общий объем работы в период равен . Таким образом, получаем зависимость от .

.

Пусть средние времена между двумя отказами составляют величины , где соответствует легкому отказу, соответствует тяжелому отказу. Тогда среднее число отказов каждого вида во время вычислений равно . Для каждого отказа необходимо учитывать и . Также надо учитывать время на выполнение работы , которая была уже сделана в процессе предыдущей итерации сохранения контрольных точек, но не была сохранена в последнюю контрольную точку.

Считаем, что с вероятностью

отказ произойдет во время вычислений (не сохранения контрольной точки) и потери времени при этом в среднем составят . А с вероятностью отказ произойдет во время сохранения контрольной точки и потери времени при этом в среднем составят

. Мы пренебрегаем вероятностью того, что отказ произойдет во время восстановления системы после другого отказа.

Для каждого отказа потери составят Таким образом, получаем Общее время выполнения приложения составит

Из этого уравнения получаем оптимальное значение для периода сохранения контрольных точек (1) (2) 3. Оценка времени выполнения программ в среде с внедренными средствами обеспечения отказоустойчивости

Проведем сравнение времени выполнения программы в среде, учитывающей легкие и тяжелые отказы, и среде с однородными отказами. В работе [ 14 ] для случая однородных отказов приведены следующие формулы (3) (4) Пусть есть две программы и время их выполнения без средств обеспечения отказоустойчивости составляет 12 и 24 часа. Таким образом, . Согласно работе [ 14 ] примем следующие значения параметров: мин, мин. Время восстановления из контрольных точек после тяжелого отказа примем равным мин. Аналогично время восстановления для однородных отказов: мин. Время восстановления из контрольных точек после легкого отказа должно быть меньше, чем после тяжелого отказа, мы будем рассматривать два значения мин и мин. Пусть , а среднее время между отказами будет принимать значение от 0.5 часа до 3 часов.

Рис.1. Оценка время выполнения программы в среде поддерживающей обеспечение отказоустойчивости. Параметры: мин, мин, мин, мин, Согласно формулам (1-4) вычислим время выполнения программ. Результаты представлены на рисунках 1 и 2. Из них следует, что использование средств обеспечения отказоустойчивости, поддерживающих разделение отказов на легкие и тяжелые, позволит существенно сократить время работы программ особенно для частых отказов. В данной работе рассмотрен узкий диапазон значений параметров характеризующих вычислительные системы и средства обеспечения отказоустойчивости. Более подробная оценка значений параметров будущих вычислительных систем и анализ границ применимости данного подхода является задачей будущих исследований.

Рис. 2. Оценка время выполнения программы в среде поддерживающей обеспечение отказоустойчивости. Параметры: мин, мин, мин, мин, Заключение

Для системы позволяющей работать с легкими и тяжелыми отказами и для приложений, использующих схему сохранения контрольных точек на локальные устройства хранения, получены формулы полного времени выполнения приложения и времени уходящего на работу с отказами. Для некоторого диапазона значений параметров роботы вычислительных систем получено, что использование средств обеспечения отказоустойчивости, поддерживающих работу с легкими и тяжелыми отказами, позволит существенно сократить время работы приложения. Для рассмотренных примеров характерно, что в случае среднего времени между отказами менее часа использование средств разделения на легкие и тяжелые отказы позволяет сократить время вычислений более чем на 10%.

Основным направлением дальнейших исследований является определение границ применимости техники сохранения контрольных точек на локальные устройства хранения экзафлопсных вычислительных систем. Подобные оценки границ применимости метода, позволят выявить необходимость или отсутствие таковой в развитии рассматриваемого метода и разработки аппаратных и программных средств позволяющих его реализовать. Литература Optimal checkpointing to the local storage device Aleksey Bondarenko and Mikhail Iakobovski 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%.

References

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 .

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://faulttolerance.org/ulfm/ulfm-specification (дата обращения: 1 . 06 . 2015 ).

7. Fault Tolerance Research Hub [Электронный ресурс] Режим доступа: http://faulttolerance.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 technologies to reduce checkpoint overhead for future exscale systems // Proceedings of the Conference on High Performance Computing Networking, Storage and Analysis (Portland, Oregon USA November 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 Systems (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 .