Принципы реализации машин БД (стр. 4 из 6)

Рис. 5.9. Структура подсистемы потоковой обработки в МВД DFRU

Управление выполнением запросов при этом должно происходить собственно потоками данных, что облегчает задачу программного контроля выполнением операций, синхронизации их и т. п. Например, в проекте DFRU предпринята попытка аппаратно реализовать потоковую обработку в регулярной структуре обрабатывающих процессоров (рис. 9). Основным обрабатывающим элементом является универсальный компаратор кортежей (К). В матрице компараторов кортежей, соединяемых коммутирующими сетями, возможна динамическая коммутация выходов процессоров обработки i-го уровня со входами процессоров (i+1)-го уровня. В каждой строке матрицы по одному арифметическому процессору (АП) для реализации агрегатных функций. Связи между процессорами устанавливаются в соответствии с дугами дерева запроса (дерева реляционных операций). Это позволяет отображать дерева запроса в дерево процессоров, вырезаемых в данной матрице, так что каждой операции назначается один процессор обработки. После этого исходные отношения в потоке читаются из подсистемы массовой памяти и обрабатываются конвейерно в настроенном дереве процессоров, так что кортежи, образованные в операции i-го уровня, через коммутирующую сеть попадают в соответствующий процессор (i+l)-го уровня. На рис. 10 проиллюстрирован этот процесс для следующего запроса: «Выдать имена поставщиков, которые поставляют более 100 деталей типа I» применительно к трем исходным отношениям:

(RI) ПОСТАВЩИК (КОД ПОСТАВЩИКА, имя);
(R2) ДЕТАЛЬ (КОД-ДЕТАЛИ, ТИП-ДЕТАЛИ, НАИМЕНОВАНИЕ);
(R3) ПОСТАВКА (КОД-ДЕТАЛИ, КОД-ПОСТАВЩИКА, КОЛИЧЕСТВО).

Рис. 10. Реализация дерева операций в матрице процессоров

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

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

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

высокая скорость и близкая к линейной зависимость времени сортировки от объема отношения;

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

конвейерный режим обработки потока данных;

наличие внутренних буферов объемом не менее страницы отношения (64, 128, 256 Кбайт);

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

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

Необходимо отметить, что даже применение аппаратных потоковых сортировщиков не решает полностью проблему потокового выполнения бинарных операций. Сортировщик может начать выдачу кортежей сортированного отношения только после получения на входе последнего кортежа исходного отношения, да и то с задержкой. Например, процессор сортировки в Delta имеет задержку (2lm+N-1)t, где l-длина кортежа в байтах, t=ЗЗО нс-время пересылки байта между сортирующими элементами, m-число сортируемых кортежей, N - число сортирующих элементов. Таким образом, наличие даже аппаратной потоковой сортировки прерывает и замедляет общий поток кортежей между реляционными операциями. А любое замедление входного потока одного отношения-операнда требует для другого операнда бинарной операции наличия промежуточного буфера. Поэтому конвейер кортежей при потоковой обработке должен иметь вид «растягиваемых рукавов» (рис. 11). Все это может свести к минимуму преимущества потоковой обработки.

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

Примером такой памяти является изделие фирмы Сименс, структурная схема подключения которого к общей шине представлена на рис. 12.а., Наличие порта обычной адресации позволяет осуществлять подкачку данных в ассоциативную память через общую шину из УМП. Ассоциативная память в этом изделии содержит 64 параллельные линии обработки (шириной 8 разрядов каждая), так что информация из памяти поступает в каждый из 64 процессорных элементов побайтно (в виде столбца байтов длиной 256 К). Длина обрабатываемого слова 256К, общая емкость ассоциативной памяти 16 Мбайт. Модуль памяти, обрабатываемой каждым процессорным элементом, 256 Кбайт. Каждый модуль памяти имеет адрес на общей шине, и информация в него может записываться автономно по первому порту. Кроме того, внутри столбца-своя адресация в пределах 256К, доступная контроллеру ассоциативной памяти. Ассоциативный поиск осуществляется синхронно всеми (или частично) процессорными элементами.

Структура каждого процессорного элемента изображена на рис. 12.б. Каждый процессорный элемент содержит АЛУ и тест-устройство, два входных регистра А и В, регистр маски М и блок регистров С. Все эти устройства выходят на внутреннюю шину памяти (М-шину). Процессорный элемент и модуль памяти реализованы двумя кристаллами. Общий контроллер управляет синхронной работой всех процессорных элементов, воспринимает результат и при поиске постоянно фиксирует текущий адрес в пределах 256К, с которым 8 данный момент работают процессорные элементы. Факт нахождения релевантной информации в каждом процессорном элементе фиксируется в контроллере Для последующего извлечения информации. В такой ассоциативной памяти наиболее эффективно реализуется операция поиска вхождений по заданному образцу. Особый интерес представляет использование такой памяти в машинах баз знаний, где операция поиска вхождений по образцу является основной.

Рис. 12. Гибридная двухпортовая ассоциативная память:
а - общая схема; б - схема процессорного элемента

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

Во многих проектах предлагается аппаратная реализация операций реляционной алгебры на основе универсальных компараторных процессоров (компараторов). Пример такого компаратора (проект DFRU) представлен на рис.13. Компаратор (К) предназначен для реализации операций селекции, проекции, сужения и соединения отношений и используется в процессорной матрице (рис. 9). Он имеет два буфера объемом, достаточным для помещения одного кортежа, и управляется потоком кортежей, поступающих по двум входным линиям побайтно. Компаратор может находиться в разных состояниях, управляемых тремя внутренними линиями. Он управляется микропрограммой, запускаемой входными кортежами. Режим работы микропрограммы определяется текущим состоянием компаратора. Компаратор содержит три микропрограммных процессора (модуля); ввода, сравнения и выхода, и набор внутренних регистров (Доп. Р, БР). Входной модуль читает кортежи на своих входных линиях и направляет каждый кортеж побайтно в буфер или/и в компаратор (в зависимости от своего внутреннего состояния). Дополнительные компараторы необходимы для анализа управляющих битов (флагов), таких как признак окончания отношения, который оканчивает обработку. В центральном компараторе происходит сравнение значений заданных атрибутов из входных кортежей (побайтно). В компаратор поступает не весь кортеж, а только сравниваемые значения. Этим управляет входной модуль по своей микропрограмме, синхронизируясь по заданному расположению этих сравниваемых значений. Весь кортеж находится в буфере, и после сравнения заданных атрибутов компаратор задает выходному модулю команду на вывод кортежей из соответствующих буферов. Вывод может осуществляться:

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

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