Home

저궤도 위성 네트워크에서의 라우팅 문제는 여러 위성으로 이루어진 네트워크에서 각 위성이 데이터를 전송하는 경로를 결정하는 일련의 문제를 일컫는다. 이를 수학적으로는 마르코프 결정 과정(Markov decision process)으로 표현할 수 있는데, 그중에서도 그리드 마르코프 결정 과정(Grid MDP, Grid-Markov Decision Process)을 사용할 수 있다.

그리드 마르코프 결정 과정은 “First-order Markov Assumption”이라는 가정에 기반하여, 시간 t에서의 상태는 이전 시간인 t-1의 상태에만 영향을 받는다고 가정한다.

Grid MDP에서는 상태(State), 행동(Action), 보상(Reward), 상태 전이 확률(State transition probability)을 사용하여 문제를 모델링한다. 상태는 각 위성의 위치와 해당 위성에 저장된 패킷의 데이터를 나타내며, 행동은 위성이 데이터를 전송하는 방향을 의미한다. 보상은 특정 방향으로 데이터를 전송했을 때 얻는 점수를 나타내며, 상태 전이 확률은 패킷 전송에 따른 위치 변화를 표현한다.

Grid MDP는 일반적인 MDP에 비해 상태 공간이 Grid 형태로 구성되어 있어서 상태 전이와 보상에 대한 계산이 비교적 간단하다. 본 논문에서는 이러한 Grid MDP 환경에서 동작 가능한 심층 강화학습 기반 라우팅 알고리즘을 사용한다.

강화학습 알고리즘을 사용하여 Grid MDP에 적용시키면 전체 상태에 대해 정의하지 않아도 된다. 기존의 Grid를 이용한 MDP의 경우는 미리 상태, 행동, 보상, 상태 전이 확률을 전부 모델링 해 두어야만 원활하게 적용이 가능하지만 강화학습을 사용하여 진행하게 되면 사전에 모델링을 하지 않고도 직접 계산하여 결과를 도출해낼 수 있다. 대신, 상태와 보상에 대한 정보를 학습을 통해 실시간으로 수집하며, 이를 기반으로 강화학습 알고리즘이 최적의 라우팅 경로를 결정하는 데에 도움을 준다. 초반에는 학습 데이터가 존재하지 않기 때문에 낮은 적중률 및 성적을 보이지만 학습을 거듭할수록 점차 최적의 성적을 거두게 된다. 정리하자면, MDP를 사용하게 되면 학습 프로세스에서 가치 반복이나 정책 반복과 같은 다이나믹 프로그래밍 알고리즘을 사용하게 되어 최적 가치 함수 또는 정책을 찾게 되고, 강화학습을 사용하게 되면 상태 관찰 및 보상을 통해 에이전트가 직접 경험을 쌓아 이를 토대로 가치 함수나 정책을 학습하게 된다.

따라서 강화학습 알고리즘을 사용하게 되면, 기존의 방식에 비해 학습이라는 시간이 추가되게 되지만, 전체 상태에 대해 미리 정의하는 모델링 과정이 생략되게 된다. 추가로 MDP를 활용하는 방법의 경우 확실한 정책을 찾을 수 있는 반면 강화학습을 이용한 방법은 학습 결과가 불안정해질 수 있지만 본 논문에서 제시하는 동적 상황에서의 위성 라우팅 알고리즘에 적용하기에는 적합하다고 판단했다.

Dueling DQN은 기존 DQN 알고리즘의 구조적인 부분을 개선하여 성능을 향상시킨 모델이다. DQN(Deep Q-Network)는 Q-Learning의 딥러닝 기반 확장으로, 강화학습 문제를 해결하기 위한 신경망 구조이다. 기존 DQN은 상태를 입력받아 Q함수를 출력하는 구조를 가지고 있다[15]. Dueling DQN의 주요한 특징으로 가치 함수(Value function)와 행동 가치 함수(Advantage function)를 명시적으로 분리하여 대상을 추정하는데 사용한다[16]. 이를 통해, 신경망은 상태 가치와 행동에 따른 가치의 차이를 추정할 수 있으며, 이로 인해 기존 DQN보다 더 큰 환경 내에서 학습 성능을 높일 수 있다. Dueling DQN의 구조는 기존 DQN과 동일한 입력부를 사용하나 출력부에 Value와 Advantage를 고려한 별도의 계층을 추가하는 것이 특징이다. 이렇게 구성된 Dueling DQN은 상태 가치와 행동 가치를 분리하고 하나의 종합된 Q-value로 합쳐 계산한다.

동적 저궤도 위성 네트워크와 이종 프로세서 환경에서 Dueling DQN 기반 라우팅 알고리즘을 사용할 때 연산 복잡성 문제를 반드시 고려해야 한다. Dueling DQN은 신경망에 의한 복잡한 연산 과정을 포함하므로, 신경망의 크기, 깊이를 적절히 조절해 연산량을 줄이는 방안을 반드시 고려하여야 한다.

온보드 강화학습 기반 라우팅이 동적 저궤도 위성 네트워크에서 효과적인 솔루션을 제공할 수 있지만, 여전히 몇 가지 문제점이 존재한다. 그 중 핵심 문제는 강화학습의 수행 시간 때문에 발생하는 실시간성 문제이다.

강화학습 알고리즘은 주기적으로 업데이트되는 위성 네트워크의 동적 상황에 대응하여 라우팅 결정을 내리는 데 사용되며, 이 과정에서 다양한 요인들을 고려해야 한다. 이러한 요인들에는 대역폭, 지연 시간, 오류율, 위성의 이동 궤도 등이 포함된다. 이러한 변수들 변화에 신속하게 대응하면서 최적의 라우팅 솔루션을 제공하는 것이 온보드 강화학습 기반 라우팅의 목표이다.

그러나 강화학습 기반 라우팅 알고리즘의 훈련 및 추론 과정에서 소비되는 시간이 많을수록 실시간성이 저하되며, 동적 저궤도 위성 네트워크의 변경 요인들에 빠르게 대응하는 데 어려움이 발생한다. 이로 인해 강화학습 기반 라우팅 알고리즘이 최적의 솔루션을 찾지 못하거나 지연이 발생하게 된다. 이러한 실시간성 문제를 해결하기 위해 본 논문에서는 이종 프로세서 기반 추론 병렬화 기술을 제안한다. Dueling DQN 알고리즘을 사용한 온보드 강화학습 기반 라우팅에서 PL에서 연산을 병렬화하여 추론 과정을 가속화하는 방식을 사용하게 된다. 이를 통해 강화학습의 수행 시간을 줄이고, 실시간성 문제를 해결할 수 있을 것으로 생각된다.

본 논문의 후속 챕터에서는 이종 프로세서 기반 추론 병렬화 기술의 세부 사항과 구현, 그리고 성능 향상에 대해 더 깊게 다루게 된다. 그 결과, 본 논문의 제안 방법을 도입함으로써 동적 저궤도 위성 네트워크에서의 온보드 강화학습 기반 라우팅의 실시간성과 성능 개선을 기대할 수 있다.

본 논문에서는 다음과 같은 순서로 이종 프로세서 기반 추론 병렬화를 진행한다. 우선 PS에서 그리드 환경 생성 및 5가지 행동에 대해 정의하고, reward를 설정한다. 행동은 현재 에이전트의 위치에서 상, 하, 좌, 우, 정지로 총 5가지 행동에 대해 정의한다[17]. Reward는 5가지 행동에 관계 없이 매 time step마다 1점을 감점하며, 도착지에 도착하였을 경우 1점을 상점으로 부여하고 과정이 종료된다. 만약 에이전트가 이동 중 장애물(위성 링크 단절)에 부딪힐 경우 다음 time step에는 동작을 하지 못한다. 즉, 장애물에 부딪히는 경우는 2 time step을 소모하기 때문에 총 –2점 감점이라고 생각할 수 있다.

이렇게 PS에서 환경 생성 및 행동과 보상에 대해 설정하고 나면 Dueling DQN 파트로 넘어온다. 본 논문에서 제시하는 Dueling DQN은 우선 main layer를 통해 2D convolution과 ReLU 과정을 총 4번 진행한다. 이 과정을 PL로 데이터를 보내서 연산한다. 전체 프로세스에서 convolution 연산을 담당하는 부분이 가장 크기가 크고 시간이 오래 걸리기 때문에 해당 부분을 PL에서 연산하여 병렬화를 진행한다. PL에서 convolution 및 ReLU 과정을 거치고 나면 다시 PS로 데이터를 보내 advantage layer와 value layer에서 linear 연산을 수행한다. 이렇게 도출된 연산 값 중 최고치에 해당하는 행동을 판단한 뒤, 그 행동을 수행하고 수행 후의 위치와 보상 값을 계산한다. 이렇게 나온 위치와 보상 값을 다시 현재 state로 넘겨 위의 과정을 반복하며 최적의 라우팅 경로를 찾아낸다. 그림 1은 이종 프로세서 기반 추론 병렬화 과정을 도식화한 것이다.

Fig. 1. 
Heterogeneous processor-based inference parallelization process schematic

본 논문에서는 온보드 강화학습 기반 라우팅을 위하여 Dueling DQN 코드를 Jupyter 환경에서 학습시키고, 가중치 파일을 Pynq 보드로 전송하여 추론 과정을 진행한다. 이를 위해 이종 프로세서 기반 추론 병렬화 기술을 제안한다. 추론 코드 추출 과정은 다음과 같이 진행된다.

먼저, Dueling DQN에 사용된 신경망 구조를 확인한다. 이를 통해 각 계층별로 가중치와 계수를 별도의 파일 형태로 저장하며, 이를 .pt 파일 형식으로 변환한다. 저장된 .pt 파일을 Pynq 보드로 업로드하여 추론 과정 시작에 앞서 필요한 정보를 불러오도록 한다.

또한, 추론 과정은 병렬화하여 처리되도록 한다. 이를 통해 Pynq 보드의 이종 프로세서를 활용하여 병렬 연산이 가능한 구조로 코드를 수정한다. 이를 통해 효율적인 병렬 처리가 가능하도록 설계한다.

Convolution 연산을 담당할 코드는 HLS tool에서 직접 설계한다. 기본적으로 본 논문에서 제시하는 방법은 4번의 convolution과 ReLU 과정을 포함하기 때문에 HLS에서 이를 코드로 작성하여 IP화한다. 그 후 IP를 가지고 block design하여 bitstream, blockdesign, hardware hondoff 파일을 추출한 뒤 Pynq에 업로드한다.

이렇게 가중치 파일과 block design을 통해 추출한 파일이 업로드가 완료되면 Pynq를 LAN port를 통해 접속한다. Jupyter 환경을 사용하였으며 .ipynb 파일을 생성한 뒤 라이브러리와 함수를 호출한다. 그 후 기존의 Dueling DQN의 추론 코드에서 main layer 부분을 PL로 병렬화하는 코드를 통해 진행한다.

Pynq는 python을 사용하여 프로그래밍, 하드웨어 가속, 주변 장치 제어 등을 할 수 있도록 도구와 라이브러리를 제공한다. 그 중 Overlay 라이브러리는 이러한 임베디드 시스템에서 FPGA를 프로그래밍하고 제어하기 위한 도구이다[18].

오버레이 기반 HW/SW 동시 설계란, 하드웨어와 소프트웨어를 효과적으로 연계하여 동시에 설계하고 구현하는 개발 방식을 말한다. 오버레이는 FPGA 하드웨어의 복잡한 기능들을 소프트웨어 측면에서 추상화된 인터페이스로 제공함으로써, 개발자가 하드웨어와 소프트웨어 간의 상호 작용을 쉽게 관리할 수 있게 돕는다.

Overlay를 사용하면 기존의 python 코드가 수정되었을 때, 코드 전체를 수정하는 것이 아닌 HLS 코드만 재작성하여 사용할 수 있다는 장점이 존재한다. 본 논문에서 제시하는 방법은 PS에서 연산하는 부분과 PL에서 연산하는 부분이 명확하게 구분되어 나누어져 있는데[19], 만약 PS에서 동작하는 코드가 수정되었으면 그 부분만 수정하면 되고 PL에서 동작하는 코드가 수정되었으면 그 부분의 block design만 새롭게 하면 된다는 장점이 있다. 이를 통해 사용자는 복잡한 하드웨어 디자인 과정과 세부 사항을 크게 나누어 집중할 필요 없이 전체 시스템 개발에 초점을 맞출 수 있다. 또한 여러 프로젝트에서 중복된 코드나 모듈을 공유하여 시간을 절약할 수 있으며, 기존의 Overlay에 새로운 하드웨어 기능을 추가하여 확장할 수도 있다.

DMA(Direct Memory Access) 블록 기반 데이터 처리는 프로세서의 개입 없이 메모리와 주변장치 간의 데이터 전송을 효율적으로 처리하는 기술이다. 이 방식으로 데이터 처리를 실행하면, 프로세서의 부담을 줄이고 시스템의 전체적인 성능을 향상시킬 수 있다[20].

일반적인 데이터 처리는 중앙 처리 장치를 통해 메모리와 주변장치 간의 데이터 이동이 발생한다. 이와 달리 DMA 블록 기반 데이터 처리는 특별한 하드웨어 컨트롤러인 DMA 컨트롤러가 직접 메모리에서 데이터를 읽고 주변 기기로 전송하거나, 주변 장치로부터 데이터를 읽고 메모리로 쓰는 작업을 처리한다[21].

DMA 블록 기반 데이터 처리를 하면 독립적인 DMA 컨트롤러가 데이터 전송을 수행하기 때문에 전체 시스템의 성능이 향상될 수 있다. 또한 프로세서와 DMA 컨트롤러가 독립적으로 작동하므로 시스템의 병렬 처리 능력이 증가해 더 많은 작업을 동시에 처리할 수 있다.

그림 2는 본 논문에서 제시하는 방법에 따라 설계한 block design이다. 좌상단의 위치한 block은 DMA block이다. DMA는 PS-PL은 대용량 전송을 위해 선택한 매개체로 stream 방식으로 데이터를 송수신하며 data와 last로 나뉜다. data는 전송할 float형 데이터고 last는 마지막을 나타내는 불리안형 변수이다. 우리는 총 9개의 DMA를 사용하고, 그 중 8개는 데이터 읽기 전용 DMA이고 1개는 입출력을 모두 담당한다. 9개의 데이터를 DMA를 통해 입력받는 방식인데, 이 때 현재 상태와 목적지, 장애물, 경계면 정보를 담은 입력 데이터 1개와 convolution 연산에 필요한 weight 값과 bias 값을 총 8개 입력으로 받는다. DMA를 통해 데이터를 입력받고 나면 PL에서 연산을 수행한 뒤 출력 데이터 하나를 DMA를 통해 다시 내보낸다. 그림 3은 DMA를 통해 PS와 PL간 데이터 흐름에 대해 도식화 한 그림이다. M은 Memory-Mapped to Stream을 뜻하며 Memory-Mapped된 데이터를 스트림 형태로 전송하는 기능을 하며, 읽기 채널에 해당한다. S는 Stream to Memory-Mapped을 뜻하며 스트림 형태의 데이터를 메모리 Memory-Mapped 된 형태로 전송하는 기능을 가르킨다. 이는 쓰기 채널에 해당된다[22].

Fig. 2. 
Block design presented in this paper

Fig. 3. 
Schematic DMA dataflow

우리가 제시하는 Dueling DQN에서, 연산에 상당한 시간을 소모하는 부분은 바로 convolution 함수다. Convolution은 수 많은 입력 데이터와 weight, bias를 입력 받아서 연산을 진행한다. 특히 convolution 구조 자체가 6중 반복문으로 되어있기 때문에 PL에서 병렬화 연산을 할 때 굉장한 부담을 준다. 따라서 본 논문에서 는 입력 채널과 출력 채널을 각각 배수로 고정하고 해당 loop에 대해 loop unrolling 기법을 사용한다.

Loop unrolling은 컴퓨터 프로그래밍에서 성능 최적화를 위해 사용되는 기술 중 하나다. 해당 기술은 반복문 내의 연산을 반복 실행 횟수를 줄이고, 대신 각 반복에서 수행하는 연산을 늘려서 전체 실행 시간을 단축시키는 것을 목표로 한다[23]. Loop unrolling을 수행하는 과정에서는, loop의 몸체가 더 많은 연산을 수행하도록 코드가 수정된다[24]. 이렇게 하면 loop를 돌면서 발생하는 overhead가 줄어들 되, 실행 시간이 단축되므로 전체 성능이 향상된다. 또한 loop unrolling 기법을 사용할 경우 pipelining이나 vectorization과 같은 고급 병렬 처리 기술을 효과적으로 사용할 수 있다.

그림 4는 해당 논문에서 사용한 기법을 도식화한 예시이다. 기존의 convolution 함수에 있는 변수들의 종속성을 배열을 통해 제거하여 loop unrolling을 진행한 뒤, pipelining을 적용하여 기존보다 높은 성능을 낼 수 있다. 본 논문에서 사용하는 Dueling DQN의 경우 현재 위치, 목표 위치, 장애물, 경계면의 총 4개의 채널은 입력으로 받는다. Convolution 과정을 진행할 때 입력 채널과 출력 채널만큼 반복문을 거치기 때문에 입력 채널과 출력 채널을 4의 배수, 8의 배수로 고정하여 loop unrolling이 용이한 상태로 바꾼다.

Fig. 4. 
Schematic illustration of loop unrolling technique used in this paper

이렇게 unrolling 된 코드를 가지고 pipelining을 하게 되면 기존보다 클럭 당 연산을 많이 수행할 수 있게 되어 최종적으로는 연산 수행 시간이 감소하게 된다.

해당 실험을 진행하기 위해 보드는 PYNQ-Z2(Python Productivity for Zynq) 버전을 사용하였다. 보드에 Jupyter notebook을 설치하여 환경을 구성하였으며 PYNQ OS 2.4 및 Pytorch 1.2.0a 버전을 사용하였다. 학습은 Anaconda 가상환경을 이용한 Jupyter notebook에서 진행하였다. 학습에 사용한 PC의 사양은 Intel core i7-10700 및 Nvidia Geforce RTX 3070이 탑제된 Desktop을 사용하였다.

학습과 추론에 사용한 모델은 총 15x15의 grid 맵으로 총 4개의 채널로 구성된다. 각각의 채널은 에이전트의 위치, 목표 위치, 장애물, 경계면을 뜻하며 에이전트의 위치 및 목표 위치는 전체 15x15 맵 기준으로 구성했으며 장애물 및 경계면의 경우 현재 에이전트의 위치를 기준으로 학습하였다. 학습 횟수는 총 100회 반복하였으며 한 번의 학습 당 최대 step 수는 300, batch size는 1024로 설정하였다.

Convolution 과정의 경우 커널 사이즈를 6x6, 4x4, 3x3, 2x2로 설정하였으며 최종적으로 나오는 출력의 경우 15*15*4의 데이터를 입력으로 넣어 4*4*32의 데이터가 나온다. Loop unrolling을 사용하기 위해 입력 채널 및 출력 채널은 각각 4와 8의 배수로 고정하여 진행하였다.