автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.13, диссертация на тему:Нечисловая обработка информации на вычислительной машине нетрадиционной архитектуры потока данных

ВВЕДЕНИЕ.

ГЛАВА 1. ИССЛЕДОВАНИЕ ВОЗМОЖНОСТЕЙ

ВЫЧИСЛИТЕЛЬНОЙ МАШИНЫ ПОТОКА ДАННЫХ

ДЛЯ НЕЧИСЛОВОЙ ОБРАБОТКИ ИНФОРМАЦИИ

1.1. Особенности нечисловой обработки информации.

1.2. Ограничения традиционных архитектур и семантический разрыв.

1.3. Требования к новым архитектурам, ориентированным на нечисловую обработку.

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

1.5. Выводы.

ГЛАВА 2. ВЫЧИСЛИТЕЛЬНАЯ МАШИНА ПОТОКА

ДАННЫХ В СИСТЕМЕ КЛИЕНТ/СЕРВЕР ГГ.

2.1. Компоненты систем клиент/сервер и их задачи

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

2.3. Программные средства поддержки сложных архитектур

2.4. Машина потока данных в составе вычислительной системы, используемой для сервера базы данных.

2.5. Программные средства базового варианта вычислительного комплекса нечисловой обработки с машиной потока данных в качестве периферийного высокопроизводительного спецпроцессора.

2.6. Выводы.

ГЛАВА 3. РАЗРАБОТКА И РЕАЛИЗАЦИЯ

ИНФОРМАЦИОННОЙ СИСТЕМЫ "БИБЛИОТЕКА"

КАК ПРОТОТИПА ИС ДЛЯ ВЫЧИСЛИТЕЛЬНОЙ

МАШИНЫ ПОТОКА ДАННЫХ.

3.1. Принципы построения информационной системы.

3.2. Структурные особенности ИС "Библиотека".

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

3.4. Разработка и реализация версии ИС "Библиотека" на базе персональных компьютеров.

3.5. Разработка и реализация версии ИС "Библиотека" на базе локальной вычислительной сети и файлового сервера.

3.6. Реализация модели вычислений клиент/сервер в информационной системе "Библиотека".

3.7. Совершенствование ИС "Библиотека " и ее адаптация к вычислительной среде потока данных.

3.8. Выводы.

Глава 4. ОБРАБОТКА ПРИЛОЖЕНИЙ НА

ВЫЧИСЛИТЕЛЬНОЙ МАШИНЕ ПОТОКА ДАННЫХ.

4.1. Анализ языка запросов высокого уровня SQL.

4.2. Разработка общей схемы трансляции SQL-запросов для их исполнения на вычислительной машине потока данных.

4.3. Способы представления реляционных баз данных в машине потока данных.

4.4. Метод отображения конструкций языка запросов SQL на язык машины потока данных.

4.5. Разработка методов доступа для различных классов приложений, обрабатываемых на машине потока данных

4.6. Особенности поиска и сортировки на машине потока данных.

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

4.8. Оценка аппаратных и программных средств машины потока данных для нечисловой обработки.

4.9. Выводы.

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

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

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

- повышение производительности информационных систем.

Разработка новых архитектур вычислительных машин для нечисловой обработки осуществляется в двух направлениях. Одни исследования, целью которых является устранение ограничений традиционной архитектуры, концентрируются на вопросах параллелизма и векторных операциях. Другие исследования посвящены ассоциативным структурам, так как недостаточная производительность информационных систем является следствием необходимости эмуляции ассоциативного доступа с помощью системы ссылок и соответствующего программного обеспечения.

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

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

- необходимо использовать новые вычислительные системы, обладающие высокой производительностью и значительным объемом оперативной памяти;

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

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

- универсальная база данных, которая совмещает в себе элементы документальной и фактографической БД;

- информационная система, которая обеспечивает обработку, анализ и быстрый поиск как в структурированных данных (реляционных БД), так и в полнотекстовых документах (текстовых файлах) в рамках единой идеологии.

Учитывая экономический фактор при решении проблем переносимости языков определения и манипулирования данными на вычислительную машину нетрадиционной архитектуры потока данных, целесообразно реализовать язык запросов высокого уровня SQL, поскольку реляционный подход и методика его использования при проектировании баз данных и систем управления базами данных находят все более широкое применение. Почти все современные открытые распределенные СУБД такие, как Oracle, Sybase, Informix, поддерживают стандартизованный язык запросов высокого уровня SQL, поэтому особенно актуальна разработка средств переноса существующих приложений, написанных на SQL, на машину потока данных.

В диссертационной работе рассматривается одна из схем новой нетрадиционной высокопараллельной архитектуры вычислительных средств супер-ЭВМ на базе сетевой системы с потоковым принципом обработки данных, созданная в рамках работ по "Оптической сверхвысокопроизводительной вычислительной машине (ОСВМ)". 5

ОСВМ обеспечивает, во-первых, достижение предельного быстродействия вычислительных средства счет массового параллелизма выполнения программ с дискретностью до операции и, во-вторых, максимальное исключение человека из распределения ресурсов вычислительных средств. Следует отметить, что данная машина создавалась для решения сложных задач вычислительного класса.

Цель диссертационной работы - исследовать возможности ОСВМ для нечисловой обработки информации, выявить особенности доступа к документальным и фактографическим базам данных и разработать методы обработки современных приложений на вычислительной машине нетрадиционной архитектуры потока данных. Для проведения исследований должна быть разработана и создана информационная система - прототип ИС, работающей на базе вычислительного комплекса, имеющего в своем составе ОСВМ. Создание системы тестов, потокового расширения фрагментов теста ТРС-С (Transaction Processing Council test С), позволит оценить систему управления и обработки информации.

Задачами диссертационной работы являются:

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

- обзор современных программных средств управления базами данных и информационно-поисковых систем для адаптации на вычислительном комплексе с ОСВМ, используемой в качестве специализированного периферийного спецпроцессора;

- разработка логической структуры и исследование различных способов физической организации в ассоциативной памяти ОСВМ универсальной базы данных, совмещающей в себе элементы документальной и фактографичской;

- классификация запросов к БД и определение механизма поиска на вычислительной машине нетрадиционной архитектуры потока данных для каждого класса запросов;

- создание общей схемы трансляции и декомпозиции запросов для их вычисления на ОСВМ;

- создание методики отображения конструкций языка запросов высокого уровня SQL, в основе которых лежат основные реляционные операции, на язык машины потока данных; 6

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

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

1. Особенности нечисловой обработки информации и анализ требований, предъявляемых к аппаратному и программному обеспечению нечисловой обработки.

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

3. Сруктура программных и аппаратных средств ОСВМ, организация вычислений на машине потока данных, способы исследования процесса обработки баз данных на вычислительной машине архитектуры потока данных с помощью логических регистровых моделей ОСВМ и оценка параллельности потоковых программ с помощью инструментальной системы на персональном компьютере.

4. Модель вычислений клиент/сервер, обзор современных систем распределенной обработки, вертикальная и горизонтальная расширяемость систем клиент/сервер при подключении ОСВМ.

5. Характеристика языка описания и манипулирования данными SQL, анализ языка запросов SQL и стилей программирования на SQL с точки зрения управления и обработки реляционных БД в потоковой среде.

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

Особое внимание в первой главе уделяется анализу архитектурных решений и исследованию возможностей вычислительной машины для нечисловой обработки. Особенностью нечисловой обработки данных является ассоциативная адресация. Параллелизм - это естественное решение проблемы нечисловой 7 обработки больших наборов данных с повторяющейся структурой. Машины потока данных позволяют добиться высокой скорости вычислений за счет использования параллелизма, заложенного в самих программах. Степень параллельности определяется только алгоритмом обработки данных. Существует несколько уровней параллелизма, одна из классификаций приводится в данной главе. Аппаратное распараллеливание является функциональным свойством данной аппаратуры, необходимым для поддержки нечисловой обработки информации. Ассоциативная память на принципах оптической обработки информации и пути повышения ее производительности представлены в первой главе с точки зрения организации потоковых вычислений.

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

Во второй главе рассматривается модель распределенной обработки данных (вычисления клиент/сервер). Описываются основные компоненты систем клиент/сервер и их задачи.

Одним из преимуществ модели клиент/сервер является масштабируемость. В главе представлен обзор различных архитектур в аспекте расширяемости, поскольку производительность системы клиент/сервер в значительной степени зависит от архитектуры вычислительного комплекса, используемого для сервера базы данных. Разрабатываются различные варианты организации такого вычислительного комплекса, имеющего с своем составе машину потока данных, делается сравнительный анализ вариантов.

Рассматривается аппаратное и программное обеспечение базового варианта вычислительного комплекса с машиной потока данных в качестве периферийного высокопроизводительного спецпроцессора. В качестве ведущей ЭВМ могут использоваться симметричные многопроцессорные или массово-параллельные системы, кластеры, слабо связанные системы, поддерживаемые, например, программными средствами типа Oracle7 Parallel Server или Informix-OnLine Dynamic Server 7.1.

Определяется набор операций, выполняемых на машине потока данных, и объем изменений и дополнений сервера для исполнения 8 запросов на машине потока данных. Дается оценка производительности базового вычислительного комплекса нечисловой обработки с ОСВМ в его составе.

Третья глава представляет собой описание аппаратных и программных средств информационной системы "Библиотека". В главе также содержатся общие сведения об управлении базами данных и организации документального поиска. Излагаются основные принципы, лежащие в основе ИС, рассматривается метод построения системы и анализируются факторы, влияющие на выбор способа распределения баз данных. Описывается структура ИС "Библиотека" и данных, связанные с ними особенности.

Главной особенностью информационной системы "Библиотека" является то, что основная часть информации с которой работает ИС хранится не в фактографических базах данных (реляционных БД), а в независимых текстовых файлах, объединенных в документальную БД в центральных узлах сети. В табличной форме представлены различные каталоги и характеристики хранимой документальной информации, которые отражают содержание файлов, их тематику, актуальность, занимаемое место в информационном обеспечении.

Этапы совершенствования информационной системы "Библиотека" от централизованной системы до реализации модели вычислений клиент/сервер были подробно представлены в целом ряде печатных трудов автора, в диссертационной работе особый акцент делается на вопросы совместимости, переносимости и адаптации баз данных и программного обеспечения клиентской и серверной части ИС на различные архитектуры.

Информационная система "Библиотека" является прототипом информационной системы, работающей на базе вычислительного комплекса с машиной нетрадиционной архитектуры потока данных. ИС, разработанная автором диссертационной работы, способствует проведению исследовательских работ по направлению "Система массового параллелизма с нетрадиционной архитектурой". ИС и ее базы данных, сформированные специальным образом для вычислительной машины потока данных, являются уникальным инструментом для исследования нечисловой обработки, поскольку запросы, обрабатываемые в ИС относятся практически ко всем классификационным группам. Обобщая статистические данные результатов обработки запросов ИС на машине потока данных можно 9 судить о характере и специфических особенностях обработки различных приложений на исследуемой вычислительной машине.

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

В главе проводится подробный анализ языка описания и манипулирования данными SQL, в примерах даны различные SQL-запросы на обработку реляционных баз данных в информационной системе "Библиотека". Проведенный анализ запросов позволяет утверждать, что язык описания и манипулирования данными SQL не только прост и удобен для создания различных запросов к БД, но и обладает реляционной полнотой. Язык SQL имеет такую же выразительную силу, как реляционная алгебра и реляционное исчисление. Запросы, обеспечивающие выборку информации из БД, целиком свободны от побочных эффектов, что полностью отвечают общим принципам потока данных.

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

Разрабатывается метод непосредственного отображения конструкций языка запросов высокого уровня SQL на язык машины потока данных. Метод базируется на том, что в основе конструкций языка SQL лежат основные реляционные операции. Синтаксически язык SQL близок исчислению кортежей. Реляционное исчисление кортежей является по сути формализацией системы обозначений, предназначенной для образования множеств (данная система обозначений используется для определения операций в реляционной алгебре). Исчисление кортежей по своей сути - непроцедурная система запросов: она выражает только то, каким должен быть ответ на запрос, а не то, как его вычислить. Алгебраические выражения можно вычислять непосредственно на машине потока данных, если существуют процедуры для каждой использованной реляционной операции. Предложенный метод не исключает использования существующих методов вычисления значений безопасных выражений

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

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

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

Особое внимание в четвертой главе уделяется разработке методов доступа к фактографическим и документальным базам данных. Алгоритмы поиска и сортировки, реализованные на машине потока данных, описываются с целью создать основу для будущих исследований нечисловой обработки данных на ОСВМ.

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

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

11

4.8. Выводы

1. С помощью языка QUEL (QUEry Language) в составе СУБД INGRES RUBIN, работающей в рамках системы ДЕМОС на МВК "Эльбрус-2", разрабатывалась одна из версий информационной системы "Библиотека ВЦ". Основной идеей QUEL служит исчисление кортежей (непроцедурная система). Синтаксически язык SQL близок исчислению кортежей, поэтому для рассмотрения и анализа был принят ряд запросов в ИС "Библиотека ВЦ".

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

3. Использование машины потока данных в качестве специализированного периферийного процессора (принятый вариант организации вычислительной системы) расширяет возможности любой вычислительной системы традиционной архитектуры для обработки БД при минимальном изменении и дополнении СУБД:

Во-первых, введены дополнения, касающиеся обработки указания DFCPARALLEL (управление степенью параллельности для каждой таблицы) Применяя DFCPARALLEL, не нужно использовать для распараллеливания одного оператора большого количества серверов запросов, не страдает производительность других запросов из-за последовательной обработки. Особенно это касается операций поиска в таблицах для приложений первой группы (ВЫБРАТЬ МНОГИЕ). На машине потока данных мы фактически получаем один процесс поиска для каждой запрошенной оператором строки, не используя серверы запросов, что невозможно в других системах.

Во-вторых, необходимо изменение процессора запросов для обеспечения трансляции на язык машины потока данных. Задача процессора запросов принять запрос на языке запросов, сделать анализ запроса, совершить обращение к файлам и провести вычисления, необходимые для нахождения ответа на запрос. Процессор запросов

107 формирует коды обращений и вычислений, при анализе запроса модифицирует его для повышения эффективности вычислений.

В-третьих, изменения не должны касаться глобальной логической организации данных и физической организации данных на ВЗУ. Однако возможны несколько вариантов представления реляционных баз данных в машине потока данных.

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

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

После сравнения различных вариантов представления реляционных баз данных в машине потока данных, был принят первый вариант (отношение БД - одномерный или двумерный неоднородного массив с декларациями) в качестве базового. При выполнении запросов, содержащих один блок SQL SELEKT [FROM] [WERE] (обработка реляционного оператора выбора) более предпочтительным является данное представление отношения со следующим распределением полей токена: поле НК - имя отношения, поле И - единственный индекс на отношение.

Эффективное использование второго варианта (отношение БД -набор однородных одномерных или двумерных массивов атрибутов) возможно при введении векторных команд. Если оператор выбора выбирает подмножество строк в отношении, то оператор проекции выбирает подмножество столбцов. Для эффективного выполнения

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

5. Предложенная методика трансляции запроса легла в основу создании нового процессора запросов, ориентированного на исполнение программ на ОСВМ. Процессор запросов СУБД, работающий на ведущей ЭВМ, использует специальный пакет прикладных программ для подготовки кода и данных для загрузки и исполнения на машине потока данных, а так же для обработки результатов вычислений, произведенных на ОСВМ.

Согласно предложенной схеме трансляции:

1 этап. Язык запросов SQL транслируется в промежуточный процедурный язык. На данном этапе используются методы декомпозиции запросов, подобные используемым процессором запросов QUEL СУБД INGRES. В результате первого этапа трансляции запрос на языке SQL превращается в программу, включающую лишь присваивания, выбор, проекции и циклы.

2 этап. Процедурный язык транслируется в машинный язык. В качестве результата трансляции запроса на данном этапе подразумевается программа на Ассемблере ОСВМ.

3 этап. Программа на языке машины потока данных транслируется в код для непосредственного вычисления на машине потока данных.

6. Алгебраические выражения неявно присутствуют во внутреннем представлении запросов. Алгебраическое выражение, представленное в виде ориентированного дерева (внутренние узлы дерева выражения - операции реляционной алгебры, листья -отношения или постоянные, выходящие из внутреннего узла ребра -операнды данной операции), преобразуется в DA-граф. Процедуры для каждой использованной реляционной операции одного уровня исполняются параллельно. Второй этап трансляции подготавливает вычисление данных процедур на машине потока данных.

Реляционная операция выбора реализуется с помощью основного блока SQL - выбирается одно или несколько значений атрибутов, заданных в списке SELECT из отношения, определяемого в предложении FROM при выполнении условия WHERE. Выражения условия должны быть логического типа. Они могут комбинироваться с помощью логических связок, которые транслируется в команды

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

Для проверки выполнения заданного условия в системе команд потока данных имеется специальная команда ПУ. В зависимости от значения входного токена, результата выполнения условия, команда ПУ направляет другой входной токен либо на левый, либо на правый выходы, реализуя ветвление на две части. При запуске вычислений по одной из ветвей заблокировано прохождение операндов. Счет ведется только по ветви "выполнения условия".

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

Реляционная операция присваивания дает возможность создавать новые отношения для хранения результатов операций, являющиеся также отношениями. При наличии указания БРСРА11А1ХЕЬ новые базовые отношения могут быть сформированы в АП или на ведущей машине комплекса, имеющего в составе ОСВМ. В системе команд ОСВМ имеется команда ПВМ, с помощью которой результаты обработки запроса передаются для дальнейшего использования.

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

110 отношения неявно предполагается удаление дубликатов кортежей результирующего отношения, однако в SQL удаление дубликатов осуществляется с помощью SELECT UNIQUE. Для эффективного выполнения операции проекции при трансляции отношение должно быть представлено как набор одномерных или двумерных однородных массивов атрибутов.

7. На языке SQL сортировку кортежей по возрастанию или по убыванию можно задать в явном виде ORDER BY <атрибут> ASC и ORDER BY <атрибут> DESC. Для эффективного выполнения SELECT UNIQUE, SET, HAVING и др. также необходима сортировка. Кроме того, проведенный анализ показал, что сортировка в некоторых случаях хорошо заменяет поиск. С точки зрения параллельности наиболее интересны обменная сортировка со слиянием (параллельная сортировка Бетчера) и обменная сортировка с разделением (быстрая сортировка Хоара). Исследования алгоритмов сортировки показали, что сортировка со слиянием более эффективна для реализации на ОСВМ.

8. Дана оценка аппаратных и программных средств вычислительной машины потока данных для нечисловой обработки информации. ОСВМ оценивалась в соответствии с классификационными признаками такими, как степень параллелизма, ассоциативность, процессорная организация, тип процессорных связей, количество поддерживаемых моделей данных m др. Дана оценка параллелелизма и производительности вычислительной машины потока данных при нечисловой обработке. Доказано, что реализованные на ОСВМ алгоритмы соединения и сортировки имеют лучшую производительность, чем любые другие алгоритмы.

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

9. На основе тестов, описанных в данной главе, два из которых представлены в Приложении 2, подготовлена система тестов различных устройств логико-временной модели вычислительной машины потока данных в системе проектирования Mentor Graphics. Акт о внедрении системы тестов (Приложение 4) подтверждает правильность предложенных методов.

Ill

ЗАКЛЮЧЕНИЕ

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

2. Проведено исследование модели вычислений клиент/сервер и впервые разработаны варианты организации вычислительной системы с машиной потока данных для серверной СУБД. Определен набор операций, выполняемых на машине потока данных, и объем изменений и дополнений сервера для исполнения запросов на машине потока данных. Дана оценка производительности нового вычислительного комплекса нечисловой обработки.

Предложенный автором базовый вариант вычислительного комплекса нечисловой обработки с машиной потока данных в качестве периферийного высокопроизводительного спецпроцессора позволит значительно повысить эффективность обработки различных приложений, особенно это касается группы приложений ВЫБРАТЬ МНОГИЕ.

3. Разработанная автором методика трансляции SQL-запросов обеспечит во-первых, языковую совместимость ЭВМ различных архитектур, используемых для обработки современных приложений, во-вторых, эффективный перенос программ, написанных на языке запросов высокого уровня SQL, на машину потока данных.

4. Впервые предложены варианты представления реляционных БД в машине нетрадиционной архитектуры потока данных. В работе проведен сравнительный анализ способов представления отношения в машине и даны рекомендации по их выбору в зависимости от вида операций над отношениями для получения наиболее эффективного кода.

112

5. На основании проведенного анализа языка запросов SQL и стилей программирования на SQL с точки зрения управления и манипулирования реляционными БД в потоковой среде автором разработан метод отображения конструкций языка запросов высокого уровня SQL, в основе которых лежат основные реляционные операции, на язык машины потока данных. Предложенный метод не исключает использования существующих методов вычисления значений безопасных выражений исчисления кортежей, данный метод дополняет существующие для вычислительной среды потока данных.

6. Автором разработана и создана информационная система "Библиотека". ИС является готовым конкурентноспособным программным продуктом. Одна из версий информационной системы "Библиотека" сертифицирована Госстандартом России (Сертификат соответствия № РОСС RU.ME20.C00023). Согласно актам, ИС "Библиотека" прошла полный комплекс испытаний и успешно внедрена на предприятиях. ИС функционирует на базе вычислительных систем различных архитектур, легко настраивается на имеющиеся аппаратные средства.

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

7. Информационная система "Библиотека" способствует проведению исследовательских работ по направлению "Система массового параллелизма с нетрадиционной архитектурой". ИС и ее базы данных, сформированные специальным образом для вычислительной машины потока данных, являются уникальным инструментом для исследования нечисловой обработки, поскольку запросы, обрабатываемые в ИС относятся практически ко всем классификационным группам. Обобщая статистические данные результатов обработки запросов ИС на машине потока данных можно судить о характере и специфических особенностях обработки

113 различных приложений на исследуемой машине нетрадиционной архитектуры.

8. Разработана и внедрена система тестов различных устройств модели вычислительной машины нетрадиционной архитектуры потока данных (DFS) на рабочей станции HP в системе автоматизированного проектирования Mentor Graphics. Система тестов является потоковым расширением фрагментов теста ТРС-С (Transaction Processing Council test С).

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

1. Использовать результаты диссертационной работы для более детального анализа алгоритмов, применяемых для реализации команд SQL и усовершенствования методов их трансляции и оптимизации.

2. Разработать методы построения транслятора PL/SQL на язык машины потока данных и создать программные средства для организации хранимых процедур, что позволит полнее использовать машину потока данных для нечисловой обработки информации.

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

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

114

1. Аветисян Д. О. Проблемы информационного поиска. М.: Финансы и статистика, 1981.

2. Бобровски С. Огас1е7 и вычисления клиент/сервер. М.: Лори,1996.

3. Богачева Л. А., Подшивалов Д.Б. Проблемы построения системы команд для машин, основанных на принципе потока данных. В сб.: Вычислительные машины с нетрадиционной архитектурой. Супер ВМ. Вып. 2. - М.: ВЦКП РАН, 1994, с. 38-77.

4. Бурцев B.C. Система массового параллелизма с автоматическим распределением аппаратных средств супер-ЭВМ в процессе решения задачи. В сб.: Вычислительные машины с нетрадиционной архитектурой. Супер ВМ. Вып. 2. М.: ВЦКП РАН, 1994, с. 3-37.

5. Бурцев B.C., Тарасенко Л.Г. Использование микропроцессоров традиционной архитектуры в системе потока данных. В кн.: Параллелизм вычислительных процессов и развитие архитектуры супкЭВМ. М.: Нефть и газ, 1997, с. 121-139.

6. Бурцев B.C., Федоров В.Б. Ассоциативная память на принципах оптической обработки информации для супер-ЭВМ нового поколения. В сб.: Вычислительные машины с нетрадиционной архитектурой. Супер ВМ. Вып. 2. М.: ВЦКП РАН, 1994, с. 78-97.

7. Вирт И. Алгоритмы и структуры данных.- М.: Мир, 1989.

8. Глушановский A.B., Каленов Н.Е., Лексикова Е.Е. База данных "Science Citation Index" на CD-ROM.- М.: БЕН РАН, 1993. -(Информационный бюллетень N6).

9. Грабер М. Введение в SQL. М.: Лори, 1996.

10. Информационно-поисковая система. Программное изделие БИБЛИОТЕКА (501200). Базовое программно-информационное обеспечение. Банк данных. Описание применения. Прил. к Сертиф. Соотв. РОСС RU.ME20.C00023 №00561828. М., 1995.

11. Информационно-поисковая система. Программное изделие БИБЛИОТЕКА (501200). Базовое программно-информационное115обеспечение. Программа обслуживания банка данных. Руководство пользователя. Прил. к Сертиф. Соотв. РОСС RU.ME20.C00023 №00561828. М., 1995.

12. Использование микроЭВМ для автоматизации библиотечно-информационных процессов: Метод, рек. Вып. 2. М.: ГПНТБ, 1989.

13. Кнут Д. Искуство программирования для ЭВМ. т.З Сортировка и поиск. М.: Мир, 1978.

14. Лори П. Базы данных для микроЭВМ / Пер. с англ. Трубина Ю. К. М.: Машиностроение, 1998.

15. Льюис Ф., Розенкранц Д., Стирнз Р. Теоретические основы проектирования компиляторов. М.: Мир, 1976.

16. Люшо В., Паулус К. Технология INFORMIX для среды SAP R/3. INFORMIX Software GmbH, M10135, 1/96.

17. MBK "Эльбрус-2". Программное обеспечение. Система файлов. М., 1982.

18. Мейер Д. Теория реляционных баз данных. / Под ред. Цаленко М. Ш. М.: Мир, 1987.

19. Повышение эффективности деятельности библиотек и автоматизации библиотечных процессов: Сб. сокращенных переводов. М.: ЦНО "Старт" 1989.

20. Пратт Т. Языки программирования: разработка и реализация. / Под ред. Баяковского Ю. М. М.: Мир, 1979.

21. Провоторова А. О. Анализ состояния и тенденции развития информационной системы "Библиотека ВЦ" и распределенных баз данных.- М.: ИВВС РАН, 1995. (Препринт №4).

22. Провоторова А.О. Реализация языка манипулирования данными SQL на машине с архитектурой потока данных. М.: ИВВС РАН, 1996. - (Препринт №2).

23. Провоторова А.О. Отражение основных конструкций реляционного языка запросов высокого уровня SQL на язык потока данных. В сб.: Вычислительные машины с нетрадиционной архитектурой. Супер ВМ. Вып. 5. - М.: Нефть и газ, 1998, с. 52-68.

24. Провоторова А.О. Пути использования машины с архитектурой потока данных для нечисловой обработки информации. М.: ИВВС РАН, 1998. - (Препринт №1)

25. Провоторова А.О., Старостина Г.Н. Разработка компонент распределенной базы данных на основе локальной сети ЭВМ. М.: ИВВС РАН, 1995.- (Препринт №3)116

26. Проект ОСВМ. М.: ВЦКП РАН, 1993.

27. Сеть ПК для учреждений. Hewlett-Packard Company. / Пер. НПФ "ИнтерКомСервис". М.: МАИ, 1994.

28. Сызько Э.В. Некоторые результаты моделирования архитектуры машины потока данных. В сб.: Вычислительные машины с нетрадиционной архитектурой. Супер ВМ. Вып. 3. - М.: ВЦ РАН, 1995, с. 71-93.

29. Тарасенко Л.Г., Хайлов И.К. Система команд макета ОСВМ. Версия от 01.04.1997. М.: ИВВС РАН, 1997.

30. Тиори Т., Фрай Д. Проектирование структур баз данных. -М.: Мир, 1985.

31. Трахтенгерц Э.А. Введение в теорию анализа и распараллеливания программ ЭВМ в процессе трансляции. М.: Наука, 1981.

32. Цикритзис Д., Лоховски Ф. Модели данных. М.: Финансы и статистика, 1985.

33. Alsberg Р.А. Belford G.G. Sinchronization and Dedlock.-University of Illinois, CAC Document 185,1985.

34. Bosworth N. Automation at the University of California at Berkley. In: Proc. Fifth Scien. Sem., Moscow, 1993, p. 5-15.

35. Chu W. File Directory Design Consideration for Distributed Databases.- In: Proc. Third Int. Conf. Very Large Data Bases, IEEE, 1987.

36. Codd E. F. Relational Completeness of Data Base Sublanguages. In Rustin R. Data Base Systems. Englewood Cliffs, N. J.: Prentice Hall, Inc., 1972, p. 33-64.

37. Guide to Oracle Products and Services. Oracle Corporation, 1994, (8266.1194 A16030).

38. Gurd J. R., Kirkham С. C., Watson I. The Manchester Prototype Dataflow Computer. Communications of the ACM, 1985, Vol. 28, Num. 1, p. 34-52.

39. Ozkarahan E. A., Schuster S. A., Sevcik К. C. Performance Evaluation of a Relational Assosiativ Processor. ACM Transactions on Database Systems, 1987, Vol.2, No.2, p. 175-195.

40. Provotorova A. 'Library' Information System in Education.- Proc. of the Int. Conf. in Russia ICDED'94, Moscow, 1994, p. 276.

41. Severance D. G., Carlis J. V. A Practical Approach to Selecting Record Access Paths. ACE Comput. Curv., Vol. 9, Num. 4,1977, p. 259272.117

42. Stonebreaker M. Concurrency of Multiple Copies of Data in Distributed INGRES.- IEEE Transaction on Software Engeneering SE-5, 3, May 1979, p. 188-194.

43. Stonebreaker M. Performance Enhancement to a Relation Database System.- ACM Transactions on Database System, Vol. 8, Num. 2, 1983.

44. Tanaka Y., Nozaka Y., Masuyama A. Pipeline Searching and Sorting Modules as Components of Data Flow Data Base Computer. Proc. of IFIP World Congress, 1980, p. 427-432.

45. Treleaven P. S., Brownbridge D. R., Hopkins R. P. Data-driven and demand-driven computer architecture. ASM Comput. Surv., Vol. 14, Num. 1, 1982, p. 93-143.

46. Van Rijsbergen C. J. Information retrieval.- 2nd ed. London: Butterworth Scientific Publishers, 1979.

47. Waxman R. Hardware Design Languages for Computer Design and Test Computer, Vol. 19, Num. 4, 1986, p. 90-91.118