Nội dung được dịch bởi AI, chỉ mang tính chất tham khảo
Lập trình di truyền trên các đơn vị xử lý đồ họa
Tóm tắt
Sự có mặt của các thẻ đồ họa mạnh mẽ với chi phí thấp đã thúc đẩy việc triển khai Lập trình Di truyền (GP) trên Các Đơn vị Xử lý Đồ họa (GPU). Công trình của chúng tôi tập trung vào những khả năng mà GPU Nvidia G80 mang lại khi được lập trình bằng ngôn ngữ CUDA. Trong công trình đầu tiên, chúng tôi đã chỉ ra rằng cấu hình này cho phép phát triển các sơ đồ song song tinh vi để đánh giá nhiều chương trình GP một cách song song, đồng thời đạt được tốc độ tăng cho các bộ dữ liệu huấn luyện và kích thước chương trình thông thường. Tại đây, chúng tôi trình bày một sơ đồ song song khác và các tối ưu hóa về cách biểu diễn chương trình cũng như việc sử dụng bộ nhớ nhanh của GPU. Điều này làm tăng tốc độ tính toán lên khoảng ba lần, đạt tới 4 tỷ phép toán GP mỗi giây. Mã nguồn đã được phát triển trong thư viện ECJ nổi tiếng và được công khai nguồn.
Từ khóa
#Lập trình di truyền #GPU #CUDA #song song hóa #tối ưu hóa tính toánTài liệu tham khảo
J.R. Koza, M.A. Keane, M.J. Streeter, W. Mydlowec, J. Yu, G. Lanza, Genetic Programing IV: Routine Human-Competitive Machine Intelligence. (Springer, 2005)
C. Gathercole, P. Ross, Dynamic training subset selection for supervised learning in genetic programming, in Proceedings of the third Conference on Parallel Problem Solving from Nature, volume 866 of Lecture Notes in Computer Science, (Springer, Berlin, 1994), pp. 312–321
C. Gathercole, P. Ross, Tackling the boolean even N parity problem with genetic programming and limited-error fitness, in Proceedings of the Second Annual Conference on Genetic Programming, (Morgan Kaufmann, Los Altos, 1997), pp. 119–127
M. Keijzer, Alternatives in subtree caching for genetic programming, in Genetic Programming 7th European Conference, EuroGP 2004, Proceedings, volume 3003 of LNCS, (Springer, Berlin, 2004), pp. 328–337
C. Fillon, A. Bartoli, A divide and conquer strategy for improving efficiency and probability of success in genetic programming, in Proceedings of the 9th European Conference on Genetic Programming, volume 3905 of Lecture Notes in Computer Science, (Springer, Berlin, 2006), pp. 13–23
W.B. Langdon, Size fair and homologous tree genetic programming crossovers, in Proceedings of the Genetic and Evolutionary Computation Conference, (Morgan-Kaufmann, Los Altos, 1999), pp. 1092–1097
P. Nordin, A compiling genetic programming system that directly manipulates the machine code, in Advances in Genetic Programming, Chapter 14. (MIT Press, Cambridge, 1994), pp. 311–331.
P. Nordin, W. Banzhaf, Evolving turing-complete programs for a register machine with self-modifying code, in Genetic Algorithms: Proceedings of the Sixth International Conference (ICGA95), (Morgan Kaufmann, Los Altos 1995), pp. 318–325
P. Tufts, Parallel case evaluation for genetic programming, in 1993 Lectures in Complex Systems, volume VI of Santa Fe Institute Studies in the Science of Complexity, (Addison-Wesley, Reading, 1995), pp. 591–596
H. Juillé, J.B. Pollack, Massively parallel genetic programming, in Advances in Genetic Programming 2, Chapter 17. (MIT Press, Cambridge, 1996), pp. 339–358
F. Fernandez, M. Tomassini, L. Vanneschi, An empirical study of multipopulation genetic programming. Genet. Programm. Evolvable Mach., 4(1), 21–51, (2003)
S.M. Cheang, K.S. Leung, K.H. Lee, Genetic parallel programming: design and implementation. Evol. Comput., 14(2), 129–156, Summer (2006)
M.L. Wong, T.T. Wong, K.L. Fok, Parallel evolutionary algorithms on graphics processing unit, in Proceedings of IEEE Congress on Evolutionary Computation 2005 (CEC 2005), vol. 3. (Edinburgh, UK, 2005), pp. 2286–2293. IEEE
Q. Yu, C. Chen, Z. Pan, Parallel genetic algorithms on programmable graphics hardware, in Advances in Natural Computation, volume 3162 of LNCS, (Springer, Berlin, 2005), pp. 1051–1059
Z. Luo, H. Liu, Cellular genetic algorithms and local search for 3-sat problem on graphic hardware, in IEEE Congress on Evolutionary Computation—CEC 2006., (2006), pp. 988–2992
K. Kaul, C.-A. Bohn, A genetic texture packing algorithm on a graphical processing unit, in Proceedings of the 9th International Conference on Computer Graphics and Artificial Intelligence (2006)
T.-T. Wong, M.L. Wong, Parallel Evolutionary Computations, Chapter 7. (Springer, Berlin, 2006), pp. 133–154
K.-L. Fok, T.-T. Wong, M.-L. Wong, Evolutionary computing on consumer graphics hardware. IEEE Int. Syst., 22(2), 69–78 (2007)
S. Harding, W. Banzhaf, Fast genetic programming on GPUs, in proceedings of the 10th European Conference on Genetic Programming, EuroGP 2007, volume 4445 of Lecture Notes in Computer Science, (Springer, Berlin, 2007), pp. 90–101
S. Harding, W. Banzhaf, Fast genetic programming and artificial developmental systems on GPUs, in proceedings of the 2007 High Performance Computing and Simulation (HPCS’07) Conference. (IEEE Computer Society, 2007), p. 2
D.M. Chitty, A data parallel approach to genetic programming using programmable graphics hardware, in Proceedings of the 2007 Genetic and Evolutionary Computing Conference (GECCO’07), (ACM Press, London, UK, 2007), pp. 1566–1573
W.B. Langdon, W. Banzhaf, A SIMD interpreter for genetic programming on GPU graphics cards, in Proceedings of the 11th European Conference on Genetic Programming, EuroGP 2008, volume 4971 of Lecture Notes in Computer Science ed by M. O’Neill, L. Vanneschi, S. Gustafson, A.I.E. Alcazar, I. De Falco, A. Della Cioppa, E. Tarantino, (Springer, Naples, 2008) pp. 73–85
D. Robilliard, V. Marion-Poty, C. Fonlupt, Population parallel GP on the G80 GPU, in Proceedings of the 11th European Conference on Genetic Programming, EuroGP 2008, volume 4971 of Lecture Notes in Computer Science ed by M. O’Neill, L. Vanneschi, S. Gustafson, A.I.E. Alcazar, I. De Falco, A. Della Cioppa, E. Tarantino, (Springer, Naples, 2008), pp. 98–109
W.B. Langdon, A.P. Harrison, GP on SPMD parallel graphics hardware for mega bioinformatics data mining, Soft Computing, (2008). Special Issue. On line first
S. Harding, Evolution of image filters on graphics processor units using cartesian genetic programming, in 2008 IEEE World Congress on Computational Intelligence ed by J. Wang, (IEEE Computational Intelligence Society, IEEE Press, Hong Kong, 2008)
D.T. Anderson, R.H. Luke, J.M. Keller, Speedup of fuzzy clustering through stream processing on graphics processing units, in 2008 IEEE World Congress on Computational Intelligence ed by J. Wang, (IEEE Press, Hong Kong, 2008), pp. 1101–1106
S. Luke, L. Panait, G. Balan, S. Paus, Z. Skolicki, E. Popovici, K. Sullivan, J. Harrison, J. Bassett, R. Hubley, A. Chircop, ECJ 18—a Java-based evolutionary computation research system. Available at http://www.cs.gmu.edu/eclab/projects/ecj, (2008)
P. Sanders, Emulating MIMD behavior on SIMD machines, in Proceedings of International Conference on Massively Parallel Processing Applications and Development, (Elsevier, Delft, 1994).
D. Robilliard, V. Marion-Poty, C. Fonlupt, GPURegression: Population parallel GP on G80 GPUs—ECJ compatible code. Available at http://www.lil.univ-littoral.fr/~robillia/GPUregression.html, (2008)
A.V. Aho, R. Sethi, J.D. Ullman, Compilers—Principles, Techniques and Tools. (Addison-Wesley, Reading, 1986)
J.R. Koza, Genetic Programming II: Automatic Discovery of Reusable Programs. (The MIT Press, 1994)
J.R. Koza, Genetic Programming: On the Programming of Computers by Means of Natural Selection. (The MIT Press, 1992)
K.J. Lang, M.J. Witbrock, Learning to tell two spirals apart, in Proceedings of the 1988 Connectionist Summer Schools, ed by Morgan-Kaufmann (1988)
W.B. Langdon, Evolving programs on graphics cards—C++ code. Available at http://www.cs.ucl.ac.uk/external/W.Langdon/ftp/gp-code/gpu_gp_1.tar.gz, (2008)
M. Brameier, W. Banzhaf, Linear Genetic Programming. Number XVI in Genetic and Evolutionary Computation. (Springer, 2007)