Структурно-алгоритмические методы организации высокоточных вычислений на основе теоретических обобщений в модулярной системе счисления тема диссертации и автореферата по ВАК РФ 05.13.05, доктор технических наук Оцоков, Шамиль Алиевич

• Оцоков, Шамиль Алиевич
• доктор технических наук
• 2010

Оглавление диссертации доктор технических наук Оцоков, Шамиль Алиевич

Введение

ОГЛАВЛЕНИЕ

ГЛАВА 1. ОРГАНИЗАЦИЯ ВЫСОКОТОЧНЫХ ВЫЧИСЛЕНИЙ КАК НАПРАВЛЕНИЕ РАЗВИТИЯ

КОМПЬЮТЕРНЫХ СИСТЕМ.

1.1. Проблема организации высокоточных вычислений.

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

1.3. Состояние работ в области осуществления высокоточных вычислений.

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

1.5. Цель и задачи диссертационного исследования.

Выводы по главе 1.

ГЛАВА 2. РАЗВИТИЕ МАТЕМАТИЧЕСКОГО АППАРАТА ВЫСОКОТОЧНЫХ ВЫЧИСЛЕНИЙ НА ОСНОВЕ ТЕОРЕТИЧЕСКИХ ОБОБЩЕНИЙ В МОДУЛЯРНОЙ СИСТЕМЕ СЧИСЛЕНИЯ.

2.1. Решение задачи о выборе модулей для реализации арифметики с фиксированной точкой.

2.2. Поиск новых инвариантных свойств арифметики с плавающей точкой.

2.2.1. Целочисленный инвариант арифметики с плавающей точкой.

2.2.2. Знаковый инвариант арифметики с плавающей точкой.

2.3. Усовершенствование многомодульной арифметики с исключением ошибок округления с рациональными числами

2.4. Обобщение одномодульной арифметики с исключением ошибок округления для работы с комплексными рациональными числами.

2.5. Решение задачи о выборе модулей для реализации комплексной арифметики с фиксированной точкой.

2.6. Сводная таблица результатов и структурно-алгоритмические принципы обеспечения высокоточных вычислений.

Введение диссертации (часть автореферата) на тему «Структурно-алгоритмические методы организации высокоточных вычислений на основе теоретических обобщений в модулярной системе счисления»

Развитие современных супер-ЭВМ происходит за счет использования новых архитектурных решений и усовершенствования элементной базы. Тенденцией является создание процессоров» с многоядерной архитектурой. Увеличение количества ядер в процессоре повышает производительность, снижает стоимость и энергопотребление супер-ЭВМ. С ростом производительности супер-ЭВМ расширяется спектр решаемых задач и их размерность, повышаются требования к точности компьютерных вычислений. В связи с этим проблему повышения производительности ЭВМ необходимо решать в тесной взаимосвязи с задачей повышения точности вычислений. Большинство компьютерных вычислений проводятся в арифметике с плавающей точкой, в которой неизбежны ошибки округления. Известны случаи, когда ошибки округления приводили к катастрофам и авариям с многомиллиардными убытками и человеческими жертвами, например, сбой в работе комплекса Patriot, предназначенного для защиты от самолетов, крылатых ракет и баллистических ракет ближнего радиуса действия, состоящей на вооружении армии США. Сбой в системе Patriot 25 февраля 1991 года помешал перехватить иракскую ракету, в результате, ракета достигла цели, погибли 28 американских солдат и еще около 100 человек получили ранения. Причиной сбоя стали ошибки округления, которые привели к некорректному расчету местонахождения приближающейся ракеты [18]. Из-за ошибок округления для арифметических операций с плавающей точкой не выполняются законы алгебры (коммутативности, дистрибутивности), например, х не равно (л: + х) - х [1]. Нарушение алгебраических свойств в арифметике с плавающей точкой приводит к появлению вычислительных аномалий [12,81,90,83]. Программисты должны учитывать особенности арифметики с плавающей точкой, составляя корректные с вычислительной точки зрения программы, в которых нет вычислительных аномалий. Существуют правила для программистов по составлению «вычислительно-корректных» программ, таких как, например: при суммировании массива чисел с плавающей точкой, для уменьшения роста ошибок округления, необходимо предварительно сортировать массив по возрастанию и начать суммирование с меньших чисел [35]. Однако, они-не всегда гарантируют обнаружение в расчетной программе скрытых вычислительных аномалий. Для обнаружения вычислительных аномалий необходим анализ ошибок округления. Существует множество работ, посвященных анализу ошибок округления для типовых задач линейной алгебры, таких как, решение систем линейных уравнений и др.[10,11,29,56,60 ]. Для других задач провести такой анализ очень сложно и требуются специальные знания в этой области. Простейший способ, который обнаруживает некоторые вычислительные аномалии: решение задачи с другим режимом округления в арифметике с плавающей точкой или с большей точностью вычислений и определение в программе сильно отличающихся друг от друга результатов, там возможны вычислительные аномалии [57,81,80]. Другой более надежный способ -использование интервальных или достоверных вычислений [33 ]. С помощью интервальной арифметики можно, получить конечный результат в виде некоторого интервала, который гарантированно содержит в себе истинный искомый результат. Главный недостаток интервальной арифметики - это расширение интервалов в процессе выполнения арифметических операций и потеря информативности результатов [33] . В первой главе приводится пример, когда полученный с помощью интервальной арифметики интервал, очень широкий и никакой полезной информации о точности не дает. Интервальная арифметика не всегда может помочь, в каждом случае требуется анализ целесообразности ее применения.

Один из традиционных способов борьбы с вычислительными аномалиями связан с применением высокоточных вычислений или с преобразованием расчетных формул и вычислительных алгоритмов тогда, когда это возможно сделать. Под высокоточными вычислениями понимаются вычисления, которые имеют точность более высокую, чем поддерживаемую современными ЭВМ. В настоящее время существует множество библиотек высокоточных вычислений, таких как, ZREAL, MPARITH, GMP и др. [76,77,78, 79,107,108,109,84-88 ]

Основной проблемой суще ствую щих библиотек высокоточных вычислений, сдерживающей их применение на практике, является сильная зависимость времени выполнения арифметических операций от точности вычислений. При малом объеме вычислений это не существенно, но для задач большой размерности использование высокоточных вычислений приводит к катастрофическому росту времени решения задач [68,89,102].

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

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

Указанная проблема требует поиска новых алгоритмических способов, связанных с применением нетрадиционных методов и систем счисления для представления и обработки чисел [ 69,70,72,91,101,106,115 ].

В настоящее время в многочисленных работах модулярная арифметика использовалась как средство повышения быстродействия в цифровой обработке сигналов, криптографии, нейронных сетях и др. областях [41,43].

Существенный вклад в развитие теории модулярных вычислений внесли в нашей стране работы, Акушского И.Я, Юдицкого Д.И, Амербаева В. М, Коляда А.А, Червякова Н.И, Финько O.A. и др [ 1,2,31,32,54,61 ].

Исследование модулярной системы счисления показало новую возможность применения модулярной арифметики как средство повышения, точности вычислений и ослабления зависимости времени вычислений от точности, что позволяет выделить новое научное направление - теорию модулярных высокоточных вычислений [42,46,47,48,49 ].

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

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

ЦЕЛЬ ДИССЕРТАЦИОННОЙ РАБОТЫ состоит в разработке структурно-алгоритмических методов и средств организации вычислений высокой точности с рациональными и комплексно-рациональными числами на основе их теоретических обобщений в модулярной системе счисления. ЗАДАЧИ ИССЛЕДОВАНИЯ типизация вычислительных задач требующих применения высокоточных вычислений

- поиск инвариантных свойств арифметики с плавающей точкой.

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

- разработка алгоритмов высокоточных вычислений со слабой зависимостью времени выполнения арифметических операций от точности

- разработка структурных методов организации высокоточных вычислений

- анализ эффективности разработанных алгоритмов и структурных схем устройств, реализующих высокоточные вычисления

ПРЕДМЕТОМ ИССЛЕДОВАНИЯ является организация высокоточных вычислений на основе обобщений в модулярной системе счисления.

ОБЪЕКТОМ ИССЛЕДОВАНИЯ являются многоядерные компьютерные системы и их составляющие в виде: сопроцессора и арифметического устройства, обеспечивающих высокоточные вычисления.

МЕТОДЫ ИССЛЕДОВАНИЯ опираются на использовании математического аппарата теории чисел, алгебры, теории алгоритмов. НАУЧНАЯ НОВИЗНА данного диссертационного исследования заключается в разработке общих алгоритмических и структурных методов высокоточных вычислений с рациональными и комплексно-рациональными числами» в модулярной арифметике, отличающихся от ранее известных слабой зависимостью времени вычислений от точности при увеличении числа модулей.

На защиту выносятся следующие результаты:

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

- Единый модулярный и модулярно-позиционные форматы для представления рациональных и комплексно-рациональных чисел. Общие алгоритмические принципы высокоточных вычислений для рациональных и комплексно-рациональных чисел в модулярном формате.

- Обобщение алгоритмов вычислений с исключением ошибок над полем комплексно-рациональных чисел.

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

- Целочисленный инвариант арифметики с плавающей точкой:

- Знаковый инвариант арифметики с плавающей точкой.

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

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

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

ПРАКТИЧЕСКАЯ ЦЕННОСТЬ Разработанные методы и программные средства позволяют:

- ускорить высокоточные вычисления за счет их распараллеливания;

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

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

- исключить возможную резкую потерю точности при решении задач с разномасштабными величинами.

Результаты работы внедрены в учебный процесс в Московском энергетическом институте (ТУ), в Московском институте радиотехники, электроники и автоматики, а также нашли применение в Межрегиональной распределительной сетевой компании Северного Кавказа, институте проблем геотермии Дагестанского научного центра РАН, что подтверждено соответствующими актами о внедрении.

АПРОБАЦИЯ РАБОТЫ.

Основные результаты работы докладывались и обсуждались на

- Юбилейной международной научной конференции "50 лет модулярной арифметике" (МИЭТ, Зеленоград, 2005 г.)

- Международной конференции "Информационные средства и технологии", (МФИ, Москва, 2006 г.)

- Всероссийской научно-технической конференции "Микроэлектроника и информатика (МИЭТ, Зеленоград, 2006 г.)

- Международной конференции «Параллельные вычисления и задачи управления» (РАСО 2006, г. Москва, 2006 г.)

- Международной научно-технической конференции «Инфокоммуникационные технологии в науке, производстве и образовании (г. Кисловодск, 2008 г.)

ПУБЛИКАЦИИ. По материалам диссертационной работы опубликовано 18 научных трудов, в том числе 12 статей, из них 8 в. журналах, одобренных ВАК, 6 тезисов докладов: Получены 3 патента на изобретения в области вычислительной техники.

СТРУКТУРА И ОБЪЕМ ДИССЕРТАЦИИ. Диссертационная работа состоит из введения, 7 глав, заключения, списка литературы и приложения. Она изложена на . страницах основного машинописного текста, содержит . рисунка, . таблиц, включает библиографию из . наименований. Общий объем диссертации составляет . страниц.

Заключение диссертации по теме «Элементы и устройства вычислительной техники и систем управления», Оцоков, Шамиль Алиевич

Выводы по главе 7

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

2. Универсальность технологии высокоточных вычислений в модулярной арифметике достигается тем, что: a. арифметические операции с числами различной природы ( целые, рациональные, коплексно-рациональные) выполняются по одним и тем же правилам; b. отсутствует недостаток формата с плавающей точкой, связанный с неравномерным распределением чисел внутри диапазона.

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

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

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

ЗАКЛЮЧЕНИЕ

В настоящей работе получены следующие основные результаты.

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

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

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

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

4. Определенное развитие в диссертационной работе получила теория вычислеиий с исключением ошибок округления над полем рациональных чисел. Существующие алгоритмы вычислений с исключением ошибок округления обобщены над полем комплексно-рациональных чисел. Введено понятие комплексной дроби Фарея. Доказана теорема о порядке представимых комплексных дробей Фарея по модулю.

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

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

7. В рамках теории высокоточных модулярных вычислений могут проведены дальнейшие исследования и решены новые задачи :

- поддержка высокоточных вычислений с тригонометрическими, иррациональными числами в модулярной системе счисления.

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

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

В заключении считаю своим приятным долгом выразить благодарность своему научному консультанту И.И. Дзегеленку за большую помощь в написании диссертации. Выражаю также признательность Д.А.Орлову и другим сотрудникам научной группы автора за ценные советы и замечания по работе. гч^,

Список литературы диссертационного исследования доктор технических наук Оцоков, Шамиль Алиевич, 2010 год

1. Амербаев В.М. Теоретические основы машинной арифметики.- Алма-Ата: Наука, 1986,- 224 с.

2. Акушский Н.Я, Юдицкий Д.И. Машинная арифметика в остаточных классах, М. «Сов. радио », 1968. 439 с.

3. Аль Массри. М.И. Разрядно-параллельные процессоры обработки вещественных чисел в непозиционных системах счисления. Дисс. на соиск. уч. степ, к.т.н. Л.: ЛЭТИ, 1993,- 208 с.

4. Амосов A.A., Дубинский Ю.А., Копченова Н.В. Вычислительные методы для инженеров. М.: «Высшая школа», 1994. — 544 с.

5. Акритас А. Основы компьютерной алгебры с приложениями. М.: Мир,1994. 543 с.

6. Барабанов И.Н. Спутниковые навигационные системы GPS и GLONASS. http://www.intuit.ru/video/7/

7. Воеводин В.В. Математические основы параллельных вычислений.www.parallel.ru/info/voevodin.doc.

8. Виноградов И.М. Основы теории чисел. М.: «Наука», 1972. - 456 с.

9. Воеводин В.В, Воеводин Вл.В. Параллельные вычисления. СПб.: БХВ-Петербург, 2002. - 608 с.

10. Ю.Воеводин В.В. Вычислительные основы линейной алгебры. М.: «Наука», 1977. -303 с.

11. Воеводин В.В. Линейная алгебра. М.: «Наука», 1980. -400 с.

12. Воеводин В.В. Математические модели и методы в параллельных процессах. М.: «Наука», 1986. - 296 с.

13. Герасименко А.А, Федин В.Т. Передача и распределение электрической энергии. Ростов- н./Д.: Феникс; Красноярск: Издательские проекты, 2006. - 720 с.

14. Грегори Р., Кришнамурти Е. Безошибочные вычисления. Методы и приложения. М.: Мир, 1988. 207 с.

15. Грэхем P, Кнут Д, Паташник О. Конкретная математика. Основание информатики: Пер. с англ. М.: «Мир», 1998. - 703 с.

16. Григоренко В.П. Об одном методе решения нелинейных краевых задач, описывающих распределение неосновных носителей в базе полупроводниковой структуры // ВМиМФ, 1975, с.923-930.

17. Дискретное преобразование Фурье — Википедия.ru. wikipedia. org/. ./ДискретноепреобразованиеФурье.

18. Живич М., Каннингэм Р. Истинная цепа программных ошибок // Открытые системы. 2009.ЖЗ.

19. Дмитрий Чеканов nVidia CUDA: вычисления на видеокарте или смерть CPU?. Tom's Hardware, www.thg.ru/graphic/nvidiacuda/nvidiacuda01.html

20. Дзегелёнок И.И, Оцоков Щ.А. Подход к решению проблемы безошибочных вычислений с использованием ускоренного алгоритма отображения дробей Фарея. // Труды научной конференции, посвященной 75-летию со дня рождения академика В.А.Мельникова. РАН. М. 2004.

21. Дзегелёнок И.И. , Оцоков Ш.А. Экспериментальное исследование модели безошибочных вычислений на ПМК-сети КУРС 2000 // Сб. трудов международной научной конференции «Информационные средства и технологии» М.:МЭИ (ТУ), 2003.- С. 103-106.

22. Дзегелёнок И.И, Оцоков Ш.А. Абдулатиф О. А., Ильин П.Е., Ильин И.В. Декомпозиционный подход к осуществлению Grid-технологий. М., Физматлит, "Информационная математика" №1(5), 2005.

23. Дзегеленок И.И., Мазуренко A.K:, Оцоков Ш.А. Подход к численному воспроизведению моделей альтернативной энергетики. // Сб. научных трудов ВЭИ, М., 2006.

24. Ильин В.П. Линейная алгебра: от Гаусса до суперкомпьютеров. http://nature.web.ru/db/msg.html?mid=l 178356&uri=page2.html

25. Ирхин В.П. Теоретическое обобщение и разработка методов построения пепозиционных модулярных спецпроцессоров: Диссерт. на соиск. учен, степени д.т.н. / Воронеж, 1999.

26. Мисриханов М.Ш. Инвариантное управление динамическими системами. Алгебраический подход. М:. Энергоатомиздат, 2003.

27. Михелович Ш.Х. Теория чисел. М. «Высшая школа», 1962. 259 с.

28. Михлин С.Г. Некоторые вопросы теории погрешностей. Л.: Издательство Ленинградского университета. 1988. - 333 с.

29. Кобзаренко Д.Н., Аскеров С.Я. Внутреннее отсечение триангуляционного объекта, проецируемого на плоскость XY. // Геоинформационные технологии, №4 2008.

30. Коляда A.A. Модульные структуры конвейерной обработки числовой информации. Минск: Университетское, 1990.- 331 с.

31. Коляда A.A. Модулярные структуры конвейерной экспресс обработки цифровой информации в измерительно-вычислительных системах физического эксперимента. / Диссерт. на соиск. учен, степени д.т.н. — Минск : 1991.

32. Кулиш У., Рац Д., Хаммер Р., Xoicc М. Достоверные вычисления и их компьютерная реализация. РХД., 2005. 450 с.

33. Литвинов ГЛ., Родионов А.Я., Чуркин A.B. Приближенная рациональная арифметика с контролируемыми ошибками округления// Вычислительные технологии, т.6, №5 2001.

34. Мак-кракен Д., Дорн У. Численные методы и программирование на фортране. М.: Мир, 1977, 584 с.

35. Неочевидные особенности вещественных чисел.www.delphi1cingdoni.com/asp/viewitem.asp?catalogid::=374

36. Нуссбаумер Г. Быстрое преобразование Фурье и алгоритмы вычисления сверток. М.: РАДИО И СВЯЗЬ, 1985

37. Орлов ДА., Оцоков Ш.А. О возможности применения «безошибочных» вычислений для решения задачи Коши // Сб. трудов международной научной конференции "Информационные средства и технологии" М.:МЭИ (ТУ), 2006. 207-210.

38. Оцоков Ш.А. Критерий целочисленности результата арифметических операций с плавающей точкой. // Информационные технологии7.2007, с. 50-52.

39. Оцоков Ш.А. Нейронный алгоритм расширения диапазона представления результатов безошибочных вычислений. // Нейрокомпьютеры: разработка и применение, № 12 2004.

40. Оцоков Ш.А. О возможности обобщения параллельной модулярной арифметики для работы с двоичными дробями. // Вычислительные сети, теория и практика 2007, Номер 2, ( 11).

41. Оцоков Ш.А. Структурная организация нейропроцессора с использованием модели безошибочных вычислений. // Нейрокомпьютеры: разработка и примеиение, № 12 2004.

42. Оцоков Ш.А. Алгоритм ускоренного отображения дробей Фарея в систему остаточных классов. // Вестник Дагестанского научного центра РАН, №19-2004, с.40-43

43. Оцоков Ш.А. Обобщение вычислений над полем комплексных чисел сисключением ошибок округления // Информационные технологии, № 6-2009, с. 17-23.

44. Оцоков Ш.А. Применение модулярной арифметики с фиксированной точкой для ослабления влияния ошибок округления компьютерных вычислений. // Информационные технологии, № 12 2009/

45. Оцоков Щ.А., Мугутдинова Х.М. Устройство для округления числа в системе остаточных классов. Патент РФ № 2305861., опубл. 10.09.2007.

46. Оцоков Ш.А., Шухман И.М. Устройство для преобразования числа из системы остаточных классов в позиционный код. Патент РФ № 2235423., опубл. 27.08.2004.

47. Ортега Дж., Пул У. Введение в численные методы решения дифференциальных уравнений. М. 1986. -288 с.

48. Петров Ю.П. Как получать надежные решения систем уравнений. СПб.: BHV-СПб, 2009.- 176 с.

49. Пи кипа Г. А. Математические модели технологических объектов. М.: Изд. дом МЭИ , 2008

50. Поспелов Д. А. Арифметические основы вычислительных машин дискретного действия . М.: Высшая школа, I960;

51. Сахшок П.А., Червяков Н.И., Шапошников А.В. Модулярные вычислительные структуры пейропроцессорных систем.: Учебное55. пособие М.: Физматлит, 2003

52. Стренг Г. Линейная алгебра и ее применения. Мир, 1980.

53. How Futile are Mindless Assessments of Roundoff in Floating-Point Computation?", William Kahan.ttp://www.cs.berkeley.edu/~wkahan/Mindless.pdf

54. Тихонов A.Ii. Арсенин В .Я. Методы решения некорректных задач. — М.: Наука, 1979.г1У. . --—

55. Тягунов Олег Аркадьевич Развитие технологий анализа,многокритериальной оптимизации и моделирования многосвязных мехатронных систем управления. Дисс. на соиск. уч. степ. д.т.н.М: МИРЭА, 2009

56. Уоткинс Д. Основы матричных вычислений. М.: Бином, 2006, 660 с.

57. Финько О.А. Модулярная арифметика параллельных логических вычислений: Монография / Под ред. В.Д. Малюгина. — М.: ИПУ РАН, 2003. —224 с.

58. Форсайт Дж., Молер К. Численное решение систем линейных алгебраических уравнений. М.: Мир, 1969

59. Хамахер К., Вранешич 3., Заки С. Организация ЭВМ. 5-е изд. Спб.: Питер; Киев: Издательская группа BHV, 2003. 848 с.

60. Чарыков, IT. А. Учебное пособие по курсу "Физика полупроводниковых приборов и компонент интегральных схем": Физические явления в р-п-переходах / Н. А. 41 .Чарыков, Ред. К. В. Шалимова, Моск. энерг. ин-т (МЭИ) . М. : Изд-во МЭИ, 1982 . - 80 с.

61. Ясницкий JI.H. Введение в искусственный интеллект. М.: Изд. центр «Академия», 2005.

62. Яненко Н.Н. Введение в разностные методы математической физики. 4.1,2. Новосиб. гос. ун-т, 1968

63. Яценков B.C. Основы спутниковой навигации. Системы GPS NAVSTAR и ГЛОНАСС. М.: Горячая Линия Телеком, 2005 г. - 272 с.

64. A.M. Frolov and D.Ii. Bailey, "Highly Accurate Evaluation of the Few-Body Auxiliary Functions and Four-Body Integrals," J. Physics B, vol. 36, no. 9, 2003, pp. 1857-1867.

65. A. Edalat, R. Heckmann, Computing with real numbers: (i) LFT approach to real computation, (ii) Domain-theoretic model of computational geometry, Lecture Notes in Computer Science, vol.2395, Springer, 2002, pp.193-267.

66. A. Edalat and F. Rico.Two Algorithms for Root Finding in Exact real Arithmetic.Third Real Numbers and Computers Conference, 27-44, (1998).

67. Blanck, J.:Exact real arithmetic systems: Results of competition, Computability and Complexity in Analysis, Lecture Notes in Computer Science, Vol. 2064, (2001) 390-394

68. Brabec, T., Lorencz, R.; Arithmetic Unit based on Continued Fractions, submitted for review to ECI 2006. http://service.felk.cvut.cz/anc/brabectl/pub/eci06.pdf

69. Blum L. , Cucker F. , Shub M. and Smale S. Complexity and real computation, New York: Springer-Verlag. (1998).

70. Blum L. , Shub M. and Smale S. On a theory of computation and complexity over the real numbers. Amer. Math. Soc. Bull. 21:1-46 (1989).

71. Boehm H and Cartwright R. Exact real arithmetic, formulating real numbers as functions. In David A. Turner, editor, Research Topics in Functional Programming, chapter 3,Addison-Wesley, 1990, pages 43-64.

72. Boehm H. J., Cartwright R. , O'Donnel M. J. and Riggle M. Exact real arithmetic, a case study in higher order programming. Proc. of the ACM conference on Lisp and functional programming, 1986.August, P. 162-173.

73. Chang P. R., Lee C. S. G. Residue arithmetic VLSI arra. architecture f°r manipulator pseudo-inverse Jacobian computation Proc. IEEE Int. Conf. Rob-and Autom. (Philadelphia. Pa, 24-29 Apr. 1988). 1988. Vol. 1. Washington, D. C. P. 297-302.

74. David H. Bailey, Yozo Hida, Xiaoye S. Li and Brandon Thompson, "ARPREC: An Arbitrary Precision Computation Package," technical report LBNL-53651, software and documentation available at http://crdl.bl.gov/~dhbailey/mpdist.

75. D.M. Priest: Algorithms for Arbitrary Precision Floating Point Arithmetic. Lrx Proceedings of the J 0th Symposium on Computer Arithmetic, 1991.

76. D. H. Bailey: High-precision Floating-point Arithmetic in Scientific Computation. Computing in Science and Engineering, May-June 2005.

77. David H. Bailey. Resolving Numerical Anomalies in Scientific1.wrence Berkeley National Laboratory, 2008.

78. David H. Bailey. High-Precision Computation and Mathematical Physics. Lawrence Berkeley National Laboratory, 2009.

79. David Goldberg «What Every Computer Scientist Should Know About Floating-Point Arithmetic» ACM Computing Surveys (CSUR), v. 23 , Issue 1 (March 1991), pp. 5-48

80. D.Ii. Bailey, R. Krasny, and R. Pelz, "Multiple Precision, Multiple Processor Vortex Sheet Roll-Up Computation," Proc. 6th SIAM Conf. Parallel Processing for Scientific Computing, SIAM Press, 1993, pp. 52-56.

81. D.H. Bailey, P.B. Borwein, and S. Plouffe, "On the Rapid Computation of Various Polylogarithmic Constants," Mathematics of Computation, vol. 66, no. 218, 1997, pp. 903-913.

82. David FI. Bailey, Jonathan M. Borwein and Richard Crandall, "Integrals of the Ising Class," 2006, available at http://crd.lbl.gov/~dhbailey/dhbpapers/ising.pdf.

83. D.H. Bailey and S. Robins, "Highly Parallel, High-Precision Numerical Integration," Computational Research Division, Berkeley

84. Lab Computing Sciences, 2004; http://crd.lbl.gov/~dhbailey/ dhbpapers/quadparallel.pdf.

85. Escardo M.H. PCF extended with real numbers: A domain-theoretic approach to higher-order exact real number computation. Technical Report ECS-LFCS-97-374, Department of Computer Scicnce, University of Edinburgh, December 1997.

86. Floating Point Arithmetic," Proceedings of ARITIT-15, IEEE Computer Society, 2001.

87. Froment A. Error Free Computation: A Direct Method to Convert Finite-Segment p-Adic Numbers into Rational Numbers // IEEE Trans, on comput., 1983, Vol. C-32, N 4, P 337-343.

88. Gregory R. T. A. method for and an application of error-free com/p

89. Proceedings of the AFCET Symposium «Mathematics for CZ Science». Paris, 152-158, 1982.

90. Gregory R. T. Error-free computation with rational numbers. BIT, 2 3 194-202.

91. Gregory R. T. Exact computation with order-N Farey fractions. CZ

92. Science and Statistics: Proceedings of the 15th Symposium on the Int«e E. Gentle Editor, North Holland, Amsterdam, 1983.

93. Gregory R. T. Residue arithmetic with rational operands. ProceecL Symposium on Computer Arithmetic. IEEE Computer Society, A Michigan, 144-145, 1981a.

94. Gregory R. T. The use of Finite-segment p-adic arithmetic fo computation. BIT, 18, 1978, 282-300.

95. Gregory R. T., Matula D. W. Base conversion in residue systems//BTT. 1977. Vol. 17. P. 286-302.

96. Heckmann, R.: The Appearance of Big Integers in Exact Real Arithme based on Linear Fractional Transformations, Foundations of Software and Computation Structures, Springer LNCS 1378, 1998, pp. 172-188.

97. Koren, O. Zinaty, Evaluating Elementary Functions in a Numerical Coprocessor Based on Rational Approximations, IEEE Trans, on Comp> Vol. 39, No. 8, Aug. 1990.

98. Jen Vuillemin, Exact real computer arithmetic with continued fractions IEEE Transactions on Computers, Vol. 39, 1990, pp. 1087-1105.

99. J.R. Shewchuk: Adaptive Precision Floating-Point Arithmetic and Fast Robust Geometric Predicates. Technical Report CMU-CS-96-140, Carn< Mellon University, 1996.natations. Computer1981b,imputerirface. J.jigs 5th Arbor,exactumberiters,

100. J. M. Borwein and B. Salvy, "A proof of a recursion for Bessel raoraen"C Exp.Mathematics, vol. 17 (2008), 223-230.t&Z

101. Kornerup, P., Matula, D. W.; An Algorithm for Redundant Binary Bit-Pipelined Rational Arithmetic, IEEE Transactions on Computers, Vol. 39, No. 8, 1990, pp. 1106-1115.

102. Kornerup, P. and Matula, D., "Algorithms for Arbitrary Precision Floating Point Arithmetic," Proceedings of the 10th IEEE Symposium on Computer Arithmetic, 1991.

103. K. Briggs, Implementing exact real arithmetic in python, C++ and C, Theoretical Computer Science, vol.351, 2006, pp. 74-81.

104. Limongelli, C. ''Exact solution of computational problems via parallel truncated p-adic arithmetic" in: A. Miola and M. Temperini Eds. "Advances in Design of Symbolic Computation Systems" RISC Series in Symbolic Computation, Springer-Verlag 1997.

105. Mencer, O., Morf, M. and Flynn, M. J., "Precision of Scmi-Exact Redundant Continued Fraction Arithmetic for VLSI," SPIE '99 ,Arithmetic session, 1999

106. Matula, D. and Kornerup, P., "Finite Precision Rational Arithmetic: An Arithmetic Unit," IEEE Transactions on Computers, Vol. C-32 pp. 378-387, 1983.

107. MPFR C library for multiple-precision floating-point computations. http://www.mpfr.org/

108. NVIDIA CUDA Compute Unified Device Architecture: http://developer.download.nvidia.com/compute/cuda/l0/NVIDIACUDAP rogrammingGuidel .O.pdf

109. Online book from CUDA programming course at UIUC. http://courses.ece.illinois.edu/ece498/al/Syllabus.html

110. Peter R. Turner: Fraction-Free RNS Algorithms for Solving Linear Systems, IEEE Symposium on Computer Arithmetic 1997: Asilomar, CA, USA, pp 218-217

111. P.FI. Hauschildt and E. Baron, "The Numerical Solution of the Expanding

112. Stellar Atmosphere Problem," J. Computational and Applied Mathematics, vol. 109, 1999, pp. 41-63.

113. Potts P. J., Edalat A., and Escardo M. H. Semantics of exact computer arithmetic. In Twelfth Annual IEEE Symposium on Logic in Computer Science, Warsaw, Poland, 1997, P. 248-257.

114. Pour-el M.B. and Richards I. Computability and non-computability in classical analysis. Trans. Am. Math. Soc., P. 539-560, 1983.

115. Rao T. M. Error-free computation of characteristic polynomial of a matrix. Comp. and Math, with Appl., 4, 1978, 61-65.

116. Rao T. M. Finite field computational techniques for exact solution of numerical problems. Ph. D. Dissertation. Department of Applied Mathematics, Indian Institute of Sciences, Bangalore, 1975.

117. Rao T. M., and Gregory R. T. The conversion of Hensel codes to rational numbers. Proceedings 5th Symposium on Computer Arithmetic, IEEE Computer Society, Ann Arbor, Michigan, 1981, 10-20.

118. Rao T. M., Subramanian K., and Krishnamurthy E. V. Residue arithmetic algorithms for exact computation of q-inverses of matrices, SI AM J. Numer. Anal., 13, 1976, 155-171.

119. Simpson A. Lazy functional algorithms for exact real functionals. Mathematical Foundations of Computer Science 1998, volume 1450 of Lecture Notes in Computer Science, pages 323-342. Springer-Verlag, 1999.

120. Smyre J. S. Exact computation using extended-precision single-modulus residue arithmetic. M. S. Thesis. Department of Computer Science, University of Tennessee, Knoxville, 1983.

121. Soderstrand M. A. Escott R. A. VLSI implementation in multiple-valued logic of an FIR digital filter using residue number system arithmetic//lEEE Trans, on Circuits and Syst. 1986. Vol. CAS-33, N 1. P. 5-20

122. Y. Fie and C. Ding, "Using Accurate Arithmetics to Improve Numerical Reproducibility and Stability in Parallel Applications," J. Supercomputing, vol. 18, no. 3, 2001, pp. 259-277.

123. Yozo Hida, Xiaoye S. Li and David FI. Bailey, "Algorithms for Quad-Double Precision"

124. Watanuki O. and Ercegovac M.D. Error Analysis of Certain Floating-Point On- Line Algorithms // IEEE Trans, on comput., 1983, Vol. C-32, N 4, P-352-358.

125. Newton division. http://en.wikipedia.org/wiki/Division(digital)