А.Ю. Попов
4
щих, ускорение может быть достигнуто благодаря высокому внут-
реннему параллелизму СП.
• Синхронизация с вычислительным процессом в ЦП.
СП
функционирует под управлением собственной программы, выбирае-
мой им из локальной памяти команд. При выполнении ветвлений в
программе ЦП требуется обеспечение синхронизации кода в обоих
вычислительных узлах: СП и ЦП. Эта синхронизация выполняется на
основе передачи специальных команд перехода, реализующих меха-
низм сложных событий. Во втором случае СП должен ожидать от ЦП
передачу информации для выполнения некоторых операций, таких
как
Поиск
,
Добавление
,
Удаление
. В этом варианте используется
примитив синхронизации «порт завершения ввода-вывода», пред-
ставляющий собой аппаратную очередь. В третьем варианте взаимо-
действия ЦП ожидает результат выполнения операции от СП
(например,
Поиска
), для чего также используется примитив «порт
завершения ввода-вывода».
Принципы хранения и организации доступа к структурам в
СП.
Информация представляется в памяти данных СП в виде струк-
туры
B
+ дерева. Отличительной особенностью этого вида деревьев
является то, что данные хранятся исключительно на нижнем уровне,
а соответствующие им ключи организованы в виде непересекающих-
ся множеств. В отличие от программной реализации, при аппаратной
обработке
B
+ дерева его высота является постоянной и соответствует
максимуму для выделенного объема памяти. Это связано с необхо-
димостью реализации фиксированного количества аппаратных бло-
ков для обработки уровней дерева и хранения нескольких структур
разных размеров в единой локальной памяти. На всех уровнях, кроме
нижнего (уровень
n
–1),
B
+ дерево хранит границы подмножеств
ключей [Low, High], по которым можно определить, какая именно
вершина соответствует искомому значению ключа. Состав и алго-
ритмы обработки множеств ключей для уровней 0…
n
–2 и блоков
данных на уровне
n
–1 существенно отличаются (рис. 1). Обработку
множеств ключей для уровней 0…
n
–2 обеспечивает
Каталог
СП.
Данные уровня
n
–1 обрабатываются в
Операционном буфере
[4]. Все
основные операции выполняются в
B
+ дереве за
(log )
b
O n
операций,
где
b
— количество вершин на одном уровне дерева. Аппаратная ре-
ализация
B
+ деревьев в СП отличается от классической программной
реализации [5, 6] в части алгоритмов таких операций, как
Добавление
и
Удаление
.
Каждый уровень дерева, кроме нижнего, реализован в СП в виде
набора взаимосвязанных вершин, осуществляющих хранение и обра-
ботку информации о структуре дерева, которая загружается по мере
необходимости в
Каталог
СП. Для ускоренного поиска и модифика-
