Автор неизвестен - Информация, язык, интеллект - страница 82

Страницы:
1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25  26  27  28  29  30  31  32  33  34  35  36  37  38  39  40  41  42  43  44  45  46  47  48  49  50  51  52  53  54  55  56  57  58  59  60  61  62  63  64  65  66  67  68  69  70  71  72  73  74  75  76  77  78  79  80  81  82  83  84  85  86  87  88  89  90  91  92  93  94  95  96  97  98  99  100  101  102  103  104  105  106  107  108  109  110  111  112  113  114  115  116  117  118  119  120  121  122 

n

использования операции A = (mb л A), если необ-

i        b i =1 i

ходимо исключить из А-таблицы все незначимые для решения координаты и векторы, отмеченные единичными значениями в ma.

Интересное решение для задач диагностирова­ния путем анализа строк таблицы, представленное на рис. 8, необходимо интерпретировать следую­щим образом.

После выполнения диагностического экспери­мента формируется двоичный вектор эксперимен­тальной проверки ma, который маскирует А-таб-лицу неисправностей для поиска одиночных или кратных дефектов. Векторы mb и mc используются для накопления результатов выполнения операций конъюнкции и дизъюнкции. Затем осуществляет-

Можно пойти еще дальше в части сервисного обслуживания функциональных модулей: на уни­версальной структуре системы векторного логи­ческого анализа решить оптимизационную задачу восстановления работоспособности. С помощью минимального числа ремонтных запасных строк и/ или столбцов, например, памяти, необходимо пок­рыть все обнаруженные в ячейках неисправности. Технологическая и математическая культура век­торной логики в данном случае предлагает простое и интересное схемотехническое решение для полу­чения квазиоптимального покрытия, представлен­ное на рис. 9. Преимущества: 1) Вычислительная сложность процедуры: Z = n векторных операций, равное числу строк таблицы. 2) Минимум аппа­ратных затрат: таблица и два вектора mb, ma — для хранения промежуточных покрытий и накопле­ния результата в виде единичных координат, со­ответствующих строкам таблицы, которые состав­ляют квазиоптимальное покрытие. 3) Отсутствие классического деления задачи покрытия на поиск ядра покрытия и дополнения. 4) Отсутствие слож­ных процедур манипулирования ячейками строк и столбцов. Недостаток — получение квазиопти­мального покрытия, что является платой за техно­логичность векторной процедуры, представленной на рис. 9.

убывания. Вычислительная сложность процедуры равна

Z   1 2 2

где n — число строк таблицы покрытия. Процесс-модель упорядочения векторов таблицы покрытия по убыванию количества единиц изображена на рис. 10.
Рис. 9. Процесс-модель поиска квазиоптимального покрытия

Здесь имеется операция девекторизации, ко­торая на последнем этапе превращает вектор­ный результат в бит mai вектора по функции or mai =v[(mb v A) л mb ]. В общем случае операция девекторизации в алгебре векторных операций за­писывается в виде <бинарная операция><вектор>: vA, л m, л (m v A). Обратная процедура — векто­ризация есть конкатенация булевых переменных: ma (a,b,c,d,e, f, g,h).

В процедуре поиска покрытия априори векто­ры mb = 0, ma = 0 обнуляются. Квазиоптимальное покрытие накапливается за n тактов в векторе ma путем последовательного сдвига. Биты, заносимые в регистр ma, формируются схемой or, которая вы­полняет дефекторизацию, путем анализа входного полученного результата [(mb v Ai) л mb ] на присутс­твие единиц.


Эффективность процедуры иллюстрируется поиском покрытия единицами строк всех столб­цов, имеющих хотя бы одну единицу. Для матрицы покрытия, представленной в форме:

применение векторной процедуры поиска квази­оптимального покрытия дает следующий результат: P = {А1,А2,А3,А5}. Оптимальное покрытие для дан­ной таблицы имеет на одну строку меньше:

P = А А4, As}.

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

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

Таким образом, встроенная система диагнос­тирования и ремонта функциональных блоков цифровой системы на кристалле имеет следующие стадии аппаратной поддержки: 1) Тестирование цифрового изделия. 2) Поиск всех допустимых решений дефектных блоков и выбор оптималь­ного варианта. 3) Оптимизация числа ремонтных модулей для восстановления работоспособности цифрового изделия. 4) Ремонт цифровой системы на кристалле путем адресной замены неисправных компонентов.

Следующий пример интересен функциональ­ной законченностью цикла диагностирования, когда после получения квазиоптимального пок­рытия данная информация используется для вос­становления работоспособности дефектных ячеек памяти. Размерность модуля памяти — 13х15 ячеек не влияет на вычислительную сложность получе­ния покрытия десяти дефектных ячеек с помощью резервных строк (2) и столбцов (5) (рис. 11).
Для решения оптимизационной задачи выпол­няется построение таблицы покрытия неисправ­ных ячеек, которая имеет следующий вид:

Здесь столбцы соответствуют координатам де­фектных ячеек, а строки идентифицируют резерв­ные компоненты (строки и столбцы), которые мо­гут восстановить работоспособность неисправных координат. Применение вычислительной процесс-модели, представленной на рис. 8, дает возмож­ность получить оптимальное решение в виде векто­ра ma = |11111000000|. Данному вектору ставится в соответствие оптимальное пок­рытие: R = {X1, X2, X3, X4, X5} = {C2,C3,Cs,C7,C8}, которое является одним из трех R = X1X2X3X4X5 vX1X2X3X5Xn v X1X3X5X7Xn воз­можных минимальных решений для приведенной выше таблицы неисправностей. Технологическая структурная модель встроенного диагностиро­вания и ремонта памяти представлена на рис. 12. Она имеет четыре стадии: 1) Testing — тестирова­ние модуля памяти (UUT Unit Under Test) с ис­пользованием эталонной модели (MUT Model Under Test) для формирования вектора экспери­ментальной проверки ma, размерность которого соответствует числу тестовых наборов. 2) Diagnosis — поиск дефектов на основе анализа таблицы неис­правностей A в соответствии с процесс-моделью, представленной на рис. 8. 3) Optimization — опти­мизация покрытия дефектных ячеек ремонтными строками и столбцами на основе анализа таблицы A в соответствии с процесс-моделью, представлен­ной на рис. 9. 4) Repairing — восстановление рабо­тоспособности модуля памяти путем замены адре­сов (AD Address Decoder) неисправных строк и столбцов, представленных вектором ma, на адре­са компонентов из ремонтного запаса SM Spare Memory.

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

Исходя из описанных выше процесс-моделей анализа данных можно предложить относительно универсальную структуру секвенсора (рис. 13), как компонента логического ассоциативного муль­типроцессора, который включает: 1) Логический процессор (LP), имеющий 5 базовых операций. 2) Ассоциативную память в виде A-матрицы для параллельного выполнения базовых операций. 4) Блок векторов m, предназначенный для параллель­ного обслуживания строк и столбцов А-матрицы, а также обмена данными в процессе вычислений. 5) Память прямого доступа (CM), сохраняющую команды программы обработки информации. 6) Устройство или автомат (CU), управляющий вы­полнением логических операций. 7) Интерфейс (I), осуществляющий связь секвенсора с другими элементами и устройствами мультипроцессора.
Логический процессор (LP) (рис. 14) осущест­вляет выполнение пяти операций (and, or not, xor,


shift left bit crowding), которые являются базой для создания алгоритмов и процедур информаци­онного поиска и оценивания решения. Модуль LP имеет мультиплексор на входе для выбора одного из четырех операндов, который подается на один из выбранных логических элементов, выполняющий векторную операцию. Сформированный результат через мультиплексор (элемент or) заносится в один из четырех операндов, который выбирается соот­ветствующим адресом.


Особенности реализации логического процес­сора заключаются в наличии трех бинарных (and, or, xor) и двух унарных (not, slc) операций. Послед­ние можно присоединять к такту обработки регис­тровых данных путем выбора одной из трех опера­ций (not, slc, nop — нет операции). Для повышения эффективности работы логического устройства вводятся два элемента с пустой операцией. Если, например, необходимо выполнить только унарную операцию, то на уровне (слое) бинарных команд следует выбрать nop, что практически означает пе­редачу данных через проводник (повторитель) ко второму уровню унарных операций. Все операции в LP — регистровые или регистрово-матричные. Пос­ледние предназначены для анализа вектор-строк таблицы при использовании входного m-вектора как запроса для точного поиска информации.

{ma ,mb ,mc ,я% }ДА; 4{ma ,mb ,mc ,md }Д{/т m ,mc ,md}; {not, nop, slc}{ma ,mb ,mc ,md, Ai}. Д = {and,or, xor}.

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

Logic Block Utilization:

Number of 4 input LUTs: 400 out of 9,312 4%

Logic Distribution:

Number of occupied Slices: 200 out of 4,656 4% Number of Slices only related logic: 200 out of 200 100 % Total Number of 4 input LUTs: 400 out of 9,312 4% Number of bonded IOBs: 88 out of 320 29% Total equivalent gate count for design: 2400 Тактовая частота выполнения регистровой опе­рации в кристалле Virtex 4, Xilinx, равна 100МГц, что на порядок выше, чем реализация аналогич­ных процедур на универсальном компьютере с час­тотой 1ГГц.

Выводы

Научная новизна представлена новыми про­цесс-моделями анализа табличных форм задания информации на основе использования векторных логических операций для решения задач поис­ка, диагностирования, распознавания образов и принятия решений в векторном дискретном бу­левом пространстве. Модели ориентированы на достижение высокого быстродействия процедур параллельного векторного логического анализа информации, в пределе полностью исключающего использование арифметических операций, в том числе и для подсчета критерия качества решения. Разработаны новые методы и алгоритмы решения задач диагностирования цифровых изделий, на­хождения квазиоптимального покрытия, исполь­зующие векторные операции для параллельного выполнения вычислительных процессов и подсче­та критериев качества.

Практическая значимость заключается в ори­ентации предложенных процесс-моделей, ис­пользующих векторные операции, для анализа ассоциативных таблиц на основе логического мультипроцессора с ограниченной системой ко­манд, обеспечивающей высокое быстродействие параллельной обработки больших массивов ин­формации, представленных в общем случае гра­фовыми структурами ассоциативных матриц или таблиц. Дальнейшие исследования будут направ­лены на разработку прототипа мультипроцессора в целях решения актуальных практических задач с помощью предложенной инфраструктуры вектор­ных логических операций.Список литературы: 1. Zorian Y. Test Strategies for System-in-Package / Y. Zorian // Plenary Paper of IEEE East-West Design & Test Symposium (EWDTS'08). Lviv, Ukraine.

2008. 2. Smith L. 3D Packaging Applications, Requirements, Infrastructure and Technologies / L. Smith // Fourth Annual International Wafer-Level Packaging Conference. San Jose, California. September, 2007. 3. The next Step in Assembly and Packaging: System Level Integration in the package (SiP) / Editors: William Chen, W. R. Bottoms, Klaus Pressel, Juergen Wolf // SiP White Paper. International Technology Roadmap for Semiconductors. — 2007. —Р. 17-23. 4. А.с. №1439682. 22.07.88. Регистр сдвига / Какурин Н.Я., Хаханов В.И., Лобода В.Г., Какурина А.Н. — 4с. 5. Бондаренко М.Ф. О мозгоподобных ЭВМ / М.Ф. Бондаренко, З.В. Дударь, И.А. Ефимова, В.А. Лещинский, С.Ю. Шабанов—Куш-наренко // Радиоэлектроника и информатика.—Харьков: ХНУРЭ. — 2004, № 2. — С. 89—105. 6. Бондаренко М.Ф. Об алгебре предикатов / М.Ф. Бондаренко, Ю.П. Ша-банов—Кушнаренко // Бионика интеллекта. — Харьков: ХНУРЭ. — 2004, № 1. — С. 15—26. 7. Бондаренко М.Ф. Теория интеллекта. Учебник. / М.Ф. Бондаренко, Ю.П. Шабанов—Кушнаренко; Харьков: СМИТ. — 2006. — 592 с. 8. Бондаренко М.Ф. Модели языка / М.Ф. Бондаренко, Ю.П. Шабанов—Кушнаренко // Бионика интеллекта.

Страницы:
1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25  26  27  28  29  30  31  32  33  34  35  36  37  38  39  40  41  42  43  44  45  46  47  48  49  50  51  52  53  54  55  56  57  58  59  60  61  62  63  64  65  66  67  68  69  70  71  72  73  74  75  76  77  78  79  80  81  82  83  84  85  86  87  88  89  90  91  92  93  94  95  96  97  98  99  100  101  102  103  104  105  106  107  108  109  110  111  112  113  114  115  116  117  118  119  120  121  122 


Похожие статьи

Автор неизвестен - 13 самых важных уроков библии

Автор неизвестен - Беседы на книгу бытие

Автор неизвестен - Беседы на шестоднев

Автор неизвестен - Богословие

Автор неизвестен - Божественность христа