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

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

СОРОКИН Валерий Евгеньевич

СТРУКТУРНО-ЛИНГВИСТИЧЕСКИЕ, АЛГОРИТМИЧЕСКИЕ И АППАРАТНЫЕ СРЕДСТВА АКСЕЛЕРАЦИИ РАБОТЫ СИМВОЛЬНОЙ МАШИНЫ БАЗ ДАННЫХ

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

Автореферат диссертации на соискание ученой степени кандидата технических наук

Курск 2005

Работа выполнена на кафедре программного обеспечения вычислительной техники в Государственном образовательном учреждении высшего профессионального образования «Курский государственный технический университет» Министерства образования и науки Российской Федерации

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

Довгаль В.М.

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

Лопин В.Н.

кандидат технических наук Елагин В.В.

Ведущая организация -в/ч 25714

Защита состоится » 2005 г. в — часов на заседании

диссертационного совета Д 21?Л05.02 при Курском государственном техническом университете по адресу: 305040, г. Курск, ул. 50 лет Октября, 94 (конференц-зал).

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

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

Автореферат разослан «"У » /сОЛ^/^Л. 2005 г.

Ученый секретарь диссертационного совета, канд. техн. нйук / Е. А. Титенко

Ы1-Н

г№ов4е

$0 2 9

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

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

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

Решению проблем создания машин и систем баз данных и знаний посвящены работы М. Сенко, Я. Палмера, Г. Найсена, Э. Озкарахана, Л. Капиниченко, Д. Поспелова и других исследователей как у нас в стране, так и за рубежом.

Между тем, в существующих работах отсутствуют реализации машин баз данных, основанных на технологии обработки символьной ин-. формации. ■ ■ •

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

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

Работа выполнялась в рамках НИР по Единому заказ-наряду и грантам Г00-4.2.15 и Г02-4.2.5, выполненных в Курском государственном техническом университете в период с 1999 по 2005 годы при непосредственном участии автора.

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

Для достижения указанной цели решены следующие основные задачи:

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

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

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

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

Объектом исследования являются алгоритмические и аппаратные средства, поддерживающие процессы управления данными.

Прёдмет исследования составляют процессы преобразования информации в системах управления базами данных (СУБД).

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

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

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

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

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

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

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

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

Апробация работы. Результаты работы докладывались и обсуждались на: 1

- 2-й Международной конференции «Оптико-электронные приборы и устройства в системах распознавания образов, обработки изображений и символьной информации. Распознавание-1995» (Курск, 1995);

- Международной конференции «Актуальные проблемы компьютеризации в странах СНГ» (Донецк, 2002);

- б-й Международной конференции «Оптико-электронные приборы и устройства в системах распознавания образов, обработки изображений и символьной информации. Распознавание-2003» (Курск, 2003);

- б-й Международной научно-технической конференции «Медико-экологические информационные технологии-2003» (Курск, 2003).

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

Реализация и внедрение. Результаты диссертационной работы внедрены в НПО «Экран» (Москва), а также используются в учебном процессе Курского государственного технического университета в рамках курса «Высокопроизводительные вычислительные системы», что подтверждается актами о внедрении.

На защиту выносятся:

1. Акселерационные формы представления продукций, а также образцов для быстрых символьных вычислений и процессов сопоставления в контурах СУБД.

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

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

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

Структура и объём диссертации. Диссертация состоит из введения, четырех глав и заключения, изложенных на 167 страницах, содержит 57 рисунков, 2 таблицы, списка литературы из 75 . наименований.

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

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

Первая глава носит обзорный характер и служит целям анализа и функциональных особенностей машин баз данных (МБД).

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

родная, параллельная). МБД представляет собой аппаратно-программный комплекс, являющийся частью вычислительной системы и-предназначенный для выполнения всех или некоторых функций СУБД. Анализ задач, решаемых современными СУБД, позволил выделить основные требования, предъявляемые к МБД: возможность обработки больших объёмов обрабатываемых данных со сложной логической структурой, быстрый по-' иск, добавление, изменение и удаление фрагментов структур; возможность обработки данных, хранящихся как в реляционных базах данных, так и данных, хранящихся в текстовом или документальном формате". Анализ вычислительных средств, ориентированных на выполнение указанных требований, позволил выявить два альтернативных подхода: применение универсальных компьютеров с программным обеспечением, поддерживающим СУБД, и применение специализированных аппаратных устройств, реализующих ресурсоёмкие или часто выполняемые функции СУБД. Рассмотрены преимущества и недостатки указанных подходов.

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

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

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

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

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

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

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

Определение 1. Два слова Б1 и Б2 имеют непустое пересечение только тогда, когда верным является хотя бы один член следующей конструктивной дизъюнкции:

(81,,= 820) V (810 = 82,,) V (81 = (} 18202) V (82 = 0381 <34), (1) где индексы «н» и «о» обозначают собственные начала и окончания слов соответственно; 01, (22, С?3, С>4 - любые слова в заданном фиксированном алфавите; = - знак графического равенства.

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

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

Рассмотрим продукцию, которая завершает работу за конечное число шагов и имеет следующий вид:

ЗА —► Т„Т0, (2)

где Б,,, Эо - непустые начала и окончания образцов; Т,„ Т0 - непустые начала и окончания модификаторов; 8Н80 = Б - образец; ТНТ0 = Т - модификатор; образец и модификатор являются непустыми словами в рабочем алфавите фиксированного языка.

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

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

(80= Т„) V (Э,, = Т0) V (Б = СТО), - (3)

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

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

1. Пусть верным является первый член из (3) S0 = Т,„ тогда продукция представляется акселерационной формой:

'[SMhS0->TH[T0]1;', (4)

где индекс-счетчик к указывает на число смежных повторений фрагмента S„ в обрабатываемом слове и определяет число смежных подстановок в него фрагмента Т0; 1 - символ-указатель позиции начала чтения в обрабатываемом слове при очередной активации продукции; [,] - скобки, задающие границы повторяющихся фрагментов образцов и модификаторов.

2. При верном втором члене S„ = Т0 акселерационная форма представления продукции имеет следующую запись:

' SH [S0)i( —[TJk Т0'. (5)

3. Акселерационная форма продукции при истинном третьем члене дизъюнкции (3) S = CTD будет иметь следующее представление:

'[SJiTtSol Т1, (б)

где индексы-счетчики i и j являются указателями числа вхождения фрагментов S„ и S0, симметричных относительно позиции Т в обрабатываемом слове. Работа продукции (6) заключается в аннуляции всех симметрично расположенных (относительно вхождения фрагмента образца Т) фрагментов в обрабатываемом слове, число которых определяется минимальным из двух значений счетчиков итераций по i или j.

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

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

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

Объединение (R1 UNION R2). Обрабатываемое слово представляет собой последовательность кортежей из отношений R1 и R2. Продукционный алгоритм:

'ар...уо ->* ар...уо'#' оср..,уо ~>*', (7)

где а, Р, у - литеральные переменные, принимающие значение элемента кортежа с первым, вторым и т. д. атрибутами из R1; о - разделитель кортежей в обрабатываемом слове; —»* - обозначение заключительной продукции; # - обозначение композиции алгоритмов;' - метка-указатель позиции начала сопоставления при очередной активации продукции.

Пересечение (R1 INTERSECT R2). Обрабатываемое слово представляет собой последовательность кортежей из отношений R1 и R2. Продукционный алгоритм:

1 ар...уо -+*1 «р...у —>*а$р...7', (8)

где а, р, у - литеральные переменные, принимающие значение элемента кортежа с первым, вторым и т. д. атрибутами из R1 и R2; S - метасимвол из расширения рабочего алфавита.

Вычитание (R1 MINUS R2). Обрабатываемое слово представляет собой последовательность кортежей из отношения R1. Продукционный алгоритм:

W-V0-»'. (9)

где ф, х, у - литеральные переменные, принимающие значение элемента кортежа с первым, вторым и т. д. атрибутами из R2.

Декартово произведение (R1 TIMES R2). Обрабатываемое слово представляет собой последовательность кортежей из отношения R1. Продукционный алгоритм:

'(хр...уо —►* ар...у фх..луо1ар...уо, (10)

где а, Р, у - литеральные переменные, принимающие значение элемента кортежа с первым, вторым и т. д. атрибутами из R1; ф%.. .т}/ - литеральные переменные, принимающие значение элемента кортежа с первым, вторым и т. д. атрибутами из R2,

Деление (R1 DIVISION R2). Обрабатываемое слово представляет собой последовательность кортежей из отношения R1: уК1уК2у ...уКп, где п - число кортежей, а каждый кортеж является словом вида: /V1/V2/ .../Vm/, где Vk - атрибут из Rl, ш - число элементов (атрибутов) кортежа, у - разделитель в обрабатываемых словах. Продукционный алгоритм:

V а/1 # 'yty/Mvp у[м>/М^', (11)

7[/ф] # Vе0 ~*+ усо' # !у® 1

где ф - литеральная переменная на множестве атрибутов всех кортежей из R2, который представляет собой слово: vl, v2, ...,vp, где Vk-атрибут из Rl, р - число атрибутов; цг - литеральная переменная на множестве Vl:Ua (к = 1,2,.. .,m; U - обозначение операции объединения множеств, m - число элементов (атрибутов) кортежа); a - метасимвол, со - литеральная переменная на множестве Ki (i = 1,2, ...,N).

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

Далее приводится иллюстрация продукционной реализации процедурных расширений языка SQL. Базовая функция DECODE, реализованная в языке PL-SQL в СУБД Oracle. Обрабатываемое слово представляет собой значение выбранного элемента кортежа из отношения R1 в виде литеральной переменной Qj. Продукционный алгоритм:

где а, р- литеральные переменные, принимающие значение аргумента и модификатора соответственно; у—трафарет.

Конкретизация литеральных переменных для всех приведенных выше продукционных алгоритмов осуществляется соответствующими мета-алгоритмами.

Во второй главе также приводятся результаты структурно-лингвистического анализа и разработки процедуры поиска по образцу, соответствующей основной операции в СУБД. Разработан положенный в основу запатентованного устройства способ быстрого поиска по обращу. Сущность данного способа заключается в организации безотступного режима сопоставления с образцом, основанного на подсчете числа повторений начала образца в обрабатываемом слове, когда истинным является следующее высказывание:

где 8 - образец; <3 и - любые непустые слова в рабочем алфавите, включая однобуквенные слова, п - число повторений начала образца в его структуре; [,] - границы начального повторяющегося фрагмента образца.

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

При истинности (13) способ сопоставления образца продукции с обрабатываемым словом заключается в следующем:

- обнаруживаются и подсчитываются смежные позиции вхождения С> в обрабатываемом слове;

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

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

где К - число повторяющихся фрагментов; п1- пК - число повторений каждого начального фрагмента образца; \У - собственное окончание образца.

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

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

(13)

8-[...[[<г1]т<г2],а...<гк]пк\у,

(14)

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

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

(0,(М1)<^(М2)) -|-М[<}|,(МЗ):= в, (М1); ¡:= I + 1]; к:=к +1;

-О [Ок(МЗ):= О; (М2);]:=3 + 1] (15)

где в - значение элемента массива в строго определенной позиции; ¡, .ь к -позиционные переменные массивов М1, М2, МЗ соответственно. Работа продукции (15) завершается при любом значении позиционных переменных, превышающем размер хотя бы одного из массивов. Преимущество выбора такого способа слияния определяется низким уровнем алгоритмической и аппаратной сложности устройства слияния и высокой скорость^ его работы.

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

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

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

Устройство сортировки упорядочивает входные данные Бозу, полученные по общим быстродействующим шинам (шина 0, шина 1) из ОЗУ или ВЗУ, и передаёт упорядоченные массивы данных (для дальнейшего их слияния) В УСТРОЙСТВО СЛИЯНИЯ ПОСреДСТВОМ ШИНЫ ДаННЫХ БдаУ!-

----------—-----------------—---—------------------------

ЦП 1-К

ОЗУ 1-Ь

ВЗУ 1-М

ПУ

Контроллеры 1-И

Т1РГ1

Хост-система

Шина О

Символьная машина баз данных

Шина!

^озу 5П1

8п1 |5ДВУ2 Бдву!

Устройство сортировки

Бщ

вп

УДр

Зуд^ддаз

8пз

Устройство слияния

Пооиессоо сотогоовкй

2П4 Зпл^йпмруз Ббпс

Устройство поиска вхождений (Патент РФ 2150740)

£>БПВ.

Буш Су2 .

Су] ■ 5п

СуА

>Г4

Устройство модификации

Униветсалышй символьный ппоиессоп

Рис. 1. Схема взаимодействия устройств сортировки, слияния, поиска и подстановки, выполненная на основе модульной асинхронной архитектуры СМБД

Обозначения на рисунке 1 следующие: ЦП - центральный процессор; ОЗУ - оперативное запоминающее устройство; ВЗУ - внешние запоминающие устройства; ПУ - множество периферийных устройств; S03y - входные данные устройства сортировки, получаемые из основной памяти; Sm - сигнал запуска работы устройства сортировки; Sm» Sm - сигналы запуска устройства слияния при совместном и раздельном режимах работы соответственно; Sn, Sf2 - сигналы готовности устройства слияния при совместном и раздельном режимах работы; Здауь Бдауз - входные данные устройства слияния, получаемые с выхода устройства сортировки или из основной памяти; 8дау2 - выходные данные устройства сортировки при раздельном режиме работы; Буд - выходные упорядоченные данные устройства слияния; Stm - сигнал запуска работы устройства поиска вхождений; Snnc - выходной сигнал блока памяти слов устройства поиска вхождений; Ббпв - выходной сигнал блока памяти вхождений устройства поиска вхождений; ДН1 и АД1 -шины загрузки данных и адресов данных блока памяти вхождений соответственно; ДН2 и АД2 — шины загрузки данных и адресов данных блока памяти слов соответственно; SnM и БПам — шины загрузки данных и адресов данных в память модификаторов и адресов модификаторов устройства модификации; СУ1 и СУ2; Суз и Су4 - сигналы управления, подаваемые с устройства поиска вхождений на вход устройства модификации при совместном и раздельном режимах работы; Бупв - модифицированные данные, возвращаемые в устройство поиска вхождений; Sn, Sp»- сигнал готовности устройства модификации при совместном и раздельном режимах работы.

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

Входными данными для устройства поиска вхождений являются данные, полученные по общим быстродействующим шинам (шина 0, шина 1) из ОЗУ. По шинам ДН1 и АД] загружаются данные и адреса данных блока памяти вхождений соответственно. По шинам ДН2 и АД2 загружаются данные и адреса данных блока памяти слов соответственно. Сигналы Sn4 и установки 0 производят запуск и начальную инициализацию устройства. Найденные адреса вхождений передаются из устройства поиска вхождений на вход устройства модификации по шине данных Sßm- Слова из блока памяти слов устройства поиска вхождений загружаются в устройство модификации по шине Бблс-

Образцы и их адреса загружаются в память модификаторов и память адресов модификаторов устройства модификации по шинам Эпм и Бпам соответственно. По шине Syrm осуществляется обмен данными между устройствами модификации и поиска при их совместной работе. В конфигу-

рации с раздельной работой этих двух устройств результат модификации передаётся в основную память.

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

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

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

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

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

База данных размещалась на RAID-массиве 3 уровня общей ёмкостью 128 Гбайт, поддерживающем скорость 100 Мб/с,

В качестве объекта сопоставления выбрана СУБД-машина «Rinda» (фирма NTT, Япония), ее аналогами являются СУБД-машины Terada и Gamma.

Программа пользователя измеряет время от начала выполнения запроса до возвращения последнего ряда результатов. Все выполненные запросы были разбиты на 4 категории: простая выборка, объединение, функции Min (функция вычисления минимума) и Count (функция счёта). Получены зависимости затрат времени при реализации всех названных запросов для аналогов и разработанной СМБД и установлено, что се скоростное преимущество составляет три-четыре раза.

СМБД Rinda Terada Gamma

1 10 100 1000 п, тыс. рядов

Рис.2. Зависимость времени выполнения 1 %-ной выборки от числа рядов результата (Selection 1%)

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

т, с 50

40 30 20 10

/ X

Uc_*r Xs'

—СМБД -в— Rinda Terada -к— Gamma

1 10 100 1000 п, тыс. рядов

Рис. 3. Зависимость времени выполнения операций по выборке минимального значения без группировки данных от количества обрабатываемых кортежей (Min Scalar)

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

на СМБД нахождение минимума происходит параллельно и не требует дополнительных временных затрат.

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

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

В приложении размещен листинг программных средств для моделирования работы алгоритмов и устройств.

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

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

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

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

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

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

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

1. Довгаль, В. М. Проблема визуализации объектов [Текст] / В. М. Довгаль, В. Е. Сорокин // Материалы 2-й Межд. конф. «Оптико-электронные приборы и устройства в системах распознавания образов, обработки изображений и символьной информации» («Распознавание-1995»). Курск, 1995. С. 245-246.

2. Пат. РФ 2150740, МКИ7 G Об F 17/30. Устройство для реализации подстановок [Текст] / Сорокин В. Е. [и др.]. Опубл. 10.06.2000, Бюл. № 16.

3.Сорокин, В.Е.Архитектура символьной СУБД-машины [Текст] / В, Е. Сорокин // Материалы Межд. конф. «Актуальные проблемы компьютеризации в странах СНГ». Донецк: АРК-Ц, 2002, С. 70-78.

4. Сорокин, В.Е. Метод быстрой обработки двумерных массивов [Текст] / В.Е. Сорокин [и др.] // Материалы 6-й Межд. конф. «Оптико-электронные приборы и устройства в системах распознавания образов, обработки изображений и символьной информации» («Распознавание-2003»). Курск, 2003. С. 90-92.

5. Сорокин, В.Е. Процессор быстрых символьных вычислений [Текст] / В.Е. Сорокин [и др.] // Материалы 6-й Межд. науч.-техн. конф. «Медико-экологические информационные технологии-2003». Курск, 2003. С. 157-158.

6. Довгаль, В, М. Проблема построения символьных бриджеров для сопряжения разнородных компьютерных сетей. Ч. 1. Акселерация работы автономных продукций [Текст] / В. М. Довгаль, В.Е.Сорокин,

A. В, Шанцев // Телекоммуникации. 2004. № 3. С. 16-22.

7. Довгаль, В. М. Проблема построения символьных бриджеров для сопряжения разнородных компьютерных сетей. Ч. 2. Акселерация работы алгоритмических схем и архитектура аппаратных средств [Текст] /

B. М. Довгаль, В. Е. Сорокин, А. В. Шанцев // Телекоммуникации. 2004. №7. С. 5-13.

20 I-

РНБ Русский фонд

2007-4 9025

ИД №06430 от 10.12.01 Подписано в печать 22.04.05. Формат 60x84 1/16. Печать офсетная. Печ. л. 1,35. Тираж 100 экз. Заказа Курский государственный технический университет. Издательско-полиграфический центр Курского государственного технического университета. 305040, г. Курск, ул. 50 лет Октября, 9

ф ВВЕДЕНИЕ

Глава 1. Аналитический обзор современного состояния средств

СУБД и машин баз данных .Г

1.1. Общие положения: исторический очерк

1.2. Неоднородные многопроцессорные ма шины баз данных (МБД) 21 .|г 1.3. Параллельные машины баз данных

1.4. Побудительные причины исследования и сущность предлагаемого подхода к созданию МБД

1.5. Выводы

Глава 2. Структурно - лингвистические средства акселерации —

2.1. Понятийный базис продукционной алгоритмической системы

2.2. Классификация формул подстановок

2.3. Способы синтеза акселерационных форм представления продукций

2.4. Иллюстрация продукционной реализации операций реляционной алгебры

2.5. Способы сопоставления (поиска по образцу)

2.6. Способы сортировки

2.6.1. Классификация алгоритмов сортировки последовательное

2.7. Способ парной параллельной сортировочной транспозиции эле ментов и слияния отсортированных последовательностей

2.8. Выводы

Глава 3. Разработка аппаратных средств акселерации 3.1. Способ организации машины баз данных 3.2. Специализированное устройство сортировки

3.3. Специализированное устройство слияния

3.4. Специализированное устройство быстрого поиска позиций вхождений образцов.

ЗАЛ. Работа устройства поиска вхождений образца

3.5. Специализированное устройство модификации слов

3.6. Выводы

Глава 4. Алгоритмические средства устройств управления специализированными устройствами МБД и результаты исследования скоростных характеристик 4.1. Алгоритмы управления устройств сортировки и слияния

4.1.1. Алгоритм управления устройства сортировки

4.1.2. Алгоритм управления устройства слияния

4.2. Алгоритм управления устройства поиска вхождения

4.3. Алгоритм управления устройства модификации

4.4. Результаты исследования скоростных характеристик

4.4.1. Сопоставительный анализ ускорений разработанного устройства и аналога

4.4.2. Анализ скоростных характеристик устройства поиска

4.4.3. Анализ скоростных характеристик продукционного символьного процессора .J

4.5. Выводы

i Актуальность работы. Сбор релевантной информации, надежность её хранения, высокоскоростной доступ и обработка при минимально допустимой стоимости составляют основные направления в условиях глобальной информатизации и компьютеризации. Бурный рост объёмов, разнообразия типологий и сложности логических структур информации в современных компьютерных системах определяет необходимость в разработке новых методов и систем хра-У нения с быстрым откликом на запросы пользователей.

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

Решению проблем создания машин и систем баз данных и знаний посвящены работы М. Сенко, Я. Палмера, Г. Найсена, Э. Озкарахана, JI. Калини-ченко, Д. Поспелова и других исследователей как у нас в стране, так и за рубежом. ф Между тем, в существующих работах отсутствуют реализации машин баз данных, основанных на технологии обработки символьной информации.

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

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

Работа выполнялась в рамках НИР по Единому заказ-наряду и грантам Г00-4.2.15 и Г02-4.2.5, выполненных в Курском государственном техническом университете в период с 1999 по 2005 годы при непосредственном участии автора.

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

Для достижения указанной цели поставлены и решены следующие основные задачи:

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

- создание алгоритмических средств организации быстрых процессов сопоставления с образцом (поиск), работы продукций (поиск и модификация), сортировки и слияния;

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

- проведение экспериментальных исследований скоростных характеристик символьной машины баз данных.

Объектом исследования являются алгоритмические и аппаратные средства, поддерживающие процессы управления данными.

Предмет исследования составляют процессы преобразования информации в системах управления базами данных (СУБД).

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

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

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

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

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

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

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

Апробация работы. Результаты диссертационного исследования докладывались и обсуждались на:

- 2-й Международной конференции «Оптико-электронные приборы и устройства в системах распознавания образов, обработки изображений и символьной информации. Распознавание-1995» (Курск, 1995);

- Международной конференции «Актуальные проблемы компьютеризации в странах СНГ» (Донецк, 2002);

- 6-й Международной конференции «Оптико-электронные приборы и устройства в системах распознавания образов, обработки изображений и символьной информации. Распознавание-2003» (Курск, 2003);

- 6-й Международной научно-технической конференции «Медико-экологические информационные технологии-2003» (Курск, 2003).

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

Реализация и внедрение. Результаты диссертационной работы внедрены в НПО «Экран» (Москва), а также используются в учебном процессе Курского государственного технического университета в рамках курса «Высокопроизводительные вычислительные системы», что подтверждается актами о внедрении.

На защиту выносятся:

1. Акселерационные формы представления продукций, а также образцов для быстрых символьных вычислений и процессов сопоставления в контурах СУБД.

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

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

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

Структура и объём диссертации. Диссертация состоит из введения, четырех глав и заключения, изложенных на 167 страницах, содержит 57 рисунков, 2 таблицы, списка литературы из 75 наименований.

4.5. Выводы

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

В результате проведения эксперимента в конфигурации с раздельным использованием устройств СМБД для получения зависимости затрат времени от длины данных, соответственно, для основных функций: SELECTION 1% (выборка 1 процента данных); SELECTION 10% (выборка 10 процента данных); JOIN AselB (объединение двух отношений); JOIN CselAselB (объединение трёх отношений); MIN Scalar (скалярная операция нахождения минимума); MIN Group (групповая операция нахождения минимума); COUNT Scalar (скалярная операция СЧЁТ); COUNT Group (групповая операция СЧЁТ) - достигается скоростное преимущество в три-четыре раза по отношению к СУБД-машине Rinda ее аналогов: Terada и Gamma для всех перечисленных функций.

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

Установлено, что затраты времени на реализацию функции DECODE, реализованной в языке PL-SQL, поддерживаемом СУБД Oracle, в конфигурации с совместным функционированием устройства поиска и модификации с использованием акселерационных форм представления продукций уменьшаются до восемнадцати раз по сравнению с выполнением этой функции на марковском символьном процессоре.

157

ЗАКЛЮЧЕНИЕ

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

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

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

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

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

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

1. Довгаль, В. М. Проблема визуализации объектов [Текст] / В. М. Довгаль, В. Е. Сорокин // Материалы 2-й Межд. конф. «Оптико-электронные приборы и устройства в системах распознавания образов, обработки изображений и символьной информации» («Распознавание-1995»). Курск, 1995. С. 245-246.

2. Пат. РФ 2150740, МКИ7 G 06 F 17/30. Устройство для реализации подстановок [Текст] / Сорокин В. Е. [и др.]. Опубл. 10.06.2000, Бюл. № 16.

3. Сорокин, В. Е. Архитектура символьной СУБД-машины [Текст] / В. Е. Сорокин // Материалы Межд. конф. «Актуальные проблемы компьютеризации в странах СНГ». Донецк: АРК-Ц, 2002. С. 70-78.

4. Сорокин, В.Е. Метод быстрой обработки двумерных массивов [Текст] / В.Е. Сорокин [и др.] // Материалы 6-й Межд. конф. «Оптико-электронные приборы и устройства в системах распознавания образов, обработки изображений и символьной информации» («Распознавание-2003»). Курск, 2003. С. 90-92.

5. Сорокин, В.Е. Процессор быстрых символьных вычислений [Текст] / В.Е. Сорокин [и др.] // Материалы 6-й Межд. науч.-техн. конф. «Медико-экологические информационные технологии-2003». Курск, 2003. С. 157-158.

6. Довгаль, В. М. Проблема построения символьных бриджеров для сопряжения разнородных компьютерных сетей. Ч. 1. Акселерация работы автономных продукций [Текст] / В. М. Довгаль, В. Е. Сорокин,

A. В. Шанцев //Телекоммуникации. 2004. № 3. С. 16-22.

7. Довгаль, В. М. Проблема построения символьных бриджеров для сопряжения разнородных компьютерных сетей. Ч. 2. Акселерация работы алгоритмических схем и архитектура аппаратных средств [Текст] /

B. М. Довгаль, В. Е. Сорокин, А. В. Шанцев // Телекоммуникации. 2004. №7. С. 5-13.

160

1. Озкарахан, Э. Машины баз данных и управление базами данных: Пер. с англ. Текст. / Э. Озкарахан // М.: Мир, 1989. 487 с.

2. Su, S. Database machine and some issues on database management systems standart Text. / S. Su, H. Chang, P. Eischer, E. Lowenthal // AFIPS, NCC, USA, 1980.

3. Boral, H. Database machine Morphology Text. / H. Boral, S.Redfield // Proc. of the 11-th Int. Conf. on VLDB. Database machine Morphology , Stockholm, Aug. 1985.

4. Ozkarachan, E. Database machines and database management Text. / E. Ozkarachan // USA, Prentice Hall, 1986.

5. Hawthorn, P. B. Performance analysis of alternative database machine architectures Text. / P. B. Hawthorn, D. J. De Witt // IEEE Trans, of Software Eng.-Jan. 1982.-Vol. SE-8,No.l.

6. Калиниченко, Л. А. Машины баз данных и знаний. Текст. / Л. А. Калиниченко, В. М. Рыбкин // М.: Наука. Гл. ред. физ.-мат. лит., 1990. 248 с.

7. Калиниченко, Л. А. Методы и средства интеграции неоднородных баз данных. Текст. / Л. А. Калиниченко // М.: Наука, 1983.- 423 с.

8. Feng, Т. A. Very large data base computer Text. / T. A. Feng // IEEE Computer Soc. Workshop on Computer Architecture for Analysis and Image Database Management. Virginia, USA, 1981.

9. Day, K. Micro-based DBMS manages and relational database Text. / K. Day // Electronic Design. June 1982. - No. 3.

10. E. A. Ozlcarahan, L. A. Kerschberg I I Heterogeneous Technical Report TR-82-006, Dept. of Computer Science, Arizona State University, Tempe, 1998.

11. Ozlcarahan, E. A. Performance Evaluation of a Relational Associative Processor. Text. / E. A. Ozlcarahan, S. A. Schuster, К. C. Sevcik // ACM Transactions on Database Systems, 1999, Vol. 2, No. 2.

12. Kamibayashi, N. A. Database machine based on the data distribution approach Text. / N. A. Kamibayashi //AFIPS, NCC. USA, Virginia, 1997.

13. Kamibayashi, N. A. SPIRIT-3: an advanced relational data base machine introducing a novel data-staging architecture with tuple stream filters to process relational algebra Text. /N. A. Kamibayashi, K. Seo //AFIPS, NCC.—1998.

14. Hsiao, D. K. Database machine architecture on the Context of information technology Evolution Text. / D. K. Hsiao, S. Madnick // Proc. of the 3-rd Intern. Conf. on VLDB.- Japan, Tokyo, 1998.

15. Madnick, S. E. INFOPLEX hierarchical ecomposition of a large information management system using microprocessor complex Text. / S. E. Madnick // AFIPS, NCC.- 2001.

16. Seo, K. Look-ahead data staging architecture for relational data base machine Text. / K. Seo, A. Mikamatsu, H. Aiso, N. A. Kamibayashi // Proc. of 8-th Ann. Symp. Comput-Architecture.-May 1998.

17. Takeda, H. "An Accelerating Processor for Relational Operations," Text. / H. Takeda, T. Satoh // Proc. Int'l Conf. Databases, Parallel Architectures, and Their Applications. Mar. 1999, p. 559.

18. Shiokawa, S. "UfPS-ll/5E Series Mainframe" Text. / S. Shiokawa, Y. Obasht, A. Nagoya// Review of the ECL. Vol. 35, No. 6, June 2001, pp. 633-641.

19. Itoh, K. "DIPS-V30 Development." Text. / K. Itoh, R. Yazawa, Y. Fukumura // Review of the ECL, Vol. 34, No. 5, May 2000, pp. 587-593.

20. Aid, S. G. Parallel Sorting Algorithms Text. / S. G. Akl // Academic Press, New York. 1985.

21. Blasgenand, M. W. "Storage and Access in Relational Data Bases," Text. / M. W. Blasgenand, 1С. P. Eswaran // IBM System J. Vol. 16, No. 4, 2002, pp. 363377.

22. Kitsuregawa, M. "Application of Hash to Data Base Machine and Its Architecture" Text. / M. Kitsuregawa, M. Tanaka, T. Moto-oka // New Generation Computing, Vol. 1, No. 1, 2002, pp. 63-74.

23. McGregor, D. R. "High Performance Hardware for Database Systems in Systems for Large Data Bases" Text. / D. R. McGregor, R. G. Thomson, W. N. Dawson, P. C. Lockemann, E. J. Neuhold [eds.] // North-Holland, Amsterdam, 2001, pp. 103-116.

24. Satoh, T. "A Compact Multiway Merge Sorter Using VLSI Linear-Array Comparators" Text. / T. Satoh, H. Takeda, N. Tsuda // Proc. Int'lConf, Foundation Data Organization and Algorithms, June 1999, pp. 223-227.

25. Tsuda, N. "A Pipeline Sorting Chip," Text. / N. Tsuda, T. Satoh, T. Kawada // Proc. IEEE Int'l Solid-State Circuits Conf. IEEE CS Press. Los Alami-tos. Calif, 2001. pp. 270-271.

26. Maryanski, F. Backend database systems Text. / F. Maryanski // Computing Surveys.- March 1980.- Vol. 12, No. 1.

27. ЗЗ.Четверушкин, Б. H. Высокопроизводительные многопроцессорные вычислительные систем Текст. / Б. Н. Четверушкин // Вестник РАН, 2002, том.72. № 9. С. 786-794.

28. Пат. РФ 2150740, МКИ7 G 06 F 17/30. Устройство поиска вхождений Текст. / Сорокин В. Е. [и др.]. Опубл. 10.06.2000, Бюл. № 16.3 5.Коллинз, Г. М. Микроэлектронные технологии. Текст. / Г.М.Коллинз // Интрон-М, 2003. 271 с.

29. Зб.Ва, Б. У. ЭВМ для обработки символьной информации Текст. / Б. У. Ва, М. Б. Лоурай, Ли Гоцзе // ТИИЭР. 1989. т.77, № 4. С.5-40.

30. Эйсымонт, Л. К. Компьютеры для обработки символьной информации Текст. / Л. К. Эйсымонт // Зарубежная радиоэлектроника. 1990. №. 4. С.3-28.

31. Вагин, В. Н. Проект «ПАМИР» Текст. / В. Н. Вагин, В.Н.Захаров, Д.А.Поспелов и др. // Известия АН СССР. Техническая кибернетика. 1988. №2. с.161-171.

32. Довгаль, В. М. Методы модификации формальных систем обработки символьной информации. Текст. / В. М. Довгаль // Курск: Курск, гос. техн. унт, 1996.115 с.

33. Довгаль, В. М. Марковские системы обработки символьной информации Текст. / В. М. Довгаль // Известия вузов "Приборостроение". Т. 40, вып.2, 1997. С.55-58.

34. Марков, А. А. Теория алгорифмов. Текст. / А.А.Марков, М. Н. Нагорный // М.: Наука, 1984. 432 с.

35. Пат. РФ 2039375, МКИ6 G 06 F 17/00, 17/20. Устройство для реализации продукций Текст. / В. М. Довгаль [и др.] (Россия). Опубл. 09.07.95, Бюл. № 19.

36. Пат. РФ 2067315, МКИ5 G 06 F 15/20. Устройство для реализации подстановок Текст. / В. М. Довгаль [и др.] (Россия). Опубл. 27.09.96, Бюл. № 27.

37. Довгаль, В. М. Проблема построения символьных бриджеров для сопряжения разнородных компьютерных сетей. Часть 1. Акселерация работы автономных продукций Текст. / В. М. Довгаль, В. Е. Сорокин, А. В. Шанцев // Телекоммуникации. № 3. 2004. С. 16-22.

38. Довгаль, В. М. Акселерация обработки символьной информации Текст. / В. М. Довгаль, В. В. Малютин // Сборник материалов 6-ой Международной научно-технической конференции "Медико-экологические информационные технологии-2003", Курск, 2003. С. 174-177.

39. Довгаль, В. М. Метод синтеза продукций-акселераторов конструктивных процессов: Препринт 56-96 Текст. / В. М. Довгаль // Курск, гос. техн. ун-т. Курск, 1996. 11 с. 161.

40. Довгаль, В. М. Алгоритмический индикатор пересечения слов: Препринт 58-96 Текст. / В. М. Довгаль // Курск, гос. техн. ун-т. Курск, 1996. 6 с.

41. Довгаль, В. М. Конструктивные процессы, порождаемые продукциями с пересекающимися образцами и модификаторами: Препринт 63-96 Текст. / В. М. Довгаль // Курск, гос. техн. ун-т. Курск, 1996. 7 с.

42. Довгаль, В. М. Самоиндукционные процессы в схемах продукций: Препринт 63-96 Текст. / В. М. Довгаль // Курск, гос. техн. ун-т. Курск, 1996. 7 с.

43. Довгаль, В. М. Взаимодействие конструктивных процессов: Препринт 52-96 Текст. / В. М. Довгаль // Курск, гос. техн. ун-т. Курск, 1996. 7 с.

44. Писаненко, Р. И. Способы быстрого сопоставления с образцом Текст. / Р. И. Писаненко, В. М. Довгаль // Известия КГТУ. №2(9). 2002. С. 111-117.

45. Baeza-Yates, R. A. "Searching subsequences, Baeza-Yates R.A." Text. / R. A. Baeza-Yates // Theoretical Computer Science, 1991, Vol. 78, No. 2, p. 363-76.

46. Воуег, R. S. "A fast string searching algorithm" Text. / R. S. Boyer, J. S. Moore // Communications of the ACM, 1977, Vol. 20, No. 10, p. 762-72, October 1977.

47. Knuth, D. E. Fast pattern matching in strings Text. / D. E. Knuth, J. H. Morris (Jr), V. R. Pratt // SIAM Journal on Computing 6(1), 1977:323-350.

48. Horspool, R. N. Practical fast searching in strings Text. / R. N. Horspool Software//Practice & Experience, 10(6), 1980:501-506.

49. Smith, P. D. Experiments with a very fast substring search algorithm Text. / P. D. Smith // Software Practice & Experience 21(10), 1991:1065-1074.67.http://www.codenet.ru.

50. Марчук, Г. И. Модульная асинхронная развиваемая система: концепция Препринт N 86 Текст. / Г. И. Марчук, В. Е. Котов // ВЦ СО АН СССР. -1978.154 с.

51. Котов, В. Е. Введение в теорию схем программ Текст. / В. Е. Котов // Новосибирск, Наука, 1978, 258 с.

52. Котов, В. Е. Асинхронные вычислительные процессоры над памятью. Текст. / В. Е. Котов, А. С. Нариньяни // Кибернетика, 1966. № 3. С. 64-71.

53. Скотт, Урман Oracle9i. Программирование на языке PL/SQL: Пер. с англ. Текст. / У. Скотт// М.: Издательство "Лори", 2004, 544 с.

54. Грейвс, Марк Проектирование баз данных на основе XML: Пер. с англ. Текст. / М. Грейвс // М.: Издательский дом "Вильяме", 2002, 640 с.

55. Валиков, А. Н. Технология XSLT Текст. / А. Н. Валиков // СПб.: БХВ-Петербург, 2002, 544 с.74.http://www.intelligententerprise.com.

56. Пат. РФ 2246750, МПК7 G 06 F 7/08. Устройство для сортировки чисел /Довгаль В.М. и др. (Россия). Опубл. 20.02.05, Бюл. № 5.

57. ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ «КУРСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ»

58. УДК 681.3 На правах рукописи

59. СОРОКИН ВАЛЕРИЙ ЕВГЕНЬЕВИЧ

60. СТРУКТУРНО-ЛИНГВИСТИЧЕСКИЕ, АЛГОРИТМИЧЕСКИЕ И АППАРАТНЫЕ СРЕДСТВА АКСЕЛЕРАЦИИ СИМВОЛЬНОЙ МАШИНЫ БАЗ ДАННЫХ

61. Специальность 05.13.05 «Элементы и устройства вычислительной техники и систем управления»