автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.15, диссертация на тему:Методы и алгоритмы организации высокоточных вычислений в арифметике остаточных классов для универсальных процессорных платформ

На правах рукописи

ИСУПОВ Константин Сергеевич

МЕТОДЫ И АЛГОРИТМЫ ОРГАНИЗАЦИИ ВЫСОКОТОЧНЫХ ВЫЧИСЛЕНИЙ В АРИФМЕТИКЕ ОСТАТОЧНЫХ КЛАССОВ ДЛЯ УНИВЕРСАЛЬНЫХ ПРОЦЕССОРНЫХ ПЛАТФОРМ

Специальность

05.13.15 — Вычислительные машины, комплексы и компьютерные сети

6 НОЯ 2014

Автореферат диссертации на соискание ученой степени кандидата технических наук

ПЕНЗА 2014

005554447

Работа выполнена в Федеральном государственном бюджетном образовательном учреждении высшего профессионального образования «Вятский государственный университет».

Научный руководитель - доктор технических наук, профессор

Князьков Владимир Сергеевич.

Официальные оппоненты: Галанина Наталия Андреевна, доктор

технических наук, ФГБОУ ВПО «Чувашский государственный университет имени И. Н. Ульянова», профессор кафедры математического и аппаратного обеспечения информационных систем;

Федюнин Роман Николаевич, кандидат технических наук, ФГБОУ ВПО «Пензенский государственный университет», заместитель начальника управления информационных технологий и телекоммуникаций.

Ведущая организация - Федеральное государственное унитарное

предприятие «Российский федеральный ядерный центр — Всероссийский научно-исследовательский институт экспериментальной физики», г. Саров.

Защита состоится «11» декабря 2014 г., в 14-00 часов, на заседании диссертационного совета Д 212.186.01 в Федеральном государственном бюджетном образовательном учреждении высшего профессионального образования «Пензенский государственный университет» по адресу: 440026, г. Пенза, ул. Красная, 40.

С диссертацией можно ознакомиться в библиотеке Федерального государственного бюджетного образовательного учреждения высшего профессионального образования «Пензенский государственный университет» и на сайте: http://science.pnzgu.ru/page/13778.

Автореферат разослан «30» октября 2014 г.

Отзывы на автореферат (в двух экземплярах, заверенные печатью организации) просим направить по адресу: 440026, г. Пенза, ул. Красная, 40, ученому секретарю диссертационного совета.

Ученый секретарь

диссертационного совета Гурин Евгений Иванович

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы. Решение многих научных и практических задач с использованием современных средств вычислительной техники требует повышения численной точности результатов обработки. Потребность науки в высокоточных вычислениях существовала всегда, и в настоящее время она особенно актуальна. Крупные задачи, критичные к точности, возникают в самых разнообразных областях: в физике и космологии, в экспериментальной математике и вычислительной геометрии, в различных сферах высокотехнологичной промышленности и т.д. Некоторые из них требуют двукратного увеличения точности, другие — четырехкратного, третьи же требуют сотни и более разрядов для получения численно значимых результатов. Характерной особенностью таких задач является большая размерность, в связи с чем критичным параметром становится время решения.

Основной причиной, влияющей на точность вычислений, является использование округлений в арифметических операциях, необходимость которых обусловлена фиксированной и относительно малой длиной операндов в современных процессорах. Строгий анализ алгоритмов на устойчивость относительно ошибок округления и выбор оптимального из альтернативных вариантов часто оказываются непомерно трудоемкими, что подтверждается в работах Д. Голдберга, Д. Каханера, Дж. X. Уилкинсона, М. Овертона, К. Моулера, С. Нэша, С. К. Годунова, В. В. Воеводина. Поэтому основной способ получения корректных результатов численных расчетов, критичных к округлениям, - использование программной обработки чисел большой (превышающей длину машинного слова) разрядности. Однако построение длинной арифметики на базе позиционных систем счисления приводит к существенному, часто неприемлемому, снижению быстродействия.

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

На развитие методов вычислений в СОК существенное влияние оказали российские ученые - И. Я. Акушский, Д. И. Юдицкий, В. М. Амербаев, Н. И. Червяков, Н. А. Галанина, В. С. Князьков, Ш. А. Оцоков, за рубежом -Н. L. Garner, N. S. Szabo, G. С. Cardarilli, A. Omondi и др. Однако до сих пор основной нерешенной проблемой на пути создания быстродействующих алгоритмов высокоточной модулярной обработки остается большая

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

Еще одна важная проблема — построение быстродействующих алгоритмов вещественной модулярной арифметики. Известные методы представления чисел с плавающей точкой в СОК либо являются достаточно узконаправленными, либо ориентированы на специализированные аппаратные архитектуры и неэффективны с точки зрения скорости при реализации на вычислительных системах общего назначения. Развитие указанных направлений позволит использовать модулярную арифметику для организации высокоточных быстродействующих вычислений во многих приоритетных областях науки и техники.

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

Для достижения поставленной цели были решены следующие задачи.

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

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

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

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

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

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

Соответствие паспорту научной специальности. Область исследования соответствует паспорту специальности 05.13.15 - Вычислительные машины, комплексы и компьютерные сети по пункту 3 «Разработка научных методов и алгоритмов организации арифметической, логической, символьной и специальной обработки данных, хранения и ввода-вывода информации» и пункту 4 «Разработка научных методов и алгоритмов организации параллельной и распределенной обработки информации, многопроцессорных, многомашинных и специальных вычислительных систем».

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

Достоверность и обоснованность полученных в диссертационной работе результатов и сформулированных на их основе выводов обеспечиваются строгостью производимых математических выкладок и корректным использованием методологического аппарата исследований. Справедливость выводов относительно эффективности и корректности предложенных методов и алгоритмов подтверждена компьютерным моделированием и экспериментами. Получены свидетельства о государственной регистрации разработанных программных средств [17—23], а также патент на новый способ организации вычислений [24].

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

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

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

3. Итерационный метод масштабирования чисел в СОК коэффициентом 2Ч (<7 - натуральное число), отличающийся тем, что на каждой итерации для вычисления нового приближения выполняются определение интервала

локализации и корректировка формального частного от деления предыдущего приближения в модулярном представлении на шаг масштабирования 2Л (1 < И < д), что обеспечивает повышение скорости вычислений в сравнении с аналогами.

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

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

Основные научные положения, выносимые на защиту:

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

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

3. Итерационный метод масштабирования чисел в СОК коэффициентом 2Ч.

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

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

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

Реализация и внедрение. Результаты диссертации использованы при выполнении НИР №2.2.1.1/3302 по АВЦП Минобрнауки РФ «Развитие научного потенциала высшей школы» (2009-2010), НИР № 14.В37.21.0590

по ФЦП «Научные и научно-педагогические кадры инновационной России» (2009-2013), НИР №2.4.1-2 по ПСР ФГБОУ ВПО «ВятГУ» (2012-2013), научного проекта РФФИ № 14-07-31075 «Разработка программной библиотеки высокоточных вычислений для решения задач численного моделирования» (2014-2015), а также в образовательном процессе ФГБОУ ВПО «ВятГУ» при подготовке магистров по направлению «Информатика и вычислительная техника».

Апробация результатов работы. Результаты диссертации докладывались и обсуждались на: III сессии научной школы «Технологии высокопроизводительных вычислений и компьютерного моделирования» (Санкт-Петербург, 2010); летней сессии Всероссийской молодёжной школы по суперкомпьютерным технологиям и параллельному программированию (Москва, 2010); трех Международных суперкомпьютерных конференциях «Научный сервис в сети Интернет» (Новороссийск, 2010, 2011, 2012); конкурсе «Невозможное стало возможным: реальные приложения для НРС» (Москва, 2010); двух Международных выставках «CeBIT» (Ганновер, 2011, 2013); IV и V Испано-Российских Форумах «Информационно-коммуникационные технологии» (Мадрид, 2011, 2012); двух Всероссийских научных конференциях «Математическое моделирование развивающейся экономики, экологии и биотехнологий» (Киров, 2011, 2012); четырех Всероссийских конференциях «Общество, наука, инновации» (Киров, 2010, 2012, 2013, 2014); выставке информационных технологий «SofTool» (Москва, 2011); двух конкурсах прикладных разработок и исследований «Компьютерный континуум: от идеи до воплощения» (Москва, 2011, 2012); Международной научной конференции «Суперкомпьютерные системы и их применение» (Минск, 2012); Всероссийской научно-методической конференции «Телематика'2012» (Санкт-Петербург, 2012).

Публикации. По материалам диссертации опубликовано: 16 статей, из них семь в рецензируемых журналах из перечня ВАК РФ; 15 тезисов докладов. Получено семь свидетельств о регистрации программ для ЭВМ и один патент.

Личный вклад соискателя. Все научные результаты, приведенные в диссертационной работе и сформулированные в положениях, выносимых на защиту, получены автором лично. Работы [1, 2, 8, 15, 16] опубликованы в соавторстве с научным руководителем, которому принадлежат формулировка концепции решаемой проблемы и постановка цели исследования. Новый формат представления многоразрядных чисел с плавающей точкой в базисе СОК, рассматриваемый в работе [13], предложен лично автором. Основной объем работ по написанию программ [17-23], их отладке, тестированию и интерпретации результатов экспериментов выполнен автором. Способ умножения чисел большой разрядности [24] разработан автором. Все основные положения тезисов докладов, подготовленных с соавторами, сформулированы лично диссертантом.

Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения, списка терминов, списка сокращений и условных обозначений, списка литературы из 151 наименования и 10 приложений. Основная часть работы изложена на 178 страницах машинописного текста и содержит 35 рисунков, 11 таблиц.

СОДЕРЖАНИЕ РАБОТЫ

Во введении обоснована актуальность темы, сформулированы цель и основные задачи исследования, раскрываются научная новизна и практическая значимость работы, приведены основные положения, выносимые на защиту.

В первой главе приводится классификация задач, критичных к численной точности, рассматриваются методы, алгоритмы и программное обеспечение (ПО) высокоточной арифметики. Высокоточные вычисления -совокупность вычислительных методов, способов представления чисел и алгоритмов их обработки, приемов программирования, позволяющих получить результат решения численной задачи с точностью, большей, чем обеспечивается спецификацией IEEE-754. К основным причинам необходимости использования высокоточных вычислений относятся: 1) решение плохо обусловленных СЛАУ [10] и жестких систем дифференциальных уравнений (ДУ); 2) вычисление рекуррентных формул и больших сумм; 3) крупномасштабное и длительное моделирование физических процессов и т.д.

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

Недостатков позиционных систем счисления (ПСС) лишены системы остаточных классов (СОК). Базис СОК определяется взаимно простыми модулями-основаниямир\,рг,...,рщ а их произведение Р = Р\Р2~-Р„ задает диапазон уникального числового представления. При этом число A'sfO, F-1], многоразрядное в ПСС, представляется в СОК в виде п малоразрядных остатков (модулярных разрядов): X = (х\,х2,-.,хп}, xt=\X |д <-> X mod Pi. Число в такой форме называется модулярным. Все

модульные операции в СОК (сложение, умножение и прочие) выполняются независимо по каждому модулю, поэтому легко и быстро в связи с малой разрядностью остатков Это позволяет распараллеливать вычисления на уровне модулярных разрядов. Результаты апробации комплекса для решения матричных задач в модулярной арифметике [1, 8, 9, 11, 17] показывают, что даже при последовательных вычислениях массовое выполнение модульных операций позволяет повысить скорость на несколько порядков.

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

Во второй главе рассматриваются немодульные операции сравнения, вычисления знака, оценки переполнения диапазона и масштабирования чисел в СОК [3-7, 16]. Для их выполнения требуется оценка позиционной величины модулярного числа, которая, согласно китайской теореме об остатках (CRT), определяется как Х= \х\В\+...+хпВ„\р, где В, - ортогональный базис СОК. Однако ее вычисление затратно, поскольку каждое слагаемое имеет величину порядка Р. Поэтому для выполнения немодульных операций используются позиционные характеристики (ПХ) - функции от остатков, позволяющие оценить величину модулярного числа без ее прямого вычисления. Вместе с тем алгоритмы вычисления известных ПХ (представление в системе со смещанными основаниями, ранг, ядро, диагональная функция и пр.) также обладают высокой вычислительной сложностью, а применение методов табличной выборки часто сопряжено с неприемлемыми затратами памяти. В связи с этим перспективными являются подходы на основе оценки относительной величины чисел в СОК.

Определение. Относительная величина Е(Х/Р) модулярного числа ЛГ— это отношение его позиционного значения к произведению Р модулей СОК: Е(Х/Р) = \х1В1+х2В2+ — + х„Вп\р/Р, 0 < Е(Х/Р) < 1. (1)

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

Предлагается новый метод выполнения немодульных операций [3, 5, 16] на основе интервальной аппроксимации величины (1). Центральным в нем является понятие интервально-позиционной характеристики числа.

Определение. Интервально-позиционная характеристика (ИПХ) -это отрезок 1(Х1 Р): = \_Х/Р, XIр] с направленно округленными позиционными границами, которые удовлетворяют условию включения: Х/Р < Е(Х/Р) < XIP.

ИПХ проецирует диапазон СОК на полуинтервал [0, 1), ассоциируя модулярное число Хс парой округленных позиционных чисел - границ, которые локализуют его относительную величину (рисунок 1).

Вычисление нижней границы / \ Вычисление верхней границы ИПХ с округлением по недостатку / \ ИПХ с округлением по избытку

у 1(Х!Р) к

"f

+

!

-Е(Х/Р)

Рисунок 1 - Интервально-позиционная характеристика Для вычисления границ ИПХ справедливы соотношения:

Х/Р =

/=1

>-1

'Pi I

Pi

x/p =

Et (=i

МтЧ

'a

Pi

(2)

где x, — /-Й остаток числа X, Ip-1! - вес /-го ортогонального базиса СОК,

I I \Pi

| |i — дробная часть аргумента, а стрелки соответствуют направленным округлениям: 1 - округление с недостатком («вниз»), Т - округление с избытком («вверх»). Последовательное вычисление формул (2) требует 0(п) элементарных операций, параллельное - 0(log п). Это на порядок быстрее преобразования в смешанную систему (Mixed Radix Conversion, MRC), требующего, соответственно, 0{rr) и 0(ri) операций.

При использовании ИПХ основные немодульные операции сводятся к анализу позиционных границ интервалов и оценке достоверности результата. Например, для сравнения чиселХи Fнеобходимо: 1) вычислить ИПХ 1{Х/Р) и I{Y/P); 2) убедиться в соблюдении формальных условий корректности результата; 3) определить результат, сопоставив границы ИПХ по правилам интервальной арифметики: если Х/Р > Y/P, то Х> Y; если Х/Р < Y/P. то Х< Y. Аналогично выполняется определение знака числа в симметричной СОК, а также контроль переполнения суммы или произведения чисел.

Рассмотрим подробнее условия, проверяемые на шаге 2. Величина абсолютной ошибки округления характеризуется значением диаметра ИПХ:

diam 1(Х/Р) = ~Х/Р - Х[Р.

Если п - число модулей, а к- разрядность мантисс в представлении границ ИПХ, то при вычислении по формулам (2) справедлива оценка: diam 1(Х/Р)<п-2~к. Направленные округления увеличивают диаметр ИПХ, не влияя в общем случае на свойство включения Е(Х/Р) е 1(Х/Р). Однако в ряде случаев из-за недостаточной точности вычисления границ ИПХ это свойство нарушается: когда число X очень мало по отношению к Р либо наоборот, когда X находится вблизи (Р - 1). В первом случае неправильно вычисляется нижняя граница ИПХ, во втором — верхняя. В любом случае diamI(Х/Р) <0. Такая ИПХ называется неправильной по Каухеру

или просто неправильной. Первое формальное условие корректного выполнения любой немодульной операции - правильность ИПХ операндов. Если оно выполнено, то окончательный вывод о корректности результата определяется на основании анализа второго формального условия (таблица 1).

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

Операция Условие

Сравнение Шат [1(Х1Р) п /(КАР)] < 0

Определение знака Лат 1(Х!Р) гл I < 0 V Х/Р = 4^г

Оценка переполнения числового диапазона при сложении (Пат [[1{Х1Р) + ЦУ1Р)] п 1] < 0 V т ф(Х/Р) + 1(Г/Р)] = 1

Оценка переполнения числового диапазона при умножении &\ш\[[ЦХ1Р) ■ 1(ПР)] п 1] < 0 vinf [1{Х!Р) • /(№)] = 1

В таблице 1 т^1{Х/Р) +(•) /(У//5)] - это нижняя граница интервала-суммы (произведения). Сложение и умножение ИПХ выполняются с учетом свойства монотонности по включению аппроксимируемой величины. Пересечение ИПХ определяется в терминах интервального исчисления:

[1{Х1Р) п /(ГЛР)] = [шах{Х/Р, Г/Р},тшШл 77р}].

Если диаметр этого интервала меньше нуля, то ИПХ не пересекаются в стандартном теоретико-множественном смысле.

Таким образом, при интервальной аппроксимации величины чисел в СОК осуществляется автоматический учет погрешностей округлений, не требующий рассмотрения специфики машинных вычислений. Конъюнкция двух формальных условий составляет признак (достаточное условие) корректности результата немодульной операции, инвариантный как к числу модулей СОК, так и к их разрядности. В случае нарушения достаточного условия корректности появляется возможность повысить точность ИПХ или использовать другие методы выполнения немодульных операций.

На базе ИПХ разработаны алгоритмы сравнения [7], определения знака и контроля переполнения диапазона. Анализ сложности показал, что, в зависимости от частоты нарушения достаточного условия корректности, их ускорение по сравнению с алгоритмами МЯС-метода и многоразрядного метода ортогональных базисов (СЯТ-метод) может достигать, соответственно, 0.31« раз и 1.39и раз, где п — число модулей. Результаты экспериментов (параметры СОК: 32

5.5-1

5.0-

4.5-

4.0-

и X Ч 5

Е

3.0-

и 2.5

т 2.0

1.5

1.0-

0.5-

0.0-1

Г Щ них 1Ш МЯС □ СШ 1

—

— / /

ш %

И ............ % /

ши N в V. : 4 ш

а) Г,) в) г)

Рисунок 2 - Времена выполнения немодульных операций в СОК: а) сравнение; б) определение знака; в) и г) контроль переполнения при сложении и умножении

модуля, Р~ 2479; конфигурация: Intel Core i5-3570K 3.40 GHz / 4 Cores / 6M Cache / 8 Gb RAM / Intel С++ Compiler v. 13.0) представлены на рисунке 2. ИПХ вычислялись в 64-битной арифметике. Среднее ускорение составило 4.11 раза по сравнению с MRC и 7.32 раза по сравнению с CRT.

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

Следующей решенной задачей стало обеспечение быстрого и точного вычисления ИПХ. Мера точности ИПХ - ее относительная погрешность

5I(X/P) = max{SAVP, 8xJp). (3)

При большой погрешности (3) оценка величины (1) становится неинформативной. Пусть £ - предел допустимой относительной ошибки ИПХ, а ее границы вычисляются по формулам (2) в ¿-значной арифметике с ПТ, т.е. разрядность мантисс равна к. Показано, что Ы(Х!Р) < s, только если

Х>уР, (4)

где у = п ■ 2~к / е, п - число модулей СОК, а Р - их произведение. Если X < ц/Р, то формулы (2) не обеспечивают заданную точность. Уменьшение у за счет увеличения к приводит к необходимости работы с длинными числами и снижению быстродействия. Таким образом, при вычислении ИПХ выдвигаются противоречивые требования — точность и скорость. Для достижения компромисса разработан алгоритм ISaC (Iterative Shift and Correction) [6, 7], представленный на рисунке 3. Он основан на возможности безошибочного деления границ ИПХ, представленных двоичными числами с ПТ, на степени двойки. Это позволяет, когда Хне отвечает условиям (4), вычислить смещенную ИПХ - характеристику числа XМ = X ■ ТУ, для которого эти условия выполняются, а затем без увеличения погрешности перейти к искомой ИПХ, разделив смещенные границы на 2V. Однако при таком подходе на смещение накладываются ограничения:

\\iP<X-2v <Р/2 для всех X е[1, уР], (5)

которые не согласованы при Р > 1/2*|/2. Противоречие решается декомпозицией критической области. Для этого задается векторное смещение

v = (2vi,2v^,...,2v0,

где v, =jjog2(l/2-V)J для j = \,g, причем g = Iog2(l /Р)/(1 + log2 у)] -1

(при \|/ < 0.5). Элементы вектора v разбивают отрезок [1, \|/Р] на g интервалов и обеспечивают выполнение условий (5) в каждом из них по отдельности. Заранее вычисляется матрица смещенных весов ортогональных базисов

/ \

м = 2VJ -Ip-'l

ч 1 1 1й Pi 1 2 \Р2 Р2 1 " 'л, Р" /

11. Вычислить верхнюю границу 12. —Точность ^чобеспечена?/^

Нет]

Ф

14. Инициализировать смещение 15. Вычислить

смещенную верхнюю границу

17.

Увеличить смещение

13.

Вычислить нижнюю границу

Ж

Вычислить смещенную

нижнюю границу +

19.

Коррелировать

ПО. Завершить

Рисунок 3 - Высокоточный алгоритм вычисления ИПХ (18аС)

На шаге II вычисляется верхняя граница по формуле из (2); если она больше то условие (4) выполняется и вычисляется нижняя граница. Иначе инициализируется индекс смещения ;' = 1 и выполняется основной цикл (15—»16—>17), в котором вычисляется смещенная верхняя граница

X{v']!P =

It i=i

■мл\

Pi

(6)

где Мр - i-й элемент j-й строки матрицы М. Если на j-й итерации цикла Vp > , то требуемая точность достигнута и вычисляется смещенная нижняя граница X^VjbP по формуле, аналогичной (6). На шаге 19 выполняется масштабирование смещенных границ j-м элементом вектора степеней v:

X!Р = X{vi]IP / 2Vj, YiP = Х^'ЬР / 2V'. Если результат лежит в пределах диапазона нормализованных чисел, масштабирование не приводит к потере точности. В результате работы алгоритма вычисляется ИПХ 1(Х/Р) с погрешностью 51(Х/Р) < с.

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

Результаты экспериментов (параметры СОК: 32 модуля, Р~ 2479; конфигурация: Intel Core ¡5-3570К 3.40 GHz / 4 Cores / 6M Cache / 8 Gb RAM / Intel С++ Compiler v. 13.0) представлены на рисунке 4. Исследованы три алгоритма: классический,

5 1.50 5 1.25

I 1.00

| 0.50 И 0.25 0.00

^ Алгоритм ISaC, 64 бит Классический алгоритм, 64 бит

-+-

-Ь

-+-

2 ы 2128 2 2 2 2 2 Абсолютная величина модулярного числа

Рисунок 4 - Зависимость времени вычисления ИПХ от позиционной величины модулярного числа

вычисляющий формулы (2) в 64-битном формате с ПТ, алгоритм ¡БаС, также использующий 64-битный формат, и многоразрядный, реализующий формулы (2) в 490-битной арифметике пакета МРЕЯ V. 3.0.1. Точкой на графике (2435) отмечена правая граница области значений модулярных чисел, в пределах которой классический 64-битный алгоритм не позволил получить ИПХ требуемой точности. Алгоритм КаС и многоразрядный позволили на всем диапазоне получить ИПХ с погрешностью £ < 1 %, при этом скорость алгоритма КаС выше многоразрядного более чем в 13 раз.

Таким образом, предложен алгоритм вычисления ИПХ, позволяющий получить высокоточную информацию о величине модулярного числа без использования многоразрядной арифметики и сложного преобразования в ПСС.

Интервально-позиционные характеристики используются в новом методе масштабирования чисел в СОК степенью двойки. Задача масштабирования состоит в отыскании для числа X = (х\,х2,...,хп} и натурального коэффициента и = 2Ч частного У = \_х / и\ ■ Известный метод половинного деления состоит в вычислении соотношения % = /2\ для / = 1,2,...,<7. Однако он обладает высокой сложностью 0(дп), где п - количество модулей.

Предлагаемый метод позволяет сократить количество итераций за счет увеличения шага. Пусть дано число X, которое требуется масштабировать числом и = 2я. Зафиксируем 2к — основной шаг. Предварительно вычислим модулярные коды мультипликативных инверсий первых к натуральных степеней двойки, которые представим в виде матрицы

н^Ыг'^Ыг1^,...,^)-1^), у = 1,...,/,

Также вычислим матрицу модулярных поправок размера (2Л -1) х и: 8=(Г>/2»\,\\]Р,2%2,..,\\]Р12%), у=1,...,2*-1.

Тогда весь процесс масштабирования в соответствии с предлагаемым методом распадается на два этапа: итерационное приближение и уточнение.

I. Итерационный этап. Используется основной шаг масштабирования, числовой диапазон [0, Р-\] разбивается на 2Н интервалов, а вычисления выполняются в соответствии с рекуррентным соотношением % = / 2}>\,

1= 1,2,...,а, где а = \л / Ь\, Уо = X. Каждая итерация состоит из трех действий.

1. Вычисление формального частного (ФЧ) У, = умножением }/_] на инверсию (2Л)-1, определяемую /г-й строкой матрицы Н.

2. Вычисление ИПХ ФЧ 1(^/Р) и определение номера к е {1,2,...,2а — 1} интервала его локализации по формуле к = ]>.//>. 2Л].

3. Корректировка ФЧ вычитанием к-й строки матрицы в: = ^ - .

И. Уточняющий этап. Используется шаг 2Ь, 6 = |91й> вычисляется результат масштабирования У = [_Уа 12ь\. Действия аналогичны одной итерации этапа I (код поправки выбирается из в со смещением 2Л / 2Ь).

Число итераций предлагаемого метода меньше в q/(\_q/h\ + I) раз, чем

у метода половинного деления. Максимальный шаг 2h ограничивается лишь объемом памяти и точностью ИПХ. Основные этапы эффективно распараллеливаются по модулям. Результаты экспериментов (параметры СОК: 32 модуля, Р ~ 2479; конфигурация: Intel Pentium Т4400 2.20 GHz / 2 Cores / 1M Cache / 3 Gb RAM / Intel С++ Compiler v. 13.0) представлены на рисунке 5.

11.0 ю.о-

9.o l 8.0 | 7.0

S- 6.0

I 5.0 1 4.0 i 3.0

I 2.0-

J- 1.0 0.0

18 j 1614-

S 12

P. « 10 я

S 8

Q,

§ 6+ о

* 4-

L.....шита

Гпгпп

Результаты эксперимента - Аналитическая оценка

у

</\

2+ У

О

0

2 4 6 8 10 12 14 16 18 20 Логарифм шага масштабирования, h

б)

2 4 6 8 10 12 14 16 18 20 Логарифм шага масштабирования, И

а)

Рисунок 5 - Зависимость времени масштабирования 50000-элементного массива модулярных чисел коэффициентом и = 264 (а) и ускорения нового метода относительно метода половинного деления (б) от шага масштабирования

Таким образом, предложен и экспериментально подтвержден новый итерационный метод, позволяющий повысить скорость масштабирования чисел в СОК степенью двойки без перевода их в ПСС.

Практическая ценность полученных в главе результатов заключается в возможности их использования при создании ПО модулярных вычислений в цифровой обработке сигналов, криптографии и при реализации библиотек высокоточной арифметики, когда диапазон СОК имеет большую величину и применение MRC-, CRT-мeтoдoв или табличной выборки для выполнения немодульных операций сопряжено со значительными временными или ёмкостными затратами. Все разработанные алгоритмы реализованы в виде программы для выполнения немодульных операций [22].

В третьей главе предлагается новый формат представления чисел большой разрядности для повышения скорости высокоточных вычислений, разрабатываются алгоритмы арифметики в новом формате [12—14].

Для представления многоразрядных чисел предлагается следующий модулярно-позиционный формат с плавающей точкой (МП-формат):

х-ф,МД,/(М/Р)}, (7)

где 5 = - знак числа, М = (т\,т2,--;Гпп) - модулярная мантисса в СОК,

^ е [^-тт > ^тах ] ~ целочисленный порядок со знаком, 1{М!Р) = [М/Р, М/Р~] -ИПХ мантиссы. Значение числа вида (7) определяется выражением

X = (-1)5 • \тхВх + т2В2 + ...+ тпВп\р ■ 2х,

где В\, &,..., В„ - ортогональные базисы. Мантисса М принимает значения из интервала [О, Р- 1], где Р — произведение модулей СОК. Модульные операции над знакопозициями мантиссы т: свободны от переносов, поэтому выполняются быстро. Возможна их параллельная обработка на уровне данных (векторизация) и на уровне задач (многопоточность).

Основное отличие МП-формата от известных ранее - включение ИПХ в представление числа. Это дает следующие преимущества: 1) позволяет использовать новую организацию арифметической обработки на основе быстрой предвычислительной оценки мантиссы результата; 2) применение интервальной арифметики позволяет при выполнении модульных операций снизить время вычисления ИПХ до нескольких тактов, используя алгоритмическое уточнение лишь при выполнении немодульных процедур.

Характеристики МП-формата (7): машинный эпсилон: eps = 2~Llog2(^-l)J. шаг: ulp(x) = , y = [log2[(/'-l)/M]J; абсолютная и относительная ошибки округления ограничены ulp(x) и eps, соответственно. Относительная погрешность основных операций имеет границу 5 < 21—L'°g2 V/"-]J

На основе этих характеристик разработан алгоритм генерации модулей, который для априорно заданного разряда точности вычислений е находит набор соседних взаимно простых чисел р\,р2,...,р„, логарифм квадратного корня от произведения которых аппроксимирует е.

Для формата (7) предложены кодировки чисел, бесконечностей и нечисловых величин, разработаны алгоритмы преобразования позиционных чисел в МП-формат и обратно. Если преобразуемая в СОК мантисса имеет большую разрядность, то целесообразно использовать новый табличный метод [2].

Разработаны новые алгоритмы округления, выравнивания порядков, сложения, вычитания, умножения, деления и сравнения чисел в МП-формате. Использование ИПХ для быстрой оценки мантиссы позволило реализовать новую предвычислительную схему округления, согласно которой решение о необходимости округления принимается на основании анализа ИПХ операндов непосредственно перед арифметической операцией, а не после ее выполнения. Такая схема предпочтительна с точки зрения точности и снижения количества итераций масштабирования мантиссы.

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

rsh(M) = max {("log2 M/P - log2 öf|, [log2 M/P - log2 а], o},

где log2/(a) = [log2 a, log2ä], a = LV/'-lJ/p - константы. При известной ИПХ 1(М/Р) сложность алгоритма инвариантна к числу модулей СОК.

Округление чисел в МП-формате состоит в масштабировании мантиссы М коэффициентом с сопутствующим увеличением порядка X. Для

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

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

1. Для разности порядков АХ = Хх - Ху (при АХ < 0) проверяется условие 1(МУ /Р) < 2ах . Если оно выполняется, то г = 0 и переходим к шагу 3.

2. ИПХ 1(Му/Р) уточняется, вычисляется число г = ^Му/Р+ \ АХ |~|. Если 1о§2 Мх/Р > г - 1о«2 Р, то переходим к шагу 3, иначе х обнуляется.

3. Мантисса Му умножается на 2а, а = |ДХ.| - г; из Ху вычитается а, х округляется масштабированием Мх степенью 2'", к Хх прибавляется г.

Разработанные алгоритмы поддерживают арифметику бесконечностей и обработку исключений стандарта 1ЕЕЕ-754. Все алгоритмы, кроме деления, имеют в общем случае линейную сложность по числу модулей при последовательном вычислении знакопозиций мантиссы. Параллельная обработка во многих случаях позволяет снизить оценку до логарифмической.

Экспериментально подтвержден высокий уровень параллелизма алгоритмов. При векторизации циклов обработки мантисс и ИПХ быстродействие возросло в среднем в 2.38 раза с эффективностью (отношение ускорения к числу одновременно обрабатываемых пар операндов) 0.60.

add sub cmp mult aac sac mac div

Рисунок 6 - Временная сложность операций многоразрядной арифметики: add, sub, cmp, mult, div - сложение, вычитание, сравнение, умножение и деление, aac, sac и mac - операции сложения, вычитания и умножения с накоплением (результаты получены при точности вычислений 239 бит на конфигурации: Intel Core ¡5-3570К 3.40 GHz/4 Cores/6М Cache/8 Gb RAM/Intel С++Compiler v. 13)

Сравнительные эксперименты (рисунок 6) позволили получить следующие усредненные показатели ускорения алгоритмов по сравнению с аналогами (ввиду сильного разброса использована медиана распределения):

4.35 раза по сравнению с пакетом A Library for doing Number Theory (NTL), 1.32 раза по сравнению с пакетом The GNU MPFR Library и 13.15 раза по сравнению с системой Wolfram Mathematica. Деление требует преобразования мантисс в ПСС, и его быстродействие ниже более чем на порядок. Поэтому следует избегать расчетов, требующих множественных делений.

Полученные результаты могут использоваться для повышения быстродействия многоразрядных модулей прикладного ПО, используемого для решения критичных к округлениям задач во многих отраслях науки и техники. Разработанный формат и алгоритмы могут выступать в качестве базы для высокоточной параллельной арифметики. На программные реализации алгоритмов получены свидетельства о регистрации [18-21]. Прототип формата и способ умножения чисел с ПТ в СО К защищены патентом РФ [24].

В четвертой главе разрабатывается новая библиотека высокоточной арифметики в МП-формате [15, 23]. В библиотеке используется тип данных (mf_t), обеспечивающий произвольную длину чисел (и произвольную точность). Этот тип состоит из пяти полей, представленных в таблице 2.

Таблица 2 - Тип данных, используемый в библиотеке

Поле Базовый тип языка Си Описание

Sign int Знак числа

Residue long \п] Модулярная мантисса - массив остатков

Exp int Порядок

Ic bot double Нижняя граница ИПХ

le top double Верхняя граница ИПХ

Библиотека состоит из трех модулей: модуль ядра, модуль вспомогательных подпрограмм и модуль тестов. Для перехода на другой базис СОК используется вспомогательный многоразрядный модуль. Быстродействие библиотеки исследовано на задачах матричного умножения и моделирования распространения теплоты в металлическом стержне с точностью 239 бит (тестовая конфигурация: Intel Core Î5-3570K 3.40 GHz / 4 Cores / 6M Cache / 8 Gb RAM / Intel С++ Compiler v. 13.0). В качестве аналогов рассматривались пакеты NTL v. 6.1.0 и MPFR v. 3.0.1.

Матричное умножение. Матрицы были плотно заполнены 239-битными псевдослучайными числами с ПТ. Время преобразования массивов в целевой многоразрядный формат не учитывалось. В результате проведения серии экспериментов среднее ускорение разработанной библиотеки составило 2.34 раза относительно MPFR и 5.93 раза относительно NTL.

Задача термодинамики. Решалась краевая задача теплопроводности с граничными условиями первого рода. Материал стержня был однородным (коэффициент теплопроводности D = 0.03). Использовалась четырехточечная явная разностная схема на сетке с равномерным шагом. Моделировалось 0.75 с процесса с постоянным шагом по пространству h = 0.001 и с различным шагом по времени: 5 мкс, 10 мкс и 15 мкс. С использованием разработанной библиотеки задача была решена быстрее в среднем в 1.51 раза по сравнению с MPFR и в 3.63 раза по сравнению с NTL.

Основные прикладные области высокоточных вычислений, в которых применение разработанных решений, предположительно, позволит повысить быстродействие: 1) решение СЛАУ больших порядков; 2) вычисление рядов Тейлора; 3) преобразование Фурье и цифровая фильтрация; 4) интерполяция полиномов высоких степеней; 5) решение жестких систем ДУ в гидродинамике, химической кинетике, теории ядерных реакторов и пр.

В заключении сформулированы основные результаты диссертационной работы. В приложениях представлены обзор и анализ высокоточного ПО; приведена структура комплекса для решения матричных задач в СОК; представлены устройства для выполнения немодульных операций; дана оценка сложности методов выполнения немодульных операций; исследована вероятность коллизии ИПХ; обоснован метод генерации смещения для алгоритма вычисления ИПХ; приведены схемы алгоритмов вычислений в МП-формате и листинги программ, а также акты о внедрении результатов.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

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

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

2. Предложен новый метод выполнения немодульных операций сравнения чисел, определения знака числа и контроля переполнения числового диапазона в системе остаточных классов на основе использования интер-вально-позиционной характеристики для быстродействующей двусторонней аппроксимации относительной величины модулярного числа. Метод обеспечивает достоверность результата и позволяет ускорить вычисления в среднем до 0.3 In раз по сравнению с методом на основе преобразования модулярных представлений в смешанную систему счисления (MRC) и в среднем до 1.39п раз по сравнению с методом ортогональных базисов (CRT), где п — количество модулей СОК. В частности, эксперименты показали увеличение скорости выполнения перечисленных немодульных опе-

раций в 32-модульной СОК в 4.11 и 7.32 раза по отношению к MRC-методу и CRT-методу, соответственно. Это является хорошей предпосылкой для реализации широкого спектра надежных алгоритмов высокоскоростной модулярной обработки.

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

4. На основе модификации техники половинного деления предложен новый итерационный метод масштабирования чисел в модулярном представлении натуральным коэффициентом 2я, позволяющий в q/{\_q!h\ +1)

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

5. Предложен новый модулярно-позиционный формат с плавающей точкой для повышения скорости при организации высокоточных арифметических вычислений на системах общего назначения, в котором многоразрядная мантисса представлена в СОК, порядок и знак — в позиционной системе счисления и впервые дополнительно включена интервально-позиционная характеристика мантиссы, что обеспечивает высокую скорость выполнения как модульных, так и немодульных операций. Для нового модулярно-позиционного формата разработаны кодировки числовых и нечисловых величин, получены выражения машинного эпсилона, функции шага числа, верхних границ погрешностей округления, разработан алгоритм подбора модулей СОК, обеспечивающих априорно заданную точность вычислений.

6. Предложены алгоритмы выполнения арифметических операций и округления многоразрядных чисел в модулярно-позиционном формате с плавающей точкой, сохраняющие высокое быстродействие как при одиночных вычислениях, так и при длительных итерационных расчетах, требующих выравнивания порядков, вычисления знака и контроля переполнения диапазона. При сравнении с аналогами получены следующие усредненные по медиане распределения показатели ускорения алгоритмов: 4.35 раза по сравнению с NTL, 1.32 раза по сравнению с MPFR и 13.15 раза по сравнению с Wolfram Mathematica. Достоинство алгоритмов - высокая степень параллелизма. Векторизация повысила быстродействие (за исключением деления) в среднем в 2.38 раза с эффективностью (отношение ускорения к числу одновременно обрабатываемых операндов) 0.60. Относительно применения алгоритмов сформулированы рекомендации.

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

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

ОСНОВНЫЕ ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ Публикации в изданиях, рекомендованных ВАК РФ

1. Исупов, К. С. Инструментальный комплекс для проектирования параллельных масштабируемых программ численных расчетов / К. С. Исупов, В. С. Князьков // Научно-технический вестник СПбГУ ИТМО / гл. ред. - д-р техн. наук, проф. В. О. Никифоров. - 2010. - № б (70). - С. 68-72.

2. Исупов, К. С. Табличный метод прямого преобразования двоичных чисел в систему остаточных классов с модулями {2AF - 1} / К. С. Исупов, В. С. Князьков // Фундаментальные исследования. - 2012. - № 9, ч. 4. - С. 909-917.

3. Исупов, К. С. Метод выполнения немодульных операций в системе остаточных классов на основе интервальных позиционных характеристик / К. С. Исупов // Фундаментальные исследования. -2013. -№ 4, ч. 3. - С. 566-570.

4. Исупов, К. С. Способ уточненного вычисления приближенной позиционной характеристики для выполнения немодульных операций в системе остаточных классов / К. С. Исупов // Фундаментальные исследования. - 2013. - № 4, ч. 4. - С. 796-800.

5. Исупов, К. С. Методика выполнения базовых немодульных операций в модулярной арифметике с применением интервальных позиционных характеристик / К. С. Исупов // Известия высших учебных заведений. Поволжский регион. Технические науки. - 2013. - № 3 (27). - С. 26-39.

6. Исупов, К. С. Алгоритм вычисления интервально-позиционной характеристики для выполнения немодульных операций в системах остаточных классов / К. С. Исупов // Вестник ЮУрГУ. - 2014. - Т. 14, № 1. - С. 89-97. - (Компьютерные технологии, управление, радиоэлектроника).

7. Исупов, К. С. Об одном алгоритме сравнения чисел в системе остаточных классов / К. С. Исупов // Вестник АГТУ. - 2014. - № 3. - С. 40-49. - (Управление, вычислительная техника и информатика).

Публикации в других изданиях

8. Исупов, К. С. Система остаточных классов как инструмент для выполнения параллельных высокоточных численных расчетов / К. С. Исупов, В. С. Князьков // Математическое моделирование развивающейся экономики, экологии и биотехнологий (ЭКОМОД-2010) : сб. тр. V Всерос. науч. конф. (5-11 июля 2010 г.). - Киров : Изд-во ВятГУ, 2010.-С. 79-88.

9. Исупов, К. С. Построение эффективных методов параллельного выполнения численных расчетов на основе полиномиальной системы классов вычетов [Электронный

ресурс] / К. С. Исупов // Научный сервис в сети Интернет: суперкомпьютерные центры и задачи : тр. Междунар. суперкомпьютерной конф. (г. Новороссийск, 20-25 сентября 2010 г.). - М.: Изд-во МГУ, 2010. - С. 642-649. - 1 электрон, опт. диск (CD-ROM).

10. Исупов, К. С. Современный подход к решению «некорректных» математических задач / К. С. Исупов // Высокопроизводительные параллельные вычисления на кластерных системах (НРС-2010) : материалы X Междунар. конф. (1-3 ноября 2010 г.) : в 2 т. - Пермь : Изд-во ПермГТУ, 2010. - Т. 1. - С. 294-302.

11. Исупов, К. С. Параллельные вычисления над многоразрядными числами в системе остаточных классов [Электронный ресурс] / К. С. Исупов // Научный сервис в сети Интернет: экзафлопсное будущее : тр. Междунар. суперкомпьютерной конф. (г. Новороссийск, 19-24 сентября 2011 г.). - М. : Изд-во МГУ, 2011. - С. 534-540. -1 электрон, опт. диск (CD-ROM).

12. Исупов, К. С. Способ и программный пакет для организации разрядно-параллельных вычислений с плавающей точкой высокой точности [Электронный ресурс] / К. С. Исупов // Научный сервис в сети Интернет: поиск новых решений : тр. Междунар. суперкомпьютерной конф. (г. Новороссийск, 17-22 сентября 2012 г.). -М. : Изд-во МГУ, 2012. - С. 718-730. - 1 электрон, опт. диск (CD-ROM).

13. Исупов, К. С. Использование модулярно-позиционных представлений для высокоточных вычислений с плавающей точкой / К. С. Исупов, В. С. Князьков,

A. В.Логинов // Суперкомпьютерные системы и их применение (SSA'2012) : доклады Четвертой Междунар. науч. конф. (23-25 октября 2012 г.). - Минск : ОИПИ HAH Беларуси, 2012. - С. 79-83.

14. Исупов, К. С. Модулярно-позиционный формат и программный пакет для разрядно-параллельных вычислений высокой точности в формате с плавающей точкой / К. С. Исупов // Вестник ЮУрГУ. - 2013. - Т. 2, № 1. - С. 65-79. - (Вычислительная математика и информатика).

15. Исупов, К. С. Программный пакет высокоточных модулярно-позиционных вычислений с плавающей точкой / К. С. Исупов, В. С. Князьков // Advanced Science. -Киров : Изд-во ВятГУ, 2013.-№3,-С. 150-171.

16. Исупов, К. С. Выполнение немодульных операций в системе остаточных классов на основе интервальных позиционных характеристик / К. С. Исупов,

B. С. Князьков // Перспективные научные исследования - 2013 : материалы IX Междунар. науч.-практ. конф. (г. София, Болгария, 17-25 февраля 2013 г.). - София : «Бял ГРАД-БГ» ООД, 2013. - Т. 27. - С. 17-25.

Свидетельства о регистрации программ для ЭВМ и патент

17. Свидетельство о государственной регистрации программы для ЭВМ № 2012611793. Программа для выполнения высокоточных параллельных операций матричной алгебры / К. С. Исупов, В. С. Князьков. - Зарег. в Реестре программ для ЭВМ 16.02.2012.

18. Свидетельство о государственной регистрации программы для ЭВМ № 2013613857. Выполнение высокоточной операции умножения вещественных чисел в модулярно-позиционном формате с плавающей точкой / К. С. Исупов, В. С. Князьков, А. Н. Мальцев, А. В. Логинов. - Зарег. в Реестре программ для ЭВМ 17.04.2013.

19. Свидетельство о государственной регистрации программы для ЭВМ № 2013613858. Выполнение высокоточной операции сложения вещественных чисел в модулярно-позиционном формате с плавающей точкой / К. С. Исупов, В. С. Князьков, А. Н. Мальцев, А. В. Логинов. - Зарег. в Реестре программ для ЭВМ 17.04.2013.

20. Свидетельство о государственной регистрации программы для ЭВМ № 2013615425. Выполнение преобразования величин из двоичных (float, double, mpfr) в модулярно-позиционный формат / К. С. Исупов, В. С. Князьков, А. Н. Мальцев, А. В. Логинов. - Зарег. в Реестре программ для ЭВМ 10.06.2013.

21. Свидетельство о государственной регистрации программы для ЭВМ № 2013615428. Выполнение операции сравнения вещественных чисел в модулярно-позиционном формате с плавающей точкой / К. С. Исупов, В. С. Князьков, А. Н. Мальцев, А. В. Логинов. - Зарег. в Реестре программ для ЭВМ 10.06.2013.

22. Свидетельство о государственной регистрации программы для ЭВМ № 2013661592. Выполнение немодульных операций в системах остаточных классов с использованием метода интервальных позиционных характеристик / К. С. Исупов, А. Н. Мальцев. - Зарег. в Реестре программ для ЭВМ 11.12.2013.

23. Свидетельство о государственной регистрации программы для ЭВМ № 2013661911. Выполнение высокоточных арифметических операций с плавающей точкой с использованием систем счисления в остаточных классах / К. С. Исупов, А. Н. Мальцев. - Зарег. в Реестре программ для ЭВМ 18.12.2013.

24. Пат. № 2509345 Российская Федерация, МПК G 06 F 7/72. Способ организации выполнения операции умножения двух чисел в модулярно-позиционном формате представления с плавающей точкой на универсальных многоядерных процессорах / Исупов К. С., Князьков В. С. - Выдан 10.03.2014 г., Бюл. № 7.

МЕТОДЫ И АЛГОРИТМЫ ОРГАНИЗАЦИИ ВЫСОКОТОЧНЫХ ВЫЧИСЛЕНИЙ В АРИФМЕТИКЕ ОСТАТОЧНЫХ КЛАССОВ ДЛЯ УНИВЕРСАЛЬНЫХ ПРОЦЕССОРНЫХ ПЛАТФОРМ

Специальность 05.13.15 - Вычислительные машины, комплексы и компьютерные сети

Редактор Т. Н. Судовчихина Компьютерная верстка Р. Б. Бердниковой

Подписано в печать 08.10.2014. Формат 60х84'Лб. Усл. печ. л. 1,16. Заказ № 2606. Тираж 120.

Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «Вятский государственный университет» 610000, г. Киров, ул. Московская, 36. Тел.: (8332) 64-23-56, http://vyatsu.ru

Научное издание

Исупов Константин Сергеевич