Передача данных от одного процессора всем остальным процессорам сети

Передача данных между двумя процессорами сети

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

Операция передачи данных (одного и того же сообщения) от одного процессора всем остальным процессорам сети (one-to-all broadcast or single-node broadcast) является одним из наиболее часто выполняемых коммуникационных действий; двойственная операция передачи – прием на одном процессоре сообщений от всех остальных процессоров сети (single-node accumulation). Подобные операции используются, в частности, при реализации матрично-векторного произведения, решении систем линейных уравнений при помощи метода Гаусса, поиска кратчайших путей и др.

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

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

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

Для гиперкуба рассылка может быть выполнена в ходе N- этапной процедуры передачи данных. На первом этапе процессор-источник сообщения передает данные одному из своих соседей (например, по первой размерности) – в результате после первого этапа имеется два процессора, имеющих копию пересылаемых данных (данный результат можно интерпретировать также как разбиение исходного гиперкуба на два таких одинаковых по размеру гиперкуба размерности N-1, что каждый из них имеет копию исходного сообщения). На втором этапе два процессора, задействованные на первом этапе, пересылают сообщение своим соседям по второй размерности и т.д. В результате такой рассылки время операции оценивается при помощи выражения.

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

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

(как и ранее, при достаточно больших сообщениях, временем передачи служебных данных можно пренебречь).

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

Для гиперкуба алгоритм рассылки (и, соответственно, временные оценки длительности выполнения) при передаче пакетов не отличается от варианта для метода передачи сообщений.

Сложные задачи. Масштабируемость параллельных вычислений. Функция изоэффективности

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

где V – количество операций, которые необходимо выполнить при решении задачи на ВС; n – число параллельных ветвей или число вычислителей, на которых решается задача, n≥2;

t(V,n) – время, затрачиваемое на:

· синхронизацию параллельных ветвей алгоритма,

· настройку (программирование структуры) системы,

· реализацию обменов информацией между ветвями (вычислителями);

T(V,n) – время, расходуемое системой собственно на счет.

На основе анализа задач и опыта их решения (с использованием методики крупноблочного распараллеливания) на вычислительных системах установлено, что при n = const показатель ε(V,n) асимптотически стремится к нулю с ростом объема операций в задаче, т.е. имеет место: ε(V,n) → 0 при V → ∞. Значения ε(V,n) будут практически удовлетворительными при выполнении неравенства

V ≥n*10^k

где k – эмпирический коэффициент, k≥1. Очевидно, что имеет место зависимость k от быстродействия ν каналов связей между вычислителями: k→ 1 при ν → ν*, где 1/ν* – время обращения к локальной памяти в вычислителе. При удовлетворении неравенства достигается адекватное размещение параллельной программы на системе из n вычислителей (при произвольной структуре сети связей) и обеспечивается эффективное использование этих вычислителей.

Таким образом, если объем операций V, связанных с решением задачи, на несколько порядков превышает число вычислителей n, на которых должно осуществляться её решение, то достигается эффективное функционирование системы.

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