Введение к работе
Актуальность темы. С ростом производительности современных ЭВМ расширяется спектр и размерность решаемых на ЭВМ задач, повышаются требования к точности компьютерных вычислений. Большинство компьютерных вычислений проводятся в арифметике с плавающей точкой с жестко ограниченной длиной мантиссы, что приводит к появлению неустранимых ошибок округления.
Проблема точности компьютерных вычислений особенно остро стоит при решении ряда прикладных задач, таких как, например, жестких задач с разномасштабными коэффициентами в ядерной физике, наноэлектронике, анализе многосвязных мехатронных систем и др.
Один из традиционных способов борьбы с ошибками
округления - применение высокоточных вычислений. В настоящее время существует множество библиотек, поддерживающие высокоточные вычисления: ZREAL (Россия), MPARITH (Германия), GMP (США) и др.
Основной проблемой существующих библиотек высокоточных вычислений, сдерживающей их применение на практике, является сильная зависимость роста времени выполнения арифметических операций от точности вычислений. При малом объеме вычислений это не существенно, но для задач большой размерности использование существующих библиотек высокоточных вычислений приводит к резкому росту времени решения задач.
Многие задачи электротехники, энергетики и др. областей науки и техники требуют вычислений с комплексными числами. При вычислениях с комплексными числами также может происходить резкая потеря точности, т.к. комплексная арифметика на ЭВМ реализуется на основе традиционной арифметики с плавающей точкой и проблема сильной зависимости роста времени выполнения арифметических операций от точности еще в большой степени характерна для вычислений с комплексными числами.
Указанная проблема требует поиска новых способов, связанных с применением нетрадиционных систем счисления и арифметик для представления и обработки чисел.
Одной из таких арифметик является модулярная арифметика. В настоящее время в многочисленных работах модулярная арифметика использовалась как средство повышения быстродействия в цифровой обработке сигналов, криптографии, нейронных сетях и др. областях. Модулярной системе счисления присущи возможность глубокого распараллеливания вычислений, отсутствие информационных обменов в
процессе вычислений. Недостатками этой системы являются сложность сравнения, деления, округления чисел.
Существенный вклад в развитие теории модулярных вычислений внесли в нашей стране работы Акушского И.Я, Юдицкого Д.И, Амербаева В. М, Коляда А.А, Червякова Н.И, Финько О.А. и др, среди зарубежных можно выделить работы М.А. Soderstand, D.D.Miller, G.A. Jullien, M.A. Jenkins, B.J. Leon и др.
Модулярные вычисления развиваются как в теоретическом, так и прикладном направлении.
Исследование модулярной системы счисления показало новую возможность применения модулярной арифметики как средство повышения точности вычислений и ослабления зависимости времени вычислений от точности, что позволяет выделить новое научное направление - теорию модулярных высокоточных вычислений.
Разработка эффективных алгоритмов высокоточных вычислений с рациональными и комплексно- рациональными числами со слабой зависимостью времени вычислений от точности и их аппаратная реализация позволит использовать высокоточные вычисления во многих областях науки и техники.
Таким образом, актуальность эффективных алгоритмов высокоточных вычислений с рациональными и комплексно-рациональными числами со слабой зависимостью роста времени вычислений от точности является несомненной и подтверждается мировой практикой.
Объектом исследования является многоядерные компьютерные системы и их составляющие в виде: сопроцессора и арифметического устройства, обеспечивающих высокоточные вычисления с учетом возможностей практической реализации.
Предметом исследования является организация высокоточных вычислений на основе теоретических обобщений в модулярной системе счисления.
Цель работы состоит в разработке структурно-алгоритмических методов и средств организации вычислений высокой точности с рациональными и комплексно-рациональными числами на основе теоретических обобщений в модулярной системе счисления.
Основными задачами диссертационной работы являются:
1. Типизация вычислительных задач, критичных к точности компьютерных вычислений и их конкретизация в таких областях как: геоинформатика, робототехника, наноэлектроника и др.
-
Поиск целочисленного и знакового инварианта арифметики с плавающей точкой для определения целочисленности и знака значения полиномиального и дробно-рационального выражения.
-
Разработка единого формата представления рациональных и комплексно-рациональных чисел на основе теоретических обобщений в модулярной системе счисления.
-
Разработка алгоритмов высокоточных вычислений со слабой зависимостью роста времени выполнения арифметических операций от точности.
-
Разработка структурных принципов реализации высокоточных вычислений.
-
Анализ эффективности разработанных алгоритмов и структурных схем устройств, реализующих высокоточные вычисления.
-
Подтверждение разработанных методов высокоточных вычислений на примере решения ряда задач: определение управляемости линейных динамических систем, решения уравнения теплопроводности вдоль стенок труб с разномасштабными параметрами и др.
-
Внедрение разработанных программных средств для решения вычислительных задач, критичных к точности компьютерных вычислений в таких областях как: геоинформатика, робототехника, теплоэнергетика и др.
Методы исследования опираются на использовании математического аппарата теории чисел, универсальной алгебры, теории алгоритмов.
Научная новизна диссертационного исследования заключается в
разработке общих алгоритмических и структурных принципов
высокоточных вычислений с рациональными и комплексно-
рациональными числами в модулярной арифметике, отличающейся от ранее известных слабой зависимостью роста времени вычислений от точности при увеличении числа модулей.
На защиту выносятся следующие результаты :
-
Типизация вычислительных задач, требующих применения высокоточных вычислений и критичных к нарушению алгебраических свойств в арифметике с плавающей точкой.
-
Единый модулярный и модулярно-позиционные форматы представления рациональных и комплексно-рациональных чисел в модулярной системе счисления.
1 Пункты 2-5, 8,9 -по специальности 05.13.05, пункты 6,7,10 -по 05.13.15
-
Алгоритмы, реализующие высокоточные вычисления для рациональных и комплексно-рациональных чисел в модулярном формате.
-
Обобщение разработанных алгоритмов вычислений с исключением ошибок для работы с комплексно-рациональными числами.
-
Ускоренные алгоритмы параллельных вычислений с исключением ошибок округления с рациональными числами в модулярной арифметике.
-
Целочисленный инвариант, позволяющий определить целочисленность значения полиномиального или дробно-рационального выражения в арифметике с плавающей точкой.
-
Знаковый инвариант, позволяющий определить знак значения полиномиального или дробно-рационального выражения в арифметике с плавающей точкой.
-
Структурные принципы организации высокоточных вычислений на основе модулярной арифметики.
-
Теоретическая оценка ускорения высокоточных модулярных вычислений при увеличении числа модулей.
-
Экспериментальная оценка быстродействия выполнения арифметических операций в модулярной системе счисления на многоядерном графическом ускорителе
Практическая ценность работы
-
Определена возможность создания сопроцессора высокоточных вычислений, что подтверждено тремя патентами на узлы сопроцессора (устройства преобразования и округления в модулярной системе счисления).
-
Разработана библиотека, которая может найти применение при:
проведении высокоточных вычислений с дробными и комплексными числами в таких областях как: электротехника, энергетика и др.;
исключении ошибок, связанных с неоднозначным представлением целых чисел и потерей знака в арифметике с плавающей точкой при вычислении значений дробно-рациональных функций;
исключении потенциально возможной резкой потери точности при решении задач с разномасштабными величинами.
Результаты работы внедрены в институте системного анализа РАН, в учебном процессе в Московском энергетическом институте (ТУ), в НПО «Энергонаука», а также нашли применение в Межрегиональной распределительной сетевой компании Северного Кавказа, институте
2Пункт 1 -по специальности 05.13.05, пункт 2 -по 05.13.15
проблем геотермии Дагестанского научного центра РАН, что подтверждено соответствующими актами о внедрении.
Диссертационная работа выполнена при поддержке
Гранта Президента РФ для молодых кандидатов наук МК-65190.2010.9
Государственного контракта № 02.442.11.7546 по приоритетным направлениям, выполняемых в рамках программного мероприятия 1.9 "Проведение молодыми учеными научных исследований по приоритетным направлениям науки, высоких технологий и образования" федеральной целевой научно-технической программы "Исследования и разработки по приоритетным направлениям развития науки и техники" на 2002-2006 годы.
Гранта НШ-7239.2010.9 "Планирование масштабных вычислений и управление ресурсами распределенных вычислительных сред". Совет по грантам Президента Российской Федерации на право получения средств для государственной поддержки ведущих научных школ Российской Федерации.
Достоверность основных результатов подтверждается
следующим:
корректным использованием математического аппарата теории чисел, универсальной алгебры;
соответствием основных теоретических положений результатам выполненных экспериментов на многоядерных системах;
Апробация работы. Основные результаты работы докладывались и обсуждались на
Юбилейной международной научной конференции "50 лет модулярной арифметике" (МИЭТ, Зеленоград, 2005 г.)
Международной конференции "Информационные средства и технологии", (МФИ, Москва, 2006 г.)
Всероссийской научно-технической конференции "Микроэлектроника и информатика (МИЭТ, Зеленоград, 2006 г.)
Международной конференции «Параллельные вычисления и задачи управления» (РАСО 2006, г. Москва, 2006 г.)
Международной научно-технической конференции «Инфокоммуникационные технологии в науке, производстве и образовании (г. Кисловодск, 2008 г.)
Международной научной конференции «Параллельная компьютерная алгебра» (Parallel Computer Algebra 2010, г. Тамбов, 2010 г.)
Публикации. Опубликовано 27 печатных работ, в том числе 18 работ при подготовке данной диссертационной работы, 12 статей, из них 8
в журналах, одобренных ВАК, 6 тезисов докладов. Получены 3 патента на изобретения в области вычислительной техники.
Структура и объем диссертации. Диссертация состоит из введения, семи глав, заключения, списка литературы из 126 наименований и приложения и изложено на 287 страницах машинописного текста, содержит 72 рисунка и 13 таблиц.
