Введение к работе
Актуальность проблемы. Решение многих научных и практических задач на ЭВМ требует повышения точности результатов обработки. Одной из важных причин, влияющих на точность вычислений, является использование округлений в арифметических операциях. Они, в основном, связаны с фиксированной и относительно малой длиной операндов в универсальных ЭВМ. Поэтому разработка устойчивых к округлениям алгоритмов является принципиальной задачей вычислительной математики.
На реализационном уровне для уменьшения влияния ошибок округления обычно используют специальные алгоритмические и программные средства, позволяющие проводить учет этой погрешности в процессе вычислений, аналитические преобразования расчетных выражений, а также программную реализацию или микропрограммную интерпретацию арифметики многократной точности. Однако, решение этой проблемы на базе однопроцессорных систем ведет к быстрому замедлению скорости решения задачи и неэффективному использованию памяти.
В работах Н.Н. Миренкова, С. Реддауэя, Д. Бьюэла и других показано, что параллельная обработка открывает широкие возможности для организации вычислений с повышенной точностью. Развитие современной интегральной технологии и вычислительной техники делает возможным создавать параллельные системы, работающие со словами не фиксированной, а динамически изменяемой длины. Это позволяет на основе различных типов параллельной обработки решать задачи либо с заданной точностью, либо с точностью, которая обеспечивается ресурсами системы и о которой пользователю известно по окончанию счета.
К таким системам следует отнести параллельные системы вертикальной обработки (СВО). Их отличительные особенности, сочетающие в себе возможность размещения и параллельной обработки операндов произвольно-большой размерности (до нескольких тысяч бит), программируемость форматов обрабатываемых данных, маскируемость данных в выполняемых операциях и т.д., обеспечивают эффективное выполнение и программирование высокоточных вычислений.
В связи с этим особую актуальность приобретают вопросы исследования и разработки алгоритмических и программных средств высокоточной параллельной арифметики (СПАРФ-арифметики) на базе ассоциативных параллельных процессоров (АПП), представляющих собой довольно большой подкласс систем вертикальной обработки.
Целью диссертационной работы является создание методов и средств СПАРФ-арифметики на базе ассоциативных параллельных процессоров. Достижение указанной цели связывается с решением следующих задач:
разработка и анализ параллельных алгоритмов СПАРФ-арифметики для систем вертикальной обработки;
исследование возможностей базовой архитектуры СВО с точки зрения эффективности выполнения операций с многократной точностью и динамически изменяемой разрядностью операндов. Определение путей дальнейшего развития этой архитектуры с целью увеличения производительности СВО для задач СПАРФ-арифметики;
разработка системы программирования СПАРФ-вычислений на базе АПП ЕС-2720 с архитектурой, совместимой с системой STARAN.
Научная новизна состоит в создании и исследовании нового типа программно-аппаратных средств, поддерживающих специальные виды численных экспериментов. Новизну раскрывают следующие результаты:
-
Разработан язык VEPRAN, предназначенный для описания алгоритмов для СВО как базовой, так и расширенной архитектуры и обеспечивающий наглядность в изображении механизма вертикальной обработки и получение оценок временной сложности этих алгоритмов.
-
Разработаны параллельные алгоритмы СПАРФ-арифметики для АПП, в которых обеспечено параметрическое управление разрядностью операндов, предложена методика получения уточненных оценок времени выполнения алгоритмов на СВО, позволяющая различать алгоритмы с одинаковыми асимптотическими оценками, но имеющими разную практическую эффективность, получены асимптотические оценки ускорения для основных СПАРФ-операций при их реализации на СВО в сравнении с универсальными ЭВМ.
-
Определены пути адаптации архитектуры СВО для более эффективного выполнения СПАРФ-вычислений за счет использования сопроцессоров, разработаны способы включения этих устройств в базовую архитектуру СВО, алгоритмы их функционирования и получены оценки временной сложности для основных СПАРФ-операций при использовании этих устройств.
-
Разработана система программирования высокоточных вычислений на АПП, представляемая для пользователя как программируемый векторный процессор (СПАРФ-процессор), архитектура которого встроена в базовую архитектуру АПП с сохранением всех ее свойств и обеспечением динамического управления разрядностью векторных операндов в процессе вычислений.
Практическая ценность:
Язык 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 таблиц.
