Partial restoration of descreet systems with random access.pdf Широкое распространение микропроцессорной техники породило настоятельную потребность в создании цифровых микросхем. Наряду с технологическими и физическими од­ ним из методов повышения качества микросхем является вве­ дение в них аппаратной избыточности, которая бы позволя­ ла устройству функционировать даже в случае отказа неко­ торых из его составных частей. Отказоустойчивые системы подобного рода делятся на два класса: системы с полным сохранением функциональных воз­ можностей и системы с частичным сохранением функциона­ льных возможностей устройства Системы с полным сохране­ нием используют резервирование и, как правило, имеют зна­ чительную аппаратную избыточность. В ряде случаев можно сократить аппаратную избыточность, ограничившись частич­ ным сохранением функциональных возможностей устройства В данной работе рассматривается метод построения от­ казоустойчивых систем с произвольным доступом с частич­ ным сохранением функциональных возможностей. К систе­ мам с произвольным доступом отнесем класс устройств, включающих в себя набор однородных элементов (элемен­ тов, выполняющих одинаковые функции) и поддерживаю­ щих возможность использования каждого из них в произ­ вольном порядке. Для этого каждый из таких элементов должен характеризоваться своим уникальным номером или адресом. Множество адресов элементов, входящих в состав устройства, назовем полным адресным пространством этого устройства. В современных электронных устройствах адрес представляет собой двоичный вектор длины п, тогда адрес­ ное пространство есть булево пространство размерности п. Предположим, что часть элементов, входящих в состав устройства, неисправны. Вид конкретной неисправности знзг чения не имеет. Поставим задачу восстановления частичной работоспособности устройства с использованием элементов, оставшихся исправными. Предлагаемый способ восстановле­ ния заключается в выборе нового адресного пространства меньшей размерности, такого, чтобы адресам из него соответ­ ствовали адреса исправных элементов из полного адресного пространства Новое адресное пространство назовем сокращен­ ным адресным пространством. Соответствие между элемен­ тами адресных пространств обеспечивается специальным ком­ бинационным устройством, по возможности меньшей слож­ ности. Сложность дополнительного устройства будем оцени­ вать числом конъюнкций реализуемой им системы ДНФ. Основные определения Соответствие между со 1 фащенным (А) и полным (В) адресными пространствами можно задать в виде отно­ шения Р со следующими свойствами: APB=>'iae.A 3 единственный Ь&В и biE, где Е - множество адресов полного адресного пространства, соответствующих неисправным элементам устройства. Различным элемен­ там из А соответствуют различные элементы из В. Непосредственное задание отношения в виде мно­ жества пар элементов громоздко. Можно упростить запись отношения, если в качестве элементов отноше­ ния использовать целые подмножества адресов, за­ данные непересекающимися интервалами в булевых пространствах различной размерности: АРВ^сот иfeA,TT и^еВ &и^г\Е=0, (1) где и f ,и* - равномощные интервалы. Различным ин­ тервалам из А соответствуют различные интервалы из В. Интервалы Uj,Uf удобно представлять в виде троичных векторов а ^ , а *. Если компонентам век­ торов сокращенного адресного пространства поста­ вить в соответствие символы входных переменных, а компонентам векторов полного адресного простран­ ства - значения функций, то по отношению Р можно построить систему F={f^ из и булевых фун­ кций от т переменных, где ш и и - размерности со­ кращенного и полного адресных пространств соответ­ ственно. При этом й/ будет описывать конъюнкцию входных переменных, а а * - вхождение этой конъ­ юнкции в функции системы. Конъюнкции системы F попарно ортогональны. Может быть выбрано несколько различных отноще- ний Р между сокращенным и полным адресными про­ странствами. Возникает задача выбора лучшего в том или ином смысле. Уточнить понятие качества решения можно, конкретизировав базис, в котором предлагается реализовать дополнительное комбинационное устройся во, обеспечивающее частичное сохранение работоспо­ собности системы с произвольным доступом. В данной работе в качестве базиса синтеза выбраны гфограмми- руемые логические матрицы (ПЛМ). ПЛМ характеризу­ ется тройкой (s, /, q), где s - число входов ПЛМ, t - чис­ ло выходов, q - число промежуточных шин. Число входов и выходов определяются размерностями сокращенного и полного адресных пространств, и не мо­ гут быть изменены. Число щэомежуточных щин зависит от числа конъюнкций в системе функций F, которое оп­ ределяется числом пар интервалов в отношении Р. По­ этому в качестве критерия оптимальности отношения вы­ брано число пар интервалов, образующих отношение Р. Два множества непересекающихся интервалов назо­ вем сопоставимыми, если любому интервалу из одного множества можно взаимооднозначно сопоставить ин­ тервал такой же мощности из другого множества. Задача поиска минимального отношения состоит в том, чтобы получить два сопоставимых множества интервалов, со­ держащих минимальное количество элементов: при этом одна система является разбиением сокращенного адресного пространства, а другая не содержит элементов множества Е в полном адресном тфостранстве. Дихотомическое дерево - двоичное дерево, в кото­ ром из каждой неконцевой вершины исходит два реб­ ра. Пусть дано дихотомическое дерево с / концевыми вершинами. Каждому ярусу дерева сопоставим компо­ ненту троичного вектора, а ребра пометим символами О и 1. В результате каждый путь из корня в концевую вершину будет представлен троичным вектором. В нем компоненты, сопоставленные вершинам пути, прини­ мают определенные значения О, 1 согласно пометкам ребер, составляющих путь. Неупомянутым среди вер­ шин пути компонентам сопоставляется неопределен­ ное значение. Дерево в целом будет содержать / таких троичных векторов. Это множество образовано орто­ гональными интервалами и является разбиением буле­ ва пространства на подмножества. Будем говорить, что полученное множество интервалов несомо деревом. Если некоторое множество непересекающихся ин­ тервалов С сопоставимо множеству интервалов Д не­ сомому дихотомическим деревом R, то будем говорить, что множество интервалов С сопоставимо дереву R. Два дихотомических дерева будем считать эквива­ лентными, если они содержат одинаковое число ярусов и одинаковое число концевых вершин на каждом ярусе. Дихотомическое дерево, ребра и вершины которого не помечены, будем называть неразмеченным дихотомиче­ ским деревом. Каждой концевой вершине этого дерева сопоставим 2* ”' элементов булева пространства, где г - число ребер простой цепи, соединяющей концевую вер­ шину с корнем дерева, & к- размерность булева прост­ ранства. Будем считать, что подмножества, сопоставляемые различным концевым вершинам, не пересекаются. Вну­ тренней вершине непомеченного дихотомического де­ рева сопоставляется подмножество элементов булева пространства, полученное объединением подмножеств подчиненных вершин соседнего яруса. Известно, что любой интервал в булевом простра­ нстве содержит 2* ■ элементов булева пространства, где г - ранг интервала. В булевом пространстве мож­ но выделять подмножества из 2*" элементов, не яв­ ляющихся интервалами. В дальнейшем такие под­ множества будем называть неинтервальными подмно­ жествами ранга г. Для представления таких подмно­ жеств требуется от двух до 2 * троичных векторов. Интервальные разбиения булева пространства Разбиение булева пространства на интервалы бу­ дем называть интервальным разбиением. Утверждение 1. Интервальное разбиение Т булева пространства представимо неразмеченным дихотоми­ ческим деревом. Доказательство. Мощность каждого интервала ю Т есть степень двойки. Выберем из Т подмножество ин­ тервалов минимальной мощности. Обозначим число элементов в каждом интервале через 2", т

Скачать электронную версию публикации