SPM(ScratchPad Memory) 기반 요소기술 연구

연구 배경

컴퓨터 시스템에서 코어의 확장성을 제한하는 요소 중의 하나로 메모리 계층 (Memory Hierarchy) 이 논의되고 있다. 특히 캐시 간에 동일한 메모리 이미지를 갖도록 해 주는 캐시 일관성 (Cache coherency) 은 메모리 계층 내에서도 확장성을 크게 저해하는 요인이다. SPM (ScratchPad Memory) 는 캐시에서 하드웨어적으로 제공하는 태그 및 일관성 기능이 제외된 메모리이다. SPM 은 데이터를 직접적으로 관리해야 한다는 부담이 있는 반면, 확장성이나 에너지, 공간 효율성 등에서 캐시에 비해 뛰어난 성능을 보이므로 다양한 아키텍처에서 이를 도입하고 있다.

연구 내용

코드 관리 기법

  • 함수 분할 기법

SPM 기반의 아키텍처에서는 효율적인 실행을 위해서 code / stack / heap 등을 각각 소프트웨어적으로 관리해 주어야 한다. 본 연구에서는 SPM 에서의 code management 를 연구하였으며, 그 중에서 많이 사용되는 방식인 function-to-region mapping 기술을 개선하였다. Fig1

그림과 같이, function-to-region mapping algorithm 은 SPM 을 region 단위로 분할하고 각각의 function 을 region 에 할당함으로써 코드를 관리한다. 효율적인 mapping 을 만들기 위해서는 서로 자주 호출하는 함수들을 다른 region 에 할당하는 것이 중요한데, 본 연구에서는 함수 단위로 mapping 이 작동한다는 점에 착안하여 function splitting 기술을 제안하였다.

Fig2

위의 그림에서 M1 과 M2 는 동일한 크기의 SPM 에 적용할 수 있는 두 가지 mapping 을 나타내고 있다. 같은 공간을 사용함에도 M2 는 M1 보다 효율적인데, 이는 M1 의 경우 main 과 F1 을 동일한 주소에 mapping 하여 서로를 호출할 때 마다 충돌이 발생하는 반면, M2 에서는 두 함수를 다른 주소에 mapping 하여 충돌을 최소화했기 때문이다.

Fig3

그러나 모든 프로그램에서 효율적인 mapping 이 가능한 것은 아니다. 위의 그림과 같이 충분한 SPM 공간이 없을 경우, 자주 충돌하는 함수인 caller 와 callee 를 서로 다른 주소에 mapping 할 수 없으므로 코드 관리 비용이 매우 커진다. 이 경우, 함수 내부의 실제로 충돌이 발생하는 loop 부분만을 새로운 함수로 만들면 충돌하는 함수의 크기를 감소할 수 있어 효율적인 mapping 을 만들 수 있는 기회가 생긴다. 이 점에 착안하여, 본 연구에서는 함수의 내부에서 loop 구조를 새로운 함수로 만드는 방법을 기본으로 하여 loop 을 선택하는 방법과 그 구현에 대하여 제안하였다.

Fig4

위 그림은 주어진 프로그램에서 어떤 loop 를 선택하여 함수 분할을 수행할 지 결정하는 알고리즘을 나타내고 있다. 알고리즘 내의 SELECT 함수는 함수 간 연관성을 비교하여 가장 자주 호출되는 loop 을 결정하는 함수이다. 본 알고리즘은 가장 자주 호출되는 순서대로 loop 을 분할한 후 SPM 크기 및 프로그램 성능을 평가하여 향상이 있을 경우 다음 loop 를 선택하는 greedy algorithm 으로 구성되었다.

Fig5

위 그래프는 함수 분할 기법을 적용한 결과를 나타내고 있다. 성능은 최소한의 공간을 사용했을 때의 성능과 비교되었다. 함수 분할 기법은 최소 공간 대비 64%의 추가 공간을 사용하여 평균적으로 16%의 성능 향상을 보였으며, 88% 의 메모리 접근을 감소시켰다. 함수 분할 기법을 적용하지 않고 유사한 성능을 얻기 위해서는 20% 이상 많은 SPM 공간이 필요하였다.

  • 함수 인라이닝 및 아웃라이닝 기법

함수 인라이닝 및 아웃라이닝 기법은 함수 분할 기법을 확장하여, 함수의 인라이닝까지 고려한 기법이다. 본 기법으로 함수 분할의 성능을 더욱 확장하여, 최소 공간보다 더 적은 공간을 사용하면서 함수 분할 이상의 성능 향상을 제시하였다.

  • 선제적 함수 적재 기법

본 기법은 기존 연구들이 미리 함수를 SPM 에 적재시키지 않고, 함수가 호출되는 시점에 적재를 시작함으로써 CPU 가 불필요한 대기 시간을 가지게 되는 점을 향상시킨 기법이다. 이를 이용하여 추가적인 SPM 공간을 사용하지 않고 14.7% 의 성능을 추가적으로 향상시킬 수 있다.

향후 계획

향후 연구 계획으로 stack 과 heap 을 관리하는 기술 개발 및 SPM 기술을 실제적인 OS에 적용하는 연구를 계획하고 있다.

  • SPM 에서의 stack 관리 기법 및 최적화 방법
  • SPM 에서의 heap 관리 기법 및 최적화 방법
  • LWK 에서 SPM 을 활용하는 방법에 대한 연구

연구 결과물

  • 논문
    • "Splitting functions in code management on scratchpad memories." Proceedings of the 35th International Conference on Computer-Aided Design. ACM, 2016.
    • "Reducing Code Management Overhead in Software-Managed Multicores", Design, Automation and Test in Europe (DATE) 2017 (accepted)
    • "스크래치패드 메모리 기술 활용 동향", 정보과학회지 10월호, 2017
  • 시연 영상