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

РОССИЙСКАЯ АКАДЕМИЯ НАУК Сибирское отделение Институт Систем Информатики

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

Важенин Александр Павлович

МЕТОДЫ И СРЕДСТВА ПАРАЛЛЕЛЬНОЙ ВЫСОКОТОЧНОЙ АРИФМЕТИКИ НА БАЗЕ СИСТЕМ ВЕРТИКАЛЬНОЙ ОБРАБОТКИ

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

Автореферат

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

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

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

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

Официальные оппоненты - доктор технических наук, профессор А.Д. Рычков

кандидат технических наук Ю.Л. Вишневский

Ведущее предприятие - Институт Вычислительных Технологий СО РАН (г. Новосибирск)

Защита состоится " 15" января 1993 года в 1430 часов на заседании специализированного совета К 003.93.01 в Институте систем информатики Сибирского отделения РАН по адресу: 630090, г.Новосибирск-90, пр. Академика Лаврентьева, 6.

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

Автореферат разослан "Н" 12- 1992г.

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

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

(У

* г <;• С К Л г,

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

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

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

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

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

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

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

- разработка и анализ параллельных алгоритмов СПАРФ-арифметики для систем вертикальной обработки;

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

- разработка системы программирования СПАРФ-вычислений на базе АПП ЕС-2720 с архитектурой, совместимой с системой ЗТАЯАЫ.

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

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

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

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

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

Практическая ценность:

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

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

Апробация работы. Результаты работы докладывались на Всесоюзном научно-техническом семинаре "Программное обеспечение многопроцессорных систем" (Калинин, 1988 г.), VIII Всесоюзном семинаре "Параллельное программирование и высокопроизводительные структуры" (Алушта, 1988 г.), VII Всесоюзной школе-семинаре "Распараллеливание обработки информации" (Львов, 1989 г.). Всесоюзной конференции "Высокопроизводительные вычислительные системы для комплексных центров математического моделирования" (Новосибирск, 1989 г.), Межотраслевом научно-техническом семинаре "Системы, средства и алгоритмы первичной обработки информации" (Ленинград, 1989 г.), Международной конференции CONPAR 90-VAPP IV (Швейцария, Цюрих, 1990 г.), Всесоюзной школе-семинаре "Многоуровневое структурное проектирование программных систем" (Планерское, 1991 г.), Международной конференции "Parallel Computing Technologies" (Новосибирск, 1991 г.), а также на заседаниях семинара "Математическое и архитектурное обеспечение параллельных вычислений" в ВЦ СО РАН (Новосибирск, 1987-1992 г.).

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

Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения, списка литературы (95 наименований) и приложения. Работа содержит 149 страниц основного текста, 50 иллюстраций, 20 таблиц.

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

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

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

Предложено использовать СВО, в качестве базы для создания средств программирования и выполнения СПАРФ-вычислений. На основе предложенной обобщенной структурной схемы СВО выполнен аналитический обзор зарубежных (STARAN, МРР, LUCAS, CM, DAP и т.д.) и отечественных (ЕС-2720, ППО-1, ПАРС) систем данного типа. Высокая производительность СВО достигается с помощью одновременной работы большого количества простейших одноразрядных процессорных элементов (ПЭ), каждый из которых имеет локальную память и связан с остальными с помощью соединительной сети. Показано, что отличительные особенности СВО удовлетворяют перечисленным требованиям.

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

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

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

одноразрядных ПЭ, каждый из которых имеет локальную память и связан с

остальными с помощью соединительной сети. Общая память СВО рассматривается

как битовая матрица В s [й. ] порядка т х п, где m - число однобитовых

каналов обработки (число ПЭ), an- емкость локальной памяти. Обработка

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

сформированных двоичных битовых векторов, называемых битовыми срезами.

С учетом способа формирования определены типы битовых срезов:

вертикальный срез или просто срез S^ = [6.J, где i = 0,m-l, занимающий к-ый

столбец матрицы в; словный срез или слово W' з [Ъ.], где j = к,к+т-1,

к и *

расположенный в /-ой строке матрицы в и сложный срез S^, формируемый

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

матрицы в, образованная соседними вертикальными срезами и определяемая

номером начального среза к и количеством этих срезов /, называемое

разрядностью поля f' = [S ], где i = k,k+l-1, 0 s t s я-1 и 1 s / S п-к.

Элементом F поля F называется битовый срез такой, что F т \Ь ], где ik i ij

j = k,k+l-1. С учетом типа обрабатываемых данных в поле могут размещаться

массивы (векторы) чисел или же строки реляционной таблицы при нечисловой

обработке. В первом случае каждый элемент вектора располагается в

соответствующем элементе поля. В зависимости от входных и результирующих

данных определен набор типовых процедур обработки на СВО: <S,S>—> <S>,

<F,F>—> <F>, <S,F>—> <W,F>—> <F>, <W,F><S>, <F,F> —» <S>,

<F> —> <S>, <F> —» <W>, <W>-^ <F>.

При анализе алгоритмов для СВО используются традиционные

/

асимптотические оценки: 1) арифметической временной сложности как функции от

N - числа обрабатываемых данных ОJf(N,m)), позволяющей учесть уменьшение

числа арифметических операций за счет их параллельного выполнения; 2)

битовой временной сложности как функции от п - разрядности данных Og(/(n)),

отражающей поразрядно-последовательный характер обработки в СВО, - а также

предложенная с овмещенна я оценка вида Og (f(N, n(t),m)), отражающая

параллелизм операций и динамику изменения п в процессе вычислений.

Для того, чтобы различать алгоритмы с одинаковыми асимптотическими

оценками, но имеющими разную практическую эффективность разработана

методика, дополняющая асимптотическое оценивание временной сложности в

случаях, когда важны конкретные значения параметров размера задачи и

/

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

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

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

Разработаны параллельные алгоритмы высокоточной арифметики для АПП с архитектурой, совместимой с системой STARAN, в которых обеспечены параметрическое управление разрядностью операндов и получение точного результата (без округления). Показано,что при m ^ N параллельные алгоритмы пересылки данных и поиска, сложения-вычитания могут быть выполнены за время 1) и Og(rc)

(утверждения 2.1 и 2.2), а алгоритмы умножения и деления - за время О (1) и

2 А Og(ii ) (утверждения 2.5, 2.7 и 2.11). Процедура вычисления суммы элементов

вектора выполняется методом сдваивания с использованием возможностей соединительной сети АПП FLIP за время 0A(\og2N) и Og(/!log2AO (Утверждение 2.3). Точное скалярное произведение векторов рассматривается как результат выполнения процедур "умножение полей" и "сумма элементов вектора", что составляет Од(log^yV) и 0^(n2+n\og2N) операций (утверждение 2.9).

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

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

С точки зрения программиста подключение КВС может быть выполнено путем расширения числа операционных регистров АПП, что обеспечивает сохранение принципа вертикальной обработки и не нарушает функционирования других подсистем АПП (маскируемость, операции соединительной сети, многомерный доступ). Показано (утверждение 2.4), что процедура вычисления суммы N элементов вектора при реализации ее на АПП с КВС может быть выполнена за время Оа( 1) и ОБ(/г+^Л0.

Конвейерное умножающее устройство (КУУ) представляет собой двумерную однородную структуру размером Nxn ячеек, где N - количество каналов умножения (число перемножаемых компонент), а п - разрядность чисел. Получение точного произведения осуществляется в три этапа. На первом этапе выполняется загрузка множимых в КУУ, начиная со старших разрядов. На втором - производится формирование младшей части произведения путем подачи в КУУ разрядных срезов множителей, начиная с младших разрядов, и извлечения из него срезов произведения. Выгрузка старшей части произведения осуществляется на третьем этапе. Показано (утверждение 2.8), что при данном способе подключения параллельное умножение можно выполнить за время 1) и О^(п).

Формирование точного скалярного произведения на АПП с данными сопроцессорами можно организовать путем программного "зацепления" КУУ и КВС, осуществляя подачу срезов частичных произведений на вход сумматора. Показано (утверждение 2.10), что при этом данная процедура может быть выполнена за время О (1) и

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

Реализация ускоренного умножения вектора на скаляр выполнена путем распараллеливания алгоритма Лемана с анализом двух смежных разрядов множителя и пропуском циклов частичных сложений при нулевом или единичном значении этих разрядов. Показано, что для множителей, содержащих большое число смежных единичных разрядов, это обеспечивает значительное ускорение (приблизительно в 30 раз для п = 256 бит и в 50 раз для п = 512 бит). В остальных случаях время умножения равно времени выполнения обычного поразрядного алгоритма.

Для ускорения процедуры "умножение векторов" разработан параллельный рекурсивный алгоритм умножения, выполняющий в каждом канале обработки АПП умножение двух ¿-разрядных чисел и = н +2"-и и V = у(+2"-у1 следующим образом

Р = и-У = 2 2"а + 2"(с-а-Ь) + Ъ, (2.7)

где к = 2п, а = и 'V . Ь = ид-уд, с = ("0+«;)При этом алгоритм (2.7) используется рекурсивно для вычисления произведений а,Ь и с.

С помощью предложенной методики выполнен сравнительный анализ рекурсивного и поразрядного алгоритмов, показывающий рост ускорения в зависимости от разрядности перемножаемых операндов (рис. 1а) на базовой архитектуре АПП и на АПП с КУУ относительно умеренной разрядности р = 4,8,16,32 бит (рис. 16).

40

30-

%го\

о «

а

10

12

4 6 8 10 12 14 16 Разрядность

б)

2 4 в 8 10 Число рекурсий

а)

Рис. 1

Получены оценки ускорения для основных СПАРФ-операций при их реализации на СВО в сравнении с универсальными ЭВМ. Сформулирован и доказан ряд теорем, показывающих, что ускорение для базовой архитектуры АПП при выполнении основных арифметических операций над длинными п-разрядными данными определяется соотношением объема параллельно обрабатываемых данных N и длиной разрядной сетки универсальной ЭВМ /. При условии, что п » /, величина ускорения для арифметических операций сложения-вычитания, умножения, деления и скалярного произведения векторов составляет (теоремы 2.1, 2.4 и 2.6) и О^ N ) ПРИ вычислении суммы элементов

вектора (теорема 2.2). При использовании КУУ и КВС ускорение составит

(л X N 1

—2— для процедур умножения и скалярного произведения (теоремы 2.5 и ) и О^^| для суммы элементов вектора (теорема 2.3). Полученные оценки демонстрируют эффективность СВО при выполнении СПАРФ-вычислений.

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

системе БТАЯАМ. Одна из главных особенностей системы "Сибирь" заключается ь обеспечении решения задачи или ее частей на параллельной архитектуре (векторно-конвейерной, векторно-параллельной и ассоциативной), свойства которой согласованы с особенностями этой задачи. Определены требования к программному обеспечению (ПО), которые включают в себя: 1) выделение в решаемой задаче участков, вычисляемых с повышенной точностью; 2) организация двух типов процессов: управляющего (в хост-ЭВМ) и параллельного (в АПП); и 3) эффективное программирование и выполнение этих процессов.

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

для хранения точных (без округления) промежуточных результатов; скалярные регистры или скаляры Б, для размещения скалярных операндов; операционные регистры АПП X, У, М; индексные регистры или индексы 1, являющиеся целыми числами без знака и используемые для хранения констант, определяющих число повторений циклических участков СПАРФ-программы, режимы доступа к векторным регистрам, адреса слов и срезов и т.д.; регистры хранения масок ЯМ, служащие для запоминания масок, а также битовых срезов, являющихся результатами выполнения векторных операций.-

О

Сое

X м У дини

т ель

ная

с еть

т

1 п п п п к

У,',',',','//, \\\

им 0 1-1 УИ -г-УЯ 0 у - 1 У8 0 у8/ У32 VSJ

ШИН тт т \\\ \\\

Рис.2. Архитектура СПАРФ-про ц е ссора

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

Первый режим характеризуется постоянством разрядности операндов в

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

N - 4,1 - / , (3.1)

п

где п - требуемая разрядность операндов; I - число RM-регистров; N - размер слова АПП (емкость локального ЗУ).

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

СПАРФ-процессор имеет три формата данных: "integer" (целые числа), "fixed-point" (числа с фиксированной запятой и нулевой целой частью) и "real" (числа с целой и дробной частями).

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

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

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

В п. 4.1 демонстрируются возможности СПАРФ-процессора при получении точных скалярных произведений, а также сравнительный анализ результатов тестовых просчетов с параллельными ЭВМ SIEMENS/Fujitsu VP 400-ЕХ, CRAY-2 и пакета высокоточной арифметики ACRITH фирмы IBM. Примером этих тестов являются произведения Р= Х1'1 -ч'1', ¡=1,2 (табл. 1).

Таблица 1

х(1, Y< 1 > х(2, у<2>

27182818280 -31415926540 14142135620 5772156649 0 3010299957 14862497000000 8783669879000000 -223749200000 47737146470000000 0 1850490 5772156649 3010299957 0 27182818280 -31415926540 14142135620 47737146470000000 1850490 0 14862497000000 8783669879000000 -223749200000

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

Таблица 2

Си стема Р 1 Р 2

VP-400-EX VP-400-EX(C векторизацией) CRAY-2 CRAY-2 (С векторизацией) IBM PC/AT(Дв . точность) IBM4381 (ACRITH) СПАРФ 0.462915718600000Е+10 -0.334189890000000Е+09 -0.179496213989999Е+13 -0.110380659550720Е+13 0.186091654600000Е+10 -0.100657107000000Е+10 -0.100657107000000Е+10 -0.115474320000000Е+10 О.ОООООООООООООООЕ+ОО -0.170625964441600Е+13 -0.110380659550720Е+13 0.436495923200000Е+10 -0.100657107000000Е+10 -0.100657107000000Е+10

В п. 4.2 рассмотрены алгоритмы умножения матриц с многоразрядными элементами. С учетом минимизации числа векторных регистров разработан алгоритм умножения матриц А э [а. .] и В з [Л ] порядка N с одновременным

получением N элементов результирующей матрицы С = АВ а [а ] [6 ] = [с ].

( / у к /к

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

С. Показано (утверждение 4.1), что умножение матриц порядка N на СПАРФ-процессоре, имеющем т = Ы2 каналов обработки и разрядность операндов п бит может быть выполнено за время Од(Мо%2Ы) и О^ (Ып+пЫХо^^Ы).

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

до размера N = 2 , и сжатия матрицы размерности N до требуемого

размера N. Показано (утверждения 4.2 и 4.3), что эти алгоритмы могут быть выполнены за время и ^с^Л^+я).

Если порядок матриц достаточно мал, то выполняется параллельное вычисление нескольких произведений, поддерживая тем самым максимальную производительность АПП (рис. За). Число одновременно перемножаемых матриц

при этом равно ц

N

где Ы =

Показано (утверждение 4.4), что относительное ускорение (рис. 36) умножения матриц порядка N с я-разрядными элементами на СПАРФ-процессоре,

имеющем т каналов обработки, при т & ЛГ составляет О

оп/с 3001

100

.4

е-

о

о д 80

л

с

0)

н 60

ч

о

в 40-

сч

о

а го-

с

о-^-б-о Г1—64 * п=128

®©€кэе п-»56 /

N

20

а)

б)

Рис. 3

Разработан алгоритм ускоренного получения точного произведения (без округления) с промежуточным запоминанием частичных произведений и сумм и переключением СПАРФ-процессора на требуемый предел разрядности п/ = 2n+log2N бит. Данный подход обеспечивает в среднем трехкратное ускорение по сравнению с вычислениями с фиксированной точностью.

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

р-1

Р(х) а х' (п. 4.3), рассматриваемых как скалярное произведение вектора

А = {а~,а ,а и вектора степеней X* = {1,*,д:2,...,Определена

операция префиксного произведения, формирующая из вектора

I

С = {с0,сг..,ск вектор С* = такой, что с* =ПС,-

Показано (утверждение 4.5.), что вычисление префиксного произведения для вектора, содержащего р элементов, на СПАРФ-процессоре, имеющем тар каналов параллельной обработки и разрядность операндов п бит, может быть выполнено за время О^Хоъу) и п2\о%^). Получение вектора X осуществляется путем применения префиксного произведения к вектору X' = {1,х,х,формируемому размножением аргумента х.

Это позволяет вычислить N полиномов степени р с /¡-разрядными элементами на СПАРФ-процессоре, содержащем т = рЫ 1 каналов параллельной обработки и имеющем разрядность операндов п бит за время Ол(1оё^р) и О^Д/г^к^уг^+пк^^р) (утверждение 4.6) с ускорением при вычислении одного Р

полинома О - (утверждение 4.7).

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

'-167,для / = 8

1 б4 ,для /=11 (/= О.....15),

16"',в остальных случаях

и исходными значениями х, = 16 + /'-¡б'7 при (/ = -6,-5,...,-1,0,1,...,4).

Таблица 3

j PJ(эка1аг) УР400-ЕХ Р^(уес1ог) УР400-ЕХ Р^(Ногпег) УР400-ЕХ PJ(АСЯ1ТН) PJ (СПАРФ)

-6 -4831838152 -4831838140 -4831838162.0 -4831838139.25 -4831838133 2500

-5 -4026531800 -4026531788 -4026531810.5 -4026531789.81 -4026531783 8125

-4 -3221225448 -3221225436 -3221225456.0 -3221225437.00 -3221225431.0000

-3 -2415919096 -2415919084 -2415919098.5 -2415919080.81 -241591907 4 8125

-2 -1610612728 -1610612716 -1610612738.0 -1610612721.25 -1610612715 2500

-1 -805306360 -805306348 -805306374.5 -805306358.31 - 805306352 3125

О 8 4 8.0 8.00 14 0000

1 805306376 805306372 805306377.5 805306377.68 805306383 6875

2 1610612744 1610612740 1610612750.0 1610612750.75 1610612756 7500

3 2415919112 2415919108 2415919125.5 2415919127.18 2415919133 1875

4 3221225480 3221225476 3221225504.0 3221225507.00 3221225513 0000

методом простой итерации (п. 4.4). Показано (утверждение 4.9), что вычисление каждого приближения вектора неизвестных для системы линейных уравнений порядка N с »-разрядными элементами на СПАРФ-процессоре, содержащем т = Л^ каналов обработки, может быть выполнено за время О^Оод^ЛО и ОцО^+нк^ЛО. Для обработки систем уравнений произвольных порядков используются описанные выше процедуры растяжения и сжатия. Показано (утверждение 4.10), что ускорение вычисления каждой итерации для системы линейных уравнений порядка Л' с /¡-разрядными элементами на СПАРФ-процессоре, имеющем т каналов обработки, при /л > Л/2 составляет

/г+ 1 og2Л'

Рассмотрена возможность параллельного решения нескольких систем уравнений. В случае, когда число каналов обработки т таково, что позволяет разместить в векторном регистре более одной системы уравнений, то можно организовать одновременную обработку l^n/N2¡\ систем. Общее время решения в этом случае равно времени решения наихудшей по сходимости системы.

Предложен алгоритм ускоренного получения требуемой точности решения с поэтапным уточнением результата. Выигрыш получается за счет использования операндов с малой разрядностью на начальном этапе вычислений, поскольку в этом случае значительно сокращается время выполнения арифметических операций. Другими словами, вначале осуществляется грубое вычисление результата, которое затем уточняется при переходе СПАРФ-процессора на следующие пределы разрядности. В этом случае параметр, определяющий требуемую точность вычислений, представляет собой вектор значений Е = {£;,е2,...,£.,...,£;}. Каждое е. задает требуемую точность результата на соответствующем пределе разрядности СПАРФ-процессора. При выполнении условия завершения текущего этапа СПАРФ-процессор переходит на следующий диапазон разрядности, и вычисления осуществляются для нового е .

Величина ускорения зависит от соотношения начального и требуемого для заданной точности диапазонов разрядности. Приведены результаты измерения ускорения, которые свидетельствуют о значительном увеличения скорости вычислений. Так, например, при начальной разрядности п = 32 бита и требуемой точности £ = 10"6< ускорение составит 5.81, а при п = 64 и £ = 10"^2 оно составит 2.22. Это также подтверждает большие возможности СПАРФ-процессора для эффективного выполнения вычислений с повышенной точностью.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

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

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

2. Разработан язык описания алгоритмов УЕРИАГ*}, обеспечивающий наглядность в изображении механизма вертикальной обработки и получение оценок временной сложности различных алгоритмов с учетом свойств как базовой архитектуры СВО, так и СВО с сопроцессорами.

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

4. Разработана система программирования СПАРФ-вычислений, на базе АПП ЕС-2720 с архитектурой, близкой системе 5ТАЯА1Ч, рассматриваемая как векторный процессор с динамически изменяемой разрядностью векторных операндов и являющаяся практическим средством для решения задач, содержащих большую долю векторных и матричных операций. Показано, что разработанная система соизмерима по точности с аналогичными системами для универсальных ЭВМ, обладая при этом более высокой производительностью за счет эффективного использования массового параллелизма СВО.

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

1. Важенин А.П. Оценка быстродействия алгоритмов для ассоциативных параллельных процессоров // Труды Всес. научно- техн. семинара "Программное

обеспечение многопроцессорных систем". - Калинин: Центрпрограммсистем, 1988. - С. 213-216.

2. Важенин А.П. Алгоритмы ускоренного высокоточного умножения для ассоциативного параллельного процессора // Математическое и архитектурное обеспечение параллельных вычислений.- Новосибирск: 1989.- С. 6-21.

3. Важенин А.П. Рекурсивный алгоритм ускоренного умножения сверхбольших операндов для ассоциативного параллельного процессора // Труды VII Всес. семинара "Параллельное программирование и высокопроизводительные структуры" .- Киев: Ин-т кибернетики им. В.М. Глушкова АН УССР, 1988.- С. 141-142.

■ 4. Важенин А.П. Организация высокоточных параллельных арифметических вычислений на ассоциативном параллельном процессоре // Труды VII Всес. школы-семинара "Распараллеливание обработки информации".- Львов: Физ.-мех. ин-т им. Г.В. Карпенко АН УССР, 1989.- т.1, С. 18-19.

5. Важенин А.П., Седухин С.Г., Фет Я.И. Высокопроизводительные вычислительные системы комбинированной архитектуры // Труды VII Всес. школы-семинара "Распараллеливание обработки информации",- Львов: Физ.-мех. ин-т им. Г.В. Карпенко АН УССР, 1989.- т.1, С. 72-73.

6. Важенин А.П., Седухин С.Г., Фет Я.И. Высокопроизводительные вычислительные системы комбинированной архитектуры,- Новосибирск: 1989,24 с. (Препринт / АН СССР. Сиб. отд-ние. ВЦ; 866).

7. Важенин А.П. Математическое обеспечение высокоточных параллельных арифметических вычислений для ассоциативного параллельного процессора // Высокопроизводительные вычислительные системы для комплексных центров математического моделирования. Архитектура и общесистемное математическое обеспечение,- Новосибирск: 1991,- С. 127-138.

8. Vazhenin А.Р. Programming System of High Accuracy Computations for Associative Array Processor // Inter.Conf.: CONPAR 90-VAPP IV, Volume of spécial technical contributions.,- Zurich, 1990.- P. C69-C72.

9. Vazhenin A.P., Sedukhin S.G., Fet Ya.I. High-Performance Computing Systems of Combined Architecture // In: Proc. of the Int. Conf. "Parallel Computing Technologies", Novosibirsk, USSR, September 7-11, 1991.- World Scientific, Singapore.- P. 246-257.

10. Важенин A.П., Фет Я.И. Специализированные процессоры в системах вертикальной обработки // Параллельные алгоритмы и структуры.- Новосибирск: 1991.- С. 37-50.

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