1. 개요
병렬처리 시스템은 최근에 가장 주목 받고 있는 컴퓨팅 성능 향상 기술 중에 하나입니다. 물론 과거에도 병렬처리 시스템이 주목 받아 왔지만, 그 당시에는 CPU 의 업그레이드 만으로도 50%, 100% 이상의 성능향상을 이룰 수 있었기에 지금보다는 적은 관심을 보였었습니다. 그러나 현재의 CPU 가 가진 한계에 거의 다다름에 따라, 성능 개선의 기법으로 병렬처리 기법들이 주목을 받고 있습니다. 즉, 하드웨어적 한계를 소프트웨어 적인 기법으로서 넘어서려고 한다고 표현할 수 있겠습니다.
이 병럴처리 시스템은 크게 내부, 외부의 두 가지 요소로서 존재한다고 볼 수 있겠습니다. 내부 요소로서는 CPU 의 멀티 코어화, GPU 의 발전 등을 들 수 있겠고, 외부적으로는 대규모 네트워크로 구성된 컴퓨팅 환경을 제공하는 것이 되겠습니다. 대표적으로는 근래에 각광을 받고 있는 클라우드 컴퓨팅이 있겠습니다.
진화연산은 기존의 알고리즘 들에 비해 엄청난 반복작업이 필요하며, 거대한 리소스를 갖출수록 더 좋은 효과를 가질 수 있는 특징이 있습니다. 이 거대한 리소스에 대한 것은 반박의 여지가 충분히 존재하며, 각 문제에 따른 특화된 알고리즘의 적용으로 이를 개선할 수 있습니다만, 그렇다고 해도 아주 오랜시간에 걸쳐 반복작업이 이루어져야 그에 따른 최적값을 기대해 볼 수 있다는 것은 부정할 수 없는 사실입니다.
2. 진화 연산에 적용된 병렬처리기법
2.1 다수의 CPU 사용
초창기 유전프로그래밍(이하 GP)의 창시자라고 언급되는 John. R. Koza 의 경우에는 천 대의 컴퓨터를 하나의 클러스터로 활용해 GP를 수행하였으며, 이를 통해 과거에 발표되었던 특허들을 그대로 GP의 결과물로서 만들어내는 결과를 보여주었습니다.[1] (첫 페이지의 팔짱을 끼고 있는 그의 모습 뒤로 펼쳐진 것들이 수많은 컴퓨터의 클러스터입니다.)
그러나 일반적인 연구자들이 이러한 리소스를 활용할만한 능력을 갖추기는 어려웠기 때문에 사실상 대규모 클러스터링을 활용한 연구는 Koza 의 이후로 거의 나타나지 않고 있었습니다. 소수의 연구자들에 의해 소규모의 분산 처리 시스템[2]이나 여러 개의 CPU 를 사용한 연구[3]는 이루어지고 있었습니다. ([3] 논문은 가상의 병렬 처리 머신을 통해 데이터를 주고받는 것에 대한 논문입니다만, 저 논문의 결과물로서 lil-gp 의 병렬화된 형태를 언급하는 데 이것은 다중의 CPU 를 사용하는 병렬 처리 기법이 사용되어 있습니다.)
2.2 GPU
시간이 흐른 뒤, nVidia 에서 GPU 가 나오게 되었습니다. 이것은 벡터 연산에 특화되어 있고, CPU 에 비해 압도적인 처리성능을 보여주기에 수 많은 알고리즘이 이를 해당 알고리즘에 적용시키기 시작하였습니다. 물론 진화연산에서도 절대 예외일 수는 없었습니다.
대표적인 논문으로 몇가지를 언급하자면, 우선은 진화 연산을 타겟으로 삼은 것은 아니지만, GPGPU(General-Purpose computation on Graphics Processing Units) 의 개념을 활용해 알고리즘에 적용하는 것이 좋겠다고 제안한 논문이 있습니다. [4] 그리고 실제 GPU 를 사용해서 GP를 수행하고, 이에대한 성능 비교를 수행한 논문이 발표되게 되었습니다. [5,6,7]
일반적으로 생각하기에 GPU 를 통해 병렬적으로 개체의 해석을 수행하게 되면 CPU 만을 사용하는 현 GP 에 비해서 엄청난 속도 향상을 기대 하지만, 실제로는 모든 문제에 대해서 그렇지는 않았다는 내용이 [6] 논문에서 나타나고 있습니다. 그러나 위의 논문에서 사용된 컴퓨터의 사양은 T2400 (1.83 Ghz), 1.5GB ram, GeForce 7300 GO with 512 RAM 으로서, 노트북 컴퓨터라고 보시면 됩니다. 즉, 일반적으로 사용하는 GPU 에 비해서는 그다지 좋은 성능을 보여주는 것은 아니었던 것입니다.
그리고 [7] 논문에서는 GPU 에 최적화된 GP 연산 기법을 소개하고, SIMD 처리 형태에 알맞은 데이터 처리 방식을 사용하여 더 좋은 효율을 보여준다는 것을 나타내고 있습니다. 또한, 이 논문에서 더 주목해 볼 수 있는 것은 Geforce 8800 GTX 라는 고사양의 GPU를 사용했다는 것과 이를 통해 CPU 의 오버헤드가 0.1%에 근접한다는 내용, 그리고 기존에 해결하는데 매우 오랜 시간이 걸렸던 거대한 형태의 Regression 문제를 해결했다는 것에 있습니다. 1024 x 1024 x 1000 의 크기의 문제를 200번 수행하는데 6시간 46분 17초가 걸렸다는 건, 기존에 우리가 처리할 엄두도 못 내던 거대한 크기의 문제들을 GPU 를 사용하여 처리한다면 더 큰 효율과 빠른 결과를 얻을 수 있다는 것을 의미합니다.
[8] 논문에 이르러서는 Xbox360 이라는 이 종의 하드웨어를 통해 GP를 수행하게 됩니다. 컴퓨터의 GPU 를 통한 결과와 Xbox 360 의 GPU 를 통한 결과를 서로 비교하는 내용이 있는데, 특이할 만한 점은 C# 과 XNA Framework 를 통해 구현된 동일한 프로그램(GP)을 Xbox360 과 PC 에서 변환 없이 수행할 수 있었다는 것, 그리고 결국 성능은 PC 가 더 좋았다는 것이 되겠습니다.
2.3 기타 웹이나 네트워크 기반의 진화연산 기법
이렇듯 GPU 의 등장과 함께 진화 알고리즘은 매우 빠른 병렬처리 알고리즘을 통한 복잡한 문제의 해결, 그리고 GPU 에 걸맞는 형태의 알고리즘의 변화 등이 이루어져 왔습니다. 그러나 사실 GPU 를 통한 GP 의 발전은 아직은 한계가 있습니다. 가장 큰 한계점이라면 단순 Regression 문제나 디지털 논리회로를 벗어나는 문제에 대해서는 아직 그 위에서 해석할 방법이 없다는 것 입니다. 즉, 단순한 문제지만 거대한 데이터 셋을 갖는 문제에 대해서는 그 효율을 극대화 하여 이용할 수 있지만, 복잡한 시뮬레이션의 경우에는 아직 GPU 에서 그것을 수행하기에는 많은 무리가 따르게 됩니다.
GPU 의 진화 연산보다는 살짝 앞선 시기에 웹을 통한 진화 연산의 수행기법들에 대한 연구가 이루어 졌습니다. [9] 논문의 경우에는 웹을 통해 사람이 어떠한 평가를 내리고, 이를 서버에서 모아서 진화연산을 수행하는 형태에 대한 연구기법에 대해 논하고 있습니다. 이는 기계로 평가를 내리기 어려운 적합도 함수, 즉 좋은 음악이나 색의 조합 등 인간의 주관이 개입되어야 하는 문제에 대해서도 진화연산의 수행이 가능하다는 것을 보여준 사례가 되겠습니다.
2007년에 발표된 [10] 논문의 경우에는 XML 과 Ajax 를 통해 웹브라우저로 데이터를 서로 주고받고, 적합도 함수를 평가하며 해결하는 시스템을 구축하였습니다. 이 논문에서 아쉬운 점은 비교할만한 대상이 없었기 때문에, 해당 기법이 기존의 기법에 비해 어느 정도 효율성을 갖는지가 나타나지 않았고, 매우 빠른 연산을 보여주었다는 시간만을 언급하고 있다는 것이었습니다.
그리고 ECJ Framework[11] 에서는 TCP/IP 상의 Asynchronous Island Model 을 지원함에 따라 기존의 진화 연산 문제를 대규모 네트워크를 통한 처리 형태를 쉽게 사용해 볼 수 있습니다. 이미 모든 구현이 이루어져 있기 때문에 약간의 파라미터 수정만 거치면 바로 네트워크를 통한 진화연산 기법의 연구가 가능하다는 장점이 있습니다. 관심 있으신 분은 한번쯤 해보시면 좋을 것 같습니다.
3. 정리
이보다도 이른 시기에 네트워크를 통한 데이터 교환을 통해 진화 연산의 병렬화의 효율에 대해 논하는 것들이 많이 있었지만, 사실상 GPU 와 같이 핵심 테마로서 자리를 잡을 만큼의 파급력을 갖출 수 없었습니다. 이는 어쩌면 진화 연산 자체를 병렬처리로 수행한다는 것은 하나의 연구테마로 갖추기가 어려운 것이었을 수도 있고, 기존의 방법들에 비해 획기적인 성능을 보여주는 사례가 없었기 때문일 수도 있습니다. 혹은 고도의 시뮬레이터를 통한 시뮬레이션을 필요로 하는 그런 문제가 정의되지 않았기 때문일 수도 있습니다.
진화연산에서는 알고리즘 자체가 적은 수행 횟수를 통해 더 개선된 성능을 보여주는 것은 여전히 중요한 테마입니다. 단위 시간에 대해 더 효율적인 공간의 탐색을 할 수 있다면, 성능 개선을 위한 가장 훌륭한 접근이 될 수 있겠습니다. 거기에 같은 단위 시간에 대해 두 배 아니 열 배 이상의 수행이 가능하다면 더 좋은 성능을 보여주기 위한 가장 좋은 해결책이 아닐까 생각이 듭니다. 물론 이렇게 말하게 되면, 병렬처리 자체는 기존의 알고리즘의 개선을 위한 접근 방법들에 비해서는 중요도가 떨어져 보이는 것이 사실입니다. 그러나 이전에는 접근해 볼 수 없었던 100만개~1억개 이상의 개체의 진화나 이로 인해 나타나는 현상들은 기존의 알고리즘으로 접근하는 방식들과는 다를 것이라 생각되기 때문에, 진화 연산 자체의 병렬처리 시스템은 기존의 방식들과는 별도로 매우 중요한 테마가 되지 않을까 생각합니다.
4. 참고문헌
[1] John. R. Koza – http://www.genetic-programming.com/johnkoza.html
[2] F. S. Chong and W. B. Langdon. Java based distributed genetic programming on the internet. In W. Banzhaf, et al., editors, Proceedings of the Genetic and Evolutionary Computation Conference, volume 2, page 1229, Orlando, Florida, USA, 13-17 July 1999. Morgan Kaufmann. ISBN 1-55860-611-4.
[3] F. Fernandez, J. M. Sanchez, M. Tomassini, and J. A. Gomez. A parallel genetic programming tool based on PVM. In J. Dongarra, et al., editors, Recent Advances in Parallel Virtual Machine and Message Passing Interface, Proceedings of the 6th European PVM/MPI Users' Group Meeting, volume 1697 of Lecture Notes in Computer Science, pages 241-248, Barcelona, Spain, September 1999. Springer-Verlag.
[4] J. D. Owens, D. Luebke, N. Govindaraju, M. Harris, J. Kruger, A. E. Lefohn, and T. J. Purcell. A survey of general-purpose computation on graphics hardware. Computer Graphics Forum, 26(1):80-113, March 2007.
[5] D. M. Chitty. A data parallel approach to genetic programming using programmable graphics hardware. In D. Thierens, et al., editors, GECCO '07: Proceedings of the 9th annual conference on Genetic and evolutionary computation, volume 2, pages 1566-1573, London, 7-11 July 2007. ACM Press.
[6] S. Harding and W. Banzhaf. Fast genetic programming on GPUs. In M. Ebner, et al., editors, Proceedings of the 10th European Conference on Genetic Programming, volume 4445 of Lecture Notes in Computer Science, pages 90-101, Valencia, Spain, 11 - 13 April 2007. Springer.
[7] W. B. Langdon and W. Banzhaf. A SIMD interpreter for genetic programming on GPU graphics cards. In EuroGP, LNCS, Naples, 26-28 March 2008. Springer.
[8] G. Wilson, W. Banzhaf, Linear Genetic Programming GPGPU on Microsoft’s Xbox 360, in Proceedings of 2008 IEEE World Congress on Computational Intelligence, Hong Kong, 2008.
[9] W. B. Langdon. Pfeiffer - A distributed open-ended evolutionary system. In B. Edmonds, et al., editors, AISB'05: Proceedings of the Joint Symposium on Socially Inspired Computing (METAS 2005), pages 7-13, University of Hertfordshire, Hatfield, UK, 12-15 April 2005a.
[10] J. Klein and L. Spector. Unwitting distributed genetic programming via asynchronous javascript and XML. In D. Thierens, et al., editors, GECCO '07: Proceedings of the 9th annual conference on Genetic and evolutionary computation, volume 2, pages 1628-1635, London, 7-11 July 2007.
[11] ECJ - http://cs.gmu.edu/~eclab/projects/ecj/