Содержание к диссертации
Введение
1. Обзор методов обеспечения работоспособности систем с произвольным доступом и самопроверяемости логических схем 17
1.1. Введение 17
1.2. Обзор методов восстановления поврежденных систем с произвольным доступом 18
1.2.1. Статическое резервирование 21
1.2.2. Динамическое резервирование 22
1.2.3. Гибридная избыточность 24
1.2.4. Использование резервирования для восстановления поврежденных систем с произвольным доступом 25
1.3. Обзор методов обеспечения самопроверяемости логических схем 28
1.3.1. Самотестируемые схемы 30
1.3.2. Самопроверяемые схемы 31
1.4. Выводы 37
2. Частичное восстановление работоспособности дискретных систем с произвольным доступом 39
2.1. Введение 39
2.2. Постановка задачи 39
2.3. Минимизация отображения Р 44
2.3.1. Точный метод 44
2.3.2. Построение минимизированного отображения Р 57
2.3.3. Сравнение алгоритмов 66
2.4. Выводы 68
3. Частично монотонные системы и А,Б-неисправности 70
3.1. Введение 70
3.2. Монотонные и частично монотонные системы 72
3.3. Получение частично-монотонных систем булевых функций по микропрограммному описаниго синхронного последовательности ого устройства 76
3.4. Многоуровневые методы синтеза 83
3.5. Выводы 97
4. Проявление А,Б-неисправностей в синхронных последовательностных устройствах 99
4.1. Введение 99
4.2. Проявление А,Б-неисправностей в самопроверяемых синхронных последовательностных схемах 100
4.3. Выводы 105
Список литературы 107
Заключение 117
- Обзор методов восстановления поврежденных систем с произвольным доступом
- Построение минимизированного отображения Р
- Монотонные и частично монотонные системы
- Проявление А,Б-неисправностей в самопроверяемых синхронных последовательностных схемах
Введение к работе
Актуальность проблемы.
Высокие требования к функциональным возможностям сверхбольших электронных схем (СБИС) ведут к росту их структурной и технологической сложности. Следствием этого становится снижение количества исправных микросхем на стадии их серийного производства и увеличение числа возможных неисправностей в процессе функционирования схемы.
Задача увеличения выпуска исправных микросхем известна как задача повышения процента выхода годных микросхем. Один из путей ее решения - разработка логической структуры СБИС, позволяющей использовать часть устройства, оставшуюся исправной. Разработка таких структур, как правило, выполняется для некоторого заданного класса устройств и позволяет уменьшить стоимость производимых СБИС путем увеличения процента выхода годных микросхем.
Для контроля правильности функционирования устройства широко применяется внесение избыточности в проектируемое устройство. При этом стремятся обеспечить обнаружение неисправности в момент ее первого проявления на выходах устройства. Такое свойство позволяет локализовать распространение последствий неисправности и тем самым повышает надежность всей системы, в состав которой входит устройство. Один из подходов к обнаружению неисправности в момент ее первого проявления на выходах заключается в проектировании самопроверяемых устройств.
Таким образом, задачи восстановления работоспособности устройств и обеспечения их самопроверяемости являются актуальными.
Цель работы.
Целью работы является разработка методов восстановления работоспособности систем с произвольным доступом и обеспечения самопроверяемости синхронных последовательностных устройств внесением избыточности в их структуру. Решение обеих проблем предполагает минимизацию дополнительных аппаратурных затрат.
Методика исследования.
В работе используется аппарат дискретной математики, в частности, алгебры логики, теории автоматов и теории графов. Эффективность разработанных методов подтверждается компьютерными экспериментами.
Научная новизна.
Предложен метод частичного восстановления работоспособности системы с произвольным доступом в случае неисправности части ее элементов. Метод основан на минимизации интервального представления множества адресов исправных элементов системы. Разработаны точный и приближенный алгоритмы минимизации интервального представления.
Введена функциональная модель неисправностей синхронных последовательностных схем, описывающая практически значимый класс структурных неисправностей этих схем.
Установлено, что неисправности, данного класса проявляются на выходах синхронной последовательностной схемы только монотонно и накопление таких неисправностей сохраняет их монотонное проявление.
Достоверность полученных результатов.
Все научные положения и выводы, содержащиеся в диссертации, основаны на утверждениях, доказанных с использованием аппарата дискретной математики. Эффективность предложенных методов восстановления работоспособности систем с произвольным доступом подтверждена компьютерными экспериментами.
Практическая ценность работы.
Предлагаемый в работе метод частичного восстановления работоспособности систем программно реализован и может быть использован при разработке устройств с произвольным доступом.
Предлагаемый в работе метод обеспечения само проверяемости синхронных последовательностных схем хорошо сочетается с широко распространенными в САПР методами синтеза дискретных устройств. Это позволяет воспользоваться существующими САПР для разработки самопроверяемых дискретных устройств.
Предлагаемый метод обеспечения само проверяемости позволяет существенно снизить сложность дополнительного аппаратного обеспечения (детектора кодов) за счет наблюдения только за выходами самопроверяемых синхронных последовательностных устройств, а не за выходами и линиями обратных связей, как это обычно делается.
Реализация и внедрение полученных результатов.
Исследования, результаты которых изложены в диссертации, проводились в рамках следующих проектов.
Госбюджетная тема Сибирского физико-технического института при ТГУ (СФТИ), программа "Исследование и разработка новых методов электромагнитного контроля и диагностики материалов, сред и технических систем", 1995-2000 гг., раздел "Разработка методик и аппаратуры исследований".
Межвузовская научно-техническая программа "Конверсия и высокие технологии. 1994-2000 гг.", проект №95-1-21 и №59-1-7 "Информационные компьютерные технологии дискретного математического моделирования, анализа, синтеза и тестирования сверхскоростных интегральных схем логического управления".
ФЦП "Интеграция". Раздел "Прикладная дискретная математика".
Проекты министерства образования по разделу "Автоматика и телемеханика":
"Элементы, узлы и устройства автоматики, телемеханики и вычислительной техники", 1995-1996 гг.;
"Исследование проблемы повышения качества тестирования и контроле пригодно го проектирования", 1997-1998 гг.;
"Исследование проблемы синтеза самотестируемых устройств и проблемы повышения качества тестирования", 1999-2000 гг.
Апробация работы.
Научные результаты, приведенные в данной работе, обсуждались и получили одобрение на заседаниях объединенного семинара кафедры математической логики и проектирования радиофизического факультета ТГУ, кафедры программирования факультета прикладной математики и кибернетики ТГУ, лаборатории синтеза дискретных автоматов Сибирского физико-технического института (СФТИ) при ТГУ и кафедры защиты информации факультета прикладной математики и кибернетики ТГУ.
Результаты работы представлялись на следующих научных конференциях.
Международная конференция "Всесибирские чтения по математике и механике" (Россия, Томск, 1997).
III Международная конференция "Новые информационные технологии в исследовании сложных структур", (Россия, Томск, 2000).
8-th IEEE International On-Line Testing Workshop, (Bendor, France, July 2002).
IV Всероссийская конференция с международным участием "Новые информационные технологии в исследовании сложных структур", (Россия, Томск, 2002).
Структура и объем диссертации.
Обзор методов восстановления поврежденных систем с произвольным доступом
Благодаря достижениям в области проектирования сверхбольших электронных схем (СБИС) плотность размещения элементов на кристалле постоянно растет. Однако с ростом плотности компоновки элементов увеличивается число потенциальных неисправностей, и усложняются способы их обнаружения. Кристалл СБИС может содержать десятки тысяч внутренних элементов, которые недоступны для непосредственного наблюдения и управления. Задача поиска неисправностей в таких условиях может оказаться чрезвычайно сложной. Для преодоления этой сложности используются как специальные методы диагностирования, так и методы построения устройств со структурой, облегчающей диагностирование, а в некоторых случаях, и обеспечивающей устранение неисправности.
Под неисправностью схемы будем понимать ее физический дефект. Такие дефекты могут появляться в схеме, как в процессе ее производства, так и в процессе ее эксплуатации.
Появление дефектов в СБИС на стадии производства ведет к уменьшению процента выхода годных микросхем в общем объеме продукции. что в свою очередь ведет к удорожанию микросхем. Один из способов уменьшения числа производственных дефектов заключается в совершенствовании технологических операций изготовления СБИС. Однако даже современные технологии изготовления микросхем не дают возможности значительно улучшить процент выхода годных устройств [1,2]. Поэтому актуальной является задача разработки логической структуры устройства, позволяющей полностью или частично восстанавливать его работоспособность в случае возникновения дефектов. Разработка таких логических структур выполняется для определенных классов устройств. 1.2. Обзор методов восстановления поврежденных систем с произвольным доступом Широко распространенным классом устройств являются системы с произвольным доступом. Такие устройства включают в себя набор элементов, выполняющих одинаковые функции, и поддерживают возможность использования каждого из них в произвольном порядке, независимо друг от друга. Для этого каждый элемент, входящий в состав устройства, должен характеризоваться уникальным номером, или адресом. Примером такого устройства может служить блок памяти с произвольным доступом к его элементам. Исследования дефектов, возникающих при производстве систем с произвольным доступом (в частности, для СБИС памяти) [3,4,5] показали, что с точки зрения восстановления работоспособности устройства все виды дефектов можно разделить на две категории: - дефекты, влияющие на подмножество рабочих элементов системы (запоминающие устройства, для СБИС памяти); - фатальные дефекты, полностью выводящие устройство из строя. В ряде работ [3,5,6] отмечается, что дефекты, влияющие на подмножество рабочих элементов систем с произвольным доступом, происходят значительно чаще. Это объясняется тем, что вероятность отказа для каждого класса устройств пропорциональна площади, занимаемой соответствующими подсхемами на кристалле [3]. Поэтому, был разработан ряд методов, позволяющих использовать частично работоспособные микросхемы для повышения процента выхода годных устройств. На практике наиболее широко используются следующие методы [3,6,62]: метод индивидуальных соединений, согласно которому сформированные рабочие элементы не соединяются между собой в процессе производства. В процессе контроля СБИС устанавливается местоположение дефектных элементов и на основании этого, производят соединение годных элементов, образующих систему. Такой метод непригоден при массовом изготовлении микросхем; метод дублирования рабочих элементов, при котором, в разных местах СБИС располагается несколько рабочих элементов, обращение к которым выполняется по одному адресу, а при считывании используется принцип мажорирования. Реализация этого метода требует значительных аппаратных расходов и повышения энергопотребления микросхемы. метод контрольного считывания сводится к тому, что в процессе производственного тестирования микросхемы устанавливается расположение неисправных элементов. Затем, дополнительной технологической операцией в дефектные рабочие элементы вносят изменения так, чтобы их состояние отличалось от состояния исправного элемента (для запоминающих устройств -состояние, отличное от логического 0 или 1). Перед использованием элемента производится контрольное считывание состояния элемента, по результатам которого используется либо текущий элемент, либо резервный. Использование такого метода приводит к значительной потере быстродействия. метод использования резервных строк и/или столбцов рабочих элементов взамен дефектных. Замена неисправных элементов может выполняться как на завершающих стадиях производства, так и в процессе функционирования микросхемы, в зависимости от реализации метода замены. использование корректирующих кодов. Наибольшее применение находят последние два метода. При этом следует отметить, что корректирующие коды применяются в первую очередь для устранения неисправностей, возникающих в процессе эксплуатации устройства. Большинство остальных перечисленных методов для восстановления устройства используют множество резервных рабочих элементов. Поэтому, имеет смысл рассмотреть основные виды резервирования [7], используемые, в частности, и для восстановления систем с произвольным доступом.
Построение минимизированного отображения Р
Представим f Е в виде ортогональной ДНФ. Для этого воспользуемся алгоритмом Квайна перебора частичных интерпретаций с направленным выбором переменных [70]. Пусть fK задана совершенной ДНФ DE ИЛИ любой другой ДНФ. Алгоритм построения ортогональной ДНФ функции /,.. Некоторую вершину примем в качестве корня дерева поиска. 1. Для каждой переменной из DE подсчитываем число ее вхождений в D/ с инверсией и без инверсии. Выбираем ту переменную, у которой число вхождений в ДНФ с одним и тем же знаком инверсии максимально. При фиксировании такой переменной соответствующим значением исключается максимальное число конъюнкций DE. Это позволяет быстрее находить конъюнкции меньших рангов, ортогональные DE. 2. Сопоставляем очередной вершине дерева символ этой переменной. Из помеченной таким образом вершины проводим ребро в новую вершину. Помечаем его соответствующим значением переменной (то есть, таким, чтобы фиксация переменной этим значением обращала в 0 максимальное число конъюнкций из DE). 3. Для очередной неотмеченной вершины находим последовательность ребер от нее до корня дерева поиска. Выписываем двоичный набор, приписанный ребрам этой простой цепи. Подставим в DE значения из полученного набора. Если после этого DE обратилась в 1, то помечаем вершину символом 1 и считаем ее концевой. Если )/, обращается в 0, то переменные, которыми помечены символы простой цепи от корня, до рассматриваемой вершины, образуют конъюнкцию, ортогональную D/,-, а значения, приписанные ребрам этой цепи описывают знаки инверсии над переменными конъюнкции. Включаем эту конъюнкцию в строящуюся D,,. Вершину помечаем символом 0 и считаем ее концевой. Если Dg не обращается в константу, то переходим в п.1, рассматривая в качестве DE ТО, ЧТО ОТ нее останется после подстановки констант. 4. Возврат на предыдущий уровень дерева поиска осуществляется, если вершина концевая, либо из нее уже проведены два ребра. Если из вершины проведено только одно ребро, то проводим из нее второе, пометив ее инверсным значением и переходим в п.З. Закончив обход дерева поиска, строим ),, из конъюнкций, сопоставляемых вершинам, помеченным константой 0. В качестве примера, рассмотрим ДНФ D=x x2x7ixAxfi v х{х2х2х хя v использованную в предыдущем разделе. В соответствии с пунктом 1 алгоритма, корень дерева поиска отмечаем переменной Xj, и из этой вершины проводим ребро, помеченное символом 0 в новую вершину. Этой вершине будет соответствовать ДНФ На основании подсчета числа вхождений переменных с одинаковыми знаками инверсий новой вершине приписываем символ переменной х? и проводим из нее ребро, помеченное символом 0. Таким образом, переходим к ДНФ Dx ( = х3х4х5. Приписываем текущей вершине символ хз и проводим из нее ребро, помеченное символом 0. Поскольку в новой вершине ДНФ D-- - обращается в 0, то включаем в решение конъюнкцию х,х2х,. Согласно алгоритму проводим из вершины х? ребро, помеченное 1. В полученной вершине ДНФ обращается в 1 и данная конъюнкция нас не интересует. Переходим ярусом выше и проводим из вершины х2 ребро, помеченное 1. Новой вершине соответствует ДНФ х3х4х5 v х3х х5, которая обращается в 0 фиксацией переменной х единичным значением. Таким образом, в решение включается конъюнкция х}х2х,, и мы возвращаемся в корневую вершину.
Монотонные и частично монотонные системы
Вернемся к рассмотрению синхронных последовательностных устройств. Пусть поведение устройства задано микропрограммным описанием. Предполагается, что символы входного и выходного алфавитов соответствующего синхронного автомата уже закодированы, а символы состояний - еще нет. Таблица 1 есть микропрограммное описание поведения некоторого синхронного устройства (автомата).
Выполнив кодирование состояний в микропрограммном описании, получим систему частичных функций переходов-выходов. Перейдя к полностью определенной системе, будем иметь задание на синтез синхронного последовательностного устройства.
Кодирование состояний существенно влияет на результат синтеза (на структурную реализацию устройства). Кодирование выполняется либо с целью упрощения структурной реализации, либо с целью обеспечения надежности функционирования за счет введения (по возможности меньшей) структурной избыточности. Последнее имеет место при синтезе самопроверяемых синхронных устройств. В этом случае часто применяется кодирование состояний неупорядоченными кодами, среди которых выделяют равновесные коды и коды Бергера [84]. Предпочтение отдается тому коду, который для конкретного микропрограммного описания обеспечивает меньшую длину кода.
Кодирование неупорядоченными кодами символов выходного алфавита и состояний позволяет обнаруживать неисправности, приводящие к замене кодового слова на некодовые [79,80,82]. Напомним, что неупорядоченным кодом называется множество булевых векторов (кодов) одинаковой размерности, где любые два вектора не сравнимы.
В рассматриваемом в таблице 2 примере мы воспользовались равновесным кодом для кодирования состояний. Равновесные коды для уже закодированных символов выходного алфавита получаются добавлением недостающих единичных компонент. В рассматриваемом примере равновесный код оказывается короче кода Бергера. Действительно, для кодирования четырех состояний кодом Бергера потребовались бы две компоненты для информационной составляющей кода и две - для контролирующей составляющей. При кодировании символов выходного алфавита кодами Бергера пришлось бы добавить к имеющимся кодам три компоненты вместо двух.
Будем иметь ввиду, что таблица 2 может рассматриваться как интервальное описание системы F(Jf,Z) частичных булевых функций, в котором характеристика интервалов представлена булевым вектором. Если компонента булева вектора в характеристике принимает значение 1(0), то соответствующая ей функция системы на интервале, к которому характеристика относится, также принимает значение 1(0). Два троичных вектора а(,а2 1-ортогональны, если в одном из них существует г-я компонента, принимающая значение 1(0), а в другом эта же компонента принимает значение 0(1). Если для векторов а,,а, найдутся две такие компоненты, векторы 2-ортогональны, три - 3-ортогональны и так далее. Векторы а,,а, инверсно 2-ортогональны, если для них найдется компонента /, такая, что в а і она принимает значение 0, а в а 2 — 1 и компонента у такая, что в а і она принимает значение 1, а в а2 - 0. Векторы а,,а, могут быть ортогональны и по другим компонентам. Все сказанное для векторов справедливо и для представляемых ими интервалов [74].
Проявление А,Б-неисправностей в самопроверяемых синхронных последовательностных схемах
В рассматриваемом примере неисправности на полюсах схем элементов реального базиса, являются подмножеством неисправностей логической схемы устройства в фиктивном базисе. В общем случае это условие выполняется не всегда, поскольку элемент может являться точкой ветвления в логической схеме.
Как правило ([67,76]), используются эвристические процедуры выделения в G подсхем и оптимального покрытия каждого выделенного фрагмента подсхемами в фиктивном базисе. Критерием оптимальности получаемого покрытия схемы G подсхемами фиктивного базиса служит их суммарная площадь. Различные эвристики, примененные при получении минимизированной системы логических функций за счет выделения ядер и соядер и при покрытии логической схемы подсхемами элементов в фиктивном базисе, характеризуют множество методов многоуровневого синтеза комбинационных схем. Многие современные коммерческие системы автоматизированного проектирования используют разновидности многоуровневого метода синтеза.
Будем ориентироваться именно на эту технологию получения комбинационной схемы и рассматривать одиночные константные неисправности на полюсах схем, соответствующих элементам реального базиса. Одиночная константная неисправность полюса логической схемы в реальном базисе есть А,Б-неисправность. Доказательство. Если полюс реального элемента не является точкой ветвления логической схемы в фиктивном базисе, то рассматриваемая неисправность эквивалентна неисправности соответствующего полюса схемы в фиктивном базисе, и, следовательно, является А,Б-неисправностью. Если полюс является точкой ветвления в логической схеме устройства в фиктивном базисе, тогда имеем следующие возможные случаи: 1. Неисправность на полюсе элемента реального базиса приводит к исчезновению подмножества конъюнкций в системе F по отношению к множеству тех конъюнкций, которые исчезают в случае неисправности этого же полюса в логической схеме устройства в фиктивном базисе. 2. Неисправность на полюсе элемента реального базиса приводит к исчезновению букв в подмножестве тех конъюнкций в системе F , которые соответствуют множеству искаженных конъюнкций для случая неисправности этого же полюса в логической схеме устройства в фиктивном базисе. Теорема доказана. Таким образом, в логической схеме устройства синтезированного многоуровневым методом по системе булевых функций частично-монотонных по Беременным, сопоставляемым линиям обратных связей, константные неисправности на полюсах элементов являются А,Б-неисправностями. Это значит, что предлагаемая функциональная модель неисправностей описывает практически значимый класс структурных неисправностей, с учетом использования многоуровневого метода синтеза. 3.5. Выводы 1. Введено понятие частично-монотонной системы булевых функций и основанное на нем понятие функциональных А,Б-неисправностей для синхронных логических схем. 2. Показано, что всякий синхронный автомат после кодирования его состояний неупорядоченными кодами может быть представлен системой частично-монотонных (по внутренним переменным) булевых функций. 3. Доказано, что при реализации этой системы многоуровневым методом синтеза, заключающим в себе минимизацию системы и последующее ее покрытие заданными базовыми элементами, неисправности на полюсах базовых элементов полученной комбинационной схемы являются А,Б-неисправностями.
