Multiprocessor for analyzing information space. 2. Infrastructure of vector logic analysis.pdf Современный рынок электронных и информационных технологий очень нуж-дается в новых носителях больших объемов информации, эффективных структу-рах данных для хранения и поиска требуемой информации, новых интеллектуаль-ных и компьютерных средствах, точно и быстро обеспечивающих любые запросыпользователя. Современные компьютеры ориентированы в своей основе на ариф-метические вычисления, а поэтому не всегда являются эффективным инструмен-том для решения логических, ассоциативных и поисковых задач в существующемокеане информации. Поэтому актуальным представляется разработка новых спе-циализированных технологий, ориентированных на создание цифровой системына кристалле с ограниченной системой логических команд для анализа в реальноммасштабе времени больших информационных массивов, организованных в эф-фективные структуры данных. Такие информационно-ориентированные процес-соры могут поддерживать как серверную, так и клиентскую стороны компьютер-ной сети путем встраивания в системную плату или их соединения через один изпортов, например с использованием USB. Если исключить из рассмотрения ариф-метические операции, которые не свойственны человеческому мозгу, то все ре-сурсы мозгоподобного компьютера можно переориентировать на повышениемощности и производительности вычислителя для чрезвычайно большого классапроблем логического, ассоциативного анализа, распознавания образов, диагно-стирования и поиска информации.Цель данного исследования - существенное (.100) повышение быстродейст-вия процедур решения актуальных прикладных задач путем мультипроцессорнойи параллельной реализации ассоциативно-логических векторных операций дляанализа графовых и табличных структур данных в дискретном булевом простран-стве без использования арифметических операций.Для достижения цели необходимо решить задачи, связанные с разработкойвекторно-логических процесс-моделей встроенного диагностирования цифровыхсистем на кристаллах, поиска квазиоптимального покрытия, использующие сред-ства логического ассоциативного мультипроцессора, параллельные операции вы-числительных процессов и подсчета критериев качества.Источники. 1. Ассоциативно-логические структуры данных для мозгоподоб-ных вычислительных процессов [1 - 5]. 2. Мультипроцессорная аппаратная плат-форма информационно-логического анализа [6 - 9]. 3. Модели и методы дискрет-ного анализа, синтеза и диагностирования цифровых изделий [10 - 15].1. Инфраструктура векторно-логического анализаИнфраструктура - совокупность моделей, методов и средств описания, анали-за и синтеза структур данных для решения функциональных задач. Модель (сис-темная) - совокупность взаимосвязанных, определенных в пространстве и време-ни компонентов с заданной адекватностью описывающая процесс или явление ииспользуемая для достижения поставленной цели при наличии ограничений иметрики оценивания качества решения. Здесь ограничения есть аппаратурные за-траты, время разработки и производства до появления изделия на рынке (time-tomarket),подлежащие минимизации. Метрика оценивания решения при использо-вании модели определена двоичным логическим вектором в дискретном булевомпространстве. Концептуальная модель вычислительного изделия представлена со-вокупностью управляющего и операционного автоматов. Системная модельLAMP функциональности использует GALS (Global Asynhronus Local Synchronus)-технологию создания иерархических цифровых систем с локальной синхрониза-цией отдельных модулей и одновременно глобальной асинхронностью функцио-нирования всего устройства [13].В целях детализации структуры векторного процессора и секвенсора нижепредставлены аналитические и структурные процесс-модели, которые приводятсяк анализу А-матрицы по столбцам или строкам. Первая из них представлена нарис. 1 и предназначена для определения множества допустимых решений относи-тельно входного запроса mb .11[( ) ];( ).nmai b i i bni bi im m A mA m A===   ⊕= mbmaРис. 1. Поиск всех допустимых решенийВторая структура (рис. 2) осуществляет поиск оптимального решения на мно-жестве найденных в первой процессной модели путем анализа строк. Кроме того,вторая модель имеет и самостоятельное применение, ориентированное на опреде-ление однозначного и многозначного решения, например, при поиске дефектов вцифровой системе на кристалле.1 01 0( ) ( )( ) ( )ai aiai aisb m i m imb m i m im A Am A A =  = =  == =    mambmcmdРис. 2. Структура выбора оптимального решенияВсе операции, представленные в двух моделях процессов, являются вектор-ными. Процесс-модель анализа строк (см. рис. 1) формирует вектор ma - иденти-фикации допустимых mai = 1 или противоречивых mai = 0 решений относительновходного условия mb за n тактов обработки всех m-разрядных векторов таблицыA=card(mn). Качество (допустимость) решения определяется для каждоговзаимодействия входного вектора mb и строки Ai  A на блоке (девекторизации)дизъюнкции. Матрица A может быть модифицирована путем ее пересечения свходным вектором на основе использования операции1( )ni bi iA m A==  , если необ-ходимо исключить из А-таблицы все незначимые для решения координаты и век-торы, отмеченные единичными значениями вектора ma. Интересное решение длязадач диагностирования путем анализа строк таблицы, представленное на рис. 2,необходимо интерпретировать следующим образом. После выполнения диагно-стического эксперимента формируется двоичный вектор экспериментальной про-верки ma, который маскирует А-таблицу неисправностей для поиска одиночныхили кратных дефектов. Векторы mb и mc используются для накопления результа-тов выполнения операций конъюнкции и дизъюнкции. Затем осуществляется ло-гическое вычитание из первого регистра mb содержимого второго вектора mc с по-следующей записью результата в регистр md. Для реализации второго уравнения,которое формирует множественное решение, элемент and заменяется функциейor. Схема имеет также переменную выбора режима поиска решения: single илиmultiple. Процесс-модель использует в качестве входного условия вектор ma, ко-торый управляет выбором векторной операции and, or для обработки единичныхAi(mai =1)A или нулевых Ai(mai =0)A строк A-таблицы. В результате вы-полнения n тактов осуществляется накопление единичных и нулевых относи-тельно значений координат вектора ma решений в регистрах A1, A0 соответствен-но. Априори в указанные регистры заносится вектор единиц и нулей:A1=1,A0=0 . После обработки всех n строк A-таблицы за n тактов выполняетсявекторная конъюнкция содержимого регистра A1 с инверсией регистра A0 , кото-рая формирует результат в виде вектора mb, где единичные значения координатопределяют решение. При анализе таблицы неисправностей цифрового изделияединичным координатам вектора mb соответствуют столбцы, отождествляемые сномерами дефектов или неисправных блоков, подлежащих восстановлению илиремонту.Можно пойти еще дальше в части сервисного обслуживания функциональныхмодулей: на универсальной структуре системы векторного логического анализарешить оптимизационную задачу восстановления работоспособности. С помощьюминимального числа ремонтных запасных строк и/или столбцов, например, памя-ти, необходимо покрыть все обнаруженные в ячейках неисправности. Технологи-ческая и математическая культура векторной логики в данном случае предлагаетпростое и интересное схемотехническое решение для получения квазиоптималь-ного покрытия, рис. 3. Преимущества: 1) Вычислительная сложность процедуры:Z = n векторных операций, равное числу строк таблицы. 2) Минимум аппаратныхзатрат: таблица и два вектора mb, ma - для хранения промежуточных покрытий инакопления результата в виде единичных координат, соответствующих строкамтаблицы, которые составляют квазиоптимальное покрытие. 3) Отсутствие класси-ческого деления задачи покрытия на поиск ядра покрытия и дополнения. 4) От-сутствие сложных процедур манипулирования ячейками строк и столбцов. Недос-таток - получение не всегда оптимального покрытия, что является платой за тех-нологичность векторной процедуры, представленной на рис. 3.1( );[( ) ].b b inai i b i bm m Am m A m==  ⎧⎪⎨=    ⎪⎩mambРис. 3. Процесс-модель поиска квазиоптимального покрытияЗдесь имеется операция девекторизации, которая на последнем этапепревращает векторный результат в бит mai вектора ma по функции ormai = [(mb Ai ) mb ] . В общем случае операция девекторизации в алгебре век-торных операций записывается в виде :Ai,m,(mAi). Обратная процедура - векторизация есть конкатенация бу-левых переменных: ( , , , , , , , ) a m a b c d e f g h . В процедуре поиска покрытия априоривекторы mb=0,ma=0 обнуляются. Квазиоптимальное покрытие накапливаетсяза n тактов в векторе ma путем последовательного сдвига. Биты, заносимые в ре-гистр ma, формируются схемой or, которая выполняет девекторизацию, путеманализа входного полученного результата [(mbAi)mb] на присутствие единиц.Следующий пример интересен функциональной законченностью цикла диаг-ностирования, когда после получения квазиоптимального покрытия данная ин-формация используется для восстановления работоспособности дефектных ячеекпамяти [9]. Размерность модуля памяти - 13.15 ячеек не влияет на вычислитель-ную сложность получения покрытия десяти дефектных ячеек с помощью резерв-ных строк (2) и столбцов (5) (рис. 4).1 . . . . . 1 . . .. . . 1 . . . . 1 .. 1 . . 1 . . 1 . .. . . . . . . . . 1. . 1 . . 1 . . . .1 1 1 . . . . . . .. . . 1 . . . . . .. . . . 1 1 . . . .. . . . . . 1 . . .. . . . . . . 1 . .. . . . . . . . 1 1Рис. 4. Модуль памяти с резервом и таблица покрытияДля решения оптимизационной задачи выполняется построение таблицы по-крытия (см. рис. 10) неисправных ячеек, которая имеет строки - резервные ресур-сы для покрытия дефектов: 2 3 5 7 8 2 (С ,С ,С ,С ,С ,С ,R2,R4,R5,R7,R8,R9), а столбцыпредставляют собой дефекты ячеек:(F2,2,F2,5,F2,8,F4,3,F5,5,F5,8,F7,2,F8,5,F9,3,F9,7),подлежащие ремонту. Здесь столбцы соответствуют координатам дефектных яче-ек, а строки идентифицируют резервные компоненты (строки и столбцы), которыемогут восстановить работоспособность неисправных координат. Процесс-модель,рис. 2, дает возможность получить оптимальное решение в видеma = 1 1 1 1 1 0 0 0 0 0 0 ,которому соответствует покрытиеR={C2,C3,C5,C7,C8}как одно из трехR=C2,C3,C5,C7,C8C2,C3,C5,C8,R9C2,C5,C8,R4,R9возможных минимальных решений для таблицы неисправностей. Технологиче-ская модель встроенного диагностирования и ремонта памяти представлена нарис. 5. Она имеет четыре компонента: 1) Testing - тестирование модуля (UUT -Unit Under Test) с использованием эталонной модели (MUT - Model Under Test)для формирования вектора экспериментальной проверки ma, размерность которо-го соответствует числу тестовых наборов. 2) Diagnosis - поиск дефектов на основеанализа таблицы неисправностей A. 3) Optimization - оптимизация покрытия де-фектных ячеек ремонтными строками и столбцами на основе анализа таблицы A.4) Repairing - восстановление работоспособности памяти путем замены адресов(AD - Address Decoder) неисправных строк и столбцов, представленных векторомma , на адреса компонентов из ремонтного запаса SM - Spare Memory [9].mambmcmdmamb mbРис. 5. Модель встроенного тестированияи восстановления памятиПроцесс-модель встроенного сервисного обслуживания работает в реальноммасштабе времени и позволяет поддерживать в работоспособном состоянии, безвмешательства человека, цифровую систему на кристалле, что является интерес-ным решением для критических технологий, связанных с дистанционной эксплуа-тацией изделия.Предложенные процесс-модели анализа (графа) ассоциативных таблиц, а так-же введенные критерии качества логических решений позволяют решать задачиквазиоптимального покрытия, диагностирования дефектов программных и/илиаппаратных блоков. Модель векторных вычислений послужила основой для раз-работки специализированной мультипроцессорной архитектуры, ориентирован-ной на поиск, распознавание и принятие решений на использовании структур ас-социативных таблиц.ЗаключениеСуществующие программные аналоги не предлагают чисто ассоциативно-логических маршрутов поиска, распознавания и принятия решений в дискретноминформационном пространстве [4, 5, 15]. Практически все они используют уни-версальную систему команд современного дорогостоящего процессора с матема-тическим сопроцессором. Кроме того, аппаратные специализированные средствалогического анализа, которые могут выступать прототипами [1, 6, 7], как правило,ориентированы на побитовую или невекторную обработку информации.Для устранения недостатков программных аналогов и аппаратных прототиповв работе предложен новый подход векторно-логической обработки ассоциатив-ных данных с полным исключением арифметических операций, влияющих на бы-стродействие и аппаратную сложность, который оказался удачно реализуемым наоснове использования современной микроэлектронной аппаратуры в виде муль-типроцессорной цифровой системы на кристалле.Фактическая реализация подхода основывается на предложении инфраструк-туры, которая включает следующие компоненты: 1. Процесс-модели анализа ас-социативных таблиц на основе использования векторных логических операцийдля поиска, распознавания образов, принятия и оценивания решений в векторномдискретном булевом пространстве. Модели ориентированы на достижение высо-кого быстродействия параллельного векторного логического анализа информациии подсчета критериев качества решения. 2. Мультипроцессорная архитектура па-раллельного решения ассоциативно-логических задач с минимальным множест-вом векторных логических операций и полным исключением арифметическихкоманд, что обеспечивает высокое быстродействие, минимальную стоимость инезначительное энергопотребление LAMP, имплементированного в кристалл про-граммируемой логики. 3. Новые векторно-логические процесс-модели встроенно-го диагностирования цифровых систем на кристаллах, поиска квазиоптимальногопокрытия, использующие средства логического ассоциативного мультипроцессо-ра, параллельные операции вычислительных процессов и подсчета критериев ка-чества.Достоверность и практическая значимость полученных результатов подтвер-ждается созданием инфраструктуры мультипроцессора для диагностирования ивосстановления работоспособности компонентов памяти в цифровой системе накристалле. Дальнейшие исследования направлены на разработку прототипа логи-ческого ассоциативного мультипроцессора в целях решения актуальных задач по-иска, распознавания и принятия решений с помощью предложенной инфраструк-туры векторного логического анализа.Статья является продолжением работы [16].

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