Структура данных для решения задачи "квадратного корня

11. Структура данных для решения задачи "квадратного корня"

  • сканируется вся память зщт и проверяется, находится ли содержимое виртуального слова i в одном из слов памяти зщт. Подчеркнем, что здесь мы обращаемся к каждой ячейке памяти зщт в предопределенном порядке независимо от того, находится ли там виртуальное слово, которое нам надо;
  • в случае, если iтое виртуальное слово не найдено в памяти зщт, мы восстанавливаем его из фактического слова π(i), которое является текущей ячейкой iтого виртуального слова в течение этого периода;
  • в противном случае (т.е., в случае, если i виртуальное слово найдено в памяти зщт), мы получаем доступ к следующему "фиктивному слову" в перемешанной памяти (например, мы обращаемся к фактическому адресу π(m+j), где j число шагов, моделируемых в текущем периоде);
  • в любом случае модифицируемое значение для iтой виртуальной ячейки записано (забывающим образом) в память зщт посредством сканирования заново всех слов памяти зщт
  • .

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

Перед тем как приступить к деталям реализации вышеупомянутых шагов, сделаем несколько замечаний относительно того, почему они составляют забывающее моделирование. Далее покажем, как осуществить доступ к памяти на шаге 1 фиксированным образом а, следовательно, независимо от входа и виртуальной модели доступа оригинальной RAMмашины. Различают два типа операций доступ к памяти, выполненных на шаге 2: полное сканирование памяти зщт (т.е., осуществление доступа к каждому из слов дважды на каждую виртуальную операцию доступа) и осуществление доступа к ячейкам перемешанной памяти во время каждого периода. Для каждых возможных виртуальных операций доступа, последние фактических операций доступа равномерно распределены среди всех подмножеств {1,...,m+}, где распределение вероятностей индуцировано выбором перестановки π. Таким образом, фактический доступ, выполняемый на шаге 2, не открывает никакой информации относительно виртуальных операций доступа, выполняемых в этом шаге. Легко увидеть, что шаг 3 не создает никаких новых трудностей, поскольку он может быть сделан при выполнении операций фактического доступа на шагах 1 и 2 в обратном порядке.


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

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


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

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