라즈베리 파이 피코에서 최단 경로 알고리즘 실행하기

1. 라즈베리 파이 피코 (Raspberry Pi Pico)

Buy a Raspberry Pi Pico – Raspberry Pi

 라즈베리 파이 피코는 라즈베리 파이 재단에서 출시한 마이크로 컨트롤러 보드이다. 기존 라즈베리 파이 4B와 같은 제품은 리눅스를 설치하고 그 위에 Docker나 OpenMediaVault 등을 실행할 수 있었다. 마인크래프트 서버를 구동하여 친구들과 같이 사용하기도 했고, mariaDB와 nginx를 설치해 웹 사이트를 올릴 수도 있었다. 

 

 하지만 라즈베리 파이 피코는 그런 종류의 컴퓨터가 아니다. 구체적인 사양을 보면 알겠지만 133MHz 듀얼코어의 낮은 CPU 성능, 264KB 뿐인 RAM, 2MB의 프로그램 저장공간을 보면 이 제품의 목적이 분명히 보인다. 피코는 마이크로 컨트롤러로서 냉장고, 세탁기, 공기청정기와 같은 가전제품부터 도어락, 게임기 컨트롤러, TV 리모컨과 같이 저전력 환경에서 정확히 필요한 만큼의 성능을 제공하기 위한 컴퓨터이다. 쉽게 말하면 아두이노와 비슷한 역할을 할 수 있다고 보면 된다. 

 

 

2. 프로젝트 개요

 21년 여름에 SPA_compare라는 이름의 프로젝트를 진행한 적이 있다. 미로를 생성하고 여러 알고리즘으로 미로의 최단 경로를 탐색하는데 걸리는 시간을 비교해보았다. 이에 대한 자세한 내용은 이전 글에서 볼 수 있다. 이번에는 라즈베리 파이 피코에서 이 프로젝트가 작동하도록 만들어 보았다. 

 

 라즈베리 파이 피코에서 동작하는 프로그램을 만들려면 일반적인 컴퓨터와는 다르게 프로그래밍 해야한다. 라즈베리 파이 재단은 더 쉬운 피코 프로그래밍을 위해 MicroPython을 지원하지만, C/C++ 코드보다 어느 정도 성능 차이가 벌어진다고 알려져 있다(참고). 따라서 C++를 사용해 코드를 작성했다. 

 

 기본 코드 베이스는 이전 프로젝트에서 가져왔으며, 여러 최적화 과정을 통해 피코에서도 원활히 작동하는 프로그램을 만들 수 있었다. 

 

 

3. 초기 상태

 이전 프로젝트 코드를 거의 그대로 사용한다면 미로의 크기를 20x20에서 더 키울 수가 없었다. 이는 객체를 필요 이상으로 만들거나, 편의를 위해 간단한 계산으로 대체될 수 있는 데이터들을 더 저장했기 때문이었다. 

 

 

4. 최적화

 리소스가 충분한 일반적인 컴퓨터에서 몇 천개의 포인터나 몇 개의 최단 경로 탐색 알고리즘 구현체 객체 정도는 큰 문제가 되지 않는다. 심지어 메모리 누수가 있더라도 어느 정도 루프 동안은 정상적으로 작동할 수도 있다. 조금 무겁더라도 남들이 미리 만들어 놓은 라이브러리를 가져다 쓰는 것도 좋은 방법이다. 개발 시간이 더 중요한 요소이기 때문이다. 함수 호출 오버헤드가 있더라도 함수를 작게 쪼개는 것이 유지 보수와 가독성에 더 유리하다. 메모리를 더 쓰더라도 객체 지향을 충실히 따르는 것이 안전하다. 

 

 하지만 라즈베리 파이 피코에 이 프로그램을 구동하기 위해서는 편의와 유지보수를 때문에 구축한 이런 요소들을 최대한 가볍게 줄여야 했다. 간단한 산술 연산이나 한두 번의 조건문으로 데이터에 접근할 수 있다면 굳이 같은 데이터를 접근성 때문에 또 저장할 필요가 없다. 가능한 값의 최대 값을 고려해 자료형을 더 작게 변경하는 것도 효과가 있었다. 객체 지향보다는 최적화에 더 노력을 기울였다. 

 

 다음은 사용한 최적화 방법들이다. 

• 미로 가로, 세로의 최대 값은 이전 프로젝트에서도 200을 넘지 않았다. 따라서 unsigned char를 좌표의 자료형으로 사용해 공간을 절약했다. 
• 가중치 또한 그 최대 값이 어느 정도 고정되어 있다. 따라서 short를 자료형으로 사용했다. 
• 각 칸이 갖고 있는 인접한 칸을 가리키던 포인터 배열을 삭제했다. 이는 가벼운 조건문을 사용한 함수 호출로 대신할 수 있다. 
• 난수를 생성하거나 두 위치의 맨하탄 거리를 계산하는 함수와 같이 굉장히 자주 호출되는 함수를 매크로로 바꾸었다. 
• vector, set과 같이 자주 사용하는 STL 컨테이너를 사용하지 않고 직접 배열을 동적 할당하고 해제하였다. 

 이 외에도 우선순위 큐를 직접 구현하고, 버킷 큐의 배열 할당을 유연하게 바꿈으로써 시간복잡도 또는 공간복잡도의 이득을 볼 수 있었다. 처음에는 20x20 크기의 미로만 겨우 생성할 수 있던 것에 비해 최적화 이후에는 39배 이상 증가한 125x125 크기의 미로를 생성, 저장할 수 있었다. 또한 다익스트라 알고리즘이나 A* 알고리즘을 더욱 개선시켜 수행 시간을 단축시킬 수 있었다. 

125x125 크기의 미로를 생성하고 최단 거리 탐색 알고리즘을 반복 실행하는 모습

 

5. 결론

 비록 짧은 프로젝트였지만 임베디드 시스템 환경을 체험해볼 수 있었다. 학교에서 말로만 듣던 '리소스가 극히 부족한 상황'을 직접 체험해보고 그 안에서 최대한 많은 일을 하도록 프로그램을 최적화 시키는 일을 해보았다. 이 과정에서, 엄청나게 많은 데이터를 처리하는 상황이 아니라면 일반적인 컴퓨터에서는 쉽게 느끼지 못했던 시간복잡도와 공간복잡도의 중요성을 다시 깨닫게 되었다. 알고리즘과 자료구조 과목에서 배웠던 것들을 최적화 과정에서 의도를 가지고 사용해볼 수 있었다. 

 

 또한 Java 프로젝트를 할 때 Javadoc을 사용해봤듯이, 이번 C++ 프로젝트를 하면서 Doxygen으로 코드 내용을 문서화하는 법을 배우게 되었다. 코드를 재사용하는데 문서가 얼마나 중요한지 라이브러리들을 사용하며 배웠듯이, 나도 내 코드를 더 쉽고 효율적인 방법으로 문서화하는 방법을 알게되었다. 

 

참고

SPA_pico Github Repository 

SPA_compare Github Repository