| Three level logic minimization using graphics processing units |
|
 |
|
|
| Authors |
| | Nadolenko V.V. |
| Date of publication |
| | 2022 |
| DOI |
| | 10.31114/2078-7707-2022-4-9-14 |
|
| Abstract |
| | This paper presents a method for three level logic minimization. It takes inspiration from two level minimization algorithm Espresso and attempts to enhance its capabilities by working with more complex Boolean formulae. Espresso only processes sums or products resulting in two level logic circuits at the output. Proposed algorithm called Xpresso works with sums of pseudo-products that consist from product of some literals and XOR of some other literals. This allows better global optimization before running any local multi-level minimization algorithms. Pseudo-product processing relies on Espresso principles of expanding cubes and removing redundant ones. Classic cube is a subspace of minimized function’s domain in which the function takes value of 1. Three level cube also defines a subspace but it can be filled with 1’s in a XOR pattern instead. Taking that into account allows introducing new expansion principles. Espresso cubes can only expand as long as they do not run into blocking areas of inverted function. Xpresso cubes, however, not necessarily conflict with function’s off-set on overlap as they can also include off-set areas. This complicates expansion’s validity function but it still can be converted to product of sums form under some restrictions. Hence maximal expansion can be found as a solution to set covering problem, similar to Espresso’s approach. In the same fashion this paper suggests a way to irredundant algorithm on three level cubes. Furthermore, expand’s computations up until set covering are represented in matrix form and can be performed with graphics processing unit. Both expand and irredundant were compared to those in Espresso by their effectiveness measured in number of cubes, literals, operations and average expansions in resulting functions. Results show that further research has promising perspectives. |
| Keywords |
| | logic synthesis, two level minimization, three level minimization, espresso. |
| Library reference |
| | Nadolenko V.V. Three level logic minimization using graphics processing units // Problems of Perspective Micro- and Nanoelectronic Systems Development - 2022. Issue 4. P. 9-14. doi:10.31114/2078-7707-2022-4-9-14 |
| URL of paper |
| | http://www.mes-conference.ru/data/year2022/pdf/D087.pdf |
