Обеспечение работоспособности систем с произвольным доступом и самопроверяемости логических схем тема диссертации и автореферата по ВАК РФ 05.13.01, кандидат технических наук Седов, Юрий Владимирович

• Седов, Юрий Владимирович
• кандидат технических наук
• 2004

Оглавление диссертации кандидат технических наук Седов, Юрий Владимирович

ВВЕДЕНИЕ.

1. ОБЗОР МЕТОДОВ ОБЕСПЕЧЕНИЯ РАБОТОСПОСОБНОСТИ СИСТЕМ С ПРОИЗВОЛЬНЫМ ДОСТУПОМ и САМОПРОВЕРЯЕМОСТИ ЛОГИЧЕСКИХ СХЕМ.

1.1. Введение.

1.2. Обзор методов восстановления поврежденных систем с произвольным доступом.

1.2.1. Статическое резервирование.

1.2.2. Динамическое резервирование.

1.2.3. Гибридная избыточность.

1.2.4. Использование резервирования для восстановления поврежденных систем с произвольным доступом.

1.3. Обзор методов обеспечения самопроверяемости логических схем.

1.3.1. Самотестируемые схемы.

1.3.2. Самопроверяемые схемы.

1.4. Выводы.

2.ЧАСТИЧНОЕ ВОССТАНОВЛЕНИЕ РАБОТОСПОСОБНОСТИ ДИСКРЕТНЫХ СИСТЕМ С ПРОИЗВОЛЬНЫМ ДОСТУПОМ.

2.1. Введение.

2.2. Постановка задачи.

2.3. Минимизация отображения Р.

2.3.1. Точный метод.

2.3.2. Построение минимизированного отображения Р.

2.3.3. Сравнение алгоритмов.

2.4. Выводы.

3. ЧАСТИЧНО МОНОТОННЫЕ СИСТЕМЫ И А ,Б-НЕИСПРАВНОСТИ.

3.1. Введение.

3.2. Монотонные и частично монотонные системы.

3.3. Получение частично-монотонных систем булевых функций по микропрограммному описанию синхронного последовательностного устройства.

3.4. Многоуровневые методы синтеза.

3.5. Выводы.

4. ПРОЯВЛЕНИЕ А,Б-НЕИСПРАВНОСТЕЙ В СИНХРОННЫХ ПОСЛЕДОВАТЕЛЬНОСТНЫХ УСТРОЙСТВАХ.

4.1. Введение.

4.2. Проявление А,Б-неисправностей в самопроверяемых синхронных последовательностных схемах.

4.3. Выводы.

Введение диссертации (часть автореферата) на тему «Обеспечение работоспособности систем с произвольным доступом и самопроверяемости логических схем»

Актуальность проблемы

Высокие требования к функциональным возможностям сверхбольших электронных схем (СБИС) ведут к росту их структурной и технологической сложности. Следствием этого становится снижение количества исправных микросхем на стадии их серийного производства и увеличение числа возможных неисправностей в процессе функционирования схемы.

Задача увеличения выпуска исправных микросхем известна как задача повышения процента выхода годных микросхем. Один из путей ее решения -разработка логической структуры СБИС, позволяющей использовать часть устройства, оставшуюся исправной. Разработка таких структур, как правило, выполняется для некоторого заданного класса устройств и позволяет уменьшить стоимость производимых СБИС путем увеличения процента выхода годных микросхем.

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

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

Цель работы

Целью работы является разработка методов восстановления работоспособности систем с произвольным доступом и обеспечения самопроверяемости синхронных последовательностных устройств внесением избыточности в их структуру. Решение обеих проблем предполагает минимизацию дополнительных аппаратурных затрат.

Методы исследования

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

Научная новизна

1. Предложен метод частичного восстановления работоспособности системы с произвольным доступом в случае неисправности части ее элементов. Метод основан на минимизации интервального представления множества адресов исправных элементов системы. Разработаны точный и приближенный алгоритмы минимизации интервального представления.

2. Введена функциональная модель неисправностей синхронных последовательностных схем, описывающая практически значимый класс структурных неисправностей этих схем.

3. Установлено, что неисправности, данного класса проявляются на выходах синхронной последовательностной схемы только монотонно и накопление таких неисправностей сохраняет их монотонное проявление.

Достоверность полученных результатов

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

Практическая ценность

1. Предлагаемый в работе метод частичного восстановления работоспособности систем программно реализован и может быть использован при разработке реконфигурируемых устройств с произвольным доступом.

2. Предлагаемый в работе метод обеспечения самопроверяемости синхронных последовательностных схем хорошо сочетается с широко распространенными в системах автоматизированного проектирования (САПР) методами синтеза дискретных устройств. Это позволяет воспользоваться существующими САПР для разработки самопроверяемых дискретных устройств.

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

Реализация полученных результатов

Исследования, результаты которых изложены в диссертации, проводились в рамках следующих проектов.

1. Госбюджетная тема Сибирского физико-технического института при ТГУ (СФТИ), программа "Исследование и разработка новых методов электромагнитного контроля и диагностики материалов, сред и технических систем", 1995-2000 гг., раздел "Разработка методик и аппаратуры исследований".

2. Межвузовская научно-техническая программа "Конверсия и высокие технологии. 1994-2000 гг.", проект №95-1-21 и №59-1-7 "Информационные компьютерные технологии дискретного математического моделирования, анализа, синтеза и тестирования сверхскоростных интегральных схем логического управления".

3. Федеральная целевая программа "Интеграция". Раздел "Прикладная дискретная математика".

4. Проекты министерства образования по разделу "Автоматика и телемеханика":

Элементы, узлы и устройства автоматики, телемеханики и вычислительной техники", 1995-1996 гг.;

Исследование проблемы повышения качества тестирования и контролепригодного проектирования", 1997-1999 гг.;

Исследование проблемы синтеза самотестируемых устройств и проблемы повышения качества тестирования", 1999-2000 гг.

Апробация работы

Научные результаты, приведенные в данной работе, обсуждались и получили одобрение на заседаниях объединенного семинара кафедры математической логики и проектирования радиофизического факультета ТГУ, кафедры программирования и кафедры защиты информации факультета прикладной математики и кибернетики ТГУ, лаборатории синтеза дискретных автоматов Сибирского физико-технического института (СФТИ) при ТГУ.

Результаты работы представлялись на следующих научных конференциях:

1. Международная конференция "Всесибирские чтения по математике и механике" (Россия, Томск, 1997);

2. III Международная конференция "Новые информационные технологии в исследовании сложных структур" (Россия, Томск, 2000).

3. 8-th IEEE International On-Line Testing Workshop (Bendor, France,

2002).

4. IV Всероссийская конференция с международным участием "Новые информационные технологии в исследовании сложных структур" (Россия, Томск, 2002).

Структура и объем диссертации

Диссертация состоит из введения, 4 глав, заключения и списка используемой литературы. Диссертация содержит 18 рисунков и 8 таблиц. Объем диссертации составляет 117 стр., в том числе: титульный лист - 1 стр., оглавление — 2 стр., основной текст — 92 стр., библиография из 95 наименования - 10 стр., заключение - 1 стр.

Заключение диссертации по теме «Системный анализ, управление и обработка информации (по отраслям)», Седов, Юрий Владимирович

4.3. Выводы

1. Установлено, что А,Б-неисправности могут проявляться на выходах синхронной последовательностной схемы только как монотонные неисправности.

2. Добавление А,Б-неисправности к кратной А,Б-неисправности синхронной последовательностной схемы не проявляющейся в рабочей области функционирования схемы, может привести только к монотонному проявлению новой кратной неисправности.

3. Если структурные неисправности самопроверяемой синхронной последовательностной схемы являются А,Б-неисправностями, достаточно подключать детектор кодов только к выходам схемы, а не к выходам и линиям обратных связей, как это обычно делается. Такая возможность позволяет применять более простые детекторы кодов и, следовательно, сокращать аппаратурные затраты в системе: самопроверяемая схема, детектор кодов.

Список литературы диссертационного исследования кандидат технических наук Седов, Юрий Владимирович, 2004 год

1. Обеспечение качества микроэлектронных устройств // Радиоэлектроника (состояние и тенденции развития) обзор по материалам зарубежной печати, ч.1,2, 1983.

2. Zorian Y. Yield Improvement and Repair Trade-Off for Large Embedded Memories // Design, Automation and Test in Europe.- March 27, 2000. pp. 69-72.

3. Stapper С. H., McLaren A. N., Dreckmann M. Yield Model for Productivity Optimization of VLSI Memory Chips with Redundancy and Partially Good Product // IBM Journal of Research and Development, 1980, v.24, N 3, pp.398410

4. Schuster S.E. Multiple word/bit line redundancy for semiconductor memories // IEEE Journal of Solid-State Circuits, 1978, v.SC-13, N 5, pp.698-703

5. Blanks H. S. The temperature dependence of component failure rate // Microelectronics and Reliability, 1980, v.20, N 3, pp.297-307

6. Bossen D. C., Hsiao M. Y. A System Solution to the Memory Soft Error Problem // IBM Journal of Research and Development, 1980, v.24, N 3, pp.390-398

7. Anderson A., Lee P. Fault tolerance: Principles and Practice. Prentice Hall, 1980.

8. Davies D., Wakerley J.F. Synchronization and matching in redundant systems // IEEE Trans. Computers, C-27 June 1978 - pp.531-539.th

9. Lewis D.W. A fault tolerant clock using stand-by sparing // Proc. 9 Int. Symp. Fault-Tolerant Computing, 1979, pp.33-40.

10. FTSC. The fault-tolerant spaceborne computer. Digest 6th Int. Symp. Fault-Tolerant Computing, 1976, pp. 129-147.

11. Ball M., Hardie H. Majority voter design considerations for TMR computers // Computer Design, April, 1969, pp. 100-104.

12. Васильев Н.П. и др. Самовосстанавливаемая управляющая ВС // В книге "III Всесоюзное совещание по технической диагностике". М., Наука, 1975.

13. Pradah D.K. Redundancy schemes for Recovery. Univ. of Massachusetts, 1989.

14. Веселовский Г.Г., Каравай М.Ф., Кузнечик С.И. Коммутационные сети в МВС с общим управлением (анализ современного состояния) // Автоматика и телемеханика, N2, 1988 г.

15. Toy W.N. Fault-tolerant design of local ESS processors. // Proc. IEEE 66, October 1978, pp.1126-1145.16.1hara H., Fukuoka K., Kubo Y., Yokota S. Fault-tolerant computer system with three symmetric computers // Proc. IEEE 66, October 1978, pp.1160-1177

16. Katsman J.A. A fault-tolerant computing system // Proc. 11th Int. Conf on Syst. Sciences, Hawaii, Jan.1978, 85-102.

17. Cochi В., Reliabilty modeling and analysis of hybrid redundancy // Proc. 5th Int. Symp. Fault-Tolerant Computing, 1975, 569-577.

18. Siewiorek D.P., McCluskey E.J. An iterative cell switch design for hybrid redundancy // IEEE Trans. Computers, C-22, March 1973 pp.290-297.

19. Mathur F.P. On reliability modelling and analysis of ultra-reliable fault-tolerant systems. // IEEE Trans. Computers, C-20, November 1971 pp.1376-1382.

20. Patent N 4047163 USA / Fault-tolerant cell addressable array.-September 6, 1977

21. Patent N 4748597 USA / Semiconductor memory device with redundancy circuits.- May 31, 1988

22. Patent N 6484271 USA / Memory redundancy techniques.- November 19, 2002

23. Patent N 5889711 USA / Memory redundancy for high density memory.- March 30, 1999

24. Patent N 5313424 USA / Module level electronic redundancy.-May 17, 1994

25. Пархоменко П. П., Согомонян Е. С. Основы технической диагностики. -М.: Энергоиздат, 1981. -320 с.

26. Lala, Parag К. Self-checking digital design // Academic press 2001.

27. McCluskey E. J. Built-in Self-Test Structures// IEEE Design & Test of Computers. -April 1985. -Pp. 21-36.

28. Agrawal V. D., Kime C. R., Saluja К. K. A Tutorial on Built-In-Self-Test, Part 1: Principles// IEEE Design & Test of Computers. -Vol.10, -№1. -1993. -Pp. 73-82.

29. Agrawal V. D., Kime C. R., Saluja К. K. A Tutorial on Built-In-Self-Test, Part 2: Applications//IEEE Design & Test of Computers. -Vol.10, -№2. -1993. Pp. 69-77.

30. Horwarth J. Checking Sequential Logic Circuits/ US PS 4556976, G06F 11/00. -1985.

31. Siewiorek D. P., Schwarz R. S. The Theory and Practice of Reliable System Design. -Bedford: Digital Press. -1982.

32. Sellers F. F., Hsiao M. J., Bearnson L. W. Error Detecting Logic for Digital Computers. -New York: McGraw-Hill. -1968.

33. Betrand J. C., Gambiasi N., Mercier J. J. Totally Self-Checking Sequential Circuits// Proc. Int. Sympos. «Discrete Systems». -Riga: Zinatne. -Bd. 2. -1974. -pp. 36-44.

34. Carter W. C., Schneider P. R. Design of Dynamically Checked Computers// JFIP Congress. -1968. -pp. 878-883.

35. Согомонян E. С. Построение дискретных устройств с диагностикой в процессе функционирования// Автоматика и телемеханика. -№11. -1970. -с. 153-160.

36. Аксенова Г. П., Согомонян Е. С. Синтез схем встроенного контроля для автоматов с памятью// Автоматика и телемеханика. -№9. -1971. -с. 170-179.

37. Lala, Parag К. Self-checking digital design // Academic press 2001.

38. Anderson D.A., G.Metze Design of totally self-checking check circuits for m-out-of-n codes // IEEE Trans.Comput., pp 263-269, March 1973.

39. Marouf M.A., Friedman A.D. Efficient design of self-checking checker for any m-out-of-n code // IEEE Trans. Comput., pp 482-490, June 1978.

40. Mak G.P., Abraham J.A., Davidson E.S. The design of PLAs with concurrent error detection // Proc. 12th Int. Symp. on Fault-Tolerant Computing, Milan, Italy, 1982, pp.202-210.

41. Goessel M., Sogomonyan E. S. Code Disjoint Self-Parity Combinational Circuits for Self-Testing, Concurrent Fault Detection and Parity Scan Design// 12th IEEE VLSI Test Symp. -1994. -p. 151-157.

42. Gossel M., Sogomonyan E. S. Self-Parity Combinational Circuits for Self-Testing, Concurrent Fault Detection and Parity Scan Design// Procceedings VLSI 93. -1993.- pp. 311-318.

43. Wong C.Y., Fuchs W.S., Abraham J.A., Davidson E.S. The design of a microprogram control unit with concurrent error detection // Proc. of 12th Int. Symp. on Fault-Tolerant Computing, Milan, Italy, 1982, pp.476-482.

44. Bose В., Rao T.R.N. Theory of unidirectional error correcting/detecting code // IEEE Trans .Computers, C-31, N6 1982 - pp.521-530.

45. Яблонский C.B., Введение в дискретную математику, Москва, "Наука", 1979.

46. Berger J. М. A Note on Error Detection Codes for Asymmetric Channels, Inform. Contr., -vol.4, -March, -1961, -pp. 68-73.

47. Каравай М.Ф., Согомонян E.C., Шагаев И.А. Отказоустойчивые вычислительные системы // Журнал "Успехи наук", 1990, N26.

48. M.Choi, N-J.Park Optimal Spare Utilization in Repairable and Reliable Memory Cores // Proc. of the 2003 Int. Workshop on Memory Technology, Design and Testing.

49. Subhasish Mitra, Edward J. McCluskey Design Diversity for Concurrent Error Detection in Sequential Logic Circuts // 19th IEEE VLSI Test Symposium, April 2001.

50. Tohma Y., Ohyama Y. Realization of fail-safe sequential machines by using a k-out-of-n code // IEEE Trans. Сотр. -1971, pp. 1270-1275.

51. Bolchini C., Montandon R., Salice F., Sciuto D. Self-Checking FSMs Based on a Constant instance State Encoding// Int. Symp. on Defects on Fault Tolerance in VLSI Systems. -1998, November.

52. Bolchini, C., Montandon R., Salince F., Sciuto D. Design of VHDL-Based Totally Self-Checking Finite State Machines and Data-Path Descriptions // IEEE Transaction on VLSI Systems, v.8, No. 1, 2000.

53. Diaz M., Geffroy J.C., CourvoisierM. On-Set Realization of Fail-Safe Sequential Machines // IEEE Trans, on Сотр., v.C-23, pp. 133-138, Feb. 1974.

54. Diaz M. Design of Totally Self-Checking and Fail-safe Sequential Machines // Proc. 4th Int. Fault Tolerant Computing Symposium, Urbana, IL, 1974.

55. Лосев B.B., Конопелько B.K., Урбанович П.П. Системы памяти на базе запоминающих устройств с дефектными элементами // Зарубежная электронная техника, N9, 1982, сс.3-33.

56. Touba, N.A., McCluskey E.J. Logic Synthesis of Multilevel Circuits with Concurrent Error Detection // IEEE Transactions on Computer-Aided Design, v. 16, N 7, pp. 783-789, July 199764.3акревский А.Д. Логический синтез каскадных схем. M.: Наука 1981 г.

57. Баранов С.И., Скляров В.А. Цифровые устройства на программируемых БИС с матричной структурой. М.: Радио и связь 1986 г.бб.Закревский А.Д., Балаклей Л.И., Елисеева H.A. и др. Синтез асинхронных автоматов на ЭВМ. -Минск: Наука и техника, -1975.

58. R.Murgai, R. Brayton, A. Sangiovanni-Vincentelli. Logic Synthesis for Field Programmable Gate Arrays. Cluver Academic Publishers, 1995, 425p.

59. Яблонский C.B., Гаврилов Г.П., Кудрявцев В.Б. Функции алгебры логики и классы Поста. М.: Наука 1966 г.

60. Нигматуллин Р.Г. Сложность булевых функций. М.: Наука 1991 г.

61. Матросова А.Ю. Алгоритмические методы синтеза тестов. Издательство ТГУ.- 1990 г.

62. Матросова А. Ю., Останин С. А. К синтезу самопроверяемых комбинационных схем// Международная конференция «Всесибирские чтения по математике и механике», Россия, Томск, Тезисы докладов том 1 «Математика», -1997. -160-161 с .

63. Матросова А. Ю., Останин С. А. К синтезу самопроверяемых комбинационных схем// Международная конференция «Всесибирские чтения по математике и механике», Россия, Томск, Избранные доклады том 1 «Математика», -1997. -179-185 с .

64. Горяшко А.П. Синтез диагностируемых схем вычислительных устройств // М.: Наука 1987.

65. Матросова А.Ю., Останин С.А., Паршина Н.А. К синтезу контролепригодных комбинационных устройств// Автоматика и телемеханика. -№2. -1999. -С. 129-137.

66. Prabhu A.M. LOGOPT a multi-level logic synthesis and optimization system // Custom Integrated Circuit Conference, 1989.

67. R.Murgai, Y.Nishizaki, R. Brayton, A. Sangiovanni-Vincentelli. Logic Synthesis for Programmable Gate Arrays // 27th ACM/IEEE Design Automation Conference 1990 - pp.620-625.

68. Матросова А.Ю., Останин C.A. Синтез самопроверяемых синхронных последовательностных устройств// Материалы международной сибирской конференции по исследованию операций, Новосибирск, 22-27 июня, -1998. -132 с.

69. Матросова А.Ю., Останин С.А. Синтез самопроверяемых синхронных автоматов// Труды международной конференции «Новые информационные технологии в науке, образовании, телекоммуникации и бизнесе», часть 2, Украина, Крым, Ялта-Гурзуф, 15-24 мая. -1998.

70. Matrosova A.Yu., Ostanin S.A. Self-Checking Synchronous Sequential Circuit Design for Unidirectional Error// Compendium of papers. IEEE European Test Workshop 1998, May 27-29, -1998, Sitges, Barcelona, Spain.

71. Matrosova A. Yu., Ostanin S.A. Self-Checking Synchronous FSM Network Design// Compendium of papers. 4th IEEE International On-Line Testing Workshop, July 6-8, 1998, Capri, Italy.

72. Levin I., Matrosova A. Yu., Sinelnikov V., Ostanin S. A. Totally Self-Checking FPGA based FSM //5th IEEE Intl. On-Line Testing Workshop, Rhodes, Greece, July 1999.

73. Матросова А.Ю., Останин С.А. Синтез самопроверяемых синхронных устройств и сетей из них// Материалы конференции "Новые информационные технологии в исследовании дискретных структур", Екатеринбург, -1998, -173-179 с.

74. Matrosova A. Yu., Levin I., Ostanin S. A. Self-Checking Synchronous FSM Network Design with Low Overhead// Journal of VLSI Design.-Overseas Publishers Assocoation. volOO, -.№00, -2000, -L-L2p.

75. J.A.Abraham. Challenges in Fault Detection // 9th IEEE Int. On-Line Testing Symp. July 2003.

76. Агибалов Г. П., Оранов А. М. Лекции по теории конечных автоматов: Учеб. Пособие, -Томск: Из-во Том. Университета, -1984. -186 с.

77. Ball М., Hardie F. Effects and detection of intermitten faults in digital systems. // Proc. Fall Joint Computer Conf., 1978, pp.329-335.

78. Tasar O., Tasar V. A study of intermitten faults in digital computers // AFIPS Conf. Proc. 1977, pp.807-811.

79. Lala P.K., Missen J.I. Method for the diagnosis of a single intermitten fault in combinatorial logic circuits // IEEE Jour. Computers and Digital Techniques, October 1979, pp.187-190.

80. Malaiya Y.K., S.Y.H.Su A survey of methods for intermitten faults analysis. // Proc. Nat. Сотр. Conf., 1979, pp.577-584.

81. Ю.В. Седов К проблемам частичного восстановления работоспособности дискретных систем с произвольным доступом // Вестник ТГУ, 2002

82. A.Matrosova, V.Andreeva, Yu.Sedov Survivable Discrete Circuits Design // Proc. of 8-th IEEE International On-Line Testing Workshop, Bendor, France, July 2002

83. Matrosova A., Andreeva V., Goloubeva О., Nikitin К., Ostanin S., Sedov Yu. Self-Checking and Fail-Safe Synchronous Sequential Circuit Design. // Радиоэлектроника и информатика, №3, 2003, -С. 107-112.1. ЗАКЛЮЧЕНИЕ