※ 사전지식
이 문제에서 필요한 사전지식은 파이프라인과 ARM 아키텍쳐의 두 종류의 모드에 대한 것이다.
그럼 하나씩 살펴보도록 하겠다.
파이프라인
CPU는 클록 신호에 따라 명령을 처리하게 설계되어 있다. 하지만 이 파이프라인이라는 메커니즘을 적용하면 주어진 클록 속도보다 더 빠르게 처리할 수 있게 된다. 기본 명령어는 순차적으로 명령을 처리하기 전에 일련의 종속 단계로 니뉘어져 서로 다른 단계가 병렬로 실행될 수 있다.
위 내용을 받아드리기 쉽게 좀 구체화시켜 정리해보도록 하겠다.
보통 파이프라인에 대한 설명을 할 때 우리는 명령 처리 단계를 4단계(CPU 아키텍쳐에 따라 다양함)로 나누어 설명하곤 한다.
1. Instruction Fetch : 다음에 실행할 명령어를 읽는다.
2. Instruction Decode : 명령어를 해석한다.
3. Execute : 명령어를 수행한다.
4. Write-Back : 처리된 결과를 저장한다.
위 순서대로 잘 설명되어 있는 내용을 찾아서 이를 그림에 맞춰 순서대로 정리해보겠다.
상단의 회색 박스는 실행되기를 기다리는 명령어의 리스트이고 아래의 회색 박스는 실행이 완료된 명령어의 리스트이다. 중간의 하얀 박스가 바로 파이프라인이다.
명령어들이 어떻게 실행되는지 싸이클 몇 개를 통해 알아보도록 하겠다.
§ 0 Cycle
4개의 명령어가 실행되기를 기다린다.
§ 1 Cycle
녹색 명령어는 메모리로부터 패치된다.
§ 2 Cycle
녹색 명령어는 디코드된다.
보라색 명령어는 메모리로부터 패치된다.
§ 3 Cycle
녹색 명령어는 실행된다. (실제 명령이 실행된다)
녹색 명령어는 디코드된다.
파랑 명령어는 페치된다.
§ 4 Cycle
녹색 명령어는 결과적으로 레지스터나 메모리에 쓰인다.
녹색 명령어는 실행된다.
파랑 명령어는 디코드된다.
빨강 명령어는 패치된다.
이제 파이프라인이란 개념이 어떤건지 좀 명확해졌을거라 믿는다.
즉, 하나의 명령어를 처리할 수 있는 여러 단계로 나누어 종속된 일련의 명령어들이 처리되는 것에 있어 서로에게 영향을 주지 않는 범위에서 동시에 다른 명령어를 처리할 수 있는 것이다.
예를 들면, ADD 명령어와 MOV 명령어가 존재할 경우 처음 ADD 명령어를 Fetch 한 뒤 ADD 명령어가 다 처리되기도 전에 다시 MOV 명령어가 다시 Fetch 단계로 진입되게 되는 것이다.
따라서 PC(Program Counter)는 단순히 다음 명령어를 나타내기 보단 Fetch를 진행해야 하는 위치를 나타낸다고 하는게 더 옳은 표현이다(파이프라인 기술이 도입된 아키텍쳐의 경우).
ARM vs Thumb Mode
이 문제풀이에서 가장 크게 눈여겨봐야 할 것은 아래 두줄로 설명 가능하다.
ARM : 32bit RISC Machine
Thumb : 16bit RISC Machine
아래 레퍼런스에 추가해놓은 사이트(ref.2)에 따라 추가로 설명하자면,
처음 32 bit ARM을 만들어 냈을 때, 이 세상을 지배하던 Embedded system의 memory는 16 bit data line을 가진 Memory가 그 시대의 주인공 이었슴다. 32 bit Core라고 해서 그 시대에 가장 흔히 구할 수 있고 많이 생산되던 16bit bus line의 메모리를 무시할 수없는 노릇이었지요.
해서 나타난 게 Thumb 모드라고 한다.
사전지식 끝!!
※ 문제풀이
그럼 이제 문제풀이를 시작해보겠다.
이 문제는 위에 사전지식에서 보았듯이 파이프라인과 ARM, Thumb 모드에 관련된 지식, 그리고 약간의 ARM 어셈블러를 해석할 수 있으면 풀 수 있는 문제이다.
우선 문제를 한번 보자.
크기상 우선 메인함수만 캡쳐해왔다.
key1 함수, key2 함수 그리고 key3 함수의 결과 값을 합쳐 내가 입력한 값과 비교하는 문제이다.
그럼 key? 함수가 어떤 값을 반환하는 지 알아보도록 하자.
우선 key1 함수이다.
현재 pc 레지스터에 있는 값을 r3로 옮기고 난 뒤 반환한다.
위에서 설명한 파이프라인을 보았으면 이제 pc가 가리키는 값이 0x0008cdc라고 생각하지 않을거라 믿는다. :)
그 다음은 Key2 함수이다.
여기에서는 key+12 위치에 있는 add 명령어와 bx 명령어를 잘 확인해야 한다. bx는 분기명령어 중 하나인데 피연산자의 0번째 비트의 값을 확인하여 1일 경우 Thumb 모드로 진입하게 된다. 그렇게 되면 pc를 계산하는 값이 Thumb 모드에 맞춰 변경되게 될 것이다. 그럼 뭐 key2 함수에서 어떤 값을 반환할 지도 예측 가능하지 않은가?!
그리고 마지막 key3 함수는
이와 같다. lr은 리턴 주소값을 가지고 있는 레지스터이다. 이것은 직관적이니까 넘어가도록 하겠다.
그럼 이 값을 다 더한 값이 곧 정답이다.
문제풀이 끝!!!
사실 이 leg 문제까지는 문제를 직접 풀어보려하지 않고 인터넷을 먼저 검색해서 어떤 것이 문제의 핵심인지 파악하고 나서 접근했다. 다시 일을 시작하게 되니 이런 저런 고민하는 시간이 너무 아쉬워서 단순 학습의 개념으로만 만족했었다. 어째든 이 문제까지 풀어본 바(학습해본 바?^^) 여러가지 그러려니 했던 많은 내용들을 구체화시키고 포너블이라는 영역이 어떤것인지 대충 개념은 잡을 수 있었다(기초적인 거에도 쩔쩔매던 놈이-ㅅ-).
앞으로는 시간있을 때마다 스스로 고민해서 풀어봐야겠다.
화이팅~~!!
Reference
[1] Instruction pipelining, https://en.wikipedia.org/wiki/Instruction_pipelining
[2] ARM mode와 THUMB mode, http://recipes.egloos.com/4985218
