1
\$\begingroup\$

I'm currently in the situation in which I need to optimize a binary circuit by reducing its number of gates. We regard a circuit simply as a directed acyclic graph with some input wires and some output wires. Some of the input wires may hold constants, and some other hold "variables". Vertices contain gates which can be either XOR or AND.

The circuit appeared in a Computer Science context, not in a Electrical Engineering one. We need to optimize our circuit by reducing its number of gates, so we started thinking of some approaches to achieve this task. Researching online we discovered that this is a well-studied problem in Electrical Engineering, with a lot of software out there that aids in this direction. However, as expected most of the documentation/information/blogs/etc are targeted towards electrical engineers, and they are overwhelming for outsiders who do not have the terminology.

For instance, I managed to gather from here the following steps

...We first created flattened Verilog netlists, we started from a purely combinational HDL description of the implementation. We used Cadence Encounter RTL compiler in conjunction with the Faraday FSA0A_C 0.18 mm ASIC Standard Cell Library for synthesis. For synthesis we flattened the hardware modules hierarchy and we allowed only the use of INV1S, AN2, XOR2HS, TIE0, and TIE1 cells. After this we re-wrote the output and topologically sorted the resulting circuits.

I have highlighted the terms that do not make sense to me, even after extensive searches online. Also, other sources I found that may help with this problem keep a similar notation and are hard to understand for an outsider.

Given the above, my question is

Given a boolean circuit with only XOR and AND gates, what should be the starting point in order to minimize its number of gates?

Any recommendation on software, examples, terms, etc. is highly appreciated.


Addendum

I was suggested to provide more details on the problem I'm trying to solve here. I have a large binary circuit (to be explicit, this circuit is written in a file like this one), roughly 300K gates (as I said above, these are XOR or AND gates). I want to algorithmically minimize the size of this circuit so that it ends up with fewer gates. Morever, due to the context in which this circuit appeared, AND gates have a much higher cost than XOR gates. Therefore, an optimization with a smaller number of AND gates is very much preferable (I think this may contrast with usual optimization in electrical engineering in which only the size matters without distinction on the different types of gates, but I may be wrong).

To receive more accurate answers I include a bit of my background for this problem. I know about boolean logic and I can identify the optimization techniques that can be used for this purpose. I have read about two-level and multi-level optimization (although I don't get the differences between the two). I also know about the existence of algorithms like Esspreso and Quine–McCluskey. Finally, I've read a bit about HDL and RTL languages and compilers, but I'm not even sure it's relevant.

My main issue here is that I don't know where to get started. Which of these concepts/tool fit better in my setting?


Context of the question

In case you're interested, here I add some details about the context where this question appeared.

The field is cryptography, a subdomain of computer science. More specifically, I'm talking about something called Multiparty Computation and Fully Homomorphic Encryption. The important point here is that we regard functions to be computed as circuits, or DAGs, where each vertex is an operation (either addition or multiplication). This is another way to say multivariate polynomials. When this is done modulo 2 we're talking then about binary circuits with AND and XOR as the two allowed operations.

Now, the goal of these techniques is to be able to secretly compute some function over some data. This is done by writing the function in terms of XOR and AND operations (so, a binary circuit or a very long boolean expression) and proceeding from the inputs to the outputs in an operation-by-operation fashion.

Due to the way these techniques work, each AND operation for us is much more expensive than an XOR operation. This means that having equivalent representations for the same program with a smaller number of AND operations is much better, since it can be performed more efficiently. Moreover, having a very "deep" circuit is bad, so we also want to optimize to have a more shallow circuit (I hope these terms of "deep" and "shallow" make sense in this context).

My initial impression is that this problem could be similar to some problems faced in electrical engineering. Is there any correlation?


PS: Please bear I mind that I come from Computer Science and hold no knowledge on Electrical Engineering at all, so this question may be silly, contain incorrect terminology, wrong tags, or even be off-topic, in which case I kindly ask you for a pointer to the right place to ask.

\$\endgroup\$
  • \$\begingroup\$ Do you mean optimizing the boolean logic? There are established rules for that from decades ago. Consult a logic design text book. \$\endgroup\$ – doubleE Sep 30 '18 at 17:04
  • \$\begingroup\$ @Learner Thanks. Yes, I guess that is precisely what I want: optimizing the underlying boolean formula. Can you please point to a particular logic design textbook you consider relevant? \$\endgroup\$ – Daniel Sep 30 '18 at 17:05
  • 1
    \$\begingroup\$ These are standard books. All are good. See which one is easier for your level. 1- Digital Logic Design by Moris Mano, 2- Digital Design: Principles and Practices, John. F. Wakerly, 3- Digital Design: A Systems Approach by William J. Dally \$\endgroup\$ – doubleE Sep 30 '18 at 17:15
  • 1
    \$\begingroup\$ Daniel, minimization doesn't have a single answer or process. There is a standard process for forming the sum of products or product of sums and there is software that can do this called Espresso. You can download the source for that, too, I think. An input to that process is whether or not you want to treat the outputs as isolated, or combined. But even with that, you also need to look up "two-level and three-level" minimization methods and also the "sum of pseudo-products." Those should get you started. \$\endgroup\$ – jonk Sep 30 '18 at 18:57
  • 1
    \$\begingroup\$ @Daniel If I were you, I'd go find researchers publishing in areas related to compiler development for FPGA and ASIC optimization, as well as just general compiler optimization for specialized computer systems, such as "VLIW" areas (the Bulldog compiler PhD thesis circa 1985 comes to mind, not as an answer but as the direction I'm pointing towards.) I'd then contact these researchers by email or phone, listen and follow up on their thoughts, and I think you will eventually find the right handful of people who can actually help you. \$\endgroup\$ – jonk Sep 30 '18 at 19:50
0
\$\begingroup\$

A first place to go might be something called "boolean algebra". If you have only few boolean algebra terms, then you can do that by hand.

Example from school: (x+1)*(1+2)reduces to 3x+3

analogous...

(A xor B) * A reduces to A * not_B

You just have to learn the boolean algebraic rules. A place to start might be here

\$\endgroup\$
  • \$\begingroup\$ Thanks for your answer Stefan. I'm ok with boolean algebra and with its simplification rules and so on. I mostly wanted to look at automated tools that can optimize the circuit for me, without me having to check manually for the existence of simplification opportunities \$\endgroup\$ – Daniel Sep 30 '18 at 18:30
  • \$\begingroup\$ Ok. Maybe if you show us your problem, we can give you better advice. \$\endgroup\$ – Stefan Wyss Sep 30 '18 at 18:34
  • \$\begingroup\$ Thanks for the suggestion Stefan! I tried to add a bit more detail, please see the question body :) \$\endgroup\$ – Daniel Sep 30 '18 at 19:13
  • 1
    \$\begingroup\$ Well, giving the size of the problem, this is a bit out of my league. But here is how I would approach it: You seem to know HDL, which is used for fitting logic into some FPGA devices. These compilers are very powerful in logic reduction, so I would try to transform your logic file into such a HDL file (VHDL or ABEL language) and feed that into the HDL Compiler of a FPGA toolchain. You might not get XOR preference over AND, but you will get reduction of terms. \$\endgroup\$ – Stefan Wyss Sep 30 '18 at 19:22
  • \$\begingroup\$ Thanks! This looks like a very good starting point! I'm definitely going to try it out. Yes, I was not expecting to find the preference of XOR over AND in this domain to be honest, but just minimizing terms in general is very useful to me! \$\endgroup\$ – Daniel Sep 30 '18 at 19:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.