Структура данных для решения задачи "квадратного корня
11. Структура данных для решения задачи "квадратного корня"
- сканируется вся память зщт и проверяется, находится ли содержимое виртуального слова i в одном из слов памяти зщт. Подчеркнем, что здесь мы обращаемся к каждой ячейке памяти зщт в предопределенном порядке независимо от того, находится ли там виртуальное слово, которое нам надо;
- в случае, если iтое виртуальное слово не найдено в памяти зщт, мы восстанавливаем его из фактического слова π(i), которое является текущей ячейкой iтого виртуального слова в течение этого периода;
- в противном случае (т.е., в случае, если i виртуальное слово найдено в памяти зщт), мы получаем доступ к следующему "фиктивному слову" в перемешанной памяти (например, мы обращаемся к фактическому адресу π(m+j), где j число шагов, моделируемых в текущем периоде);
- в любом случае модифицируемое значение для iтой виртуальной ячейки записано (забывающим образом) в память зщт посредством сканирования заново всех слов памяти зщт .
Модификация перемешанной памяти. В конце периода, используются значения, сохраненные в памяти зщт для модификации забывающим образом содержимого перемешанной памяти.
Перед тем как приступить к деталям реализации вышеупомянутых шагов, сделаем несколько замечаний относительно того, почему они составляют забывающее моделирование. Далее покажем, как осуществить доступ к памяти на шаге 1 фиксированным образом а, следовательно, независимо от входа и виртуальной модели доступа оригинальной RAMмашины. Различают два типа операций доступ к памяти, выполненных на шаге 2: полное сканирование памяти зщт (т.е., осуществление доступа к каждому из слов дважды на каждую виртуальную операцию доступа) и осуществление доступа к ячейкам перемешанной памяти во время каждого периода. Для каждых возможных виртуальных операций доступа, последние фактических операций доступа равномерно распределены среди всех подмножеств {1,...,m+}, где распределение вероятностей индуцировано выбором перестановки π. Таким образом, фактический доступ, выполняемый на шаге 2, не открывает никакой информации относительно виртуальных операций доступа, выполняемых в этом шаге. Легко увидеть, что шаг 3 не создает никаких новых трудностей, поскольку он может быть сделан при выполнении операций фактического доступа на шагах 1 и 2 в обратном порядке.
Магазин недорогих сумок - брендовая одежда. Интернет-бутик Luxury-Mall одежды.
4/04/10 - 
