Кинетическая модель мелкозернистого параллелизма

• Автор: Горбунова, Екатерина Олеговна
• Шифр специальности: 05.13.17
• Научная степень: Кандидатская
• Год защиты: 2001
• Место защиты: Красноярск
• Количество страниц: 88 с.

Оглавление
Введение

Актуальность проблемы.

Цель работы.

Научная новизна.

Практическая значимость.

Апробация работыб

Структура диссертации.

Содержание работы.

Глава 1. Известные модели мелкозернистого параллелизма и близкие к

Глава 2. Основные понятия кинетической машины Кирдина. Модели выполнения и методы реализации.
1. Понятие кинегической машины Кирдина.
2. Модели выполнения программы.
2.1. Последовательная модель
2.2. Параллельнопоследовательная модель
2.3. Максимальная параллельнопоследовательная модель.
3. Методы реализации.
3.1. Статистический метод реализации
3.2. Решеточнопроцессорный метод реализации
Глава 3. Свойства программ, состоящих из одной команды
3.1. Распад
рименимость
Финитность
Детерминированность.
3.2. Синтез.
Применимость.5
Финитность
Детерминированность.
3.3. Прямая замена
Применимость
Финитность
Детерминированность.
Глава 4. Алгоритмическая универсальность кинетической машины
Кирдина.
Глава 5. Примеры применения КМК.
5.1. Бесструктурная память
5.2. Подпрограммы и структурное программирование кинетической машины Кирдина.
ЗАКЛЮЧЕНИЕ
Литература


Модели выполнения и методы реализации. Понятие кинегической машины Кирдина. Модели выполнения программы. Максимальная параллельно-последовательная модель. Методы реализации. Глава 3. Детерминированность. Синтез. Применимость. Детерминированность. Детерминированность. Глава 4. Кирдина. Глава 5. Примеры применения КМК. Подпрограммы и структурное программирование кинетической машины Кирдина. Литература. Проблема эффективного программирования при наличии мелкозернистого параллелизма пока еще далека от своего решения. Хорошо известна “гипотеза М. Минского”: производительность параллельной системы растет (примерно) пропорционально логарифму числа процессоров и уж по крайней мере является выпуклой вверх (т. Сейчас все чаще для преодоления этого ограничения применяется следующий подход: для различных классов задач строятся максимально параллельные алгоритмы решения, использующие какую-либо абстрактную архитектуру (парадигму) мелкозернистого параллелизма, а для конкретных параллельных компьютеров создаются средства реализации параллельных процессов заданной абстрактной архитектуры. В результате появляется эффективный аппарат производства параллельных программ. Модели мелкозернистого бесструктурного параллелизма могут использоваться для решения проблемы эффективного параллелизма по следующей схеме (рис 1). Новым перспективным направлением развития мелкозернистого параллелизма считается бесструктурный параллелизм, где вычислительные элементы не взаимосвязаны и хаотически взаимодействуют между собой. В данной работе рассматривается такая абстрактная парадигма параллельных вычислений - кинетическая машина Кирдина. Ожидается, что эта модель сыграет ту же роль для параллельных вычислений, что и нормальные алгоритмы Маркова, машины Колмогорова и Тьюринга или схемы Поста для последовательных вычислений. Кирдина. Доказана теорема об алгоритмической универсальности данного формализма. Также предложено расширение кинетической машины Кирдина, которое делает се более мощным инструментом для программирования. Предложены эффективные параллельные решения некоторых задач, для которых параллельное решение является наиболее органичным. Уточнение формулировки понятия кинетической машины Кирдина. Рассмотрение основных моделей выполнения программ кинетической машины Кирдина и методов реализации. Исследование применимости, дегерминированности и финитности простых программ кинетической машины Кирдина и получение соответствующих критериев. Исследование алгоритмических возможностей кинетической машины Кирдина. Соотнесение се со стандартными алгоритмическими формализмами и другими моделями мелкозернистого параллелизма. Применение кинетической машины Кирдина для решения модельных задач. Кирдина, использующее подпрограммы, решен ряд задач в терминах кинетической машины Кирдина. Кинегичсская машина Кирдина может быть использована двояким образом. Во-первых, при решении произвольных задач, в терминах кинетической машины Кирдина можно создать максимально параллельный эффективный алгоритм для решения задачи, а потом выполнять этот алгоритм на имеющихся параллельных компьютерах, возможно, укрупняя параллелизм наиболее подходящим образом для имеющейся аппаратной базы. Во-вторых, кинетическая машина Кирдина может служить универсальной формальной моделью для химических и ДНК-вычислений, обзор работ в этих областях дан в первой главе диссертации. Основные результаты работы докладывались и обсуждались на VI и VII Всероссийских семинарах «Нейроинформатика и сё приложения» проходивших в Красноярске в , годах, на конференциях молодых ученых Красноярского научного центра в , , гг. Третьем Сибирском конгрессе но прикладной и индустриальной математике (TNPRIM-), на Первом Всесибирском конгрессе женщин-математиков в г. Красноярске в г. Всероссийской научно-технической конференции «Нейроинформатика-» в г. Москве, VI Международной конференции «Математика. Компьютер. Образование» в г. Пущино в г. Новые информационные технологии” в г. Москве в г. XII Международной конференции по нсйрокибсрнстикс в г. Ростов-на-Дону в г.