ارائه روشي براي سنتز بهينه مدارهای برگشت‌پذير با بکارگيري الگوريتم‌هاي متاهيوريستيک
محورهای موضوعی :
مریم محمودی
1
*
,
ندا اشرفی خوزانی
2
,
علی قربانی
3
1 - دانشکده مهندسي کامپيوتر، واحد ميمه، دانشگاه آزاد اسلامي، ميمه، ايران
2 - دانشکده مهندسي کامپيوتر، واحد ميمه، دانشگاه آزاد اسلامي، ميمه، ايران
3 - دانشکده مهندسي کامپيوتر، واحد ميمه، دانشگاه آزاد اسلامي، ميمه، ايران
کلید واژه: مدارهای برگشت‌پذير, بهينه سازي, الگوريتم‌هاي متاهيوريستيک. ,
چکیده مقاله :
يک مدار منطقي برگشت‌پذير، مداري است که از گيت‌هاي برگشت‌پذير تشکيل شده است و ميان ورودي و خروجي‌هاي آن يک تناظر يک به يک برقرار است. اين ويژگي باعث مي‌شود ورودي منحصر به فرد متناظر با هر خروجي، قابليت بازيابي داشته باشد و اتلاف اطلاعات در اين نوع مدارها اتفاق نيفتد. تاکنون تلاش‌هاي متعددي در زمينه‌ي سنتز خودکار مدارهای برگشت‌پذير به خصوص به کمک روش‌هاي مهندسي دانش انجام شده است. در اين پژوهش مساله‌ي سنتز خودکار مدارهای برگشت‌پذير به صورت نوآورانهاي به يک مساله بهينه‌سازي چند معياره مدلسازي شده و سپس يک روش جديد ترکيبي از الگوريتم‌هاي متاهيوريتسک ژنتيک و خفاش، براي حل اين مساله بهينه‌سازي ارائه شد. در معماری روش پیشنهادی، مدارهای برگشت‌پذیر ابتدا به صورت کروموزوم در الگوریتم ژنتیک و مکان در الگوریتم خفاش کدگذاری می‌شوند. سپس با سازوکار اشتراکگذاری جمعیت میان دو الگوریتم، از مزایای جستجوی سراسری ژنتیک و جستجوی محلی دقیق الگوریتم خفاش به صورت مکمل بهره‌برداری می‌شود. روش پیشنهادی در مقایسه با هر یک از این الگوریتم‌ها نتایج بهتری به‌ویژه از نظر هزینه کوآنتومی و تأخیر دارد. برای مثال، در مدار مکمل-2 هزینه کوآنتومی از 25 و 22 به 19 و تأخیر از 20 و 14 به 12 کاهش یافته است. همچنین در مدار تمام‌جمع‌کننده تعداد خروجی‌های زائد از 18 به 9 رسیده که نشان‌دهنده بهبود قابل توجه است.
A reversible logic circuit is a circuit that consists of reversible gates, and there is a one-to-one correspondence between its inputs and outputs. These circuits have a unique input corresponding to each output, and information loss does not occur as a result. So far, many attempts have been made in the field of automatic synthesis of reversible circuits, especially with the help of knowledge engineering methods. In this research, the problem of automatic synthesis of reversible circuits was innovatively modeled into a multi-criteria optimization problem, and then a new combination of genetic and bat metaheuristic algorithms was presented to solve this optimization problem. The architecture of the proposed method encodes reversible circuits as chromosomes in the genetic algorithm and as positions in the bat algorithm. By automatically sharing populations between the two algorithms, the method exploits the global exploration ability of GA and the local exploitation capability of BA in a complementary manner. The proposed method outperforms each algorithm individually, especially in quantum cost and delay. For example, in the 2’s complement circuit, the quantum cost drops from 25 and 22 to 19, with the delay reduced to 12. In the full adder, garbage outputs decrease from 18 to 9, indicating significant improvement.
- ارائه روشی بهینه برای سنتز مدارهای برگشت‌پذیر با ترکیب الگوریتم‌های ژنتیک و خفاش.
- افزایش کارآیی، بهبود هزینه کوانتومی و تأخیر مدار با روش پیشنهادی اشتراکگذاری جمعیت بین الگوریتم‌ها.
- افزایش سرعت سنتز روش پیشنهادی در مقایسه با روشهای موجود.
[1] R. Wille, M. Soeken, D.M. Miller, and R. Drechsler, “circuit lines and gate costs in the synthesis of reversible logic,” Integration, vol. 48, pp. 284-294, Mar. 2014, doi: 10.1016/j.vlsi.2013.08.002.
[2] P. W. Shor, “Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer,” SIAM J. Sci. Statist. Comput. , vol. 41, pp. 303-332, 1999, doi: 10.1137/S0097539795293172.
[3] A. M. Steane, “Error Correcting Codes in Quantum Theory,” Physical Review Letters, vol. 77, pp.793-797, July 1996, doi: 10.1103/PhysRevLett.77.793.
[4] R. Wille and R. Drechsler, “BDD-based synthesis of reversible logic for large functions,” 46th ACM/IEEE Design Automation Conference, 2009, pp. 270-275, doi: 10.1145/1629911.1629984.
[5] C. P. Williams and A. G. Gray, “Automated Design of Quantum Circuits,” NASA International Conference on Quantum Computing and Quantum Communications (Springer), pp. 113-135, 1999, doi: 10.1007/3-540-49208-9_8.
[6] S. A. Mirjalili, “Evolutionary Algorithms and Neural Networks Theory and Applications,” Springer, vol. 780, pp. 43-55, 2019.
[7] M. Kumar, M. Husain, N. Upreti, and D. Gupta, “Genetic Algorithm: Review and Application,” International Journal of Information Technology and Knowledge Management vol. 2, no. 2, pp. 451-454, 2010.
[8] H. Thapliyal and N. Ranganathan, “Design of Reversible Latches Optimized for Quantum Cost, Delay and Garbage Outputs,” 23rd International Conference on VLSI Design, 2010, pp. 235-240, doi: 10.1109/VLSI.Design.2010.74.
[9] H. Thapliyaland and N. Ranganathan, “Design of reversible sequential circuits optimizing quantum cost, delay, and garbage outputs,” ACM Journal on Emerging Technologies in Computing Systems, vol. 6, no. 4, pp. 1-31, Dec. 2010, doi: 10.1145/1877745.1877748.
[10] B. Sen, M. Dutta, S. Some, and B. K. Sikdar, “Realizing Reversible Computing in QCA Framework Resulting in Efficient Design of Testable ALU,” ACM Journal on Emerging Technologies in Computing Systems, vol. 11, no. 3, pp. 1-22, Dec. 2014, doi: 10.1145/2629538.
[11] A. Barenco, C. H. Bennett, R. Cleve, D. P. DiVincenzo, N. Margolus, P. Shor, T. Sleator, J. Smolin, and H. Weinfurter, “Elementary gates for quantum computation,” Physical Review Letters, vol. 52, pp. 34-57, Mar. 1995, doi: 10.1103/PhysRevA.52.3457.
[12] W. N. N. Hung, Xiaoyu Song, Guowu Yang, Jin Yang, and M. Perkowski, “Optimal synthesis of multiple output Boolean functions using a set of quantum gates by symbolic reachability analysis,” in IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 25, no. 9, pp. 1652-1663, Sept. 2006, doi: 10.1109/TCAD.2005.858352.
[13] M. Morrison, “Design of a reversible ALU based on novel reversible logic structures,” University of South Florida, 2012.
[14] J. A. Smolin and D. P. DiVincenzo, “Five two-bit quantum gates are sufficient to implement the quantum Fredkin gate,” Physical Review A, vol. 53, pp. 28-55, Apr. 1996, doi: 10.1103/PhysRevA.53.2855.
[15] X. S. Yang, “A New Metaheuristic Bat-Inspired Algorithm,” Nature Inspired Cooperative Strategies for Optimization (NICSO 2010)-Springer, vol. 284, pp. 65-74, 2010, doi:10.1007/978-3-642-12538-6_6.
[16] R. Seyghaly, J. Garcia, X. Masip-Bruin, and M. M. Varnamkhasti, “Interference Recognition for Fog Enabled IoT Architecture using a Novel Tree-based Method,” IEEE International Conference on Omni-layer Intelligent Systems (COINS), 2022, pp. 1-6, doi: 10.1109/COINS54846.2022.9854944.
[17] A. Ghorbani, M. Dolatshahi, S. M. Zanjani, and B. Barekatain, “A new low-power Dynamic-GDI full adder in CNFET technology,” Integration, vol. 83, pp. 46–59, Mar. 2022, doi: doi: 10.1016/j.vlsi.2021.12.001.
[18] A. Ghorbani, Mehdi Dolatshahi, S. Mohammadali Zanjani, and Behrang Barekatain, “A New Low Power, Area Efficient 4-bit Carry Look Ahead Adder in CNFET Technology,” Majlesi Journal of Electrical Engineering, vol. 16, no. 1, pp. 65–73, Mar. 2022, doi: 10.52547/mjee.16.1.65.