10.Показатели эффективности параллельного алгоритма.
Ускорение, получаемое при использовании параллельного алгоритма для p процессоров, по сравнению с последовательным вариантом выполнения вычислений определяется
,
т.е. как отношение времени решения задач на скалярной ЭВМ к времени выполнения параллельного алгоритма (величина n используется для параметризации вычислительной сложности решаемой задачи и может пониматься, например, как количество входных данных задачи).
Эффективность использования параллельным алгоритмом процессоров при решении задачи определяется соотношением:
(величина эффективности определяет среднюю долю времени выполнения алгоритма, в течение которой процессоры реально используются для решения задачи).
Как следует из приведенных соотношений, в наилучшем случае Sp(n) = p и Ep(n) = 1. В 4 разделе данные показатели будут определены для ряда рассмотренных параллельных алгоритмов для решения типовых задач вычислительной математики.
11.Оценка максимально достижимого параллелизма. Анализ масштабируемости параллельных вычислений.
Оценка качества параллельных вычислений предполагает знание наилучших(максимально достижимых) значений показателей ускорения и эффективности
Получение идеальных величин Sp=p для ускоренияиEp=1 для эффективности может быть обеспечено не для всех вычислительно трудоемких задач
Анализ масштабируемости параллельных вычислений
Параллельный алгоритм называют масштабируемым(scalable), если при росте числа процессоров он обеспечивает увеличение ускорения при сохранении постоянного уровня эффективности использования процессоров
Накладные расходы (total overhead) появляютсязасчетнеобходимостиорганизациивзаимодействияпроцессоров, выполнениянекоторыхдополнительныхдействий, синхронизациипараллельныхвычисленийит.п.
T0=pTp-T1
Новыевыражениядлявременипараллельногорешениязадачииполучаемогоприэтомускорения:
Tp Sp= T1/ Tp
Тогдаэффективностьиспользованияпроцессоровможновыразитькак
Ep= Sp/p
-Если сложность решаемой задачи является фиксированной (T1=const), то при росте числа процессоров эффективность, как правило, будет убывать за счет роста накладных расходов T0,
–При фиксации числапроцессоровэффективностьиспользованияпроцессоровможноулучшитьпутемповышениясложностирешаемойзадачиT1,
–При увеличении числапроцессороввбольшинствеслучаевможнообеспечитьопределенныйуровеньэффективностиприпомощисоответствующегоповышениясложностирешаемыхзадач.
-Пусть E=const есть желаемый уровень эффективности выполняемых вычислений. Из выражения для эффективности можно получить
T0/T1=(1-E)/E
–Порождаемую последним соотношением зависимость n=F(p) между сложностью решаемой задачи и числом процессоров обычно называют функцией изоэффективности (isoefficiency function).
12.Процессы и потоки.
Процессы, задачи (потоки) и синхронизация.
Процесс – код программы в процессе выполнения.
Имеет собственную память под код и данные, отображение виртуальной памяти на реальную, а также стек.
Задача (поток, нить) – одна из ветвей выполнения процесса. Разделяет с процессом память под код и данные, отображение виртуальной памяти на реальную. Имеет собственный стек, то есть свои локальные переменные.
Взаимодействие задач легче, поскольку у них есть общая разделяемая память. Для процессов приходится организовывать обмен сообщениями.
Состояние параллельной программы состоит из значений переменных в некоторый момент времени. Программа начинает выполнение в некотором начальном состоянии. Процессы (потоки) выполняются параллельно и каждый изменяет состояние программы. Каждый оператор процесса изменяет состояние неделимым образом. Выполнение пар. программы можно рассматривать как последовательность состояний, которая называется история s0->s1->…->sn. Число возможных историй программы огромно.
на всякий случай//Цель синхронизации процессов – исключить нежелательные истории.
Взаимное исключение состоит в выделении в процессах критических секций, которые не прерываются другими процессами, использующими те же переменные. Условная синхронизация состоит в приостановке процесса до выполнения некоторого условия.
<await (B) S;>
Параллельная программа должна обладать некоторыми свойствами:
– безопасность (программа не переходит в нежелательное состояние)
– живучесть (программа обязательно оказывается в желательном состоянии)
Пример.
Поиск образца в файле
{открыть файл}
readln(f,s);
while not (eof(f)) do
begin
if search(p,s) then Writeln(s);
readln(f,s);
end;
Две строки в теле цикла можно попытаться выполнить параллельно. Однако они не являются независимыми. Нужно, чтобы чтение производилось не в ту строку, где происходит поиск.
{открыть файл}
readln(f,s1);
while not (eof(f)) do
begin
if search(p,s1) then Writeln(s1); //*
readln(f,s2); //*
s1:=s2
end;
Программа правильна, но неэффективна, поскольку надо потоки создавать внутри цикла и копировать строки. Нужно сделать два цикла в разных потоках. Используем схему производитель-потребитель. Один поток будет читать из файла в буфер. Другой – искать строку в буфере.
Взаимодействуют потоки через разделяемую переменную buffer.
Var buffer:string;
Const done:Boolean=false;
//процесс 1
var s1:string;
….
While true do
begin
//ожидать заполнения буфера или значения true
if done then break;
s1:=buffer
//сигнализировать, что буфер пуст
if search(p,s1) then Writeln(s1);
end;
//процесс 2
var s2:string;
….
While true do
Begin
Readln(f,s2);
If eof(f) then
Begin
Done:=true;
Break
End;
//ожидать опустошения буфера
buffer:=s2;
//сигнализировать о заполнении буфера
end;
Пример. Поиск максимального элемента в массиве.