Экспоненциальное ускорение во внешней памяти

Фон

Внешняя память, или модель DAM, определяет стоимость алгоритма по количеству операций ввода-вывода, которые он выполняет (по сути, по числу пропущенных кешей). Эти времена выполнения обычно даются в терминах , размера памяти и , количества слов, которые могут быть переданы в память за один раз. Иногда и используются для и соответственно. $M$ $B$ $L$ $Z$ $B$ $M$

Например, для сортировки требуется стоимость а для умножения наивной матрицы требуется $\Theta(N/B\log_{M/B} N/B)$ . $\Theta(n^3/B\sqrt{M})$

Эта модель используется для анализа «алгоритмов кэш-забывчивый», которые не имеют знаний или . Как правило, цель состоит в том, чтобы алгоритм, не обращающий внимания на кэш, работал оптимально в модели внешней памяти; это не всегда возможно, как, например, в задаче о перестановках (показано в Brodal, Faderberg 2003 ). Посмотрите эту статью Эрика Демейна для более подробного объяснения алгоритмов, не обращающих внимания на кэш, включая обсуждение сортировки и умножения матриц. $B$ $M$

Мы можем видеть, что изменение вызывает логарифмическое ускорение для сортировки и полиномиальное ускорение для умножения матриц. (Этот результат родом из Гонконга, Кунга, 1981 г. и фактически предшествует забвению кеша и формализации модели внешней памяти). $M$

У меня вопрос такой:

Есть ли случай, когда ускорение экспоненциально в ? Время работы будет что-то вроде . Я особенно интересуюсь алгоритмом или структурой данных, не учитывающей кэш, который подходит под это описание, но был бы доволен алгоритмом / структурой данных с учетом кэша или даже самой известной нижней границей. $M$ $f(N,B)/2^{O(M)}$

В большинстве моделей обычно предполагается, что размер слова если - это размер входного файла и ясно, что . Тогда убыстрение дает полиномиальное ускорение в . Это заставляет меня поверить, что если проблема, которую я ищу, существует, она не является полиномиальной. (В противном случае мы можем изменить размер кэша на константу, чтобы получить постоянное количество операций ввода-вывода, что маловероятно). $w = \Omega(\log N)$ $N$ $M > w$ $2^M$ $N$

ds.algorithms ds.data-structures cache-oblivious Samm
источник

можете догадаться, но

? нашел случай дан как ускорении

, достаточный?

N =

$N=$

B^{p o l y l o g (B)}

$B^{\rm{polylog}(B)}$

vzn

К сожалению, для моих целей это должно быть с точки зрения

Я был бы заинтересован в ссылке, хотя.

M

$M$

SamM

Википедия о кешировании забытых алгоритмов . Кстати, в этой записи полей есть некоторые тонкости. Сноска p7 Demaine гласит, что

- это размер проблемы, а иногда

где

- количество блоков, «но запись в нижнем регистре, кажется, перестала пользоваться». Вы используете

выше и альтернативно

видимо, оба в качестве размера ввода. думаю, что вы должны по крайней мере стандартизировать в своем вопросе.

N

$N$

n = N / B

$n = N/B$

n

$n$

n

$n$

N

$N$

Я отредактировал это для последовательности.

- это размер входных данных, а

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

(т.

N

$N$

n

$n$

n \times n

$n\times n$

N = n^{2}

$N = n^2$

Е.

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

для этого случая ...? или, может быть, какая-то фрактальная схема доступа к памяти - наихудший случай? этой линии обучения всего лишь немногим более десяти лет ....

M

$M$

vzn

Ответы:

Я не уверен, что понял вопрос. Но мне кажется, что в предположении, что содержит проблемы, требующие экспоненциального времени, такие проблемы будут соответствовать вашим требованиям, поскольку, если равно вам потребуется экспоненциальное число операций ввода-вывода ( поскольку вы не можете «оставаться» в одном и том же блоке памяти размером больше, чем полиномиальное количество шагов, не входя в цикл), и если $PSPACE$ $M$ $O(\log N)$ $O( \log N)$ $M=N$ вам потребуется только линейное количество операций ввода-вывода. Кроме того, что касается вашего наблюдения, что такая проблема не может принадлежать , это правильно, если ускорение должно выполняться для значений которые являются (поскольку это будет означать, что у нас экспоненциальное число операций). Но если ускорение применимо только к меньшим значениям , интуитивно я полагаю, что это не так, потому что я чувствую, что должна быть возможность разработать проблему, которая на самом деле является объединением меньших задач размера каждая из которых требует экспоненциального время в его собственный размер, и экспоненциального числа операций ввода / вывода (то есть, $P$ $M$ $\Omega(N)$ $M$ $O(\log N)$ , так является экспоненциальной в ). На практике я считаю, что -полные проблемы, такие как удовлетворяют вашему условию. $poly (N)$ $poly(N)$ $O(\log N)$ $PSPACE$ $TQBF$

user8477
источник

Боюсь, я не следую некоторым твоим аргументам. Если

, любая проблема во внешней памяти тривиальна. Как я уже упоминал,

несколько глупо, поскольку это означает, что память имеет только постоянное количество слов (возможно, но не так, как обычно проверяется внешняя память). Я понимаю, что вы говорите, что был экспоненциальный выигрыш, но это ничего не говорит о промежуточных значениях. Например, оптимальное разделение во внешней памяти - это минимум двух терминов (по сути, если все умещается в памяти, мы делаем что-то совершенно иное, чем если бы этого не произошло). Вы можете исключить это?

M = Ω (N)

$M= \Omega(N)$

M = O (\log N)

$M = O(\log N)$

СамМ

Я не понимаю, почему любая проблема во внешней памяти тривиальна, если

. Если

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

M = Ω (N)

$M = \Omega(N)$

M = N / 2

$M=N/2$

user8477

Ах, конечно, вы правы в том, что постоянный фактор важен. Это имеет большой смысл; это, безусловно, хорошая отправная точка.

SamM

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

, приведенный выше аргумент «голубя дыра» (цикличность) все равно даст выигрыш в

где

- временная сложность задачи.

M = ω (\log N)

$M=\omega(\log N)$

T (N) / 2^{M}

$T(N)/2^M$

T (N)

$T(N)$

user8477

-4

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

Оставайтесь на том, кого вы цитируете, пишет: «Основная идея [алгоритмов, не обращающих внимания на кэш], проста: разрабатывать алгоритмы с внешней памятью, не зная и Но эта простая идея имеет несколько удивительно мощных последствий». $B$ $M$

он также имеет удивительно тонкие последствия. Кажется, трудно проанализировать эту модель на предмет экстремального поведения, и, похоже, до сих пор никто этого не делал. Есть некоторые опросы, и они, кажется, до сих пор опрашивают все поле. это не удивительно, учитывая, что области всего ~ 1 десятилетие.

$B,M$
ТМ были изобретены в 1936 году Тьюрингом, и теоремы о пространственно - временной иерархии Хартманиса-Стернса (на которые вы несколько ссылаетесь в этом вопросе) были открыты в 1965 году. Это замечательные ~ 3 десятилетия, хотя теоремы о пространственно-временной иерархии теперь считаются несколько элементарный и преподавал в бакалавриате. похоже, что в этой модели еще не установлены соответствующие теоремы об иерархии, и то, как это сделать, не является тривиальной проблемой. эта модель на самом деле, кажется, имеет больше «движущихся частей», чем стандартная машина Тьюринга (которая уже обладает довольно дьявольски сложной динамикой), то есть похожа на расширенную машину Тьюринга.
другая идея заключается в том, чтобы каким-то образом преобразовать эту модель внешней памяти в ТМ, что опять же не отражено в литературе / обзорах по алгоритмам забытого кэша, и, возможно, посмотреть, как можно перевести теоремы иерархии Хартманиса-Стернса. похоже, это относится к двум лентам ТМ, где одна лента имеет размер «М», а другая лента бесконечна, а блоки передаются в «М» с размерами «В». но также трудность заключается в том, что это скорее модель ОЗУ, чем модель Тьюринга, которая использует последовательный доступ к ленте. с другой стороны, это может натолкнуться на тонкости, связанные с преобразованиями между одиночными и многолучевыми ТМ .
Предложите эмпирически рассмотреть эту проблему с помощью симуляций, на которых, как правило, фокусируется литература, как, например, в этом большом обзоре Кумара о забывающих алгоритмах Cache (2003). Есть много программ и статей в Интернете для моделирования кэша, и можно было бы ответить на ваш вопрос без большого количества кода, используя некоторые упрощения. одна из основных идей заключается в создании вероятностных алгоритмов, которые получают доступ к «близлежащим» областям памяти на основе вероятностей. «поблизости» здесь не обязательно непрерывная память, а алгоритм, который выбирает случайные страницы памяти (блоки) на основе отслеживания своих последних страниц, к которым недавно обращались. предложить использовать законы властиопределить вероятность выбора «ближайших» страниц в списке «последних посещений». похоже, это ключевой аспект, с которым связаны улучшения производительности на основе кэша.
Вот грубый аргумент, основанный на «М», который в основном является мерой «памяти ядра» по сравнению с памятью диска. для алгоритма можно ожидать, что при увеличении памяти ядра можно лишь [асимптотически] приблизиться к линейному улучшению скорости алгоритма, и добавление «памяти ядра» для получения любого суперлинейного увеличения скорости алгоритма кажется интуитивно почти равным превышению скорости ограничить и «получить что-то даром». однако, не достаточно хорошо понимайте модель, чтобы доказать это [но, очевидно, никто другой не имеет, включая власти / учредителей / экспертов].
Эта литература по кэш-памяти, не обращающая внимания на кэш-память, была сосредоточена на P-алгоритмах и до сих пор не видела ни одного случая анализа не-P-алгоритма и, возможно, такого не существует. это может быть потому, что анализ слишком сложен! в этом случае вопросы об экстремальном поведении могут остаться без ответа в этой области в долгосрочной перспективе.
он даже не кажется интуитивно понятным или, возможно, вообще изученным, о том, как ведут себя в этой модели «малые» алгоритмы сложности, такие как в L, или «большие» алгоритмы, такие как не P (например, Expspace и т. д.). модель измеряет локальность памяти, которая, по-видимому, принципиально отличается, но тесно связана с иерархией времени и пространства.
есть несколько неясное измерение сложности машины Тьюринга, называемое «сложностью обращения», с некоторыми исследованиями, результатами и работами, которые могут быть связаны. в основном ТМ может охватывать определенное количество времени и пространства, но реверсы являются несколько независимым измерением головки ленты во время вычислений. Похоже, что «большие изменения» могут быть связаны с «высокой локальностью памяти», потому что в обоих случаях головка ленты имеет тенденцию оставаться в «меньшей» области по сравнению с перемещением в более крупные области.
этот вопрос и модель напоминают мне о законе Амдала и подозревают, что какой-то еще не обнаруженный аналогичный закон, связанный с уменьшением прибыли или сальдо / компромиссов, может иметь место или быть применимым в этой области. Грубые рассуждения: теория алгоритмов, не обращающая внимания на кеш, ищет баланс / компромисс между конечной «локальной» памятью и стоимостным внешним «бесконечным» диском. это в основном два ресурса, которые ведут себя «параллельно», и между ними, вероятно, существует какой-то оптимальный компромисс.

ВЗН
источник

k

$k$

Модель TM - это базовая модель TCS и «связующее звено» между ее иерархией сложности (время / пространство, базовые классы сложности, такие как P / NP и т. д.) с алгоритмами, забывающими о кеше, по-видимому, еще предстоит отобразить. модели внешней памяти и связанные с ними модели кэш-памяти в основном пытаются моделировать характеристики производительности в реальном мире, и литература пока не заинтересована в больших теоретических абстракциях, таких как заданные в вопросе.

vzn