Теоретические основы применения модулярной арифметики для обнаружения и коррекции ошибок

Материал из Модулярная арифметики
(Различия между версиями)
Перейти к: навигация, поиск
Строка 1: Строка 1:
 
Одним из основных параметров при проектировании сложных вычислительных устройств была и остается надежность их функционирования [1],[2],[3],[4],[5]. Ведь, с одной стороны, постоянный рост требований к скоростным характеристикам вычислительных устройств приводит к необходимости организации параллельных вычислений, а с другой стороны, при этом увеличивается частота возникновения отказов, и возрастает время простоя процессоров, вызванное трудностью отыскания и ликвидации неисправности. Очевидно, что независимо от того, какие характеристики проявляет вычислительное устройство, единственная ошибка в любом из его блоков может отключить или повредить всю систему и в некоторых случаях привести к катастрофическим неисправностям. Проблема высокой надежности не только передачи информации, но и ее обработки особенно актуальна в современных системах, работающих в реальном времени, где ошибки работы оборудования должны быть обнаружены и исправлены немедленно. Стоит отметить и то, что переход на новейшие субмикронные технологии только усугубляет данную проблему, так как сложность изготовления ИС многократно возрастает, а вместе с ней возрастает и вероятность возникновения отказов. Такие отказы могут быть обнаружены заблаговременно и влиять на процент выхода годных, так и на этапе их непосредственной эксплуатации, что крайне нежелательно для целого ряда систем, таких, например, как медицинская техника, навигационное оборудвание и другая аппаратура, неисправности в работе которой могут обходиться очень дорого. Таким образом, высокая надежность в этом случае должна достигаться не столько совершенствованием самих технических средств передачи информации, сколько за счет применения таких способов ее кодирования, которые были бы устойчивы по отношению к возможным случайным искажениям и позволяли бы при необходимости осуществлять коррекцию данных. В связи с этим наиболее перспективным путем решения рассматриваемой проблемы является придание вычислительным устройствам свойства устойчивости к отказам и сбоям в процессе функционирования. Принято считать вычислительную систему отказоустойчивой (faut-tolerant system), если при возникновении отказа она сохраняет свои фукциональные возможности в полном (fail-save) или уменьшенном (fail-soft) объеме. При этом отказоустойчивость обеспечивается сочетанием избыточности системы и наличием механизма обнаружения ошибок, а также процедур для автоматического восстановления ее правильного функционирования. Fail-save устойчивость к отказам характеризует способность вычислительной системы обеспечивать корректную работу, несмотря на возникновение отказа, но с понижением качества, то есть находясь в состояни постепенного снижения эффективности. Именно в таком контексте будет рассматриваться далее понятие отказоустойчивости.
 
Одним из основных параметров при проектировании сложных вычислительных устройств была и остается надежность их функционирования [1],[2],[3],[4],[5]. Ведь, с одной стороны, постоянный рост требований к скоростным характеристикам вычислительных устройств приводит к необходимости организации параллельных вычислений, а с другой стороны, при этом увеличивается частота возникновения отказов, и возрастает время простоя процессоров, вызванное трудностью отыскания и ликвидации неисправности. Очевидно, что независимо от того, какие характеристики проявляет вычислительное устройство, единственная ошибка в любом из его блоков может отключить или повредить всю систему и в некоторых случаях привести к катастрофическим неисправностям. Проблема высокой надежности не только передачи информации, но и ее обработки особенно актуальна в современных системах, работающих в реальном времени, где ошибки работы оборудования должны быть обнаружены и исправлены немедленно. Стоит отметить и то, что переход на новейшие субмикронные технологии только усугубляет данную проблему, так как сложность изготовления ИС многократно возрастает, а вместе с ней возрастает и вероятность возникновения отказов. Такие отказы могут быть обнаружены заблаговременно и влиять на процент выхода годных, так и на этапе их непосредственной эксплуатации, что крайне нежелательно для целого ряда систем, таких, например, как медицинская техника, навигационное оборудвание и другая аппаратура, неисправности в работе которой могут обходиться очень дорого. Таким образом, высокая надежность в этом случае должна достигаться не столько совершенствованием самих технических средств передачи информации, сколько за счет применения таких способов ее кодирования, которые были бы устойчивы по отношению к возможным случайным искажениям и позволяли бы при необходимости осуществлять коррекцию данных. В связи с этим наиболее перспективным путем решения рассматриваемой проблемы является придание вычислительным устройствам свойства устойчивости к отказам и сбоям в процессе функционирования. Принято считать вычислительную систему отказоустойчивой (faut-tolerant system), если при возникновении отказа она сохраняет свои фукциональные возможности в полном (fail-save) или уменьшенном (fail-soft) объеме. При этом отказоустойчивость обеспечивается сочетанием избыточности системы и наличием механизма обнаружения ошибок, а также процедур для автоматического восстановления ее правильного функционирования. Fail-save устойчивость к отказам характеризует способность вычислительной системы обеспечивать корректную работу, несмотря на возникновение отказа, но с понижением качества, то есть находясь в состояни постепенного снижения эффективности. Именно в таком контексте будет рассматриваться далее понятие отказоустойчивости.
 +
При общем взгляде на проблему повышения надежности устройств можно выделить три наиболее распространенных способа обеспечения отказоустойчивости (рис.) Кроме того, в зависимости от причины возникновения ошибок методы борьбы с ошибками в цифровых устройствах  при обработк информации разделяют на методы, ориентированные на борьбу с отказами и/или сбоями элементов. Эти методы требуют различного уровня вводимой избыточности, причем борьба со сбоями по сравнению с отказами элементов требует более сложных схем коррекции ошибок.
 +
 +
Рис.1. Основные способы обеспечения отказоустойчивости цифровых схем.
 +
 +
Самым простым и распространенным методом борьбы как с отказами, так и сбоями элементов является аппаратное резервирование цифровых устройств и систем [1],[2],[3],[4],[6]. Существует много различных методов резервирования. Рассмотрим, например, два наиболее известных метода: нагруженное ("горячее") и ненагруженое ("холодное") резервирование. В последнем случае используется резервный комплект оборудования, который подключается, когда рабочий комплект начинает выдавать ошибочную информацию. Рабочий комплект в этот момент, естественно, отключается. При "горячем" резервировании одновременно функционируют все комплекты оборудования, выходы которых объединяются через мажоритарный элемент. Как видно, для любого из методов резервирования характерна очень высокая избыточность. Так, например, в большинстве случаев обнаружение правильности результатов достигается двойным просчетом, а выбор правильного результата по совпадающим данным тройным просчетом. Такая высокая избыточность объясняется тем, что при резервировании практически полностью игнорируется специфика самого устройства и корректируются ошибки с любой вероятностью возникновения. Однако во многих вычислительных устойствах для обеспечения надежной работы достаточно исправить лишь часть наиболее вероятных ошибок.
 +
Другим способом обеспечения отказоустойчивости является применение специальных позиционных кодов, широко используемых в каналах связи [7],[8],[9],[4]. Такие коды призваны обнаруживать и исправлять случайные ошибки, возникающие в процессе хранения или передачи информации.
  
  

Версия 17:32, 25 сентября 2013

Одним из основных параметров при проектировании сложных вычислительных устройств была и остается надежность их функционирования [1],[2],[3],[4],[5]. Ведь, с одной стороны, постоянный рост требований к скоростным характеристикам вычислительных устройств приводит к необходимости организации параллельных вычислений, а с другой стороны, при этом увеличивается частота возникновения отказов, и возрастает время простоя процессоров, вызванное трудностью отыскания и ликвидации неисправности. Очевидно, что независимо от того, какие характеристики проявляет вычислительное устройство, единственная ошибка в любом из его блоков может отключить или повредить всю систему и в некоторых случаях привести к катастрофическим неисправностям. Проблема высокой надежности не только передачи информации, но и ее обработки особенно актуальна в современных системах, работающих в реальном времени, где ошибки работы оборудования должны быть обнаружены и исправлены немедленно. Стоит отметить и то, что переход на новейшие субмикронные технологии только усугубляет данную проблему, так как сложность изготовления ИС многократно возрастает, а вместе с ней возрастает и вероятность возникновения отказов. Такие отказы могут быть обнаружены заблаговременно и влиять на процент выхода годных, так и на этапе их непосредственной эксплуатации, что крайне нежелательно для целого ряда систем, таких, например, как медицинская техника, навигационное оборудвание и другая аппаратура, неисправности в работе которой могут обходиться очень дорого. Таким образом, высокая надежность в этом случае должна достигаться не столько совершенствованием самих технических средств передачи информации, сколько за счет применения таких способов ее кодирования, которые были бы устойчивы по отношению к возможным случайным искажениям и позволяли бы при необходимости осуществлять коррекцию данных. В связи с этим наиболее перспективным путем решения рассматриваемой проблемы является придание вычислительным устройствам свойства устойчивости к отказам и сбоям в процессе функционирования. Принято считать вычислительную систему отказоустойчивой (faut-tolerant system), если при возникновении отказа она сохраняет свои фукциональные возможности в полном (fail-save) или уменьшенном (fail-soft) объеме. При этом отказоустойчивость обеспечивается сочетанием избыточности системы и наличием механизма обнаружения ошибок, а также процедур для автоматического восстановления ее правильного функционирования. Fail-save устойчивость к отказам характеризует способность вычислительной системы обеспечивать корректную работу, несмотря на возникновение отказа, но с понижением качества, то есть находясь в состояни постепенного снижения эффективности. Именно в таком контексте будет рассматриваться далее понятие отказоустойчивости. При общем взгляде на проблему повышения надежности устройств можно выделить три наиболее распространенных способа обеспечения отказоустойчивости (рис.) Кроме того, в зависимости от причины возникновения ошибок методы борьбы с ошибками в цифровых устройствах при обработк информации разделяют на методы, ориентированные на борьбу с отказами и/или сбоями элементов. Эти методы требуют различного уровня вводимой избыточности, причем борьба со сбоями по сравнению с отказами элементов требует более сложных схем коррекции ошибок.

Рис.1. Основные способы обеспечения отказоустойчивости цифровых схем.

Самым простым и распространенным методом борьбы как с отказами, так и сбоями элементов является аппаратное резервирование цифровых устройств и систем [1],[2],[3],[4],[6]. Существует много различных методов резервирования. Рассмотрим, например, два наиболее известных метода: нагруженное ("горячее") и ненагруженое ("холодное") резервирование. В последнем случае используется резервный комплект оборудования, который подключается, когда рабочий комплект начинает выдавать ошибочную информацию. Рабочий комплект в этот момент, естественно, отключается. При "горячем" резервировании одновременно функционируют все комплекты оборудования, выходы которых объединяются через мажоритарный элемент. Как видно, для любого из методов резервирования характерна очень высокая избыточность. Так, например, в большинстве случаев обнаружение правильности результатов достигается двойным просчетом, а выбор правильного результата по совпадающим данным тройным просчетом. Такая высокая избыточность объясняется тем, что при резервировании практически полностью игнорируется специфика самого устройства и корректируются ошибки с любой вероятностью возникновения. Однако во многих вычислительных устойствах для обеспечения надежной работы достаточно исправить лишь часть наиболее вероятных ошибок. Другим способом обеспечения отказоустойчивости является применение специальных позиционных кодов, широко используемых в каналах связи [7],[8],[9],[4]. Такие коды призваны обнаруживать и исправлять случайные ошибки, возникающие в процессе хранения или передачи информации.


Литература


1. Акушский И. Я., Юдицкий Д. И. Машинная арифметика в остаточных классах. - М.: Советское радио, 1968. - 440с.

2. Коёкин А. И. Структурные методы обеспечения надежности информационных систем// Диссертация на соискание ученой степени доктора технических наук. - Москва, 1974. - 303с.

3. Конопелько В. К., Борискевич А. А. Контроль ошибок в цифровых устройствах// Учеб. пособие по курсам "Теория кодирования" и "Цифровые и микропроцессорные устройства". - Мн.: БГУИР, 2003. - 18с.

4. Торгашев В. А. Система остаточных классов и надежность ЦВМ. - М.: Советское радио, 1973. - 120с.

5. Watson R. W., Hastings C. W. Self-Checked Computation Using Residue Arithmetic// Proceedings of the IEEE, vol. 54, no. 12, December 1966. - P.1920-1931.

6. Угрюмов Е. П. Цифровая схемотехникаю - СПб.: БХВ-Петербург, 2002. - 528с.

7. Блейхут Р. Теория и практика кодов, контролирующих ошибки: Пер. с англ. М.: Мир, 1986.-576с.

8. Кларк Дж., мл., Кейн Дж. Кодирование с исправлением ошибок в системах цифровой связи: Пер. с англ. М.: Радио и связь, 1987. - 391с.

9. Питерсон У., Уэлдон Э. Коды, исправляющие ошибки: Пер. с англ. М.: Мир, 1976. -590с.

10. Barsi F., Maestrini P. Error Correcting Properties of Redundant Residue Number Systems// IEEE Transactions on Computers, vol. C-21, no. 3, March 1973. P. 307-315.

11. Barsi F., Maestrini P. Error Detection and Correction by Product Codes in Residue Number Systems// IEEE Transactions on Computers, vol. C-23, no. 9, September 1974. -P. 915-924.

12. Jenkins W.K., Altman E.J. Self-Checking Properties of Residue Number Error Checkers Based on Mixed Radix Conversion// IEEE Transactions on Circuits and Systems, vol. 35, no. 2, February 1988. P. 159-167.

13. Krishna H., Lin K.-Y., Sun J.-D. A Coding Theory Approach to Error Control in Redundant Residue Number Systems - Part I: Theory and Single Error Correction// IEEE Transactions on Circuits and Systems-II: Analog and Digital Signal Processing, vol. 39, no. 1, January 1992.-P. 8-17.

14. Krishna H., Sun J.-D. On Theory and Fast Algorithms for Error Correction in Residue Number System Product Codes// IEEE Transactions on Computers, vol. 42, no. 7, July 1993.-P. 840-853.

15. Orton G.A., Peppard L.E., Tavares S. E. New Fault Tolerant Techniques for Residue Number Systems// IEEE Transactions on Computers, vol. 41, no. 11, November 1992. -P.1453-1464.

16. Sun J.-D., Krishna H. A Coding Theory Approach to Error Control in Redundant Residue Number Systems - Part I: Multiple Error Detection and Correction// IEEE Transactions on Circuits and Systems-II: Analog and Digital Signal Processing, vol. 39, no. 1, January 1992.-P. 18-34.

17. Yang L.-L., Hanzo L. Coding Theory and Performance Of Redundant Residue Number System Codes// submitted to IEEE Transactions on Information Theory, 1999. 40 p.

18. Yang L.-L., Hanzo L. Redundant Residue Number System Based Error Correction Codes// IEEE Vehicular Technology Conference, 2001. IEEE VTC 54th, vol. 3, 7-11 October 2001.-P. 1472-1476.

19. Cosentino R.J. Fault Tolerance in a Systolic Residue Arithmetic Processor Array// IEEE Transactions on Computers, vol. 37, no. 7, July 1988. P. 886-890.

20. Radhakrishnan D., Preethy A.P. A novel 36-bit single fault tolerant multiplier using 5-bit moduli// IEEE TENCON 98, vol. 1, pp. 128-130, New Delhi, India, Dec. 1998.

21. Исследование методов пректирования и разработка прграмных средств синтеза быстродействующих арифметических устройств// Отчет о НИР по программе ОИТВС РАН " Оптимизация вычислительных архитектур под конкретные классы задач, информационная безопасность сетевых технологий" (шифр "Вега-О-Ст-2006"). #ГР 01.200606060, инв.#0220.0701842. М.: ИППМ РАН, 2006.

22. Калашников В.С. Основные принципы построения отказоустойчивых систем с применением аппарата модулярной арифметики. Микроэлектроника и информатика-2006. 13-я Всероссийская межвузовская научно-техническая конференция студентов и аспирантов: Тезисы докладов, М.:МИЭТ, 2006. - С. 237.

23. Корнилов А.И., Семенов М.Ю., Ласточкин О.В., Калашников В.С. Методология проектирования специализированных вычислителей на основе автоматизированной генерации технологически независимых IP-блоков.// Проблемы разработки перспективных микроэлектронных схем -2005. Сборник научных трудов/ под общ. ред. А. Л. Стемпковского. М.: ИППМ РАН, 2005. - 537с., С.487-492.

24. Корнилов А.И., Семенов М.Ю., Ласточкин О.В., Калашников В.С. Реализация специализированных быстродействующих вычислителей на основе нетрадиционных алгоритмов с применением IP-генераторов. 5 Международная научно-техническая конференция "Электроника и информатика". - 2005.

25. Стемпковский А.Л., Корнилов А.И., Семенов М.Ю., Ласточкин О.В., Калашников В.С. Построение систем повышенной надежности на основе аппарата модулярной арифметики с применением современных методов и средств проектирования// Проблемы разработки перспективных микроэлектронных схем -2006. Сборник научных трудов/ под общ. ред. А. Л. Стемпковского. М.: ИППМ РАН, 2006. - 452с., С.253-258.


Персональные инструменты
Пространства имён

Варианты
Действия
Навигация