Машины баз данных

Рязанская государственная радиотехническая академия Кафедра ЭВМ

Машины баз данных

курсовой проект по дисциплине

«Организация ЭВМ и систем»

Выполнил:

ст. гр. 140

Калинин Д.В.

Проверил:

Волковыский А.В.

Рязань, 2001

Проектирование МБД

1. Задание

1.1 Структура базы данных

Основную часть БД составляет таблица Tab1, содержащая 64 строки. Атрибуты БД описываются табл.1. В состав БД включена таблица Tab2, формируемая из Tab1 операцией селекции.

1.2 Выполняемые операции

— Sel (F1>C)&(F6=D)

1.3 Способы доступа

— параллельный (по срезам) — побитовый;

— последовательный (по адресам) — 4-байтовый.

1.4 Уточнение задания

Компаранд с[14] - 14-байтовая (112-битная) символьная константа.

Команда Selection (селекция) формирует таблицу Tab2 из строк Tab1, удовлетворяющей заданным условиям. Условие (ИМЯ C) выделяет строки, в которых атрибут ИМЯ, рассматриваемое как 14-байтовая (112-битная) строка символов.

Таким образом, операция Selection сводится к последовательности двух операций:

MARK.NE (ИМЯ, c[14]) — отметка записей, удовлетворяющих условию;

SEL (Tab2, Tab1) marked — передача отмеченных строк из Tab1 в Tab2.

Таблица 1. Структура базы данных.

2. Организация МБД

2.1 Структура памяти и адресация данных

В качестве памяти МБД используется ассоциативное запоминающее устройство (АЗУ). АЗУ разделено на два блока АЗУ1 и АЗУ2, допускающие независимое обращение. Каждый блок содержит 64 строки по 128 байта в каждой. В АЗУ1 размещается таблица Tab1, в АЗУ2 — Tab2. Строка таблицы содержит 92 байтов. Остальные 36 могут использоваться как резервные.

При параллельном (ассоциативном) доступе каждый блок АЗУ рассматривается, как содержащее 736=2E0Н 1-битных среза по 64 бита в каждом. Адресом поля считается адрес старшего среза. При последовательном (адресном) доступе блоки АЗУ рассматриваются как состоящие из 64 строк по 32 4-байтовых слов в каждой. Адресом строки считается адрес её левого слова, адресом поля — адрес слова, в котором оно начинается. Поля могут пересекать границы слов. Строки таблиц Tab1 и Tab2 содержат по 92-байтов и считаются состоящими из 23-х слов .

Для АЗУ определены операции чтение среза Rds, запись среза Wrs, чтение слова Rdw, запись слова Wrw.

Для выполнения операций МБД, указанных в задании, используются для АЗУ1 чтение среза Rds1, чтение слова Rdw1, а для АЗУ2 — запись слова Wrw2. Обращение к АЗУ1 и АЗУ2 может происходить одновременно.

2.2 Структурная схема МБД

Структурная схема проектируемой МБД приведена на рис. 1. В состав МБД входят два блока ассоциативной памяти АЗУ1 и АЗУ2, управляющий процессор, схема адресации слов и срезов, 64 исполнительных процессора для поиска строк, удовлетворяющих заданным условиям, блок маркеров, включающий регистры маркеров MRK и HLP и вспомогательные элементы, схему поиска отмеченных строк СПОС, блок регистров слов PгW1 и PгW2, исполнительный процессор вычисления суммы ИП SUM.

На управляющий процессор из центрального процессора ЦП поступают коды операций, значения компарандов, адреса обрабатываемых полей (cрезов или слов) и сигнал СТАРТ. Из УП МБД в ЦП выдается сигнал «конец операции».

Из УП на АЗУ поступают сигналы чтения срезов Rds, чтения слов Rdw и записи слов Wrw. На схему адресации поступают из УП начальные адреса слов и срезов. Кроме того, УП вырабатывает различные управляющие сигналы для исполнительных устройств МБД. Значение суммы из ИП SUM поступает в центральный процессор.

Рис. 1 Структурная схема МБД

3. Разработка алгоритмов операций и исполнительных процессов

3.1 Поиск в диапазоне (MARK.DI)

Поиск по условию Low < attr < High, где Low и High границы диапазона, возможен по нескольким алгоритмам.

Алгоритм 1:

М 1: = 11 … 1; Н: = 11 … 1; С: = Low;

SGE (М1); /*поиск больших или равных с отметкой в маркере М1*/

М2: = 11 … 1; Н: = 11 … 1; С: = High;

SLE (М2); /*поиск меньших или равных с отметкой в М2*/.

М1: = М1 & М2; */результат*/

end.

Алгоритм требует трех маркеров — М1, М2 и Н.

Алгоритм 2:

М: = 11 … 1; Н: = 11 … 1; С: = Low;

SGE (М);

С: = High; Н: = М; /*записи, удовлетворяющие условию Attr > = Low*/

SLE (М); /*поиск записей, удовлетворяющих условию Attr < = High, среди отмеченных */

end.

Для этого алгоритма достаточно двух маркеров.

3.2 Схема адресации срезов

При выполнении операций MARK. NE над полем ИМЯ адреса срезов AddrS поступают из регистра адреса срезов в составе УП МБД.

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

Таблица 2. Формирование адреса среза

/

Рис. 2 Схема формирования адреса среза

3.4 Исполнительные процессоры для операции MARK. NE

ИП MARK. NE имеются для каждой as строк АЗУ. Все работают параллельно. Схема ИП С триггерами HLP[j] и MRK[j] приведена на рис. 3. В схеме использованы следующие обозначения:

SB — 4-разрядный двоичный вычитатель;

Thj, Tmj — R-S триггеры маркеров HLP, MRK с выходами h и m.

S[j] - тетрада j очередного среза;

c[i] - тетрада i компоранда;

Df — разность S[j]-C[i], состоящая из битов f3, f2, f1, f0;

Br — признак заема;

Sth, Rsth, Stm, Rstm — сигналы сброса и установки триггеров Th, Tm;

rh, rm — внутренние сигналы комбинационной схемы для формирования сигналов Rsth, Rstm;

y1,y2,…, y6 — общие управляющие сигналы для всех ИП.

По этим сигналам выполняются микрооперации:

y1: MRK := 00…0B; / * Сброс MRK*/

y2: HLP := 11…1B; / *установка HLP*/

y3: S := АЗУ1 [AddrS]; /*Чтение среза*/

y4: MRK:= HLP; / * Передача MRKHLP*/

y5: AddrS := AddrS+1; /*Адрес следующего среза*/

y6: HLP := HLP & Rh; / * Сброс части битов HLP*/

Df?0 означает неравенство C[i] и S[j], заем Br=1, означает, что C[i]>S[j].

Комбинационная схема описывается логическими выражениями:

Рис 3. Исполнительный процессор операций Mark. NE

rh = f3 v f2 v f1 v f0;

rm = Br & h;

Sth = y2 v (m & y5) v (m & y4);

Rsth = rh v y6 v (m & y4);

Stm = h & y5;

Rstm = (rm & y3) v y1;

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

3.5 Операция SEL

Операция заключается в передаче отмеченных строк Tab1 в Tab2.

Общий алгоритм операции:

LAddr1 := 0;

LAddr2 := 0; /*начальные адреса строк Tab1, Tab2*/

For j:=0 to 63 do

{ If MRK[j]=1 then do

{

Line MOV; /*передача строки*/

LAddr2 := LAddr2+1; /*инкремент адреса строки Tab2*/

};

LAddr1:=LAddr1+1; /*инкремент адреса строки Tab1*/

}.

Здесь LAddr- 6-битный адрес строки. Полный адрес содержит 9 бит и состоит из адреса строки LAddr и счетчика 4-байтовых слов WC. Разрядность счетчика слов — 3 бита. Инкремент LAddr1 происходит в каждом такте, а инкремент LAddr2 — только в случае отмеченных строк.

Поиск отмеченных строк может быть выполнен путем сдвига MRK. Признаком отметки является бит MRK[j]=1. При переходе к следующей строке MRK сдвигается на 1 бит влево. При сдвиге стираются ставшие ненужными метки.

Поиск выполняется за 64 такта независимо от числа отмеченных строк. Его можно ускорить с помощью схемы, называемой «искатель самой левой единицы», которая находит самую левую единицу в двоичной слове и возвращает двоичной код ее порядкового номера n. При большой длине слова искатель может быть введен для k его старших битов. При отсутствии единиц в группе вырабатывается сигнал NO₁.

Алгоритм операции SEL меняется следующим образом:

LAddr1 := 0;

LAddr2 := 0;

While (MRK? 0) do

{

if NO₁ = 1 then do

{

MRK := MRK shl k;

LAddr1 := LAddr1 + k;

}

Else do

{

MRK := MRK shl k;

LAddr1 := LAddr1 + n;

Line MOV;

LAddr1 := Laddr + 1;

LAddr2 := LAddr2 + 1

};

}.

Рис. 5. Схема поиска отмеченных строк Таблица 3: Описание схемы искателя

Схема поиска отмеченных строк СПОС приведены на рис. 5. Выходы битов 0−7 MRK поступают на вход искателя ИСК. Код номера левой единицы n и сигнал NO₁ поступают на схему адресации и на управляющий вход с двигателя СДВ.

Искатель ИСК представляет собой логическую схему, описываемую таблицей 3 и логическими выражениями 1 и 2, где m0, m1, …, m7 — выходы старших битов MRK, а n1, n2, n3, NO₁ — выходы искателя.

M1 = m0 m1

M2 = m0 m1 m2

M3 = m0 m1 m2 m3

M4 = m0 m1 m2 m3 m4

M5 = m0 m1 m2 m3 m4 m5 (1)

M6 = m0 m1 m2 m3 m4 m5 m6

M7 = m0 m1 m2 m3 m4 m5 m6 m7

M8 = m0 m1 m2 m3 m4 m5 m6 m7

n1 = M4 M5 M6 M7

n2 = M2 M3 M6 M7 (2)

n3 = M1 M3 M5 M7

NO₁ = M8

Передача отмеченной строки происходит при NO₁ = 0, после чего находится следующая метка. При NO₁=1 MRK сдвигается на 8 бит влево, а передача строки не выполняется. Для получения адреса отмеченной строки к текущему адресу LAddr1 прибавляется значение n (n=0, 1, …, 7). При отсутствии отметок в старшем байте (NO₁=1) LAddr1 увеличивается на 8. Инкремент LAddr2 при этом не производится. При NO₁=0 после передачи строки LAddr1 и LAddr2 одновременно увеличиваются на 1.

Передача одного слова из Tab1 в Tab2 выполняется в 3 такта:

чтение слова W из Tab1;

запись W в Tab2;

инкремент счетчика слов WK.

Передача строки из 7-и слов занимает 21 такт. Ускорение передачи возможно при совмещении микроопераций чтения, записи и инкремента.

Для этого используются 4 счетчика слов WC1, WC2, WC3, WC4; 2 регистра слова РгW1, РгW2, а также средства для коммутации и модификации адресов и данных. Упрощенная схема ускоренной передачи строк приведена на рис. 6. На схеме показаны блоки памяти АЗУ1 и АЗУ2 с регистрами РгW1 и РгW2 и схемой адресации слов.

Выбор регистров слов для чтения или записи производится с помощью демультиплексора DMX и мультиплексора MX3. Схема адресации осуществляет выбор и модификацию адресов строк LAddr1 и LAddr2 и счетчиков слов WC1, WC2, WC3, WC4. Для формирования адреса очередной строки используется сумматор СМ, на один из входов СМ поступает сигнал NO₁ и код позиции отмеченной строки, формируемый схемой поиска отмеченной строки. Формирование и модификация адресов происходит по сигналам управляющего процессора (на схеме не показаны).

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

WC1:=0; WC2:=1; WC3:=0; WC4:=1;

Строка передается за 8 тактов:

Такт 1: РгW1 := АЗУ1[WC1]; /*чтение слова W0*/

Такт 2: РгW2 := АЗУ1[WC2]; /*чтение W1*/

АЗУ1[WC3] := РгW1; /*запись W0*/

WC1:= WC1+2; /*инкремент адреса чтения*/

Такт 3: РгW1 := АЗУ1[WC1]; /*чтение W2*/

АЗУ[WC4] := РгW2; /*запись W1*/

WC2 := WC2+2; /*инкремент адреса чтения*/

WC3 := WC3+2; /*инкремент адреса записи*/

Такт 4: РгW2 := АЗУ1[WC2]; /*чтение W3*/

АЗУ2[WC3] := РгW1; /*запись W2*/

WC1 := WC1+2; /*инкремент адреса чтения*/

WC4 := WC4+2; /*инкремент адреса записи*/

Такт 5: совпадает с тактом 3; /*чтениеW4, записьW3*/

Такт 6: совпадает с тактом 4; /*чтениеW5, записьW4*/

Такт 7: совпадает с тактом 3; /*чтениеW6, записьW5*/

Такт 8: АЗУ2[WC3] := РгW1; /*запись W6*/

Рис. 6. Схема ускоренной передачи строк

4. Управляющий процессор

На УП МБД из ЦП поступают коды операций, значения компарандов, адреса обрабатываемых полей (начальные адреса слов и срезов). В нашем случае выполняются всегда две операции Sel и Mark. NE над заранее известными полями, поэтому нет необходимости в указании адресов, а операции инициируются сигналом Start Sel. Компаранды C и D поступают из ЦП на внешнюю шину УП. Проектирование УП производится на основе кодированных граф — схем алгоритмов (ГСА) выполняемых операций. УП организован на базе микропрограммного автомата (МПА) с жесткой логикой, а именно МПА Мили.

4.1 Структура УП

В состав УП (рис.11) входят блок регистров БР и микропрограммный автомат с тактовым генератором ТГ. ТГ запускается сигналом Start из ЦП. На вход МПА поступают тактовые сигналы из ТГ и сигналы логических условий {x} из исполнительных процессов. С выхода МПА снимаются две группы управляющих сигналов — внутренние {Yin} для блока регистров и {Yout} для ИП.

В состав БР входят регистр компаранда РгComp, мультиплексор тетрад МХТ, регистр адреса среза AddrS, счетчик тетрад СТТ, указатель номера шага Step, триггер признака операции MARK. NE NE и признак останова HLT.

Значения компарандов поступают в РгComp через порты Port C и Port D. AddrS, CTT, Step и NE устанавливаются внутренними сигналами ИП. Признак HLT устанавливает МПА при поступлении соответствующих сигналов из ИП. Выход HLT подается на вход ЦП как сигнал окончания операции EOP.

Рис. 11 Управляющий процессор

4.2 Граф-схема алгоритма и схема МПА

Кодированная ГСА операции MARK. NE с отметкой состояний МПА Мили представлена на рис. 12. Описание операторов, микроопераций (МО) и логических условий ЛУ даны в табл.5,6,7.

Прямая структурная таблица МПА приведена в таблице 8.

Рис. 12. Кодированная ГСА операции MARK. NE

машина база адрес строка процессор

Таблица № 6. Описание микроопераций (МО)

Таблица № 8. Структурная таблица МПА

а исх. — исходное состояние

а пер. — состояние перехода

d — функция возбуждения

Матрица `И'

Матрица `ИЛИ'

Кодированная ГСА операции MARK. NE с отметкой состояний МПА Мили представлена на рис. 13. Описание операторов, микроопераций (МО) и логических условий ЛУ даны в табл.9.

Прямая структурная таблица МПА приведена в таблице 10.

Рис. 13. Кодированная ГСА операции SEL

Таблица № 9. Описание микроопераций (МО)

Таблица № 10. Структурная таблица МПА

а исх. — исходное состояние

а пер. — состояние перехода

D — функция возбуждения

1. Цифровые радиоприемные системы / Под ред. М. И. Жодзишского. М.: Радио и связь, 1990. 208 с.

2. Повышение эффективности мощных радиопередающих устройств / Под ред. А. Д. Артыма. М.: Радио и связь, 1987. 175 с.

3. Гольденберг Л. М., Матюшкин Б. Д., Поляк М. Н. Цифровая обработка сигналов: Учеб. пособие для вузов. М.: Радио и связь, 1990. 256 с.

4. Семенов Б. Ю. Современный тюнер своими руками. М.: СОЛОН_Р. 2001. 352 с.

5. Бродин В. Б., Калинин А. В. Системы на микроконтроллерах и БИС программируемой логики. М.: ЭКОМ. 2002.399 с.

6. Новиков Ю. В., Калашников О. А., Гуляев С. Э. Разработка устройств сопряжения для персонального компьютера типа IBM PC. М.: ЭКОМ. 2000 222 с.

7. Дингес С. И. Мобильная связь: технология DECT. М.: СОЛОН-Пресс. 2003. 266 с.

8. Проектирование радиопередатчиков: Учеб. пособие для вузов. / Под ред. В. В. Шахгильдяна. М.: Радио и связь. 2000. 654 с.

9. Солонина А., Улахович Д, Яковлев Л. Алгоритмы и процессоры цифровой обработки сигналов. СПб.: БХВ-Петербург. 2001. 455 с.

10. Тяпичев Г. Компьютер на любительской радиостанции. С-Пб.: БХВ-Петербург. 2002. 442 с.

11. Кириллов С. Н., Бодров О. А., Макаров Д. А. Стандарты и сигналы средств подвижной радиосвязи. Рязань: РГРТА. 1999.

12. Гольцова М. Широкополосные ЦАП: борьба на рынке коммуникационных систем усиливается. // Электроника. 2001. № 2.