Nothing Special   »   [go: up one dir, main page]

skip to main content
research-article

GSGP-hardware: instantaneous symbolic regression with an FPGA implementation of geometric semantic genetic programming

Published: 25 June 2024 Publication History

Abstract

Geometric Semantic Genetic Programming (GSGP) proposed an important enhancement to GP-based learning, incorporating search operators that operate directly on the semantics of the parents with bounded effects on the semantics of the offspring. This approach posed any symbolic regression fitness landscape as a unimodal function, allowing for more directed search. Moreover, it became evident that the search could be implemented in a much more efficient manner, that does not require the execution, evaluation or manipulation of variable length syntactic models. Hence, efficient implementations of this algorithm have been developed using both CPU and GPU processing. However, current implementations are still ill-suited for real-time learning, or learning on devices with limited resources, scenarios that are becoming more prevalent with the continued development of the Internet-of-Things and the increased need for efficient and distributed learning on the Edge. This paper presents GSGP-Hardware, a fully pipelined and parallel design of GSGP developed fully using VHDL, for implementation on FPGA devices. Using Vivado AMD-Xilinx for synthesis and simulation, GSGP-Hardware achieves an approximate improvement in efficiency, in terms of run time and Gpops/s, of three and four orders of magnitude, respectively, compared with the state-of-the-art GPU implementation. This is a performance increase that has not been achieved by other FPGA-based implementations of genetic programming. This is possible due to the manner in which GSGP evolves a model, and competitive accuracy is achieved by incorporating simple but powerful enhancements to the original GSGP algorithm. GSGP-Hardware allows for instantaneous symbolic regression, opening up new application domains for this powerful variant of genetic programming.

References

[1]
Alinodehi SPH, Moshfe S, Zaeimian MS, Khoei A, and Hadidi K High-speed general purpose genetic algorithm processor IEEE Trans. Cybern. 2016 46 7 1551-1565
[2]
A. Amaricai, O. Boncalo, Srt radix-2 dividers with (5, 4) redundant representation of partial remainder, in 2013 NORCHIP (IEEE, 2013)
[3]
C. AMD, Vivado design suite, user guide logic simulation (2018). https://docs.amd.com/v/u/2018.3-English/ug900-vivado-logic-simulation
[4]
C. AMD, Quality and reliability vivado (2023). https://www.xilinx.com/support/quality.html
[8]
C. AMD, Vivado design suite (2023). www.amd.com
[9]
C. AMD, Xilinx system generator for dsp (2023)
[10]
I. Arnaldo, K. Krawiec, U.M. O’Reilly, Multiple regression genetic programming, in GECCO ’14 (Association for Computing Machinery, New York, 2014), pp. 879–886
[11]
Asad A, Kaur R, and Mohammadi F A survey on memory subsystems for deep neural network accelerators Future Internet 2022 14 5 146
[12]
F. Baeta, J. Correia, T. Martins, P. Machado, Tensorgp-genetic programming engine in tensorflow, in Applications of Evolutionary Computation-24th International Conference, EvoApplications 2021 (Springer, 2021)
[13]
Bharany S, Sharma S, Khalaf OI, Abdulsahib GM, Humaimeedy ASA, Aldhyani THH, Maashi M, and Alkahtani H A systematic survey on energy-efficient techniques in sustainable cloud computing Sustainability 2022 14 10 6256
[14]
M. Bhardwaj, Aradhana, A. Kumar, P. Kumar, V. Nath, Digital implementation of sigmoid function in artificial neural network using VHDL, in Nanoelectronics, Circuits and Communication Systems (Springer, Singapore, 2020), pp. 45–53
[15]
J. Brookhouse, F.E. Otero, M. Kampouridis, Working with opencl to speed up a genetic programming financial forecasting algorithm: initial results, in Proceedings of the Companion Publication of the 2014 Annual Conference on Genetic and Evolutionary Computation, GECCO Comp ’14 (Association for Computing Machinery, New York, 2014), pp. 1117–1124
[16]
Brown SZV Fundamentals of Digital Logic 2009 New York McGraw-Hill
[17]
B. Burlacu, G. Kronberger, M. Kommenda, Operon c++: An efficient genetic programming framework for symbolic regression, in Proceedings of the 2020 Genetic and Evolutionary Computation Conference Companion, GECCO ’20 (Association for Computing Machinery, New York, 2020), pp. 1562–1570
[18]
Cappuccino Pa G and Corsonello GC High performance vlsi modules for division and square roots Microprocess. Microsyst. 1998 22 5 239-246
[19]
Castelli M and Manzoni L Gsgp-c++ 2.0: a geometric semantic genetic programming framework SoftwareX 2019 10
[20]
Castelli M, Silva S, and Vanneschi L A c++ framework for geometric semantic genetic programming Genet. Prog. Evolv. Mach. 2015 16 1 73-81
[21]
Castelli M, Trujillo L, Vanneschi L, and Popovič A Prediction of energy performance of residential buildings: a genetic programming approach Energy Build. 2015 102 67-74
[22]
M. Castelli, L. Trujillo, L. Vanneschi, S. Silva, E. Z-Flores, P. Legrand, Geometric semantic genetic programming with local search, in Proceedings of the 2015 Annual Conference on Genetic and Evolutionary Computation, GECCO ’15 (2015), pp. 999–1006
[23]
Chitty DM Faster GPU-based genetic programming using a two-dimensional stack Soft. Comput. 2016 21 14 3859-3878
[24]
M. Clive Max, in FPGA Architectures (Newnes, Burlington, 2008), pp. 13–48
[25]
C. Crary, W. Piard, G. Stitt, C. Bean, B. Hicks, Using FPGA devices to accelerate tree-based genetic programming: A preliminary exploration with recent technologies, in Lecture Notes in Computer Science (Springer, Switzerland, 2023), pp. 182–197
[26]
F.M. De Rainville, F.A. Fortin, M.A. Gardner, M. Parizeau, C. Gagné, Deap: a python framework for evolutionary algorithms, in Proceedings of the 14th Annual Conference Companion on Genetic and Evolutionary Computation, GECCO ’12 (Association for Computing Machinery, New York, 2012), pp. 85–92
[27]
Dibene JC, Maldonado Y, Trujillo L, and Dunn E Prepare for ludicrous speed: marker-based instantaneous binocular rolling shutter localization IEEE Trans. Visual Comput. Graph. 2022 28 5 2201-2211
[28]
C. Digilent, Artix-7 fpga (2023)
[29]
Fernando P, Katkoori S, Keymeulen D, Zebulum R, and Stoica A Customizable FPGA IP core implementation of a general-purpose genetic algorithm engine IEEE Trans. Evol. Comput. 2010 14 1 133-149
[30]
J. Fowers, G. Brown, P. Cooke, G. Stitt, A performance and energy comparison of FPGAs, gpus, and multicores for sliding-window applications, in Proceedings of the ACM/SIGDA International Symposium on Field Programmable Gate Arrays, FPGA ’12 (ACM, 2012)
[31]
Funie AI, Grigoras P, Burovskiy P, Luk W, and Salmon M Run-time reconfigurable acceleration for genetic programming fitness evaluation in trading strategies J. Signal Process. Syst. 2017 90 1 39-52
[32]
Gonçalves I, Silva S, and Fonseca CM Machado P, Heywood MI, McDermott J, Castelli M, García-Sánchez P, Burelli P, Risi S, and Sim K On the generalization ability of geometric semantic genetic programming Genetic Programming 2015 Cham Springer 41-52
[33]
Goribar C, Maldonado Y, and Trujillo L Schütze O, Trujillo L, Legrand P, and Maldonado Y Automatic random tree generator on FPGA NEO 2015. Studies in Computational Intelligence 2016 New York Springer 89-104
[34]
L. Guo, A.I. Funie, D.B. Thomas, H. Fu, W. Luk, Parallel genetic algorithms on multiple FPGAs 43(4), 86–93 (2016)
[35]
L. Guo, D.B. Thomas, W. Luk, Automated framework for general-purpose genetic algorithms in FPGAs, in Applications of Evolutionary Computation (Springer, Berlin, Heidelberg, 2014), pp. 714–725
[36]
A. Guyot, L. Montalvo, A. Houelle, H. Mehrez, N. Vaucher, Comparison of the layout synthesis of radix-2 and pseudo-radix-4 dividers, in Proceedings of the 8th International Conference on VLSI Design, ICVD-95 (IEEE Comput. Soc. Press, 1995)
[37]
D.L.N. Hettiarachchi, V.S.P. Davuluru, E.J. Balster, Integer vs. floating-point processing on modern FPGA technology, in 2020 10th Annual Computing and Communication Workshop and Conference (CCWC) (IEEE, 2020)
[38]
Ho TK The random subspace method for constructing decision forests IEEE Trans. Pattern Anal. Mach. Intell. 1998 20 8 832-844
[39]
J. Hopf, A parameterizable handelc divider generator for FPGAs with embedded hardware multipliers, in IEEE International Conference on Field-Programmable Technology (IEEE, New York), pp. 355–358
[40]
R. Hrbacek, M. Sikulova, Coevolutionary cartesian genetic programming in FPGA, in Advances in Artificial Life, ECAL 2013 (MIT Press, 2013)
[41]
L.Y. Hu, Y. Dongming, H. Hefei, A wrapper of pci express with fifo interfaces based on FPGA. arvix 1(5), 1–5 (2013)
[42]
Hua H, Li Y, Wang T, Dong N, Li W, and Cao J Edge computing with artificial intelligence: a machine learning perspective ACM Comput. Surv. 2023
[43]
Huerta EA, Khan A, Davis E, Bushell C, Gropp WD, Katz DS, Kindratenko V, Koric S, Kramer WTC, McGinty B, McHenry K, and Saxton A Convergence of artificial intelligence and high performance computing on NSF-supported cyberinfrastructure J. Big Data 2020 7 1
[44]
Ibarra-Vazquez G, Olague G, Chan-Ley M, Puente C, and Soubervielle-Montalvo C Brain programming is immune to adversarial attacks: towards accurate and robust image classification using symbolic learning Swarm Evol. Comput. 2022 71
[45]
C. Intel, FPGA optimization guide for intel (2023). www.intel.com
[46]
Koza JR Human-competitive results produced by genetic programming Genet. Prog. Evol. Mach. 2010 11 3–4 251-284
[47]
W. La Cava, P. Orzechowski, B. Burlacu, F. de Franca, M. Virgolin, Y. Jin, M. Kommenda, J. Moore, Contemporary symbolic regression methods and their relative performance, in Proceedings of the Neural Information Processing Systems Track on Datasets and Benchmarks, ed. by J. Vanschoren, S. Yeung (eds), vol. 1 (Curran, 2021)
[48]
W.B. Langdon, A many threaded CUDA interpreter for genetic programming, in Lecture Notes in Computer Science (Springer, Berlin, Heidelberg, 2010), pp. 146–158
[49]
W.B. Langdon, Failed disruption propagation in integer genetic programming, in Proceedings of the Genetic and Evolutionary Computation Conference Companion, GECCO ’22 (Association for Computing Machinery, New York, 2022), pp. 574–577
[50]
Langdon WB Jaws 30 Genet. Program. Evolv. Mach. 2023
[51]
Letras M, Morales-Reyes A, and Cumplido R A scalable and customizable processor array for implementing cellular genetic algorithms Neurocomputing 2016 175 899-910
[52]
G. Louppe, P. Geurts, Ensembles on random patches, in Machine Learning and Knowledge Discovery in Databases (Springer, Berlin, Heidelberg, 2012), pp. 346–361
[53]
Lu Y Industry 4.0: a survey on technologies, applications and open research issues J. Ind. Inform. Integr. 2017 6 1-10
[54]
Martin P A hardware implementation of a genetic programming system using FPGAs and handel-c Genet. Prog. Evolv. Mach. 2001 2 4 317-343
[55]
Matula DW, Panu MT, and Zhang JY Multiplicative division employing independent factors IEEE Trans. Comput. 2015 64 7 2012-2019
[56]
Martínez Y, Naredo E, Trujillo L, Legrand P, and López U A comparison of fitness-case sampling methods for genetic programming J. Exp. Theor. Artif. Intell. 2017 29 6 1203-1224
[57]
McCann M and Pippenger N Srt division algorithms as dynamical systems SIAM J. Comput. 2005 6 34 1279-1301
[58]
L. Montalvo, A. Guyot, Svoboda-tung division with no compensation, in Proceedings of the 8th International Conference on VLSI Design (IEEE, New York, 1995), pp. 381–385
[59]
A. Moraglio, K. Krawiec, C.G. Johnson, Geometric semantic genetic programming, in Proceedings of the 12th International Conference on Parallel Problem Solving from Nature-Volume Part I, PPSN’12 (2012), pp. 21–31
[60]
Olague G and Trujillo L Evolutionary-computer-assisted design of image operators that detect interest points using genetic programming Image Vis. Comput. 2011 29 7 484-498
[61]
I. Ortigosa, R. Lopez, J. G, A neural networks approach to residuary resistance of sailing yachts prediction, in Proceedings of the International Conference on Marine Engineering MARINE (2007), p. 250
[62]
Patankar US and Koel A Review of basic classes of dividers based on division algorithm IEEE Access 2021 9 23035-23069
[63]
M. Qasaimeh, K. Denolf, J. Lo, K. Vissers, J. Zambreno, P.H. Jones, Comparing energy efficiency of CPU, GPU and FPGA implementations for vision kernels, in 2019 IEEE International Conference on Embedded Software and Systems (ICESS) (IEEE, 2019)
[64]
J.R. Quinlan, Combining instance-based and model-based learning, in Machine Learning, Proceedings of the Tenth International Conference (University of Massachusetts, Amherst, 1993), pp. 236–243
[65]
Real E, Aggarwal A, Huang Y, and Le QV Regularized evolution for image classifier architecture search Proc. AAAI Conf. Artif. Intell. 2019 33 01 4780-4789
[66]
E. Real, C. Liang, D. So, Q. Le, AutoML-zero: Evolving machine learning algorithms from scratch, in Proceedings of the 37th International Conference on Machine Learning, Proceedings of Machine Learning Research, vol. 119, ed. by H.D. III, A. Singh (PMLR, 2020), pp. 8007–8019
[67]
E. Real, S. Moore, A. Selle, S. Saxena, Y.L. Suematsu, J. Tan, Q.V. Le, A. Kurakin, Large-scale evolution of image classifiers, in Proceedings of the 34th International Conference on Machine Learning, Proceedings of Machine Learning Research, vol. 70, ed. by D. Precup, Y.W. Teh (PMLR, 2017), pp. 2902–2911
[68]
Robertson JE A new class of digital division methods IRE Trans. Electron. Comput. 1958 EC–7 3 218-222
[69]
Robilliard D, Marion-Poty V, and Fonlupt C Genetic programming on graphics processing units Genet. Prog. Evolv. Mach. 2009 10 4 447-471
[70]
C. Rudin, Do simpler models exist and how can we find them?, in Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, KDD ’19 (Association for Computing Machinery, New York, 2019), pp. 1–2
[71]
Rudin C Stop explaining black box machine learning models for high stakes decisions and use interpretable models instead Nat. Mach. Intell. 2019 1 5 206-215
[72]
A. Rushton, Vhdl for logic synthesis, in VHDL for Logic Synthesis (Wiley, 2011), pp. 1–496
[73]
Said O A bandwidth control scheme for reducing the negative impact of bottlenecks in IoT environments: simulation and performance evaluation Internet Things 2023 21
[74]
Salih KOM, Rashid TA, Radovanovic D, and Bacanin N A comprehensive survey on the internet of things with the industrial marketplace Sensors 2022 22 3 730
[75]
I.H. Sarker, Deep learning: a comprehensive overview on techniques, taxonomy, applications and research directions. SN Comput. Sci. 2(6) (2021)
[76]
Schmit H, Cadambi S, and Moe M Pipeline reconfigurable FPGAs J. VLSI Signal Process. Syst. 2000 24 129-146
[77]
Shackleford B, Snider G, Carter RJ, Okushi E, Yasuda M, Seo K, and Yasuura H A high-performance, pipelined, FPGA-based genetic algorithm machine Genet. Prog. Evolv. Mach. 2001 2 1 33-60
[78]
R.P.S. Sidhu, A. Mei, V.K. Prasanna, Genetic programming using self-reconfigurable FPGAs, in Field Programmable Logic and Applications (Springer, Berlin, Heidelberg, 1999), pp. 301–312
[79]
M. Sipper, W. Fu, K. Ahuja, J.H. Moore, Investigating the parameter space of evolutionary algorithms. BioData Min. 11(1) (2018)
[80]
K. Sörensen, M. Sevaux, F. Glover, A history of metaheuristics, in Handbook of Heuristics (Springer, 2018), pp. 1–18
[81]
Soronkin N Implementation of high-speed fixed-point dividers on FPGA J. Comput. Sci. Technol. 2006 6 1 8-11
[82]
K. Staats, E. Pantridge, M. Cavaglia, I. Milovanov, A. Aniyan, Tensorflow enabled genetic programming, in Proceedings of the Genetic and Evolutionary Computation Conference Companion, GECCO ’17 (Association for Computing Machinery, New York, 2017), pp. 1872–1879
[83]
Strubell E, Ganesh A, and McCallum A Energy and policy considerations for modern deep learning research Proc. AAAI Conf. Artif. Intell. 2020 34 09 13693-13696
[84]
Suganuma M, Kobayashi M, Shirakawa S, and Nagao T Evolution of deep convolutional neural networks using cartesian genetic programming Evol. Comput. 2020 28 1 141-163
[85]
G. Sutter, J.P. Deschamps, High speed fixed point dividers for FPGAs, in 2009 International Conference on Field Programmable Logic and Applications (IEEE, 2009)
[86]
Tocher K Techniques of multiplication and division for automatic binary computers Q. J. Mech. Appl. Math. 1998 11 3 364-384
[87]
J. Togelius, G.N. Yannakakis, Choose your weapon: Survival strategies for depressed ai academics (2023)
[88]
Trujillo L, Álvarez González E, Galván E, Tapia JJ, and Ponsich A On the analysis of hyper-parameter space for a genetic programming system with iterated f-race Soft. Comput. 2020 24 19 14757-14770
[89]
Trujillo L, Muñoz Contreras JM, Hernandez DE, Castelli M, and Tapia JJ Gsgp-cuda—a cuda framework for geometric semantic genetic programming SoftwareX 2022 18
[90]
Tsanas A and Xifara A Accurate quantitative estimation of energy performance of residential buildings using statistical machine learning tools Energy Build. 2012 49 560-567
[91]
Vanneschi L, Castelli M, and Silva S A survey of semantic methods in genetic programming Genet. Prog. Evolv. Mach. 2014 15 2 195-214
[92]
L. Vanneschi, S. Silva, M. Castelli, L. Manzoni, Geometric Semantic Genetic Programming for Real Life Applications (Springer, New York, 2014), pp. 191–209
[93]
Z. Vasicek, L. Sekanina, Hardware accelerators for cartesian genetic programming, in Lecture Notes in Computer Science (Springer, Berlin, Heidelberg, 2008), pp. 230–241
[94]
Z. Vašíček, L. Sekanina, Hardware accelerator of cartesian genetic programming with multiple fitness units. Comput. Inform. 29(6+), 1359–1371 (2012)
[95]
Wang H, Qu Z, Zhou Q, Zhang H, Luo B, Xu W, Guo S, and Li R A comprehensive survey on training acceleration for large machine learning models in IoT IEEE Internet Things J. 2022 9 2 939-963
[96]
Wang J, Wang C, Lin Q, Luo C, Wu C, and Li J Adversarial attacks and defenses in deep learning for image recognition: a survey Neurocomputing 2022 514 162-181
[97]
Xu X and Yu Z FPGA-Based PCI Data Acquisition Synchronization Card of Railway Clearance Detection System 2011 Berlin, Heidelberg Springer 15-23
[98]
Yang Y, Wu L, Yin G, Li L, and Zhao H A survey on security and privacy issues in internet-of-things IEEE Internet Things J. 2017 4 5 1250-1258
[99]
Yeh I Modeling of strength of high-performance concrete using artificial neural networks Cement Concr. Res. 1998 28 12 1797-1808

Recommendations

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Genetic Programming and Evolvable Machines
Genetic Programming and Evolvable Machines  Volume 25, Issue 2
Dec 2024
170 pages

Publisher

Kluwer Academic Publishers

United States

Publication History

Published: 25 June 2024
Accepted: 10 June 2024
Revision received: 21 May 2024
Received: 31 May 2023

Author Tags

  1. Genetic programming
  2. Geometric semantic genetic programming
  3. VHDL
  4. FPGA

Qualifiers

  • Research-article

Funding Sources

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • 0
    Total Citations
  • 0
    Total Downloads
  • Downloads (Last 12 months)0
  • Downloads (Last 6 weeks)0
Reflects downloads up to 17 Dec 2024

Other Metrics

Citations

View Options

View options

Media

Figures

Other

Tables

Share

Share

Share this Publication link

Share on social media