A hybrid PSO-GA algorithm for Reversible Circuits Synthesis

• Autorzy: Podlaski K.

Warianty tytułu

PL

Hybrydowy algorytm PSO-GA dla syntezy układów odwracalnych

• Języki publikacji: EN

Abstrakty

EN

In the domain of Reversible Circuits there is still lack of good synthesis algorithms. There are many heuristic propositions, unfortunately, their results for a given reversible function usually are circuits far from optimal implementations. There are some propositions of using Particle Swarm Optimization (PSO) and Genetic Algorithms (GA) for this purpose. In this paper a new hybrid PSO-GA algorithm is proposed. Comparison of the proposed algorithm with the existing ones gives promising results.

PL

W dobie poszukiwania układów cyfrowych o niskim zużyciu energii układy odwracalne stanowią ciekawą alternatywę dla aktualnie stosowanych układów cyfrowych. Jednym z najistotniejszych zagadnień w dziedzinie budowy układów cyfrowych jest synteza układu reprezentującego zadaną funkcję. Niestety do dzisiaj nie ma dobrych rozwiązań w dziedzinie syntezy układów odwracalnych, istniejące rozwiązania są bardzo czasochłonne bądź generują układy o dużej redundancji. Ciekawą alternatywą dla obecnie stosowanych metod heurystycznych jest wykorzystanie algorytmów ewolucyjnych np. Particle Swarm Optimization (PSO) lub algorytmów genetycznych (GA). W niniejszym artykule zaproponowano nowy hybrydowy algorytm PSO-GA dostosowany do syntezy odwracalnych układów cyfrowych. Stworzony algorytm zastosowano do syntezy układów dla wybranych funkcji testowych (tzw. benchmarków) a wyniki porównano z wynikami otrzymywanymi za pomocą algorytmów heurystycznych. Wygenerowane układy okazały się mniej redundantne niż układy otrzymane w syntezie metodami heurystycznymi.

Słowa kluczowe

EN

reversible circuits; reversible logic synthesis; particle swarm optimization (PSO); genetic algorithms

PL

układy odwracalne; synteza układów odwracalnych; particle swarm optimization; algorytmy genetyczne

• Wydawca: Wydawnictwo PAK
• Czasopismo: Pomiary Automatyka Kontrola
• Rocznik: 2014
• Tom: R. 60, nr 7
• Strony: 474--476
• Opis fizyczny: Bibliogr. 14 poz., tab.

Twórcy

autor

Podlaski K.

• Faculty of Physics and Applied Informatics, University of Lodz, Pomorska 149/153, 90-236 Łódź

Bibliografia

• [1] Landauer R.: Irreversibility and Heat Generation in the Computing Process, IBM Journal, Vol. 5 pp 183-191, 1961.
• [2] Bennett C. H.: Logical reversibility of computation, IBM Journal of Research and Development, vol. 17, no. 6, pp. 525-532, 1973.
• [3] Nielsen M, Chuang I.: Quantum Computation and quantum Information, Cambridge University Press, 2000.
• [4] Kerntopf P., Perkowski M., Podlaski K.: Synthesis of Reversible Circuits: A View on the State-of-the-Art, in Nanotechnology (IEEENANO), 2012 12th IEEE Conference on. IEEE, pp. 1-6, 2012.
• [5] Datta, K., Sengupta, I., Rahaman, H.: Particle Swarm Optimization Based Circuit Synthesis of Reversible Logic. In Electronic System Design (ISED), 2012 International Symposium on. IEEE. pp. 226-230, 2012.
• [6] Li, M., Zheng, Y., Hsiao, M. S., & Huang, C.: Reversible logic synthesis through ant colony optimization. In Design, Automation & Test in Europe Conference & Exhibition (DATE), IEEE, pp. 307-310, 2010.
• [7] Saeedi M., Markov I. L.: Synthesis and optimization of reversible circuits – a survey, ACM Computing Surveys, Vol. 45, Issue 2, 2012.
• [8] Maslov D. , Dueck G.W.: Improved Quantum Cost for n-bit Toffoli Gates, IEE Electronic Letters, vol. 39, 2003, no 25.
• [9] Kennedy J., Eberhart R.: Particle swarm optimization. In Proceedings of IEEE international conference on neural networks, Vol. 4, no. 2, pp. 1942-1948, 1995.
• [10] Poli R.: Analysis of the publications on the applications of particle swarm optimisation. Journal of Artificial Evolution and Applications, 685175, 2008.
• [11] Hu X., Eberhart R.C., Shi Y.: Swarm intelligence for permutation optimization: A case study of n-queens problem, in: Proceedings of the 2003 IEEE Swarm Intelligence Symposium, (2003).
• [12] Eiben, A. E., Raue, P. E., Ruttkay, Z.: Genetic algorithms with multiparent recombination. In Parallel Problem Solving from Nature-PPSN III, pp. 78-87, 1994.
• [13] Maslov D.: Reversible Logic Synthesis Benchmarks Page, http://www.cs.uvic.ca/~dmaslov.
• [14] Soeken M., Frehse S., Wille R., Drechsler R.: RevKit: A toolkit for reversible circuit design, Proc. Workshop on Reversible Computation, 2010, pp. 69-72, available at http://www.revkit.org.