автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.11, диссертация на тему:Параллельная реализация математических функций для архитектур с динамически изменяемой длиной операндов

- ] российская академия наук

Сибирское отделение Институт Систем Информатики

На правах рукописи

Вартазарян Ара Эдикович

ПАРАЛЛЕЛЬНАЯ РЕАЛИЗАЦИЯ МАТЕМАТИЧЕСКИХ ФУНКЦИИ ДЛЯ АРХИТЕКТУР С ДИНАМИЧЕСКИ ИЗМЕНЯЕМОЙ ДЛИНОЙ ОПЕРАНДОВ

Специальность 05.i3.ii - Математическое и программное обеспечение вычислительных машин, комплексов, систем и сетей

Автореферат

диссертации на соискание ученой степени кандидата технических наук

Новосибирск - 1993

Работа выполнена в Вычислительном центре Сибирского отделения Российской Академии Наук (ВЦ СО РАН).

Научный руководитель - доктор физико-математических наук, профессор H.H. Миренков

Официальные оппоненты - доктор технических наук

Б.М. Глинский

кандидат физико-математических наук В.И. Константинов

Ведущее предприятие - Новосибирский Государственный Технический

Университет '

Защита состоится марта 1993 гоОа в 14 часов На заседании специализированного совета К oo3.93.oi в Институте систем информатики Сибирского отделения РАН по адресу: бзооэо, г.Новосибирск-эо, пр. Академика Лаврентьева» 6.

С диссертацией можно ознакомиться в читальном зале ВЦ СО РАН (пр. ак. Лаврентьева, 6).

Автореферат разослан "_" _ хээзг.

Ученый секретарь Специализированного Совета к 003.93.01

к.ф.-м.н. S'''/*1/ М.А. Бульонков

- 3 -

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

Влияние погрешностей округления может, в принципе, быть сделано сколь угодно малым за счет увеличения количества разрядов в представлении чисел. Операции с плавапцей точкой выполняются в ЭВМ над словами с фиксированной (ограниченной) длиной. Ошибки округления быстро нарастают и являются предметом особого внимания. К тому же ЭВМ, как правило, ничего "не говорит" о реальной точности полученных результатов. Таким образом, если заранее не доказано слабое влияние ошибок округления (что является весьма распространенным явлением), то результат вычислений на современных машина« может быть воспринят только с большой долей сомнения.

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

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

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

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

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

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

Целью работы является создание параллельных алгоритмов и соответствующих программ вычисления элементарных функций с использованием возможности динамической изменяемости длины операндов и идеи вертикальной обработки данных.

Для достижения указанной цели ставится задача проектирования и микропрограммирования базовых операций векторной арифметики и линейной алгебры, а также задача использования этих операций при создании параллельных алгоритмов и программ для высокоточных

вычислений элементарных функций.

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

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

Выявлены дополнительные аспекты повышения эффективности вычислений за счет совмещения некоторых этапов вычислительного процесса для перечисленных выше функций.

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

Разработаны параллельные микропрограммы, которые могут быть использованы в проведении новых типов численных экспериментов.

Проведенные в работе исследования позволили разработать программы ускоренного вычисления некоторого набора элементарных функций для ассоциативного параллельного процессора ЕС 2720.

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

Реализованная библиотека включена в состав Системы Сверхточной Параллельной АРиФметики (системы СПАРФ-вычислений) и является составной частью системы моделирования архитектур высокопроизводительных вычислительных систем.

Результаты диссертационной работы отражены в публикациях [1-4], докладывались на заседаниях семинара "Математическое и архитектурное обеспечение параллельных вычислений" ВЦ СО РАН

(Новосибирск, 1991, 1992) и семинара кафедры "Вычислительные системы" Новосибирского Государственного университета (1991, 1992).

Структура и объем работы. Диссертация состоит из введения, трех глав, заключения и списка литературы {99 наименований). Работа содержит 114 страниц основного текста, 47 иллюстраций, 27 таблиц.

СОДЕРЖАНИЕ РАБОТЫ

Во введении обосновывается актуальность создания средств высокоточных вычислений математических функций на базе Систем Вертикальной Обработки (СВО), формулируются основные задачи диссертации, научная новизна и практическая значимость.

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

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

Другим условием получения требуемой точности вычислений является устранение (полностью или частично) влияния погрешностей

округления. Это может быть обеспечено путем использования арифметики многократной точности.

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

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

Введено понятие обобщенной структурной схемы, которая .отражает основные подсистемы и в некоторой общей форме - характер их взаимодействия. Как видно из рис. 1, в основу создания обобщенной структурной схемы положено разделение основных подсистем СВО по их функциональному назначению.

Хост

Контроллер

Процессорная матрица

Акселераторы ^

Память

Устройство преобразования структур данных

Система ввода-вывода

Рис. 1. Обобщенная структурная схема СВО

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

Название СВО ::= [ Кластеры / Модули ] 1-й уровень

[ Способ управления ][ Процессорная матрица ] [ Соединительная сеть ][ Контроллер ] (1)

[ Память ][ Устройство преобразования структур данных ] [ Акселераторы ] [ Система ввода-вывода ]

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

Приведены примеры описания известных СВО (dap, staran).

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

Выполнен анализ основных особенностей системы программирования сверхточных параллельных арифметических вычислений

(СПАРФ-вычислений), разработанной на базе Ассоциативного Параллельного Процессора (АПП) ЕС-2720, с архитектурой, совместимой с системой staran.

С точки зрения пользователя данная система рассматривается как векторный процессор (СПАРФ-процессор) с динамически изменяемой разрядностью векторных операндов, архитектура которого реализована программным путем в рамках архитектуры АПП.

Вычисления в СПАРФ-процессоре могут выполняться в двух режимах: с фиксированной или динамической точностью. Первый режим характеризуется постоянством разрядности операндов в процессе вычислений. В режиме с динамической точностью в процессе вычислений разрядность операндов может изменяться в интервале, определяемом пользователем.

Важным свойством СПАРФ-процессора является возможность сохранения точного результата после любой арифметической операции. Программная реализация команд СПАРФ-процессора позволяет относительно легко адаптировать его к решению различного типа задач, в том числе и для вычисления элементарных функций.

Вторая глава посвящена вопросам анализа и . разработки параллельных базовых операций СПАРФ-арифметики и особенностям их реализации на АПП ЕС-2720. Эти операции являются частью системы команд СПАРФ-процессора и определяют операционный базис для вычисления элементарных функций. К ним относятся: процедуры умножения вектора на скаляр, параллельного деления, вычисления сумм

и произведений, преобразования- структур данных, вычисления полиномов. Описание алгоритмов осуществляется с помощью языка vepran. Для анализа времени выполнения используются асимптотические оценки временной сложности oA(f(N)), как арифметической функции от порядка • обрабатываемых данных, битовой временной . сложности Og(f(n)), как функции от разрядности данных, а также совмещенная оценка вида Og(f(n,N)), учитывающая поразрядно - последовательную обработку в каждом канале СВО и. параллельно - пословную обработку всей системы в. целом. Кроме.этого, для получения уточненных оценок используется методика,, основанная на представлении, времени выполнения алгоритма в виде полинома.

Для ' операции ■ "умножение вектора на скаляр" разработан ускоренный параллельный алгоритм, основанный на методе Лемана, с анализом двух смежных разрядов множителя - скаляра, и пропуском тактов .суммирования в подходящих случаях. Алгоритм строится таким образом, чтобы число суммирований - вычитаний было минимальным.

Для сравнения ускоренного и обычного • поразрядного алгоритмов, получены оценки ускорения для' метода Лемана. Поскольку . результат сравнения зависит от того, какие данные участвуют в операций, рассмотрены различные варианты- для обоих алгоритмов. Выбраны относительно малые .по абсолютной величине множимое и множитель.-Путем использования ' знакопеременных чисел были получены . оценки ускорения метода Лемана' в сравнении с поразрядным алгоритмом. Результаты сведены в табл. 1. В этой таблице-: В - положительный целочисленный вектор, с - целочисленный скаляр, lc - количество команд,' затраченное на •обыкновенное умножение, lh -количество команд для метода Лемана. .В'табл. 1 включен также наихудший, случай для метода Лемана - число с чередованием о и 1.(для с*).

Таблица 1

РазРядность Ускорение s = lc / lm

в*с . -в*с в*(-с) (-в)*(-с) в*с*

32 0,947 0,966 3,971 3,474 0, 938

64 0,950 0,960 7,544 6,477 0,965

128 0,947 0,961 14,737 12,530 0,981

256 0,946 0,962 29,150 24,663 0,990

512 0,946 0,962 58,078 48,995 0,995

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

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

Разработаны параллельные алгоритмы ускоренного вычисления сумм и произведений (префиксные операции). Выполнение этих операций основывается на промежуточном использовании операций сложения и умножения векторов. Идея быстрого выполнения этой операции заключается в использовании "метода сдваивания". Показано, что вычисление префиксной суммы на АПП, содержащем n ПЭ, может быть выполнено за время oA(iog2N) и оБ(п iog2N). Операция префиксной суммы вычисляет сумму всех предшествующих чисел для любого элемента массива (или вектора). Алгоритм префиксного умножения в целом выполняется аналогично префиксной сумме. Разница между ними заключается в том, что в промежуточных операциях формируются не частичные суммы элементов вектора, а частичные произведения, что позволяет вычислить префиксное произведение за время oA(iog2N) и

Og(nZ log2N).

Разработаны специальные алгоритмы параллельного преобразования структур данных растяжения и сжатия векторов, используемые для согласования структуры данных с архитектурой системы. Необходимость этого согласования связана с тем, что обмен между ПЭ в АПП осуществляется с помощью сети Flip, в которой перестановки осуществляются в группах ПЭ, размер которых кратен степени двойки, а в структурах данных это не всегда имеет место.

ОПРЕДЕЛЕНИЕ. Растяжением называется операция дополнения векторов размера N * 2* некоторыми элементами, допустим нулями, до

llo3 hjh

размера Nt= 2=2

Процедура "растяжения" к векторов размером N * 2* до размера

l1 " Я ♦ 1

n( = 2 на np = к n, ПЭ на СПАРФ-процессоре, имешем т г к

каналов обработки и разрядность п бит, может быть выполнена за o^(iog2Np) и оБ(п iog2Np) операций.

Операция сжатия векторов выполняет обратное к операции растяжения преобразование структур данных.

Рассматривается также задача вычисления степенных полиномов, являщаяся базовой при вычислении элементарных функций. При этом полином представляется как "скалярное произведение" двух векторов:

вектора коэффициентов а = {а0,а).....а } и, так называемого,

"вектора степеней" х = (1,х,х2,х3,.... Вычисление степенного полинома распадается на три этапа: подготовка вектора переменных типа х' = (1,х,х,...,х), получения вектора х путем применения к вектору х' операции префиксного произведения и скалярного произведения вектора а и х. Показано (Утверждение 2.5), что вычисление n полиномов степени р с n-разрядными элементами на СПАРФ-процессоре, содержащем m = рлг каналов параллельной обработки и имешем разрядность операндов п бит может быть выполнено за время оА(log р) и ob(n2iog р + п + n log р), что дает относительное

р

ускорение о

Liog2pJ+i

(Утверждение 2.6).

Рассмотрена возможность параллельного вычисления нескольких полиномов и сохранения тем самым максимальной производительности системы. Число одновременно вычисляемых значений полиномов при этом равно:

N =

5, для р кратных степени 2, ■"j———-г—г-, в остальных случаях.

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

Таблица 2

р Параметр Начальная разрядность

32 64 128 256

6 Время, с 0.004 0.015 0.06 0.24

Ускорение 3.15 3.0 2.7 2.5

8 Время, с 0.003 0.014 0.05 0.23

Ускорение 3.19 3.1 2.9 2.7

13 Время, с 0.006 0.006 0.021 •0.08

Ускорение 5.18 4.8 4.3 3.9

16 Время, с 0.005 0.019 0.07 0.31

Ускорение 5.97 5.54 4.6 4.1

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

В третьей главе рассматриваются вопросы практической разработки параллельных процедур для вычисления ряда элементарных функций с помощью разложения их в степенной ряд Тейлора-Маклорена и . программирования СПАРФ-процессора для указанных задач (основные и обратные тригонометрические, показательная и логарифмическая функции и квадратный корень).

Исходные аргументы, а для некоторых функций (у = tg х, у = ctg х) также и часть коэффициентов должны быть размещены в соответствующих векторных регистрах СПАРФ-процессора. Если они находятся в памяти управления, то выполняется загрузка в векторный регистр СПАРФ-процессора за оА(к) и оБ(пк).операций, где к - число входных данных. Выполняется размножение данных в группе размером n так, чтобы сформировать вектор переменных типа х=(х,х,...,х). Размножение осуществляется за oA(iog2N) и оБ(п iog2N) операций. Размер группы, необходимый для вычисления функции от одного аргумента, определяется, исходя из требуемой точности вычислений (число требуемых для этого членов ряда). Для определения необходимого числа членов ряда проведен анализ зависимости точности

вычислений от абсолютной величины аргумента и величины отбрасываемого члена ряда. Основной интервал изменения аргумента (интервал приведения) разбивается на подинтервалы с величиной б (чем меньше б, тем точнее вычисляется функция) и оценивается величина отбрасываемого члена. Результаты подобной оценки для рассматриваемых элементарных функций запоминаются в специальных таблицах. По данным таблицам определяется количество N членов ряда, необходимых для обеспечения требуемой точности вычислений. Это значит, что в вычислении функции от одного аргумента участвуют N ПЭ. Если N = 21, то допустимое число одновременно обрабатываемых данных определяется формулой к = m/N, где ш - общее число ПЭ. Если n i- 21, то к = ш/2l'°92m-1 . В случае n + 2' с помощью процедуры растяжения исходный вектор переменных преобразуется в вектор размера м,= 2l1o92hJ

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

В зависимости от типа функции ряд может иметь четные, нечетные или все степени переменных, а также факториалы четных и нечетных чисел, коэффициенты другого типа, которые были упомянуты выше. Поэтому для получения вектора х*'= (х х3х5х?.,х2п*1) в начале формируется вектор х2= (х х2х2х2..х2) путем возведения в квадрат вектора х = (хххх...х) (при этом маскируется первый элемент), после чего к вектору х2 применяется процедура префиксного произведения. Вектор х*2= (x2x',xex?. .х2") получается путем предварительного формирования вектора x2= (х2х2х2х?..х2) с последующим применением ' процедуры префиксного произведения.

Вектор факториалов для чисел от i до N получается из вектора, содержащего N единиц последовательным применением к нему префиксных процедур сумм и произведений. Разделение факториалов четных и нечетных чисел осуществляется процедурой сортировки, требующей oA(iog2N) и оБ(п iogzN) операций.

Показано, что вычисление функций у = sin х, у = cos х,

у = aresin х, у = arceos х, у = arctg х, у = arcctg х, у = е" И

у = in х в группе из N * г' ПЭ на СПАРФ-процессоре, имеющем ш г n каналов обработки и разрядность операндов п бит, может быть выполнено за 0A(Llog2Nj+ l) И Og(n Llog2Nj + n + n l1o82Nj + П) операций, а функций y = tg x, у = ctg x и квадратного корня - за

Oa(N + i_log2Nj + 1) И Og(n2Llog2Nj + n2 + n N + n Llog.,Nj + n) операций.

Проведено измерение времени вычисления рассмотренных выше функций в зависимости от степени ряда р и разрядности операндов п. Получены оценки производительности СПАРФ-процессора при вычислении этих функций от одного аргумента р = NA/tC4, где n¿ - число арифметических операций, затрачиваемых на вычисление, a t -измеренное время, максимальной производительности и относителного ускорения. Для всех рассматриваемых функций оценки времени вычислений, производительности и относительного ускорения, в целом, повторяют поведение, этих оценок, полученных для общего случая при вычислении степенных полиномов.

Разработаны параллельные алгоритмы совмещенного вычисления для ФУНКЦИЙ С бЛИЗКИМИ СВОЙСТВаМИ, Например, у = sin х И у = cos х, у = tg х и у = ctg х, и т.д. Показано, что имеются богатые возможности совмещения различных этапов вычислений разных функций, например, совмещение формирования векторов переменных, коэффициентов и т.д.

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

у = aresin х.

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

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

Таблица з

p=2n-1 Параметр Начальная разрядность

32 64 128 256

3 Ускорение 3.676 3.514 3. 356 3.214

5 Ускорение 3.924 3.806 23.64 Невоз.выч.

7 Ускорение 3.982 3.828 3.712 Невоз.выч.

11 Ускорение 4.286 3.824 Невоз.выч. Невоз.выч.

15 Ускорение 4.32 3.98 Невоз.выч. Невоз.выч.

25 Ускорение 4.511 Невоз.выч. Невоз.выч. Невоз.выч.

31 Ускорение 4,67 Невоз.выч. Невоз.выч. Невоз.выч.

ТЕОРЕМА I. Пусть вычисления элементарных функций выполняются на СПАРФ-процессоре в формате real, с фиксированной разрядностью п.

Тогда ошибка вычисления значения хк составляет величину

п п

к_1 —1

ûk* Va"~ *(а*Ео*С) 1-а ' Где 'xlSa> £=2 2 И ео= 2 2 •

ТЕОРЕМА 2. Пусть вычисления элементарных функций выполняются на СПАРФ-процессоре в формате real, с фиксированной разрядностью п.

Тогда погрешность вычисления функции не превышает величины

Д s 2 2 , при условии |х| S а * 0,5.

Заключение

В рамках исследований, проведенных в диссертационной работе, получены следующие основные научные и практические результаты:

1. Предложено использовать СВО в качестве базы для создания программных средств параллельного вычисления математических функций с повышенной точностью путем использования операндов с динамически изменяемой длиной.

Разработана двухуровневая схема морфологического описания

архитектуры CBQ.

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

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

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

4. Создана Сиблиотока программ вычисления элементарных функций на базе АПП к*: 2720, н которых осуществляется параметрическое управление точностмо исчислений.

Основные penyjii.Tivrw диссертации опубликованы в следующих работах:

1. Важенин А.П., Нартааарян к Ли Трудоемкие арифметические операции, для ассоциатинпого параллельного процессора // Параллельные алгоритмы и структуры.- Новосибирск: 1991.-с. 51-66.

2. Важенин А.П., Вартазаряи А.Э., Непомнящая А.Ш. Базовые процедуры для ассоциативных параллелных процессоров с вертикальной обработкой // Методы теоретического и системного программирования.- Новосибирск: 1991.- С. 114-124.

3. Важенин А.П., Вартазарян А.Э., Фет Я.И. .Морфологический подход к анализу систем вертикальной обработки информации.-Новосибирск, 1992.- 32 С. (Препринт / СО РАН. ВЦ; 982).

4. Важенин А.П., Вартазарян А.Э. Параллельные алгоритмы умножения матриц с многоразрядными элементами.- Новосибирск, 1992.32 С. (Препринт / СО РАН. ВЦ; 973).