TY - GEN

T1 - Parallel Factorization of Boolean Polynomials

AU - Kulkarni, Vadiraj

AU - Emelyanov, Pavel

AU - Ponomaryov, Denis

AU - Krishna, Madhava

AU - Raha, Soumyendu

AU - Nandy, S. K.

PY - 2019/12/16

Y1 - 2019/12/16

N2 - 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).

AB - 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).

KW - Boolean polynomials

KW - Factorization

KW - Reconfigurable computing

UR - http://www.scopus.com/inward/record.url?scp=85077492875&partnerID=8YFLogxK

U2 - 10.1007/978-3-030-37487-7_7

DO - 10.1007/978-3-030-37487-7_7

M3 - Conference contribution

AN - SCOPUS:85077492875

SN - 9783030374860

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 80

EP - 94

BT - Perspectives of System Informatics - 12th International Andrei P. Ershov Informatics Conference, PSI 2019, Revised Selected Papers

A2 - Bjørner, Nikolaj

A2 - Virbitskaite, Irina

A2 - Voronkov, Andrei

PB - Springer International Publishing AG

T2 - 12th International Andrei P. Ershov Informatics Conference, PSI 2019

Y2 - 2 July 2019 through 5 July 2019

ER -