Главная » Просмотр файлов » Краткий_Курс

Краткий_Курс (1184370), страница 6

Файл №1184370 Краткий_Курс (Краткий курс ПОД) 6 страницаКраткий_Курс (1184370) страница 62020-08-19СтудИзба
Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 6)

Функция MMAX(X,Y) выбирает ближайшее целое, большее или равное максимуму из чисел X и Y, а функция MMIN(X,Y) - ближайшее целое, меньшее или равное минимуму из X и Y.

Внутренний цикл по переменной T может выполняться параллельно для всех значений T. Границы изменения переменной цикла T меняются при переходе с одной прямой (гиперплоскости) на другую, поэтому их необходимо перевычислять во внешнем цикле. Число итераций внутреннего цикла, то есть потенциальная длина векторной операции, меняется с изменением

28. Ограничения на распараллеливание циклов.

Распараллеливание циклов возможно, если все итерации цикла независимы. Тело цикла не должны содержать:

  • операторов перехода

  • операторов ввода-вывода

Индексные выражения не должны иметь индекс в индексе А(В(С))

29. Алгоритмы преобразования программ методом координат

Метод координат:

- позволяет определить возможность выполнения цикла в синхронном режиме(для архитектуры 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)

  1. A(I,J) = B(I,J)+C(I)

23 B(I,J) = TEMP(I) ** 2

  1. C(I) = B(I-1,J)

24 CONTINUE

Примеры векторизации

Исходные тела циклов Преобразованные тела циклов

A(I) = B(I) C(I) = A(I+1)

C(I) = A(I+1) A(I) = B(I)

A(I) = B(I) D(I) = A(I)

C(I) = A(I) + A(I+1) A(I) = B(I)

C(I) = A(I) + D(I+1)

30. Синхронный и асинхронный способы передачи сообщений

В MPI имеется три режима коммуникаций - стандартный, режим готовности и синхронный.

В стандартном режиме последовательность выдачи операций send и receive произвольна, операция send завершается тогда, когда сообщение изъято из буфера и он уже может использоваться процессом.

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

Неблокирующие операции не приостанавливают процесс до своего завершения , а возвращают ссылку на коммуникационный объект, позволяющий опрашивать состояние операции или дожи­даться ее окончания. Имеются операции проверки поступающих процессу сообщений, без чтения их в буфер (например, для определения длины сообще­ния и запроса затем памяти под него).

31. Параллельное выполнение цикла вида

DO i=2,N A(I) =(B(i)+C(i))/A(i+const) ENDDO.

Если const = 0, то все итерации цикла независимы и токой цикл может быть выполнен на любой многопроцессорной ЭВМ, влючая Иллиак-4. (каждый виток цикла выполняется на отдельном процессоре)

Если const > 0 (пусть =1) то при параллельное выполнение цикла на ЭВМ класса МКМД без дополнительных мер по синхронизации работы процессоров невозможно. Например, пусть N=3 и два процессора вычисляют параллельно эти итерации, тогда, первый процессор вычисляет А2 по В2, С2, А3, а второй, А3 по В2, С2, А4 . При отсутствии синхронизации может случиться ситуация, при которой второй процессор завершит свою работу до начала работы первого. Тогда первый процессор для вычислений будет использовать А3, которое обновил второй процессор, что неверно, ибо здесь нужно “старое” значение А3. Однако, этот цикл выполняется параллельно на ЭВМ ОКМД (SIMD) так как там этот цикл может быть выполнен такими командами:

1. Считать Вi в сумматоры каждого из n АЛУ.

2. Сложить Сi со своим содержимом сумматора.

3. Разделить содержимое каждого i-сумматора на Аi+1.

4. Записать содержимое i- сумматоров в Аi.

Из за того, что выборка из памяти и запись в память производится синхронно (одновременно), то работа цикла – корректна.

Если const < 0 то параллельное выполнение цикла невозможно, ибо для выполнения очередной итерации цикла необходимы результаты работы предыдущей (рекурсия). Однако известны приемы преобразования такого рода циклов к виду, допускающие параллельное выполнение.

24. Статический и динамический способы образования параллельных процессов.

"Процесс - группа ячеек памяти, содержимое которых меняется по определенным правилам. Эти правила описываются программой, которую интерпретирует процессор” /Цикритзис Д./.

32. Распараллеливание алгоритмов сложения методом редукции.

Рекурсия - последовательность вычислений, при котором, значение самого последнего терма в последовательности зависит от одного или несколько ранее вычисленных термов. Пусть группа вычислений может производиться параллельно, использую результаты вычислений, выполненных на предыдущих этапах (полученных в виде начальных данных). Тогда, каж­дая группа вычислений называется "ярусом" параллельной формы, число групп - "высотой", максимальное число операций в группе "шириной" параллельной формы. Один и тот же алгоритм может иметь несколько представлений в виде параллельных форм, различающиеся как шириной, так и высотой. Редукционный алгоритм сдваивания для суммирования чисел с получением частных сумм может иметь вид:

Данные А1 А2 А3 А4 А5 А6 А7 А8

Ярус 1 А1+А2 А3+А4 А5+А6 А7+А8

Ярус 2 А12+А3 А12+А34 А56+А7 А56+А78

Ярус 3 А1234+А5 А1234+А56 А1234+А567 А1234+А5678

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

33. Метод распараллеливания алгоритма общей рекурсии 1-го порядка.

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

Общей линейной рекурсией первого порядка называется система уравнений вида:X1 = D1

X2 = X1 * A2 + D2

Xi = Xi-1 * Ai + Di

Xn = Xn-1 * An + Dn

в общем виде: Xi = Xi-1 * Ai + Di, i = 2,3,...n, X1 = D1

Последовательный алгоритм вычислений может быть записан так:

X(1) = A(1) + D(1)

DO i = 2,n

X(i) = X(i-1) * A(i) + D(i)

ENDDO

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

Xi-1 = Xi-2 * Ai-1 + Di-1

Xi = Xi-1 * Ai + Di

и подставив первое во второе, получаем:

Xi = (Xi-2 * Ai-1 + Di-1) * Ai + Di = Xi-2 * A1i + D1i , где

A1i = Ai * Ai-1 ,

D1i = Ai * Di-1 + Di

Тогда, проведя эту операцию для всей системы уравнений, получим систему уравнений порядка n/2. Если повторить процедуру l раз (если n = 2**l), то в результате получается значение: Xn = Dnl. Для получения полного вектора X необходимо модифицировать алгоритм, например, по аналогии с алгоритмами суммирования.

Очевидно, что вычисления Aji и Dji можно проводить параллельно методом каскадных сумм с сохранением частных сумм. Приведенные уравнения для уровня i имеют вид:

Xi = Ali * Xi-2**l + Dli , где l = 0,1,..,log2n , i = 1,2,..,n

Ali = Al-1i * Al-1(i-2**l-1)

Dli = Al-1i * Dl-1(i-2**l-1) + Dl-1i

Начальные данные: A0i = Ai, D0i = Di

Если индекс i у любого Ali, Dli и Xi попадает вне диапазона 1 <= i <= n , то он должен быть приравнен к нулю. Тогда , при l = log2n в уравнениях: Xi = Ali * Xi-2**l + Dli индекс Xi-2**l = Xi-n находится вне диапазона, и, следовательно, решением системы уравнений будет:

вектор: Xi = Dli, Векторная нотация Хокни для данного алгоритма: X = D

DO L = 1,LOG2(N)

X = A * SHIFTR(X,2**(L-1)) + X

A = A * SHIFTR(A,2**(L-1))

ENDDO

24. Системы счисления.

Подмножество вещественных чисел, которое может быть представлено в ЭВМ в форме чисел с плавающей запятой, принято обозначать буквой F и определять его элементы для конкретной архитектуры - "машинные числа", (по Форсайту и др.) четырмя целочисленными параметрами: базой b, точностью t и интервалом значений показателя [L,U]. Множество F содержит число нуль и все f числа вида: f = (+/-).d1d2...dt * b**e, где е назы­вается показателем, число .d1d2...dt = (d1/b+ ....+dt/(b**t)) - дроб­ной частью - мантиссой, причем: 0<=di<b, L<=e<=U. Каноническая или нормализованная форма F определяется дополнительным соотношением d1 =/= 0 ; это условие позволяет устранить неоднозначность представления одинаковых чисел, дает наивысшую возможную точность представления чисел. Особенности F:

- для каждого ненулевого f верно: m<=|f|<=M, где m = b**(L-1),

M = (b**U) * (1-b**(-t));

  • множество F конечно и содержит 2*(b-1)*(b**(t-1))*(U-L+1)+1 чисел, которые отстоят друг от друга на числовой оси на неравные проме­жутки.

35. Определить минимальное значение числа с плавающей запятой

- для каждого ненулевого f верно: m<=|f|<=M, где m = b**(L-1),

M = (b**U) * (1-b**(-t));

36. Определить количество элементов чисел с плавающей запятой.

  • множество F конечно и содержит 2*(b-1)*(b**(t-1))*(U-L+1)+1 чисел, которые отстоят друг от друга на числовой оси на неравные промежутки.

37. Машинный эпсилон, определение разрядной сетки ЭВМ.

Точность плавающей арифметики можно характеризовать посредством машинного эпсилона. Максимальное число Е такое, что 1.+ Е = 1. является мерой точности представления чисел на данной ЭВМ (машинное эпсилон). Грубая схема вычисления эпсилона:

EPS = 1.0

1 EPS = 0.5 * EPS

EPS1 = EPS + 1.0

IF (EPS1 .GT. 1.0) GO TO 1 >

Задача. Написать программу, определяющую количество разрядов, ис­пользуемых для представления мантиссы чисел с плавающей запятой. (Пусть на испытываемой ЭВМ мантисса числа хранится в нормализованном виде 1A2A3...An).

38. Источники погрешности при вычислениях на параллельных системах.

В общем случае, арифметические операции над элементами дискретного подмножества вещественных чисел F не корректны.

Результат арифметических операций чисел с плавающей запятой может:

- иметь абсолютное значение, больше M (максимального числа) - машинное переполнение;

- иметь ненулевое значение, меньшее m (минимального числа) по абсолютной величине - машинный нуль;

- иметь значение в диапазоне [m:M] и тем не не менее не принадлежать множеству F (произведение двух чисел из F, как правило, записывается посредством 2t либо 2t-1 значащих цифр);

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

А) Пусть x=9.900 y=1.000 z=-0.999 и тогда:

1 (x+y)+z = 9.910

2 x+(y+z) = 9.901

В) Пусть x=1100. y=-5.000 z=5.001 и тогда:

1 (x*y)+(x*z) = 1.000

2 x*(y+z) = 1.100

Здесь операции + и * - плавающие машинные операции. Такие 'чиcленные' процессы называют иногда 'неточными', здесь нарушаются ассоциативный и дистрибутивный законы арифметики..

39. Оценить полную ошибку для суммирования положительных чисел.

Пример расчета полной ошибки для суммирования положительных чисел

Формула полной ошибки для суммирования положительных чисел Ai(i=1,..,n) имеет вид: Ds = A1*da1 + A2*da2 +...+ An*dan + d1*(A1+A2) +..+ d(n-1)*(A1+..+An) + dn , где

dai - относительные ошибки представления чисел в ЭВМ, а di - относительные ошибки округления чисел при каждой следующей операции сложения. Пусть: все dai = da и di = d , a Ks = A1+A2+..+An, тогда: Ds = da*Ks + d*[(n-1)*A1+(n-1)*A2 +...+ 2*A(n-1) + An]

Очевидно, что наибольший "вклад" в сумму ошибок вносят числа, сум­мируемые вначале. Следовательно, если суммируемые положительные числа упорядочить по возрастанию, максимально возможная ошибка суммы будет минимальной. Изменяя порядок суммирования чисел можно получать различные результаты. Но если даже слагаемые отличаются друг от друга незначительно, на точность результата может оказать влияние способ суммирования. Пусть суммируются 15 положительных чисел, тогда ошибка результата: Ds = da*Ks + d*(14*A1+14*A2+13*A3+....+2*A14+A15).

Слагаемое da*Ks не зависит от способа суммирования, и далее не учитывается. Пусть слагаемые имеют вид: Ai = А0+ei, где i=1,...,15, тогда: Dss = 199*(A0+em)*d, где em = max(ei), d - ошибка округления при выполнении арифметической операции сложения.

Если провести суммирование этих чисел по группам (три группы по четыре числа и одна группа из трех чисел), то ошибки частных сумм имеют вид:

Ds1 = d*(3*A1+3*A2+2*A3+A4) <= 9*d*(A0+em)

Ds2 = d*(3*A5+3*A6+2*A7+A8) <= 9*d*(A0+em)

Характеристики

Тип файла
Документ
Размер
299 Kb
Тип материала
Высшее учебное заведение

Список файлов книги

Свежие статьи
Популярно сейчас
Как Вы думаете, сколько людей до Вас делали точно такое же задание? 99% студентов выполняют точно такие же задания, как и их предшественники год назад. Найдите нужный учебный материал на СтудИзбе!
Ответы на популярные вопросы
Да! Наши авторы собирают и выкладывают те работы, которые сдаются в Вашем учебном заведении ежегодно и уже проверены преподавателями.
Да! У нас любой человек может выложить любую учебную работу и зарабатывать на её продажах! Но каждый учебный материал публикуется только после тщательной проверки администрацией.
Вернём деньги! А если быть более точными, то автору даётся немного времени на исправление, а если не исправит или выйдет время, то вернём деньги в полном объёме!
Да! На равне с готовыми студенческими работами у нас продаются услуги. Цены на услуги видны сразу, то есть Вам нужно только указать параметры и сразу можно оплачивать.
Отзывы студентов
Ставлю 10/10
Все нравится, очень удобный сайт, помогает в учебе. Кроме этого, можно заработать самому, выставляя готовые учебные материалы на продажу здесь. Рейтинги и отзывы на преподавателей очень помогают сориентироваться в начале нового семестра. Спасибо за такую функцию. Ставлю максимальную оценку.
Лучшая платформа для успешной сдачи сессии
Познакомился со СтудИзбой благодаря своему другу, очень нравится интерфейс, количество доступных файлов, цена, в общем, все прекрасно. Даже сам продаю какие-то свои работы.
Студизба ван лав ❤
Очень офигенный сайт для студентов. Много полезных учебных материалов. Пользуюсь студизбой с октября 2021 года. Серьёзных нареканий нет. Хотелось бы, что бы ввели подписочную модель и сделали материалы дешевле 300 рублей в рамках подписки бесплатными.
Отличный сайт
Лично меня всё устраивает - и покупка, и продажа; и цены, и возможность предпросмотра куска файла, и обилие бесплатных файлов (в подборках по авторам, читай, ВУЗам и факультетам). Есть определённые баги, но всё решаемо, да и администраторы реагируют в течение суток.
Маленький отзыв о большом помощнике!
Студизба спасает в те моменты, когда сроки горят, а работ накопилось достаточно. Довольно удобный сайт с простой навигацией и огромным количеством материалов.
Студ. Изба как крупнейший сборник работ для студентов
Тут дофига бывает всего полезного. Печально, что бывают предметы по которым даже одного бесплатного решения нет, но это скорее вопрос к студентам. В остальном всё здорово.
Спасательный островок
Если уже не успеваешь разобраться или застрял на каком-то задание поможет тебе быстро и недорого решить твою проблему.
Всё и так отлично
Всё очень удобно. Особенно круто, что есть система бонусов и можно выводить остатки денег. Очень много качественных бесплатных файлов.
Отзыв о системе "Студизба"
Отличная платформа для распространения работ, востребованных студентами. Хорошо налаженная и качественная работа сайта, огромная база заданий и аудитория.
Отличный помощник
Отличный сайт с кучей полезных файлов, позволяющий найти много методичек / учебников / отзывов о вузах и преподователях.
Отлично помогает студентам в любой момент для решения трудных и незамедлительных задач
Хотелось бы больше конкретной информации о преподавателях. А так в принципе хороший сайт, всегда им пользуюсь и ни разу не было желания прекратить. Хороший сайт для помощи студентам, удобный и приятный интерфейс. Из недостатков можно выделить только отсутствия небольшого количества файлов.
Спасибо за шикарный сайт
Великолепный сайт на котором студент за не большие деньги может найти помощь с дз, проектами курсовыми, лабораторными, а также узнать отзывы на преподавателей и бесплатно скачать пособия.
Популярные преподаватели
Добавляйте материалы
и зарабатывайте!
Продажи идут автоматически
6418
Авторов
на СтудИзбе
307
Средний доход
с одного платного файла
Обучение Подробнее