Функция с привязкой к памяти

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

Границы памяти и вычислений иногда могут быть сопоставлены друг с другом, например, путем сохранения и повторного использования предварительных результатов или использования справочных таблиц .

Функции, связанные с памятью, и функции памяти

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

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

 Fibonacci (n)
 {
     for i = 0 to n-1
         results[i] = -1  // -1 means undefined

     return Fibonacci_Results (results, n);
 }

 Fibonacci_Results (results, n)
 {
     if (results[n] != -1)  // If it has been solved before,
         return results[n]  // look it up.
     if (n == 0)
         val = 0
     else if (n == 1)
         val = 1
     else
         val = Fibonacci_Results(results, n-2 ) + Fibonacci_Results(results, n-1)
     results[n] = val  // Save this result for re-use.

     return val
 }

Сравните приведенное выше с алгоритмом, который использует только рекурсию и работает за экспоненциальное время процессора:

 Recursive_Fibonacci (n)
 {
     if (n == 0)
         return 0
     if (n == 1)
         return 1

     return Recursive_Fibonacci (n-1) + Recursive_Fibonacci (n-2)
 }

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

Термин «функция, связанная с памятью» появился совсем недавно и используется в основном для описания функции, которая использует XOR и состоит из серии вычислений, в которых каждое вычисление зависит от предыдущего вычисления. В то время как функции памяти уже давно играют важную роль в улучшении временной сложности, функции, связанные с памятью, нашли гораздо меньше применений. Недавно ^{[ когда? ]}Однако ученые предложили метод, использующий функции, привязанные к памяти, как средство предотвращения злоупотребления ресурсами спамерами, что может стать крупным прорывом в этой области.

Использование функций с привязкой к памяти для предотвращения спама

Функции, связанные с памятью, могут быть полезны в системе доказательства работы , которая может сдерживать спам , который стал проблемой масштабов эпидемии в Интернете .

В 1992 году ученые-исследователи IBM Синтия Дворк и Мони Наор опубликовали на CRYPTO 1992 статью под названием « Ценообразование через обработку или борьбу с нежелательной почтой» . ^[1] предлагая возможность использования функций, связанных с процессором, для предотвращения рассылки спама злоумышленниками. Схема была основана на идее, что пользователи компьютеров с гораздо большей вероятностью будут злоупотреблять ресурсом, если стоимость злоупотребления ресурсом незначительна: основная причина, по которой спам стал таким безудержным, заключается в том, что отправка электронного письма обходится спамерам совсем незначительно.

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

Основная схема, защищающая от злоупотреблений, выглядит следующим образом:
Даны отправитель, получатель и сообщение электронной почты. Если Получатель заранее дал согласие на получение электронного письма от Отправителя, то Сообщение передается обычным способом. В противном случае Отправитель вычисляет некоторую функцию $G(Сообщение)$ и отправляет $(Сообщение, G(Сообщение))$ Получателю. Получатель проверяет, имеет ли то, что он получает от отправителя, форму $(Сообщение, G(Сообщение))$ . Если да, Получатель принимает Сообщение. В противном случае Получатель отклоняет Сообщение.

Функция $G()$ выбирается таким образом, чтобы проверка Получателем была относительно быстрой (например, занимала миллисекунду) и чтобы вычисления Отправителя были несколько медленными (занимающими по меньшей мере несколько секунд). Таким образом, Отправителю не будет рекомендуется отправлять сообщение нескольким получателям без каких-либо предварительных соглашений: затраты времени и вычислительных ресурсов на повторное вычисление $G()$ станут непомерно высокими для спамера, который намеревается отправить многие миллионы электронных писем. .

Основная проблема использования приведенной выше схемы заключается в том, что быстрые процессоры выполняют вычисления намного быстрее, чем медленные. Кроме того, компьютерные системы более высокого класса также имеют сложные конвейеры и другие полезные функции, облегчающие вычисления. В результате спамер с современной системой вряд ли пострадает от такого сдерживания, в то время как обычный пользователь с посредственной системой пострадает. Если вычисление занимает несколько секунд на новом ПК , оно может занять минуту на старом ПК и несколько минут на КПК , что может быть неприятно для пользователей старых ПК, но, вероятно, неприемлемо для пользователей КПК. Несоответствие в скорости клиентского ЦП представляет собой одно из серьезных препятствий на пути широкого внедрения любой схемы, основанной на функции, привязанной к ЦП. Поэтому исследователи озабочены поиском функций, которые большинство компьютерных систем будут оценивать примерно с одинаковой скоростью, чтобы высокопроизводительные системы могли оценивать эти функции несколько быстрее, чем младшие системы (в 2–10 раз быстрее, но не в 10–100 раз). быстрее), как это может подразумевать из-за различий в процессорах. Эти соотношения « эгалитарный » достаточно для предполагаемых применений: эти функции эффективны в предотвращении злоупотреблений и не приводят к чрезмерной задержке законных взаимодействий в широком диапазоне систем.

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

См. также

Ссылки

^ Дворк, Синтия ; Наор, Мони (1992). «Ценообразование посредством обработки или борьбы с нежелательной почтой» . Достижения криптологии — КРИПТО' 92 . Конспекты лекций по информатике. Том. 740. стр. 139–147. дои : 10.1007/3-540-48071-4_10 . ISBN 978-3-540-57340-1 . ( обновленная версия того же )

Абади М., Берроуз М., Манасс М. и Воббер Т. (май 2005 г.). Умеренно сложные функции, связанные с памятью , транзакции ACM в интернет-технологиях .
Дворк К., Голдберг А. и Наор М. (2003). О функциях, связанных с памятью, для борьбы со спамом , Достижения в криптологии .
Хеллман, Мэн (1980). Криптоаналитический компромисс между временем и памятью , Транзакции IEEE в теории информации .

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

[1] Дворк, Синтия ; Наор, Мони (1992). «Ценообразование посредством обработки или борьбы с нежелательной почтой» . Достижения криптологии — КРИПТО' 92 . Конспекты лекций по информатике. Том. 740. стр. 139–147. дои : 10.1007/3-540-48071-4_10 . ISBN 978-3-540-57340-1 . ( обновленная версия того же )

[1]