Şerife SUNGUN, Yavuz ŞENOL, Mustafa GÜNDÜZALP

GENETİK PROGRAMLAMA İÇİN FPGA ÜZERİNDE EN KÜÇÜK SIRALAMA AĞININ GERÇEKLENMESİ

Bu makale, Altera MaxPlusII aracını Flex 10K FPGA üzerinde kullanarak genetik programlamanın seçim işlemi için en küçük sıralama ağının nasıl gerçeklenebileceğini anlatmaktadır. Zaman alıcı bir işlem olan turnuvadaki bireylerin uygunluk değerlerinin azalan bir düzende sıralanması işleminin hızlandırılmasını sağlamak amacıyla sıralama ağının dört farklı uygulaması gerçeklenmiştir.Özellikle dördüncü sırada gerçeklenen ağ ile FPGA üzerindeki yeniden yapılandıralabilir bilişimin paralel işleme yeteneği yardımıyla karşılaştırma-yerdeğiştirme işlemlerinin toplam sayısı başarılı bir şekilde azaltılmıştır. Böylece, genetik programlamada uygunluk ölçüm işlemi hızlandırılmıştır.

Anahtar Kelimeler:

En küçük sıralama ağı, Yeniden yapılandırılabilir bilişim, Genetik programlama, FPGA

MINIMAL SORTING NETWORK REALIZATION ON FPGA FOR GENETIC PROGRAMMING

This paper describes how the minimal sorting network (MSN) for selection operation of genetic programming can be implemented on Flex10K FPGA by using MaxPlus II tool of Altera.Four different implementations of sorting network have been realised to accelerate the time-consuming process of sorting individuals in the tournament in ascending order of their fitness values.Especially in the fourth one, with the help of the parallel processing capability of the reconfigurable computing on FPGA, total number of comparison-exchange operations has been successfull

Keywords:

Minimal sorting network (MNS), Reconfigurable computing, Genetic programming, FPGA,

PDF

___

Banzhaf, W, Nordin, P., Keller, R.E., Genetic Programming-An Introduction on the Automatic Evolution of Computer Programs and Its Applications, pp. 106-123, Morgan Kaufmann Publishers, San Francisco, 1998.
Koza, J.R, Andre, D., Evolution of Both the Artchitecture and the Sequence of Work-Performing Steps of a Computer Program Using Genetic Programming with Architecture-Altering Operations, AAAI Fall Symposium on Genetic Programming, pp 50-60, November 10-12, 1995.
Heywood, M.I., Zincir-Heywood, A.N., Register Based Genetic Programming on FPGA Computing Platforms, EuroGP2000, 3rd European Conference on Genetic Programming, Lecture Notes in Computer Science. (vol. ), pp 44-59, 2000.
Zhang, X , Ng, K.W. A Review of High-Level Synthesis for Dynamically Reconfigurable FPGAs, Elsevier Science-Microprocessors and Microsystems, 24, 199-211, 2000.
Koza, J.R., Evolving Computer Programs using Rapidly Reconfigurable Field-Programable Gate Arrays and Genetic Programming, FPGA'98 Sixth International Symposium on Field Programmable Gate Arrays, pp. 209- , February 22-24, 1998.
Knuth, D.E., The Art of Computer Programming: Sorting and Searching, volume 3. Addison-Wesley Publishing Company, Reading: MA, 1973.
Salcic, Z., Smailagic, A. Digital Systems Design and Prototyping Using Field Programmable Logic, 2nd ed., Kluwer Academic Publishers, 2000.
Koza, J.R., Genetic Programming II – Automatic Discovery of Reusable Programs, The MIT Press, London, Alfke,P., New,B., Implementing State Machines in LCA devices, In The Programmable Logic Data Book XAPP027.001, San Jose, CA: Xilinx, Inc., pp 8-172 - 8-172, 1996.