Research output: Contribution to journal › Article › peer-review
Factorization of Boolean Polynomials : Parallel Algorithms and Experimental Evaluation. / Emelyanov, P. G.; Krishna, M.; Kulkarni, V. et al.
In: Programming and Computer Software, Vol. 47, No. 2, 03.2021, p. 108-118.Research output: Contribution to journal › Article › peer-review
}
TY - JOUR
T1 - Factorization of Boolean Polynomials
T2 - Parallel Algorithms and Experimental Evaluation
AU - Emelyanov, P. G.
AU - Krishna, M.
AU - Kulkarni, V.
AU - Nandy, S. K.
AU - Ponomaryov, D. K.
AU - Raha, S.
N1 - Publisher Copyright: © 2021, Pleiades Publishing, Ltd. Copyright: Copyright 2021 Elsevier B.V., All rights reserved.
PY - 2021/3
Y1 - 2021/3
N2 - Polynomial factorization is a classical algorithmic algebra problem with a wide range of applications. Of particular interest is factorization over finite fields, among which fields of order two are probably the most important ones when representing Boolean functions by Zhegalkin polynomials. In particular, factorization of Boolean polynomials corresponds to conjunctive decomposition of Boolean functions given in algebraic normal form. In addition, factorization enables decomposition of functions given in full disjunctive normal form (DNF) and positive DNF, as well as Cartesian decomposition of relational data. These applications demonstrate the importance of developing fast factorization algorithms. In this paper, we consider some recently proposed factorization algorithms of polynomial complexity and describe a parallel MIMD implementation that takes advantage of both task-level and data-level parallelism. We conduct some experiments on logic synthesis benchmarks and synthetic (random) polynomials to demonstrate significant factorization speedup. In conclusion, we discuss results of testing a parallel implementation of the algorithm on a massively parallel multicore architecture (REDEFINE).
AB - Polynomial factorization is a classical algorithmic algebra problem with a wide range of applications. Of particular interest is factorization over finite fields, among which fields of order two are probably the most important ones when representing Boolean functions by Zhegalkin polynomials. In particular, factorization of Boolean polynomials corresponds to conjunctive decomposition of Boolean functions given in algebraic normal form. In addition, factorization enables decomposition of functions given in full disjunctive normal form (DNF) and positive DNF, as well as Cartesian decomposition of relational data. These applications demonstrate the importance of developing fast factorization algorithms. In this paper, we consider some recently proposed factorization algorithms of polynomial complexity and describe a parallel MIMD implementation that takes advantage of both task-level and data-level parallelism. We conduct some experiments on logic synthesis benchmarks and synthetic (random) polynomials to demonstrate significant factorization speedup. In conclusion, we discuss results of testing a parallel implementation of the algorithm on a massively parallel multicore architecture (REDEFINE).
UR - http://www.scopus.com/inward/record.url?scp=85104513063&partnerID=8YFLogxK
U2 - 10.1134/S0361768821020043
DO - 10.1134/S0361768821020043
M3 - Article
AN - SCOPUS:85104513063
VL - 47
SP - 108
EP - 118
JO - Programming and Computer Software
JF - Programming and Computer Software
SN - 0361-7688
IS - 2
ER -
ID: 28454338