paralllel_data_processing (811086), страница 13
Текст из файла (страница 13)
SEND(ALL)A,(B(I),I=1,5),(B(I,1),I=1,5),(B(I,I),I=1,5) перешлет всем процессам программы следующие объекты: - массив А целиком, - первый столбец массива В, - диагональные элементы массива В.
Этим способом можно организовать не только передачу (прием) любых вырезок их массивов, но и множества одинаковых данных, например, переслать пять копий массива В: SEND(ALL)(B,I=1,5)
-
Идентификация абонентов при передачи сообщений в языке Фортран-GNS.
Идентификация абонентов при организации передачи сообщений может производится по имени процесса (массиву имен) или идентификатору задачи, по описанию которой образован процесс. Есть способы безадресных (широковещательных) посылок сообщений - "всем", и приема от произвольного отправителя сообщений с заказанной "маркой" - тегом. Идентификация абонентов может быть произведена:
По имени процесса
Основным способом идентификации абонентов при передаче сообщений является задание имени процесса (системного идентификатора) переменными типа TASKID и стандартными функциями этого типа MYTASKID, РАRENT и МАSTER. Использование этих стандартных функций является единственным первоначальным способом сослаться из порождаемых процессов на имена порождающих процессов, так как начальный диалог между процессами возможен только на уровне порожденный-порождаемый. Путем обмена сообщениями можно организовать передачу имен процессов для организации произвольной абонентской сети.
Переменные типа TASKID - параметры операторов передачи сообщений могут:
- ссылаться на функционирующий процесс,
- ссылаться на завершенный процесс,
- иметь значение .NOTASKID.,
- быть не инициализированными.
Реакция программы на три последних случая не оговаривается в языке и определяется реализацией. Одно из решений - игнорирование оператора обмена сообщениями с такими параметрами (кроме синхронных операторов, для которых такой случай следует считать "авостом" в программе). Процесс-отправитель имеет возможность организовать дублирование передаваемых сообщений для передачи их одновременно нескольким процессам-получателем. Для этого допускается задание абонентов в параметрах оператора передачи сообщений в виде массива типа TASKID. Сообщение будет передано при этом всем процессам, на которые есть ссылки через элементы массива. Данная массовая операция предпочтительнее передачи сообщений, организованной поэлементной циклической конструкцией. Цикл предписывает порядок перебора элементов массива - абонентов передачи, а для синхронного обмена и завершение очередной передачи до посылки следующего сообщения. Массовая операция обмена может проводиться параллельно и независимо для всех заказанных абонентов. Массовые операции ассиметричны, нельзя заказать ожидание сообщения от нескольких процессов сразу. Теговая идентификация сообщений и конструкции выбора допускает некоторую вольность в указаниях об именах отправителей.
По имени программной единицы-задачи
Задание в операторе передачи сообщений в качестве адресата - получателя имени программной единицы-задачи означает рассылку сообщений всем процессам, образованным по описанию указанной задачи на момент выполнения оператора. Случай, когда к этому моменту не было образовано ни одного процесса по указанному образцу, можно рассматривать по аналогии с передачей сообщения процессу с "именем" - .NOTASKID. . Возможность задать в качестве адресата имя главного процесса уточняется в описаниях входных версий языка.
Безымянные абоненты
Специальный идентификатор ALL в параметре адресата-получателя сообщения предписывает передать данное сообщение всем процессам программы, инициализированным на данный момент.
Передача сообщений двумя последними способами предполагает возможность параллельной рассылки сообщений и исключение процесса, выполняющего оператор передачи сообщения, из списка абонентов - получателей.
Помеченные сообщения
При передаче сообщений асинхронным способом сообщения при отправлении помечаются целым числом - тегом. Эта разметка дает возможность абонентам идентифицировать сообщения от разных операторов передачи сообщений одного процесса. Получив сообщение с заданным тегом, процесс может узнать имя отправителя, через аппарат SENDERов. Это замечание верно и для передачи сообщений без ожидания.
-
Автоматическое распараллеливание последовательных программ.
http://parallel.ru/tech/tech_dev/auto_par.html
-
Семантика циклов, выполняемых параллельно на ОКМД системах.
-
Алгоритмы преобразования программ методом координат.
Одним из методов распараллеливания программ является метод координат, обеспечивающий векторизацию циклов для синхронных ЭВМ (ОКМД - SIMD архитектуры). Семантика синхронных циклов следующая: для каждой итерации цикла назначается процессор; вычисления должны производиться всеми процессорами (процессорными элементами) параллельно и синхронно. Операторы тела цикла выполняются по очереди, но каждый оператор выполняется всеми процессорами одновременно. При выполнении оператора присваивания сначала вычисляется правая часть, затем одновременно выполняется операция присваивания для всех элементов массива левой части.
Теоретическое обоснование классического метода координат предложено Лэмпортом. Метод применим для канонических ("чистых") циклов, тела которых состоят только из операторов присваивания, причем управляющая переменная заголовка цикла (параметр цикла) должна входить в индексные выражения операторов тела цикла линейно. Метод предназначен для синхронной векторизации одномерных циклов (многомерные циклы можно рассматривать по каждому параметру отдельно). Идея данного метода состоит в том, что для индексов, содержащих параметры цикла, рассматривается порядок следования, который и определяет очередность выборки/записи соответствующего элемента массива. Так как рассматриваются только линейные индексные выражения, порядок следования определяется значениями соответствующих алгебраических выражений. Строится граф характеристических множеств всех индексов, и при отсутствии в графе петель делается заключение о возможности векторизации всего цикла.
В некоторых случаях (устранимая векторная зависимость) векторизация возможна лишь в случае переупорядочивания - перестановки операторов цикла или путем введения временной переменной (массива), куда будут копироваться элементы вектора для защиты перед их изменением для последующего использования в исходном виде. Итак, метод координат:
- позволяет определить возможность выполнения цикла в синхронном режиме;
- содержит алгоритмы преобразования тела цикла к синхронному виду.
Например, по Лэмпорту, цикл:
DO 24 I=2,M
DO 24 J=2,N
21 A(I,J) = B(I,J)+C(I)
22 C(I) = B(I-1,J)
23 B(I,J) = A(I+1,J) ** 2
24 CONTINUE
преобразуется в цикл:
DO 24 J=2,N
DO 24 SIM FOR ALL I {i:2<=i<=M}
C SIM - SI Multeneusly (одновременно)
TEMP(I) = A(I+1,J)
21 A(I,J) = B(I,J)+C(I)
23 B(I,J) = TEMP(I) ** 2
22 C(I) = B(I-1,J)
24 CONTINUE
Конструктивный алгоритм реализации метода координат.
Пусть, цикл одномерный, все операторы тела - операторы присваивания, в левых частях которых - переменные с индексом - параметром цикла. Индексы линейные, т.е. имеют вид i+/-b,где b - константа. Определяются отношения следования для всех пар одноименных переменных с индексами: генерируемых переменных (переменные в левой части операторов присваивания - f) и используемых переменных (входящих в формулы правых частей - q). Отношение следования для одной пары зависит от порядка обращения к одному и тому же элементу массива при выполнении цикла. Так, для A(I) = A(I+1) отношение можно кодировать: f<q . Для многомерных циклов для всех пар (f,q) определяются направляющие вектора, элементы которых состоят из символов (=, >, <) в позиции соответствующего индекса, которая определяется порядком индексов в гнезде цикла. В примере Лемпорта (исходном) для А вектор имеет вид: (<,=).
Для тела цикла, состоящего из одного оператора, отношения, и соответственно, семантика выполнения, могут быть: < > = и их сочетание. Например, тело цикла: A(I) = (А(I)+A(I+1))/2 допускает векторное выполнение; оно невозможно при наличии в операторе хотя бы одного соотношения: f>q. Для тела цикла: A(I) = A(I+C))/2 при С>0 возможно синхронное выполнение, при С=0 кроме синхронного, возможно параллельное асинхронное; а при С<0 параллельное выполнение невозможно.
Для многомерных (тесногнездовых) циклов такое исследование может проводиться для каждого параметра, а для распараллеливания выбираться наиболее оптимальный вариант. Для самого внутреннего цикла определение следования можно проводить, считая его одномерным. Для любого другого цикла, исследование можно проводить по такой же схеме, если семантика цикла допускает перестановку его на позицию самого внутреннего. Перестановка допустима, если для всех новых направляющих векторов крайне левый, отличный от = , элемент сохранил направление. Например, для двумерного цикла, наличие вектора (<,>) делает перестановку некорректной. Так для цикла:
DO 99 J=2,M
DO 99 K=2,M
99 U(J,K) = (U(J+1,K)+U(J,K+1)+U(J-1,K)+U(J,K-1)) .25
направляющие вектора:
1 <U(J,K),U(J+1,K)> = (<,=)
2 <U(J,K),U(J,K+1)> = (=,<)
3 <U(J,K),U(J-1,K)> = (>,=)
2 <U(J,K),U(J,K-1)> = (=,>)
Отсюда:
- операторы циклов по I и J можно менять местами,
- часть оператора, включающая вхождения из векторов 1 и 2, можно вынести в отдельный оператор, который векторизуется как по I так и по J.
Для двух операторов тела цикла отношения следования переменных с индексами можно систематизировать и кодировать так (qi в общем случае, список - информационные поля q и f) : А - независимые отношения В - (qi>qj) , C - (qi<qj) , K - (qi=qj) G - B+K,B+C,B+K+C , Н - неоднозначные отношения. Тогда по координатам приводимой ниже таблице можно определить типы связей и метод выполнения цикла для этих операторов. Если объединить информационные поля двух операторов , то таблицу можно использовать для анализа третьего оператора и т.д.
* Таблица решений для метода координат
* Оператор 1 O1 = I1 Oi,Ii - список переменных с индексами
* Оператор 2 O2 = I2 -> - порядок анализа отношений
*---------------------------------------------------------------------
* . O2 -> I1 .
* . A . B . K . C . G . H .
* . HEЗАВ. . O > I . O = I . O < I . O <=>I * .
* I2 -> O1 . . . . . . .
*----------------------------------------------------------------------
* . . . . . . .
* A HEЗАВ. . P . R . S . M . R(K,C). T .
*______________________________________________________________________
* . . . . . . .
* B I > O . R . R . M(B) . M(B) . R(K,C). T .
*______________________________________________________________________
* . . . . . . .
* K I = O . S . T . S . M . T . T .
*______________________________________________________________________
* . . . . . . .
* C I < O . M . T . M . M . T . T .
*______________________________________________________________________
* . . . . . . .
* G I <=> O. M(B) . T . M(B) . M(B) . T . T .
*______________________________________________________________________
* . . . . . . .
* H * . T . T . T . T . T . T .
*______________________________________________________________________
* Кодировка отношений следования
* А - независимые отношения
* В - (qi>qj) , C - (qi<qj) , K - (qi=qj)
* G - B+K,B+C,B+K+C
* Н - неоднозначные отношения
* TИПЫ CBЯЗEЙ
* P - независимые операторы
* M - SIMD , M(EA) - SIMD с защитой EA
* R - SIMD с реверсом, R(EA) - и с защитой EA
* S - PAR (асинхронная параллельность)
* T - запрет векторизации
* Защита ЕА - копирование массивов ЕА перед
В общем случае, алгоритм векторизации методом координат с использования данной таблицы следующий.
Обработка тела цикла начинается с анализа на возможность векторного выполнения каждого оператора тела в отдельности. Затем к первому оператору добавляется второй и проводится анализ на возможную их векторизацию. Пара получает тип, определяющий возможность векторизации ее компонент, информационные поля операторов сливаются, и на следующем шаге применения процедуры векторизации пара рассматривается как единый супероператор. Таким образом из всех операторов тела цикла образуется один супероператор и, если его тип есть Т, то векторизация тела цикла невозможна. Для всех других типов производится обратный анализ полученного графа (супероператора). Если при этом связки имели тип R или R(EA),M(EA), то хотя они и допускают асинхронное параллельное выполнение, но необходимы преобразование тела цикла. Связки типа Т дают операторы, векторизация которых невозможна. Интерпретация остальных типов связок очевидна. В процессе формирования супероператоров к связкам типа Т могут применяться процедуры поиска минимальных границ области типа Т и чистки области Т.
Примеры векторизации
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
