Решение задачи "Квадратного корня

Решение задачи "Квадратного корня

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

Пусть заранее известен объем памяти, обозначаемый m, требуемый для соответствующей программы. Ниже мы показываем, как моделировать такую RAMмашину посредством забывающей RAMмашиной с объемом памяти m+2 таким образом, что t шагов оригинальной RAMмашины моделируются за O(t) шагов на забывающей RAMмашине. Всякий раз, когда мы говорим о виртуальном доступе к памяти, мы подразумеваем доступ к памяти, требуемый для оригинальной RAMмашины, которая моделируется. Доступ к памяти при забывающем моделировании RAMмашины рассматривается как фактический доступ к памяти. Кроме того, без потери общности, будем понимать, что виртуальная операция доступа состоит из содержимого единственной ячейки памяти (т.е., выборка(i), сопровождаемая командами сохранить(i,') для некоторого i).

Общее описание алгоритма "Квадратного корня". Интуитивно, чтобы полностью скрыть виртуальную модель доступа, мы должны скрыть следующее:

  • к каким виртуальным ячейкам осуществляется доступ и в каком порядке ?
  • сколько раз к конкретной виртуальной ячейке осуществляется доступ (в случае, если к ней обращались)?

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

Инициализация: Первые m+ слов RAMмоделирования расположены так, чтобы содержать m виртуальных адресов (к которым оригинальная RAMмашина обращается в процессе выполнения) и "фиктивных" слов. Оставшиеся слов распределены так, чтобы обслужить дополнительную ("краткосрочную") память (здесь и далее называемую зщт).

Моделирование шагов RAMмашины: Пока моделирование RAMмашины не остановится, выполнить. (Моделирование выполняется за периоды, каждый из которых состоит из шагов оригинальной/моделируемой машины). В каждом таком периоде выполняются следующие шаги.

    Случайно переставить содержимое ячеек от 1 до m+ . То есть необходимо равномерно выбрать перестановку π над целыми числами от 1 до m+ и забывающим образом переместить содержимое виртуального слова i в фактическое слово πi. Необходимо подчеркнуть, что память зщт (т.е., ячейки от (m++1) до (m+2)) не участвует в этом случайном перемешивании. Таким образом, фактические адреса от 1 до m+ называются перемешанной памятью.

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


Ведете ли вы блог?

Да
Нет
Планирую


Результаты опроса

Новостной блок