Serguey Zefirov (thesz) wrote,
Serguey Zefirov
thesz

zdd

Вот эти вот.

ZDD в своём построении требуют условия уникальности: если мы создаём узел с переменной i и двумя подузлами (ссылками) A и B, то ссылка на такой узел должна быть одной и той же всегда .

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

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

Соответственно, работа разбивается на 1) насоздавать узлов и 2) отсечь только достижимые. 1-я часть весьма параллельна, мы можем создавать узлы независимо от работающих рядом процессов. 2-я часть так же весьма параллельна - это, фактически, слияние с фильтрацией. Мы можем сделать настолько много (или мало) потоков выполнения для операций слияния, насколько это нам выгодно.

Если я всё правильно понимаю, это позволяет сделать довольно экономный вариант работы с ZDD на GPU.
Tags: gpgpu, алгоритмы, структура, таблицы истинности
Subscribe

  • Смотрю Мастер и Маргарита

    Корнелюк - гений. Местами очень страшно и это я смотрю пятую серию (попалась на ТТ), где дьявольщины никакой, пока.

  • "Люцифер"

    Оказался довольно интересным сериалом. Напомнил мне День Сурка. В "Люцифере" многотысячелетний дьявол рассматривает жизни людей со скоростью их,…

  • The Boys.

    Одна из стадий алкоголизма, далеко не самая первая - когда блюёшь раньше, чем засыпаешь. Подавляющее действие алкоголя ослабло из-за привычки и стало…

  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

  • 0 comments