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

Оглавление.

Введение.

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

§ 1 Вычисления на компьютерах dataflow с использованием оптической ассоциативной памяти.

§2 Графовая модель вычислительного алгоритма.

§3 Математическая модель оптической АП.

§4 Математическая модель иерархической модульной оптической ассоциативной памяти.

§5 Оценки функционала на тестовых потоках данных.

§6 Вероятностное представление потоков данных для классов вычислительных алгоритмов.

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

§ 1 Описание применяемого в работе генетического алгоритма.

§2 Структура функционала качества.

§3 Исследование влияния размера популяции на сходимость оптимизационного процесса.

§4 Исследование влияния операторов ГА на поиск оптимального распределения потока данных. п. 1 Влияние выбора начальных разрезаний на точность метода. п.2 Масштабирование функционала. п.З Исследование возможностей стратегий отбора при формировании разрезаний. п.4 Зависимость ошибки вычисления максимума функционала от применяемого оператора скрещивания. п.5 Влияние модели мутации на распределение токенов по модулям. п.6 Использование элитизма при построении разрезания.

§5 Сравнение ГА с методом Монте-Карло.

Глава 3. Исследование распределения потоков данных для различных вычислительных алгоритмов.

§ 1 Построение хэширования для класса алгоритмов.

§2 Исследование потоков данных для решения реальных задач многомерного моделирования МГД устойчивости плазмы в установках управляемого термоядерного синтеза.

§3 Эволюционная модель модульной оптической АП.

§4 Система программ анализа и оптимизации структуры модульной ассоциативной памяти. п. 1 Общая характеристика системы программ. Состав модулей. п.2 Конструктор потоковых графов алгоритмов. п.З Эмулятор потоковой машины. п.4 Система оптимизации. п.5 Система хранения результатов экспериментов. п.6 Система анализа хэширования. п.7 Система отображения.

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

Проблема эффективного отображения вычислительных алгоритмов на архитектуру параллельной вычислительной системы является важной при математическом моделировании в различных областях: моделировании атмосферы и гидродинамики течений, молекулярной биологии, генной инженерии [81,5].

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

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

Максимальная производительность АН в настоящее время ограничена возможностью отвода тепла, возникающего при срабатывании ключей. Нагрев пропорционален объему такой памяти [9]. Поэтому было предложено разбить большую АП на меньшие модули. Размер матрицы каждого модуля в отдельности будет меньше, что позволит повысить его максимальную производительность. В тоже время поиск модуля будет являться адресным, хотя сам модуль - ассоциативным. В нашей стране академик B.C. Бурцев с сотрудниками проводит фундаментальные исследования в области принципов параллельных вычислений, основанных на потоке данных [3]. В последнее время ими был предложен целый ряд архитектур с использованием иерархической модульной АП.

При этом для таких архитектурных решений возникает задача распределения потоков данных по модулям АП. При выборе распределения необходимо учитывать следующее [3]:

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

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

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

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

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

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

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

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

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

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

Диссертация состоит из введения, трех глав, заключения и литературы.

Выводы.

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

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

3. Приведено исследование потоков данных, соответствующих решению реальных задач широкомасштабного моделирования 3/) МГД устойчивости плазмы в установках управляемого термоядерного синтеза.

4. Предложена эволюционная модель модульной АП для систем потока данных, основанная на эволюционных вычислениях.

Заключение.

В работе получены следующие основные результаты:

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

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

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

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

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

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

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

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