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

• Автор: Чумаченко, Георгий Олегович
• Шифр специальности: 05.13.15
• Научная степень: Кандидатская
• Год защиты: 2005
• Место защиты: Москва
• Количество страниц: 162 с. : ил.

Введение

Глава 1. Исследование модели вычислений, управляемых потоком данных

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

1.2 Основные принципы модели вычислений, управляемых потоком данных

1.3 Эволюция модели вычислений, управляемых потоком данных.

1.3.1 Статическая модель вычислений, управляемых потоком данных

1.3.2 Динамическая модель вычислений, управляемых потоком данных.

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

1.5 Выводы к первой главе

Глава 2. Разработка принципов функционирования ассоциативной памяти для управления параллельными вычислительными процессами.
2.1 Исследование гибридной динамической модели вычислений, управляемых потоком данных, с динамически формируемым контекстом.
2.1.1 Структура программы и принцип се выполнения
2.1.2 Принципы управления контекстом параллельных вычислительных процессов.
2.1.3 Принципы многократной рассылки операндов.
2.1.4 Принципы определения готовности параллельных вычислительных процессов к запуску
2.1.5 Принципы распределения параллельных вычислительных процессов по процессорным элементам.
2.1.6 Механизмы управления параллельными вычислительными процессами
2.2 Постановка задачи и пути ее решения
2.3 Общие принципы реализации механизмов управления параллельными вычислительными процессами в ассоциативной памяти
2.3.1 Система команд ассоциативной памяти
2.3.2 Общий принцип выполнения команда АП
2.3.3 Исследование особенностей выполнения команд АП, обусловленных наличием кратности
2.4 Алгоритмы выполнения команд ассоциативной памяти.
2.4.1 Принципы выполнения команды Синхронизация запуска подпрограммы узла по входным данным.
2.4.2 Принципы выполнения команды Аппаратная косвенная переадресация токена .
2.4.3 Принципы выполнения команды Аппаратнопрограммная косвенная переадресация токена
2.4.4 Принципы выполнения команды Подсчет количества событий.
2.4.5 Принципы выполнения команды Стирание токена
2.4.6 Принципы выполнения команды Чистка ассоциативной памяти
2.4.7 Обобщение вариантов взаимодействия токенов различных типов. Таблица взаимодействия токенов.
2.5 Выводы к второй главе
в Глава 3. Принципы функционирования аппаратуры ассоциативной памяти ВСАРР
3.1 Структура и принципы функционирования вычислительной системы с автоматическим распределением ресурсов.
3.2 Исследование особенностей функционирования Блока ассоциативного сравнения ассоциативной памяти ВСАРР.
3.3 Разработка структуры ассоциативной памяти ВСАРР
3.3.1 Принципы модульного построения ассоциативной памяти ВСАРР
3.3.2 Метод распределения токенов по модулям ассоциативной памяти
3.3.3 Особенности использования механизма маскирования полей ключа токена, обусловленные модульным построением ассоциативной памяти
3.4 Принципы функционирования аппаратуры модуля ассоциативной памяти ВСАРР .
3.4.1 Структурная схема и общий алгоритм функционирования МАП.
3.4.2 Реализация механизма блокировки взаимодействия токенов различных типов .
3.4.3 Обработка исключительных ситуаций в ассоциативной памяти.
3.4.4 Принципы прерывания обработки множественного отклика.
3.4.5 Принципы выполнения команд АП, взаимозависимых между собой по ключу верхнего токена.
3.4.6 Принципы работы БВК при выполнении команд АП, взаимозависимых между собой по кратности нижнего токена.
3.5 Выводы к третьей главе
Глава 4. Создание макета модуля ассоциативной памяти вычислительной системы с автоматическим распределением ресурсов
4.1 Выбор элементной базы макета. Обоснование использования ПЛИС как элементной базы макета
4.2 Структура макета ВСАРР и конструктивные решения для него
4.3 Инструментальная среда и методология проектирования макета
4.4 Макет модуля ассоциативной памяти ВСАРР.
4.4.1 Конструктивное исполнение модуля ассоциативной памяти
4.4.2 Функциональность Блока управления макета МАП.
4.4.3 Инициализация макета ВСАРР и начало работы.
4.4.4 Методы отладки макета модуля ассоциативной памяти
4.5 Перспективы развития макета модуля ассоциативной памяти.
4.6 Поведенческая модель ВСАРР
4.7 Краткий обзор средств системы программирования для ВСАРР
4.8 Результаты проверки эффективности использования команд ассоциативной памяти на примере тестового набора программ.
4.8.1 Результаты выполнения тестовой задачи умножения матриц.
4.8.2 Результаты выполнения тестовой задачи пузырьковой сортировки.
4.8.3 Общие выводы по проведенному тестированию
4.9 Выводы к четвертой главе
Заключение
Список литературы


Однако опыт параллельного программирования и выполнения параллельных программ на ЛВС фоннеймановской архитектуры показал, что фоннеймановская модель организации вычислительного процесса обладает существенными недостатками при ее применении для параллельных вычислений. Основным недостатком ЛВС фоннеймановской архитектуры является крайне низкая эффективность загрузки процессоров. Результаты тестирования высокопроизводительных вычислительных многомашинных и многопроцессорных комплексов при помощи известных пакетов тестирующих программ и 6, 7. Данные тесты показывают, что на рассматриваемом классе задач, которые являются весьма представительными, эффективность загрузки процессоров современных ЛВС фоннеймановской архитектуры колеблется в пределе от 5 до 8,9. В многопроцессорных ЛВС синхронизация параллельных вычислительных процессов обеспечивается за счет применения блокирующих переменных семафоров, мьютексов, ассоциированных с общими, разделяемыми данными или ресурсами. Перед тем, как обратится к общим данным, процесс обязан проверить состояние блокирующей переменной, и только в случае, если она свободна, занять ее и получить доступ к общим данным. В том случае, если блокирующая переменная занята, процесс должен ожидать ее освобождения. Такое ожидание может быть двух типов ожидание с активным опросом и ожидание с переключением процессов. При ожидании с активным опросом спинблокировка процессы, ожидающие доступа к заблокированным общим данным, постоянно опрашивают блокирующую переменную. Данный способ обеспечивает наиболее быстрый доступ ожидающего процесса к освободившемуся общему ресурсу, однако обладает значительными накладными расходами в виде тактов процессора, затраченных на опрос блокирующей переменной во время данного опроса процессор не выполняет полезной вычислительной работы. При ожидании с переключением процессов процесс, не получивший доступа к общим данным, снимается с выполнения на процессоре и переводится в состояние ожидания освобождения нужного ему общего ресурса. В этом случае нет накладных расходов на опрос блокирующей переменной, однако присутствуют значительные накладные расходы, связанные с переключением задач на процессорс5. Таким образом, оба случая обладают значительными накладными расходами, приводящими к падению реальной производительности многопроцессорной ПВС фоннеймановской архитектуры. Кроме этого, на синхронизацию параллельных процессов в многопроцессорных ПВС значительным образом влияет проблема когерентности кэшпамяти процессоров. Кэшпамять процессора предназначена для нивелирования разности скоростей работы процессора и основной памяти ВС. При введении кэшпамяти в процессоры многопроцессорной ПВС возникает новая и очень сложная проблема поддержки когерентности содержимого кэшпамяти. Если некоторый процессор изменяет значение переменной, копия которой записана в кэшпамять многих процессоров ПВС, то после данного изменения верное значение переменной содержится только в кэшпамяти процессора, изменившего его. При этом копии данной переменной в кэшпамяти других процессоров объявляются недействительными. Это приводит к тому, что при обращении к данной переменной процессоры, в кэшпамяти которых копии данной переменной были объявлены недействительными, вынуждены обращаться за ее значением в основную память, причем, не ранее того момента, когда значение переменной будет обновлено в памяти. Все это приводит к простою процессоров и падению числа команд, реально выполненных в единицу времени. При использовании метода активного ожидания для опроса блокирующей переменной, как правило, используется специальная команда ТЕ5ТАЫОЕТ5, , которая единым неделимым действием проверяет состояние блокирующей переменной и в любом случае устанавливает се в состояние блокировки. В том случае, если блокирующая переменная до установки в состояние блокировки была в свободном состоянии, процесс, выполняющийся на данном процессоре, получает доступ к разделяемому ресурсу. Если до установки блокирующей переменной в состояние блокировки она уже находилось в этом состоянии, то, соответственно, общий ресурс занят и процесс продолжает опрос блокирующей переменной.