Geum.ru
   Авторефераты по темам  >>  Разные специальности - [часть 1]  [часть 2]

МЕТОДЫ, АЛГОРИТМЫ И УСТРОЙСТВО СОПОСТАВЛЕНИЯ ПО ОБРАЗЦУ

Автореферат кандидатской диссертации

 

На правах рукописи

исицин а

еонид Александрович

МЕТОДЫ, АЛГОРИТМЫ И УСТРОЙСТВО

СОПОСТАВЛЕНИЯ ПО ОБРАЗЦУ

Специальность 05.13.05 - Элементы и устройства

вычислительной техники и систем ауправления

 

АВТОРЕФЕРАТ

диссертации на соискание ученой степени

кандидата технических наук

Курск а2009


Работа выполнена в ГОУ ВПО

Курский государственный технический университет

Научный руководитель:а аадоктор технических наук, профессор

Довгаль Виктор Митрофанович

Официальные оппоненты: доктор технических наук, с.н.с.

А.А. Бурмака

кандидат технических наук

В.В.Елагин

Ведущая организация:аа аКурский государственный университет

Защита состоится а8 июня 2009 г. в 1600 часов на заседании диснсертационного совета Д 212.105.02 при Курском государственном технинческом университете по адресу: 305040, г. Курск, ул. 50 лет Октября, 94 (конференц-зал).

Заверенные отзывы на автореферат в двух экземплярах направлять по адресу: 305040, г. Курск, ул. 50 лет Октября, 94, ученому секретарю.

С диссертацией можно ознакомиться в библиотеке университета.

Автореферат разослан 7маяаа 2009 г.

Ученый секретарь совета по защите докторских

и кандидатских диссертаций Д212.105.02,

кандидат технических наукаа Титенко Е.А.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность работы. Современный этап развития вычислительной техники характеризуется повышенным вниманием к созданию аппаратных средств для обработки символьной информации (ОСИ). Особую значимость приобретает создание средств быстрых символьных вычислений, поскольку они занимают до 98% временного ресурса в современных системах обработки и передачи данных. Доминирующее положение в системах ОСИ занимает процедура поиска по образцу, называемая операцией сопоставления.а При быстром росте аобъемов обрабатываемых данных операция сопоставления по частоте использования является лидирующей. Действительно, все алгоритмы ОСИ, функционирующие на основе формул подстановок и продукций, системы ситуационного управления, все грамматики и распознающие автоматы, системы обработки знаний и языков, криптография, а также поисковые машиныа компьютерных сетей аосновываются на сопоставлении как анеотъемлемой составляющей этого класса массовых символьных вычислений.

Важность и массовость операции сопоставления отражена в научных трудах высших авторитетов в истории вычислительной техники А. Тьюринга, А. Черча, А.А. Маркова, А.Н. Колмогорова, D.E. Knuth, (Jr) J.H. Morris, V.R. Pratt, R.S. Boyer, J.S. Moore аи многих других отечественных и зарубежных исследователей.

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

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

Работа выполнялась в рамках агосбюджетных НИР кафедры программного обеспечения вычислительной техники Курского государственного технического университета, аа также по гранту А04-3.16-695 Федерального агентства по образованию Методы акселерации работы продукций и символьные мультипроцессоры автоматизированных систем ситуационного управления при участии автора данной диссертационной работы. а

Объекта исследования - процессы обработки символьной информации.

Предмет исследования - процессы сопоставления (поиск по образцу).

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

Основные задачи диссертационного исследования:

1. Осуществить анализ методов, алгоритмов и устройств ОСИ для определения частотного показателя операции сопоставления.

2. Создать методы и алгоритмы для высокоскоростной реализации операции сопоставления и исследовать их временную сложность.

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

4. Выполнить экспериментальное исследование характеристик устройств.

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

Научная новизна. В результате проведенных теоретических исследований получены следуюнщие основные научные результаты:

1. Созданы новые методы сопоставления, осуществлена их алгоритмизация и исследована временная сложность последовательных, конвейерных, параллельных (ассоциативных) и матричных алгоритмов сопоставления. Выведены аналитические зависимости временной сложности алгоритмов от структурно-лингвистических характеристик образцов и обрабатываемых слов.

2. Установлено, что существенное снижение временной сложности по отношению к аналогам соотноситсяа с аассоциативным алгоритмом, а также с матричным алгоритмом, что служит основанием для их аппаратной поддержки.

3. Впервые разработана структурно-функциональная организация устройства, ареализующего аматричный алгоритм сопоставления (матричное устройство, патент № 72771 РФ), отличающегося тем, что в нем впервые применяетсяа безотступная параллельная технология сопоставления, обеспечивающая высокие скоростные преимущества по отношению к аналогам, открывающие пути их эффективного применения в акачестве перспективных символьных спецпроцессоров-акселераторов серверов и поисковых машин.

Практическая ценность работы состоит в следующем:

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

2.а Разработанные методы аксенлерации операции сопоставления и схемотехнические решения устройств сопоставления дают необходимые основания для постановки НИОКР по разработке специализированных устройств-акселераторов сопоставления различной конфигурации, назначенния и массового применения.

3. Проведенные экспериментальные исследования скоростных и аппаратных ахарактеристик устройств позволили получить зависимости скорости их работы от структурно-лингвистических особенностей образцов и обрабатываемых слов, что позволяет определить как целесообразность, так и сферы применения разработанных средств сопоставления для решения специфических и разноплановых задач символьных вычислений. Матричное устройство имеет 54 кратное скоростное преимущество по отношению к эталонному компьютеру с неймановской архитектурой. Скоростное преимущество матричного устройства по отношению к параллельному (ассоциативному) составляет 15 раз при сопоставимых аппаратных затратах.

Реализация результатов работы. Результаты диссертационной рабонты нашли применение в учебном процессе Курского государственного технического университета на кафедре программного обеспечения вычислительной техники, а также внедрены в ООО Раскат (г.Курск) для акселерации процессов поиска в БД.

Апробация работы. Основные научныеа результаты работы докладывались и обсужданлись на VII Всероссийской научно-технической конференции Теоретические и прикладные вопросы современных информационных технологий

(г. Улан-Удэ, 2006), VIII Международном симпозиуме Интеллектуальные системы (INTELSТ2008) (г. Н.Новгород, 2008), а также на НТС кафедры программного обеспечения КурскГТУ.

Основные положения, выносимые на защиту:

1. Безотступные методы и алгоритмы сопоставления с образцом, основанные на последовательном, конвейерном и параллельных методах поиска.

2. Матричное устройство безотступного параллельного сопоставления и его структурно-функциональная организация. а

3. Результаты экспериментальных исследований скоростных ахарактеристик и аппаратных затрат разработанных устройств сопоставления.

Публикации по работе. По результатам выполненных разработок и исследований опубликованы 4 печатные работы, в том числе 1 по аПеречню центральных рецензируемых журналов и изданий, рекомендуемых ВАК Министерства образования и науки РФ, а также получен патент № 72771 РФ .

ичный вклад. В работах, написанных в соавторстве, лично автором диссертации в [1] аметод быстрого поиска при символьных вычислениях в системах принятия решений, в частности в машинах вывода экспертных систем [2]. аВ а[3] предложен алгоритм ассоциативного поиска сопоставления, в [4]а матричный алгоритм параллельного поиска по образцу, а ва [5] разработано схемотехническое решение матричного устройства сопоставления.

Структура и объём работы. Диссертация состоит из введения, четырех глав и заключения, изложенных на 122 страницах машинописного текста, содержит 32 рисунка, 8 таблиц, список литературы из 65 наименований иа 5а приложений объемом в а45 страниц.

ОСНОВНОЕ СОДЕРЖАНИЕ ДИССЕРТАЦИОННОЙ РАБОТЫ

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

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

Анализ типовых задач обработки символьной информации приводит к тому, что все типовые задачи символьных вычислений, имеющих первостепенное практическое значение редуцируются к операции сопоставления, от скорости выполнения которой непосредственно зависит время решения задачи в целом или отклика системы. Частота использования операции сопоставления (частотный показатель) достигает 80-85% от общего временного ресурса при осуществлении символьных вычислений.

Установлено, что при реализации символьных вычислений на различных аппаратных платформах во всем многообразии архитектур осуществления символьных вычислений, включая неймановскую архитектуру, используется широкий спектр алгоритмов выполнения операции сопоставления. При этом в основном используется программная поддержка КМП-алгоритма и алгоритма Бойера Мура, в микропроцессоре символьного компьютера Facom Alpha фирмы Fujitsu применяется программно-аппаратная реализация КМП-алгоритма, а в системе OPS-5 выполнена аппаратная поддержка операции сопоставленияа с анализируемой глубиной отступа. Установлено, что сопоставление является доминирующей операцией при обработке строк и списков, изображений и аудиофайлов на современных компьютерах и вычислительных системах. При этом разметка позиций вхождения образцов специальными символами-указателями,а осуществляемая устройствами сопоставления, приводит к существенным искажениям обрабатываемого слова и созданию мусора. Это обстоятельство требует введения дополнительных аппаратных средств при согласовании структуры данных с другими процессорами или типовыми устройствами вычислительной техники, в частности часто используются специальные аппаратные и/или программные сборщики мусора.

В символьных компьютерах, которые аппаратно поддерживают известные языки ОСИ (Лисп: Zeta Lisp, Common Lisp, Interнlisp; Пролог и другие), основное внимание уделяется повышению скорости выполнения типовых операций названных языков. При этом сопоставление, входящее в типовые операции, не выделяется в отдельную категориальную единицу и под нее не выделяется специальный аппаратный ресурс, что приводит к снижению скорости решения практически важных задач ОСИ. Этим, в частности, объясняется появление многообразия версий языка Лисп, как и других языков символьных вычислений (например, аСнобол).

Получившие в последнее время широкое распространение многоядерные вычислители не достигают существенныха скоростных преимуществ при выпол-нении символьных вычислений на том основании, что операция сопоставления в них реализуется, как правило, на программном уровне. В них преимущественно используются алгоритмы Бойера Мураа или его модификации, а иногда СДВИГ-И.

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

Изложенные материалы апервой главы дают основания для заключения о том, что решена первая задача диссертации.

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

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

Ва главе выполнен структурно-лингвистический анализ образцов, а также исследование влияния структуры образца на скорость и корректность протекания конструктивных процессов сопоставления.

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

Рассмотрим два произвольных слова V и W в виде цепочек символов:

v1v2v3Еvn-2vn-1vn;а аа аа(1)

w1w2w3Еwn-2wn-1wn;а а (2)

где viIА, для i = 1, n, wj I А, для j = 1, m,а А - рабочий алфавит.

Пусть W Ч это образец, V Ч обрабатываемое слово, в котором требуется найти вхождение образцаа W.

Если исключить случай, когда длина m образца больше длины n обрабантываемого слова (при этом результат сопоставления является изначально ложным), то последовательный разработанный нами алгоритм сопоставления имеет вид:

  • указатель на текущую букву обрабатываемого словаа i:=l, указатель на текущий символ образца j:=l;
  • если i ? n и j ? m, где n - длина обрабатываемого слова, m - длина образца, тогда после выполнения условия равенства букв vi и wj осуществляется переход к сравнению следующих букв (i:=i+l, j:=j+l);
  • при неравенстве vi и wj: побуквенное сопоставление слов начинается с первой буквы образца (j:=l) и текущей буквы слова;
  • алгоритм завершает работу с результатом вхождение обнаружено в позиции (i-j+l) слова V при истинности условия j > m или с результатом вхожденние не обнаружено при выполнении условия i > n.

Представленный алгоритм поиска вхождений при низком уровне емкостной сложности имеет временную сложность О(n), но устанавливает ограничения на лингвистическую структуру образца. Анализ ситуаций пропуска объективно существующей позиции образца в обрабатываемом слове при работе приведенного последовательного алгоритма сопоставления позволил определить типологию структур образцов и осуществить модификацию алгоритма с временной сложностью от О(n) до O(m(n-m+2)). Модификация заключается в том, что при любом частичном совпадении начального повторяющегося фрагментаа образца са соответствующим фрагментом обрабатываемого слова (в отличие от алгоритма прямого сопоставления)а дальнейшее сопоставление необходимо выполнять с позиции обрабатываемого слова, следующей за началом частично совпавшего фрагмента, и ас первой буквы образца - синхронно.аа

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

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

Местоположение итераций позволяет выделить следующие структуры сложных образцов: {P}i - итерация слова по всей своей длине (1); {P}iR - итерация в начале слова (префиксная итерация) (2); R{P}i - итерация в конце слова (3);

Rl {P}jR2 - итерация в середине слова (4); {Pl}jR{P2}j - итерация в начале и конце слова.

Временные затраты, связанные с многократными отступами и повторной обработкой символов, дляа случая префиксной итерации при работе последовательного алгоритма составят

T=m(k-m+2) -1.аа а а а(3)

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

T=(k-d)(d+1)+d,а а аа а а аа(4)

где d - число итераций в префиксе образца.

Для образцов вида ((а)2bc)3p будет справедлива формула

Т=2gХd2+g,а а аа (5)

где g - общее число символов во внешних скобках с учетом внутренней итерации; d - число итераций внешних скобок.

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

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

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

Рассмотрим метод применения нуль-единичной характеристической матрицы. Пусть в общем алфавите Sа мощностью ?S?= w заданы образец W и обрабатываемое слово V как последовательности кодов символов из алфавита S длиной в n и m символов (n < m) соответственно и пусть каждый символ образца и обрабатываемого слова (ОС) кодируется p=log2w разрядами соответственно. Требуется определить все позиции начала вхождений W в V.

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

Известен алгоритм СДВИГ-И параллельной реализации операции сопоставления, основанный на поиске всех возможных префиксов образца в тексте с помощью логических векторов-столбцов длиной в n бит каждый. Каждый элемент такого вектора-столбца принимает значение логической л1 или л0 в зависимости от того: присутствует ли текущий префикс образца в тексте в данной позиции. При такой организации исходных данных операция поиска вхождения сводится к последовательной обработке нуль-единичных векторов-столбцов (битовых срезов). Основной анедостаток этого алгоритма заключается в последовательной обработке m векторов-столбцов, что приводит к избыточным затратам времени за счет m-кратного обращения к памяти символов текста для вычисления текущего вектора-столбца.

Работа устройства основана на обработке элементов двух множеств (признаков и объектов) с помощью логических векторов-строк или векторов столбцов. Вектор-строка является характеристическим вектором, описывающим определенное подмножество признаков, принадлежащих множеству объектов. В качестве элементарных операций над векторами реализованы логические операции умножения, сложения, суммы по модулю 2, инверсии и т.д., а также операции идентификации логического вектора-строки (поиск по столбцу).

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

Сущность параллельной обработки характеристической матрицы заключается в побитовой обработке элементов строк и столбцов в составе диагоналей матрицы, длина которых равна длине образца, а направление поиска - от последнего символа к первому по каждой диагонали. На рисунке 1 приведена иллюстрация применения характеристической матрицы. Характеристическая матрица состоит из ячеек, имеет геометрическую форму параллелограмма, размер матрицы - n?k ячеек (k=m-n+1 - количество строк, а также диагоналей в матрице). На вход каждой ячейки, расположенной в последней строке матрицы, подано значение лог. л1.

аа

Рис. 1. Иллюстрация примененияа характеристической матрицы при сопоставлении

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

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

Рассмотрим организацию одного из перспективных для поисковых машин специализированных процессоров-акселераторов сопоставления. Приведема в доступной для экспертизы форме дескриптор его структурно-функциональной организации (патент № 72771 РФ).аа Функциональная схема устройства показана на рисунке 2. Оно состоит из блока управления (БУ) иа блока матричного поиска (БМП), связанных между собой управляющими шинами и шинами данных.

Рис. 2 Обобщенная схема матричного устройства

Рассмотрим структуру блока управления. Управление функционированием БУ и синхронизация работы блоков осуществляетсяа с помощью шин управляющих сигналов. Шины данных и адресов служат для передачи данных и адресов междуа БУ и БМП.

Блок управления предназначен для формирования сигналов хранения исходных и результирующих данных, общего управления процессом поиска и представляет собой анесложную комбинационную схему. Блок БУ содержит три управляющих входа: Старт (от внешнего устройства), вход N для задания размерности образца ( от внешнего устройства) и вход Загрузка разрешена,а также три выхода: Начальная установка, Запись строк иа выход N для задания размерности образца. Символы образца и ОС подаются по ШДО (шина данных образца) иа по шина данных и адреса ОС (ШДиА) в параллельном коде через информационные входы. Результат выдается по сигналу Загрузка разрешена по шина данных и адреса результата (ШДР).

Блок БМП (Рис. 3) содержит три управляющих входа: Начальная установка 71 (первый вход) и вход Запись строк (второй вход), вход N для задания размерности образца, третий и четвертый - входы для подачи символов образца и ОС в параллельном коде через информационные входы 43 и 44 устройства, а также дваа информационных выхода - второй выход 52 устройства и выход Загрузка разрешена.

Блок БМП содержит элемент азадержки 1, состоящий из n пар инверторов, n регистров 21-2n для хранения кодов символов образца, m регистров 31-3m для хранения кодов символов текста, характеристической матрицы ячеек 411-4nm и k триггеров 7 позиций, причем регистры 2i (i=1-n) и 3j (j=1-m) содержат первый и второй управляющие входы, третий p-разрядный информационный вход и один выход соответственно. Первые и вторые входы n регистров 2 для хранения кодов символов образца и первые и вторые входы m регистров 3 для хранения кодов символов текста соединены соответственно с первым и вторым управляющими входами БМП, третий вход которого разрядностью p?n бит предназначен для параллельной записи образца в регистры 21-2n и состоит из n групп разрядов по p разрядов каждая группа, кодирующих символы образца, причем i-ая группа разрядов (i=1-n) подается на третий p-разрядный вход регистра 2i (i=1-n), четвертый вход БМП разрядностью p?m бит предназначен для параллельной записи текста в регистры 31-3m и состоит из m групп разрядов по p разрядов в каждой группе, кодирующих символы текста, причем j-я группа разрядов (j=1-m) подается на третий p-разрядный вход регистра 3j (j=1-m). Второй управляющий вход блока БМП также соединен со входом элемента задержки 1.

Рис. 3. Структурная схема устройства БМП

Характеристическая матрица ячеек 411-4nm (рис. 3) имеет размер n?k ячеек (k=m-n+1 - количество строк, а также диагоналей в матрице), причем каждая поисковая ячейка 4ij имеет три входа и один выход и содержит двухвходовую схему 5ij сравнения на равенство p-разрядных кодов символов образца и текста и двухвходовый элемент 6 (И). Каждая двухвходовая схема 5ij сравнения на равенство в составе поисковой ячейки 4ij состоит из p двухвходовых элементов 81-8p суммы по модулю два с инверсией, на первые входы которых подается соответствующий разряд из i-й р-разрядной группы третьего входа блока БМП, а на вторые входы двухвходовых элементов 81-8p суммы по модулю два с инверсией - соответствующий разряд из j-й р-разрядной группы четвертого входа блока 4 матричного поиска. Все выходы двухвходовых элементов 81-8p суммы по модулю два с инверсией в составе двухвходовой схемы 5ij сравнения на равенство соединены с p-входовым элементом 9 (И), выход которого является выходом двухвходовой схемы 5ij сравнения на равенство. Первый и второй p-разрядные входы поисковой ячейки 4ij соответственно соединены с первым и вторым p-разрядными входами двухвходовой схемы 5ij сравнения на равенство, выход которой является первым входом двухвходового элемент 6 (И), второй вход которого является третьим входом поисковой ячейки 4ij, выходом которой является выход двухвходового элемента 6 И.

Характеристическая матрица ячеек 411?4nm имеет геометрическую форму параллелограмма, в которой в каждой строке располагается k ячеек, сдвинутых относительно следующей строки ячеек влево на 1 позицию начиная с ячеек последней строки 4nn?4nm. Такая форма матрицыа обеспечивает направление поиска по диагоналям, проходящим через ячейки от последней строки к первой строке включительно.

Рис.4. Схема одной ячейки матрицы

Первые p-разрядные входы k ячеек i-й строки матрицы (i=1-n) соединены с p-разрядным выходом регистра 2i. P-разрядный выход регистра 3j (j=1-m) соединен со вторыми p-разрядными входами всех ячеек, входящих в j-й столбец матрицы. Выход каждой поисковой ячейки 4ij, кроме i=1 (первая строка матрицы), соединен с третьим входом поисковой ячейки 4i-1j-1, кроме i=n (последняя строка матрицы). Выход поисковой ячейки 4iv (v=1-k), расположенной в первой строке матрицы, соединен с информационным входом 3 триггера 7v позиции. На третий вход каждой поисковой ячейки, расположенной в последней строке матрицы, подается значение логической л1, задавая тем самым направление поиска по соответствующей диагонали от последней строки матрицы к первой строке включительно.

Триггеры 71-7k позиций хранят результат поиска в виде k-разрядного кода, в котором значением логической л1 отмечены позиции начала вхождений образца в текст. Триггер 7i позиции (i=1-k) содержит три входа (первый и второй - управляющие, третий - одноразрядный информационный вход) и один выход. Первый вход БМП соединен соответственно с первыми входами k триггеров 7 позиций, вторые входы k триггеров 7 позиций соединены с выходом элемента 1 задержки. Выходы триггеров 71-7k позиций образуют k-разрядный информационный выход БМП.

Данное устройство работает следующим образом.

При подаче на вход сигнала Старт блока БУ формирует ана входа Начальная установка блокаа матричного поиска импульсный сигнал начальной установки, который сбрасывает в нулевое состояние k триггеров 7 позиций по их входу 1, n регистров 2 по их входу 1 и m регистров 3 по их входу 1. После окончания действия сигнала начальной установки наа второй вход Запись строк блока матричного поиска подается импульсный сигнал. Данный импульсный сигнал по входу Запись строк блокаа матричного поиска подается соответственно на вторые входы разрешения записи n регистров 2 для хранения кодов символов образца и на вторые входы разрешения записи m регистров 3 для хранения кодов символов текста, обеспечивая тем самым запись n символов образца и m символов текста в параллельном коде с входов 3 и 4 устройства. Также импульсный сигнал по входу Запись строк блока 4 матричного поиска через элемент 1 задержки подается соответственно на вторые входы разрешения записи k триггеров 7 позиций. Элемент 1 задержки, выполненный в виде n пар инверторов, необходим для завершения процессов параллельного поиска вхождений по диагоналям характеристической матрицы, состоящей из поисковых ячеек 411 - 4nm. Поиск начинается с ячеек последней строки характеристической матрицы. Начальный k-битовый характеристический вектор, равный 11Е1, подается на третьи входы ячеек последней строки матрицы и определяет тем самым направление параллельного поиска по всем диагоналям характеристической матрицы - от поисковых ячеек последней строки до ячеек первой строки включительно. Время параллельного поиска вхождений не зависит от количества диагоналей, а определяется величиной T=ntИ, где tИ - время задержки в элементе 6 (И). По завершении процессов поиска импульсный сигнал с выхода элемента 1 задержки через время TТ=n2tинв (2tинв - время задержки на паре инверторов) записывает k-битовый результат поиска начала вхождений в триггеры 7i-7k позиций. Выходы триггеров 71-7kа позиций являются k-разрядным выходом блока БМП и образуют второй выход устройства 52 рис. 3.

Однородная структура поисковых ячеек 411-4nm (рис. 4), составивших основу БМП, обусловливает реализацию устройства для параллельного поиска и обработки данных на СБИС программируемой логики (FPGA, CPLD, FLEX и др.) для необходимых разрядностей n, m образца иа текста соответственно.

В данной главе выполнены оценки аппаратных затрат защищаемого аустройства и известных устройств сопоставления, разработанных на кафедре программного обеспечения вычислительной техники КурскГТУ. Аппаратные затраты в транзисторах на последовательное устройство 9607 транз., на конвейерное устройство составляют 19797 транз., ана параллельное (ассоциативное) устройство 59558 транз., на матричное устройство 48014 транз. в виде одного модуля при n=m=16.

Таким образом, в третьей главе создана структурно-функциональная организация нового устройства-акселератора сопоставления, создающего основу для постановки НИОКР.

В четвертой главе приводятся результаты исследования скоростных характеристик разработанного устройства сопоставления и устройств-аналогов. Данная глава посвящена разработке программных моделей и экспериментальному исследованию скоростных характеристик разработанного устройстваа по отношению к аналогам, в том числе и к устройствам сопоставления, разработанным на кафедре программного обеспечения Курского государственного технического университета. В экспериментальных исследованиях использовались программные модели следующих устройств: последовательное; конвейерное; параллельное (ассоциативное); матричное. В качестве эталонной модели использовался микропроцессор Intel Pentium IV, реализующий строковую функцию strstrбиблиотеки <string.h> аBorland C++ 6.0. Время, затрачиваемое устройством на процесс сопоставления, измеряется в машинных тактах. Под машинным тактом традиционно принимается фиксированный квант времени, за которое устройство реализует одну элеменнтарную операцию символьного сравнения.

В процессе исследования выполнено 15 экспериментов, в каждом из которых задавались различные и важные с практической точки зрения структуры образцов и обрабатываемых слов в виде абстрактных текстов с тем, чтобы отдельно не рассматривать типы файлов: естественных языков, программных кодов, изображений, оцифрованных сигналов и т.д., которые не являются специфическими при выполнении алгоритмов сопоставления. Все обрабатываемые слова разделены на три класса: А - слова, которые не содержат фрагментов, приводящих к отступам (возвратным переходам в пространстве слова); Б - слова, содержащие только такого рода фрагменты;а В - смешанный класс слов с чередующимися фрагментами, принадлежащими аклассам А или Б, имеющий самую высокую частоту встречаемости ва процессах символьных вычислений.

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

На рис. 5 и 6 приведены результаты экспериментальных исследований для массово распространенного B-класса обрабатываемых слов и для образцов, содержащих префиксную итерацию (с варьируемой длиной) для разработанного матричного и ассоциативного устройств, а также для эталонного компьютера с неймановской архитектурой.

На рисунках устройства обозначены следующим образом: У1 - последовательное, У2 - конвейерное, У3- параллельное (ассоциативное ), Матр - матричное, УЭВМ - эталонный компьютер.

Таким образом, в четвертой главе завершено диссертационное исследование в соответствииа с его целью и задачами.

Рис. 5. Графики зависимостей временных затрат исследуемых устройств (среда Б)

Рис. 6. Графики зависимостей временных затрат исследуемых устройств

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

от длины этих итераций (при условии, что в тексте нет вхождений образца)

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


ОСНОВНЫЕ РЕЗУЛЬТАТЫ И ВЫВОДЫ

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

1.а Анализ разноплановых и разнообразных по прикладным областям задач ОСИ позволил определить частотный показатель операции сопоставления и установлено, что сопоставление является массовой операцией (до 85%) общего ресурса времени при символьных вычислениях. Поэтому созданы новые безотступные методы сопоставления, осуществлена их алгоритмизация и исследована временная сложность последовательных, конвейерных, параллельных (ассоциативных) и матричных алгоритмов. Проведен структурно- лингвистический анализ образцов и обрабатываемых слов, что позволило получить аналитические зависимости для определения временной сложности исследуемых алгоритмов сопоставления. Установлено, что существенное скоростное преимущество по отношению к аналогам имеет параллельный (ассоциативный) алгоритм, но явное авременное преимущество установлено для матричного алгоритма, что послужило основанием для его аппаратной поддержки.

2.а Разработана структурно-функциональная организация устройств,а реализующих матричный алгоритм сопоставления, отличающийся тем, что в нем впервые применяетсяаа безотступная параллельная технология сопоставления, открывающая пути их эффективного применения ва качестве перспективных спецпроцессоров-акселераторов мощных серверов и поисковых машин. Матричное устройство имеет 54 кратное скоростное преимущество по отношению к эталонному компьютеру с неймановской архитектурой. По отношению к ассоциативному аустройству разработанное устройство имеет 15 кратное преимущество.

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

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

 

ОСНОВНЫЕ ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

Публикации по перечню ВАК:

  • исицин, Л.А. Быстрые символьные вычисления в медицинских системах поддержки принятия решений [Текст] / Л.А. Лисицин, С.Г. Емельянов, Е.А. Титенко // Вестник новых медицинских технологий.аа 2006. №2. С.158-160.

Публикации:

  • исицин, Л.А. Анализ стратегий выводов в экспертныха системах для разработки методов быстрых символьных вычислений [Текст] / Л.А. Лисицин, В.М. Довгаль, Е.А. Титенко // Теоретические и прикладные вопросы современных информационных технологий: матер. VII Всерос. науч.-техн. конф. / Восточно-Сибирский гос. технол. ун-т., Улан-Удэ, 2006. С. 162-166.
  • Довгаль, В.М.а Способ параллельной реализации подстановки [Текст] / Л.А. Лисицин, Е.А. Титенко, С.В. Малюк // Интеллектуальные системы (INTELSТ2008): VIII Междунар. симпоз. Н.Новгород, 2008. С. 242-244.
  • исицин, Л.А. Повышение быстродействия работы путем организации параллельного поиска в характеристической нуль-единичной матрице [Текст]/а Л.А. Лисицин, В.М. Довгаль // Известия Курск. гос. техн. ун-та. 2008. №4. С. 39-41.

Патенты

  • Устройство для параллельного поиска и обработки данных [Текст]: Пат. на полез. модель 72771 РФ, МПК G 06 F 12/00 / Л.А. Лисицин , Е.А.Титенко, В.М. Довгаль; патентообладатель ГОУ ВПО Курск. гос. техн. ун-т; № 2007149075/22: заявл. 25.12.2007; опубл. 27.04.2008, Бюл.№12.

Соискатель аЛ.А.Лисицин

 

 

Подписано в печатьа 05.05.2008. Формат 60?84 1/16. Бумага офсетная.

Усл. печ. л. аа 1,0. Тиража 100 экз. Заказ 205.

Курский государственный технический университет.

Издательско-полиграфический центр Курского государственного

технического университета. 305040, г. Курск, ул. 50 лет Октября, 94.

     Авторефераты по темам  >>  Разные специальности - [часть 1]  [часть 2]