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

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

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

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

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

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

 Фибоначчи (п) {     за я = 0 к п-1         Результаты[я] = -1  // -1 означает undefined     возвращаться Fibonacci_Results (Результаты, п); } Fibonacci_Results (Результаты, п) {     если (Результаты[п] != -1)  // Если это было решено раньше,         возвращаться Результаты[п]  // поищи это.     если (п == 0)         вал = 0     еще если (п == 1)         вал = 1     еще         вал = Fibonacci_Results(Результаты, п-2 ) + Fibonacci_Results(Результаты, п-1)     Результаты[п] = вал  // Сохраняем этот результат для повторного использования.     возвращаться вал }

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

 Рекурсивный_Фибоначчи (п) {     если (п == 0)         возвращаться 0     если (п == 1)         возвращаться 1     возвращаться Рекурсивный_Фибоначчи (п-1) + Рекурсивный_Фибоначчи (п-2) }

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

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

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

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

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

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

Базовая схема защиты от злоупотреблений выглядит следующим образом:
Позволять S быть отправителем, р быть получателем, и M быть электронной почтой. Если р заранее согласился получать электронную почту от S, тогда M передается обычным способом. Иначе, S вычисляет некоторую функцию G (М) и отправляет (М, Г (М)) к р. р проверяет, от чего он получает S имеет форму (М, Г (М)). Если да, р принимает M. Иначе, р отвергает M. На рисунке справа показаны случаи, в которых не было предварительных договоренностей..

Функция ГРАММ() выбирается таким образом, чтобы проверка р относительно быстро (занимает миллисекунду) и так, что вычисление S выполняется несколько медленно (занимает не менее нескольких секунд). Следовательно, S будет не рекомендуется отправлять M нескольким получателям без каких-либо предварительных соглашений: стоимость с точки зрения как времени, так и вычислительных ресурсов вычислений ГРАММ() многократно станет очень запретительным для спамера, намеревающегося отправить миллионы электронных писем.

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

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

Смотрите также

Рекомендации

  1. ^ Дворк, Синтия; Наор, Мони (1992). «Ценообразование с помощью обработки нежелательной почты или борьбы с ней». Достижения в криптологии - CRYPTO 1992, 12-я ежегодная международная конференция по криптологии, Санта-Барбара, Калифорния, США, 16-20 августа 1992 г., Труды: 139–147. Дои:10.1007/3-540-48071-4_10. (обновленная версия того же )

внешняя ссылка