Реальная оперативная память

Математическая модель компьютера

В вычислительной технике, особенно в вычислительной геометрии , реальная оперативная память ( машина с произвольным доступом ) — это математическая модель компьютера, который может выполнять вычисления с точными действительными числами вместо двоичных чисел с фиксированной точкой или плавающей точкой , используемых большинством реальных компьютеров. Реальная оперативная память была сформулирована Майклом Яном Шамосом в его докторской диссертации 1978 года. ^[1]

Модель

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

Допустимые операции обычно включают сложение, вычитание, умножение и деление, а также сравнения, но не модуль или округление до целых чисел. Причина, по которой следует избегать целочисленного округления и операций модуля, заключается в том, что разрешение этих операций может дать реальной оперативной памяти необоснованные объемы вычислительной мощности, позволяя ей решать задачи PSPACE-complete за полиномиальное время. ^[2]

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

Выполнение

Были разработаны библиотеки программного обеспечения, такие как LEDA , которые позволяют программистам писать компьютерные программы, работающие так, как если бы они работали на реальной оперативной памяти. Эти библиотеки представляют реальные значения с использованием структур данных , которые позволяют им выполнять арифметические действия и сравнения с теми же результатами, которые давала бы настоящая оперативная память. Например, в LEDA реальные числа представлены с использованием типа leda_realданных, который поддерживает корни k -й степени для любого натурального числа k , рациональные операторы и операторы сравнения. ^[3] Анализ времени базового алгоритма реальной оперативной памяти с использованием этих реальных типов данных можно интерпретировать как подсчет количества библиотечных вызовов, необходимых данному алгоритму. ^[4]

Сравнение с другими вычислительными моделями

• В модели машины Тьюринга основная единица вычисления включает один бит. Поэтому временная и пространственная сложность числовых алгоритмов зависит от количества бит, необходимых для представления чисел. Напротив, в модели Real RAM основная единица вычисления включает действительное число, независимо от того, сколько бит требуется для его представления. Это различие важно при анализе таких алгоритмов, как исключение Гаусса : этот алгоритм требует полиномиального числа арифметических операций над действительными числами, поэтому он является полиномиальным в модели Real RAM; однако числа, используемые в промежуточных вычислениях, могут (если реализованы наивно) расти экспоненциально, поэтому его время выполнения в модели машины Тьюринга является экспоненциальным. ^{[5] : Раздел 1.4}
• Реальная оперативная память очень похожа на более позднюю машину Блюма–Шуба–Смейла . ^[6] Однако реальная оперативная память обычно используется для анализа конкретных алгоритмов в вычислительной геометрии , в то время как машина Блюма–Шуба–Смейла вместо этого формирует основу для расширений теории NP-полноты на вычисления с действительными числами.
• Альтернативой реальной оперативной памяти является словесная оперативная память , в которой как входные данные для задачи, так и значения, хранящиеся в памяти и регистрах, предполагаются целыми числами с фиксированным числом бит. Модель словесной оперативной памяти может выполнять некоторые операции быстрее реальной оперативной памяти; например, она допускает быстрые алгоритмы сортировки целых чисел , в то время как сортировка в реальной оперативной памяти должна выполняться с помощью более медленных алгоритмов сортировки сравнения . Однако некоторые задачи вычислительной геометрии имеют входные или выходные данные, которые не могут быть точно представлены с использованием целочисленных координат; см., например, конфигурацию Перлза , расположение точек и отрезков линий, которое не имеет представления в виде целочисленных координат.

Ссылки

1. Шамос, Майкл Ян (1978), Вычислительная геометрия , докторская диссертация, Йельский университет.
2. Шёнхаге, Арнольд (1979), «О мощности машин с произвольным доступом», Труды Шестого международного коллоквиума по автоматам, языкам и программированию (ICALP '79) , Lecture Notes in Computer Science , т. 71, Springer, стр. 520–529, doi :10.1007/3-540-09510-1_42, ISBN 978-3-540-09510-1, МР  0573259.
3. Мельхорн, Курт; Наэр, Стефан (1999). Платформа LEDA комбинаторных и геометрических вычислений. Cambridge University Press . Получено 12 ноября 2019 г.
4. Мельхорн, Курт ; Ширра, Стефан (2001), «Точные вычисления с leda_real — теория и геометрические приложения» (PDF) , Символические алгебраические методы и методы проверки (Dagstuhl, 1999) , Springer, стр. 163–172, doi :10.1007/978-3-7091-6280-4_16, ISBN 978-3-211-83593-7, г-н  1832422.
5. Грётшель, М.; Ловас, Л.; Шрайвер, А. (1981-06-01). «Метод эллипсоида и его последствия в комбинаторной оптимизации». Combinatorica . 1 (2): 169–197. doi :10.1007/BF02579273. ISSN  1439-6912. S2CID  43787103.
6. Блюм, Ленор ; Шуб, Майк ; Смейл, Стив (1989), «О теории вычислений и сложности над действительными числами: NP-полнота, рекурсивные функции и универсальные машины», Бюллетень Американского математического общества , 21 (1): 1–46, doi : 10.1090/S0273-0979-1989-15750-9 , Zbl  0681.03020.

Внешние ссылки

• Возможные ссылки на реальные машины с произвольным доступом
• Геометрические вычисления. Наука о том, как заставить работать геометрические алгоритмы.