Краткий_Курс (1184371), страница 8
Текст из файла (страница 8)
Приведенные уравнения для уровняi имеют вид:Xi = Ali * Xi-2**l + Dli , где l = 0,1,..,log2n , i = 1,2,..,nAli = 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 * Xi2**l + Dli индекс Xi-2**l = Xi-n находится вне диапазона, и, следовательно,решением системы уравнений будет:вектор: Xi = Dli, Векторная нотация Хокни для данного алгоритма: X = DDO L = 1,LOG2(N)X = A * SHIFTR(X,2**(L-1)) + XA = A * SHIFTR(A,2**(L-1))ENDDO24. Системы счисления.Подмножество вещественных чисел, которое может быть представлено вЭВМ в форме чисел с плавающей запятой, принято обозначать буквой 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.32Каноническая или нормализованная форма 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.01 EPS = 0.5 * EPSEPS1 = EPS + 1.0IF (EPS1 .GT. 1.0) GO TO 1 >Задача. Написать программу, определяющую количество разрядов, используемыхдля представления мантиссы чисел с плавающей запятой. (Пусть наиспытываемой ЭВМ мантисса числа хранится в нормализованном виде 1A2A3...An).38.
Источники погрешности при вычислениях на параллельных системах.В общем случае, арифметические операции над элементами дискретногоподмножества вещественных чисел F не корректны.Результат арифметических операций чисел с плавающей запятой может:- иметь абсолютное значение, больше M (максимального числа) - машинноепереполнение;- иметь ненулевое значение, меньшее m (минимального числа) по абсолютнойвеличине - машинный нуль;- иметь значение в диапазоне [m:M] и тем не не менее не принадлежатьмножеству F (произведение двух чисел из F, как правило, записываетсяпосредством 2t либо 2t-1 значащих цифр);33Поэтому, на множестве чисел с плавающей запятой определяются и"плавающие" арифметические операции, за результаты которых, если они невыходит за границы множества F, принимается ближайшие по значениюэлементы F.
Примеры из четырехразрядной десятичной арифметики по Н. Вирту.А) Пусть x=9.900 y=1.000 z=-0.999 и тогда:1 (x+y)+z = 9.9102 x+(y+z) = 9.901В) Пусть x=1100. y=-5.000 z=5.001 и тогда:1 (x*y)+(x*z) = 1.0002 x*(y+z)= 1.100Здесь операции + и * - плавающие машинные операции. Такие 'чиcленные'процессы называют иногда 'неточными', здесь нарушаются ассоциативный идистрибутивный законы арифметики..39.
Оценить полную ошибку для суммирования положительных чисел.Пример расчета полной ошибки для суммирования положительных чиселФормула полной ошибки для суммирования положительных чиселAi(i=1,..,n) имеет вид: Ds = A1*da1 + A2*da2 +...+ An*dan + d1*(A1+A2) +..+ d(n1)*(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)Ds3 = d*(3*A9+3*A10+2*A11+A12) <= 9*d*(A0+em)Ds4 = d*(3*A13+2*A14+A15) <= 5*d*(A0+em)а полная оценка ошибок округления будет Ds <= 32*d*(A0+em), что меньшеDss.
Итак суммирование по группам дает меньшую ошибку результата.34Например, разделив процесс суммирования массива положительных чисел напараллельные процессы, и затем получив сумму частных сумм, можно получитьрезультат, отличный от последовательного суммирования в одном процесс.40. Определить .....Эффект от буферизации можно определить среднему времени выборки: t =t2*p+ t1*(1-p), где t1 - среднее время доступа к данным основной памяти, t2 среднее время доступа к данным из буфера (t2<t1), p - вероятность наличияданного в буфере.41.
Привести пример программы, вызывающей перезагрузку кэша с прямымраспределением.В кэше с прямым отображением адреса кэша для передаваемых объектовданных являются функцией полного виртуального адреса объектов. Для кэшаобъемом в 1 Мбайт адреса процессорного кэша вычисляются в процессе работы поформуле: cache_address=MOD(virtual_address,2**20) MOD - функция, возвращающаяостаток от деления virtual_address на 2**20 (2**20=1048576=1 Мбайт). Такимобразом, адрес кэша объекта данных - это младшие 20 бит его виртуального адреса.Старшие разряды адреса – теги храняться в специальной памяти – памяти тэгов. Такая схема адресации может стать причиной перезагрузки кэша (кэш трэшинг), еслипоследовательно используемые процессором данные расположены в оперативнойпамяти по адресам, кратным размеру памяти кэша.
Пусть 1- М-байтный кэшпроцессора прямо отображается на виртуальную память. Это означает, чтообращение к памяти с шагом в 1 - М-байт "гарантирует" перезапись строк кэша[строка кэша - блок данных, читаемые из или записываемые в (или из) память за однообращение; 32 байта для кэша процессора]. Пусть имеется программа:REAL *8 A(65536),B(65536),C(65536)DO I = 1,NA(I) = B(I) + C(I)ENDDOКаждый массив имеет размер - точно 1/2 М-байта. Предположим, что онизагружены в память без разрывов.
Тогда, все строки кэша для С в точностинакладываются на строки кэша для массива А. Так что, процессор,выполняющий 1 итерацию цикла, будет загружать строку кэша массива В,строку кэша массива С, вычислит B(I) + C(I) , а затем загрузит строку кэша А(которая приведет к перезаписи строки кэша С). На следующей итерации строкикэша для С и А должны быть выбраны снова, так что не будет повторногоиспользования данных из кэша без перезаписи. Добавка некоторого смещения кразмерности массива исключает эту проблему.
Таким образом, следующий кодбудет выполняться значительно быстрее:REAL *8 A(65536+8),B(65536+8),C(65536+8)DO I = 1,N35A(I) = B(I) + C(I)ENDDOТакое изменение размерности гарантирует, что строки кэша, которыетребуются в одной итерации, не будут записываться друг на друга.Приложение: Стандартные префиксы Международной системы измерений СИпрефиксдвоичная системадесятичная системакило-Кмега-Мгига-Гтера-Тпета-Пекзазеттайотта-1024**1 = 2**101024**2 = 2**201024**3 = 2**301024**4 = 2**401024**5 = 2**501024**6 = 2**601024**7 = 2**701024**8 = 2**80======10241 048 5761 073 741 8241 099 551 627 7761 125 899 906 842 624...................1000**11000**21000**31000**41000**51000**61000**71000**8========10**310**610**910**1210**1510**1810**2110**24тысячамиллионмиллиард, биллионтриллионквадриллионквинтиллионсексиллионсептииллионПрефиксы, используемые при умножении на отрицательную степень 1000милли- 1000** -1 = 10** -3 = 0.001микро- 1000** -2 = 10** -6 = 0.000001нано1000** -3 = 10** -9 = 0.000000001пико1000** -4 = 10** -12 = ..........фемто- 1000** -5 = 10** -15атто1000** -6 = ........зенто- 1000** -7йокто- 1000** -8В АНГЛИИ:Биллион = миллиону миллионов = 1 с 12 нулямиТриллион = миллиону биллионов = 1 с 18 нулямиКвадриллион = миллиону триллионов = 1 с 24 нулямиКвинтиллион = миллиону квадриллионов = 1 с 30 нулямиСекстиллион = миллиону квинтиллионов = 1 с 36 нулямитактовая частота в МГцпродолжительность циклав нс6015100101337.5166636Особенности вычисления выражений в Фортране 90 ( пункты стандарта).7.1.7.
Выполнение операций"При вычислении выражения А+В, где А,В - массивы, процессор может выполнятьпо-элементные операции сложения в любом порядке"7.1.7.1. Вычисление операндов"Процессор не обязательно вычисляет все операнды выражения или полностьюкаждый операнд, если значения можно определить без этого. Так в выражении: X.GT.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
