Принципы организации и методология применения вычислительных систем с набором команд дискретной математики тема диссертации и автореферата по ВАК РФ 00.00.00, доктор наук Попов Алексей Юрьевич

• Попов Алексей Юрьевич
• доктор наук
• 2024

Оглавление диссертации доктор наук Попов Алексей Юрьевич

Введение

Глава 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.2.1 Топология общей шины

3.2.2 Топология независимых шин

3.2.3 Топология с иерархией шин

3.3 Принципы функционирования Процессора обработки структур

3.3.1 Функциональная декомпозиция Процессора

обработки структур

3.3.2 Принципы хранения структур данных

3.4 Аппаратные средства реализации основных операций

в вычислительной системе со множественным потоком команд и одиночным потоком данных

3.4.1 Функциональная схема Процессора обработки структур

3.4.2 Принцип функционирования Каталога

3.4.3 Принцип функционирования Операционного буфера

3.4.4 Принцип функционирования Устройства выборки команд

и определение форматов

3.4.5 Набор машинных команд

3.4.6 Реализация команды Добавление

3.4.7 Реализация команды Удаление

3.5 Реализация центрального устройства управления Процессора обработки структур

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

3.7 Выводы по главе

Глава 4. Оптимизация алгоритмов в вычислительной системе

с набором команд дискретной математики

4.1 Цели и принципы оптимизации алгоритмов в вычислительной

системе с набором команд дискретной математики

4.1.1 Особенности представления алгоритмов

в вычислительной системе с набором команд

дискретной математики

4.1.2 Анализ существующих подходов к разработке параллельных алгоритмов в вычислительных системах

4.1.3 Общие вопросы ускорения вычислительного процесса

при организации параллельной обработки

4.1.4 Методика модификации алгоритмов для вычислительной системы со множественным потоком команд и одиночным потоком данных

4.2 Вопросы представления программы ЭВМ с набором команд

дискретной математики

4.2.1 Представление алгоритмов со множественным потоком команд и одиночным потоком данных в виде псевдокодов

4.2.2 Формальная постановка задачи декомпозиции информационного графа программы

4.2.3 Преобразование декомпозиции информационного графа программы и критерии получения оптимальной декомпозиции информационного графа алгоритма

4.2.4 Преобразование декомпозиции информационного графа программы для вычислительной системы со множественным потоком команд

и одиночным потоком данных

4.3 Реализация алгоритмов оптимизации на сетях и графах

4.3.1 Алгоритм Дейкстры

4.3.2 Алгоритмы обхода графа

4.3.3 Алгоритм Форда-Фалкерсона

4.3.4 Алгоритмы поиска минимального остовного дерева

4.4 Вопросы применения вычислительной системы с набором

команд дискретной математики

4.4.1 Применение Процессора обработки структур для аппаратного ускорения баз данных

4.4.2 Защита данных в системах обработки информации

4.4.3 Применение вычислительной системы с набором команд дискретной математики

4.5 Выводы по главе

Глава 5. Реализация и экспериментальные исследования

эффективности вычислительной системы с набором команд дискретной математики

5.1 Реализации вычислительной системы с набором команд дискретной математики

5.1.1 Этапы проектирования системы с набором команд дискретной математики

5.1.2 Основные технические параметры реализации

Процессора обработки структур

5.1.3 Язык ассемблера и машинные коды команд Процессора обработки структур

5.2 Верификация Процессора обработки структур и вычислительной системы с набором команд дискретной математики

5.2.1 Верификация модели системы

5.2.2 Отладка прототипа на макете

5.3 Экспериментальные исследования эффективности вычислительной системы с набором команд дискретной математики345

5.3.1 Экспериментальное исследование временной сложности основных операций

5.3.2 Исследование производительности Процессора обработки структур на алгоритмах поиска

минимального остовного дерева

5.3.3 Исследование производительности Процессора обработки структур на алгоритмах обхода графа

5.4 Архитектура высокопроизводительного вычислительного комплекса Тераграф

5.5 Выводы по главе

Заключение

Список сокращений и условных обозначений

Список литературы

Введение

Посвящается моей семье!

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

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

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

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

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

Введение диссертации (часть автореферата) на тему «Принципы организации и методология применения вычислительных систем с набором команд дискретной математики»

Цель работы:

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

Задачи исследования:

- Исследование эффективности существующих средств вычислительной техники, подходов к ускорению вычислений и обработке больших объемов данных.

- Анализ современной элементной базы и выбор вариантов реализации устройств ускорения вычислений.

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

- Разработка принципов функционирования аппаратного устройства обработки множеств и структур данных на основе набора команд дискретной математики: Процессора обработки структур.

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

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

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

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

- Исследование эффективности и области применения вычислительной системы с набором команд дискретной математики.

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

Научная новизна работы:

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

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

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

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

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

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

- Разработаны параметризованные модели устройств: Каталога, Устройства загрузки команд, Операционного буфера, устройства микропрограммного управления, что позволило реализовать Процессор обработки структур и вычислительную систему с набором команд дискретной математики.

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

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

- Определены общие принципы применения систем с набором команд дискретной математики для реализации СУБД и систем обработки информации, геоинформационных и робототехнических систем.

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

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

Положения, выносимые на защиту:

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

- Функциональная модель устройства обработки отношений данных, определяющая выполняемые им операции.

- Принципы функционирования вычислительной системы с аппаратной поддержкой операций над множествами и структурами данных.

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

- Принципы аппаратной обработки структуры B+дерева в составе Процессора обработки структур, позволившие впервые реализовать устройства: Каталог, Операционный буфер и Устройство загрузки команд.

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

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

- Алгоритмы дискретной оптимизации на сетях и графах, оптимизированные для системы с набором команд дискретной математики: алгоритмы Крускала, Прима, Форда-Фалкерсона, Дейкстры, алгоритмы обхода графа в ширину и глубину.

Практическая значимость работы. Наибольшую практическую значимость имеют следующие результаты работы:

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

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

- Транслятор ассемблера Процессора обработки структур.

- Действующие программы реализации алгоритмов Форда-Фалкерсона, Дейкстры, Крускала, Прима, и других алгоритмов для системы с набором команд дискретной математики.

Апробация работы. Основные положения диссертационной работы обсуждены на второй международной научно-технической конференции, посвященной 95-летию со дня рождения академика В.Н.Челомея (г. Москва 2009), международной конференции ICACON 2015 (Будапешт, 2015), меж-

дународной научной конференции Hawaii International Conference on System Science «HICSS50» (Гавайи, 2017), международной выставке «Армия 2017» (Москва, 2017), международной выставке «ChipExpo 2017» (Москва, 2017), международной конфренции IEEE MMET 2018 (Санкт-Петербург, 2018), международной конфренции IEEE EIConRus 2019 (Москва, 2019), международной конференции «Математические методы в технике и технологиях 2019 (Санкт-Петербург, 2019), международной конференции IEEE EIConRus 2020 (Москва, 2020), международной конфренции IEEE EIConRus 2021 (Москва, 2021), международной выставке «ЦИПР 2022» (Нижний Новгород, 2022). международной выставке «Армия 2022» (Москва, 2022), XI форуме по цифровизации оборонно-промышленного комплекса - «ИТ0ПК-2022» (Пермь, 2022), международной конференции «Суперкомпьютерные дни в России», RuSCDays2022 (Москва, 2022), международном форуме «Микроэлектроника 2023» (Сочи, 2023).

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

Достоверность результатов. Достоверность полученных в диссертационной работе результатов подтверждается проведенными натурными испытаниями действующего образца системы с набором команд дискретной математики. Функциональность, работоспособность и технические характеристики всей системы и Процессора обработки структур продемонстрированы в ходе проведения выставок, приведены автором в периодических изданиях и открыто демонстрируются на действующих образцах в Центре обработки данных МГТУ им. Н.Э.Баумана.

Реализация и внедрения. Теоретические и практические результаты работы, полученные автором, нашли применение при исследовании факторов активного долголетия в ФГБУ ФНКЦ ФХМ ФМБА России, при проведении научно-исследовательской деятельности АО «БАЙКАЛ ЭЛЕКТРОНИКС», в научно-исследовательской и коммерческой деятельности компании ООО «ИБС Софт», при реализации программно-технического комплекса по предотвращению угроз, реализуемом УИ-ВЦ МГТУ им. Н.Э. Баумана, при создании высокопроизводительного вычислительного комплекса Тераграф в ходе совместной исследовательской и коммерческой деятельности с АО «ТРИНИТИ

СОЛЮШНС», в научно-исследовательской деятельности и учебном процессе научно-учебного комплекса «Информатика и системы управления» МГТУ им. Н.Э.Баумана.

Публикации автора по теме диссертации. По результатам диссертационной работы автором опубликовано 19 работ, в том числе 15 работ в журналах, входящих в список научных журналов ВАК Минобрнауки России и патент Российской Федерации. Общий объем: 11.0 п.л.

Объем и структура диссертации. Диссертационная работа состоит из введения, пяти глав, заключения, списка литературы и приложения, занимающих 400 страниц текста, в том числе 81 рисунок и 56 таблиц, список литературы из 164 наименований на 16 страницах.

Содержание работы. Во введении обоснована актуальность темы диссертации, сформулированы основные задачи и научные результаты, дано краткое содержание глав.

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

В результате исследований, проведенных во второй главе, был определен базис операций, кванторов и отношений, применяемых в дискретной математике ко множествам. Была определена вычислительная сложность их реализации для различных типов структур данных, известных из практики программирования. На основе этого B+деревья были выбраны в качестве прототипа при аппаратной реализации функций обработки множеств и структур данных. Анализ элементной базы для реализации аппаратной обработки множеств и структур данных показал, что наиболее перспективными технологиями для вывода проекта на рынок является первичная реализация на ПЛИС и БМК с последующим переводом на ASIC/ASSP решения.

Рассмотренные в разделе 2.3 алгоритмы выполнения операций в B+дереве позволили выявить возможность повторения однотипных действий над различными уровнями дерева. Это показывает возможность разработки универсальных

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

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

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

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

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

Анализ способов взаимодействия устройств и вариантов обмена информацией в системе с набором команд дискретной математики, проведенный в разделе 3.2, позволил определить три режима работы: режим сопроцессора, режим МКОД и комбинированный режим. Показаны и выявлены достоинства и недостатки трех вариантов организации топологии системы: общей шины; независимых шин и иерархии шин.

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

В разделе 3.4 представлены варианты реализации Каталога, Операционного буфера, и Устройства загрузки команд. Были определены 6 форматов команд процессора обработки структур и набор из 19 машинных команд высокого уровня.

В разделе 3.4.5 рассмотрены вопросы организации управления блоками СП. Выполнена декомпозиция функций управления на четыре иерархических подчиненных уровня: центральное устройство управления, устройство управление уровнями дерева, управление Каталогом и управление Операционным буфером. Показано, что при реализации микропрограммных управляющих автоматов на ПЛИС типа FPGA возможности языковых средств и САПР существенно ограничены. В связи с этим в разделе 3.5 была разработана специальная технология микропрограммирования, направленная на ускоренное создание, модификацию и отладку таких устройств.

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

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

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

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

В разделе 4.3 проведены исследования реализации алгоритмов Форда-Фалкерсона, Дейкстры, алгоритмов обхода графов в ширину и глубину, а также алгоритмы Крускала и Прима. Исследования показали возможность решения задач на графах на основе параллельно и независимо работающих ЦП и СП в системе с набором команд дискретной математики. На основе общей схемы алгоритма удалось получить модифицированную версию, представленную в базисных операциях над структурами данных, а также версию с двумя потоками команд и одиночным потоком данных. Также рассмотрены принципы реализации баз данных на основе системы с набором команд дискретной математики (раздел 4.4.1). Показано, что планы выполнения SQL запросов могут использовать аппаратные команды СП, что приводит к большей параллельности обработки запросов в целом.

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

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

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

5.2 приводятся результаты комплекса процедур верификации модели Процессора обработки структур и опытного образца и представлен состав тестов. В разделе

5.3 приведены результаты экспериментальных исследований полученной системы с помощью специально разработанных программных тестов. В разделе 5.4 представлена архитектура высокопроизводительного вычислительного комплекса Тераграф, реализованного на основе принципов построения вычислительных систем с набором команд дискретной математики. Приводятся результаты тестов 24-х ядерной реализации микропроцессора DISC и структура многопроцессорной гетерогенной системы, реализованной в виде действующего образца.

Глава 1. Определение предметной области и постановка задачи

1.1 Анализ опыта применения вычислительных систем для обработки

больших объемов данных

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

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

Согласно ГОСТ 15971-90 [1], данные - это информация, представленная в виде, пригодном для обработки автоматическими средствами при возможном участии человека. В ряде случаев термины информация и данные используются как синонимы, если не оговаривается явно выраженного смыслового различия между этими понятиями. Например, в случае фильтрации входных данных и выявления пригодной для анализа ее части, можно говорить о получении

информации. Иными словами, термин информация может употребляться для определения результата преобразования и анализа данных.

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

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

Зарождение первых систем обработки данных началось в 50-е годы 20-го века, когда стали очевидны преимущества применения вычислительной техники, осознана роль информации при организации предприятий, хозяйственной и научной деятельности и военной сфере. В это время проекты по созданию вычислительных машин привели к формированию базовых принципов организации вычислительного процесса, сформулированные в документе, который назывался «Первый проект отчёта о EDVAC — отчет для Баллистической Лаборатории Армии США» и в работе «Предварительное рассмотрение логической конструкции электронно-вычислительного устройства» [2; 3], получившие название «Принципов Фон-Неймана». Вычислительные машины первого поколения строились преимущественно на базе электромагнитных реле и электронных ламп, и функциональность их ограничивалась выполнением основных арифметических команд

(+,-,/,*) и построенных на их основе более сложных действий. В работе [2] описаны также принципы реализации устройств для извлечения корня.

Первым примером успешной реализации системы обработки данных можно считать ЭВМ LEO I (сокращенно от английского Lyons Electronic Office I). Проект был реализован в 1947 году британской фирмой J. Lyons and Co., которая использовала его для расчёта цен, зарплаты сотрудников, учёта товаров [4]. В течении рабочего дня из магазинов розничной сети компании собирались заказы, которые использовались для расчёта требований количества продукции на следующий день. ЭВМ обеспечивала планирование поставок, обрабатывала счета и отчёты для руководителей магазинов.

Список литературы диссертационного исследования доктор наук Попов Алексей Юрьевич, 2024 год

- —

—>

пустая вершины в структуре «0»

I - занятая вершины, входящая в структуру \

Рисунок 3.10 — Представление нескольких структур в В+дереве при аппаратной

реализации

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

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

На нижнем уровне В+дерева ключи и информация хранятся в виде блоков данных, которые содержат в упорядоченном виде несколько пар «ключ-значение». Для осуществления основных операций со структурами все блоки, соответствующие вершинам Каталога п — 1 уровня, загружаются из внутренней Памяти структур в Операционный буфер СП. Трасса дерева выделена на Рисунке 3.9 серым цветом, и обращение к ее информации возможно за наименьшее время, т.к. при этом не требуется доступ во внутреннюю или локальную Память структур. При выполнении операции Поиска производится восходящий поиск информации в трассе до тех пор, пока не будет найден искомый путь, либо не будет достигнут уровень 0. После этого выполняется нисходящее движение в дереве до уровня п — 1. Использование загруженной в СП трассы позволяет существенно ускорить доступ к соседним частям дерева.

3.4 Аппаратные средства реализации основных операций в вычислительной системе со множественным потоком команд и одиночным потоком данных

3.4.1 Функциональная схема Процессора обработки структур

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

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

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

й - размер поля номера структуры (количество структур составит 2е — 1); £ - размер номера тега составляет 2 бита, так как максимально возможно три тега в команде;

а - размер поля адреса локальной памяти структур (размер памяти структур составит 2а);

А - размер поля адреса внешней памяти структур (размер внешней памяти структур составит 2А);

Ь - количество вершин на уровне В+дерева;

В - количество ключей в листе дерева (размер линейки);

с - размер команды СП в битах;

р - размер поля способа адресации в команде;

т - размер поля маски в битах;

а(г - размер поля адреса перехода в битах;

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

/ - размер флагового регистра.

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

- Поток команд поступает из Локальной памяти команд в Блок выборки команд. Команды содержат от одного до трех операндов с указанием

о ц

та

С

Архив каталога

Буфер записи

пэ

пэ

пэ

А СП -у 2 пэ СП н :<D о с

пэ

>. а. ь la пэ 5 э п к

а. Б пэ с СП О

Б S 1_ л CL пэ ж 8 о I S

аз CL пэ 3

пэ

пэ

СП о D а.

Й а.

Б

аз CL

К | Д | к I Д I .Щ

5

I I I |к|д;

Память структур

Р

z

Линейка

KlfllKlfl |K|flT.| I I IKE

Операционный буфер

пэ ПЭ | ПЭ | ПЭ | ... ПЭ

Блок анализа и установки маски

ПЭ ПЭ | ПЭ | ПЭ | ... ПЭ

О

Внутренняя шина данных

ММ

Устройство выборки команд

КОП

Теги

Операнды

Т

Т

Буфер команд ЦП Буфер данных

КОП Номер структуры

Ключ

Данные

Блок загрузки и выгрузки

^Шина памяти команд ^ Системная шина ^ Шина памяти данных^)

Рисунок 3.11 — Структурно-функциональная схема процессора обработки структур

способа их адресации. При непосредственной адресации в команде присутствуют сами операнды. Использование внешней адресации предполагает, что тег операнда не валиден. При составной регистровой адресации в команде указывается номер регистра составного ключа, общее количество которых равно 2Г. Для трех способов адресации требуется всего два бита для кодирования, но при совмещении способов адресации группу разрядов можно кодировать и более компактно: 1од2(3) = 2 бита для одного операнда (3 варианта адресации); 1од2(9) = 4 бита для двух операндов (3*3 вариантов адресации); 1од2(27) = 5 бит для трех операндов (3*3*3 вариантов адресации). Далее для упрощения расчетов примем размер способа адресации одного операнда постоянным и равным р = 2. Минимальная по размеру команда состоит из поля операции, способа адресации и одного операнда. Количество структур при аппаратной реализации не должно быть слишком большим и не будет превышать 32-х. Также предполагается, что количество регистров составных ключей не может существенно превосходить количество структур. Выбор наиболее рационального соотношения количества регистров и количества структур данных целесообразно проводить по результатам разработки общих алгоритмов решения задач в системе с набором команд дискретной математики, которые будут продемонстрированы в следующей главе. Предварительно будем считать, что количество бит для хранения структуры равно количеству бит для указания номера регистра составного ключа (в = г). Минимальный размер команды СП составит:

с + р + тт(в, г , (, к , а(г) (3.1)

Максимальный размер с учетом того, что составная регистровая адресация может применяться для каждого операнда, составляет:

с + 3 * р + тах(в,г) + тах(к,г) + тах((,г) (3.2)

Интерфейс является внешним, в связи с чем его ширина ограничена применяемым типом внешней памяти. Наиболее типичным вариантов шины памяти является 64 разряда данных и 8 разрядов кода коррекции ошибок. Поле данных и ключ также могут достигать 64 бит и более. Таким образом максимальный размер шины может превышать 128 бит, что мало осуществимо из-за ограничения по количеству внешних выводов микросхем. Возможным вариантом является пакетная передача, причем код

операции должен передаваться в первом информационном слове. Далее по коду операции определяется размер команды и выбираются следующие информационные слова.

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

тт(к,((,в)+ £ (3.3)

Максимальный размер составляет:

к + ( + в + 3 * £ (3.4)

Максимальное и минимальное по размерам слово существенно отличается. Однако, определение значений операндов в ЦП происходит последовательно, поэтому теги и операнды могут быть переданы по мере их вычислений. Таким образом следует выбрать размер шины данных, обеспечивающий передачу одного тега и максимального из операндов: £ + тах(к,(,в)

- Поток результатов передается из Буфера данных в ЦП по мере их востребованности в вычислительном потоке ЦП. Возможна передача только флагов, указывающих на успешность операции, а также передача результатов поиска в виде ключа и значения. Минимальная ширина шины равен /. Максимальная ширина составляет:

к + ( + / (3.5)

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

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

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

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

- Передача операндов между Буфером данных и Операционным буфером. Ключ и значение передаются в Операционный буфер для выполнения операций в линейках. Ширина шины составляет к + (.

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

- Линейка передается из Памяти структур в Операционный буфер и обратно. Размер линейки составляет В * (к + () бит.

- Ключ и значение передаются из Операционного буфера в Буфер данных для выгрузки результата. Размер информационного слова из операционного буфера составляет к + (.

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

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

тги(к , ()

(3.6)

Максимальная ширина составляет:

(к + () * тах(Ь, В)

(3.7)

слов в зависимости от запроса. Такой вариант возможен в ряде протоколов шин, в том числе PCI,PCIX,PCIe и других.

- Передача данных на удвоенной частоте: технология DDR поддерживается большинством современных ПЛИС и микропроцессоров, но требует применения двух тактовых сигналов (0° и 180°) для выходных буферов и двух тактовых сигналов для входных буферов.

- Использование современных типов ЗУ с конвейеризацией транзакций и поддержкой высокоскоростных интерфейсов, соответствующих стандартам SDRAM, NVMe (Non-Volatile Memory Host Controller Interface Specification) и ряда других.

Для внутренних интерфейсов СП характерна постоянная ширина шин, что позволяет реализовать их в максимально параллельном исполнении.

3.4.2 Принцип функционирования Каталога

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

Принцип функционирования Каталога. Для выполнения вставки, удаления и последовательного обхода поддеревьев в вершине B+дерева все записи одного уровня, принадлежащие одной структуре, объединяются в связанные цепочки записей.

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

- A,B - диапазон ключей поддерева [а , b];

- ADR - код поддерева, позволяющий определить адрес вершины нижнего уровня;

- PREV, NEXT - указатели на предыдущий и последующий Вершинные процессоры. Если Вершинный процессор замыкает цепочку, поля содержат специальное числовое значение, позволяющее обработать эту ситуацию;

- STR - номер структуры, к которой относится поддерево;

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

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

- E - атрибут указывает на наличие пустой линейки в поддереве.

Команды обработки | вершин

Шина вершинных процессоров

Структура Ключ

Номер уровня

Сигналы п

Вершинный процессор совпадений

М-

Память вершин Сигналы совпадений

Вершинный процессор

Память вершин

Сигналы совпадений

Вершинный процессор -М-

Память вершин

А

Бит

выборки вершины

Бит

вы борки вершины

Бит

вы борки вершины

Q.

О

ю

_с

аз 5

со О

2

с 1—

V (0

т

с; CG

о ^

а. X

О.

т <

о

о

LQ

Код

выборки вершины

Рисунок 3.12 — Структура Каталога

В каждом Вершинном процессоре хранятся данные со значениями ключей, попадающих в интервал [а,Ь]. Все процессоры каталога получают на вход одни и те же команды, которые исполняются ими в зависимости от хранимых значений и состояния флагов. Таким образом, структура на Рисунке 3.12 обрабатывает

много потоков данных одиночным потоком команд (ОКМД, SIMD). Каждый Вершинный процессор должен выполнять следующие действия:

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

- Сравнение ключа поиска с границами [a,b] и выдача сигнала совпадения в Блок контроля ключа выборки.

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

- Прием сигнала о попадании искомого ключа «выше верхней границы» (предыдущий случай) и сравнение его с нижней границей b. В случае успешного сравнения и получения сигнала вырабатывается положительный сигнал выборки вершины, который передается в Блок контроля ключа выборки.

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

- Выдача кода выборки вершины в Архив каталога, который служит для временного хранения трасс, полей и состояния флагов.

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

Фиксированный за вершиной адрес (поле ADR) не сбрасывается в исходное состояние при удалении поддерева из какой-либо структуры, а изменяется только при операциях вставки, описанной в разделе 2.3. Для вставки в поддерево, для которого флаг O = 1, на вышестоящем и частично заполненном уровне создается новое пустое поддерево и туда переносится часть ключей из переполненного поддерева. В том случае, когда перенос части ключей не связан с переносом данных из одной области памяти в другую, а изменяется лишь адресная часть, сводятся к минимуму трудоемкие операции по копированию памяти. Начальное

состояние флагов: 0='0'; Е='1'; 1='0'. После рестарта СП по сигналу сброса флаг I устанавливается в состояние '0' а после успешной инициализации флаг устанавливается в состояние '1'. Полученный в Вершинных процессорах код ассоциативных сравнений позволяет однозначно выбрать область Памяти структур, в которой должен находиться искомый элемент.

Каталог обладает рядом уникальных функциональных особенностей. В [136; 137] описан способ хранения чисел, попадающих в интервал между двумя известными значениями. Однако, предложенные в работах схемы не определяют способа инициализации и изменения границ при поступлении произвольной входной последовательности данных, в связи с чем указанные устройства для реализации операций над произвольными множествами не применимы. Действительно, пусть есть два параллельно работающих устройства, способных сохранять те данные, которые попадают соответственно в интервалы [04,61] и [02,62]. В общем случае может оказаться, что эти интервалы не пересекаются (61 < а2). Такой случай требует, чтобы определялся тот Вершинный процессор, который должен выбрать единственную линейку Памяти структур для сохранения поступивших данных и, при необходимости, изменить границы в Каталоге. При хранении в линейках не пересекающихся или граничащих множеств задача выбора линейки при указании ключа на границе или между граничными значениями сводится для каждого Вершинного процессора к формированию и передаче в следующий процессор информационного кода попадания. Для этих целей в предлагаемом устройстве используется шина связи (Шина вершинных процессоров).

Биты выборки вершины из Вершинных процессоров позволяют проанализировать результаты поиска. В случае успешного нахождения единственного интервала [а,6], соответствующий ему процессор выдает адрес поддерева в Буфер данных для его загрузки. Если же Вершинный процессор не найден, происходит поиск на границе интервалов. Общий код выбора вершины для каждого уровня дерева сохраняется в Архиве каталога, который представляет собой адресную память. Это позволяет совместно с локальной памятью самих Вершинных процессоров выполнять восходящий и нисходящий поиск в загруженной трассе дерева. Хранение указанной информации в Каталоге обеспечивает избирательное кэширование (ассоциативное хранение и доступ) информации трассы В+дерева для различных уровней, что должно существенно повысить эффективность Процессора обработки структур в целом.

3.4.3 Принцип функционирования Операционного буфера

Операционный буфер предназначен для обработки информации нижнего уровня дерева (линеек). Для этого из Памяти структур загружается В ключей и значений, причем только часть из них может быть занята информацией. Для указания занятых и свободных позиций в линейках для каждой пары сохраняется бит достоверности, указывающий на наличие реальных данных. Операционный буфер позволяет выполнять не только основные действия над одной линейкой, но и обеспечивает обработку нескольких линеек в ходе И-ИЛИ-НЕ операций. Функциями Операционного буфера являются:

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

- Формирование линеек в виде упорядоченных групп ключей и значений и выгрузка их в Память структур.

- Обработка линеек с различным количеством элементов в соответствии с битами достоверности.

- Поиск в линейке по ключу и последующие чтение или запись соответствующих значений.

- Поиск места вставки новых ключей и значений.

- Сдвиг данных внутри линейки в ходе добавления и удаления.

- Контроль переполнения линеек при вставке и сохранения вытесненных значений для последующей обработки.

- Загрузка двух дополнительных линеек (помимо линейки основной структуры результата) для структур, используемых в И-ИЛИ-НЕ операциях.

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

- Определение граничных значений ключей линеек и передача их в Каталог для изменения структуры дерева.

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

(ПЭР), выполняющих команды по принципу «один поток команд и один поток данных» (ОКМД, SIMD). Эти устройства обладают небольшой памятью для хранения ключей и значений и позволяют выполнить поиск, чтение и запись ключей и значений.

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

Рисунок 3.13 — Структура Операционного буфера

Для работы Операционного буфера необходимо подать на его вход команду управления и ключ, а для операции добавления еще и значение. Результаты поиска записываются в регистры ключа KEY и регистр данных DATA. После добавления или удаления могут измениться границы линейки в блоке R, что требует чтения граничных значений (первого и последнего ключей). Для хранения этих значений предусмотрены регистры нижней границы (регистр LOW) и регистр верхней границы (регистр HIGH). Выбор конкретного ПЭР (первого, последнего и т.д.) осуществляется с помощью установки и анализа битов маски.

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

Ряд команд выполняется только в тех процессорах, маска в которых установлена. После первоначальной загрузки линейки из Памяти структур маска может устанавливаться на основе бита достоверности (бит BUSY). Выставленный на Шину коммутатора (общую шину) ключ KEY сравнивается с хранимым в ПЭР, а результат сравнения (больше, меньше, равно) также влияет на установку маски. Далее применяются специальные команды, целью которых является выбор необходимых ПЭР. Чтение и запись ключей и значений возможно после нахождения единственного ПЭР, что подтверждает Блок анализа и установки маски.

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

Процессоры получают команды установки маски и код, характеризующий ее тип. Ниже приведены типы устанавливаемых в ПЭР масок (Таблица 12, Рисунок 3.14).

Таблица 12 — Типы устанавливаемых в ПЭР Операционного буфера масок

Маска Назначение

Сброс маски Установки бита маски в '0' вне зависимости от текущего состояния. Используется для начальной инициализации буфера.

Маска поиска Маска устанавливается в состояние '1' в тех ПЭР, в которых установлен бит достоверности BUSY и хранимый ключ равен регистру KEY. Используется в операции поиска и добавления.

Таблица 12 (окончание)

Маска Назначение

Маска вставки Маска устанавливается в состояние '1' в тех ПЭР, в которых установлен бит достоверности BUSY и хранимый ключ больше регистра KEY или равен ему. Используется в операции добавления для сдвига элементов вправо. В результате освобождается ПЭР для вставки нового значения.

Прием маски слева Маска принимается от ПЭР, находящегося слева (хранящий меньшие ключи). Используется для последовательного выполнения операций И-ИЛИ-НЕ.

Маска последнего занятого Маска устанавливается для того ПЭР, в котором маска уже установлена, маска правого процессора не установлена, маска левого установлена (с меньшими значениями ключей). Используется для определения верхней границы линейки (поле HIGH).

Маска первого занятого Маска устанавливается в том случае, когда в ПЭР установлен бит достоверности и из левого процессора не поступил бит достоверности. Используется для определения нижней границы линейки (поле LOW).

Маска первого свободного Маска устанавливается для того ПЭР, в котором не установлен бит достоверности, а в левом процессоре бит достоверности установлен. Используется для добавления элемента в случае, когда новый ключ больше любого ключа линейки.

Два других блока (буферы А и Б) хранят линейки исходных структур в ходе выполнения И-ИЛИ-НЕ операций и состоят из примитивных процессорных элементов, схожих с ПЭР: линейка загружается в них совместно с битом достоверности, каждая пара ключ-значение загружается в отдельный процессорный элемент. Однако, в буферах А и Б отсутствуют общие шины, а передача информации происходит с помощью последовательных сдвигов влево или вправо по локальным межпроцессорным шинам. Сравнение минимальных ключей (находящихся в самом левом процессорном элементе) и сдвиг значений происходит через Коммутатор, который также обеспечивает вытеснение ключей и значений при

Рисунок 3.14 — Типы масок Блока R

переполнении из буферов R в буферы А или Б. Также Коммутатор позволяет передать значение из буферов А и Б в буфер R для их вставки. В случае переполнения линейки результата происходит сохранение линейки блока R в Память структур, выборка следующей линейки в Каталоге и последующая загрузка линейки в блок R.

Набор команд процессорных элементов блока результата представлен в Таблице 13.

Таблица 13 — Команды Операционного буфера

Команда Назначение

DEL - Удаление Команда заключается в поиске по ключу, записанному в KEY и сдвигу влево всех больших. Удаленный элемент записывается в выходной регистр данных

INSERT - Добавление из KEY Команда заключается в поиске по ключу KEY места для записи, сдвига и непосредственно записи KEY и DATA в буфер R линейки каталога

Таблица 13 (продолжение)

Команда Назначение

INSERT_AБ - Добавление из A или Б буферов в R Команда заключается в поиске по ключу из A или B (определяется автоматически по наличию в них информации). места для записи, сдвига и записи KEY и DATA в буфер R

AND - Команда И Команда заключается в последовательной записи из А и В по алгоритму И

SEARCH - Команда Поиск Команда заключается в поиске по ключу, записанному в KEY и записи найденной информации в выходной регистр данных

LD_LOW - Команда записи LOW Команда заключается в записи в регистр LOW наименьшего KEY элемента из R без загрузки из памяти каталога. Также записываются регистры KEY и DATA

LD_HIGH - Команда записи HIGH Команда заключается в записи в регистр HIGH наибольшего KEY элемента из R без загрузки из памяти каталога. Также записываются регистры KEY и DATA

OR - Команда ИЛИ Команда заключается в последовательной записи из А и В по алгоритму ИЛИ

INSERT_OTHER -Команда добавления оставшихся из A или Б Команда заключается в последовательном добавлении из А или Б (определяется по наличию информации).

NOT - Команда НЕ Команда заключается в последовательной записи из А и Б по алгоритму НЕ

LD_LOWLD - Команда записи LOW с загрузкой Команда заключается в записи в регистр LOW наименьшего KEY элемента из R с загрузкой линейки из памяти каталога. Также записываются регистры KEY и DATA.

LD_HIGHLD - Команда записи HIGH с загрузкой Команда заключается в записи в регистр HIGH наибольшего KEY элемента из R с загрузкой линейки из памяти каталога. Также записываются регистры KEY и DATA

Таблица 13 (окончание)

Команда Назначение

INSERT_CLR - Добавление из KEY с вытеснением и очисткой Команда заключается в очистке буфера R и добавлении нового ключа из KEY и данных из DATA

INSERT_ABCLR -Добавление из A или B буферов с вытеснением и очисткой Команда заключается в очистке буфера R и добавлении оставшихся из буферов A или Б (определяется автоматически по наличию в них информации)

Коммутатор получает от Устройства управления специальный код коммутации, который задает вариант связи входов и выходов. Возможны несколько вариантов коммутации:

- Коммутация отключена.

- Коммутация для простых операций с вытеснением в буфер А: Исходные ключ и значение передаются на Шину Коммутатора, при переполнении буфера R ключ и значение сдвигаются в буфер А.

- Коммутация для простых операций с вытеснением в буфер Б: Исходные ключ и значение передаются на Шину Коммутатора, при переполнении буфера R ключ и значение сдвигаются в буфер Б.

- Коммутация при выполнении операций И-ИЛИ-НЕ: на Шину Коммутатора выдаются ключи и данные из буферов А и Б в соответствии с кодом операции.

- Коммутация при добавлении вытесненного ключа из буферов А и Б: на Шину Коммутатора выдаются ключи и данные одного из буферов А или Б в зависимости от того, в каком буфере имеются достоверные данные. Такой тип коммутации используется после переполнения буфера R с вытеснением.

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

не содержат достоверных данных (т.е. полностью опустошен) происходит останов выполнения операции, в Каталог передается запрос на поиск новой линейки. Если такая линейка найдена, она загружается из Памяти структур в этот буфер и операция продолжается. В случае нахождения равных ключей в буфере А и Б, этот ключ совместно с данными передается на Шину Коммутатора в буфер R. После этого выбранный по маске ПЭР принимает эту информацию и записывает ее в линейку результата, а буферы А и Б выполняют сдвиг влево на одну позицию. Если после этого линейка результата оказывается заполненной, она записывается в Память структур, после чего в Каталог выдается запрос на выборку новой линейки в структуре результата. Как только это выполняется, буфер R приводится в исходное состояние: сбрасывается маска и биты достоверности. Операция повторяется до того момента, пока не будет достигнут последний ключ в одной из исходных структур. После этого результирующая структура считается сформированной.

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

3.4.4 Принцип функционирования Устройства выборки команд

и определение форматов

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

- Очередность исполнения определяется очередностью поступления команд. Такой вариант предполагает наличие общей очереди, заполняемой

командами от обоих интерфейсов в порядке их поступления. Однако, команды из Локальной памяти команд могут содержать невалидные теги, т.е. требуют поступления операндов из ЦП. Тогда продвижение команд в очереди команд может остановиться, несмотря на возможность исполнения команд от ЦП. Стоит отметить, что сохранение очередности исполнения этих потоков не имеет особого значения.

- Исполнение по готовности команд предполагает запуск команд ЦП только в случае неготовности очередной команды из Локальной памяти команд к исполнению (наличие невалидных тегов). Данный способ позволяет комбинировать режимы работы сопроцессора и МКОД.

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

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

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

- Прямая адресация используется в случае, когда операнд известен заранее, что позволяет указать его на этапе компиляции. Например, это номер структуры или константное значение ключа.

- Внешняя адресация используется в том случае, когда между двумя потоками команд есть зависимость по данным, а операнд должен поступить

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

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

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

Рисунок 3.15 — Структура устройства выборки команд

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

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

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

Блок упорядочивания потоков команд получает готовые к исполнению команды от Блока анализа тегов (поток команд дискретной математики) и от Буфера команд (поток команд ЦП). Блок отвечает за выдачу команд в соответствии с принятой процедурой определения очередности: в случае поступления команд от ЦП они в первоочередном порядке передаются в Устройство управления. Если таких команд нет, то формируются команды DISC.

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

Рассмотрим вопрос аппаратной генерации составных ключей на основе регистров ключей и масок. На основе исследования вариантов алгоритмов дискретной оптимизации, алгоритма Дейкстры [133], алгоритма Форда-Фалкерсона [108], были выделены команды, повторно использующие ранее переданные операнды. Разделим указанные команды на три группы (см. главу 4 далее):

- Группа 1. В 50% команд переданная информация используется без каких-либо изменений. В алгоритме Форда-Фалкерсона в СП передается номер вершины графа, названный в алгоритме u_index, а далее в итерации он используется повторно.

- Группа 2. В 20% команд используют простое сочетание использованных операндов с какими-либо константами. Например, в алгоритме Форда-

Фалкерсона используется составной ключ [1,u_index] и [0,u_index], а в алгоритме Дейкстра составной ключ с использованием специального значения [to,u].

- Группа 3. Около 30% команд используют различные сочетания двух и более значений исходных ключей для генерации составных ключей (например, [u_index,v_index]). Из таких команд более половины использует только два исходных ключа.

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

Задача генерации может быть сформулирована следующим образом:

Пусть задано множество Key из kc числовых значений исходных ключей Key = {keyi,..,keykc}, где каждый ключ key представлен bc двоичными разрядами keyi = {bi,..,bbc}. Необходимо получить значения для fc разрядов составного ключа ComplexKey, однозначно определяемых на основе исходных ключей при помощи fc функций маски Mask = {maski,..maskfc}. Тогда составной ключ определяется: ComplexKey = {mask\ (Key),..maskfc (Key)}.

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

Генерация по фиксированным позициям максимально упрощает функции и не предполагает использование маски. Регистр составного ключа разделен на группы разрядов таким образом, чтобы каждая группа определялась только одним регистром (Рисунок 3.16). Такой вариант реализации

Составной ключ

Рисунок 3.16 — Структура генератора ключей по фиксированным позициям

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

- Генерация без ограничений обладает максимальными возможностями по конструированию ключей, так как предполагает функциональную зависимость каждого разряда составного ключа от всех разрядов исходных ключей. Функции mask определяют номер одного из разрядов среди всех исходных ключей: mask = f (bKeybi,..,bKeyic;bc), т.е. один из bc • ic бит. Для выборки разряда используется мультиплексор с количеством входов bc • ic и количеством адресных линий log2(bc • ic). Учитывая, что всего в составном ключе fc разрядов, количество разрядов маски составляет:

log2(bc • ic) • fc. (3.8)

Аппаратная сложность реализации мультиплексора зависит от выбранной схемы его реализации и глубины дерева элементарных коньюнкторов (Рисунок 3.17). Асимптотика сложности мультиплексора с 1-битными информационными линиями оценивается как O(2address), где address -размер шины адреса. Для параллельного мультиплексора, в котором каждый информационный вход состоит из line линий, аппаратная сложность оценивается как O(line • 2address).

Рисунок 3.17 — Структура генератора ключей без ограничений маски

Аппаратная сложность такой реализации является чрезвычайно высокой:

- Количество мультиплексоров составляет: ¡е.

- Количество информационных входов мультиплексора: Ье • ге.

- Разрядность адреса: 1од2(Ье • ге).

- Разрядность информационного слова мультиплексора: 1.

- Общая аппаратная сложность: ¡е • Ье • ге.

- Генерация с группировкой по разрядам исходных ключей позволяет сократить размер маски благодаря объединению разрядов исходных ключей в группы (Рисунок 3.18). При это сокращается количество разрядов, необходимое для указания одной из групп. В каждом регистре ключа формируется де групп. Это позволяет использовать меньшее количество входов мультиплексоров, а их количество уменьшается в де раз. При этом на каждый вход мультиплексора передается уже не один, а Ье / де разряд. Общее количество разрядов маски уменьшается:

ш—) ¡е •де

(3.9)

де ' Ье

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

- Количество мультиплексоров составляет:

Ьс

- Количество информационных входов мультиплексора:

- Разрядность адреса: 1од2( ——).

. Ьсгс 9с .

дс

- Разрядность информационного слова мультиплексора: —.

9с

- Общая аппаратная сложность: Ц^ • = .

^ Ьс дс дс дс

- Генерация с ограничением по позициям разрядов позволяет сократить размер маски благодаря назначению каждому разряду регистра

Составной ключ

Рисунок 3.18 — Структура генератора ключей с группировкой по разрядам исходных ключей (до = 2)

ключа ограниченного количества позиций в регистре составного ключа (Рисунок 3.19). Если для генерации без ограничений любой разряд исходных ключей может определять любой разряд составного ключа, то при ограничении по позициям он может определять только ограниченное множество позиции. Примером может являться разделение исходных ключей на байты, а позиция разряда в байте должна оставаться и в составном ключе. Пусть регистр составного ключа разделен на группы позиций и в каждой группе содержится ро разрядов. Тогда размер маски составит:

, Ъо • го • ро

%2(—уо—) • /о

(3.10)

Рисунок 3.19 — Структура генератора ключей с ограничением по позициям разрядов (ро =1)

Аппаратная сложность схемы с ограничением по позициям разрядов определяется следующим образом:

- Количество мультиплексоров составляет: /о.

- Количество информационных входов мультиплексора: Ьс^Срс.

- Разрядность адреса: 1од2(Ьс'гсрс).

- Разрядность информационного слова мультиплексора: 1.

- Общая аппаратная сложность:¡с • = рс • Ьс • гс, (рс < ¡с). Генерация с ограничением по регистрам ключей предполагает, что функция каждого разряда составного ключа использует только ограниченное количество регистров исходных ключей (Рисунок 3.20). Например, общее количество регистров исходных ключей составляет гс, но при формировании бита составного ключа могут использоваться разряды только из гс регистров. Размер маски для этого варианта составит:

1од2(Ьс • гс) • ¡с.

(3.11)

Рисунок 3.20 — Структура генератора ключей с ограничением по регистрам ключей (гс = 1 )

Аппаратная сложность схемы с ограничением по регистрам определяется следующим образом:

- Количество мультиплексоров составляет: ¡с.

- Количество информационных входов мультиплексора: Ьс • гс.

- Разрядность адреса: 1од2(Ьс • гс).

- Разрядность информационного слова мультиплексора: 1 .

- Общая аппаратная сложность:¡с • Ьс • гс, (гс < гс).

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

мультиплексор принимает группы только от го регистров. Тогда размер маски составляет:

10д2(^) . ^ (3.12)

до Ьо

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

- Количество мультиплексоров составляет: .

- Количество информационных входов мультиплексора: ^дЪ1.

- Разрядность адреса: 1од2(7-С1£).

дс

- Разрядность информационного слова мультиплексора: —.

дс

- Общая аппаратная сложность: Ц31 • — • — = ?1ГС-ЬС.

^ г Ъс дс дс дс

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

го • (Ьо + 1од2(/о)). (3.13)

Аппаратная сложность последовательной схемы определяется по количеству элементарных логических элементов. Схема сдвига при последовательной реализации на регистру сдвига содержит О(Ьо) триггеров. Тогда общая аппаратная сложность составит О(Ьо • го).

Рисунок 3.21 — Структура генератора ключей последовательного типа

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

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

передается его порядковый номер в команде, что и указывает на поступление соответствующего тега. Набор команд предусматривает 6 форматов команд (Рисунок 3.22).

Код Способ операции адресации г

Формат Б

Формат А

Л г~

Операнды

_А_

коп СА п.и. п.и. ТегО СТР

коп СА п.и. Тег 1 ТегО СТР Ключ

коп СА Тег 2 Тег 1 ТегО СТР Ключ Значение

коп СА Тег 2 Тег 1 ТегО СТРР СТР А СТР В

коп СА Тег 2 Тег 1 ТегО СТРР СТР А Ключ

коп СА н.и. Тег 1 ТегО Адрес

Рисунок 3.22 — Форматы команд Процессора обработки структур

Формат S используется для команд, в которых кодируется номер структуры. Это такие команды, как: удаление структуры и мощность, поиск минимального и максимального значения. Размерность такой команды составляет: с+р+в бит.

Формат SK содержит поле номера структуры и ключ поиска. Формат используется в таких командах, как поиск и удаление. Размерность команды формата SK составляет: с + 2 * р + в + к бит.

Формат SKD содержит поле номера структуры, ключа и поле данных, что делает такую команду наиболее длинной из всех форматов. Размер команды составляет: с + 3 * р + в + к + ( бит. Например, для СП, хранящего 8 структур (в = 3), ключ и данные содержат 32 разряда, размер кода операции 5 бит, а способ адресации для трех операндов 6 бит. Тогда суммарный размер команды формата SKD составит 80 бит. Размер команды формата S при таких параметрах составит всего 10 бит (в 8 раз меньше).

Формат SSS содержит три поля номеров структур, что необходимо в таких командах, как объединение, пересечение и дополнение. Размер команды составляет с + 3 * р + 3 * в бит.

Формат SSK используется для среза: в команде указывается номера структуры результата, номер исходной структуры, а также значение ключа среза. Размер команды составляет c + 3 * p + 2 * s + k бит.

Формат A используется для команд перехода. В команде указывается адрес перехода и способ адресации. При непосредственной адресации переход происходит незамедлительно. При внешней адресации СП получает из ЦП адрес перехода. Размер команды составляет c + p + adr бит.

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

Можно привести следующий пример. Пусть необходимо выполнить поиск в структуре G по ключу, значение которого заранее для СП неизвестно (внешняя адресация). Данную ситуацию будем отображать знаком «?»(смотри Таблицу 14), который означает, что операнда не валиден, в результате чего для выполнения команды требуется получить его по шине данных из ЦП. Результат выполнения команды SEARCH отправляется в очередь данных в ЦП.

Таблица 14 — Структура данных G(V,E)

Выполнить поиск в структуре G по ключу KEY

Поток ЦП Поток СП

1. Передать в СП значение Key Поиск в структуре G по ключу «?»

2. Получить из СП результат Передать в ЦП результат

В этом примере необходимо передавать номер тега операнда и сам операнд. Так как количество тегов невелико, а передачу целесообразно организовать в пакетном режиме, возможно использовать адресную информацию в качестве номера тега. Например, если базовый адрес СП на шине обозначить за BASE_ADR, то по смещению BASE_ADR[0] можно обратиться к операнду с тегом 0, по адресу BASE_ADR[1] к тегу 1 и т.д.

3.4.5 Набор машинных команд

Машинные команды процессора обработки структур представляют собой сложные действия высокого уровня, основанные на операциях дискретной математики [27; 32; 122]. В связи с этим будем называть набор команд вычислителя, реализованного на основе Процессора обработки структур, набором команд дискретной математики (Discrete Mathematics Instructions Set ^mputer, DISC) Общие принципы обработки множеств были обсуждены ранее в главе 2 разделе 2.3. В этом разделе рассмотрим реализацию основных команд, определим мнемокоды команд для последующей реализации ассемблера. В настоящий момент в СП реализовано 19 команд обработки множеств и структур данных (Таблица 15).

Таблица 15 — Базовые операции над структурами данных

Команда Мнемокод Операнды* Результаты* СОПР** МКОД***

Поиск SEARCH,SRCH R К - - С К З + +

Добавление INSERT,INS R К - З С К З + +

Удаление DELETE,DEL R К - - С К З + +

Удаление структуры DELS R - - - С - - + +

Максимум MAX R - - - С К З + +

Минимум MIN R - - - С К З + +

Мощность CARDINALITY,C R - - - С К З + +

И AND R A B - С - - + +

ИЛИ OR R A B - С - - + +

НЕ NOT R A B - С - - + +

Срез LS LS R A К - С - - + +

Срез LSEQ LSEQ R A К - С - - + +

Срез GR GR R A К -С - - + +

Срез GREQ GREQ R A К - С - - + +