Авторефераты по всем темам >>
Авторефераты по техническим специальностям
На правах рукописи
ОЦОКОВ ШАМИЛЬ АЛИЕВИЧ
СТРУКТУРНО-АЛГОРИТМИЧЕСКИЕ МЕТОДЫ ОРГАНИЗАЦИИ ВЫСОКОТОЧНЫХ ВЫЧИСЛЕНИЙ НА ОСНОВЕ ТЕОРЕТИЧЕСКИХ ОБОБЩЕНИЙ В МОДУЛЯРНОЙ СИСТЕМЕ СЧИСЛЕНИЯ
05.13.05. - Элементы и устройства вычислительной техники и систем управления 05.13.15. - Вычислительные машины, комплексы и компьютерные сети
АВТОРЕФЕРАТ
диссертации на соискание учёной степени доктора технических наук
Москва -2010
Работа выполнена на кафедре Вычислительных машин, систем и сетей Московского энергетического института (технического университета).
Научный консультант доктор технических наук, профессор Дзегелёнок Игорь Игоревич Официальные доктор технических наук, оппоненты академик Национальной академии наук Казахстана, профессор Амербаев Вильжан Мавлютинович доктор технических наук, профессор Борисов Вадим Владимирович доктор технических наук, профессор Горбатов Александр Вячеславович Ведущая организация Федеральное государственное унитарное предприятие НИИ Квант
Защита состоится л _______ в ___ ч. на заседании диссертационного совета Д 212.157.16 при Московском энергетическом институте (техническом университете) по адресу: 111250, Москва, Красноказарменная ул., д. 17, ауд. Г 306.
С диссертацией можно ознакомиться в библиотеке МЭИ.
Автореферат разослан л___ _______________ Отзывы в двух экземплярах, заверенные печатью организации, просим отправлять по адресу: 111250, г. Москва, Красноказарменная ул., д. 14, Учёный совет МЭИ(ТУ).
Учёный секретарь диссертационного совета к.т.н., доцент С.А. Чернов
ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ
Актуальность темы. С ростом производительности современных ЭВМ расширяется спектр и размерность решаемых на ЭВМ задач, повышаются требования к точности компьютерных вычислений.
Большинство компьютерных вычислений проводятся в арифметике с плавающей точкой с жестко ограниченной длиной мантиссы, что приводит к появлению неустранимых ошибок округления.
Проблема точности компьютерных вычислений особенно остро стоит при решении ряда прикладных задач, таких как, например, жестких задач с разномасштабными коэффициентами в ядерной физике, наноэлектронике, анализе многосвязных мехатронных систем и др.
Один из традиционных способов борьбы с ошибками округления - применение высокоточных вычислений. В настоящее время существует множество библиотек, поддерживающие высокоточные вычисления: ZREAL (Россия), MPARITH (Германия), GMP (США) и др.
Основной проблемой существующих библиотек высокоточных вычислений, сдерживающей их применение на практике, является сильная зависимость роста времени выполнения арифметических операций от точности вычислений. При малом объеме вычислений это не существенно, но для задач большой размерности использование существующих библиотек высокоточных вычислений приводит к резкому росту времени решения задач.
Многие задачи электротехники, энергетики и др. областей науки и техники требуют вычислений с комплексными числами. При вычислениях с комплексными числами также может происходить резкая потеря точности, т.к. комплексная арифметика на ЭВМ реализуется на основе традиционной арифметики с плавающей точкой и проблема сильной зависимости роста времени выполнения арифметических операций от точности еще в большой степени характерна для вычислений с комплексными числами.
Указанная проблема требует поиска новых способов, связанных с применением нетрадиционных систем счисления и арифметик для представления и обработки чисел.
Одной из таких арифметик является модулярная арифметика. В настоящее время в многочисленных работах модулярная арифметика использовалась как средство повышения быстродействия в цифровой обработке сигналов, криптографии, нейронных сетях и др. областях.
Модулярной системе счисления присущи возможность глубокого распараллеливания вычислений, отсутствие информационных обменов в процессе вычислений. Недостатками этой системы являются сложность сравнения, деления, округления чисел.
Существенный вклад в развитие теории модулярных вычислений внесли в нашей стране работы Акушского И.Я, Юдицкого Д.И, Амербаева В. М, Коляда А.А, Червякова Н.И, Финько О.А. и др, среди зарубежных можно выделить работы М.A. Soderstand, D.D.Miller, G.A. Jullien, M.A.
Jenkins, B.J. Leon и др.
Модулярные вычисления развиваются как в теоретическом, так и прикладном направлении.
Исследование модулярной системы счисления показало новую возможность применения модулярной арифметики как средство повышения точности вычислений и ослабления зависимости времени вычислений от точности, что позволяет выделить новое научное направление - теорию модулярных высокоточных вычислений.
Разработка эффективных алгоритмов высокоточных вычислений с рациональными и комплексно- рациональными числами со слабой зависимостью времени вычислений от точности и их аппаратная реализация позволит использовать высокоточные вычисления во многих областях науки и техники.
Таким образом, актуальность эффективных алгоритмов высокоточных вычислений с рациональными и комплексно- рациональными числами со слабой зависимостью роста времени вычислений от точности является несомненной и подтверждается мировой практикой.
Объектом исследования является многоядерные компьютерные системы и их составляющие в виде: сопроцессора и арифметического устройства, обеспечивающих высокоточные вычисления с учетом возможностей практической реализации.
Предметом исследования является организация высокоточных вычислений на основе теоретических обобщений в модулярной системе счисления.
Цель работы состоит в разработке структурно-алгоритмических методов и средств организации вычислений высокой точности с рациональными и комплексно-рациональными числами на основе теоретических обобщений в модулярной системе счисления.
Основными задачами
диссертационной работы являются:
1. Типизация вычислительных задач, критичных к точности компьютерных вычислений и их конкретизация в таких областях как: геоинформатика, робототехника, наноэлектроника и др.
2. Поиск целочисленного и знакового инварианта арифметики с плавающей точкой для определения целочисленности и знака значения полиномиального и дробно-рационального выражения.
3. Разработка единого формата представления рациональных и комплексно-рациональных чисел на основе теоретических обобщений в модулярной системе счисления.
4. Разработка алгоритмов высокоточных вычислений со слабой зависимостью роста времени выполнения арифметических операций от точности.
5. Разработка структурных принципов реализации высокоточных вычислений.
6. Анализ эффективности разработанных алгоритмов и структурных схем устройств, реализующих высокоточные вычисления.
7. Подтверждение разработанных методов высокоточных вычислений на примере решения ряда задач: определение управляемости линейных динамических систем, решения уравнения теплопроводности вдоль стенок труб с разномасштабными параметрами и др.
8. Внедрение разработанных программных средств для решения вычислительных задач, критичных к точности компьютерных вычислений в таких областях как: геоинформатика, робототехника, теплоэнергетика и др.
Методы исследования опираются на использовании математического аппарата теории чисел, универсальной алгебры, теории алгоритмов.
Научная новизна диссертационного исследования заключается в разработке общих алгоритмических и структурных принципов высокоточных вычислений с рациональными и комплекснорациональными числами в модулярной арифметике, отличающейся от ранее известных слабой зависимостью роста времени вычислений от точности при увеличении числа модулей.
На защиту выносятся следующие результаты1:
1. Типизация вычислительных задач, требующих применения высокоточных вычислений и критичных к нарушению алгебраических свойств в арифметике с плавающей точкой.
2. Единый модулярный и модулярно-позиционные форматы представления рациональных и комплексно-рациональных чисел в модулярной системе счисления.
Пункты 2-5, 8,9 - по специальности 05.13.05, пункты 6,7,10 - по 05.13. 3. Алгоритмы, реализующие высокоточные вычисления для рациональных и комплексно-рациональных чисел в модулярном формате.
4. Обобщение разработанных алгоритмов вычислений с исключением ошибок для работы с комплексно-рациональными числами.
5. Ускоренные алгоритмы параллельных вычислений с исключением ошибок округления с рациональными числами в модулярной арифметике.
6. Целочисленный инвариант, позволяющий определить целочисленность значения полиномиального или дробнорационального выражения в арифметике с плавающей точкой.
7. Знаковый инвариант, позволяющий определить знак значения полиномиального или дробно-рационального выражения в арифметике с плавающей точкой.
8. Структурные принципы организации высокоточных вычислений на основе модулярной арифметики.
9. Теоретическая оценка ускорения высокоточных модулярных вычислений при увеличении числа модулей.
10. Экспериментальная оценка быстродействия выполнения арифметических операций в модулярной системе счисления на многоядерном графическом ускорителе Практическая ценность работы 2 :
1. Определена возможность создания сопроцессора высокоточных вычислений, что подтверждено тремя патентами на узлы сопроцессора (устройства преобразования и округления в модулярной системе счисления).
2. Разработана библиотека, которая может найти применение при:
- проведении высокоточных вычислений с дробными и комплексными числами в таких областях как:
электротехника, энергетика и др.;
- исключении ошибок, связанных с неоднозначным представлением целых чисел и потерей знака в арифметике с плавающей точкой при вычислении значений дробнорациональных функций;
- исключении потенциально возможной резкой потери точности при решении задач с разномасштабными величинами.
Результаты работы внедрены в институте системного анализа РАН, в учебном процессе в Московском энергетическом институте (ТУ), в НПО Энергонаука, а также нашли применение в Межрегиональной распределительной сетевой компании Северного Кавказа, институте Пункт 1 - по специальности 05.13.05, пункт 2 - по 05.13. проблем геотермии Дагестанского научного центра РАН, что подтверждено соответствующими актами о внедрении.
Диссертационная работа выполнена при поддержке Х Гранта Президента РФ для молодых кандидатов наук МК65190.2010.Х Государственного контракта № 02.442.11.7546 по приоритетным направлениям, выполняемых в рамках программного мероприятия 1.9 "Проведение молодыми учеными научных исследований по приоритетным направлениям науки, высоких технологий и образования" федеральной целевой научно-технической программы "Исследования и разработки по приоритетным направлениям развития науки и техники" на 2002-2006 годы.
Х Гранта НШ-7239.2010.9 "Планирование масштабных вычислений и управление ресурсами распределенных вычислительных сред".
Совет по грантам Президента Российской Федерации на право получения средств для государственной поддержки ведущих научных школ Российской Федерации.
Достоверность основных результатов подтверждается следующим:
Х корректным использованием математического аппарата теории чисел, универсальной алгебры;
Х соответствием основных теоретических положений результатам выполненных экспериментов на многоядерных системах;
Апробация работы. Основные результаты работы докладывались и обсуждались на - Юбилейной международной научной конференции У 50 лет модулярной арифметикеФ (МИЭТ, Зеленоград, 2005 г.) - Международной конференции "Информационные средства и технологии", (МФИ, Москва, 2006 г.) - Всероссийской научно-технической конференции "Микроэлектроника и информатика (МИЭТ, Зеленоград, 2006 г.) - Международной конференции Параллельные вычисления и задачи управления ( PACO 2006, г. Москва, 2006 г.) - Международной научно-технической конференции Инфокоммуникационные технологии в науке, производстве и образовании (г. Кисловодск, 2008 г.) - Международной научной конференции Параллельная компьютерная алгебра (Parallel Computer Algebra 2010, г. Тамбов, 2010 г.) Публикации. Опубликовано 27 печатных работ, в том числе работ при подготовке данной диссертационной работы, 12 статей, из них в журналах, одобренных ВАК, 6 тезисов докладов. Получены 3 патента на изобретения в области вычислительной техники.
Структура и объем диссертации. Диссертация состоит из введения, семи глав, заключения, списка литературы из 126 наименований и приложения и изложено на 287 страницах машинописного текста, содержит 72 рисунка и 13 таблиц.
ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ
Во введении обоснована актуальность темы, объект и предмет исследования, сформулирована цель работы и научная проблема исследования, направления ее решения, раскрываются методы исследования, научная новизна и практическая ценность диссертации, реализация и внедрение результатов работы, основные положения, выносимые на защиту.
В главе 1 Организация высокоточных вычислений как направление развития компьютерных систем рассмотрены недостатки формата с плавающей точкой, приведены примеры задач, при решении которых в арифметике с плавающей точкой происходит резкая потеря точности, дана типизация задач, требующих применения высокоточных вычислений, проведен анализ состояния работ в области осуществления высокоточных вычислений, рассмотрена схема вычислений с отложенным округлением в модулярной арифметике.
Один из основных недостатков формата с плавающей точкой - неравномерное распределение чисел внутри диапазона представления (рисунок 1). На рисунке 1 показано распределение чисел с плавающей точкой в двоичной системе счисления, с длиной мантиссы 3 разряда, и порядком, который принимает значения от -1 до 2. В формате с плавающей точкой с данной длиной мантиссы и порядком число 9 не представимо.
Рисунок 1. Неравномерное распределение чисел с плавающей точкой Неравномерное распределение чисел может приводить к сильной потере точности компьютерных вычислений при решении вычислительных задач с разномасштабными коэффициентами. Так, например, скалярное произведение векторов x, y с координатами:
17 18 15 х = (10, 1223, 10, 10, 3, - 10 ), y = (1020, 2, -1019, 1013, 2111, 1016 ) равно 8779, а вычисленное в арифметике с плавающей точкой одинарной точности (стандарт IEEE 754) равно 4.61168602259351E+0020.
Потеря точности компьютерных вычислений может происходить и при выполнении арифметических операций с комплексными числами на ЭВМ, распределение представимых комплексных чисел в формате с плавающей точкой в диапазоне [-Fmax, Fmax; -iFmax,iFmax] показано на рисунке 2.
i Fmax - Fmax Fmax Цi Fmax Рисунок 2. Неравномерное распределение комплексных чисел с плавающей точкой Другой недостаток формата с плавающей точкой неоднозначным представлением целых и дробных чисел, например, число 1 можно представить, как целое и как бесконечную дробь: 1=0,(9)=0,999Е Из-за чего в современных языках программирования (C++, Pascal и др.) условие для проверки равенства двух переменных: if A = B then Е, где переменная А имеет тип float (число с плавающей точкой), В - целое число, или А, В - имеют тип float некорректны. Вместо проверки условия if A = B then Е иногда используется выражение вида if abs(A - B)<=eps then Е и др., но в них вводится параметр eps, который не всегда легко определить.
Неоднозначное представление целых и дробных чисел усложняет реализацию алгоритмов, где используются проверки равенства переменных различных числовых типов данных.
Недостатки формата с плавающей точкой и ошибки округления, возникающие в ходе вычислений приводят к нарушению алгебраических свойств арифметики с плавающей точкой: коммутативности, дистрибутивности, из-за этого, например, х не равно (х + х) - х. На рисунке 3 приведена типизация вычислительных задач, критичных к нарушению алгебраических свойств.
Задачи, критичные к нарушению алгебраических свойств можно условно разбить на плохо обусловленные задачи, задачи с разномасштабными коэффициентами и задачи чувствительные к классу эквивалентных преобразований (рис.3) Рисунок 3. Вычислительные задачи, критичные к нарушению алгебраических свойств Плохо обусловленные задачи, в свою очередь, можно разграничить на:
1. Плохо обусловленные с точно заданными исходными данными.
2. Чувствительные к изменению шага дискретизации.
Плохо обусловленные задачи с неточно заданными исходными данными требуют специальных методов решения и в работе не рассматриваются. Классическим примером плохо обусловленной задачи с точно заданными исходными данными является обращение матрицы Гильберта.
Так, для матрицы Гильберта уже порядка 20 относительная погрешность при вычислении коэффициентов обратной матрицы в арифметике с плавающей точкой одинарной точности ( стандарт IEEE 754) превышает 100% и с увеличением порядка исходной матрицы относительная погрешность резко возрастает. Для этой матрицы - нарушается алгебраическое свойство H H = I, где H - матрица Гильберта, - H - обратная матрица, I - единичная матрица Простейшим примером задачи, чувствительной к изменению шага дискретизации является решение задачи Коши методом Эйлера.
Рассмотрим дифференциальное уравнения x'(t)=t, x0=0, t0=0.
Аналитическое решение этого уравнения известно и можно вычислить относительную погрешность решения, полученного численным путем в арифметике с плавающей точкой. В качестве шага интегрирования были q выбраны числа 1 / 2, где - натуральное число. Результаты работы q программы представлены на рисунке 4, где показаны зависимости относительной погрешности решения задачи Коши E от числа. Верхняя q кривая представляет собой зависимость при использовании вычислений с плавающей точкой, нижняя - при использовании вычислений с исключением ошибок округления.
0,000 - вычисления с плавающей 0,00 точкой - вычисления с исключением ошибок округления 0,0000,000,00011 12 13 14 15 16 17 18 19 20 q Рисунок 4 - Зависимости относительной погрешностей от q E,% Из рисунка видно, что при уменьшении шага интегрирования относительная погрешность решения задачи Коши при использовании вычислений с плавающей точкой уменьшается при q < 19. Затем начинается резкий рост погрешности.
Примерами задач с разномасштабными коэффициентами являются эволюция электронно-дырочной плазмы и другие задачи в области ядерной физики, наноэлектроники. Особенностью этих задач является то, что в них используются дифференциальные уравнения в частных производных с сильно отличающимися по величине исходными данными, при решении которых часто происходит резкая потеря точности результатов компьютерных вычислений.Для обеспечения эффективного решения этих задач требуются высокоточные вычисления со свойством слабой зависимости роста времени выполнения арифметических операций от точности. Проведенные исследования показывают, что таким свойством обладают вычисления с отложенным округлением в модулярной системе счисления.
В модулярной системе счисления (МСС) любые целые числа представляются в виде набора остатков от деления на выбранные простые числа (модули) и арифметические операции выполняются не с исходными числами, а с их остатками. Отрицательные целые числа дополняются до модулей и представляются в виде положительных остатков. Достоинством МСС является отсутствие переносов между модулями, что позволяет распараллелить процесс выполнения арифметических операций по всем модулям. Арифметические операции сложения, вычитания и умножения в МСС могут выполняться параллельно и независимо по каждому модулю, благодаря чему достигается ускорение вычислений с многоразрядными числами по сравнению с традиционными вычислениями.
На рисунке 5 показана общая схема высокоточных вычислений в МСС с отложенным округлением. Под вычислениями с отложенным округлением понимаются такие вычисления, при которых округление производится не после каждой арифметической операции, а после группы операций. Число последовательных арифметических операций, выполняемых без округления назовем шагом отложенного округления.
Недостатком МСС является сложность округления чисел в ней. Поэтому уменьшение числа округлений, т.е увеличение шага отложенного округления приводит к ускорению вычислений в МСС. В соответствии с этой схемой вычисления проводятся в два этапа: на первом этапе выполняются q арифметических операций без округления в МСС по всем модулям параллельно и независимо друг от друга ( q - шаг отложенного округления), на втором этапе определяется необходимость округления и если она есть, то результат округляется, если нет - вычисления продолжаются. Округление производится тогда, когда результат выходит за пределы допустимого диапазона, определяемого произведением модулей. Шаг отложенного округления зависит от числа модулей. Поэтому при увеличении числа модулей в МСС расширяется диапазон представления чисел, становится возможным увеличить q и уменьшить число округлений, что приводит к ускорению вычислений в МСС, что подтверждено экспериментально и теоретически обосновано.
Выполнение q Выполнение q арифметических арифметических операций без операций без округления округления Нет Преобразование Проверка Прямое результатов в 1... необходимост...
q 2q...
q+преобразование и позиционную исходных округления систему.........
данных в счисления.........
модулярную Да...
q систему q+1... 2q...
Округление до требуемой точности Рисунок 5. Общая схема высокоточных вычислений в МСС с отложенным округлением Глава 2 Развитие математического аппарата высокоточных вычислений на основе теоретических обобщений в модулярной системе счисления посвящена математическому аппарату высокоточных вычислений, предложены модулярный и модулярно-позиционные форматы представления вещественных и комплексных чисел с фиксированной точкой в МСС, алгоритмы выполнения арифметических операций с числами этого формата, доказаны теоремы о единственности представления результатов арифметических операций в МСС, обобщена арифметика с исключением ошибок округления в МСС над полем комплексных чисел, предложены целочисленный и знаковый инвариант арифметики с плавающей точкой. Перейдем к рассмотрению предложенного в работе формата представления вещественных чисел с фиксированной точкой в МСС.
A Любое вещественное число в формате с фиксированной точкой можно представить в виде:
x x x... x. y y y... y.
1 2 3 n 1 2 3 k f f В другой форме:
K A =, (1) k f где n + k f f K 2 - K - целое число такое, что, n f длина целой части числа в формате с фиксированной точкой, k f длина дробной части числа в формате с фиксированной точкой.
P1, P,..., P Пусть 2 n - модули (последовательность простых чисел) P1 < P <,..., < P P1 > такие, что 2 n,, n - число модулей и P = P1 P2 ... P n их произведение.
Определение 1.
A Модулярным форматом числа назовем представление в виде (рис. 6):
A = [ (, ,..., ,..., ), t ], 1 2 i n где - t = A = K , i Pi Pi i = 1,..., n, 0 t k.
f t Число (после точки) назовем модулярным порядком.
n 1 2 Е t Рисунок 6. Модулярный формат представления чисел с фиксированной точкой В данном случае фиксированная точка в (1) является перемещаемой и ее положение определяется набором арифметических действий решаемой задачи. Сам по себе принцип перемещаемой точки является универсальным с точки зрения нахождения единой формы представления рациональных и комплексно-рациональных чисел. Доказана теорема о единственности представления чисел с фиксированной точкой в модулярном формате.
Теорема Существует одно и только одно представление числа вида K A =, 0 t k t f в модулярном формате:
A = [(, ,..., ,..., ), t ] 1 2 i n n по модулям P1 < P <,..., < P для всех K < Pi 2 n i = Из теоремы единственности следует, что если модули P1, P2,..., Pn n K < P ' P ' приблизительно равны между собой значению, то. В традиционном представлении в МСС при тех же модулях порядок дробей n / (P ') Фарея равен. Т.е. данный формат представления значительно расширяет диапазон представления чисел с фиксированной точкой в МСС.
Правила для выполнения арифметических операций сложения, вычитания и умножения чисел в модулярном формате имеют вид:
Входные данные:
A1 = [ (, ,..., ), t1 ] и A = [( , ,..., ), t ].
1 2 n 2 1 2 n 1. Сложение i = 1,..., n Шаг №1. Вычисляем: + .
i i Р i Шаг №2. Порядок результата равен большему порядку A A чисел и.
1 Шаг №3. Проверка на переполнение и округление.
2. Вычитание i = 1,..., n Шаг №1. Вычисляем: - ,.
i i Pi Шаг №2. Порядок результата равен большему порядку A A чисел и.
1 Шаг №3. Проверка на переполнение и округление.
3. Умножение i = 1,..., n Шаг №1. Вычисляем: ,.
i i Pi A Шаг №2. Порядок результата равен сумме порядков чисел и A.
Шаг №3. Проверка на переполнение и округление.
Что касается деления, то эта операция в МСС является наиболее сложной арифметической операцией. Рассмотрим два случая: деление на константу, деление на произвольное число. Деление на константу всегда можно заменить умножением делимого на обратную к константе, которая заранее вычислена и храниться в памяти. Во втором случае используется один из быстрых алгоритмов деления, основанный на итерационной формуле Ньютона, которая имеет вид:
W = W ( 2 - W B ).
с + 1 с с С помощью данной формулы определяется приближенное значение выражения W =. В предельном случае, когда число итераций B c стремится к бесконечности итерационный процесс сходится к и B А В А деление произвольных чисел на сводится к умножению на.
В Возникает вопрос о выборе начального приближения. Известный способ выбора начального приближения для любого 0, 5 < В < 1 не эффективен, в виду сложности проверки условия 0, 5 < В < 1 в МСС и выполнения операции сдвига. Для решения задачи выбора начального приближения в МСС используем двойное представление в модулярном В формате и в формате с плавающей точкой. Если имеет два В представления в модулярном формате и формате с плавающей точкой m В В, то преобразуя в модулярную систему счисления, можно f f получить искомое начальное приближение W.
Известно, что скорость сходимости метода Ньютона - квадратичная и на каждой итерации число верных цифр увеличивается в два раза.
В Считая, что задана с точностью одной цифры после запятой, f получим, что для вычисления W = с максимальной допустимой B - k f k f абсолютной погрешностью округления 2 достаточно итераций.
Таким образом, для операции деления на произвольное число в МСС потребовалось ввести представление в формате с плавающей точкой, соответственно при вычислениях параллельно с модулярными должны проводиться арифметические операции с плавающей точкой. В процессе этих операций возможен сильный рост разрядностей операндов и в результате ошибка переполнения. Для предотвращения ошибок переполнения при вычислениях с плавающей точкой используем В вложенный формат с плавающей точкой. Любое число во f вложенном формате с плавающей точкой записывается в виде:
p f m , f m - В где мантисса числа, сама записанная в формате с плавающей f f точкой, В р - порядок числа.
f f Представление мантиссы в виде числа с плавающей точкой позволяет расширить диапазон представления чисел во вложенном формате. Арифметические операции с числами во вложенном формате проводятся точно также как и с обычными числами с плавающей точкой.
Определение 2.
A Модулярно-позиционным форматом числа назовем представление в виде:
A = [( , ,..., ,..., ), t, m, p ], 1 2 i n f f где - t = A = K 2, i Pi Pi i = 1,..., n, 0 t k, f m - A мантисса числа во вложенном формате с f плавающей точкой, р - A порядок числа во вложенном формате с f плавающей точкой.
Перейдем к рассмотрению правила выбора модулей для представления результатов арифметических операций в МСС.
[ 0,..., P) Разобьем интервал на 4 части (рисунок 7):
[0,..., P(1/4) ), [P(1/4),..., P(1/2) ), [P(1/2),..., P' ), [P',..., P) (1/4) (1/4) и будем использовать интервалы:
[0,..., P(1/4) ) - для представления положительных чисел, [P',..., P ) (1/4) - для представления отрицательных чисел, [P,..., P(1/2) ) - для представления положительных чисел, требующих (1/4) округления [P,..., P' ) - для представления отрицательных чисел, требующих (1/2) (1/4) округления, где n n -1 (n -1)/ P = Pi, P(1/2) = Pi, P(1/4) = Pi, (2) i=1 i=1 i=P'(1/4) = P - P(1/4).
Определение 3.
Назовем рабочим положительным диапазоном (РПД) [0,..., P(1/4) ) полуинтервал, в котором представляются все положительные результаты арифметических действий в МСС.
A Если результат арифметической операций больше нуля и он [P,..., P(1/2) ) принадлежит, то эта ситуация сигнализирует о том, (1/4) данный результат необходимо округлить и, таким образом, вернуть в РПД.
Определение 4.
Назовем рабочим отрицательным диапазоном (РОД) интервал [P',..., P ) (1/4), в котором представляются все отрицательные результаты арифметических операций в МСС.
A Если результат арифметических операций меньше нуля и [P',..., P' ) принадлежит, то его необходимо округлить и вернуть (1/2) (1/4) в РОД.
РПД РОД - + + - P' P(1/2) P(1/4) (1/4) Р Рисунок 7. Представление чисел с определением области округления в МСС Для обеспечения единственности представления в МСС всех чисел с n фиксированной точкой с длиной целой части и длиной дробной части f k выберем модули МСС таким образом, чтобы выполнялось f неравенство:
( n + k ) f f P > 2.
(3) (1/4) Единственность представления чисел с фиксированной точкой следует из теоремы Рассмотрим способ округления вещественных чисел в МСС.
A = [ (, ,..., ), t ] - результат выполнения одной Пусть 1 2 n из арифметических операций сложения, вычитания и умножения чисел A A и в МСС, который необходимо округлить. Пусть - 1 максимальная допустимая относительная погрешность округления, - k f - максимальная допустимая абсолютная погрешность округления.
K A Пусть дробь, соответствует числу, т.е.
t t - K ( 2 ) mod Pi.
i Тогда t K ( 2 ) mod Pi.
(4) i K Преобразуя в смешанную системе счисления, получим:
n - K = v a, (5) i i i = где v = 1, - основания смешанной i v = Р, 1 < i < n - 1, системы счисления, i j j = a K i - цифры разложения в системе счисления со смешанными основаниями, n - ~ K = v a Пусть значения выражения (5) в формате с i i i = плавающей точкой.
~ K n f Если, то возникает ошибка переполнения t (полученный результат больше максимального представимого числа в ~ K - k f < формате с фиксированной точкой), если, то полученный t результат меньше минимально представимого числа в формате с фиксированной точкой и он заменяется нулем. Далее сравнения K < P(1/4) производится в смешанной системе счисления. Если, то P(1/4) K < P(1/2) A > и его округление не требуется. Если, то A > и его необходимо округлить. В противном случае число A A отрицательное и здесь возможны два варианта: принадлежит РОД или не принадлежит. Проверим принадлежность его РОД. Найдем A A * K * дополнение до модулей ( по формуле (4), ), вычислим K * < P(1/4) K * преобразуем, в смешанную систему счисления. Если A то принадлежит РОД и округление не требуется. Если P(1/4) K * < P(1/2) A, то не принадлежит рабочему отрицательному диапазону и требуется его округление. Округление отрицательного числа производится следующим образом: определяется его дополнение до модулей, далее результат округляется как положительное число и опять находится его дополнение до модулей. В целях ускорения округления ряд K операций могут выполняться параллельно: преобразование чисел, ~ K * в смешанную систему, определение числа K. Так как округление отрицательных чисел сводится к округлению положительных, то правило округления рассмотрим только для положительных чисел.
Для округления положительных чисел в МСС необходимо решить две вспомогательные задачи:
1. Оценить длину мантиссы при выполнении арифметических операций с плавающей точкой, достаточной, чтобы при вычислении ~ ~ K K, относительная погрешность не превышала.
2. Оценить длину мантиссы при выполнении арифметических операций с плавающей точкой, достаточной, чтобы при вычислении - k ~ f K абсолютная погрешность не превышала 2.
Справедлива следующая вспомогательная теорема.
Теорема 2.
~ K Для того чтобы относительная погрешность не превышала - k f и абсолютная погрешность не превышала 2 достаточно выбрать длину мантиссы равной:
MA T n + n - = max log + 1, n + k MA T 2 f f Рассмотрим правило округления.
Правило округления ~ K 1. Вычислим в арифметике с плавающей точкой с длиной мантиссы равной.
MA T n - k f f A 2 А > 2. Проверяем условия,. Если условия выполняются, т.е. предполагается, что не было переполнение и A больше минимального представимого числа, то проверяем А > P( 1 / 4 ). Если оно выполняется, то требуется округлить число ~ K P( 1 / 4 ), A. Сокращаем числитель и знаменатель так, чтобы p - n - k k f f A для этого делим числитель и знаменатель на величину 2, ~ p K где порядок числа k ~ K 3. Представляем в виде целого числа и преобразуем его в МСС.
Далее во второй главе рассмотрено представление комплексных чисел в МСС. Так как в современных ЭВМ арифметические операции с z1 = x1 + i y1, z = x + i y комплексными числами 2 2 2, как правило, выполняются в арифметике с плавающей точкой по формулам:
z1 z2 = (x1 x2 ) + i ( y1 y2 ) z1 z = ( x1 x - y1 y ) + i ( x1 y + y1 x ), 2 2 2 2 z1 x1 x + y1 y y1 x - x1 y 2 2 2 = + i , 2 2 2 z x + y x + y 2 2 2 то все недостатки присущие арифметики с плавающей точкой переносятся и на комплексный случай.
В работе обобщена арифметика с исключением ошибок округления над полем комплексно-рациональных чисел. Введено понятие комплексной дроби Фарея.
Определение 5.
Определим множество комплексных дробей Фарея порядка следующим образом:
z1 x + i y =, x Z, y Z, a Z, b Z, z a + i b 0 x , 0 y , B = 0 a , 0 b , z 0, НОД (z,z ) = 1.
2 1 2 где Z множество целых чисел, > - порядок комплексных дробей Фарея.
Доказана следующая теорема.
Теорема 3.
Если - порядок комплексных дробей Фарея, удовлетворяющий неравенству:
2 p + q - 4 < (6) p + q x = z1 / z и - комплексная дробь Фарея порядка сравнимая с k m = p + i q x целым числом по модулю, то - единственная k m комплексная дробь Фарея порядка, сравнимая с по модулю.
Ниже в таблице 1 приведены комплексные дроби Фарея первого порядка и соответствующие им целочисленные представления в 2 модулярной системе счисления по вещественному модулю p + q = 101, где m = p + iq = 10 + i.
Таблица 1. Комплексные дроби Фарея 1-го порядка и соответствующие им целые числа по модулю m.
В1 Z -1+0i / 1+0i, 1-1+-1i / 1+0i -1+1i / 1+0i 1+0i / 0+1i 0+0i / 1+0i 0+1i / 1+0i В1 Z 1+0i / -1+-1i 1+0i / -1+1i 1+0i / 1+-1i 1+0i / 1+1i 1+-1i / 1+0i 1+1i / 1+0i 1+0i / 1+0i 1 i Приведем примеры. + 1 = =.
- 1 + i - 1 + i i + Пользуясь таблицей 1, имеем: (55 + 1) mod 1 01 = 56 и из таблицы видно, что число 56 соответствует дроби.
1 + i 1 - i - i = 1 - 2 i.
Пользуясь таблицей 1, имеем:
(11 - 91 ) mod 1 01 = (- 80 ) mod 1 01 = 21, но число 21 отсутствует в таблице 1. Произошла ошибка псевдопереполнения (выхода результата за пределы допустимого диапазона, определяемого неравенством (6)), т.к. истинный результат 1 - 2 i комплексная дробь Фарея порядка два, а не один.
A Далее в главе рассматривается представление комплексного числа в формате с фиксированной точкой в виде:
x + i y, (7) A = k f где x + i y целое комплексное число такое, что:
n + k n + k f f f f x Z, y Z, 0 x 2 - 1, 0 y 2 -, n f - целая часть комплексного числа с фиксированной точкой, k f - дробная часть комплексного числа с фиксированной точкой.
Вводится обозначения для комплексных модулей M = p1 + i q1, M = p + i q,..., M = p + i q 1 2 2 2 n n n - последовательности простых целых комплексных чисел, нормы которых возрастают orm ( M ) < orm ( M ) <,..., < orm ( M ) 1 2 n и их произведение равно M = M M ... M = p * + i q * 1 2 n.
Доказана следующая теорема.
Теорема 4.
M = p1 + i q1, M = p2 + i q2,..., M = pn + i qn Если модули 1 2 n удовлетворяют условиям:
( p, q ) = 1,..., ( p, q ) =, 1 1 n n n n p* = Re М > 0 q* = Im М > ( p *, q *) =,, i i i=1 i=1 и выполняются неравенства:
n + k p * q * f f при p * > q *, - 2 n + k q * p * f f при q * > p *, - 2 n + k p * 2 q * f f при q * = p *, = 2 то комплексные числа с фиксированной точкой вида (7) представляются по этим модулям единственным образом.
Для представления комплексных чисел с фиксированной точкой используется такой же как и для вещественных чисел модулярный формат (рис. 6). Соответственно, арифметические операции с такими числами выполняются по тем же правилам, что и с вещественными. Отличаются лишь правила преобразования и округления чисел. Во второй главе работы представлены правила выбора модулей, округления и преобразования комплексных чисел с фиксированной точкой.
Далее в работе рассматриваются недостатки формата с плавающей точкой, связанные с неоднозначным представлением целых, дробных чисел, предложены способы проверки целочисленности и знака значений дробно-рациональных функций в формате с плавающей точкой - целочисленный и знаковый инварианты.
В главе 3 Разработка алгоритмического обеспечения высокоточных вычислений на основе математического аппарата, представленного во второй главе проведена разработка алгоритмического обеспечения высокоточных вычислений, включающего базовые алгоритмы высокоточных вычислений над полем рациональных, комплекснорациональных чисел, служебные алгоритмы округления, проверки переполнения, восстановления числа с фиксированной точкой из модулярной системы счисления, алгоритмы проверки целочисленности и знака значений дробно-рациональных функций в арифметике с плавающей точкой.
При выборе модулей малых по величине возможно ускорение высокоточных вычислений в модулярной арифметике за счет использования л tablе lookup метода, суть которого заключается в том, что в памяти хранятся всевозможные результаты для каждой арифметической операций и результаты этих операций не вычисляются, а извлекаются из памяти. Это дает возможность выполнения в модулярной арифметике всех операций за одинаковое время, что является одним из преимуществ модулярной системы счисления перед другими системами счисления.
Схема алгоритма выполнения арифметических операций: сложения, A, B вычитания и умножения над двумя числами в модулярном формате показана на рисунке 8.
Исходные данные:
1. Числа A1 = [(, ,..., ,..., ), t1 ] 1 2 i n A = [ ( , ,..., ,..., ), t ] заданные в МСС.
2 1 2 i n 2. Модули - P1, P2,..., Pn Выходные данные:
Число A = [ ( , ,..., ,..., ), t ] в МСС равное A3 = A1 * A2, где 3 1 2 i n * = (+,-,).
P1, P,..., P 2 n , ,..., , t1 2 n , ,..., , t 1 2 n i=1,...,n = * i i i P i * = +,* = t = max( t1, t ) 3 t = t1 + t 3 Рисунок 8. Схема алгоритма сложения, вычитания и умножения чисел в модулярном формате Для разработанных алгоритмов высокоточных вычислений исследованы возможности распараллеливания, получена аналитическая оценка шага отложенного округления в зависимости от числа модулей, разрядностей модулей и исходных данных, с которыми проводятся высокоточные вычисления над полем рациональных и комплексно рациональных чисел.
На основе анализа достоинств и недостатков модулярной арифметики даны рекомендации по применению разработанных алгоритмов высокоточных вычислений.
Ускорение высокоточных вычислений при решении вычислительных задач в модулярной системе счисления будет тем выше, чем меньше число операций преобразования результатов из модулярной системы счисления в позиционную и сравнений.
Исходя из этого можно предложить рекомендации по применению высокоточных вычислений в МСС для решения тех вычислительных задач, в которых:
1. Минимальное число преобразований конечного результата из МСС в ПСС. Примеры: вычисление суммы ряда, определителя матрицы, значения некоторой функции и др. Нежелательный пример: нахождение обратной матрицы большой размерности, в ней число преобразуемых величин равно квадрату порядка матрицы.
2. Минимальное число сравнений. Примеры: вычисление прямого и обратного дискретного преобразования Фурье, итерационное решение систем линейных уравнений методом Гаусса-Зейделя, в ней число сравнений определяется числом итераций и зависит только от обусловленности матрицы. Нежелательный пример: задачи, в которых в процессе вычислений используется сортировка результатов по убыванию или по возрастанию и др.
Глава 4 Реализация структурных принципов машинной арифметики посвящена вопросам проектирования структурных схем поддержки высокоточных вычислений на основе разработанных в третьей главе алгоритмов. Показано, что при реализации разработанных алгоритмов на аппаратном уровне обеспечивается наибольшее ускорение высокоточных вычислений. Определены различные уровни аппаратной поддержки высокоточных вычислений: на уровне специализированного вычислительного устройства, модулярного сопроцессора. Вычислены оценки временных затрат основных узлов модулярного сопроцессора в вентильных задержках. Под вентильной задержкой понимают задержку при прохождении сигнала через один логический элемент. Разработана обобщенная структурная схема модулярного сопроцессора для поддержки высокоточных вычислений (рис.9). В целях упрощения структурной схемы некоторые узлы модулярного сопроцессора не приведены. В модулярный сопроцессор входят следующие блоки:
Х блок постоянной памяти;
Х блок общей памяти;
Х группа потоковых вычислительных устройств (ГПВУ1,Е, ГПВУq);
Х блоки округления (БО1,Е, БОq);
Х потоковые преобразователи в МСС (ПП1,Е, ППq);
Х блоки поддержки вычислений с плавающей точкой (БСП1,Е, БСПq);
Х шины данных (ШД1,Е, ШДq );
Х шина команд (ШК).
Рисунок 9. Структурная схема модулярного сопроцессора.
В блоке постоянной памяти сопроцессора содержатся значения модулей и другие константы, необходимые для преобразования и округления чисел. Сопроцессор работает следующим образом. На шину команд поступают команды выполнения арифметических операций для соответствующих групп потоковых вычислительных устройств, в общей памяти хранятся исходные данные (операнды). Каждая ГПВУ функционирует параллельно и независимо друг от друга. Каждое вычислительное устройство ГПВУ выполняет арифметические операции параллельно и независимо по своему модулю. Результаты этих вычислений записываются в общую память или поступают в соответствующие блоки округления БО, или в соответствующие потоковые преобразователи, которые формируют результаты высокоточных вычислений. Блоки поддержки вычислений с плавающей точкой БСП служат для реализации деления в модулярно-позиционном формате, проверки на переполнение, и на необходимость округления.
В модулярном сопроцессоре обеспечивается двухуровневый параллелизм: на уровне алгоритма и на уровне арифметических операций в МСС. При проектировании узлов сопроцессора использовались разрядно-параллельные, конвейерные принципы обработки данных.
Получены 3 патента на структурные схемы узлов сопроцессора:
устройства преобразования и округления чисел в МСС.
Пятая глава Программная реализация библиотечных функций для поддержки высокоточных вычислений посвящена программной реализации высокоточных вычислений. Анализ возможностей программной реализации высокоточных вычислений на кластере и многоядерном процессоре показал, что реализация на процессорах многоядерной архитектуры более эффективна. Каждое ядро многоядерного процессора проводит параллельные и независимые друг от друга вычисления по своему модулю, а при округлении данные со всех ядер передаются одному ядру, производящему округление. Время передачи данных между ядрами на порядки меньше времени передачи между процессорами внутри кластера, поэтому этот вариант обеспечивает более удобную реализацию ряда алгоритмов модулярной арифметики (сложения, вычитания, умножения, округления и др). Для программной реализации разработанных алгоритмов использовались графические ускорители NVIDIA, которые имеют невысокую стоимость и достаточно распространены. Число ядер современных графических ускорителей может достигать 480 и более.
Разработаны ряд библиотечных функций для поддержки высокоточных вычислений в МСС на основе CUDA Runtime API и Visual Studio, включающие в себя:
1. Init - инициализацию библиотеки, выбор модулей;
2. AddRNS ( A, B ) - сложения двух чисел, входные параметры:
два числа, выходные - результат суммирования;
3. SubRNS ( A, B ) - вычитания двух чисел, входные параметры:
два числа, выходные - разность двух чисел;
4. MulRNS ( A, B ) - умножения двух чисел, входные параметры:
два числа, выходные - результат произведения двух чисел.
Функции преобразования чисел:
1. ConvertToRNS ( A, module ; Result ) - преобразование числа А из позиционной системы счисления в МСС по модулю module;
2. ConvertFarea (A) Цпреобразование числа A из МСС в ПСС.
Функция округления числа:
1. Okrug ( A ; Result ) - округление числа А в МСС.
Функция сравнения чисел:
1. Compare (A, B) - сравнение чисел.
Схематично порядок вызова библиотечных функций поддержки высокоточных вычислений представлен на рисунке 10. Здесь в основной программе, исполняемой на основном процессоре CPU осуществляется вызов библиотечных функций высокоточных вычислений, записываются исходные данные в память графического ускорителя GPU NVIDIA и передается ему управление. GPU NVIDIA создает нити, число которых равно числу модулей. Далее каждая нить GPU NVIDIA выполняет преобразование исходных данных по своему модулю и обработку данных.
После завершения обработки GPU NVIDIA возвращает результаты в основную программу и ход работы основной программы продолжается.
Рисунок 10. Порядок вызова библиотечных функций поддержки высокоточных вычислений.
В пятой главе работы порядок вызова библиотечных функций рассматривался на примере определения скалярного произведения двух векторов c числом координат m равным 15000, 10000 и 500. Были получены оценки времени определения скалярного произведения векторов в МСС на 32-х ядерном графическом ускорителе NVIDIA GeForce 9600M GT и при использовании существующей библиотеки высокоточных вычислений MPArith при одинаковой точности. Построен график зависимости коэффициента абсолютного ускорения от длины мантиссы, определяемого по формуле:
T R =, T где T - время вычислений с использованием библиотеки MPArith, T - время вычислений в модулярной арифметике при той же точности.
Ниже на рисунке 11 приведена зависимость коэффициента абсолютного ускорения от длины мантиссы.
4,m=1503,m=1002,R 1,m=300,m=50 200 400 600 800 1000 1200 14Длина мантиссы, бит Рисунок 11. Зависимость коэффициента абсолютного ускорения от длины мантиссы Из графика видно, что при увеличении длины мантиссы возрастает коэффициент абсолютного ускорения. Это объясняется слабой зависимостью в предлагаемой библиотеке времени выполнения арифметических операций от точности и более сильной зависимостью для библиотеки высокоточных вычислений MPArith.
Разработана среда для поддержки высокоточных вычислений. Среда для поддержки высокоточных вычислений (СПВС) может автоматически запускать преобразователи при необходимости округлять результаты в процессе вычислений, освобождая от этого труда программиста. СПВС состоит из нескольких слоев как показано на рис. 12.
Среда поддержки высокоточных вычислений включает в себя:
библиотеку и драйвер для работы с сопроцессором. Приложение на CPU (основном процессоре) вызывает функции библиотеки, библиотека обращается к драйверу сопроцессора. Драйвер работает непосредственно с сопроцессором и запускает соответствующие подпрограммы.
Приложение может обращаться к драйверу напрямую.
Рисунок 12. Среда для поддержки высокоточных вычислений В шестой главе Экспериментальная реализация и оценка эффективности разработанных методов отражены результаты оценки эффективности разработанных методов и средств поддержки высокоточных вычислений по схеме с отложенным округлением.
Исследована аналитически зависимость времени вычислений в МСС по схеме с отложенным округлением на примере выполнения группы арифметических операций и решения системы линейных уравнений методом Гаусса-Зейделя.
Для системы линейных уравнений с 20 неизвестными зависимость времени вычислений в условных тактах от числа модулей представлена на рисунке 13.
Из графика видно, что:
1. Увеличение числа модулей приводит к ускорению вычислений.
2. При решении СЛАУ с большим количеством модулей, время решения при увеличении точности изменяется в меньшей степени, чем при решении СЛАУ с меньшим количеством модулей. Например, при увеличении точности вычислений в 2 и 5 раз общее время решения СЛАУ для 30 модулей увеличивается в 1,6 и 5 раз, а для 1000 модулей в 1,1 и 1,раза.
1400012000100008000одинарная точность двойная точность 6000пятикратная точность 400020000 200 400 600 800 1000 1200 1400 16n Рисунок 13. Зависимость времени вычислений в МСС от числа модулей.
Седьмая глава Применение разработанных методов и средств посвящена вопросам применения разработанных алгоритмов высокоточных вычислений. Ниже приведены некоторые полученные результаты применения высокоточных вычислений в различных областях науки и техники.
1. Геоинформатика.
Задача: определение пересечения двух отрезков в проекции на плоскость XY.
В случае, когда отрезки почти параллельны в арифметике с плавающей точкой происходят ошибки при определении параллельности отрезков, например, для отрезков AB, CD с координатами A,B,C,D соответственно (100,2,100.0001,2.0001,120, 22, 120.0001, 22.0001).
Применение целочисленного инварианта арифметики с плавающей точкой позволило исключить ошибки при определении параллельности отрезков, что подтверждено актом о внедрении в институте проблем геотермии Дагестанского научного центра РАН.
2. Робототехника.
Задача: Анализ многосвязных мехатронных систем высокой размерности прямыми корневыми методами.
Прямые корневые методы анализа многосвязных мехатронных систем высокой размерности основаны на решении полиномиальных Временные затраты в ус. тактах уравнений высокой степени. В случае, когда корни полиномиального уравнения высокой степени кратные или почти кратные (плохо обусловленный полином) точность решения существенным образом зависит от точности вычислений. Численные эксперименты показали, что при нахождении решений плохо обусловленного полинома степени 400 со случайно заданными коэффициентами методом Хичкока происходила сильная потеря точности и дальнейшее увеличение числа итераций не повысило точности решения. Применение высокоточных вычислений позволило получить искомые решения.
3. Теплоэнергетика.
Задача: Решение уравнения теплопроводности вдоль стенок труб с разномасштабными параметрами.
Распространение тепла вдоль стенок труб теплообменных устройств, поверхностей нагрева котлов, и других объектов описывается с помощью нестационарного уравнения теплопроводности.
U x = a , 0 < x < l, t > t t с граничными условиями первого рода:
u (0, t ) = ( t ), t > 0;
u ( l, t ) = ( t ), t > 0, l t = и начальными условиями при :
u ( x,0 ) = ( x ), 0 x l.
Для численного решения данного уравнения используется метод w конечных разностей. Вводится конечно-разностная сетка на h пространственно-временной области:
w = { x = jh, j = 0,1,..., ;
h j k t = k , k = 0,1,..., K }.
с пространственным шагом h = l / и шагом по времени = T / K и исходное уравнение аппроксимируется системой конечноразностных уравнений.
Численные эксперименты показали, что используя абсолютно устойчивую неявную конечно-разностную схему при решении данного уравнения со следующими параметрами:
- 3 a = 0.044, h = 10, = 10, = 1000, произошла резкая потеря точности результатов (относительная погрешность составила 100% при числе итераций равной 5000). Физически эти параметры могут соответствовать случаю, когда ищется распределение температуры магистрального трубопровода длиной 1000 м через каждый метр, каждые - h 10, 3 часа. В этом случае параметр принимает значение а приблизительно сек, = 1000. Применение высокоточных вычислений позволило получить искомые результаты с требуемой точностью.
4. Теория управления.
Задача: Определение управляемости линейных динамических систем.
В соответствии с ранговым критерием Калмана управляемости динамической системы система управляема тогда и только тогда, когда все строки матрицы управляемости линейно независимы.
При вычислении на ЭВМ ранга матрицы большой размерности матрицы или плохо обусловленной матрицы, вследствие ошибок округления нет гарантии получения верного результата. Применение целочисленного инварианта арифметики с плавающей точкой позволило исключить ошибки при определении ранга матрицы и управляемости линейных динамических систем.
5. Физика плазмы.
Задача: Эволюция электронно-дырочной плазмы.
Эволюция электронно-дырочной плазмы описывается системой дифференциальных уравнений в частных производных, в процессе решения которой методом конечных разностей возможна резкая потеря точности из-за разномасштабности начальных приближений (в уравнениях непрерывности, начальные значения концентрации дырок и электронов могут сильно отличаться друг от друга). Применение высокоточных вычислений позволило получить искомое решение системы с требуемой точностью.
В заключении перечислены основные результаты работы, выводы и предложения по дальнейшему направлению исследований в этой области:
1. Определены основные классы вычислительных задач, критичные к точности компьютерных вычислений на ЭВМ на решение которых направлена настоящая работа. Эти классы задач, полностью не исчерпывают все множество возможных задач, критичных к точности компьютерных вычислений. Так как в настоящее время происходит не только расширение существующих, но и образование новых классов задач, критичных к точности компьютерных вычислений. Процессоры современных ЭВМ обеспечивают жестко ограниченную точность вычислений. Если она не достаточна, то используется множество существующих библиотек высокоточных вычислений. Но большинство известных автору таких библиотек или обладают сильной зависимостью времени выполнения арифметических операций от точности и находят применение лишь в частных случаях, когда требования к скорости вычислений не велики.
2. Традиционно модулярная арифметика используется в вычислительной техники для ускорения цифровой обработки сигналов, в нейронных сетях и др. Проведенные теоретические исследования показали принципиальную возможность ускорения высокоточных вычислений и ослабления зависимости времени выполнения арифметических операций от точности в модулярной арифметики, что позволило выделить новое научное направление - теорию модулярных высокоточных вычислений. В рамках этой теории предложены модулярный и модулярно-позиционный форматы представления рациональных и комплексно-рациональных чисел. Доказаны теоремы о единственности результатов арифметических операций с числами этого формата. Получены оценки модулей необходимых для представления чисел в модулярном формате. Предложены алгоритмы выполнения арифметических операций и округления чисел в модулярном формате. Предложена схема организации высокоточных вычислений с отложенным округлением, в соответствии с которой округления производится не после каждой арифметической операции, а после группы. Необходимость в такой схеме организации высокоточных вычислений связана со сложностью округления чисел в модулярной системе счисления. Экспериментально и теоретически подтвержден эффект ослабления зависимости времени выполнения арифметических операций от точности в модулярной арифметике при увеличении числа модулей. В этом заключается основное преимущество высокоточных вычислений в модулярной арифметике.
Практически это дает возможность существенно повысить точность вычислений ценой незначительного увеличения времени выполнения арифметических операций на процессорах с большим числом ядер.
3. Предложены целочисленные инварианты и знаковые инварианты арифметики с плавающей точкой для быстрой проверки знака и целочисленности дробно-рациональных функций. Практически они могут быть использованы и уже используются в геоинформатике (имеется соответствующий акт о внедрении), при решении задачи целочисленного линейного программирования и др.
4. Определенное развитие в диссертационной работе получила теория вычислений с исключением ошибок округления над полем рациональных чисел. Существующие алгоритмы вычислений с исключением ошибок округления обобщены над полем комплекснорациональных чисел. Введено понятие комплексной дроби Фарея.
Доказана теорема о порядке представимых комплексных дробей Фарея по модулю.
5. Разработана библиотека высокоточных вычислений для графического ускорителя. С помощью этой библиотеки на примере решения модельных задач экспериментально подтвержден эффект слабой зависимости времени выполнения арифметических операций от точности и достоверность предложенных автором алгоритмов организации высокоточных вычислений в модулярной арифметике.
Экспериментально установлена зависимость коэффициента абсолютного ускорения, определяемого как отношение времени вычислений в существующей библиотеке MPArith ко времени в предлагаемой, от точности выполнения арифметических операций на примере вычисления скалярного произведения. Эта зависимость показывает устойчивый рост коэффициента абсолютного ускорения с увеличением точности вычислений.
6. На основе разработанных алгоритмов предложены ряд структурных схемы узлов модулярного сопроцессора высокоточных вычислений и его общая схема. По трем из них ( 2 преобразователя, 1 устройство округления ) получены патенты РФ. Разработана программноаппаратная среда поддержки высокоточных вычислений. По сравнению с библиотекой программно-аппаратная среда обеспечивает лучшее ускорение высокоточных вычислений, не требуя установки отдельного графического ускорителя, предоставляет более широкие функциональные возможности.
7. В рамках теории высокоточных модулярных вычислений могут проведены дальнейшие исследования и решены новые задачи :
- поддержка высокоточных вычислений с тригонометрическими, иррациональными числами в модулярной системе счисления.
- разработка эффективных алгоритмов преобразования результатов модулярных вычислений в позиционную систему счисления.
- быстрое округление результатов модулярных вычислений В приложении к диссертации приведены листинги программ:
Преобразование целых комплексных чисел в модулярной системе счисления, Преобразование комплексных дробей Фарея в модулярной системе счисления, Целочисленный инвариант, структурные схемы узлов модулярного сопроцессора для поддержки вычислений с комплексными числами, описание лабораторной работы по теме:
Проблемы организации вычислений, вынесены акты о внедрении.
ОСНОВНЫЕ ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ Статьи в периодических изданиях, рекомендованных ВАК РФ 1. Оцоков Ш.А. Структурная организация нейропроцессора с использованием модели безошибочных вычислений. // Нейрокомпьютеры: разработка и применение, № 12 - 2004.
2. Оцоков Ш.А. Нейронный алгоритм расширения диапазона представления результатов безошибочных вычислений. // Нейрокомпьютеры: разработка и применение, № 12 - 2004.
3. Оцоков Ш.А. Алгоритм ускоренного отображения дробей Фарея в систему остаточных классов. // Вестник Дагестанского научного центра РАН, №19 - 2004, с.40-4. Оцоков Ш.А. Критерий целочисленности результата арифметических операций с плавающей точкой. // Информационные технологии, № 7Ц2007, с. 50-52.
5. Оцоков Ш.А. Возможные приложения арифметики кодов Гензеля. // Вестник МЭИ № 5, 2007 Ч С. 97-1 6. Оцоков Ш.А. Обобщение вычислений над полем комплексных чисел с исключением ошибок округления // Информационные технологии, № 6 - 2009, с. 17-23.
7. Оцоков Ш.А. Применение модулярной арифметики с фиксированной точкой для ослабления влияния ошибок округления компьютерных вычислений. // Информационные технологии, № 12 - 208. Дзегеленок И.И, Оцоков Ш.А. Алгебраизация числовых представлений в обеспечении высокоточных суперком- пьютерных вычислений // Вестник МЭИ №3 - 2010, 107-1Публикации в других изданиях 10. Дзегелёнок И.И, Оцоков Ш.А. Абдулатиф О. А., Ильин П.Е., Ильин И.В. Декомпозиционный подход к осуществлению Grid-технологий.
М., Физматлит, УИнформационная математикаФ №1(5), 2005.
11. Дзегеленок И.И., Мазуренко А.К., Оцоков Ш.А. Подход к численному возпроизведению моделей альтернативной энергетики // Сб. науч. тр.
ВЭИ. - М.: ВЭИ, 2006. - С.107.
12. Д.А.Орлов, Ш.А. Оцоков О возможности применения "безошибочных" вычислений для решения задачи Коши. // Труды международной конференции "Информационные средства и технологии", МФИ - 2006, Т.2., Москва, 2006.
13. Оцоков Ш.А. Метод организации вычислений c исключением ошибок округления в модулярной системе счисления. //Труды всероссийской научно-технической конференции "Микроэлектроника и информатика - 2006", МИЭТ - 2006.
14. Дзегеленок И.И., Оцоков Ш.А. Метод ускорения модулярной арифметики с самоисключением ошибок округления. Сб. научных трудов, посвященный юбилейной международной научнотехнической конференции "50 лет модулярной арифметике", Зеленоград (Россия), 23-25 ноября 2005. - М.:ОАО "Ангстрем", МИЭТ, 2006, с.576-586.
15. Оцоков Ш.А. О возможности обобщения параллельной модулярной арифметики для работы с двоичными дробями.
// Вычислительные сети, теория и практика 2007, Номер 2, ( 11).
16. Оцоков Ш.А. Применение модулярной арифметики для решения непрерывной задачи наименьших квадратов. // Инфокоммуникационные технологии в науке, производстве и образовании: сборник материалов третьей международной научно технической конференции. - Ставрополь, 2008. - С.210-217.
Патенты 17. Патент РФ 2235423. Устройство для преобразования числа из системы остаточных классов в позиционный код// Оцоков Ш.А., Шухман И.М. Опубл. 27.08.2004.
18. Патент РФ 2293437. Устройство для преобразования числа из системы остаточных классов в позиционный код // Оцоков Ш.А., Исмаилов ШМ.А, Мугутдинова Х.М. Опубл. 10.02.2007.
19. Патент РФ 2305861. Устройство для округления числа в системе остаточных классов // Оцоков Ш.А., Мугутдинова Х.М. Опубл.
10.09.2007.
Подписано в печать заказ № тираж печатных листов Типография МЭИ; Красноказарменная,
Авторефераты по всем темам >>
Авторефераты по техническим специальностям