Методы вычислений с гарантированной точностью на платформе "Мультикор" тема диссертации и автореферата по ВАК РФ 05.13.11, кандидат технических наук Захаров, Андрей Вениаминович

• Захаров, Андрей Вениаминович
• кандидат технических наук
• 2007

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

ВВЕДЕНИЕ.

ГЛАВА 1. Арифметика чисел с плавающей точкой.

1.1. Введение.

1.2. Платформа «Мультикор».

1.2.1. Система инструкций.

1.2.2. Ассемблер DSP.

1.2.3. Системные особенности.

1.3. Стандарт IEEE-754.

1.4. Модели плавающих арифметик.

1.4.1. Определения.

1.4.2. Доказательство реализаций.

1.5. Элементарные функции.

1.6. Применение.

1.7. Выводы.

ГЛАВА 2. Формат расширенной точности.

2.1. Введение.

2.2. Базовые определения.

2.3. Сложение (вычитание).

2.4. Деление.

2.5. Операция извлечения квадратного корня.

2.5.1. Выбор начального приближения.

2.5.2. Трудные для округления случаи.

2.5.3. Алгоритм SQRT.

2.6. Элементарные функции.

2.7. Выводы.

ГЛАВА 3. Формат двойной точности.

3.1. Введение.

3.2. Базовые определения.

3.3. Сложение (вычитание).

3.4. Умножение.

3.5. Деление.

3.5.1. Деление без восстановления остатка.

3.5.2. Деление SRT по основанию 4.

3.5.3. Деление с большим основанием.

3.6. Элементарные функции.

3.6.1. CORDIC-алгоритмы.

3.6.2. Алгоритмы редукции.

3.7. Выводы.

ГЛАВА 4. Применение гарантированной точности.

4.1. Введение.

4.2. Тестовый пакет Paranoia.

4.3. Анализ основания и разрядности.

4.3.1. Целочисленный алгоритм.

4.3.2. Бесконечные периодические дроби.

4.4. Корректность округления.

4.5. Корректность использования остатка.

4.6. Выводы.

Введение диссертации (часть автореферата) на тему «Методы вычислений с гарантированной точностью на платформе "Мультикор"»

Актуальность темы.

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

Основными производителями микропроцессорных средств в настоящее время являются зарубежные фирмы. В связи с этим важным явлением стало появление новой архитектуры - «Мультикор», перспективной отечественной разработки, способной конкурировать с зарубежными. Данная архитектура представлена серией сигнальных микроконтроллеров - в частности, микросхемами 1892ВМЗТ (МС-12) и 1892ВМ2Т (МС-24) [multicore]. Это однокристальные программируемые многопроцессорные «системы на кристалле» на базе IP-ядерной платформы, разработанной в НПЦ «Элвис». В качестве основного процессора используется RISC-подобное ядро с архитектурой MIPS32 [mips]; под его управлением работают один или более DSP-акселераторов.

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

Арифметические операции с плавающей точкой образуют базис для построения на их основе очень большого количества вычислительных алгоритмов, которые должны учитывать особенности архитектуры. К ним относятся алгоритмы линейной алгебры [Li02], подпрограммы для вычисления корней полиномов и более сложных функций и т.п. [БибердорфО!]. Кроме этого, отметим, что центральным аспектом для всех платформ является наличие реализаций различных элементарных функций, таких как тригонометрические или экпоненциально-логарифмические. Заметим, что в последние годы наблюдается тенденция к отходу от аппаратных реализаций таких функций в сторону программных [Harrison99a, GreerOl]. Благодаря этому обеспечивается гибкость в процессе разработки, снижается стоимость и увеличивается открытость архитектуры в целом.

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

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

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

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

В настоящее время перечисленные выше проблемы являются актуальными и находятся в стадии решения не только для платформы «Мультикор», но и для других DSP-платформ [Bertin04, Iordache03].

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

Цель диссертационной работы.

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

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

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

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

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

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

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

Научная новизна работы.

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

• получены характеристики реализации базовых арифметических подпрограмм в формате двойной точности стандарта IEEE-754;

• исследованы таблично-алгоритмические реализации элементарных функций в нестандартном формате расширенной точности и реализации базовых арифметических подпрограмм в том же формате;

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

Практическая значимость работы.

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

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

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

Использование результатов работы.

Практически все базовые подпрограммы реализованы и внедрены на стадии разработки специализированного математического обеспечения в НПЦ «Элвис» для платформы «Мультикор». Получен соответствующий акт о внедрении результатов.

Полученные результаты используются в курсе «Математические основы обработки сигналов» в части применения сигнальных процессоров и их математического обеспечения в НОУ Институт программных систем -Университет города Переславля.

Апробация работы.

Основные результаты диссертационной работы докладывались и обсуждались на научных семинарах кафедры информационных технологий факультета физико-математических наук Российского университета дружбы народов и на следующих конференциях: "Авиация и космонавтика-2003" (ноябрь 2003, МАИ, г. Москва), "Программные системы и приложения" (май 2004, г. Переславль-Залесский, ИПС РАН), XLI и XLII всероссийских конференциях по проблемам математики, информатики, физики и химии в секции «Программные системы» (апрель 2005,2006 г., РУДН, г. Москва).

Структура и объем диссертации.

Диссертационная работа состоит из введения, четырех глав, заключения и приложения. Во введении обосновывается актуальность темы диссертационной работы, сформулированы основные цели и задачи исследования, его научная новизна и практическая значимость. Первая глава диссертации посвящена обзору литературы по вычислениям с плавающей точкой. Здесь описываются основные подходу к анализу погрешностей, обсуждаются различные оценки гарантированности результатов. Кроме того, описываются существенные черты вычислительной платформы «Мультикор» и приводятся данные по двум архитектурам аналогичного класса для сравнительного анализа [Bertin04, Iordache03], Вторая глава посвящена исследованию вопросов реализации арифметических подпрограмм с гарантированным результатом в нестандартном формате расширенной точности [ЗахаровОб]. В этой главе получены доказательства корректности пяти базовых арифметических операций. Кроме того, исследована реализуемость таблично-алгоритмических способов вычисления элементарных функций [Tang91] на целевой платформе. В третьей главе диссертации анализируется построение библиотеки арифметических подпрограмм в формате двойной точности. Показано, что возвращаемый результат соответствует стандарту IEEE-754 на вычисления с двоичной плавающей точкой [ieee754]. Рассматриваются способы реализации элементарных алгебраических функций с быстрым предварительным масштабированием. В главе четвертой приведены примеры того, как реализация арифметики гарантированной точности позволяет доказывать утверждения относительно высокоуровневых алгоритмов. В заключении сформулированы

Заключение диссертации по теме «Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей», Захаров, Андрей Вениаминович

Заключение

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

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

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

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

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

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

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

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

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

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

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

Список литературы диссертационного исследования кандидат технических наук Захаров, Андрей Вениаминович, 2007 год

1. Амелькин. Амелькин С.А., Захаров А.В., Хачумов В.М. Обобщенное расстояние Евклида-Махаланобиса и его свойства. // Информационные технологии и вычислительные системы. №4,2006, с.40-44.

2. Байков75.: Байков В. Д., Смолов В.Б. Аппаратурная реализация элементарных функций в ЦВМ. Ленинград: Издательство ЛГУ, 1975.

3. Бибердорф01.: Бибердорф Э.А., Попова Н.И. Решение линейных систем с гарантированной оценкой точности результатов. Часть первая. Институт ядерной физики им. Г. И. Будкера СО РАН, Новосибирск, 2001.

4. Ершов04.: Ершов А.Г., Кашеварова Т.П. Интервальная математическая библиотека, основанная на разложениях в ряды Чебышева и Тейлора. Сборник трудов Международной Конференции по Вычислительной Математике, с. 201-209, 2004.

5. Захаров04.: Захаров А.В., Хачумов В.М. Алгоритмы CORDIC. Современное состояние и перспективы. Программные системы: теория и приложения, М.: Физматлит, май 2004, с. 353-372.

6. ЗахаровОб.: Захаров А.В. Обзор поддержки плавающей точки в формате расширенной точности на платформе «Мультикор». // Труды XLII всероссийскойконференции по проблемам математики, информатики, физики и химии. М.: Издательство РУДН, 2006, с. 46-66.

7. Каханер98.: Каханер Д., Моулер К., Нэш С. Численные методы и программное обеспечение.: Пер. с англ. М.: Мир, 1998. - 575 с.

8. ТаненбаумОб.: Таненбаум Э. Архитектура компьютера. 4-е издание. СПб.: Питер, 2006.-699 с.

9. УорренОЗ.: Уоррен Г. Алгоритмические трюки для программистов.: Пер. с англ. -М.: Издательский дом «Вильяме», 2003. 288 с.

10. Bertin04.: Bertin С. et al. A floating-point library for integer processors. Tech. report #5268, July 2004.

11. Boldo03.: Boldo S., Daumas M. A simple test qualifying the accuracy of Horner's rule for polynomials. Tech. report #4707,38 p., Jan. 2003.

12. Cornea98.: Cornea-Hasegan M. Proving the IEEE correctness of iterative floating-point square root, divide and remainder algorithms. Intel Technology Journal, 1998-Q2:1-11,1998.

13. Darcy98.: Darcy J.D., Kahan W. How java's floating-point hurts everyone everywhere. ACM 1998 workshop on java for high-performance computing, Stanford, 1998.

14. Daumas04.: Daumas M., Boldo S. Properties of two's complement floating-point notations International Journal on Software Tools for Technology Transfer, Vol. 5, issue 2, March 2004.

15. Daumas02.: Daumas M., Boldo S. Necessary and sufficient conditions for exact floating point operations. Tech. report #4644.18p. Nov. 2002.

16. Defour04.: Defour D., Hanrot G., Lefevre V., Muller J.-M., Revol N. and Zimmermann P. Proposal for a Standardization of Mathematical Function Implementation in FloatingPoint Arithmetic. Research Report 5406, INRIA, 2004.

17. DefourOl.: Defour D., Kornerup P., Muller J.-M., Revol N. A new range reduction algorithm, Technical report #4267, 2001.

18. Ercegovac99.: Ercegovac M., Imbert L., Matula D., Muller J.-M., Wei G. Improving Goldschmidt division, square root and square root reciprocal. Tech. report #3753. Sept.1999.

19. Goldberg91.: Goldberg D. What every computer scientist should know about floatingpoint arithmetic. ACM Computing Surveys, 23(1): 5-47, March 1991.

20. Graca06.: Graca G. Da, Defour D. Implementation of float-float operators on graphics hardware. Proc. of 7th conference on Real Numbers and Computers, RNC7, Nancy, France, July 2006.

21. GreerOl.: Greer В., Harrison J., Henry G., Li W., Tang P.T.P. Scientific computing on the Itanium TM processor. Proc. Of the 2001 ACM/IEEE conference on Supercomputing, 2001.

22. GuyOO.: Guy E., Wolfgang P. On the design of IEEE-754 compliant floating point units. IEEE Transactions on computers, Vol.49, issue 5, pp. 398-413, May 2000.

23. GuyOl.: Guy E., Seidel P.-M. On the design of fast IEEE floating-point adders. In proc.th

24. Of the 15 International Symposium on Computer Arithmetic, 2001.

25. HarrisonOO.: Harrison J. Formal verification of IA-64 division algorithms. Proc. Of the 13th International Conference on Theorem Proving in higher order logics, 2000.

26. Harrison99.: Harrison J. A machine-checked theory of theory of floating-pointarithmetic. In Y. Bertot, G. Dower, A. Hirschowitz, C. Paulin, and L. Thery, editors,th

27. Theorem proving in higher order logics: 12 international conference, p. 113-130, Nice, France, Sept. 1999, Springer-Verlag.

28. Harrison03.: Harrison J. Formal verification of square root algorithms. Formal methods in system design, vol.22, issue 2, pp. 143-153, March 2003.

29. Harrison99a.: Harrison J., Kubaska Т., Story S., and Tang P.T.P. The computation of transcendental functions on the IA-64 architecture. Intel Technology Journal, (Q4):l-7, November 1999.

30. Iordache03.: Iordache C., Tang P.T.P. An overview of floating-point support and math library on the Intel XScale Architecture. In proc. Of the 16th IEEE Symposium on computer arithmetic, pp. 122-128, June 2003.

31. Kahan05.: Kahan W. A logarithm too clever by half. Available electronically at /~wkahan/LOG 10HAF.txt.

32. КогпегирОЗ.: Kornerup P., Muller J.-M. Choosing starting values for Newton-Raphson computation of reciprocals, square-roots and square-root reciprocals. Tech. report #4687, Jan. 2003.

33. Li03.: Li R.-C., Boldo S. and Daumas D. Theorems on efficient argument reductions. Proc. Of the 16th IEEE Symposium on Computer Arithmetic, 2003.

34. Li02.: Li X.S., Demmel J.W., Bailey D.H., Henry G., et al. Design, Implementation and testing of extended and mixed precision BLAS. ACM Transaction on Mathematical Software, Vol. 28, No. 2, pp. 152-205, June 2002.

35. Markstein97.: Markstein P., Karp A.P. High precision division and square root. ACM Transactions on Mathematical Software, Vol. 23, num. 4, pp. 561-589,1997.

36. Muller03.: Muller J.-M., Brisebarre N. Finding the "truncated" polynomial that is closest to a function. Tech. report #4787, 15 pages Avr. 2003.

37. Muller05.: Muller J.-M. On the definition of ulp(x). Tech. report #5504. 16 p. Feb. 2005.43. multicore. http://multicore.ru/

38. Ng92.: K.C. Ng. Argument reduction for huge arguments: good to the last bit. Technical report, SunPro, 1992.

39. Nickmehr05.: Nickmehr H. Architectures for floating-point division. Ph.D., The university of Adelaide Australia, p. 241, Aug. 2005.

40. Oberman97.: Oberman S.F., Flynn M.J. Division algorithms and implementations. IEEE transactions on computers, 48(6): 833-854, Aug. 1997.

41. Priest91.: Priest, Douglas M. Algorithms for arbitrary precision floating point arithmetic. Proceedings of the 10th {IEEE} Symposium on Computer Arithmetic, pp. 132-144,1991.

42. Priest92.: Priest, Douglas M. On properties of floating point arithmetic: numerical stability and the cost of accurate computations. Draft of PhD Thesis, Berkeley, Nov. 1992.

43. Russinoff98.: Rusinoff, David M. A mechanically checked proof of IEEE compliance of the floating point multiplication, division, and square root algorithms of the AMD-K7 processor. LMS Journal of Computation and Mathematics, Vol. 1,1998.

44. Schulte99.: Schulte M. J., Stine J. E. Approximating elementary functions with symmetric bipartite tables. IEEE Transactions on computers, Vol. 48, No. 8, Aug. 1999.

45. Shewchuk97.: Shewchuk J. R. Adaptive precision floating-point arithmetic and fast robust geometric predicates. Discrete & Computational Geometry 18:305-363,1997.

46. Story99.: S. Story, P.T.P. Tang. New algorithms for improved transcendental functions on IA-64. Proc. 14th IEEE Symposium on Computer Arithmetic, 1999.

47. Sun.: Numerical computation guide by Sun.

48. Tang91.: Tang P.T.P. Table-Lookup algorithms for elementary functions and their error analysis. In P. Kornerup and D.W. Matula, editors, Proc. Of the 10th IEEE symposium on Computer Arithmetic, pp. 232-236, Grenoble, France, June 1991.

49. Tang89.: Tang P.T.P. Table-driven implementation of the exponential function in IEEE floating-point arithmetic. ACM Transactions on Mathematical Software, vol. 15, No. 2, pp. 144-157, June 1989.

50. Tang90.: Tang P.T.P. Table-driven implementation of the logarithm function in IEEE floating-point arithmetic. ACM Transactions on Mathematical Software, vol. 16, No. 4, pp. 378-400, Dec. 1990.

51. Tang92.: Tang P.T.P. Table-driven implementation of the expml function in IEEE floating-point arithmetic. ACM Transactions on Mathematical Software, vol. 18, No. 2, pp. 211-222, June 1992.

52. Volder59.: Voider J.E. The Cordic trigonometric computing technique. IRE Transactions on Electronic Computers. Vol. 8, pp. 330-334,1959.

53. Walther71.: Walther J.S. A unified algorithm for elementary functions. Proc. Spring Joint Computer Conference, pp. 379-385,1971.60. arm.: www.arm.com61. mips.: www.mips.com62. paranoia.: www.netlib.org/paranoia/1. Список иллюстраций

54. Рис. 1.1. Функциональная схема сложения (вычитания) чисел в формате расширенной точности: переполнение мантиссы, ненормализованная мантисса и обработка возможной потери значащих битов.

55. Рис. 1.2. Функциональная схема деления в формате расширенной точности: Step 1,2-первые две итерации, Step 3,4- третья и четвертая итерации.

56. Рис. 1.3. Функциональная схема алгоритма извлечения квадратного корня: Step 1,2-первая и вторая итерации, Step 3 третья итерация, Step 4 - переход к вычислению квадратного корня.

57. Рис. 1.4. Функциональная схема алгоритма возведения двойки в степень: Stepl редукцияаргумента, Step2 полиномиальная аппроксимация, Step3 - восстановление результата.

58. Рис. 2.1. Функциональная схема сложения чисел в формате двойной точности.

59. Рис. 2.2. Функциональная схема умножения чисел в формате двойной точности.

60. Рис. 2.3. Деление в формате двойной точности: Step 1 предварительноемасштабирование, Step 2 три итерации по основанию = 219, Step3 - округлениерезультата.