Содержание к диссертации
Введение
Глава 1. Аналитический обзор систем обработки символьной информации на основе операции сопоставления и сущность предлагаемого подхода 11
1.1. Особенности задач ОСИ 11
1.2. Аппаратные средства ОСИ 14
1.2.1. Основные направления развития технических средств ОСИ 14
1.2.2. Особенности существующих технических средств ОСИ 16
1.2.3. Специализированные процессоры ОСИ в составе универсальных вычислительных систем 20
1.3. Сущность предлагаемого подхода к созданию теоретических основ быстрых продукционных вычислений и устройств систем ОСИ 23
1.4. Выводы 24
Глава 2. Разработка теоретических основ акселерации процессов сопоставления 26
2.1, Основные понятия и определения конструктивной семиотики 26
2.2. Исследование влияния структуры образца на скорость и корректность протекания процессов сопоставления 30
2.4. Конвейеризация процесса сопоставления 34
2.5. Алфавитный способ сопоставления (ассоциативный) 39
2.6 Повышение скорости путем организации параллельного поиска на основе характеристической нуль-единичной матрицы 41
2.7. Выводы 43
Глава 3. Описание известных устройств сопоставления и разработка матричного устройства 45
3.1. Описание последовательного устройства сопоставления 45
3.1.1. Описание структурной схемы устройства 45
3.1.2. Описание алгоритмов и работа устройства 47
3.2. Описание конвейерного устройства сопоставления 51
3.2.1. Структурная схема устройства 51
3.2.2. Описание и функционирования алгоритмов работы устройства.. 54
3.3. Описание ассоциативного устройства сопоставления 59
3.3.1. Описание структурной схемы устройства 59
3.3.2. Описание и функционирование алгоритмов работы устройства... 63
3.4. Разработка матричного устройства сопоставления 67
3.4.1. Структура устройства 67
3.4.2. Структура блока управления БУ 68
3.4.3. Структура устройства БМП 68
3.4.4. Разработка алгоритмов работы устройства и описание его функционирования 71
3.5. Расчет аппаратной сложности устройств сопоставления 72
Выводы 83
Глава 4. Эксперементальное исследование скорости разработанных устройств сопоставления 85
4.1. Разработка программных моделей устройств сопоставления 86
4.2. Разработка способа измерения времени, затрачиваемого эталонным компьютером на выполнение процессов сопоставления 87
4.3. Анализ алгоритмической сложности процедуры сопоставления 88
4.4. Исследование временных характеристик моделируемых устройств... 90
4.4.1. Исследование временных характеристик устройств на образцах, в структуре которых нет итерации 90
4.4.2. Исследование скорости работы устройств на образцах, в структуре которых имеется итерация в начале слова 100
4.4.3. Исследование скорости работы устройств на образцах, в структуре которых имеется итерация в конце слова 105
4.4.4. Исследование скорости работы устройств на образцах, в структуре которых имеется итерация в начале и конце слова 107
4.4.5. Исследование работы устройств на образцах, в структуре которых есть итерация в середине слова 112
4.4.6. Исследование скорости работы устройств на образцах, состоящих из итерации 115
4.5. Выводы 120
Заключение 121
Библиографический список 123
Приложение 130
- Специализированные процессоры ОСИ в составе универсальных вычислительных систем
- Исследование влияния структуры образца на скорость и корректность протекания процессов сопоставления
- Разработка алгоритмов работы устройства и описание его функционирования
- Разработка способа измерения времени, затрачиваемого эталонным компьютером на выполнение процессов сопоставления
Введение к работе
Актуальность работы. Современный этап развития вычислительной техники характеризуется повышенным вниманием к созданию аппаратных средств для обработки символьной информации (ОСИ). Особую значимость приобретает создание средств быстрых символьных вычислений, поскольку они занимают до 98% временного ресурса в современных системах обработки и передачи данных. Доминирующее положение в системах ОСИ занимает процедура поиска по образцу, называемая операцией сопоставления. При быстром росте объемов обрабатываемых данных операция сопоставления по частоте использования является лидирующей. Действительно, все алгоритмы ОСИ, функционирующие на основе формул подстановок и продукций, системы ситуационного управления, все грамматики и распознающие автоматы, системы обработки знаний и языков, криптография, а также поисковые машины компьютерных сетей основываются на сопоставлении как неотъемлемой составляющей этого класса массовых символьных вычислений.
Важность и массовость операции сопоставления отражена в научных трудах высших авторитетов в истории вычислительной техники А. Тьюринга, А. Черча, А.А. Маркова, А.Н. Колмогорова, D.E. Knuth, (Jr) J.H. Morris, V.R. Pratt, R.S. Boyer, J.S. Moore и многих других отечественных и зарубежных исследователей.
Между тем повышение скорости выполнения операции сопоставления остается актуальной задачей, несмотря на разнообразные программные и/или аппаратные средства ее реализации. Как правило, аппаратная реализация операции сопоставления имеет явное скоростное преимущество по отношению к программной, но аппаратный подход приводит к технологической разнородности и трудностям сопряжения с типовыми аппаратными средствами современной вычислительной техники. С другой стороны, программные реализации операции сопоставления открывают пути эффективного применения существенно дешевеющих серийных микропроцессоров и транспьютеров. Сложившаяся ситуация в полной мере отражает основное объективное противоречие, на разрешение которого направлено данное диссертационное исследование, а основная научно-
техническая задача заключается в создании методов, алгоритмических и аппаратных средств акселерации массовой операции сопоставления в процессах обработки символьной информации на основе результатов структурно-лингвистического анализа образцов и обрабатываемых слов.
В научном аспекте решаемая задача сводится к разработке и
исследованию методов, алгоритмов и структурно-функциональной
организации устройства сопоставления. Практический фрагмент диссертации включает в себя схемотехнические решения устройства сопоставления и экспериментальное исследование его скоростных характеристик.
Работа выполнялась в рамках госбюджетных НИР кафедры программного обеспечения вычислительной техники Курского государственного технического университета, а также по гранту А04-3.16-695 Федерального агентства по образованию «Методы акселерации работы продукций и символьные мультипроцессоры автоматизированных систем ситуационного управления» при участии автора данной диссертационной работы.
Объект исследования - процессы обработки символьной
информации.
Предмет исследования — процессы сопоставления (поиск по образцу).
Цель работы заключается в акселерации выполнения операции сопоставления путем разработки методов, алгоритмов и средств их аппаратной поддержки в виде устройства сопоставления и в экспериментальном исследовании его скоростных и аппаратных характеристик.
Основные задачи диссертационного исследования:
Осуществить анализ методов, алгоритмов и устройств ОСИ для определения частотного показателя операции сопоставления.
Создать методы и алгоритмы для высокоскоростной реализации операции сопоставления и исследовать их временную сложность.
Разработать структурно-функциональную организацию устройств сопоставления и их схемотехнические решения.
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% от общего временного ресурса при осуществлении символьных вычислений.
Получившие в последнее время широкое распространение многоядерные вычислители не достигают существенных скоростных преимуществ при выпол-нении символьных вычислений на том основании, что операция сопоставления в них реализуется, как правило, на программном уровне. В них преимущественно используются алгоритмы Бойера Мура или его модификации, а иногда СДВИГ-И.
Сущность предлагаемого подхода к решению задачи акселерации выполнения операции сопоставления заключается в исследовании и разработке методов, алгоритмов и специализированных устройств сопоставления с такой структурно-функциональной организацией, которая
согласована с противо-речивыми требованиями по аппаратным затратам, высокой скоростью работы и сопряжения с типовыми аппаратными средствами массовой вычислительной техники. Предметной стороной предлагаемого подхода является повышение скорости реализации процессов сопоставления путем их аппаратной реализации, снижение порога сложности при сопряжении с типовыми устройствами в архитектурах современных компьютеров однородности, как основного условия технологичности при допустимых аппаратных затратах и организации параллельной и/или конвейерной работы.
Изложенные материалы первой главы дают основания для заключения о том, что решена первая задача диссертации.
Получившие в последнее время широкое распространение многоядерные вычислители не достигают существенных скоростных преимуществ при выпол-нении символьных вычислений на том основании, что операция сопоставления в них реализуется, как правило, на программном уровне. В них преимущественно используются алгоритмы Бойера Мура или его модификации, а иногда СДВИГ-И.
Сущность предлагаемого подхода к решению задачи акселерации выполнения операции сопоставления заключается в исследовании и разработке методов, алгоритмов и специализированных устройств сопоставления с такой структурно-функциональной организацией, которая согласована с противо-речивыми требованиями по аппаратным затратам, высокой скоростью работы и сопряжения с типовыми аппаратными средствами массовой вычислительной техники. Предметной стороной предлагаемого подхода является повышение скорости реализации процессов сопоставления путем их аппаратной реализации, снижение порога сложности при сопряжении с типовыми устройствами в архитектурах современных компьютеров однородности, как основного условия технологичности при допустимых аппаратных затратах и организации параллельной и/или конвейерной работы.
Изложенные материалы первой главы дают основания для заключения о том, что решена первая задача диссертации.
Во второй главе рассматриваются основные понятия и определения конструктивной семиотики, а также результаты структурно-
лингвистического анализа образцов и краткое изложение разработанных автором и известных методов сопоставления.
С целью расширения функциональных возможностей и повышения скорости выполнения операций сопоставления нами разработан механизм параллельной обработки нуль-единичной характеристической матрицы, однозначно определяющей не только позиционное, но и пространственное расположение отдельных символов образца в матричном представлении символов ОС.
Таким образом, во второй главе по результатам структурно-лингвистического анализа образцов создана основа для повышения скорости выполнения операции как для последовательной, так и параллельно-последовательной ее реализации с целью применения в системах ОСИ различного назначения.
В третьей главе описана структурно-функциональная организация устройств сопоставления конвейерного и параллельно-последовательного принципов действия,и разработано устройство сопоставления на основе характеристической нуль-единичной матрицы.
В данной главе выполнены оценки аппаратных затрат защищаемого устройства и известных устройств сопоставления.
В четвертой главе приводятся результаты исследования скоростных
характеристик разработанного устройства сопоставления и устройств-
аналогов. Данная глава посвящена разработке программных моделей и
экспериментальному исследованию скоростных характеристик
разработанного устройства по отношению к аналогам, в том числе и к устройствам сопоставления, разработанным на кафедре программного обеспечения Курского государственного технического университета.
В заключении приводятся основные результаты и выводы, а в приложениях к диссертации содержатся схемотехнические решения всех четырех устройств сопоставления, таблицы и графики, полученные в результате проведения экспериментальных исследований, а также листинги программ.
Специализированные процессоры ОСИ в составе универсальных вычислительных систем
Использование специализированных процессоров ОСИ в качестве устройств-акселераторов является эффективным средством повышения производительности компьютерных информационных систем. Устройства акселераторы представляют собой самый широкий класс аппаратных средств современной вычислительной техники. Их практическое использование существенно расширяет функциональные возможности систем обработки информации как числовой, так и символьной; Рассмотрим класс спецпроцессоров ОСИ, которые используются в целях повышения производительности информационных систем. Наиболее типичным представителем данного класса устройств следует считать микропрограммные Лисп-процессоры ALPHA фирмы Fujitsu (Япония, 1983г.) [2], подключаемые через мультиплексный канал к универсальной ЭВМ FACOM, что позволяет пользователю компьютера FACOM эффективно выполнять в режиме разделения времени программы ОСИ, написанные на языках UtiLisp (MacLisp) и Prolog. Кроме того, 40-разрядная машина SM 45000 фирмы IMI (Inference Machines Inc., США, 1987 г. [1], в которой высокоскоростной символьный процессор подключен к специализированному вычислительному процессору, обеспечивающему обработку числовых данных со скоростью 4 MFlops. Символьный процессор построен на основе быстродействующих схем для декодирования тегов и до 8 раз превышает по скорости работы эталонную модель 3600 фирмы Symbolics [33]. Перспективной разработкой в рассматриваемом классе спецпроцессоров следует считать созданный Электротехнической лабораторией Японии ассоциативный процессор IMX2 для решения задач искусственного интеллекта, перевода естественных языков и акселерации работы с базами знаний [34]. Данный процессор конструктивно строится на основе 64-х ассоциативных и 9-ти сетевых процессоров, работающих под управлением рабочей станции SPARC Station-2, АЗУ 40К по 40 разрядов и транспьютеры Т800 соответственно.
Предлагаемая модель в 13 раз опережает по скорости работы названную станцию SPARC Station-2. Важным недостатком ассоциативных процессоров является необходимость перезагрузки после модификации обрабатываемого слова при переходе к следующему акту сопоставления. В особый класс специализированных символьных процессоров следует выделить процессор MicroJava 701 (компания Sun Microsystems), выполненный в архитектурной аранжировке picoJava и предназначенный для аппаратной поддержки приложений, написанных на языке Java. Среди эффективных спецпроцессоров ОСИ целесообразно отметить техническое решение, обеспечивающее выполнение операций логического вывода на основе правил, представленных в виде импликаций [35]. Также следует выделить узко специализированное устройство поиска информации для электронного словаря и ему подобных систем. Данное устройство содержит ЗУ с несколькими банками информации и табличную память. Банки данных используются или как источник базовой информации, или как изменяемые банки и как адрес [36]. В этом проекте используется программно-аппаратная реализация сопоставления, погруженная в сложный ансамбль других символьных преобразований, из которых все реализутся на одном специализированном процессоре. Вместе с тем к этому же классу спецпроцессоров отнесем оригинальные технические решения в виде следующего списка: - процессор для обработки документов с функцией преобразования строк символов [37]; - процессор, определяющий частоту встречаемости слов в ре дактируемом тексте, хранящемся в текстовой памяти.
При этом кон фигурация памяти позволяет быстро выполнять операции над словами [19]; - устройство для логического вывода, которое имеет упрощенную архитектуру, реализующую функцию определения членов логического вывода с помощью подстановки соответствующих значений и обеспечивающую высокую эффективность обработки изменяющейся линг вистической информации [36]. Развитие микроэлектронных технологий позволяет надеяться на получение значимых результатов при аппаратной поддержке лингвистических процессоров, представленных в работах [34, 38]. Большое разнообразие спецпроцессоров приводит к нетривиальным проблемам их сопряжения в составе систем на всех уровнях организации вычислительных процессов. В заключение приведем еще один класс символьных компьютеров, которые аппаратно поддерживают языки ОСИ Лисп (Zeta Lisp, Common Lisp, Interlisp), Пролог и другие. В этих аппаратных средствах основное внимание уделяется повышению скорости выполнения типовых операций используемых языков и распараллеливанию вычислительных процессов. При этом сопоставление, входящее в типовые операции, не выделяется в отдельную категориальную единицу и под нее не выделяется аппаратный ресурс [2, 6], что приводит к существенному снижению производительности при решении отдельных практически важных задач ОСИ. Этим, в частности, объясняется появления многообразия версий Лиспа.
Исследование влияния структуры образца на скорость и корректность протекания процессов сопоставления
В данном разделе анализируются прямые алгоритмы сопоставления с образцом, рассматриваются причины возникновения пропуска позиций вхождений образца, оценивается степень влияния структуры образца на процесс сопоставления. Рассмотрим два произвольных слова V и W в виде цепочек символов: где v; є А, для і = 1, n, Wj є А, для j = 1, m, A - конечный алфавит. Пусть W — это поисковый образец, V — обрабатываемое слово, в котором требуется найти позицию вхождения слова W. Если исключить случай, когда длина m образца больше длины п обрабатываемого слова (при этом результат сопоставления очевидно ложен), то последовательный алгоритм поиска может быть таким: 1) указатель на текущий символ слова устанавливается i:=l, указатель на текущий символ образца - j:=l; 2) если і п и j m, тогда после выполнения условия равенства символ V; и Wj осуществляется переход к сравнению следующих символов (і:=і+1, j :=)+1) При неравенстве Vj и WJ: посимвольное сопоставление слов начинается с первогр символа образца (j :=1) и текущей символы слова. 3) алгоритм завершает работу с результатом вхождение обнаружено в позиции (і-j+l) слова V при истинности условия j m или с результатом вхождение не обнаружено при выполнении условия і п. Представленный алгоритм поиска вхождений при своей очевидной простоте имеет временную сложность 0(п), но не всегда обнаруживает позиции вхождения. Пусть для слов (1) и (2) обнаружено частичное вхождение образца Р в позиции к слова V, т.е. выполняется графическое равенство слов VkVk+i...VMta VfcH-i, и wi\v2...WHwb t m. В соответствии с безотступной технологией поиска, подразумевающей в ситуации частичного вхождения поиск продолжать с текущей или следующей символы обрабатываемого слова, мы условились начинать поиск с текущей (k+t) символы слова и первой символы образца. При такой организации процесса сопоставления не учитывается возможность вхождения собственного начала слова (10) в себя самого, что может повлечь за собой пропуск позиции вхождения. В литературе [43, 44, 45] приводятся способы и алгоритмы поиска, которые на основе анализа пересечений образца с образцом строят специальный числовой массив, і-й элемент массива содержит позицию образца, с которой следует начинать новый этап поиска при возникновении частичного вхождения на і-й символе образца.
Для исключения возможных пропусков позиции вхождения в рассмотренный выше алгоритм можно внести изменение, заключающееся в том, что при любом частичном совпадении начала искомого вхождения с просматриваемым обрабатываемым словом поиск продолжать с точки слова, следующей за началом частичного совпадения, и первой символы образца. При таком подходе временная сложность будет варьироваться от 0(п), для длины искомого вхождения равной одному символу (в этом случае нет ни одного частичного совпадения), до 0(m(n-m+2)), когда обрабатываемое слово состоит из одного и того же символа и полностью совпадает с первыми (т—1) символами искомого вхождения, а последний символ вхождения в позиции т - другой. Иллюстрацией сложности 0(m(n-m+2)) может послужить пример: Таким образом, анализ предельных алгоритмов поиска вхождений образца показывает, что, во-первых, структура образца влияет на корректность поиска и на некоторых образцах приводит к пропуску позиций вхождения, во-вторых, конфигурация образца значительно влияет на скорость протекания процессов сопоставления. Рассмотрим подробно классы образцов и исследуем их влияние на скорость протекания процессов сопоставления. Все образцы можно разбить на два больших класса - простые и сложные образцы. Определение 2.2.1. Простым образцом является слово в некотором фиксированном алфавите, которое не имеет более одной позиции вхождения любого своего собственного начала.
Определение 2.2.2. Класс сложных образцов, составляют слова, получаемые из простых образцов применением к ним операций конкатенации и итерации. Местоположение итерации в слове позволяет выделить следующие структуры сложных образцов: 1. {Р}І - итерация слова по всей своей длине. 2. {P};R - итерация в начале слова. 3. R{P}i - итерация в конце слова. 4. R] {P}jR2 — итерация в середине слова. 5. {Pl}jR{P2}j- итерация в начале и конце слова. Общим для структур образцов 1, 2, 5 является наличие начальной итерации образца. Рассмотрим начальную итерацию вида: {a}i=aa...aa п В случае возникновения ситуации частичного вхождения к начальных символ итерации вида (1) и выполнения отступа, на следующем этапе поиска будет обнаружено еще одно частичное вхождение (к-1) начальных символ итерации, за которым вновь последует отступ. Процесс будет продолжаться до тех пор, пока длина частичного вхождения не станет равна 1. Временные затраты, связанные с многократными отступами и повторной обработкой символов, для случая префиксной итерации при работе последовательного алгоритма составят Если распространить подобные рассуждения на произвольное число итерации в префиксе образца, то тогда для вычисления временных затрат при работе последовательного алгоритма получим общую формулу: где d — число итераций в префиксе образца. Для образцов вида ((а)2Ьс)зр будет справедлива формула где g - общее число символов во внешних скобках с учетом внутренней итерации; d - число итераций внешних скобок. Число отступов, приходящееся на итерацию, может быть вычислено по формуле v = целая часть [k/d]. Если при сопоставлении образцов со структурами 2, 5 частичное вхождение в слове будет обнаружено на этапе компарации символ слова R, то будет просмотрено дополнительное количество символов, определяемое формулой (4) для начальной итерации образца и выполнен однократный просмотр той начальной части R, вхождение которой было обнаружено в ситуации первого частичного вхождения.
Разработка алгоритмов работы устройства и описание его функционирования
В соответствии со способом матричного способа сопоставления разработаем алгоритм работы БМП, который изображен на рис. П3.5 Согласно алгоритма рис. П3.5 работа устройства заключается в следующем. Шаг 1. Инициализация устройства. По сигналу «СТАРТ» блок управления выдает на вход «Начальная установка» блока матричного поиска импульсный сигнал начальной установки, который сбрасывает в нулевое состояние регистр 8 по его входу 1, регистр 0 по его входу 1, а также к триггеров 7 позиций по их входу 1, п регистров 2 по их входу 1 и m регистров 3 по их входу 1. устанавливаются в начальное состояние . Шаг 2. По сигналу «Запись строк» устройство начинает свою работу. Этот сигнал подается на второй вход блока матричного поиска. Помимо этого импульсный сигнал «Запись строк» подается соответственно на вторые входы разрешения записи п регистров 2 для хранения кодов символов образца и на вторые входы разрешения записи m регистров 3 для хранения кодов символов текста, обеспечивая тем самым запись п символов образца и m символов текста в параллельном коде с входов 43 и 44 устройства. Также импульсный сигнал по входу «Запись строк» блока 4 матричного поиска через элемент 10 задержки подается соответственно на вторые входы разрешения записи к триггеров 7 позиций. Шаг 3. Поиск начинается с ячеек последней строки характеристической матрицы. Начальный k-битовый характеристический вектор, равный 11...1, подается на третьи входы поисковых ячеек последней строки матрицы и определяет тем самым направление параллельного поиска по всем диагоналям характеристической матрицы от поисковых ячеек последней строки до поисковых ячеек первой строки включительно. Шаг4.
По завершении процессов поиска импульсный сигнал с выхода элемента задержки 1 через время Т =п2тинв (2тинв - время задержки на паре инверторов) записывает k-битовый результат поиска начала вхождений в триггера 7r7k позиций. Выходы триггеров 7i-7k позиций являются к-разрядным выходом блока БМП В разделе производится выбор перспективной технологии изготовления устройств, выполняется вычисление и сравнение аппаратных сложностей разработанных устройств, приводится сопоставительный расчет аппаратных затрат ассоциативных устройств в зависимости от мощности алфавита и разрядности кодировки символов обрабатываемых слов. В настоящее время наиболее производительные микропроцессорные компоненты изготавливаются по БиКМОП технологии, сочетающей биполярную технологию для наиболее критичных по быстродействию цепей и КМОП для большинства основных узлов. Важным свойством логических схем на МОП-транзисторах является высокая плотность упаковки функциональных элементов. Она оказывается приблизительно в 10 раз выше, чем в интегральных схемах на основе биполярных транзисторов. Схемы, выполняемые по КМОП технологии, характеризуются существенно меньшей потребляемой мощностью по сравнению с МОП-схемами и более высоким быстродействием. Базовая схема КМОП-инвертора требует наличия двух полевых транзисторов. Двухвходовые схемы ИЛИ-НЕ и И-НЕ реализуются на четырех полевых транзисторах. БиКМОП-схемы имеют выходы, которые снабжены буферами, обеспечивающими лучшую передаточную характеристику и более постоянный коэффициент разветвления по выходу, а также обладают намного более высоким быстродействием, чем КМОП-схемы. Базовый двухвходовой элемент ИЛИ-НЕ, выполненный по БиКМОП-технологии, потребует восемь полевых транзисторов [55]. Будем рассчитывать аппаратные затраты устройств сопоставления, исходя из реализации их по КМОП-технологии. В таблице 3.1 приведены аппаратные затраты базовых цифровых схем [55]. Результат расчета аппаратных затрат на реализацию последовательного, конвейерного, ассоциативного устройств сопоставления и матричного устройств представлен в таблицах 3.2-3.4 и выполнен с учетом следующих ограничений: - 16-ти разрядная адресация памяти образцов и слов; - 8-ми разрядное кодирование букв слов. Кроме того, дополнительно для конвейерного устройства сопоставления действует ограничение на максимальную длину образца, равную 64 символам. Для ассоциативного устройства максимальная длина образца равна 64 символам и максимальная мощность алфавита образца равна 32.
Разработка способа измерения времени, затрачиваемого эталонным компьютером на выполнение процессов сопоставления
Операция сопоставления как функция поиска вхождения подстроки в строку реализована во многих языках высокого уровня. В качестве одного из примеров языка высокого уровня выберем компилятор Borland C++ - известный среди профессиональных разработчиков программного обеспечения. В стандартную поставку языка Borland C++ 5.0 входит библиотека string.h для работы со строками, оканчивающимися нулевым символом. Для поиска вхождения подстроки в строку служит функция strstr этой библиотеки. В таблице [Приложение 2] приведен дезассемблированный код этой функции, число тактов, требуемых процессору Intel Pentium -IV на выполнение каждой инструкции, описание команд. Инструкции соответствуют набору инструкций микропроцессора Intel Pentium -IV. В данной работе действия, выполняемые функцией strstr можно описать так: 1. Проверка поискового образца на равенство пустому слову. 2. Вычисление длины обрабатываемого слова. 3. Вычисление длины слова-образца. 4. Поиск позиции вхождения первой символы образца в обрабатываемом слове. 5. Проверка условия потенциального вхождения остатка образца в остаток обрабатываемого слова. 6. Посимвольное сопоставление остатков образца и обрабатываемого слова. 7. В случае частичных совпадений начала искомого вхождения с просматриваемым фрагментом обрабатываемого слова осуществляется переход к точке просмотра слова, следующей за началом частичного совпадения.
Так как устройства сопоставления не осуществляют подсчет длин обрабатываемых слов и не контролируют условие потенциального вхождения, то для корректного сравнения времени, требуемого разработанным устройствам на обработку тестовых заданий, с временем, затрачиваемым эталонным компьютером, исключим из рассмотрения действия 2, 3 и 5 библиотечной функции strstr. С учетом этого команды таблицы ( Приложение 2), которые будут вносить вес в измеряемое время поиска, в столбце «Уч» отмечены звездочкой. С учетом принятого выше соглашения о том, что машинным тактом считается квант времени требуемый на реализацию одной элементарной операции символьного уровня, измерение времени выполнения поиска сведем к подсчету числа проходов счетчика команд по отмеченным вершинам программы. При организации параллельного поиска в характеристической нуль-единичной матрице используются следующие действия: 1. Проверка поискового образца на равенство пустому слову. 2. Вычисление длины обрабатываемого слова. 3. Вычисление длины слова-образца. 4. Генерация нужного режима для проверки на основе заданных алфавитов текста и образца при помощи генератора Хенона вида [4.1]. Проверка диагоналей и запоминание вхождений производится аналитическим путем, вычисляется лишь тактовая задержка образца. Алгоритм работы описывается в ( Приложении 3.5.) Поскольку создаваемые устройства сопоставления являются процессорами-акселераторами возникает необходимость в обосновании их использования в составе эталонного компьютера с целью определения скорости его работы с акселератором и без него. Отношение этих двух скоростных характеристик дает объективный параметр для принятия решений о целесообразности акселератора. К процедуре сравнения скорости работы предлагаемых устройств сопоставления со скоростью работы эталонного компьютера предъявляется требование независимости оценки от влияния трех факторов: - способа загрузки образца и обрабатываемого слова (последовательная загрузка или параллельная); - способа расстановки заключительных символов слова; - способа реализации поиска позиций вхождения образцов с возможностью их пересечения. Для того чтобы оценки скорости не зависели от указанных факторов, будем рассчитывать для каждого из устройств реальную алгоритмическую сложность поиска. Пусть длина обрабатываемого слова составляет М символов, длина образца равна L символов, N - это общее количество вхождений образца в слово (без пересечения позиций вхождения и с пересечением). Длины образца и входного слова будем задавать без учета последнего символа в виде признака окончания входного слова. Алгоритмическая сложность поиска для последовательного устройства адекватно задается полученной нами формулой: Сложность Алгоритмическая сложность процесса сопоставления для ассоциативного устройства: Алгоритмическая сложность процесса сопоставления для эталонного компьютера: Алгорит. сложность процесса сопоставления для характеристической матрицы: Для исследования скоростных характеристик предлагаемых устройств при обработке образцов не содержащих итераций будем помещать образцы в среды трех типов: - тип А - среда не порождающая ситуаций отступа; - тип Б - среда со свойством инициирования значительного числа ситуаций отступа; - тип В - среда, занимающая промежуточное положение по отношению к типам А и Б. Среда типа А является относительно упрощенной для выполнения сопоставления. Она характеризуется тем, что при последовательной обработке в процессе сканирования обрабатываемого слова нагрузка будет распределяться на блок обнаружения вхождения первого символа образца. После чего в работу включается блок сопоставления остаточного фрагмента образца. Данный процесс отработки остатка уже не прерывается из-за отсутствия самой возможности отступа. Время, затрачиваемое на поиск позиции одного вхождения, в такой среде можно вычислить по формуле
