ПОД (пособие) (1184372), страница 53
Текст из файла (страница 53)
Циклическая редукция - алгоритмы численного анализа дляраспараллеливания последовательных алгоритмов, основанный на последовательном,циклическом применении параллельных вычислений, число которых на каждом этапеуменьшается (делится пополам).Общей линейной рекурсией первого порядка называется система уравнений вида:X1 = D1X2 = X1 * A2 + D2Xi = Xi-1 * Ai + DiXn = Xn-1 * An + Dnв общем виде: Xi = Xi-1 * Ai + Di, i = 2,3,...n, X1 = D1Последовательный алгоритм вычислений может быть записан так:X(1) = A(1) + D(1)DO i = 2,nX(i) = X(i-1) * A(i) + D(i)ENDDOРекурсивная зависимость итераций цикла не позволяет ускорить вычисления за счетпараллельной работы оборудования.
Преобразуем данный алгоритм в параллельныйметодом циклической редукции. Рассмотрим два соседних уравнения:Xi-1 = Xi-2 * Ai-1 + Di-1Xi = 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 необходимо модифицироватьалгоритм, например, по аналогии с алгоритмами суммирования.176Очевидно, что вычисления Aji и Dji можно проводить параллельно методом каскадныхсумм с сохранением частных сумм.
Приведенные уравнения для уровня 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 * Xi-2**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))ENDDOПредставление машинных чисел.Для хранения и обработки данных в ЭВМ используется двоичная система, так как онатребует наименьшего количества аппаратуры по сравнению с другими системами. Всеостальные системы счисления применяются только для удобства пользователей.Перевод числа из одной системы в другую выполняется по универсальному алгоритму,заключающемуся в последовательном делении целой части числа и образующихся целыхчастных на основание новой системы счисления, записанное в исходной системе счисления,и в последующем умножении дробной части и дробных частей получающихсяпроизведений на то же основание, записанное в исходной системе счисления.Разряд двоичного числа представляется в ЭВМ некоторым техническим устройством,например, триггером, двум различным состояниям которого приписываются значения 0 и 1.Группа таких устройств, предназначенная для представления в машине многоразрядногочисла, называется регистром.Структура двоичного регистра, представляющего в машине n-разрядное слово:n-1n-2...10Отдельные запоминающие элементы пронумерованы от 0 до n-1.
Количество разрядоврегистра определяет точность представления чисел. Путем соответствующего увеличениячисла разрядов регистра может быть получена любая точность вычислений, однако этосопряжено с увеличением количества аппаратуры (в лучшем случае зависимость линейная,в худшем - квадратичная).В ЭВМ применяются две основные формы представления чисел: полулогарифмическая сплавающей запятой и естественная с фиксированным положением запятой.При представлении чисел с фиксированной запятой положение запятой закрепляется вопределенном месте относительно разрядов числа и сохраняется неизменным для всехчисел, изображаемых в данной разрядной сетке. Обычно запятая фиксируется передстаршим разрядом или после младшего.
В первом случае в разрядной сетке могут бытьпредставлены только числа, которые по модулю меньше 1, во втором - только целые числа.Для кодирования знака числа используется старший ("знаковый") разряд.177При выполнении арифметических действий над правильными дробями могут получатьсядвоичные числа, по абсолютной величине больше или равные единице, что называетсяпереполнением разрядной сетки.
Для исключения возможности переполнения приходитсямасштабировать величины, участвующие в вычислениях.Диапазон представления правильных двоичных дробей:2-(x-1) < A < 1 - 2-(x-1).Числа, которые по абсолютной величине меньше единицы младшего разряда разряднойсетки, называются машинным нулем.Диапазон представления целых двоичных чисел со знаком в n-разрядной сетке:0 < A < 2-(x-1)-1.Использование представления чисел с фиксированной запятой позволяет упростить схемымашины, повысить ее быстродействие, но представляет определенные трудности припрограммировании. В настоящее время представление чисел с фиксированной запятойиспользуется как основное только в микроконтроллерах.В универсальных ЭВМ основным является представление чисел с плавающей запятой.Представление числа с плавающей запятой в общем случае имеет вид:A = m * N p,где N - основание системы счисления,p - целое число, называемое порядком числа A,m - мантисса числа A (¦m¦<1).Так как в ЭВМ применяется двоичная система счисления, тоA = m * 2 p,причем порядок и мантисса представлены в двоичной форме.Двоичное число называется нормализованным, если его мантисса удовлетворяетнеравенству1/2< ¦ m ¦ < 1 .Неравенство показывает, что двоичное число является нормализованным, если в старшемразряде мантиссы стоит единица.
Например, число 0,110100*10100 - нормализованное, а0,001101*10110 - ненормализованное.Ситуация, когда в процессе вычислений получено число с ¦m¦>1 называется переполнениемразрядной сетки.Нормализованное представление чисел позволяет сохранить в разрядной сетке большееколичество значащих цифр и, следовательно, повышает точность вычислений. Однакосовременные ЭВМ позволяют, при необходимости, выполнять операции также и надненормализованными числами.Диапазон представления нормализованных двоичных чисел, взятых по абсолютномузначению, удовлетворяет неравенству:2-1*2-(2k-1) < A < (1 - 2-l)*22k-1,где l - число разрядов мантиссы;k - число разрядов порядка;2-1 - наименьшее значение нормализованной мантиссы;1 - 2-l - наибольшее значение нормализованной мантиссы.Широкий диапазон представления чисел с плавающей запятой удобен для научных иинженерных расчетов. Для повышения точности вычислений во многих ЭВМ178предусмотрена возможность использования формата двойной длины, однако при этомпроисходит увеличение затрат памяти на хранение данных и замедляются вычисления.Представление отрицательных чисел в ЭВМ.Для кодирования знака двоичного числа используется старший ("знаковый") разряд (нольсоответствует плюсу, единица - минусу).
Такая форма представления числа называетсяпрямым кодом. Формула для образования прямого кода правильной дроби имеет вид: A, A 0[ Anp ] 1 A, A 0Примеры:A = 0,110111 --> [A]пр = 0,110111A = -0,110111 --> [A]пр = 1 - (-0,110111) = 1,110111Прямой код целого числа получается по формуле:A, A 0[ Anp ] n110 A, A 0где 10 - число 2 в двоичной системе счисления,n - количество позиций в разрядной сетке.Например, при n=8A = 110111 --> [A]пр = 00110111A = -110111 --> [A]пр = 10000000 - (-110111) = 10110111В ЭВМ прямой код применяется только для представления положительных двоичныхчисел.
Для представления отрицательных чисел применяется либо дополнительный, либообратный код, так как над отрицательными числами в прямом коде неудобно выполнятьарифметические операции.Формула для образования дополнительного кода дроби:[A]доп = 10 + A.Формула для образования обратного кода дроби:[A]обр = 10 - 10-(n-1) + A.Например, при n = 8, для A = -0,1100001[A]доп = 10 + (-0,1100001) = 1,0011111[A]обр = 10-10-7+(-0,1100001) = 1,1111111-0,1100001 = 1,0011110.Формула для образования дополнительного кода целого числа:[A]доп = 10n + A.Формула для образования обратного кода целого числа:[A]обр = 10n - 1 + A.Например, при n = 8, для A = -1100001[A]доп = 100000000 + (-1100001) = 10011111[A]обр = 100000000-1+(-1100001) = 11111111-1100001 = 10011110.179Таким образом, правила для образования дополнительного и обратного кода состоят вследующем:- для образования дополнительного кода отрицательного числа необходимо в знаковомразряде поставить единицу, а все цифровые разряды инвертировать (заменить 1 на 0, а 0 - на1), после чего прибавить 1 к младшему разряду;- для образования обратного кода отрицательного числа необходимо в знаковом разрядепоставить единицу, а все цифровые разряды инвертировать.Примечание: при данных преобразованиях нужно учитывать размер разрядной сетки.Прямой код можно получить из дополнительного и обратного по тем же правилам, которыеслужат для нахождения дополнительного и обратного кодов.Замена вычитания двоичных чисел A1 - A2 сложением с дополнениями [A1]пр + [-A2]допили [A1]пр + [-A2]обр позволяет оперировать со знаковыми разрядами так же, как и сцифровыми.
При этом перенос из старшего знакового разряда, если он возникает,учитывается по разному для обратного и дополнительного кодов:- при использовании дополнительного кода единица переноса из знакового разрядаотбрасывается;- при использовании обратного кода единица переноса из знакового разряда прибавляетсяк младшему разряду суммы (осуществляется так называемый циклический перенос).Пример: складываем числа A1=0,10010001 и A2= -0,01100110При использовании обратного кода получим:[A1]пр = 0,10010001+[A2]обр = 1,10011001------------10,00101010|__________1------------Результат: 0,00101011При использовании дополнительного кода получим:[A1]пр = 0,10010001+[A2]доп = 1,10011010-------------Результат: 0,00101011Если знаковый разряд результата равен нулю, то в получено положительное число, котороепредставлено в прямом коде.
Если в знаковом разряде единица, то результат отрицательныйи представлен в обратном или дополнительном коде.Для того, чтобы избежать ошибок при выполнении бинарных операций, перед переводомчисел в обратные и дополнительные коды необходимо выравнивать количество разрядовпрямого кода операндов.При сложении чисел, меньших единицы, в машине быть получены числа, по абсолютнойвеличине большие единицы.
Для обнаружения переполнения разрядной сетки в ЭВМприменяются модифицированные прямой, обратный и дополнительный коды. В этих кодахзнак кодируется двумя разрядами, причем знаку "плюс" соответствует комбинация 00, азнаку "минус" - комбинация 11.180Правила сложения для модифицированных кодов те же, что и для обычных. Единицапереноса из старшего знакового разряда в модифицированном дополнительном кодеотбрасывается, а в модифицированном обратном коде передается в младший цифровойразряд.Признаком переполнения служит появление в знаковом разряде суммы комбинации 01 присложении положительных чисел (положительное переполнение) или 10 при сложенииотрицательных чисел (отрицательное переполнение).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
