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

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

Бистре розвиток потреб застосувань БД висуває нові вимоги до СУБД:

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

естественные й ефективні подання у БД різноманітних відносин між об'єктами предметних областей (наприклад, просторово-часових з забезпеченням візуалізації данных);

поддержка несуперечливості даних, і реалізація дедуктивних БД;

обеспечение цілісності БД широтою діапазону різноманітних предметних і операційних обстановок;

управление розподіленими БД, інтеграція неоднорідних баз данных;

существенное підвищення надійності функціонування БД. Разом про те традиційна програмна реалізація численних функцій сучасних СУБД на ЕОМ загального призначення призводить до громіздким і непродуктивною системам із досить високої надійністю. Тим паче важким виявляється нарощування програмних засобів, які забезпечують перелічені вище вимоги. Це пов’язано з поруч причин:

фон-неймановская архітектура ЕОМ неадекватна вимогам СУБД, зокрема реалізації пошуку, відновлення, захисту даних, обробки транзактов лише програмним способом неефективні як у продуктивності, і по стоимости;

многоуровневое та складне програмне забезпечення СУБД знижує ефективність і надійність функціонування БД;

универсальная ЕОМ виявляється перевантаженої функціями управліннями базами даних, що знижує ефективність функціонування власне прикладних систем;

централизация і інтеграція даних у мережах персональних і фахових ЕОМ нереализуема з прийнятною вартістю без введення до складу мереж спеціалізованих ЕОМ на підтримку функції СУБД.

Эти міркування наводять на думку про нагальність створення спеціалізованих автономних інформаційних систем, орієнтованих виключно у функцій СУБД. Проте системи, реалізовані на звичайній універсальної мінічи микроэвм, неспроможні цілком вирішити зазначені проблеми. Необхідний пошуку нових архітектурних і апаратних рішень. Дослідження у цьому напрямі сприяли появлению-проектов і діючих прототипів машин баз даних, які поруч із самостійним призначенням становлять також основу обчислювальних систем 5-го покоління. Машиною баз даних (МБД) прийнято називати апаратно-програмний мультимикропроцессорный комплекс, готовий до виконання всіх, чи деяких функцій СУБД.

Такие властивості реляційної моделі даних, як розчленовування відносин на непересічні групи, можливість масової і паралельної обробки, простота і даних у цій моделі, і навіть наявність розвиненою теорії реляционных баз даних, і апарату відомості до реляційної інших моделей даних зумовили розробку МБД, орієнтованих переважно ось на підтримку реляционных баз даних. Нині очевидна правильність такого вибору в зв’язку зі встановленням можливості оперувати об'єктами баз знань на реляционном концептуальному рівні у вигляді операцій реляційної алгебры.

Перші публікації у МВС з’явилися торік у 1974 р., зараз можна назвати понад 50 відсотків проектів, вже реалізовані як промислових прототипів і є комерційними виробами. Дослідження з апаратурною підтримці операцій над базами даних проводяться й у нашій країні. Основними критеріями з оцінки тієї чи іншої проекту є повнота виконуваних функцій СУБД і очікуване підвищення продуктивності за її виконанні. Це однаково важливо, як для МБД, функціонуючих що з головною ЕОМ в складі «єдиної обчислювальної системи, так МБД, що є вузлом локальної мережі (data computer). В усіх життєвих сучасних проектах і численних комерційних МБД реалізований повний обсяг функцій СУБД. Підвищити продуктивність, враховуючи обмежені швидкісні характеристики сучасної елементної бази, можна тільки структурними методами (з допомогою структурного розпаралелювання). Через це МБД є спеціалізованими паралельними обчислювальними системами, та їх проектуванні потрібні єдина методологія порівняння і чіткі критерії оцінки продуктивності. У час ведуться інтенсивні дослідження, у цієї области.

Основными технічними прийомами, застосовуваними в структурних методах підвищення продуктивності МВС, є следующие:

использование багатоканальних пристроїв масової пам’яті (УМП) з умонтованими в апаратуру каналів процесорами пошуку істини та фільтрації зменшення обсягів перекачиваемых даних із УМП в обробні подсистемы;

использование буферизации між основний пам’яттю обробних процесорів і УМП, яка лише згладжує різницю у швидкостях обробки даних, і читання в УМП, а й зменшує частоту звернення до УМП;

сегментація даних в УМП, яка збільшує локальність доступу і покращує ефект попередніх методів; із метою передбачається розвиток мультиатрибутной кластеризації і індексації даних в УМП і апаратна їх поддержка;

использование асоціативної пам’яті як буферної і лобіювання відповідних алгоритмів обробки данных;

развитие підсистем випереджальної вибірки даних в буферну пам’ять (стадирование даних) і оптимізація алгоритмів управління віртуальним простором данных;

реализация режимів паралельної інтерпретації кожну операцію над БД (горизонтальний паралелізм типу SIMD) і режимів конвеєрної і потоковой обробки як операцій, а й транзакцій на целом;

функциональная спеціалізація процесорів оброблення і їх апаратна реалізація як СБИС.

Основные напрями розвитку структур МВД:

Можно виділити два узагальнених напрями, у яких проводяться дослідження по структурним методам підвищення продуктивності МВС: многопроцессорные неоднорідні (МН) і мережні МВС. На рис. 1 наведено узагальнені топологічні схеми таких МВС. Приватним випадком МН МВС вважатимуться комерційні МВС IDM-500, RS-310, iDBP 86/440, топологічна схема яких приведено на рис. 2.

[pic].

Рис. 1. Топологія двох класів МВД:

а — многопроцессорные неоднорідні МВС із кількома рівнями обробки б — мережні МВД К МН МВС можна віднести більшість сучасних проектів МВС, як-от DELTA, GRACE, DSDBS, MPDC, SABRE та інших. Основними особливостями МН МВС є следующие.

1. Наявність кількох рівнів обробки даних, зокрема, трьох основных:

селекція і первинна фільтрація даних у контрольних пристроях масової памяти;

вторичная обробка, яка полягає у реалізації операцій реляційної алгебри над допоміжними відносинами, отриманими першою этапе;

[pic] / - універсальний обробний /__/ -комунікаційний процессор

процесор (серійний микропроцессор).

— спеціалізований — коммутирующее пристрій (общая.

обробний процесор шина, переключательная матрица,.

Про — локальна напівпровідникова пам’ять кільцева коммутирующая шина,.

коммутирующая сеть).

— буферна загальнодоступна пам’ять — Керуючий процесор (подсистема).

— пристрій масової памяти.

з контролером (НМД з контроллером).

Рис. 2. Топологія комерційних МБД.

структурна обробка чи обробка метаданих, яка полягає підтримка допоміжних структур даних (індексація, мультиатрибутная кластеризація) .

2. Наявність системної буферної пам’яті (СБП) між першими двома рівнями обробки, у якій поміщаються стосунки або допоміжні структури даних, отримані першою рівні обробки. Така архітектура припускає наявність випереджальної вибірки і підкачування даних із рівня первинної обробки (стадирование). СБП у своїй обов’язково має бути двох чи більше портовой.

3. Наявність функціонального паралелізму, у якому різні функції первинної і вторинної обробки реалізуються на фізично розподіленої апаратурі. У цьому частина функціональних пристроїв реалізується на універсальних мікропроцесорах, частину — у вигляді спецапаратури (наприклад, замовних СБИС). Функціональний паралелізм дозволяє реалізувати конвеєрне виконання транзакцій і окремих запитів. У загальних випадках збільшення продуктивності допускається дублювання функціональних процесорів найбільш трудомістких операциях.

В ролі найбільш типових прикладів таких МН МВС можна розгледіти DELTA і GRACE. Японський проект МВС (рис. 3) є основою обчислювальної системи 5-го покоління. Чинний нині прототип і двох подсистем:

[pic].

подсистемы вторинної обробки складі чотирьох реляционных процесорів (РП), одного процесора управління (УП), одного комунікаційного процесора (КП) і самого процесора технічного обслуговування (НТО), виконує функції діагностики системи, підтримки БД, зв’язки й з операторам тощо. п.;

підсистеми ієрархічної пам’яті (Іл), що містить системну буферну пам’ять (електронний кэш-диск ємністю 128 Мбайт), масову пам’ять з вісьома НМД (з контролером магнітного диска КМД) загальною ємністю 20 Гбайт і чотирма НМЛ (з контролером магнітної стрічки — КМЛ), і навіть універсальну микроэвм управляючим процесора ієрархічної пам’яті (УПИП) і процесора виводу-введення-висновку (ПЕВ). Зв’язок між підсистемами здійснюється високошвидкісним каналом зі стандартним інтерфейсом зі швидкістю передачі до 3 Мбайт/с. Усі процесори підсистеми вторинної обробки підключаються до цьому каналу у вигляді ПВВ через спеціальні адаптери ієрархічної пам’яті (АИП).

Основным функціональним вузлом МЕД DELTA є реляционный процесор (РП) баз даних, призначення которого-выполнение операцій реляційної алгебри над відносинами довільного обсягу із високим продуктивністю. Кожен із чотирьох РП може виконувати окрему операции:

процесора (КП) і самого процесора технічного обслуговування (НТО), виконує функції діагностики системи, підтримки БД, зв’язки Польщі з оператором тощо. п.;

підсистеми ієрархічної пам’яті (Іл), що містить системну буферну пам’ять (електронний кэш-диск ємністю 128 Мбайт), масову память с вісьмома НМД (з контролером магнітного диска КМД) загальної емкостью.

20 Гбайт і чотирма НМЛ (з контролером магнітної стрічки — КМЛ), а так же універсальну микроэвм управляючим процесора ієрархічної пам’яті (ВУДИВ) і процесора вводу-виводу (НЕЇ). Зв’язок між підсистемами здійснюється високошвидкісним каналом зі стандартним інтерфейсом зі швидкістю передачі до 3 Мбайт/с. Усі процесори підсистеми вторинної обробки підключаються до цього каналу у вигляді ПВВ через спеціальні адаптери ієрархічної пам’яті (АИП).

Основным функціональним вузлом МЕД DELTA є реляционный процессор (РП) баз даних, призначення которого-выполнение операцій реляційної алгебри над відносинами довільного обсягу із високим продуктивністю. Кожен із чотирьох РП може виконувати окрему операцію реляційної алгебри незалежно з інших або всі можуть виконувати одну операцію паралельно (наприклад, сортування взаємин у Іл). РП має регулярну структуру (див. рис. 3) для полегшення його реалізації в вигляді СБИС. Крім цього він у собі має центральний процесор (ЦП) з пам’яттю 512 Кбайт для реалізації операцій із великої логікою (наприклад, агрегатних функцій типу min, mах тощо. п.). Для полегшення вхідного (ВП) і вихідного (ВИП) потоку даних РП містить два адаптера ієрархічної пам’яті (АИП), і навіть вхідний модуль на підготовку кортежів відносин (наприклад, перестановки значень атрибутів). Власне операція реляційної алгебри реалізується у РП. Процесор злиття (ПСЛ) сортированных сегментів відносин призначений для злиття сортированных сегментів відносин, соціальній та ньому реалізуються операції природного поєднання двох відносин також селекції відносини. Дванадцять процесорів сортування (ПСО) призначені для реалізації конвеєрної однопроходовой сортування сегмента відносини обсягом 64 Кбайт. ПСО і ПСЛ реалізовані повністю аппаратно.

Иерархическая пам’ять в DELTA є найскладнішою підсистемою, в функції якої входят:

управление СІВ і УМП;

стадирование даних (як сегментів відносин) з УМП в СБП в відповідність до заявками РП;

селекция і вертикальна фільтрація відносин при приміщенні в СБП з залученням спеціального (атрибутного) методу зберігання взаємин у УМП;

підтримка індексних структур, кластеризація взаємин у УМП і організація з їх допомогою швидкого пошуку УМП.

[pic].

Рис. 4. Структурна схема МВС GRACE.

Другим прикладом МН МВС є й японський проект GRACE, структурна схема якого приведено на рис. 4. СБП реалізована тут набором електронних дисків на циліндричних магнітних доменах. Як УМП використані многоканальные НМД, у кожний канал яких вмонтовані, крім пристроїв чтения-записи (Уч/з), процесори первинної обробки, названі фільтрами потоку кортежів (ФПК). Кожен ФПК содержит:

процесор фільтрації (ПФ), здійснює не більше доріжки МД власне псевдоассоциативный пошук кортежів, які відповідають заданому условию;

процессор проекції (ПП) і перетворення кортежей;

процессор хэширования (ПХ), який реалізує динамічну сегментацию кортежей читаного отношения.

Фільтр потоку кортежів працює у конвеєрному режимі дозволяє обробляти які з УМП кортежі зі швидкістю їхнього виконання (обробка «в полете»).

На рівні вторинної обробки застосовуються процесори вторинної обробки (ППО) і ФПК. Призначення ФПК — виконувати вищеописану обробку кортежів результирующих відносин, надходили з ППО в СІВ. ППО містить поруч із процесором реляційної алгебри (ПРА), реалізованою з урахуванням універсального мікропроцесора зі своєю локальною пам’яттю, також апаратний процесор сортування відносин (ПСО) і процесор видачі результату (ПВР) в канал головною ЕОМ. ПСО здійснює потоковую сортування сегмента відносини, що надходить зі Світового банку СІВ в процесор реляційної алгебри. Двухпортовые банки СІВ приєднуються до процесорам обробки обох рівнів у вигляді спеціальних петлевых шин (СПШ). Ці многоканальные шини з поділом часу здійснюють кожному рівні обробки комутацію будь-якого процесора обробки до будь-якого банку пам’яті і одночасну обробку кількох банків памяти.

Відмітними особливостями цього проекту є такі структурні решения.

1. Метод випереджальної підкачування кортежів з УМП в СБП поєднує не тільки з первинної фільтрацією, але з спеціальним розподілом кортежів у банках СІВ. Ця так звана динамічна хэш-сегментация дозволяє виконувати операції реляційної алгебри лише на рівні вторинної обробки паралельно й без обмінів кількома ПPA, отже кожен ПРА реалізує бінарну операцію над парою відповідних сегментів отношений-операндов. Це одна із джерел підвищення продуктивності МБД при виконанні операцій реляційної алгебры.

2. Включення в цикл вторинної обробки фільтрів потоку кортежів, які у циклі первинної обробки, дозволяє обробляти проміжні відносини у СБП, як і і вихідні відносини БД, однаково інтерпретувати послідовність операцій реляційної алгебри. Отже, виконання транзакції, відповідної складного запиту до реляційної БД, залежить від багаторазовому виконанні циклів первинної і вторинної обработки.

3. Попередня і паралельна фільтрація даних із швидкістю їх надходження з УМП дозволяє знизити обсяг переміщуваних з УМП в СБП даних, що є істотним джерелом підвищення продуктивності МБД загалом. Цей механізм використовується у багатьох (а то й переважають у всіх) проектах МН МБД й вважається визнаним решением.

Як засвідчили численні дослідження, СУБД може бути ефективної, коли велика частину їх працює під керівництвом операційній системи загального призначення. Тому підвищення ефективності МБД пов’язані з повної ізоляцією СУБД у межах МВС, т. е. реалізацією функционално-полных МВС, виконують всі функції управління транзакціями. Зважаючи на складність відповідної ОС МБД, реалізувати функціонально повну і высокопараллельную МН МВС сложно.

Друга основна у створенні высокопараллельных МН МБД, названа «дисковим парадоксом», у тому, що швидкість вводу-виводу сучасних УМП (одноканальные і многоканальные НМД з перемещающимися головками) є вузьким місцем і обмежує досягнення високого паралелізму у фортепіанній обробці. У МН МБД на вирішення цієї проблеми, у ролі кешдиска застосовується велика напівпровідникова буферна память.

Аби вирішити цієї проблеми деякі автори подають мережні МБД у яких розподілене зберігання великих БД складає більшій кількості НМД.

Мережні МВС (див. рис. 1, б) втілюють принципи однорідності структури, сегментації даних в пристроях масової пам’яті і розподілу процесорів обробки по УМП. Отже, стрижневу ідею мережевих MBД — наближення дешевої обробній логіки (як універсальних мікропроцесорів) до УМП і зв’язування таких «обробних сховищ» до мережі. З огляду на швидко снижающуюся вартість процесорів oбработки та жорстких НМД і економічні успіхи у техніці комунікації процесорів, у складі такий мережі то, можливо сотні УМП, з кожним із яких з'єднаний свій обробний процесор. Прикладами таких проектів є МВО; GAMMA. У розвитку мережевих MB. Д деякі автори бачать створення МВС з урахуванням обчислювальної систолической середовища. Так, проект NODD, схема якого зображено на рис. 5, реалізований у вигляді регулярної грати, в вузлах якої розміщені процессорные елементи (ПЭ). Із кожним ПЭ пов’язані своя локальна пам’ять (ЛЗ) і пристрій масової пам’яті (УМП) як жорсткого НМД.

[pic].

Прогнозується також заміна УМП енергонезалежної напівпровідникової пам’яттю відповідної ємності («силіконова» систолическая МВС). Призначення ЛЗ у кожному узле-хранение програм обробки, копії керуючої програми, буфера обмінюватись повідомленнями і кеш-пам'яті для свого УМП (3% кожного локального УМП перебуває у цій локальній кеш-пам'яті). Для цілей надійності простір кожному УМП розділене на частини: друга для зберігання частини БД, що належить своєму вузлу, другая-дублирует дані чотирьох сусідніх вузлів. Особливістю є і те, що управління виконанням транзакцій на таких мережевих МВС повністю розподілено, отже кожен процесор може він роль управляющего.

Особливу увагу набуває створення систолических МВС у зв’язку з появою серійних однокристальных транспьютеров, містять поруч із процесором і пам’яттю канали (порти вводу-виводу). Наприклад, промисловий транспьютер фірми INMOS IMS Т414 має такі характеристики. У першому кристалі реалізований 32-разрядный процесор швидкодією до 10 млн. опер./с, статична ОЗУ на 2 Кбайт, чотири каналу зв’язку, 32-разрядный інтерфейс пам’яті і контролер динамічного ОЗУ. Конструктивно транспьютерная матриця, що є основний елемент систолических транспьютерных МВС (див. рис. 5), може бути у вигляді серійних транспьютерных плат IMS ВОООЗ тієї ж фірми. Ця подвійна европлата містить чотири транспьютера Т414, пов’язаних між собою портами зв’язку, чотири устрою динамічної пам’яті по 256 Кбайт кожне і чотири зовнішніх порту вводу-виводу. Можливо, найближчим часом застосування таких транспьютерных плат переведе проекти систолических МВС в галузі теоретичних досліджень, у область практичної реализации.

[pic].

Основною проблемою в розподілених (мережевих) МБД є оптимальна кластеризація даних із локальним УМП й підтримка відповідної розподіленої індексації. У GAMMA, наприклад, пропонується кластеризація кожного відносини з всім УМП (відповідно до хешированием значенийключевых атрибутів і створення розподіленого по УМП індексу цих значень). У NODD пропонується рівномірний розподіл відносин по вузлам грати. Між конкретними кортежами різних відносин, котрим діють семантичні зв’язку, існують покажчики, що задають розташування пов’язаних кортежів (номери вузлів та його адреси в УМП). Отже, запит в БД збуджує зв’язок між кортежами в вузлах грати та породжує потік даних з-поміж них. Це дозволяє реалізовувати такий МВС потоковую обробку складних запитів з урахуванням моделі «активного графа».

До класу мережевих належить комерційна МВС фірми Teradata DBC 1012, яка інтенсивно поширюється і знаходить широке використання у разлиных інформаційних системах. На рис. 6 зображено конфігурація DBC 1012 з вісьмома обробними процесорами ПМД (з урахуванням i80386), кожен із яких має НМД і підключається до комунікаційної мережі типу двоичного дерева (Y-сеть). У вузли цієї мережі вмонтовані мережні високошвидкісні процесори і программируемые логічні матриці, реалізують функції управління мережею. Y-сеть дозволяє здійснювати двобічний обміни між обробними процесорами. У цю мережу підключаються комунікаційні процесори (Іл) реалізації інтерфейсу з головної ЕОМ. Кожен обробний процесор забезпечує підтримку всіх операцій реляційної алгебри, достатніх до виконання операторів SQL, підтримку своєї частини БД, і навіть виконання всіх функцій управління транзакціями над своєї частиною БД, зокрема захист цілісності, поновлення і т. буд. Зразки DBC 1012 включають до 128 процесорів і мають розподілену по обробним процесорам напівпровідникову пам’ять ємністю 412 Мбайт на один процесор. Загальна ємність масової пам’яті становить до 1000 Гбайт і загальне швидкодія — до 10⁹ опер./с.

[pic].

Два властивості DBC 1012 притаманні всіх мережевих МЕД: забезпечення про можливість збільшення потужності нарощуванням числа обробних процесорів, отже продуктивність у своїй зростає лінійно (показник лінійності зростання продуктивності DBC 1012 від кількості процесорів становить 97%);

забезпечення надійності функціонування з допомогою дублювання даних в локальних УМП (т. е. забезпечується робота без краху системи на виході з ладу окремих процесорів чи УМП).

Третье напрям досліджень у сфері МБД полягає у створенні недорогих комерційних пристроїв на серійних процессорных елементах з шинним інтерфейсом (топологія таких МБД зображено на рис. 2, а). Як прикладу розглянемо МБД фірми Britton Lee IDM 500, структурна схема якої зображено на рис. 7. Хоча ці вироби орієнтовані на высокопараллельную обробку та містять обмежену кількість функціональних процесорів, вони задовольняють сформульованим вище принципам МН МБД і повністю реалізують все основні функції МБД. Структурна схема комерційних МБД є приватною випадком МН МБД (див. рис. 2, a). Роль СБП виконує напівпровідникова пам’ять, до котрої я через загальну шину підключаються периферійні контролери НМД з умонтованими мікропроцесорами AMD 2901, процесор обробки (процесор БД) з урахуванням Z8002 і по 8 канальних процесорів для підключення до головною ЕОМ (канал IBM 370, інтерфейс з VAX 750) чи підключення до локальної мережі (Ethernet). Кроні того, до спільної шині може підключатися особливий функціональний процесор (акселератор БД) для виконання тих операцій, що є вузьким місцем (наприклад, сортування відносин). Старша модель IDM SOO/XL з ємністю зовнішньої пам’яті більше однієї Гбайт на жорстких МД і 500 Мбайт на МЛ має продуктивність 1000 транзакций/мин і водночас обслуговує до 400 пользователей.

Розвитком цього напряму в розробках фірми Britton Lee з’явився реляционный файлсервер (data/file server) RS310 — автономне пристрій, подключаемое до локальної мережі Ethernet чи безпосередньо до головною ЕОМ по інтерфейсу RS232. Він включает:

власне процесор бази даних (1 плата) з урахуванням 28 000 (10 МГц); сполучений з цим процесором оперативну пам’ять ємністю 1 Мбайт на однієї плате;

дві жорсткі диска типу вінчестер (5 ¼ дюйма) по 80 Мбайт кожен із відповідним контроллером;

контролер касетної МЛ з 60 Мбайт на касеті (Streaming tape ¼ дюйма);

чотирьох интерфейсных плат двох типів (інтерфейс RS232 із вісьмома виходами чи інтерфейс локальної мережі Ethernet).

Кожна інтерфейсна плата містить процесор 28 000 і свій локальну пам’ять., RS310 можна використовувати чи як автономна СУБД з вихідним мовою SQL, підтримуючи у своїй всі функції СУБД, крім першого етапу трансляції з SQL (управління транзакціями, паралельне виконання запитів, відкоти і відновлення, автоматичну оптимізацію запитів тощо. п.), чи як інтегрована систему управління файлами. У цьому RS310 виступає для головною ЕОМ як інтелектуального контролера з буферизацией і задовольняє інтерфейсу SCSI (Small Computer System Interface). RS310 забезпечує одночасну роботу до 50 користувачів і виконує одночасно до 10 запитів. Найближча перспективи розвитку RS310 — збільшення зовнішньої пам’яті до максимально восьми НМД ємністю 478 Мбайт і МЛ ємністю 300 Мбайт.

[pic].

Рис. 8. Спеціалізована машина для БД PYRAMID P. S 9810 (9820).

Подальшим розвитком такий підхід до створення комерційних МБД є їх реалізація на модульної паралельної мультимикропроцессорной системі типу систем S27 і S81 фірми Sequent і систем серії 9000 (9810, 9820) фірми Pyramid-Sybase. На рис. 8 зображено структурна схема нового вироби фірми Pyramid—система 9810(9820), що є спеціалізованої ЕОМ для БД. Ця спеціалізована машина варта автономної підтримки СУБД Sybase з вхідним мовою SQL, і навіть на підтримку прикладних інформаційних систем основі цієї СУБД для автоматизації конторської діяльності, розробки програмного забезпечення тощо. п. Система працює як data computer у мережі ЕОМ і має інтерфейс лише з локальної мережею Ethernet, а й Х25, telenet, darpa. Загальна дискова пам’ять сягає 15 Гбайт. Основна пам’ять, подключаемая до влаштуванню управління пам’яттю як плат до запланованих 4 і 16 Мбайт, може наращиваться до 128 Мбайт. У системі підтримується віртуальне адресне простір 4 Гбайт сторінок в 2048 байт. Як процесорів обробки виступають одну чи дві спецпроцесори (CPU), реалізовані вигляді 32-разрядных процесорів з RISCархітектурою. CPU має такі характеристики:

время циклу- 100 нс;

число 32-разрядных регістрів — 528;

кэш-память інструкції- 16 Кбайт;

кэш-память — 64 Кбайт. У RISC-процессорах реалізований конвеєрний режим виконання инструкций.

Основою системи є власна сверхбыстрая шина xtend.

(40 Мбайт/с), працююча за принципом комутації повідомлень. Інтелектуальний процесор виводу-введення-висновку (ПВВ) реалізований з урахуванням мікропроцесора AMD 29 116 з швидкодією 5 млн. опер./с і має 14 паралельних ОМА-контроллеров, загальна пропускну здатність яких 11 Мбайт/с. ПЕВ обслуговує периферійні устрою, контролери НМД (швидкість передачі у до 2,5 Мбайт/с) і контролери локальної мережі (КЛС).

До загальної шині підключається до 16 портів з інтерфейсом RS232 для обслуговування інтелектуальних термінальних процесорів, з допомогою яких до системі можуть підключатися термінальні користувачі. Підключення до шині адаптера шини MULTIBUS відкриває широкі змогу підключення допоміжних зовнішніх пристроїв, у яких реалізований інтерфейс цієї шины.

Управління системою здійснюється процесором підтримки системи, в функції якого входять також діагностика всіх пристроїв і системи загалом, сервісна служба системи та т. п. У цьому вся процесорі функціонує так звана двухпортовая многопроцессорная операційна система, яка з'єднує у собі дві версії UNIX ОС: System V. AT&T і 4.0 Berkly.

Перспективи розвитку МБД.

Створення високопродуктивних МВС пов’язують із рішенням наступних проблем, у яких ведуться інтенсивні исследования.

1. Створення спеціалізованих архітектур МВС, сочетающих гідності горизонтального паралелізму і під час однієї операції з функціональним паралелізмом і під час послідовності операцій та транзакцій. Особливу роль у цьому відіграє реалізація конвеєрної потоковой обробки (data flow) стосовно операціям реляційної алгебры.

[pic].

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

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

(RI) ПОСТАЧАЛЬНИК (КОД ПОСТАЧАЛЬНИКА, имя);

(R2) ДЕТАЛЬ (КОД-ДЕТАЛИ, ТИП-ДЕТАЛИ, НАИМЕНОВАНИЕ);

(R3) ПОСТАЧАННЯ (КОД-ДЕТАЛИ, КОД-ПОСТАВЩИКА, КОЛИЧЕСТВО).

[pic].

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

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

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

Необхідність в сортування пояснюється лише тим, що реалізація бінарних операцій реляційної алгебри (з нелінійної складністю 0(n²), де nкардинальность відносин) в потоковому режимі, коли одиницею обміну між операціями є кортежі чи сторінки відносин, можлива, лише коли відносини однаково упорядковані. Тому операція сортування в конвеєрному і потоковому режимах обробки є вузьким місцем, і потрібно її апаратна реалізація, яка задовольнить наступним требованиям:

висока швидкість і близька до лінійної залежність часу сортування від обсягу відносини; один прохід при реалізації сортування; конвеєрний режим обробки потоку даних; наявність внутрішніх буферів обсягом щонайменше сторінки відносини (64, 128, 256 Кбайт); можливість винятку дублікатів кортежів при сортування отношения.

[pic] рис. 11. Вплив затримки при сортування на потоковий режим обробки кортежей.

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

2. Створення асоціативної пам’яті великий ємності для системного буфера МВС. Як відомо, використання асоціативної пам’яті як СБП дозволяє істотно збільшити ефективність пошукових та інших операцій на МВС лише на рівні вторинної обробки. Викликає зацікавлення гібридна асоціативна пам’ять, має один порт-обычный для підключення пам’яті до спільної шині, а второй-ассоциативный для підключення до відповідному контроллеру.

Прикладом такої пам’яті є виріб фірми Сіменс, структурна схема підключення якого до спільної шині представлена на рис. 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³ входів) та її реалізації з їхньої основі многопортовой системної буферної пам’яті для МВД.

Фільтри є технічні чи програмні кошти на виділення даних, які відповідають будь-яким умовам. У реляційної моделі даних вибір за умовою відповідає операціям проекції і селекції реляційної алгебри. У завданнях обробки тексту потрібно, зазвичай, вибрати текст, у якому дане слово. Ті ж завдання вибору даних із умові можуть вирішуватися і з допомогою використання циклів чи хэширования.

Фильтры, проте, дозволяють перевіряти складніші умови, ніж «одно» (для хэширования можливе тільки така перевірка), «не одно», «більше», «менше». Фільтри не вимагають попередньої структуризації даних. Разом про те використання фільтрів передбачає повний перегляд відносини (чи, тоді як базі зберігаються инвертированные файли, повний перегляд значень атрибутів, що у умови). Фільтри можна застосовувати й у комбінації з индексированием і хэшированием.

Загальна схема використання фільтрів наступна. Процесор, аналізуючий запит, виділяє умова селекції. Виділене умова передається у спеціальний процесор (чи групу процесорів), що є программируемым фільтром. Цей процесор може бути як спеціалізованим, і процесором загального назначения.

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

У багатьох проектів МЕД використовуються фільтри, які моделюють для перевірки умов кінцеві автомати. Під час такої реалізації швидкість перевірки умови слабко з його складності (якщо розмір пам’яті фільтра достатній для моделювання кінцевого автомата, котрий перевіряє условие).

Бінарні операції (об'єднання, те що, з'єднання) над отсортированными відносинами також можна реалізувати з допомогою фильтров.

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

Коли ролі фільтруючого процесора використовується процесор загального призначення, вхідний буфер розбивається на два. Контролер завантажує блоки вхідного файла по черзі у одне із двох буферів. Завантаження ведеться безпосередньо з диска, оскільки фільтрація йде приблизно тричі повільніше читання. Кеш-пам'ять у разі непотрібна. Результат фільтрації записується одного з двох вихідних буферів. По заповненні буфера його вміст скидається на диск.

До вад фільтрів, моделюючих кінцеві автомати, слід віднести високі вимоги до величини пам’яті фильтра.

Інший спосіб перевірки Умов здійснюється прямим фільтром, структура якого відповідає структурі проверяемого умови. Основними блоками фільтра є компаратор, котра управляє будова та логічне пристрій. Компараторы перевіряють істинність простих умов. Їх кількість буде обмежено й фіксоване в апаратурі. Сучасна технологія СБИС дозволяє будувати прямі фільтри із кількістю компараторов порядку 100. Котра Управляє пристрій організує роботу фільтра, логічне пристрій обробляє отримані значення й генерує остаточне значення істинності складного умови. На вхід компаратора подається запис вида.

или.

деодна з умов порівняння. Результатом роботи компаратора є ознака ІСТИНА чи ЛОЖЬ.

Передане в фільтр формалізоване умова представлено в диз’юнктивної чи конъюнктивной нормальної формі. Для визначеності говоритимемо далі про диз’юнктивної нормальної формі. І тут умова є диз’юнкцію мономов. Кожен моном є сполучення простих умов. На кожен крок компаратор перевіряє чергове просте умова, та поступово формується оцінку перевірки всього складного условия.

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

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

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

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

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

Операнды найпростіше розміщувати у зовнішній пам’яті, спільної всіх компараторов. Час звернення до спільної пам’яті накладає у разі обмеження на число компараторов в фільтрі. Якщо час введення однієї записи 100 не, а час компаратора 400 не, то немає сенсу мати більш чотирьох компараторов. Використання СБИС-технологии дозволяє забезпечити кожному компаратору достатню внутрішню пам’ять (порядку 256 байт).

Є низка проблем, що є поки за рамками досліджень з МВД.

1. Підвищення ефективності зберігання даних у великих БД часто пов’язують зі стиском даних, спеціальним кодуванням даних, і т. п. Але псевдоассоциативный пошук і освоєння фільтрація даних у УМП важко реалізовані, якщо ці в УМП зберігаються у стиснутому і закодованому вигляді. Поки лише у єдиному проекті DS DBS зроблено спробу розв’язати проблему.

2. Під час розробки МЕД не розглядається проблему забезпечення інтерактивного взаємодії користувача з БД у вигляді графічного дисплея. Якщо термінали працюють під керівництвом МБД, то складність ОС МБД істотно зростає, що може спричинити до деградації загальної продуктивності МБД. Якщо термінали користувача працюють під управлінням головною ЕОМ, то зростає обсяг даних, переданих від МБД в головну ЕОМ і наоборот.

3. Підвищення продуктивності МВС зазвичай пов’язується зі швидкістю операцій, дерев запитів, окремих транзакцій і суміші таких транзакцій. У цьому видача даних терминальному користувачеві починає здійснювати аж після виконання останньої реляційної операції в послідовності операцій, відповідних запиту. Іноді до ухвалення рішення досить кількох кортежів, є наслідком цієї послідовності (дерева запиту). Збільшення реактивності МБД під час видачі цих кількох кортежів, які відповідають запиту, часто суперечить збільшення традиційної пропускну здатність МВС. Розв’язати цю проблему можна тільки реалізацією у МВС такого режиму потоковой обробки відносин, у якому реляційна операція почне видавати результуючі кортежі, не очікуючи появи повністю сформованих отношений-операндов. Для низки операцій реляційної алгебри складності 0(n²) (де n-кардинальность отношений-операндов) реалізація такої режиму важко можна залагодити, наприклад для операції сортування отношений.

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

5. Розробка єдиної методології проектування МВС з заданого набору вимог (об'єм і тип БД, типи і частота запитів, сфера застосування тощо. п.). Нині проектування МВС грунтується на інтуїтивних міркування, і немає механізмів попередньої оцінки продуктивності, такі як паралельних систем обчислювального типа.

Наявність зазначених негараздів у проектуванні МВС змушує деякими авторами питанням «Чи є ідеальна МБД?» відповісти так: «Ідеальна МБД, якщо вони існують, мусить бути, очевидно, занадто дорогою і занадто складною, щоб їх можна було використовувати універсально у кожному області применений».

Кращою рекомендацією у разі є розробка сімейства МВС, що дозволяє здійснити необхідний вибір кожному за специфічного застосування. Наприклад, мультипроцессорная машина псевдоассоциативного пошуку великих файлах бібліографічних систем чи многопроцессорные МВС на підтримку реляционных операцій як частину систем баз знань логічного виведення, чи функціонально повні МВС комерційного типу для економічних додатків у завданнях управління, відбувається доступом до структурованим даним з прикладної програми, яка у головною ЭВМ.