Структурно-алгоритмические методы организации высокоточных вычислений на основе теоретических обобщений в модулярной системе счисления
Диссертация
Особенно сильно потребность в высокоточных вычислениях появляется при решении задач с разномасштабными коэффициентами, например, в наноэлектронике, и др. областях. Увеличение точности вычислений в два и более раз по сравнению с точностью, поддерживаемую современными ЭВМ приводит к резкому росту времени вычислений т.к. традиционные алгоритмы высокоточных вычислений последовательные. Применение… Читать ещё >
Содержание
- ГЛАВА 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. Сводная таблица результатов и структурно-алгоритмические принципы обеспечения высокоточных вычислений
Список литературы
- Амербаев В.М. Теоретические основы машинной арифметики.- Алма-Ата: Наука, 1986, — 224 с.
- Акушский Н. Я, Юдицкий Д. И. Машинная арифметика в остаточных классах, М. «Сов. радио „, 1968. 439 с.
- Аль Массри. М.И. Разрядно-параллельные процессоры обработки вещественных чисел в непозиционных системах счисления. Дисс. на соиск. уч. степ, к.т.н. Л.: ЛЭТИ, 1993, — 208 с.
- Амосов A.A., Дубинский Ю. А., Копченова Н. В. Вычислительные методы для инженеров. М.: „Высшая школа“, 1994. — 544 с.
- Акритас А. Основы компьютерной алгебры с приложениями. М.: Мир, 1994. 543 с.
- Барабанов И.Н. Спутниковые навигационные системы GPS и GLONASS. http://www.intuit.ru/video/7/
- Воеводин В.В. Математические основы параллельных вычислений.www.parallel.ru/info/voevodin.doc.
- Виноградов И.М. Основы теории чисел. М.: „Наука“, 1972. — 456 с.
- Воеводин В. В, Воеводин Вл.В. Параллельные вычисления. СПб.: БХВ-Петербург, 2002. — 608 с.
- Ю.Воеводин В. В. Вычислительные основы линейной алгебры. М.: „Наука“, 1977. -303 с.
- Воеводин В.В. Линейная алгебра. М.: „Наука“, 1980. -400 с.
- Воеводин В.В. Математические модели и методы в параллельных процессах. М.: „Наука“, 1986. — 296 с.
- Герасименко А. А, Федин В. Т. Передача и распределение электрической энергии. Ростов- н./Д.: Феникс- Красноярск: Издательские проекты, 2006. — 720 с.
- Грегори Р., Кришнамурти Е. Безошибочные вычисления. Методы и приложения. М.: Мир, 1988. 207 с.
- Грэхем P, Кнут Д, Паташник О. Конкретная математика. Основание информатики: Пер. с англ. М.: „Мир“, 1998. — 703 с.
- Григоренко В.П. Об одном методе решения нелинейных краевых задач, описывающих распределение неосновных носителей в базе полупроводниковой структуры // ВМиМФ, 1975, с.923−930.
- Дискретное преобразование Фурье — Википедия.ru. wikipedia. org/. ./ДискретноепреобразованиеФурье.
- Живич М., Каннингэм Р. Истинная цепа программных ошибок // Открытые системы. 2009.ЖЗ.
- Дмитрий Чеканов nVidia CUDA: вычисления на видеокарте или смерть CPU?. Tom’s Hardware, www.thg.ru/graphic/nvidiacuda/nvidiacuda01.html
- Дзегелёнок И. И, Оцоков Щ. А. Подход к решению проблемы безошибочных вычислений с использованием ускоренного алгоритма отображения дробей Фарея. // Труды научной конференции, посвященной 75-летию со дня рождения академика В. А. Мельникова. РАН. М. 2004.
- Дзегелёнок И.И., Оцоков Ш. А. Экспериментальное исследование модели безошибочных вычислений на ПМК-сети КУРС 2000 // Сб. трудов международной научной конференции „Информационные средства и технологии“ М.:МЭИ (ТУ), 2003.- С. 103−106.
- Дзегелёнок И. И, Оцоков Ш. А. Абдулатиф О. А., Ильин П. Е., Ильин И. В. Декомпозиционный подход к осуществлению Grid-технологий. М., Физматлит, „Информационная математика“ № 1(5), 2005.
- Дзегеленок И.И., Мазуренко A.K, Оцоков Ш. А. Подход к численному воспроизведению моделей альтернативной энергетики. // Сб. научных трудов ВЭИ, М., 2006.
- Ильин В.П. Линейная алгебра: от Гаусса до суперкомпьютеров. http://nature.web.ru/db/msg.html?mid=l 178 356&uri=page2.html
- Ирхин В.П. Теоретическое обобщение и разработка методов построения пепозиционных модулярных спецпроцессоров: Диссерт. на соиск. учен, степени д.т.н. / Воронеж, 1999.
- Мисриханов М.Ш. Инвариантное управление динамическими системами. Алгебраический подход. М:. Энергоатомиздат, 2003.
- Михелович Ш. Х. Теория чисел. М. „Высшая школа“, 1962. 259 с.
- Михлин С.Г. Некоторые вопросы теории погрешностей. Л.: Издательство Ленинградского университета. 1988. — 333 с.
- Кобзаренко Д.Н., Аскеров С. Я. Внутреннее отсечение триангуляционного объекта, проецируемого на плоскость XY. // Геоинформационные технологии, № 4 2008.
- Коляда A.A. Модульные структуры конвейерной обработки числовой информации. Минск: Университетское, 1990.- 331 с.
- Коляда A.A. Модулярные структуры конвейерной экспресс обработки цифровой информации в измерительно-вычислительных системах физического эксперимента. / Диссерт. на соиск. учен, степени д.т.н. — Минск: 1991.
- Кулиш У., Рац Д., Хаммер Р., Xoicc М. Достоверные вычисления и их компьютерная реализация. РХД., 2005. 450 с.
- Литвинов ГЛ., Родионов А. Я., Чуркин A.B. Приближенная рациональная арифметика с контролируемыми ошибками округления// Вычислительные технологии, т.6, № 5 2001.
- Мак-кракен Д., Дорн У. Численные методы и программирование на фортране. М.: Мир, 1977, 584 с.
- Неочевидные особенности вещественных чисел.www.delphi1cingdoni.com/asp/viewitem.asp?catalogid:=374
- Нуссбаумер Г. Быстрое преобразование Фурье и алгоритмы вычисления сверток. М.: РАДИО И СВЯЗЬ, 1985
- Орлов ДА., Оцоков Ш. А. О возможности применения „безошибочных“ вычислений для решения задачи Коши // Сб. трудов международной научной конференции „Информационные средства и технологии“ М.:МЭИ (ТУ), 2006. 207−210.
- Оцоков Ш. А. Критерий целочисленности результата арифметических операций с плавающей точкой. // Информационные технологии7.2007, с. 50−52.
- Оцоков Ш. А. Нейронный алгоритм расширения диапазона представления результатов безошибочных вычислений. // Нейрокомпьютеры: разработка и применение, № 12 2004.
- Оцоков Ш. А. О возможности обобщения параллельной модулярной арифметики для работы с двоичными дробями. // Вычислительные сети, теория и практика 2007, Номер 2, (11).
- Оцоков Ш. А. Структурная организация нейропроцессора с использованием модели безошибочных вычислений. // Нейрокомпьютеры: разработка и примеиение, № 12 2004.
- Оцоков Ш. А. Алгоритм ускоренного отображения дробей Фарея в систему остаточных классов. // Вестник Дагестанского научного центра РАН, № 19−2004, с.40−43
- Оцоков Ш. А. Обобщение вычислений над полем комплексных чисел сисключением ошибок округления // Информационные технологии, № 6−2009, с. 17−23.
- Оцоков Ш. А. Применение модулярной арифметики с фиксированной точкой для ослабления влияния ошибок округления компьютерных вычислений. // Информационные технологии, № 12 2009/
- Оцоков Щ.А., Мугутдинова Х. М. Устройство для округления числа в системе остаточных классов. Патент РФ № 2 305 861., опубл. 10.09.2007.
- Оцоков Ш. А., Шухман И. М. Устройство для преобразования числа из системы остаточных классов в позиционный код. Патент РФ № 2 235 423., опубл. 27.08.2004.
- Ортега Дж., Пул У. Введение в численные методы решения дифференциальных уравнений. М. 1986. -288 с.
- Петров Ю.П. Как получать надежные решения систем уравнений. СПб.: BHV-СПб, 2009.- 176 с.
- Пи кипа Г. А. Математические модели технологических объектов. М.: Изд. дом МЭИ, 2008
- Поспелов Д. А. Арифметические основы вычислительных машин дискретного действия . М.: Высшая школа, I960-
- Сахшок П.А., Червяков Н. И., Шапошников А. В. Модулярные вычислительные структуры пейропроцессорных систем.: Учебное55. пособие М.: Физматлит, 2003
- Стренг Г. Линейная алгебра и ее применения. Мир, 1980.
- How Futile are Mindless Assessments of Roundoff in Floating-Point Computation?“, William Kahan. ttp://www.cs.berkeley.edu/~wkahan/Mindless.pdf
- Тихонов A.Ii. Арсенин В .Я. Методы решения некорректных задач. — М.: Наука, 1979. г1У.. --—
- Тягунов Олег Аркадьевич Развитие технологий анализа, многокритериальной оптимизации и моделирования многосвязных мехатронных систем управления. Дисс. на соиск. уч. степ. д.т.н.М: МИРЭА, 2009
- Уоткинс Д. Основы матричных вычислений. М.: Бином, 2006, 660 с.
- Финько О.А. Модулярная арифметика параллельных логических вычислений: Монография / Под ред. В. Д. Малюгина. — М.: ИПУ РАН, 2003. —224 с.
- Форсайт Дж., Молер К. Численное решение систем линейных алгебраических уравнений. М.: Мир, 1969
- Хамахер К., Вранешич 3., Заки С. Организация ЭВМ. 5-е изд. Спб.: Питер- Киев: Издательская группа BHV, 2003. 848 с.
- Чарыков, IT. А. Учебное пособие по курсу „Физика полупроводниковых приборов и компонент интегральных схем“: Физические явления в р-п-переходах / Н. А. 41. Чарыков, Ред. К. В. Шалимова, Моск. энерг. ин-т (МЭИ). М.: Изд-во МЭИ, 1982. — 80 с.
- Ясницкий JI.H. Введение в искусственный интеллект. М.: Изд. центр „Академия“, 2005.
- Яненко Н.Н. Введение в разностные методы математической физики. 4.1,2. Новосиб. гос. ун-т, 1968
- Яценков B.C. Основы спутниковой навигации. Системы GPS NAVSTAR и ГЛОНАСС. М.: Горячая Линия Телеком, 2005 г. — 272 с.
- 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.
- 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.
- A. Edalat and F. Rico. Two Algorithms for Root Finding in Exact real Arithmetic. Third Real Numbers and Computers Conference, 27−44, (1998).
- Blanck, J.:Exact real arithmetic systems: Results of competition, Computability and Complexity in Analysis, Lecture Notes in Computer Science, Vol. 2064, (2001) 390−394
- 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
- Blum L., Cucker F., Shub M. and Smale S. Complexity and real computation, New York: Springer-Verlag. (1998).
- 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).
- 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.
- 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.
- 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.
- David H. Bailey, Yozo Hida, Xiaoye S. Li and Brandon Thompson, „ARPREC: An Arbitrary Precision Computation Package,“ technical report LBNL-53 651, software and documentation available at http://crdl.bl.gov/~dhbailey/mpdist.
- D.M. Priest: Algorithms for Arbitrary Precision Floating Point Arithmetic. Lrx Proceedings of the J 0th Symposium on Computer Arithmetic, 1991.
- D. H. Bailey: High-precision Floating-point Arithmetic in Scientific Computation. Computing in Science and Engineering, May-June 2005.
- David H. Bailey. Resolving Numerical Anomalies in Scientific1. wrence Berkeley National Laboratory, 2008.
- David H. Bailey. High-Precision Computation and Mathematical Physics. Lawrence Berkeley National Laboratory, 2009.
- 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
- 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.
- 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.
- 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.
- D.H. Bailey and S. Robins, „Highly Parallel, High-Precision Numerical Integration,“ Computational Research Division, Berkeley
- Lab Computing Sciences, 2004- http://crd.lbl.gov/~dhbailey/ dhbpapers/quadparallel.pdf.
- 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.
- Floating Point Arithmetic,» Proceedings of ARITIT-15, IEEE Computer Society, 2001.
- 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.
- Gregory R. T. A. method for and an application of error-free com/p
- Proceedings of the AFCET Symposium «Mathematics for CZ Science». Paris, 152−158, 1982.
- Gregory R. T. Error-free computation with rational numbers. BIT, 2 3 194−202.
- Gregory R. T. Exact computation with order-N Farey fractions. CZ
- Science and Statistics: Proceedings of the 15th Symposium on the Int"e E. Gentle Editor, North Holland, Amsterdam, 1983.
- Gregory R. T. Residue arithmetic with rational operands. ProceecL Symposium on Computer Arithmetic. IEEE Computer Society, A Michigan, 144−145, 1981a.
- Gregory R. T. The use of Finite-segment p-adic arithmetic fo computation. BIT, 18, 1978, 282−300.
- Gregory R. T., Matula D. W. Base conversion in residue systems//BTT. 1977. Vol. 17. P. 286−302.
- 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.
- Koren, O. Zinaty, Evaluating Elementary Functions in a Numerical Coprocessor Based on Rational Approximations, IEEE Trans, on Comp> Vol. 39, No. 8, Aug. 1990.
- Jen Vuillemin, Exact real computer arithmetic with continued fractions IEEE Transactions on Computers, Vol. 39, 1990, pp. 1087−1105.
- 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,
- J. M. Borwein and B. Salvy, «A proof of a recursion for Bessel raoraen"C Exp. Mathematics, vol. 17 (2008), 223−230.t&Z
- 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.
- Kornerup, P. and Matula, D., „Algorithms for Arbitrary Precision Floating Point Arithmetic,“ Proceedings of the 10th IEEE Symposium on Computer Arithmetic, 1991.
- K. Briggs, Implementing exact real arithmetic in python, C++ and C, Theoretical Computer Science, vol.351, 2006, pp. 74−81.
- 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.
- Mencer, O., Morf, M. and Flynn, M. J., «Precision of Scmi-Exact Redundant Continued Fraction Arithmetic for VLSI,» SPIE '99, Arithmetic session, 1999
- Matula, D. and Kornerup, P., «Finite Precision Rational Arithmetic: An Arithmetic Unit,» IEEE Transactions on Computers, Vol. C-32 pp. 378−387, 1983.
- MPFR C library for multiple-precision floating-point computations. http://www.mpfr.org/
- NVIDIA CUDA Compute Unified Device Architecture: http://developer.download.nvidia.com/compute/cuda/l0/NVIDIACUDAP rogrammingGuidel .O.pdf
- Online book from CUDA programming course at UIUC. http://courses.ece.illinois.edu/ece498/al/Syllabus.html
- Peter R. Turner: Fraction-Free RNS Algorithms for Solving Linear Systems, IEEE Symposium on Computer Arithmetic 1997: Asilomar, CA, USA, pp 218−217
- P.FI. Hauschildt and E. Baron, «The Numerical Solution of the Expanding
- Stellar Atmosphere Problem,» J. Computational and Applied Mathematics, vol. 109, 1999, pp. 41−63.
- 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.
- Pour-el M.B. and Richards I. Computability and non-computability in classical analysis. Trans. Am. Math. Soc., P. 539−560, 1983.
- Rao T. M. Error-free computation of characteristic polynomial of a matrix. Comp. and Math, with Appl., 4, 1978, 61−65.
- 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.
- 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.
- 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.
- 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.
- Smyre J. S. Exact computation using extended-precision single-modulus residue arithmetic. M. S. Thesis. Department of Computer Science, University of Tennessee, Knoxville, 1983.
- 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
- 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.
- Yozo Hida, Xiaoye S. Li and David FI. Bailey, «Algorithms for Quad-Double Precision»
- 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.
- Newton division. http://en.wikipedia.org/wiki/Division (digital)