Принципы реализации машин БД

Примером такой памяти является изделие фирмы Сименс, структурная схема

подключения которого к общей шине представлена на рис. 12.а., Наличие порта

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

память через общую шину из УМП. Ассоциативная память в этом изделии

содержит 64 параллельные линии обработки (шириной 8 разрядов каждая), так

что информация из памяти поступает в каждый из 64 процессорных элементов

побайтно (в виде столбца байтов длиной 256 К). Длина обрабатываемого слова

256К, общая емкость ассоциативной памяти 16 Мбайт. Модуль памяти,

обрабатываемой каждым процессорным элементом, 256 Кбайт. Каждый модуль

памяти имеет адрес на общей шине, и информация в него может записываться

автономно по первому порту. Кроме того, внутри столбца-своя адресация в

пределах 256К, доступная контроллеру ассоциативной памяти. Ассоциативный

поиск осуществляется синхронно всеми (или частично) процессорными

элементами.

Структура каждого процессорного элемента изображена на рис. 12.б. Каждый

процессорный элемент содержит АЛУ и тест-устройство, два входных регистра А

и В, регистр маски М и блок регистров С. Все эти устройства выходят на

внутреннюю шину памяти (М-шину). Процессорный элемент и модуль памяти

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

работой всех процессорных элементов, воспринимает результат и при поиске

постоянно фиксирует текущий адрес в пределах 256К, с которым 8 данный

момент работают процессорные элементы. Факт нахождения релевантной

информации в каждом процессорном элементе фиксируется в контроллере Для

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

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

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

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

[pic]

Рис. 12. Гибридная двухпортовая ассоциативная память:

а - общая схема; б - схема процессорного элемента

3. Использование процессора потоковой сортировки отношений для слияния

отношений. Например, в проекте Delta он предназначен для потокового слияния

двух сортированных страниц отношения со скоростью поступления кортежей

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

реализовано устройство соединения двух отношений (Delta).

Во многих проектах предлагается аппаратная реализация операций реляционной

алгебры на основе универсальных компараторных процессоров (компараторов).

Пример такого компаратора (проект DFRU) представлен на рис.13. Компаратор

(К) предназначен для реализации операций селекции, проекции, сужения и

соединения отношений и используется в процессорной матрице (рис. 9). Он

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

управляется потоком кортежей, поступающих по двум входным линиям побайтно.

Компаратор может находиться в разных состояниях, управляемых тремя

внутренними линиями. Он управляется микропрограммой, запускаемой входными

кортежами. Режим работы микропрограммы определяется текущим состоянием

компаратора. Компаратор содержит три микропрограммных процессора (модуля);

ввода, сравнения и выхода, и набор внутренних регистров (Доп. Р, БР).

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

кортеж побайтно в буфер или/и в компаратор (в зависимости от своего

внутреннего состояния). Дополнительные компараторы необходимы для анализа

управляющих битов (флагов), таких как признак окончания отношения, который

оканчивает обработку. В центральном компараторе происходит сравнение

значений заданных атрибутов из входных кортежей (побайтно). В компаратор

поступает не весь кортеж, а только сравниваемые значения. Этим управляет

входной модуль по своей микропрограмме, синхронизируясь по заданному

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

после сравнения заданных атрибутов компаратор задает выходному модулю

команду на вывод кортежей из соответствующих буферов. Вывод может

осуществляться:

на выходную шину, если сравнение было успешным;

в линию обратной связи (ЛОС), если, например, из входного модуля по

шине управления пришла команда о том, что в следующем кортеже второго

отношения то же значение атрибута соединения (для операции соединения) и

этот выводимый кортеж надо повторно с ним сравнить. При этом

соответствующая входная линия перекрывается и замыкается на ЛОС, пока на

входе не появится кортеж второго отношения с новым значением атрибута

соединения;

удаление текущего кортежа из выходной последовательности при неуспешном

сравнении (выходная линия замыкается на «землю»). Для операции соединения в

выходном модуле может выполняться сцепление выходных кортежей. Режим

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

процессоры (входной, компараторный и выходной) управляются входными

последовательностями кортежей через изменение внутренних состояний. При

этом определенная микропрограмма выполняется, если модуль находится в

соответствующем состоянии, зависящем от поступления входных кортежей.

[pic]

Рис. 13. Универсальный компараторный процессор для реляционных операций:

БР-а-разрядныа буферный регистр; Доп. Р - дополнительный регистр; К -

компаратор;

ЛОС - линии обратной связи

При выполнении операции селекции в Буфер 2 загружается «псевдокортеж»,

соответствующий заданному условию поиска. (Очевидно, таким образом можно

реализовать селекцию по условию, не содержащему дизъюнкций.) Кортежи

отношения, поступающие на Вх.1, пропускаются через компаратор, а

«псевдокортеж» циркулирует по ЛОС2, Буфер 2 и компаратору. Входной модуль

синхронизирует этот процесс. При успешном сравнении в компараторе кортеж

отношения посылается на Вых.1, иначе на «землю». Аналогично рассмотренному

реализован реляционный процессор РП (см. рис. 3) в МБД Delta, но с большим

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

4. Аппаратная реализация потоковой фильтрации данных непосредственно в

каналах УМП. Такая фильтрация позволяет снизить объемы данных, передаваемых

из массовой памяти на обработку, что является существенным источником

повышения производительности МБД в целом. Потоковые процессоры фильтрации

(фильтры) должны удовлетворять следующим требованиям:

скорость обработки должна соответствовать скорости чтения НМД, чтобы

избежать холостых оборотов МД;

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

дорожку МД для обеспечения непрерывности чтения;

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

условию данные (горизонтальная фильтрация);

возможность формировать на выходе часть входной записи в соответствии с

заданным условием (вертикальная фильтрация);

задание поисковых условий в виде дизъюнктивной нормальной формы

элементарных поисковых условий или в виде поисковых образов;

объем поисковых условий допилен определяться допустимой скоростью

обработки.

Достаточно полный обзор существующих процессоров фильтрации.

5. Устранение препятствия в увеличении производительности

многопроцессорной МБД с двумя уровнями обработки и системной буферной

памятью за счет улучшения системы коммутации и связи процессоров обработки

с СБП и между собой. Это определяется интенсивностью обмена данными между

процессорами и СБП и объемом этих данных, которые, как правило, являются

частями файлов (отношений БД). Кроме этого организация параллельной работы

процессоров требует интенсивного обмена сообщениями между процессорами.

Ориентировочные требования к системе коммутации в МБД с высокой степенью

параллельности:

скорость передачи данных - 10-80 Мбайт/с;

число подключаемых автономных банков памяти - 100;

число подключаемых процессоров обработки - 100;

отсутствие конфликтов.

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

высокоскоростных сетей коммутации (до 10^3 входов) и реализации на их

основе многопортовой системной буферной памяти для МВД.

Фильтры представляют собой технические или программные средства для

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

данных выбор по условию соответствует операциям проекции и селекции

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

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

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

Фильтры, однако, позволяют проверять более сложные условия, чем «равно»

(для хэширования возможна только такая проверка), «не равно», «больше»,

«меньше». Фильтры не требуют предварительной структуризации данных. Вместе

с тем использование фильтров предполагает полный просмотр отношения (или,

если в базе хранятся инвертированные файлы, полный просмотр значений

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

с индексированием и хэшированием.

Общая схема использования фильтров следующая. Процессор, анализирующий

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

специальный процессор (или группу процессоров), который является

программируемым фильтром. Этот процессор может быть как специализированным,

так и процессором общего назначения.

Затем фильтр читает последовательно кортежи отношения, проверяя на них

заданное условие и отбирая удовлетворяющие этому условию кортежи.

Отобранные (релевантные) кортежи передаются другим процессорам для

дальнейшей обработки. Обработка может осуществляться параллельно с работой

фильтра.

В ряде проектов МЕД используются фильтры, которые моделируют для

проверки условий конечные автоматы. При такой реализации скорость проверки

условия практически не зависит от его сложности (если размер памяти

фильтра достаточен для моделирования конечного автомата, проверяющего

условие)

Бинарные операции (объединение, пересечение, соединение) над

отсортированными отношениями также могут быть реализованы с помощью

фильтров.

Специализироьанный фильтр работает приблизительно в два раза быстрее,

чем происходит загрузка входного буфера с диска. В процессе загрузки

фильтр может читать уже загруженную часть памяти. Кэш-память служит

промежуточной для обмена между дисковой памятью и буферами.

Когда в качестве фильтрующего процессора используется процессор общего

назначения, входной буфер разбивается на два. Контроллер загружает блоки

входного файла поочередно в один из двух буферов. Загрузка ведется

непосредственно с диска, так как фильтрация идет приблизительно в три раза

медленнее чтения. Кэш-память в этом случае не нужна. Результат фильтрации

записывается в один из двух выходных буферов. По заполнении буфера его

содержимое сбрасывается на диск.

К недостаткам фильтров, моделирующих конечные автоматы, следует отнести

высокие требования к размерам памяти фильтра.

Другой способ проверки Условий осуществляется прямым фильтром, структура

которого соответствует структуре проверяемого условия. Основными блоками

фильтра являются компаратор, управляющее устройство и логическое

устройство. Компараторы проверяют истинность простых условий. Их число

ограничено и фиксировано в аппаратуре. Современная технология СБИС

позволяет строить прямые фильтры с числом компараторов порядка 100.

Управляющее устройство организует работу фильтра, логическое устройство

обрабатывает полученные значения и генерирует окончательное значение

истинности сложного условия. На вход компаратора подается запись вида

или

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

является признак ИСТИНА или ЛОЖЬ.

Передаваемое в фильтр формализованное условие представлено в

дизъюнктивной или конъюнктивной нормальной форме. Для определенности будем

говорить далее о дизъюнктивной нормальной форме. В этом случае условие

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

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

постепенно формируется окончательный результат проверки всего сложного

условия.

С каждым компаратором соединен логический блок, который вычисляет

очередное промежуточное значение окончательного результата по результату

работы компаратора, предыдущему промежуточному значению и логической

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

компараторов и логических блоков.

Управляющее устройство выполняет следующие функции:

декодирование, вычисление длины операндов и подготовка данных к

вычислениям;

определение концов операндов и установка соответствующих признаков;

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

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

основной памяти.

Операнды проще всего размещать во внешней памяти, общей для всех

компараторов. Время обращения к общей памяти налагает в этом случае

ограничения на число компараторов в фильтре. Если время ввода одной записи

100 не, а время работы компаратора 400 не, то нет смысла иметь более

четырех компараторов. Использование СБИС-технологии позволяет обеспечить

каждому компаратору достаточную внутреннюю память (порядка 256 байт).

Существует ряд проблем, которые находятся пока за рамками исследований по

МВД.

1. Повышение эффективности хранения данных в больших БД часто связывают

со сжатием данных, специальным кодированием данных и т. п. Но

псевдоассоциативный поиск и фильтрация данных непосредственно в УМП трудно

реализуемы, если данные в УМП хранятся в сжатом и закодированном виде. Пока

только в единственном проекте DS DBS предпринята попытка решить эту

проблему.

2. При разработке МЕД совсем не рассматривается проблема обеспечения

интерактивного взаимодействия пользователя с БД посредством графического

дисплея. Если терминалы работают под управлением МБД, то сложность ОС МБД

существенно возрастает, что может привести к деградации общей

производительности МБД. Если терминалы пользователя работают под

управлением главной ЭВМ, то растет объем данных, передаваемых от МБД в

главную ЭВМ и наоборот.

3. Повышение производительности МВД обычно связывается со скоростью

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

транзакций. При этом выдача данных терминальному пользователю начинает

осуществляться только после выполнения последней реляционной операции в

последовательности операций, соответствующих запросу. Иногда для принятия

решения достаточно нескольких кортежей, являющихся результатом этой

последовательности (дерева запроса). Увеличение реактивности МБД при выдаче

этих нескольких кортежей, удовлетворяющих запросу, часто противоречит

увеличению традиционной пропускной способности МВД. Решить эту проблему

можно только реализацией в МВД такого режима потоковой обработки отношений,

при котором реляционная операция начнет выдавать результирующие кортежи, не

ожидая появления целиком сформированных отношений-операндов. Для ряда

операций реляционной алгебры сложности 0(n^2) (где n-кардинальность

отношений-операндов) реализация такого режима трудно разрешима, например

для операции сортировки отношений.

4. Обеспечение целостности БД при параллельных обновлениях в МВД с

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

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

5. Разработка единой методологии проектирования МВД исходя из заданного

набора требований (объем и тип БД, типы и частота запросов, сфера

применения и т. п.). В настоящее время проектирование МВД основано на

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

производительности, такие как для параллельных систем вычислительного типа.

Наличие указанных проблем в проектировании МВД заставляет некоторых

авторов на вопрос «Существует ли идеальная МБД?» ответить следующим

образом: «Идеальная МБД, если она существует, должна быть, очевидно,

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

универсально в каждой области применений».

Лучшей рекомендацией в данном случае является разработка семейства МВД,

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

применения. Например, мультипроцессорная машина псевдоассоциативного поиска

в больших файлах библиографических систем или многопроцессорные МВД для

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

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

экономических приложений в задачах управления, где осуществляется доступ к

структурированным данным из прикладной программы, функционирующей в главной

ЭВМ.

Страницы: 1, 2, 3