Standard
Parallel Factorization of Boolean Polynomials. / Kulkarni, Vadiraj; Emelyanov, Pavel; Ponomaryov, Denis et al.
Perspectives of System Informatics - 12th International Andrei P. Ershov Informatics Conference, PSI 2019, Revised Selected Papers. ed. / Nikolaj Bjørner; Irina Virbitskaite; Andrei Voronkov. Springer International Publishing AG, 2019. p. 80-94 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11964 LNCS).
Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Research › peer-review
Harvard
Kulkarni, V
, Emelyanov, P, Ponomaryov, D, Krishna, M, Raha, S & Nandy, SK 2019,
Parallel Factorization of Boolean Polynomials. in N Bjørner, I Virbitskaite & A Voronkov (eds),
Perspectives of System Informatics - 12th International Andrei P. Ershov Informatics Conference, PSI 2019, Revised Selected Papers. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 11964 LNCS, Springer International Publishing AG, pp. 80-94, 12th International Andrei P. Ershov Informatics Conference, PSI 2019, Novosibirsk, Russian Federation,
02.07.2019.
https://doi.org/10.1007/978-3-030-37487-7_7APA
Kulkarni, V.
, Emelyanov, P., Ponomaryov, D., Krishna, M., Raha, S., & Nandy, S. K. (2019).
Parallel Factorization of Boolean Polynomials. In N. Bjørner, I. Virbitskaite, & A. Voronkov (Eds.),
Perspectives of System Informatics - 12th International Andrei P. Ershov Informatics Conference, PSI 2019, Revised Selected Papers (pp. 80-94). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11964 LNCS). Springer International Publishing AG.
https://doi.org/10.1007/978-3-030-37487-7_7Vancouver
Kulkarni V
, Emelyanov P, Ponomaryov D, Krishna M, Raha S, Nandy SK.
Parallel Factorization of Boolean Polynomials. In Bjørner N, Virbitskaite I, Voronkov A, editors, Perspectives of System Informatics - 12th International Andrei P. Ershov Informatics Conference, PSI 2019, Revised Selected Papers. Springer International Publishing AG. 2019. p. 80-94. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). Epub 2019 Dec 16. doi: 10.1007/978-3-030-37487-7_7
Author
Kulkarni, Vadiraj
; Emelyanov, Pavel ; Ponomaryov, Denis et al. /
Parallel Factorization of Boolean Polynomials. Perspectives of System Informatics - 12th International Andrei P. Ershov Informatics Conference, PSI 2019, Revised Selected Papers. editor / Nikolaj Bjørner ; Irina Virbitskaite ; Andrei Voronkov. Springer International Publishing AG, 2019. pp. 80-94 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
BibTeX
@inproceedings{3743efa94f144e54886bdf2cde0f3571,
title = "Parallel Factorization of Boolean Polynomials",
abstract = "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).",
keywords = "Boolean polynomials, Factorization, Reconfigurable computing",
author = "Vadiraj Kulkarni and Pavel Emelyanov and Denis Ponomaryov and Madhava Krishna and Soumyendu Raha and Nandy, {S. K.}",
year = "2019",
month = dec,
day = "16",
doi = "10.1007/978-3-030-37487-7_7",
language = "English",
isbn = "9783030374860",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer International Publishing AG",
pages = "80--94",
editor = "Nikolaj Bj{\o}rner and Irina Virbitskaite and Andrei Voronkov",
booktitle = "Perspectives of System Informatics - 12th International Andrei P. Ershov Informatics Conference, PSI 2019, Revised Selected Papers",
address = "Switzerland",
note = "12th International Andrei P. Ershov Informatics Conference, PSI 2019 ; Conference date: 02-07-2019 Through 05-07-2019",
}
RIS
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 -
