Студопедия
МОТОСАФАРИ и МОТОТУРЫ АФРИКА !!!


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

Алгоритм выделения ветвей независимых операций в последовательной программе для её распараллеливания




Критерий выделения параллельных ветвей для машин класса МКМД (MIMD)

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

Для того, чтобы проиллюстрировать вышесказанное рассмотрим небольшой пример:

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

№ операций Операторы
A=1; B=3; C=8; D=A+B*5; X=6/(D*C-2*A); Y=8*X/B; Z=4+A+D;

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

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

Таблица 3.1

Переменная Номера операций
A O     I I   I
B   O   I I    
C     O   I    
D       O I   I
X         O I  
Y           O  
Z             O

-где I-означает что переменная является входной, а O-выходной в данной операции.

Для того чтобы выделить параллельные ветви в нашем фрагменте программы, надо определить взаимозависимость операций по данным. Во первых, параллельно не могут выполнятся операции где одни и те же переменные создаются (являются выходными) и используются (являются входными). Например: операции 2 и 4. Во вторых, при любом раскладе, данные не могут быть использованы до того, как они были инициализированы. Последнее условие влияет на распределение операций по ярусам графа ЯПФ. Все эти условия можно учесть, используя таблицу 3.1. Например: операция 5 может идти только после операции 2 из-за использования переменной B в операции 4 при вычислении D.

Ниже представлен получившийся граф ЯПФ фрагмента нашей программы (см. рис 3.1).

 
 

Рис. 3.1. Граф ЯПФ

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








Дата добавления: 2015-05-10; просмотров: 541; Опубликованный материал нарушает авторские права? | Защита персональных данных | ЗАКАЗАТЬ РАБОТУ


Не нашли то, что искали? Воспользуйтесь поиском:

Лучшие изречения: Для студента самое главное не сдать экзамен, а вовремя вспомнить про него. 10393 - | 7662 - или читать все...

Читайте также:

 

3.233.221.149 © studopedia.ru Не является автором материалов, которые размещены. Но предоставляет возможность бесплатного использования. Есть нарушение авторского права? Напишите нам | Обратная связь.


Генерация страницы за: 0.002 сек.