ВВЕДЕНИЕ
Одним из новых направлений развития средств вычислительной техники является разработка высокопроизводительных вычислительных устройств, сочетающих в себе современную элементную базу, развитое математическое обеспечение, достаточную емкость памяти и т.д [ 37 ].
Это обусловлено, в первую .очередь, необходимостью решения широкого спектра задач в реальном режиме времени, понятия которых приводятся в [ 53]. Такие задачи возникают, например, в аэродинамике [ 32 ],
I
климатологии, машинной графике , ядерной физике , физике плазмы, энергетике [ 15 ].
В то же время следует отметить, что существующие высокопроизводительные ЭВМ удовлетворяют пользователей сегодня, но уже в ближайшие годы могут не соответствовать требуемым параметрам из-за постепенного роста сложности решаемых задач. [ 15, 70 ].
Однако, наряду со значительными успехами в истории архитектуры высокопроизводительных ЭВМ, традиционно функционирующих в двоичной системе счисления, еще недостаточно исследованы возможности, связанные с оптимизацией способов кодирования потоков числовых данных, с точки зрения повышения производительности [ 4 ].
Также следует отметить, что проблему повышения производительности ЭВМ необходимо решать в тесной взаимосвязи с задачей обеспечения заданной точности вычислений. Требование к высокой точности ЭВМ приобретает особую значимость при решении класса плохообусловленных задач , где не допускается накопление ошибок округления [16]. К таким задачам относятся, например, решение систем линейных уравнений с определителем близким к нулю, обращение матриц Гильберта и др. [44,83].
Значение ошибок округления можно уменьшить путем удлинения разрядной сетки сумматоров, что безусловно влечет за собой увеличение аппаратурных затрат и не приводит к полному устранению погрешности вычислений. Указанный факт требует поиска алгоритмических способов,
6
связанных с применением новых нетрадиционных методов и систем счисления для представления и обработки чисел [ 3 ].
В [21] показывается, что это можно достичь, прежде всего, средствами специального кодирования, наиболее широкий интерес из которых представляет собой система остаточных классах (СОК). Ей присущи высокая скорость вычислений и точность результатов [1,2, 3].
В то же время практическая применимость СОК сдерживается рядом проблем, связанных со сложностью сравнения чисел, введения знака, . преобразования в позиционную систему счисления [ 3 ].
Многочисленные работы в области непозиционных систем" и математического аппарата теории чисел позволили выделить новое научное направление - теорию безошибочных вычислений [ 21, 101-104 ].
Существенный вклад в развитие теории внесли работы Р. Грегори, Е. Кришнамурти , О. Ватануки, А. Фромента, посвященные безошибочным вычислениям в системе остаточных классов и с использованием кодов , Гензеля [21,66,105, 119,122,123,139, 140].
Известны также работы, посвященные исследованиям знакоразрядной системы счисления и диадических рациональных чисел, называемых также «псевдо-цифрами» для безошибочных вычислений с плавающей запятой [138].
В работах Д. Вуллинина, А.Нильсона, П. Корнерупа, Р.Хэкмана развиваются алгоритмы безошибочных вычислений над числами с плавающей запятой [112,123,118,119].
Преимуществами системы остаточных классов для безошибочных вычислений являются высокое быстродействие в многомодульной системе и отсутствие межразрядного переноса между цифрами.
Объединение достоинств системы остаточных классов для безошибочных вычислений, табличной арифметики и разрядно-параллельных принципов обработки информации получило свое развитие в работе [ 4 ].
7
В работе [ 4 ] описывался метод оперативного выхода результата за
пределы диапазона системы остаточных классов и определения
количественной меры возникшего переполнения, позволяющей восстановить
истинную величину результата, рассматривались алгоритмы безошибочных
. вычислений с числами формата плавающей запятой на основе рангов.
Однако, данный метод обладает существенными ограничениями • применимости, поскольку не позволяет определить факт псевдопереполнения в одномодульной и многомодульной системах остаточных классов для рациональных чисел, а безошибочные вычисления с использованием рангов приводят к стремительному росту разрядности операндов и возникновению ошибки переполнения.
Следует отметить, что основными проблемами безошибочных вычислений, сдерживающими их применение на практике, являются невысокое быстродействие, отсутствие метода выбора модулей системы остаточных классов, рост разрядности операндов [112].
Решение указанных проблем позволит использовать методы безошибочных вычислений во многих задачах науки и техники.
Актуальность работы подкрепляется такими практическими приложениями, как управление сложными техническими системами, цифровая обработка сигналов и др.
ЦЕЛЬ ДИССЕРТАЦИОННОЙ РАБОТЫ заключается в исследовании модели безошибочных вычислений в системе остаточных классов и ее усовершенствованию в направлении создания высокопроизводительных ЭВМ.
ПРЕДМЕТОМ ИССЛЕДОВАНИЯ является модель безошибочных вычислений в системе остаточных классов и её алгоритмическая, аппаратная и программная реализация.
МЕТОДЫ ИССЛЕДОВАНИЯ опираются на положения теории чисел, алгебры логики, линейной алгебры, компьютерных систем
8
программирования для последовательных и параллельных ЭВМ, теорию алгоритмов и организации вычислительных процессов, теорию автоматов.
НАУЧНАЯ НОВИЗНА данного диссертационного исследования заключается в разработке модели безошибочных вычислений с рациональными числами в СОК, отличающейся от ранее известной 'введением индексов, антииндексов, расширением диапазона представления искомых результатов, а также получением верхней оценки модуля СОК, для частных задач.
На защиту выносятся следующие результаты:
- Алгоритмические принципы прямых и обратных преобразований чисел из позиционной системы счисления в СОК, включающие преобразование чисел, представленных в формате с фиксированной запятой.
- Ускоренный алгоритм деления в многомодульной СОК на основе таблиц индексов и антииндексов.
- Способ получения верхней оценки модуля СОК, обеспечивающий гарантированное получение результата безошибочных вычислений в зависимости от общего числа арифметических операций.
- Метод организации безошибочных вычислений с расширением диапазона представления искомых результатов в классе дробей Фарея порядка N с модулем р в СОК, определяемого исходя из следующего неравенства: N < р - I, вместо N ? jp-i .
- Принципы структурной реализации разработанной модели безошибочных вычислений с использованием разрядно-параллельной схемы обработки числовых данных.
- Результаты экспериментального исследования модели безошибочных вычислений в многомодульной СОК с использованием параллельной мультикомпьютерной сети «КУРС-2000», разработанной на кафедре ВМСиС МЭИ (ТУ).
- Сравнительные оценки быстродействия аппаратной и программной реализации алгоритмов безошибочных вычислений в СОК.
ПРАКТИЧЕСКАЯ ЦЕННОСТЬ
Разработана программа безошибочного решения системы линейных уравнений в одномодульной системе остаточных классов (свидетельство гос. регистрации №2003610764 в реестре, программ для ЭВМ). Программа безошибочного решения системы линейных уравнений в одномодульной СОК нашла применение в ОАО «Дагэнерго» и включена в состав комплекса программ "Расчет суточных режимов Сулакского каскада ГЭС",, что подтверждено соответствующим актом о внедрении.
Экспериментальное исследование, проведенное в ОАО «Дагэнерго» ' показало, что использование разработанной программы- безошибочных вычислений позволило уточнить прогностическую оценку уровня воды в нижнем бьефе Чирюртовской ГЭС более чем на 2% по сравнению с используемой на практике программы «Расчет добегания расхода воды».
Результаты диссертационного исследования также используются в учебном процессе Дагестанского государственного технического университета по специальностям 22.01 и 22.04, имеется акт о внедрении.
АПРОБАЦИЯ РАБОТЫ. •Основные результаты работы докладывались и обсуждались на :
- Республиканской научно-технической конференции «Информационные и телекоммуникационные системы: интегрированные корпоративные сети» («Дагинформ-2001» г. Махачкала, 2001 г.)
- Всероссийской научной конференции с международным участием молодых ученых и аспирантов «Новые информационные технологии. Разработка и аспекты применения» ( г.Таганрог, 2002 г.)
- Всероссийской научно-технической конференции «Новые информационные технологии» ( г. Москва, 2003 г.)
- Международной научной конференции «Информационные технологии в науке, образовании, телекоммуникации, бизнесе» ( Украина, Крым, Ялта-Гурзуф, 2003 г.)
10
- Международной научной конференции «Информационные средства и технологии» ( г. Москва, 2003 г.)
- Международной1 научной конференции. Parallel Computational Fluid Dynamics ( г. Москва, 2003 г.)
ПУБЛИКАЦИИ. По материалам диссертационной работы опубликовано 11 трудов, в том числе 5. статьи, 6 тезисов докладов. Получено . свидетельство о регистрации программы и поданы 3 заявки на предполагаемые изобретения в области вычислительной техники.
СТРУКТУРА И ОБЪЕМ ДИССЕРТАЦИИ . Диссертационная работа состоит из введения, 4 глав, заключения, списка литературы и приложения. Она изложена на 140 сраницах основного машинописного текста, содержит 42 рисунка, 18 таблиц, включает библиографию из 143 наименований. Общий объем диссертации составляет 264 страниц.
В ПЕРВОЙ ГЛАВЕ проводится анализ класса задач, требующих для своей реализации ЭВМ с повышенной точностью вычислений. Тем самым показывается целесообразность использования для их решения методов безошибочных вычислений.
Описываются основные операции и особенности представления чисел в системе остаточных классов. Предлагаются, способ получения верхней оценки модуля системы остаточных классов, гарантирующий получение искомого результата безошибочных вычислений и метод организации безошибочных вычислений с расширением диапазона представления искомых результатов в классе дробей Фарея. Приводятся теоретические основы алгоритмов деления в одномодульной и многомодульной СОК.
Рассматриваются способы повышения производительности вычислительных устройств, принципы построения таких устройств с целью их применения при разработке структурных схем быстродействующих устройств безошибочных вычислений в системе остаточных классов. Приводятся основные цели и задачи диссертационного исследования, обосновывается необходимость аппаратной реализации алгоритмов,
11
обеспечивающих выполнение безошибочных вычислений в системе остаточных классов. ¦
ВТОРАЯ ГЛАВА посвящена разработке быстродействующих алгоритмов,
безошибочных вычислений. К ним относятся следующие алгоритмы: прямых
. и обратных преобразований целых чисел из позиционной системы счисления
в систему остаточных классов, нахождения обратного' элемента в
• многомодульной СОК, реализации, арифметических операций с
рациональными числами в одномодульной и многомодульной системах
• остаточных классов на основе дробей Фарея, преобразования чисел с
фиксированной запятой в дроби Фарея. •
В ТРЕТЬЕЙ ГЛАВЕ на основе разработанных алгоритмов, предлагается структурная организация основных узлов процессора, обеспечивающих безошибочную обработку чисел, с фиксированной запятой. Приводятся оценки временных и аппаратурных затрат разработанных структурных схем. В ЧЕТВЕРТОЙ ГЛАВЕ проводится экспериментальное исследование 1 модели безошибочных вычислений на основе параллельной мультикомпьютерной Сети «КУРС-2000», разработанной на кафедре ВМСиС МЭИ (ТУ). Приводятся оценки быстродействия аппаратной и программной реализации алгоритмов безошибочных вычислений в системе остаточных классов. Описываются результаты применения разработанной программы безошибочных вычислений в ОАО «Дагэнерго».
12
ГЛАВА 1. МОДЕЛЬ БЕЗОШИБОЧНЫХ ВЫЧИСЛЕНИЙ КАК НАПРАВЛЕНИЕ РАЗВИТИЯ ВЫСОКОПРОИЗВОДИТЕЛЬНЫХ ЭВМ
1.1. Классы задач, определяющие необходимость перехода к " ' безошибочным вычислениям
В настоящее время в различных областях науки и техники возрастает . потребность решения задач большой размерности, которые требуют обработки огромных массивов цифровой информации с высокой точностью. • К таким задачам относятся, например, в климатологии - проведение численного эксперимента с глобальной моделью атмосферы, в энергетике -' расчет режима энергосистемы, в аэродинамике - исследование аэродинамических характеристик летальных аппаратов.
В последнее время возрастает потребность решения задач большой ¦ размерности не только в традиционных. для вычислений областях, но и в других, где ранее такие вычислительные работы не проводились, например, в биологии, военном деле и т.п.
Одной из существенных проблем решения таких задач на ЭВМ является накопление ошибок округления в ходе вычислительного процесса, учет которых требует больших временных затрат и трудозатрат.
Построение «устойчивых алгоритмов» решения такого класса задач, при использовании которых вычисления доводятся до конца без существенного искажения результатов, составляет существенную часть теории численных методов.
Наиболее распространенные в настоящее время методы приближенного решения задач механики, математической физики, такие, как метод Ритца, Бубнова-Галеркина, конечных элементов, сеток, интегральных уравнений и др, будучи применены к линейным задачам сразу приводят к линейным алгебраическим системам. Если же перечисленные методы
13
применяются к. нелинейным задачам, то они приводят к нелинейным системам с конечным числом числовых неизвестных, которые в свою очередь могут быть сведены к линейным алгебраическим "системам. Естественным поэтому является то большое внимание, которое в последние
. десятилетия уделяется улучшению старых и разработке новых методов численного , решения линейных алгебраических систем и оценке • погрешностей этих методов. .
Известно, что в реальном вычислительном процессе все вычисления
¦ осуществляются с конечным числом знаков и на каждом этапе счета возможны ошибки округления [ 5,16,17,18,60, 89, 90 ]. • .
Другая особенность реального вычислительного процесса, которую необходимо учитывать при построении алгоритмов связана с наличием на ЭВМ «машинного нуля», «машинной бесконечности», детерминированной операции округления, явлением исчезновения порядка [44]. Понятия «машинного нуля» и «машинной бесконечности» характеризуют допустимый
1 порядок чисел, которые могут быть представлены в ЭВМ и для различных ЭВМ они могут различаться. Исчезновение порядка происходит тогда, когда . результатом арифметических операций является число, слишком близкое к нулю и меньшее «машинного нуля». ЭВМ заменяет такой результат нулём. Это событие не имеет таких катастрофических последствий, как переполнение. Тем не менее существуют задачи , для которых факт появляения машинного нуля важен [44].
Влияние вычислительных погрешностей приводит к значительной потере точности при решении класса плохообусловленных задач, например, обращении матриц Гильберта (см. приложение 5), в численно неустойчивых алгоритмах и др.
Из приведенного выше следует, что проблема точности вычислений актуальна для указанных классов задач и требует тщательного изучения [15, 16,58,60 62,78].
14
Одним из перспективных и многообещающих направлений в
исследованиях по данной проблеме ' является внедрение методов
безошибочных вычислений на основе, нетрадиционных • способов
кодирования и соответствующих им- вариантов машинной арифметики
. [95,96,100,106-110,113,124,125,126-141].
Особую роль в развитии указанного направления играют числовые ¦ системы с параллельной структурой и, в первую очередь, модулярные системы счисления, в которых. целые числа представляются наборами • остатков от деления на выбранные модули [91,92,97,98].
1.2. Модель безошибочных вычислений на основе системы остаточных
классов
Суть безошибочных вычислений заключается в выполнении
арифметических операций без потери точности. Такие вычисления
« возможны в системе остаточных классов, в которой рациональные числа
представляются целыми. В этой системе счисления все вычисления
проводятся над целыми числами.
В современных математических пакетах ( Reduce, Maple, Mathcad ) для реализации рациональной арифметики, как правило, используется схема приведения дробей, т.е все арифметические действия с рациональными числами выполняются как операции над дробями. Недостатками безошибочных вычислений по схеме приведения дробей являются необходимость выполнять арифметические действия как с числителями, так и знаменателями и определения наибольшого общего делителя результатов арифметических операций. Результаты численных экспериментов показали, что быстродействие безошибочных вычислений по этой схеме значительно ниже чем в системе остаточных классов.
Существует взаимно однозначное соответствие между множеством целых чисел системы остаточных классов и некоторым конечным
15
множеством рациональных чисел. Это множество состоит из так называемых дробей Фарея - несократимых дробей, числители и знаменатели которых меньше заданного числа - порядка дроби. Фарея [21, 22 ]. 'Конечный результат •' арифметических операций, на множестве чисел системы
. остаточных классов можно отобразить в соответствующую .дробь Фарея, ' если не возникает псевдопереполнение,, что происходит тогда, когда точный
¦ результат имеет порядок дроби Фарея больше заданного. Поэтому необходима оценка порядка дроби Фарея. и соответствующего модуля
• системы остаточных классов. " '
На рис 1.2.1. показана модель безошибочных • вычислений с рациональными числами, в которую входят блоки прямых, обратных преобразований и арифметики СОК.
В соответствии с этой моделью, процесс .безошибочных вычислений включает в себя:
1 1. Определение порядка дроби Фарея и соответствующего модуля системы остаточных классой.
2. Преобразование рациональных чисел в целые числа СОК.
3. Проведение арифметических операций в СОК.
4. Преобразование результатов из СОК в соответствующие несократимые дроби Фарея.
5. Вывод точных результатов.
Из теории чисел известно, что любое целое число можно представить последовательностью его наименьших неотрицательных вычетов а,,..., ак по модулям р,,..., рк и такое представление единственно в диапазоне [О, Р), где
к
Р = Yl pi) если модули попарно взаимно простые.
Традиционная схема вычислений
ось рациональных чисел
Преобразование в СОК
Арифметика СОК
Обратное преобр.
Условие псевдопереполнения
ось целых чисел
Рис 1.2.1. Модель безошибочных вычислений в одномодульнои системе остаточных классов
17
Наоборот, каждой последовательности указанных вычетов а,,..., а k соответствует только одно число внутри того же диапазона
[3].
Рассмотрим два сравнения. Если Р, и Р2 взаимно просты, то система
двух сравнений вида:
х = al (mod P,) 1 х = or2 (mod P2)J
(1.2.1)
в точности эквивалентна одному сравнению по mod Р,Р2
Существует ровно одно решение системы по mod p,p2 [ 42 ].
Известна следующая теорема, называемая «Китайской теоремой об остатках», которая формулируется следующим образом [ 46 ]:
Пусть р,,..., р п - система попарно взаимно простых чисел, тогда система сравнений:
X = Xj(mod pj), i = 1,..., n (1.2.2)
имеет следующее единственное решение:
X н Хо (mod P) ( 1.2.3)
где
Р = Рг--Р„>
Хо = Z В, • х„ В{ = Р{ • т, , Р, = —, i=i Pi
а числа т, выбираются так, что Pjirij = 1 ( mod Pj).
Таким образом, X принадлежит классу чисел по модулю Р, наименьший неотрицательный вычет этого класса меньше Р, другие вычеты отличаются на величину, кратной Р.
Эти свойства сравнений дают возможность рассматривать каждую последовательность наименьших неотрицательных вычетов ( остатков ) по

 Часть из работы     Получить работу