Синтез параллельных сумматоров по if-диаграммам решений

Сложение является одной из критичных ко времени операций в большинстве современных процессоров. В течение десятилетий проводились обширные исследования, посвященные проектированию высокоскоростных и менее сложных архитектур сумматоров, а также разработке передовых технологий реализации сумматоров. Диаграммы решений являются перспективным подходом к эффективному проектированию многоразрядных сумматоров. Поскольку традиционные двоичные диаграммы решений не полностью соответствуют задаче моделирования архитектур сумматоров, были предложены другие типы диаграмм. If-диаграммы решений являются параллельной моделью многоразрядного сумматора с временной сложностью О(log2n) и технической сложностью О(n×log2n). Настоящая статья предлагает метод систематического разрезания длинных путей в графе диаграммы, который порождает модели сумматоров с такими характер истиками, Сумматоры на базе if-диаграмм конкурентоспособны по сравнению с сумматором Брент-Кунга и его многочисленными модификациями. Мы предлагаем блочную структуру параллельных сумматоров, построенных на if-диаграммах, и вводим их табличное представление, которое способно систематически создавать модели на основе диаграмм любой битовой ширины. Табличное представление сумматоров поддерживает эффективное отображение диаграмм в VHDL-модули на структурном и потоковом уровнях. В статье также исследовано пространство сумматоров посредством изменения коэффициента разветвления выходов. Результаты синтеза на основе ПЛИС и сравнения конкретных сумматоров, построенных на if-диаграммах, с сумматорами Брента-Кунга и мажоритарно-инверторными сумматорами показывают, что новые сумматоры дают более быстрые цифровые схемы меньшего размера.

1. T.-K. Liu, K. R. Hohulin, L.-E. Shiau, S. Muroga. «Optimal One-Bit Full-Adders with Different Types of Gates». IEEE Transactions on Computers. Bell Laboratories: IEEE, 1974, C-23 (1): 63–70.

2. Rosenberger, G. B. «Simultaneous Carry Adder». U. S. Patent 2,966,305. (1960–12–27).

3. P. M. Kogge, H. S. Stone. «A Parallel Algorithm for the Efficient Solution of a General Class of Recurrence Equations». IEEE Transactions on Computers. 1973, C-22 (8): 786–793.

4. R. P. Brent, H. Te Kung, «A Regular Layout for Parallel Adders». IEEE Transactions on Computers. 1982, C-31, (3): 260–264.

5. N. Poornima, V. S. Kanchana Bhaaskaran. «Area Efficient Hybrid Parallel Prefix Adders». Procedia Materials Science 10 (2015), pp. 371–380.

6. L. Amarú, P.-E. Gaillardon, G. De Micheli, «Majority-Inverter Graph: A New Paradigm for Logic Optimization,» IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 35, no. 5, pp. 806–819, May 2016.

7. L. Amarú, P.-E. Gaillardon, A. Chattopadhyay, G. De Micheli, «A Sound and Complete Axiomatization of Majority-n Logic,» IEEE Transactions on Computers, vol. 65, no. 9, pp. 2889–2895, September 2016.

8. V. Tenace, A. Calimera, E. Macii, M. Poncino. «Pass-XNOR logic: A new logic style for P-N junction based graphene circuits». DATE, 2014, pp.1–4.

9. Prihozhy, A.A. If-Diagrams: Theory and Application / A.A. Prihozhy // Proc. 7th Int. Workshop PATMOS’97. – UCL, Belgium, 1997. – P. 369–378.

10. Prihozhy, A.A. Parallel Computing with If-Decision-Diagrams / A.A. Prihozhy, P. U. Brancevich // Proc. Int. Conference PARELEC’98. – Poland, Technical University of Bialystok. – 1998. – P. 179–184.

11. Прихожий А. А. Частично определенные логические системы и алгоритмы / А. А. Прихожий / Минск, БНТУ. – 2013. – 343 с.

12. Прихожий, А. А. Обобщение разложения Шеннона для частично определенных функций: теория и применение / А. А. Прихожий / Системный анализ и прикладная информатика. – 2013, № 1–2. – С. 6–11.

13. C. Y. Lee, Representation of Switching Circuits by Binary-Decision Programs, Bell Systems Technical Journal, 1959, Vol. 38, No 4, pp. 985–999.

14. L. Amarú, P.-E. Gaillardon, G. De Micheli. «Biconditional BDD: a novel canonical BDD for logic synthesis targeting XOR-rich circuits,» in DATE’13, 2013, pp. 1014–1017.

15. A. Bernasconi et al., «On decomposing Boolean functions via extended cofactoring,» in DATE, 2009, pp. 1464–1469.

16. V. Tenace, A. Calimera, E. Macii, M. Poncino. One-pass logic synthesis for graphene-based Pass-XNOR logic circuits. DAC, 2015: 128:1–128:6.

17. Prihozhy, A.A. If-Decision Diagram Based Synthesis of Digital Circuits / A.A. Prihozhy // Proc. Int. Conf. «Information Technologies for Education, Science and Business». – Minsk, Belarus. – 1999. – P. 65–69.

18. Prihozhy, A.A. If-Decision Diagram Based Modeling and Synthesis of Incompletely Specified Digital Systems / A.A. Prihozhy, B. Becker // Electronics and communications, Electronics Design. – Kyiv. – 2005, pp. 103–108.

19. Prihozhy, A.A. Analysis, transformation and optimization for high performance parallel computing / A.A. Prihozhy // Minsk, BNTU. – 2019. – 229 p.

20. IEEE Standard VHDL Language Reference Manual. The Institute of Electrical and Electronics Engineers, Inc. – 2000. – 299 p.

21. Prihozhy, A.A. High-Level Synthesis through Transforming VHDL Models / A.A. Prihozhy // Chapter in Book «Systemon-Chip Methodologies and Design Languages». – Kluwer Academic Publishers. – 2001. – P. 135–146.

22. Quartus Prime Lite Edition [Electronic resource]. – Access mode: https://fpgasoftware.intel.com/?edition=lite. – Date of access: 24.04.2020.