Extension of ACETONE C code generator for multi-core architectures

이 논문은 안전-중요 시스템에 머신러닝을 안전하게 임베딩하는 C 코드 생성기 ACETONE 을 단일 코어에서 멀티코어 아키텍처를 지원하는 병렬 코드 생성으로 확장하기 위한 프로세서 할당 문제 정의 및 관련 기술 검토를 소개합니다.

핵심

이 논문은 **"안전이 최우선인 항공기 시스템에 인공지능 (AI) 을 더 빠르고 안전하게 심는 방법"**에 대한 이야기입니다.

기존의 기술로는 AI(딥러닝) 를 항공기에 탑재할 때, 계산이 너무 느리거나 예측 불가능해서 위험할 수 있었습니다. 이 연구팀은 이를 해결하기 위해 **'ACETONE'**이라는 도구를 업그레이드했습니다. 마치 단일 주방에서 요리를 하던 것을, 여러 명의 요리사가 협력하는 대형 주방으로 바꾸는 과정과 비슷합니다.

이 내용을 일상적인 비유로 쉽게 설명해 드리겠습니다.

---

1. 문제 상황: "혼자서 모든 일을 하느라 지친 주방장"

기존의 항공기 컴퓨터는 **단일 코어 (Single Core)**였습니다. 이는 마치 혼자서 모든 요리를 하는 주방장과 같습니다.

• 문제: AI(딥러닝) 는 요리 레시피가 매우 복잡하고 단계가 많습니다. 혼자서 모든 재료를 다듬고, 볶고, 끓이다 보면 시간이 너무 오래 걸립니다.
• 위험: 항공기는 정해진 시간 안에 결정을 내려야 합니다 (예: 착륙 경로 계산). 혼자서 하다가 시간이 부족하면 비행이 위험해질 수 있습니다.
• 현실: 항공기에는 전용 가속기 (GPU 등) 를 넣기 어렵고, 현재는 **여러 개의 CPU 코어 (여러 명의 요리사)**를 가진 컴퓨터를 쓰고 있습니다. 하지만 이 여러 요리사들이 어떻게 협력해야 할지, 누가 무엇을 언제 할지 정해주는 시스템이 없었습니다.

2. 해결책: "ACETONE 의 업그레이드 - 협력하는 주방"

연구팀은 ACETONE 이라는 도구를 업그레이드하여, 여러 코어 (요리사) 가 협력해서 일을 분담하게 만드는 방법을 개발했습니다.

A. 레시피를 '작업 지시표 (DAG)'로 바꾸기

복잡한 AI 모델은 하나의 거대한 레시피가 아니라, **작은 작업들이 연결된 지도 (DAG)**로 바꿉니다.

• 비유: "먼저 감자를 깎고 (A), 그다음 양파를 썰고 (B), A 와 B 가 다 끝나야 볶음밥을 볶을 수 있다 (C)"와 같은 선후 관계를 명확히 합니다.
• 목표: 이 지도를 보고, 누가 (어떤 코어가) 무엇을 할지, 그리고 누가 누구에게 재료를 넘겨줘야 할지 정합니다.

B. 최적의 일정을 짜는 '스마트 매니저'

여러 요리사에게 일을 분배하는 것은 매우 어렵습니다. (누가 먼저 시작해야 가장 빨리 끝날까? 재료를 넘겨줄 때 기다리는 시간은 어떻게 줄일까?)

• 연구팀은 **수학적인 알고리즘 (제약 프로그래밍)**과 **현명한 휴리스틱 (경험칙)**을 섞어서, 가장 효율적인 작업 순서를 찾아냅니다.
• 비유: 매니저가 "A 는 1 번 조에서 감자를 깎고, B 는 2 번 조에서 양파를 썰고, 둘 다 끝나면 3 번 조가 합쳐서 볶아라"라고 정해주는 것입니다.
• 중요한 점: 항공기처럼 안전이 중요한 곳에서는 "아마도 빠를 것 같다"가 아니라 **"최악의 경우에도 이 시간 안에 끝난다"**는 것을 수학적으로 증명해야 합니다. 이 연구는 그 시간을 정확히 계산할 수 있게 해줍니다.

C. 요리사들 사이의 '신호등 시스템' (동기화)

여러 코어가 메모리라는 공용 냉장고를 공유할 때, 서로 재료를 빼앗거나 혼란을 초래하지 않도록 해야 합니다.

• 비유: 1 번 요리사가 냉장고에 소스를 넣으면, 2 번 요리사는 "소스가 들어갔는지 확인"하고 가져가야 합니다.
• 연구팀은 **깃발 (Flag)**과 같은 신호 시스템을 만들어, "내가 다 썼으니 너가 가져가도 돼"라고 신호를 주고받게 했습니다. 이렇게 하면 데이터가 꼬이지 않고 안전하게 전달됩니다.

3. 결과: "조금 더 빨라진 비행기"

이 방법을 실제로 테스트해 본 결과:

• 속도 향상: 모든 작업을 한 코어가 할 때보다 약 8% 정도 빨라졌습니다. (전체 작업 중 일부는 46% 까지 빨라졌습니다.)
• 안전성: "최악의 경우에도 이 시간 안에 끝난다"는 것을 증명했기 때문에, 항공기 인증을 받을 수 있는 안전한 코드가 됩니다.
• 현실적인 제약: 아직은 모든 부분이 완벽하게 병렬화되지는 않았습니다. (예: 감자 깎는 작업은 혼자서만 해야 하므로, 그 부분은 병렬화의 혜택을 못 받습니다.) 하지만, 병렬화가 가능한 부분 (양파 썰기, 볶기 등) 에서는 큰 효과를 보았습니다.

4. 결론: "미래를 위한 첫걸음"

이 연구는 항공기라는 엄격한 환경에서도 AI 를 여러 코어에 나누어 빠르게, 그리고 안전하게 실행할 수 있는 첫 번째 청사진을 제시했습니다.

• 핵심 메시지: "혼자서 모든 일을 하느라 지친 항공기 컴퓨터에게, 여러 명의 요리사 (코어) 가 협력하는 시스템을 도입했습니다. 수학적으로 안전을 보장하면서, 더 복잡한 AI 기능도 탑재할 수 있게 되었습니다."

이 기술이 발전하면, 앞으로 항공기가 더 똑똑한 자율 비행이나 실시간 경로 최적화 같은 기능을 안전하게 수행할 수 있을 것입니다.

기술 요약

1. 문제 정의 (Problem Statement)

• 배경: 항공우주 분야에서는 내비게이션 보조, 활주로 감지, 궤적 최적화 등 새로운 기능을 위해 머신러닝 (DNN) 도입이 증가하고 있으나, 안전 임계 (safety-critical) 시스템에 통합하는 것은 까다로운 인증 표준과 높은 예측 가능성 (predictability) 요구사항으로 인해 큰 장벽입니다.
• 현재 한계: 기존 ACETONE 프레임워크는 오프라인 학습된 DNN 모델로부터 순차적인 (sequential) C 코드를 생성하여 단일 코어에서 실행합니다. 이는 인증은 가능하지만, 계산 시간이 길어 실시간 제약 조건을 위반할 수 있으며, 모델 크기가 커질수록 처리가 어렵습니다.
• 목표: 전용 가속기 (GPU 등) 가 없는 현재 항공우주 하드웨어 환경 (다중 코어 CPU) 에서 DNN 추론 시간을 단축하면서도, 최악의 실행 시간 (WCET) 을 예측 가능하게 유지하는 병렬 C 코드 생성 기술을 개발하는 것입니다.

2. 방법론 (Methodology)

이 연구는 크게 **오프라인 스케줄링 (Offline Scheduling)**과 코드 생성 및 동기화 (Code Generation & Synchronization) 두 단계로 나뉩니다.

2.1. DAG 스케줄링 문제 모델링

• DNN 을 **방향 비순환 그래프 (DAG)**로 모델링합니다. 각 노드는 DNN 의 레이어 (작업) 를, 간선은 데이터 의존성을 나타냅니다.
• 목표: $m$개의 동일한 코어에서 작업 할당, 작업 시작 시간 결정, 그리고 작업 중복 (Duplication) 여부를 정하여 전체 실행 시간 (Makespan) 을 최소화하는 최적의 스케줄을 찾는 것입니다.
• 제약 조건:
  • 비 선점형 (Non-preemptive) 작업.
  • 모든 선행 작업이 완료되고 데이터 통신이 끝난 후에만 작업 시작 가능.
  • 메모리 간섭 (Interference) 은 WCET 에 마진을 추가하여 고려.

2.2. 최적 스케줄 탐색 알고리즘

문제를 해결하기 위해 세 가지 접근 방식을 비교 및 제안했습니다.

1. 개선된 정수 선형 계획법 (Improved ILP Encoding):
   • 기존 Tang et al. 의 ILP 모델은 통신 변수 ($d_{ai,bj}$) 가 4 차 텐서 형태라 계산 비용이 매우 높았습니다.
   • 저자는 이 변수를 제거하고 상한선 (Upper Bound) 제약과 조건부 논리를 도입하여 변수 수를 줄이고 제약식을 단순화했습니다. 이를 통해 수백 개의 노드까지 해결 가능한 효율적인 모델을 제시했습니다.
2. 휴리스틱 알고리즘 (Heuristics):
   • ISH (Insertion Scheduling Heuristic): 작업의 시작 시간을 최소화하는 코어에 할당하고, 유휴 시간 (Idle time) 이 발생하면 대기 중인 작업을 삽입합니다. 계산 속도가 빠릅니다.
   • DSH (Duplication Scheduling Heuristic): 통신 지연으로 인한 유휴 시간을 줄이기 위해 부모 노드를 다른 코어에 **중복 (Duplication)**하여 실행합니다. ISH 보다 최적에 가까운 결과를 내지만 계산 시간이 더 걸립니다.
3. 해 공간 탐색: Chou and Chung 의 방법을 참조하여 지배 (Dominance) 및 동치 (Equivalence) 관계를 이용해 불필요한 분기를 제거하는 방식도 검토되었습니다.

2.3. ACETONE 프레임워크 확장 및 동기화 메커니즘

• 코드 생성: 스케줄러가 각 코어에 할당된 레이어 리스트를 생성하면, ACETONE 은 이를 기반으로 독립적인 병렬 C 함수를 생성합니다.
• 동기화 (Synchronization):
  • 공유 메모리 (UMA) 기반의 **플래그 (Flag) 와 배열 (Array)**을 사용하여 코어 간 통신을 관리합니다.
  • Writing Operator: 데이터 공유 후 플래그를 업데이트.
  • Reading Operator: 플래그 확인 후 데이터 복사.
  • 이 메커니즘은 인증 가능한 예측 가능한 동작을 보장하며, 코어 수가 적을 때 (예: 4 개) 메모리 오버헤드가 manageable 합니다.

3. 주요 기여 (Key Contributions)

1. DAG 스케줄링의 형식화: 임베디드 항공우주 시스템의 DNN 병렬 실행을 DAG 스케줄링 문제로 명확히 정의하고, 최적 스케줄을 찾기 위한 수학적 모델을 제시했습니다.
2. 효율적인 ILP 인코딩 제안: 기존 ILP 모델의 복잡도를 대폭 낮추어, 제한된 컴퓨팅 자원에서도 최적 또는 근사 최적 스케줄을 빠르게 찾을 수 있는 새로운 제약 조건을 도입했습니다.
3. ACETONE 의 다중 코어 확장: 순차 코드 생성기를 병렬 코드 생성기로 확장하고,bare-metal 환경에 적합한 경량 동기화 메커니즘을 통합하여 실제 하드웨어에서 실행 가능한 코드를 생성했습니다.
4. 정량적 검증: OTAWA 도구를 이용한 정적 WCET 분석과 Texas Instruments KeyStone II SoC 플랫폼에서의 실제 실험을 통해 병렬화의 이점과 예측 가능성을 입증했습니다.

4. 실험 결과 (Results)

• 스케줄링 성능:
  • 속도 향상 (Speedup): DSH 알고리즘이 ISH 보다 더 높은 속도 향상을 보였으나, 코어 수가 특정 임계값 (최대 병렬성) 을 넘으면 증가가 멈추는 현상이 관찰되었습니다.
  • 계산 시간: ISH 는 매우 빠르고 안정적이었으나, DSH 는 코어 수가 증가함에 따라 계산 시간이 급격히 증가했습니다. ILP 솔버는 소규모 그래프에서는 최적해를 찾지만, 대규모 그래프에서는 시간 제한 (Timeout) 에 걸리는 경향이 있었습니다.
• WCET 및 실제 실행 평가:
  • GoogleNet 아키텍처를 대상으로 실험한 결과, 병렬화 후 전체 WCET 는 약 8% 개선되었습니다.
  • 병렬화가 가능한 구간 (MaxPool 2 부터 Inception 2/Concat 까지) 에서는 46% 의 실행 시간 단축 효과를 보였습니다.
  • 실제 하드웨어 (4 코어 ARM Cortex-A15) 테스트에서도 이론적 개선 (8%) 과 유사한 8% 의 가속을 달성했습니다.
  • 병목 현상: 전체 실행 시간의 대부분을 차지하는 순차적 레이어 (Conv 1, Conv 2) 가 병렬화 이점을 제한하는 주요 원인으로 분석되었습니다.

5. 의의 및 결론 (Significance & Conclusion)

• 안전 임계 시스템에서의 ML 적용: 이 연구는 전용 가속기가 없는 다중 코어 CPU 환경에서도 DNN 을 안전 임계 시스템에 통합할 수 있는 실용적인 경로를 제시합니다.
• 예측 가능성 유지: 병렬화를 도입하면서도 WCET 분석 도구 (OTAWA) 와 호환되는 구조를 유지하여, 항공우주 인증 (DO-178C 등) 을 위한 예측 가능성을 확보했습니다.
• 미래 작업: 현재 연구는 동질적인 코어와 공유 메모리 (UMA) 환경에 국한되어 있습니다. 향후 이질적인 코어 (Heterogeneous cores) 나 전용 가속기가 포함된 환경으로 확장하고, 더 정교한 병렬화 기법을 탐구할 계획입니다.

결론적으로, 이 논문은 ACETONE 프레임워크를 다중 코어 환경에 적응시켜, 항공우주 시스템의 실시간 제약 조건을 만족하면서도 DNN 추론 성능을 향상시킬 수 있는 검증된 방법론을 제시했습니다.