Parallel Factorization of Boolean Polynomials

Vadiraj Kulkarni, Pavel Emelyanov, Denis Ponomaryov, Madhava Krishna, Soumyendu Raha, S. K. Nandy

Результат исследования: Публикации в книгах, отчётах, сборниках, трудах конференцийстатья в сборнике материалов конференциинаучнаярецензирование

Аннотация

Polynomial factorization is a classical algorithmic problem in algebra, which has a wide range of applications. Of special interest is factorization over finite fields, among which the field of order two is probably the most important one due to the relationship to Boolean functions. In particular, factorization of Boolean polynomials corresponds to decomposition of Boolean functions given in the Algebraic Normal Form. It has been also shown that factorization provides a solution to decomposition of functions given in the full DNF (i.e., by a truth table), for positive DNFs, and for cartesian decomposition of relational datatables. These applications show the importance of developing fast and practical factorization algorithms. In the paper, we consider some recently proposed polynomial time factorization algorithms for Boolean polynomials and describe a parallel MIMD implementation thereof, which exploits both the task and data level parallelism. We report on an experimental evaluation, which has been conducted on logic circuit synthesis benchmarks and synthetic polynomials, and show that our implementation significantly improves the efficiency of factorization. Finally, we report on the performance benefits obtained from a parallel algorithm when executed on a massively parallel many core architecture (Redefine).

Язык оригиналаанглийский
Название основной публикацииPerspectives of System Informatics - 12th International Andrei P. Ershov Informatics Conference, PSI 2019, Revised Selected Papers
РедакторыNikolaj Bjørner, Irina Virbitskaite, Andrei Voronkov
ИздательSpringer International Publishing AG
Страницы80-94
Число страниц15
ISBN (печатное издание)9783030374860
DOI
СостояниеЭлектронная публикация перед печатью - 16 дек 2019
Событие12th International Andrei P. Ershov Informatics Conference, PSI 2019 - Novosibirsk, Российская Федерация
Продолжительность: 2 июл 20195 июл 2019

Серия публикаций

НазваниеLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Том11964 LNCS
ISSN (печатное издание)0302-9743
ISSN (электронное издание)1611-3349

Конференция

Конференция12th International Andrei P. Ershov Informatics Conference, PSI 2019
СтранаРоссийская Федерация
ГородNovosibirsk
Период02.07.201905.07.2019

Fingerprint Подробные сведения о темах исследования «Parallel Factorization of Boolean Polynomials». Вместе они формируют уникальный семантический отпечаток (fingerprint).

  • Цитировать

    Kulkarni, V., Emelyanov, P., Ponomaryov, D., Krishna, M., Raha, S., & Nandy, S. K. (2019). Parallel Factorization of Boolean Polynomials. В N. Bjørner, I. Virbitskaite, & A. Voronkov (Ред.), Perspectives of System Informatics - 12th International Andrei P. Ershov Informatics Conference, PSI 2019, Revised Selected Papers (стр. 80-94). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Том 11964 LNCS). Springer International Publishing AG. https://doi.org/10.1007/978-3-030-37487-7_7