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

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

Я знаю, что многие SMT-решатели реализуют эту стратегию (например, Boolector, Beaver, Alt-Ergo или Z3), но трудно найти документы/технические отчеты/и т. д., в которых эти шаги переписывания подробно описаны. В общем, я нашел только статьи, в которых авторы описывают такие шаги упрощения в нескольких абзацах. Я хотел бы найти какой-нибудь документ, подробно объясняющий использование термина "рерайтинг": приводящий примеры правил, обсуждающий удобство рерайтинга AC и/или других эквационных аксиом, использование стратегий рерайтинга и т. д.

На данный момент, я просто я нашел технический отчет процедура принятия решения для битовых векторов фиксированной ширины , которая описывает шаги нормализации / упрощения, выполняемые CVC Lite, и я хотел бы найти больше технических отчетов, подобных этому! Я также нашел плакат опереписывании терминов в STP , но это всего лишь краткое резюме.

Я уже посещал сайты этих SMT-решателей и искал на их страницах публикации...

Я был бы признателен любому ссылка или любое объяснение того, как термин "рерайтинг" используется в текущих версиях известных решателей SMT. Я особенно заинтересован в Z3, потому что он, похоже, имеет одну из самых умных фаз упрощения. Например, Z3 3.* ввел новую процедуру принятия решений по битовым векторам, но, к сожалению, я не смог найти ни одной статьи, описывающей ее.

2 7
bitvector

2 ответа:

Я с вами согласен. Трудно найти статьи, описывающие этапы предварительной обработки, используемые в современных SMT-решателях. Большинство разработчиков SMT solver согласны с тем, что эти шаги предварительной обработки очень важны для теории битовых векторов. Я считаю, что эти методы не публикуются по нескольким причинам: большинство из них-небольшие трюки, которые сами по себе не являются значительным научным вкладом; большинство методов работают только в контексте конкретной системы; техника, которая может показаться очень эффективной. хорошо на решателе A, не работает на решателе B. Я считаю, что наличие SMT-решателей с открытым исходным кодом-это единственный способ решить эту проблему. Даже если мы опубликуем методы, используемые в конкретном решателе A, будет очень трудно воспроизвести фактическое поведение решателя а без просмотра его исходного кода.

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

  • Несколько правил упрощения, могут уменьшить этот размер локально, но увеличьте его глобально. Упрощенец должен избегать взрыва памяти, вызванного такого рода упрощением. Примеры можно найти по адресу: http://research.microsoft.com/en-us/um/people/leonardo/mit2011.pdf

  • Первый шаг упрощения выполняет только локальные упрощения, которые сохраняют эквивалентность. Примеры: 

2*x - x ->  x 
x and x -> x
  • далее, Z3 выполняет постоянное распространение. Дано равенство t = v, где v - значение. Он заменяет t везде с v.
t = 0 and F[t]  -> t = 0 and F[0]

  • Затем он выполняет гауссово исключение для битовых векторов. Однако исключаются только переменные, которые встречаются в арифметических выражениях не более двух раз. Это ограничение используется для предотвращения увеличения числа сумматоров и множителей в вашей формуле. Например, предположим, что у нас есть x = y+z+w и x происходит при p(x+z), p(x+2*z), p(x+3*z) и p(x+4*z). Тогда, после устранения x, мы бы имели p(y+2*z+w), p(y+3*z+w), p(y+4*z+w) и еще p(y+5*z+w). Хотя мы исключили x, у нас больше сумматоров, чем в исходной формуле.

  • Далее, он устраняет неограниченные переменные. Этот подход описан в докторской диссертации Роберта Бруммайера и Роберто Брутомессо.

  • Затем выполняется еще один раунд упрощения. На этот раз выполняются локальные контекстуальные упрощения. Эти упрощения потенциально очень дороги. Итак, пороговое значение максимального числа посещаемых узлов используется (значение по умолчанию-10 миллионов). Упрощение локального контекста содержит такие правила, как 

(x != 0 or  y = x+1) ->  (x != 0 or y = 1)
    Далее, он пытается минимизировать число множителей, используя дистрибутивность. Пример:

A b + a c - > (b+c)*a

  • Затем он пытается свести к минимуму число сумматоров и множителей, применяя ассоциативность и коммутативность. Предположим, что формула содержит термины a + (b + c) и a + (b + d). Затем, Z3 перепишет их на: (a+b)+c и (a+b)+d. Перед преобразованием Z3 должен был бы кодировать 4 сумматора. После этого нужно кодировать только три сумматора, так как Z3 использует полностью общие выражения.

  • Если формула содержит только равенство, конкатенацию, извлечение и аналогичные операторы. Затем Z3 использует специализированный решатель, основанный на объединении-поиске и замыкании конгруэнтности.

  • В противном случае он разбивает все на части, использует AIGs для минимизации булевой формулы и вызывает его сел решатель.

11

Z3 использует перезапись для многих упрощений, выполняемых во время предварительной обработки. Многие из правил перезаписи, используемых для стратегии UFBV (с кванторами), подробно описаны в следующей статье:

Винтерштайгер, Хамади, Моура: эффективно решать количественно бит-вектор Формулы, FMCADБЫЛ, 2010

1