재목적성을 고려한 직접 매핑 기반의 이진 변환 규칙 생성 도구 501 재목적성을 고려한 직접 매핑 기반의 이진 변환 규칙 생성 도구 (Direct Mapping based inary Translation Rule Generator with Considering Retargetability) 서용진 김 현 수 (Yongjin Seo) (Hyeon Soo Kim) 요 약 이진 변환은 특정 장치에서 동작하도록 구성된 프로그램을 다른 장치에서 동작할 수 있도록 재구성하는 과정을 말한다. 이진 변환을 수행하기 위해서는 두 장치 사이의 변환 규칙을 생성하는 것이 매우 중요하다. 변환 규칙을 생성하는 방법은 직접 매핑과 간접 매핑으로 나뉜다. 직접 매핑은 성능을 위 한 방법인 반면, 간접 매핑은 재목적성을 위한 방법이다. 본 논문에서는 임베디드 시스템에 적합한 직접 매핑 기반의 이진 변환을 수행한다. 그렇지만 재목적성 역시 중요한 요구사항이기 때문에, 재목적성을 고 려한 직접 매핑 기반의 이진 변환 방법을 제안한다. 또한 제안된 방법을 바탕으로 자동으로 변환 규칙을 생성하는 도구를 구현한다. 이 방법을 통해서 성능과 재목적성을 모두 고려한 변환 규칙을 생성할 수 있 으며, 더 나아가 이진 변환을 수행하는데 소요되는 비용을 줄일 수 있다. 키워드: 이진 변환, 직접 매핑, 재목적성, 가상 ISA Abstract inary translation is a restructuring process in order to execute a program targeting a specific device on the other devices. In binary translation, it is very important to generate the translation rules between two devices. There are two methods for generating the translation rules, direct and indirect mapping. The direct mapping is the method for performance, while the indirect mapping is the method for retargetability. This paper suggests a binary translation method based on the direct mapping for the embedded systems. ecause, however, the retargetability is also important requirement, we suggest the direct mapping based binary translation with considering the retargetability. In addition, we implement an automatic generation tool for translation rules to prove our concept. Through this method, we can generate the translation rules with considering the performance as well as the retargetability. Furthermore, we can reduce costs for the binary translation. Keywords: binary translation, direct mapping, retargetability, virtual ISA 본 연구는 한국연구재단을 통해 교육과학기술부의 우주기초원천기술개발 사업 (NSL, National Space Lab)으로부터 지원받아 수행되었습니다(2011-0020905) 학생회원 : 충남대학교 컴퓨터공학과 yjseo082@cnu.ac.kr 종신회원 : 충남대학교 컴퓨터공학과 교수 hskim401@cnu.ac.kr (Corresponding author임) 논문접수 : 2014년 3월 12일 (Received 12 March 2014) 논문수정 : 2014년 4월 26일 (Revised 26 April 2014) 심사완료 : 2014년 5월 7일 (Accepted 7 May 2014) CopyrightC2014 한국정보과학회ː개인 목적이나 교육 목적인 경우, 이 저작물 의 전체 또는 일부에 대한 복사본 혹은 디지털 사본의 제작을 허가합니다. 이 때, 사본은 상업적 수단으로 사용할 수 없으며 첫 페이지에 본 문구와 출처를 반드시 명시해야 합니다. 이 외의 목적으로 복제, 배포, 출판, 전송 등 모든 유형의 사용행위 를 하는 경우에 대하여는 사전에 허가를 얻고 비용을 지불해야 합니다. 정보과학회논문지: 소프트웨어 및 응용 제41권 제7호(2014.7)
502 정보과학회논문지 : 소프트웨어 및 응용 제 41 권 제 7 호(2014.7) 1. 서 론 이진 변환(inary Translation)은 특정 장치 M에서 동작하도록 구성된 이진 프로그램을 장치 M이 아닌 다 른 장치에서도 동작할 수 있도록 프로그램을 재구성하 는 기술을 말한다[1]. 여기서 장치 M을 원본 장치 (Source Machine)라 하고 장치 M 외의 다른 장치들을 대상 장치(Target Machine)라 한다. 원본 장치를 대상 으로 구성된 프로그램은 원본 장치의 특성(예: 명령어, 레지스터, 메모리 등)이 반영되어 있기 때문에 대상 장 치에서 동작할 수 없다. 따라서 원본 장치의 프로그램에 대상 장치의 특성이 반영되도록 재구성하는 과정이 필 요하며, 이진 변환은 이와 같은 작업을 수행하는 기술이 다. 이진 변환을 수행하는 과정에서 두 장치의 특성 사 이의 관계를 설정하는 매핑(Mapping) 작업을 수행한다. 매핑을 통해 생성된 정보를 변환 규칙이라 한다. 변환 규칙은 직접 매핑과 간접 매핑을 통해 생성된다. 직접 매핑은 두 장치의 특성 사이의 관계를 직접 설정 하는 방법이다. 반면 간접 매핑은 컴파일 기술에서 사용 되는 중간 표현을 활용하여 두 장치의 특성 사이의 관 계를 간접적으로 설정하는 방법이다. 두 매핑 방법을 도 식화하면 그림 1과 같다. 그림 1에서 정적 시점은 이진 변환이 수행되기 이전을, 동작 시점(Runtime)은 이진 변환이 수행되는 시점을 의미한다. 동작 시점이 지나면 원본 장치의 프로그램이 동작 장치에 동작될 수 있는 형태로 변환된다. 그림 1을 통해 알 수 있는 직접 매핑 과 간접 매핑의 가장 큰 차이점은 변환 규칙이 생성되 는 시점이다. 직접 매핑은 정적 시점에 생성되며, 개발 자가 직접 장치의 특성에 대해 이해한 뒤 변환 규칙을 작성하는 과정을 거친다. 따라서 변환 규칙을 생성하는 데 많은 시간이 요구되는 방법이다. 또한 장치의 변경이 발생하면 변환 규칙을 다시 작성하여야 하는 문제를 갖 는다. 하지만 동작 시점에서는 변환 규칙에 따라 변환만 수행되기 때문에 최적화된 변환을 수행할 수 있다. 간접 매핑은 동작 시점에 중간 표현 혹은 중간 코드를 이용 하여 변환 규칙을 자동으로 생성한다. 간접 매핑은 변환 규칙이 자동으로 생성되기 때문에 장치가 변경되더라도 그림 1 직접 매핑과 간접 매핑 Fig. 1 Direct Mapping and Indirect Mapping
재목적성을 고려한 직접 매핑 기반의 이진 변환 규칙 생성 도구 503 효과적으로 대처할 수 있다는 장점을 갖는다. 이러한 속 성을 재목적성(Retargetability)라고 한다. 그러나 변환 규칙을 동작 시점에 생성하기 때문에 최적화된 변환을 수행하기 어렵다. 정리하면 직접 매핑은 성능에 최적화 된 방법이며, 간접 매핑은 재목적성을 위한 방법이다. 두 방법은 서로 상충관계를 갖기 때문에 이진 변환을 적용하고자 하는 시스템의 특성에 맞게 적절한 매핑 방 법을 선택하여 사용하여야 한다. 임베디드 시스템, 즉, 실시간성과 자원제약성이 요구되 는 시스템에서 이진 변환을 수행할 때에는 직접 매핑이 간접 매핑보다 더 적합한 방법이다. 간접 매핑은 직접 매 핑에 비해 높은 자원을 요구하기 때문이다. 그러나 이는 단일 시스템에 대해 이진 변환을 수행할 때의 이야기이 다. 만일 다수의 임베디드 시스템에 대해서 이진 변환을 수행하여야 한다면, 재목적성 역시 달성하여야 하는 속 성이 된다. 물론 이 경우에도 가장 중요한 것은 최적화된 이진 변환을 수행하는 것이다. 이에 본 논문에서는 직접 매핑을 기반으로 하되 재목적성 역시 달성할 수 있는 방 법을 제안한다. 이를 위해서 간접 매핑 기법을 응용하여 변환 규칙이 갖는 의존성을 낮추면서 정적 시점에 변환 규칙을 생성하는 방법을 제시한다. 또한 제시한 방법을 기반으로 변환 규칙을 생성하는 도구를 구현한다. 본 논 문에서 다루는 변환 요소의 범위는 명령어로 한정한다. 2. 관련 연구 직접 매핑과 간접 매핑에 대한 언급은 논문[2]에서 시 작한다. 직접 매핑과 간접 매핑의 가장 큰 차이는 변환 규칙의 가시성에 있다. 직접 매핑은 개발자에 의해서 원 본 장치의 명령어가 대상 장치의 어떤 명령어로 변환되 어야 하는지 기술된다. LayVMM[3]은 ERC32 하이퍼바 이저로, LEON3의 이진 코드를 ERC32의 이진 코드로 변환하여 동작시킨다. LayVMM에서는 직접 매핑 기법 을 이용하며, 이는 변환기의 구현 코드로 반영된다. ISA- MAP[4] 역시 직접 매핑 기법을 사용한다. ISAMAP은 변환 규칙을 변환기의 구현 코드로 표현하지 않고, 변환 규칙을 명시할 수 있는 언어인 ArchC를 제공한다. ArchC를 통해 두 장치 사이의 변환 규칙을 명시하고, 도구를 통해 변환 규칙을 최적화하는 작업을 거친다. 논 문 [5]에서는 시뮬레이션의 속도 향상을 위해서 직접 매 핑 기법을 사용한다. 기존에 사용하였던 중간 표현을 사 용하지 않고 명령어 사이의 관계를 직접적으로 명시하는 방법을 사용한다. 위 연구들이 직접 매핑 기법을 사용하 는 이유는 (1)코드의 최적화에 용이하며, (2)변환 시 발 생할 수 있는 오버헤드를 최소화할 수 있음을 들고 있다. 반면, 간접 매핑 기법을 사용하면 변환 규칙의 가시성 이 떨어진다. 간접 매핑 기법에서는 원본 장치의 이진 코드를 중간 표현으로 변환하고, 중간 표현으로 변환된 이진 코드를 대상 장치의 이진 코드로 변환한다. 즉, 원 본 장치와 대상 장치 사이의 직접적인 관계가 형성되지 않기 때문에, 어떤 부분을 변환 규칙으로 바라보아야 하 는지 모호한 것이다. 이러한 모호성은 오히려 유연성을 제공한다. 간접 매핑 기법을 사용하는 연구는 대부분 재 목적성을 목표로 한다. UQDT[6], Walkabout[7] 그리 고 Crossit[8], 논문 [9,10]은 모두 간접 매핑 기법을 통해서 재목적성을 달성하고자 한다. 위 논문들을 통해 직접 매핑 기법은 변환의 최적화, 즉 성능을 위한 방법이며, 간접 매핑 기법은 재목적성을 위한 방법임을 알 수 있다. 또한 변환 규칙의 가시성이 직접 매핑과 간접 매핑을 분류하는데 기준이 되며, 더 나아가 변환 규칙의 가시성 여부가 이진 변환에 영향을 준다는 것을 알 수 있다. 따라서 임베디드 시스템에 이 진 변환을 적용하기 위해서는 우선적으로 가시성을 갖 는 변환 규칙을 생성하여야 한다. 단, 변환 규칙을 생성 하는 과정에서 재목적성을 고려하여야 한다. 본 논문에서는 이를 위해서 간접 매핑 기법의 연구를 통해서 재목적성을 달성하기 위한 요소를 다음과 같이 도출하였다. 첫 번째로 장치의 특성을 작성할 수 있는 별도의 명세 언어를 제공하여야 한다. MSI-SDL[11]은 다양한 원본 이진 코드를 하나의 대상 장치에서 동작시 키기 위해 사용하는 명세 언어이다. 이를 통해서 다양한 원본 이진 코드를 동일한 형태로 표현할 수 있다. Walkabout[7] 역시 다양한 명세 언어를 통해서 다양한 장치의 특성을 동일한 언어를 기술하여 사용한다. 이러 한 명세 언어는 경우에 따라 중간 표현으로 사용되기도 한다. 두 번째로 변환 규칙은 자동으로 생성되어야 한 다. 변환 규칙의 모호성은 중간 표현 외에도 자동 생성 을 통해 실현된다. 앞서 살펴본 간접 매핑 기법의 연구 에서는 변환 규칙을 기술하는 방법에 대해서는 언급하 지 않는다. [9]에서는 컴파일러 기법을 사용하여 변환 규칙을 자동으로 생성하며, [10]에서는 중간 표현을 이 용하여 대상 장치를 위한 이진 코드를 생성한다. 중간 변환 규칙을 직접적으로 생성하지 않더라도, UQDT[6] 와 Walkabout[7]에서는 변환을 수행하는 요소를 자동으 로 생성한다. 이는 결국 변환 규칙을 자동으로 생성하는 것과 같은 효과를 갖는다. 제시된 두 가지 요건을 만족 함으로써 재목적성을 달성할 수 있으며, 본 논문에서는 두 가지 요건을 바탕으로 재목적성을 고려한 직접 매핑 기법을 제시한다. 3. 재목적성을 고려한 직접 매핑 기반의 이진 변환 방법 관련 연구를 통해 파악한 재목적성 달성 요건을 통해
504 정보과학회논문지 : 소프트웨어 및 응용 제 41 권 제 7 호(2014.7) 그림 2 재목적성을 고려한 직접 매핑 방법 Fig. 2 Direct Mapping with Considering Retargetability 본 논문에서는 그림 2와 같은 매핑 방법을 제안한다. 제안한 매핑 방법의 핵심 아이디어는 중간 표현을 정 적 시점에서 활용하여 변환 규칙을 생성하는 것이다. 여 기서 중간 표현을 통해 추상화된 ISA(Instruction Set Architecture)를 생성하는 과정이 규칙 생성 도구에 반 쯤 걸쳐있는 형태로 표현된 것은 이 과정이 방법에 따 라 수동 혹은 자동으로 수행될 수 있기 때문이다. 중요 한 것은 이를 통해서 정적 시점에 변환 규칙을 자동으 로 생성할 수 있으며, 이는 곧 장치의 변경에 대해 효과 적으로 대처할 수 있다는 것이다. ISA를 추상화하는 것 보다는 변환 규칙을 생성하는 것이 더 많은 비용을 요 구하기 때문에, 혹여 ISA 추상화가 수동으로 수행된다 고 하더라도 이 방법이 갖는 효과에 끼치는 영향은 적 다. 그림 2의 방법은 간접 매핑처럼 중간 표현을 사용하 지만, 이를 이용하여 변환 규칙을 생성한다는 측면에서 차이가 있다. 간접 매핑에서는 원본 장치의 프로그램으 로부터 변환 규칙을 생성하지만, 그림 2의 방법에서는 원본 장치의 ISA로부터 변환 규칙을 생성한다. 제안한 매핑 방법은 재목적성을 달성할 수 있는 방법 이기 때문에, 그림 2와 같은 방법으로 변환 규칙을 생성 한다면 재목적성을 고려한 직접 매핑 기반의 이진 변환 을 수행할 수 있다. 이제는 재목적성 달성의 핵심이 되 는 중간 표현을 통해 변환 규칙을 자동 생성하는 방법 에 대해서 기술한다. 3.1 명령어 추상 모델 기반의 변환 규칙 생성 이 방법은 본 논문의 선행 연구로써, 명령어 추상 모 델을 중간 표현으로 이용하여 변환 규칙을 생성한다. [12] 에서는 중간 표현으로 RTL(Register Transfer Language) 기반으로 작성된 명령어의 행위를 AST(Abstract Syntax Tree)로 표현하며, AST로 표현된 명령어를 비 교함으로써 매핑을 수행한다. 이 방법은 프로그램을 구 성하는 원본 장치의 명령어 하나가 대상 장치의 명령어 로 변환될 수 있다면, 프로그램 전체를 대상 장치의 프 로그램으로 변환할 수 있다는 생각을 바탕으로 하고 있 다. 따라서 명령어 추상 모델은 단일 명령어를 위한 중 간 표현이며, 이를 통해 각 명령어의 행위를 표현할 수 있다. 3.1.1 명령어 추상 모델 명령어 추상 모델은 SLA(Specification Language for Automatic rule generation of inary translation) 으로 작성된 ISA 명세로부터 생성되며, SLA은 RTL 기반으로 명령어의 행위를 작성하도록 구성된다. 명령어 추상 모델은 도구를 통해 자동으로 생성되기 때문에, ISA 명세는 동일한 포맷으로 작성되어야 한다. 따라서 기존의 ISA 명세를 이용하지 않고 SLA을 통해 새로 운 명세를 작성한다. SLA을 통한 ISA 명세 작성은 개발자에 의해 이루어진다. SLA의 문법과 이를 통한 작성 예는 4.1절에서 다룬다.
재목적성을 고려한 직접 매핑 기반의 이진 변환 규칙 생성 도구 505 정의. 명령어 추상 모델 명령어 추상 모델은 트리(Tree) 구조로 다음과 같이 정의된다. N 노드 집합 은 명령어의 기능과 자료 유형을 표현하 기 위한 단위 요소들의 집합이며, 에지 집합 은 노드 간의 연결을 표현한다. 이때, 가 의 부모 노드가 되 며, 부모 노드와 자식 노드는 연산자와 피연산자 관계를 갖는다. 각 단위 요소의 의미는 에 의해 부여된 다. 의미 집합 S는 기능을 표현하는 와 자료 유형을 표현하는 로 구성된다. 는 20개의 원소를 가지며, 기능을 표현하는 값으로 구성된다. 는 자료 유형 와 자료 크기 로 구성되며, 자료 유형의 종류에는 명령어 단계에서 공통적으로 사용되는 자료 유형인 정수, 실수, 상수가 존재한다. 명령어 추상 모델을 통해서 SAPRC v7의 ADD 명령 어에 대해서 추상화하면 그림 3과 같이 표현된다. 하며, 다음과 같은 조건이 성립할 때 모델이 서로 유사 하다고 판단한다. 두 모델의 트리 형태는 동일하여야 한다. 두 모델의 트리 형태가 동일할 때, 동일한 위치에 존재하는 노드에 부여된 의미가 일치하여야 한다. 동일한 위치에 존재하는 두 노드에 부여된 의미가 라면 두 노드의 의미는 동일하여야 한다. 동일한 위치에 존재하는 두 노드에 부여된 의미가 라면 대상 장치의 노드의 의미가 원본 장치의 노 드의 의미를 포함하여야 한다. 다시 말해 원본 장치 의 노드 이고 대상 장치의 노드 일 때, 두 노드 사이의 의미가 이고 이라면 를 만족하여야 한다. 에 대한 유사성을 위와 같이 정의한 이유는 명령어 는 자신이 처리할 수 있는 자료 유형보다 작은 자료 유 형을 수용할 수 있기 때문이다. 예를 들어 64비트의 정 수 덧셈이 가능한 명령어는 64비트보다 작은 자료 유형 인 32비트 혹은 16비트의 덧셈도 수행할 수 있다. 따라 서 에 대한 유사성을 위와 같이 정의한다. 정의된 유 사성을 토대로 명령어 추상 모델 기반의 변환 규칙 생 성은 그림 4의 알고리즘과 같다. 그림 4의 알고리즘은 원본 장치의 모든 명령어에 대 해서 대상 장치의 모든 명령어와 비교하며 수행된다. 5 번째 줄의 내용은 의미 없는 비교를 피하기 위한 것이 다. 서로 노드의 수가 같지 않으면, 두 모델의 형태가 같을 수 없으므로 비교를 수행하지 않는다. 9번째의 는 16번째에 기술된 함수로써, 두 모델 의 루트 노드부터 순차적으로 비교하여 두 모델이 같은 지 판별한다. 18번째 줄은 두 노드에 부여된 의미가 그림 3 ADD 명령어에 대한 명령어 추상 모델 Fig. 3 Instruction abstract model for ADD instruction 3.1.2 명령어 추상 모델 사이의 비교 연산을 이용한 변환 규칙 생성 명령어 추상 모델은 명령어의 행위를 표현하기 때문 에, 어떤 두 명령어 추상 모델이 서로 동치 관계에 있다 면 두 명령어가 서로 동일한 행위를 한다고 볼 수 있다. 이러한 관계가 성립하기 때문에, 본 논문에서는 모델 사 이의 비교를 통해 변환 규칙을 생성한다. 단, 동일한 행 위를 하는 명령어끼리만 변환 규칙을 생성할 수 있는 것은 아니다. 여기서는 특정 명령어의 행위를 대신 수행 할 수 있는 명령어를 찾는 것이 변환 규칙을 생성하는 것이다. 따라서 모델 사이의 유사성에 대한 정의가 필요 인 경우에 수행되는 비교이며, 통상적으로 를 의미로 갖는 노드는 말단 노드가 아니기 때문에 자식 노드에 대해 재귀적으로 를 호출한다. 를 의 미로 갖는 노드는 말단 노드이기 때문에, 23번째 줄과 같이 를 반환한다. 이와 같은 방법을 통해 두 모델 을 비교하고 변환 규칙을 생성한다. 그러나 [12]에서 제시한 방법을 통해 생성되는 변환 규칙은 원본 장치의 명령어에 대해 모두 커버하지 못한 다. 그 이유는 원본 장치와 대상 장치가 갖는 명령어가 모두 동일한 행위를 갖는 명령어로만 구성되지 않기 때 문이다. 한 예로 SPARC v7과 TI의 정수 덧셈 명령어 를 들 수 있다. 두 장치의 명령어는 모두 덧셈을 수행하 지만, 그 방법은 서로 다르다. SPARC v7에서는 오직 32비트 정수형에 대한 덧셈을 제공하되 캐리 비트를 사
506 정보과학회논문지 : 소프트웨어 및 응용 제 41 권 제 7 호(2014.7) 셈 기능 제공이라는 동일한 목적을 갖는다. 따라서 본 논문에서는 행위적 측면에서의 중간 표현 대신 결과적 측면에서의 중간 표현을 사용하여 변환 규칙을 생성한 다. 결과적 측면에서의 중간 표현을 위해 가상 ISA를 제안한다. 이를 통해서 AST에서 고려하지 못한 특성에 대해서도 반영할 수 있다. 3.2.1 가상 ISA (Virtual ISA) 가상 ISA는 어떤 ISA든지 가질 수 있는 명령어의 집 합이며, 가상 ISA 내의 명령어는 기능과 출력을 통해 결과적 측면에서 분류된다. 하지만 실제로 기능과 출력 만을 이용하여 명령어 사이의 비교를 수행하는 것은 불 가능하다. 만일 가상 ISA의 명령어 중 64비트 정수를 출력하는 덧셈 명령어가 존재한다면, 32비트 정수 덧셈 명령어만 지원하는 SPARC v7에서는 해당 기능을 수행 하는 명령어를 찾아낼 수 없다. 그러나 SPARC v7은 올림수(Carry bit)를 이용하여 64비트 정수 덧셈을 수행 할 수 있으며, 이는 SPARC v7의 덧셈 명령어가 올림 수를 사용하여 동작한다는 사실을 파악해야 알 수 있다. 즉, 결과적 측면에서의 중간 표현이라고 할지라도 행위 에 대한 기술은 필요하다. 앞서 수행된 연구를 통해 단일 명령어의 행위에만 집 중하지 않아야 함을 파악하였다. 본 연구에서는 명령어 의 결과적 측면에 집중하되 행위적 측면도 함께 고려할 수 있는 방법으로 가장 단순한 방법을 적용한다. 가상 ISA의 명령어를 기능의 결과에 대한 정보와 결과를 도 출하기 위해 가질 수 있는 모든 행위로 구성하는 것이 다. 이와 같은 방법을 적용하기 위해 가상 ISA 명령어 를 정의한다. 그림 4 명령어 추상 모델을 이용한 변환 규칙 생성 알고 리즘 Fig. 4 Translation rules generation Algorithm using instruction abstract model 용하여 다양한 자료 유형에 대한 덧셈을 수행하는 반면, TI에서는 애초에 다양한 자료 유형에 대한 덧셈 명령어 를 각각 제공한다. 두 장치의 명령어는 목적은 같지만, 행위적인 측면에서는 다른 명령어로 분류될 수밖에 없 다. 본 논문에서는 이를 보완하기 위해 가상 ISA 기반 의 변환 규칙 생성 방법을 제시한다. 3.2 가상 ISA 기반의 변환 규칙 생성 SPARC v7과 TI가 갖는 정수 덧셈 명령어의 구성은 다르지만, 이는 결국 다양한 정수 자료 유형에 대한 덧 정의. 가상 ISA 명령어 가상 ISA는 다수의 명령어 로 구성되며, 아래와 같이 정의된다. 은 명령어의 기능을 결과적인 측면에서 분류한 값으로, 기능 라벨(Functional Label)을 의미한다. 논문 [13]의 내용을 바탕으로 정의된다. 명령어 추상 모델의 와 유사해 보이지만, 명령어의 기능과 자료 유형을 하나로 묶어 표현하였으며 보다 세분된 형태를 갖는 다. 는 가상 ISA의 명령어의 행위 집합을 의미하며, 는 명령어의 기능을 수행할 수 있는 행위 중 하나 의 행위 인스턴스를 의미한다. 는 명령어 추상 모델 의 집합으로 표현되는데, 이는 가상 ISA의 명령어 기능 을 수행할 때 다수의 실제 명령어가 필요하기 때문이다.
재목적성을 고려한 직접 매핑 기반의 이진 변환 규칙 생성 도구 507 예를 들어 64비트 정수 덧셈 명령어에 대해서 필요한 SPARC v7의 명령어의 개수는 두 개이다. SPARC v7 은 32비트 정수 덧셈 명령어만 존재하기 때문에 두 개 의 명령어를 통해 64비트 덧셈 연산을 수행하여야 한다. 또한 는 두 가지로 구분된다. 그 중 는 기능에 대 한 통상적인 행위(Typical behavior)를 의미하며, 항상 1개의 원소로 구성된다. 는 그 외의 행위(Alternative behavior)를 의미하며, 의 원소를 제외한 모든 의 원소로 구성된다. 따라서 의 원소 개수는 0보다 큰 값을 갖는다. 하나의 기능에 대해 다수의 행위를 표현함으로써 명 령어 추상 모델이 갖는 약점을 해결할 수 있지만, 이는 또 다른 문제를 야기한다. 이와 같은 표현으로 인해 가 상 ISA의 명령어에 대해서 다수의 원본 장치 혹은 대 상 장치의 명령어가 매핑될 가능성이 있다. 이런 문제를 해결하기 위해 우선순위 함수 를 사용한다. 즉, 다수의 명령어와 매핑 되었을 경우에는 우선순위 함 수를 통해 가장 높은 우선순위를 갖는 명령어를 채택한다. 정의. 행위 우선순위 함수 명령어 가 갖는 행위 인스턴스 와 에 대해서 항상 가 성립한다. 또한 를 구성하는 행위 인스턴스 사이의 우선순위는 각 행위와 매핑된 명령어의 개수에 반비례한다. 다시 말 해 매핑된 명령어의 개수가 적을수록 우선순위가 높아 진다. 이는 매핑된 명령어의 개수가 적을수록 더 낮은 실행 시간을 가질 수 있기 때문이다. 마지막으로 우선순 위 함수는 절대 값이 아닌 상대 값을 갖는다. 위와 같은 정의를 통해서 가상 ISA는 명령어의 기능 에 대해서 결과적 측면과 함께 행위적 측면을 표현할 수 있으며, 특정 기능이 수행될 수 있는 모든 행위를 표 현함으로써 명령어 추상 모델이 갖는 문제를 해결할 수 있다. 3.2.2 가상 ISA 기반의 변환 규칙 생성 방법 가상 ISA도 기본적으로 명령어 추상 모델을 기반으 로 정의되었기 때문에, 명령어 추상 모델과 마찬가지로 트리의 유사성을 통해 변환 규칙을 생성한다. 다만, 명 령어 추상 모델 기반의 변환 규칙 생성에서는 원본 장 치와 대상 장치의 명령어를 직접 비교하였던 것과 달리 가상 ISA 기반의 변환 규칙 생성에서는 원본 장치와 가상 ISA의 명령어, 대상 장치와 가상 ISA의 명령어 사이의 비교가 수행된다. 본 논문에서는 이 과정을 중간 규칙 생성 과정이라고 하며, 이를 통해 중간 규칙이 생 성된다. 중간 규칙은 가상 ISA와 실제 ISA 사이의 변 환 규칙을 말한다. 중간 규칙 생성 과정이 끝나고 난 뒤, 가상 ISA의 명령어를 기준으로 원본 장치와 대상 그림 5 중간 규칙 생성 알고리즘 Fig. 5 Intermediate rules generation algorithm 장치 사이의 변환 규칙을 생성한다. 먼저, 중간 규칙 생 성은 그림 5의 알고리즘의 반복을 통해 수행되며, 이는 그림 4의 알고리즘과 크게 다르지 않다. 기본적으로 그림 5의 알고리즘은 그림 4의 알고리즘 과 마찬가지로 를 이용하여 비교 연산 을 수행한다. 차이가 있다면, 가상 ISA의 명령어가 다 수의 행위를 가지고 있기 때문에 더 많은 비교 연산을 수행한다는 것이다. 또한 가상 ISA의 명령어가 갖는 행 위 중 어느 행위와 규칙이 생성될지 알 수 없기 때문에 3번째 줄의 중간 규칙 테이블 를 사용한다. 4번째 줄 부터 13번째 줄까지는 중간 규칙 테이블 를 채우는 작업을 수행한다. 중간 규칙 테이블 를 모두 채우고 나면, 중간 규칙 테이블 의 행 중에서 모든 원소를 채 운 행에 대해서만 중간 규칙을 생성한다. 이때, 우선순 위가 가장 높은 행위에 대해서 중간 규칙을 생성하도록 한다(17번째 줄). 이해를 돕기 위해 예를 통해 그림 5의 알고리즘에 대한
508 정보과학회논문지 : 소프트웨어 및 응용 제 41 권 제 7 호(2014.7) 를 제외한 모든 부분이 채워진 중간 규칙 테이블을 얻을 수 있다. 이제 이 테이블을 이용하여 중간 규칙을 생성한다. 과 는 모든 셀의 내용이 채워져 있기 때 그림 6 중간 규칙 테이블 예제 Fig. 6 Example of intermediate rule table 동작 과정을 설명한다. 먼저, 입력으로 주어진 는 세 개의 행위를 가지며, 세 개의 행위가 갖는 명령어 추상 모델은 각각,, 이라고 하자. 또한 이다. 이를 통해 그림 6과 같은 중간 규칙 테이블을 생성한다. 은 중간 규칙 테이블의 첫 번째 행을 의미하며, 동 시에 가 갖는 첫 번째 행위( )를 의미한다. 또한 첫 번째 행위를 구성하는 명령어 추상 모델 가, 즉 첫 번째 행의 첫 번째 열에 해당하는 셀을 구성한다. 이 런 방식으로 나머지 행위에 대해서도, 를 구성하 여 중간 규칙 테이블을 완성한다. 완성된 중간 규칙 테 이블을 이용하여 중간 규칙을 생성하는 과정을 설명하 기 위해 그림 7과 같이 가상 ISA와 비교를 수행하는 임의의 를 정의할 수 있으며, 이를 통해 중간 규칙 테이블이 채워지는 과정은 역시 그림 7에 도식된다. 그림 7에서 왼쪽 테이블은 중간 규칙을 생성하기 위 해 의 명령어와 비교를 수행하는 모습을 표현한 것이며, 오른쪽 테이블은 비교를 통해 중간 규칙 테이블 이 채워진 모습을 표현한 것이다. 과 는 중간 규칙 테이블 내에 존재하지 않기 때문에, 두 모델에 대해서는 아무런 일도 일어나지 않는다. 은 에 존재하기 때 문에, 은 중간 규칙 테이블 내에 채워질 수 있다. 이 런 방식으로 의 모든 명령어에 대해서 수행하면 문에 중간 규칙 생성에 활용될 수 있지만, 는 그렇지 않기 때문에 활용될 수 없다. 또한 이 보다 높은 우선순위를 갖기 때문에, 예제로부터 생성되는 중간 규 칙은 이다. 이와 같은 방법을 통해 원본 장치와의 중간 규칙 집 합 와 대상 장치와의 중간 규칙 집합 를 생성한 다. 생성된 중간 규칙을 바탕으로 가상 ISA 기반의 변 환 규칙 생성을 수행한다. 이는 관계 대수(Relational Algebra)를 이용하여 표현할 수 있으며 다음과 같다. 먼저, 조인(Join, ) 연산을 이용하여 두 중간 규칙 을 하나로 병합한다. 여기서 사용된 조인 연산은 동등조 인(Equi Join)이며, 피연산자인 튜플(Tuple) 내부에 같 은 값을 갖는 속성 값을 기준으로 두 튜플을 병합한다. 위 표현식에서는 가 조건식으로 사용되었으며, 이에 따라 동일한 기능 라벨을 갖는 튜플끼리 병합된다. 그 결과, 아래와 같은 결과를 얻는다. 위 결과에 대해서 프로젝션(Projection, ) 연산을 수 행하여 두 행위에 대한 튜플을 도출한다. 프로젝션 연산 을 통해 세 가지의 속성 값 중에서 와 만을 추출 하면 원본 장치와 대상 장치에 대한 튜플을 얻어낼 수 있다. 따라서 변환 규칙 은 다음과 같다. 4. 직접 매핑 기반의 이진 변환을 위한 변환 규칙 생성 도구 그림 7 중간 규칙 테이블 형성 과정 Fig. 7 Construction process of intermediate rule table 본 논문에서는 가상 ISA 기반의 직접 매핑 방법을 통해 변환 규칙을 생성하는 도구를 구현한다. 또한 이 도구는 직접 매핑과 유사한 단계로 동작하도록 구성되 며, 그 구성은 그림 8과 같다. 직접 매핑은 총 세 단계를 통해 진행된다. 첫 번째 단 계는 이해 단계로, 변환 관계에 있는 두 장치의 특성을 파악하는 단계이다. 두 번째 단계는 탐색 단계이다. 탐 색 단계에서는 이해 단계에서 파악된 특성을 바탕으로 매핑을 수행한다. 세 번째 단계는 작성 단계로, 변환기를 생성한다. 각 단계를 수행하는 모듈의 이름은 각각 파서 (Parser), 매퍼(Mapper), 생성기(Generator)이다. 본 논
재목적성을 고려한 직접 매핑 기반의 이진 변환 규칙 생성 도구 509 그림 8 변환 규칙 생성 단계 Fig. 8 Phases of translation rule generation 문에서는 변환 규칙을 생성하는 단계까지 구현하였으며 생성기에 대한 내용은 언급하지 않는다. 따라서 이번 절에서는 이해 단계에서 사용되는 SLA과 이를 분석하는 파서, 그리고 탐색 단계의 매퍼 에 대해서 기술한다. 4.1 SLA(Specification Language for Automatic rule generation of inary translation) 이해 단계를 수행하기 위해서는 도구가 ISA 명세를 파악할 수 있어야 한다. SLA은 이와 같은 목적으로 정의되었으며, 명령어의 행위, 다루는 자료 유형, 이진 포맷 등을 표현할 수 있다. SLA은 ANTLR v4[14]를 이용하여 정의되었으며, SLA의 문법은 그림 9와 같다. 전체 문법 중 일부만을 첨부한다. SLA은 크게 프로세서 심볼 정의부와 명령어 정의 부로 나뉜다. 프로세서 심볼 정의부에는 프로세서에서 사용 하는 고유 레지스터를 기술하며, 8 번째 줄의 symbol 을 통해 심볼 입력을 시작한다, 명령어 정의부는 명령어 의 행위, 이진 포맷 등을 입력하는 부분이며, 예약어인 instruction 을 통해 시작된다. 이후에 명령어의 식별자 를 기술하며(28번째 줄), 명령어의 식별자는 문자열로 작성되는 Identifier와 이진수로 작성되는 itidentifier로 구성된다. 명령어의 행위와 관련된 문법은 62 번째 줄부 터 시작된다. 여기서 사용된 instructionehavior는 C 언어의 표현식을 참조하여 구성하였다. 그림 9의 문법을 통해 작성되는 문서의 구조는 그림 10과 같다. 그림 10을 보면 알 수 있듯이 명령어에 대한 기술은 크게 명령어의 행위와 명령어의 이진 포맷으로 나뉜다. 명령어의 행위는 그림 9의 instrucionehavior와 관련 된 부분이며, 이를 위해 제공하는 연산자는 표 1과 같 다. 연산자 외에도 사용가능한 자료 유형 역시 중요하 며, SLA에서 제공하는 자료 유형은 표 2와 같다. 표 1의 연산자는 총 21개이며, 이 중에서 대입 연산 자(=)를 제외한 20개의 연산자는 명령어의 행위를 표현 하는데 사용된다. 20개의 연산자는 통상적으로 명령어 단계의 행위를 표현하는데 필요한 것을 정리한 것이다. 그림 9 SLA 문법 Fig. 9 SLA grammar 그림 10 SLA 기반 명세의 구조 Fig. 10 Structure of SLA based specification 대입 연산자는 명령어의 자료 유형을 기술할 때 사용되 는 연산자이다. 표 2의 자료 유형은 명령어 추상 모델에 서 사용되는 자료 유형에 맞추어 정의된다. 또한 통상적 으로 명령어 단계에서 사용되는 자료 유형은 정수형 레 지스터, 실수형 레지스터, 명령어 내부에 포함되는 상수 이므로, 표 2의 자료 유형을 통해 명령어의 행위를 충분 히 기술할 수 있다.
510 정보과학회논문지 : 소프트웨어 및 응용 제 41 권 제 7 호(2014.7) Category Arithmetic Operations Logical Operations Comparison Operations Transfer Operation Assignment Operation Memory Operation 표 1 SLA에서 제공하는 연산자 Table 1 Supporting operators in SLA Operator + (Add), - (Sub), * (Multiply), / (Division), % (Modular) & (And), (Or), ~ (Not), ^ (Xor), << (Left Shift), >> (Right Shift) == (Equal),!= (Not Equal), < (Less Than), <== (Less or Equal), > (Greater Than), >==(Greater or Equal) <= (Transfer), @ (ranch) = (Type Assignment) [ ] (Memory Access) 표 2 SLA에서 제공하는 자료 유형 Table 2 Supporting data types in SLA Data Type Description uint<size> Unsigned integer register with <size> Available value of <size> is 8, 16, 32, 64 sint<size> Signed integer register with <size> Available value of <size> is 8, 16, 32, 64 float<size> Floating-point register with <size> Available value of <size> is 32, 64 Unsigned immediate value with <size> uimm<size> Available value range of <size> is 1 to 32 Signed immediate value with <size> simm<size> Available value range of <size> is 1 to 32 SLA에서는 이진 포맷을 기능 식별자와 자료 식별 자로 나누어 입력한다. 먼저, 기능 식별자는 그림 9의 itidentifier와 관련된 부분으로, 특정 명령어에 대해서 변하지 않는 부분을 의미한다. 기능 식별자를 입력할 때 에는 실제 비트 위치와 관계없이 하나의 이진수 형태로 입력한다. 경우에 따라 _ 를 통해 0과 1의 값을 모두 그림 12 SLA을 이용한 JMPL 명령어의 명세 Fig. 12 Specification of JMPL instruction using SLA 표현하기도 한다. 자료 식별자는 레지스터 번호, 상수, 메모리 주소 등과 같이 수행될 때마다 변경될 수 있는 부분을 의미한다. 자료 식별자의 입력은 표 1의 대입 연 산자(=)를 통해 이루어지며, 기능 식별자와 달리 정확한 비트 위치를 기입하여야 한다. 자세한 입력 방법은 예제 를 통해 설명한다. 그림 11은 제조사에서 제공하는 SPARC v7의 JMPL 명령어의 명세이며, 그림 12는 SLA을 통해 작성된 JMPL 명령어의 명세이다. SLA을 이용하여 명령어를 명세하기 위해서는 먼저 그림 11의 명세에서 사용되는 심볼을 찾아야 한다. SLA에서는 일반 레지스터 외에는 전부 특수 레지스 터로 판단하기 때문에, 프로그램 카운터(PC: Program Counter)를 심볼로 입력한다. 이후에 명령어에 대한 기 술을 시작한다. 기능 식별자는 이진 포맷 중 변경되지 않는 일련의 비트이다. 이때, 비트의 실제 위치는 무시 그림 11 JMPL 명령어의 명세 [15] Fig. 11 Specification of JMPL instruction
재목적성을 고려한 직접 매핑 기반의 이진 변환 규칙 생성 도구 511 하고 상대적인 위치만 유지한다. 따라서 JMPL 명령어 의 기능 식별자는 10111000_ 가 된다. _ 는 0과 1 모 두 올 수 있는 것으로, 그림 11의 i 비트를 표기한 것이 다. i 비트는 두 번째 피연산자의 자료 유형을 결정하는 비트로, 기능 식별자에서는 _ 로 표시한 뒤 selection 구문을 이용하여 추가적인 정보를 입력한다. 명령어의 행위는 명령어가 수행하는 기능에 의거하여 SLA의 연산자를 통해 표현한다. JMPL는 특정 레지스터에 현 재의 위치를 저장한 뒤 src1 + src2 의 주소로 이동하 는 연산자이므로, Transfer 연산자와 ranch 연산자를 이용하여 이를 표현한다. 행위를 입력하는 과정에서 레 지스터의 식별자는 임의의 문자열 식별자로 표기하되, 각 식별자의 자료 유형과 자료 식별자도 함께 표기한다. 이러한 과정을 통해서 SLA을 통해 명령어를 명세할 수 있다. 4.2 매퍼 매퍼는 주로 가상 ISA의 명령어와 원본 혹은 대상 장치의 명령어 사이의 변환 규칙을 생성하는 역할을 수 행한다. 매퍼는 3.2.2절에서 제시된 그림 5의 알고리즘을 바탕으로 구현되었으며, 그림 13과 같은 방식으로 동작 한다. 1 원본 장치와 대상 장치의 ISA를 SLA을 통해 기술한다. 2 기술된 SLA 명세로부터 파서가 추상화된 ISA, 즉 명령어 추상 모델을 도출한다. 3 가상 ISA와 원본 장치의 명령어 추상 모델과의 비교 를 수행한다. 4 수행 결과는 해시 테이블에 저장되며, 이때 해시 테이블 의 키 값은 가상 ISA의 명령어가 갖는 기능 라벨이다. 5 가상 ISA와 대상 장치의 명령어 추상 모델과의 비교 를 수행한다. 6 수행 결과를 해시 테이블에 저장한다. 이때 사용되는 해시 테이블은 4의 해시 테이블과 같다. 7 해시 테이블의 저장 결과를 토대로 변환 규칙을 생 성한다. 같은 키 값을 갖는 요소를 엮어 변환 규칙을 생성한다. 이해를 돕기 위해 4.1절에서 예제로 사용하였던 SPARC v7의 JMPL 명령어에 대해서 변환 규칙을 생성하는 과 정을 설명한다. 이 과정에서 해시 테이블이 어떻게 형성 되고, 그로부터 어떻게 변환 규칙을 생성할 수 있는지 설명한다. 먼저, 그림 12의 JMPL 명령어는 그림 14와 같은 형 태로 명령어 추상 모델이 형성된다. 실제 JMPL 명령어 의 명령어 추상 모델은 두 가지가 도출되지만, 설명의 편의를 위해 그림 14의 명령어 추상 모델만을 사용한다. 또한 JMPL 명령어와 매핑될 수 있는 가상 ISA의 명령어 는 세 개의 행위를 가지며, 각각은 그림 15 와 같은 형태의 명령어 추상 모델이 형성된다. 3.2.2절의 그림 5 알고리즘에 의해서 JMPL과 사 이에 중간 규칙이 생성되며, 이는 해시 테이블에 삽입된 다. 대상 장치에 해당하는 TI(Texas Instruments)는 그림 13 매퍼의 동작 과정 Fig. 13 Operation process of Mapper
512 정보과학회논문지 : 소프트웨어 및 응용 제 41 권 제 7 호(2014.7) 그림 14 JMPL 명령어의 명령어 추상 모델 Fig. 14 Instruction abstract model of JMPL instruction 그림 16 MV와 명령어의 명령어 추상 모델 Fig. 16 Instruction abstract model of MV and instructions SPARC v7의 JMPL 명령어는 TI의 MV와 명령어로 변환될 수 있음을 의미한다. 5. 변환 규칙 생성 결과 그림 15 JMP의 행위 Fig. 15 ehavior of JMP JMP 명령어를 따로 가지고 있지 않다. 이러한 이유로 그림 16에 표현된 MV와 명령어를 이용하여 JMP 명 령어를 대체하여야 한다. 그림 16의 명령어는 그림 15의 와 동일한 명령어 추상 모델을 가지며, 따라서 TI는 JMP 명령어에 대해서 그림 15의 와 중간 규칙을 생성 한다. 그림 16의 명령어 역시 해시 테이블에 삽입된다. 최종적으로 해시 테이블에 대해 JMP 를 키로 넘겨 주면 를 반환하며, 이를 하나로 엮으면 변환 규칙 가 다음과 같이 생성된다. 아래 표현은 이번 절에서는 4절에서 제시한 변환 규칙 생성 도구 의 실행 결과를 보인다. 본 논문에서는 SPARC v7, TI DSP TMS320C67x/C67x+ 그리고 ARM v5의 명령어 에 대한 변환 규칙을 생성한다. 변환 규칙 생성 결과는 표 3과 같으며, 분량 관계 상 일부 명령어에 대한 변환 규칙을 담는다. 표 3의 변환 규칙은 가상 ISA와 각 프로세서의 명령 어 사이의 관계를 나타내며, 이를 바탕으로 임의의 두 프로세서 사이의 변환 규칙을 생성할 수 있다. 표 3의 변환 규칙에서 SRI(Subroutine in)는 서브루틴에 들어 갈 때 수행하는 명령어이며, SRO(Subroutine out)는 서브루틴에서 나올 때 수행하는 명령어를 의미한다. 이 는 아키텍처마다 각기 특성을 갖기 때문에, 별도의 기능 라벨을 정의하였다. 또한 조건에 따라 분기하는 명령어 에 대해서 비교 연산과 병합된 형태로 구성하였는데, 이 는 아키텍처에 따라 비교 연산을 통해 조건이 표현되는 경우와 분기 명령을 통해 조건이 표현되는 경우로 나뉘 기 때문에 이를 통상적인 방법으로 표현하기 위해 위와 같은 형태를 갖도록 하였다. 변환 규칙을 생성할 때, 사 용된 가상 ISA 명령어의 일부는 표 4와 같다. 명령어 추상 모델은 트리 형태로 구성되기 때문에, 표 4에서는 트리를 작성하기 편한 형태로 구성하였다. 괄호 안에는 자식 노드가 작성되고, 괄호 앞에 부모 노 드가 작성된다. 자식 노드 사이의 구분은 쉼표(,)를 통 해 이루어진다. JMP의, 의 경우에는 루트 노드가 괄호로만 표시되어 있는데, 이는 두 개의 기능이 하나 의 명령어에서 모두 수행됨을 표현한 것이다. 다시 말 해, JMP의, 는 하나의 명령어 추상 모델로 표현 된 것이며, JMP의 는 두 개의 명령어 추상 모델로 표현된 것이다. 표 4에 따라 표 3의 ADDD와 관련
재목적성을 고려한 직접 매핑 기반의 이진 변환 규칙 생성 도구 513 표 3 명령어 변환 규칙 Table 3 Instruction translation rules fl SPARC v7 TI ARM v5 ADD ADD ADDA ADD ADDH ADD ADDAH ADD ADDW ADD ADD ADD ADDD ADDcc ADD ADDAD ADDX ADC SU SU SUA SU SUH SU SUAH SU SUW SU SU SU SUD SUcc SU SUAD SUX SC MULW MULScc MPYI MUL AND AND AND AND OR OR OR ORR XOR XOR XOR EOR ASL SLL SHL MOV ASR SRA SHR MOV LSL SLL SHL MOV LSR SRL SHRU MOV LDW LD LDW NOP LDR LDD LDD LDDW NOP LDRD STW ST STW NOP STR STD STD STW STW STRD NOP CMPEQ SUcc CMPEQ CMP CMPLE SUcc CMPGT NOT CMP CMPLT SUcc CMPLT CMP CMPGE SUcc CMPLT NOT CMP CMPGT SUcc CMPGT CMP CMPNEQ SUcc CMPEQ NOT CMP A EQ SUcc CMPEQ CMP E EQ LE CMPGT SUcc CMP NOT LE LE LT SUcc CMPLT CMP L LT GE CMPLT SUcc CMP NOT GE GE GT SUcc CMPGT CMP G GT NEQ CMPEQ SUcc CMP NOT NE NE CALL CALL MV L JMP JMPL MV L MV MOV MOV MOV SRI SAVE SU PUSH ADD SRO RESTORE ADD SU JMPL POP fl ADD 표 4 가상 ISA 명령어 예제 Table 4 Example of virtual ISA instructions id 1 2 1 2 Instruction Abstract Model transfer(sint8, add(sint8, sint8)) transfer(sint32, add(sint32, sint32)) ADDH transfer(sint16, add(sint16, sint16)) transfer(sint32, add(sint32, sint32)) ADDW 1 transfer(sint32, add(sint32, sint32)) ADDD JMP 1 2 1 2 3 transfer(sint64, add(sint64, sint64)) transfer(sint32, add(sint32, sint32)) transfer(sint32, add(sint32, sint32, c)) (transfer(sint32, sint32), branch(sint32)) (transfer(sint32, sint32), branch(add(sint32, sint32)) transfer(sint32, sint32) branch(sint32) 있는 명령어는 각각,, 에 의해 규칙이 생성되 었음을 알 수 있다. 본 논문에서는 생성된 변환 규칙이 정확한지 확인하 기 위해 SPARC v7 기반의 이진 코드를 변환 규칙에 따라 변환한 뒤, 변환된 코드를 수행한다. 실행된 두 코 드의 결과를 비교하여 변환의 정확성을 검증한다. 검증 을 위해 사용된 코드는 버블정렬(ubble Sort) 알고리 즘과 팩토리얼(Factorial) 알고리즘을 통해 작성된 코드 이다. 두 코드는 산술 연산과 분기 제어에 대한 명령어 가 모두 포함되기 때문에, 변환의 정확성에 대한 검증을 위한 적합한 코드이다. 실험에서 사용된 명령어의 변환 규칙은 표 3과 같으며, 레지스터의 변환 규칙은 표 4와 같다. 레지스터 변환 규칙은 본 논문의 연구 범위는 아 니지만, 코드를 변환하여 실행하기 위해서는 이 역시 반 드시 필요한 요소이다. 본 논문에서는 실험을 위해 레지 스터 변환 방법 중 하나인 일대일 매핑 기법을 사용한 다. 이 방법은 원본 장치의 레지스터 하나를 대상 장치 의 특정 레지스터 하나와 연결하는 방법이며, 이를 통해 표 5와 같은 레지스터 변환 규칙을 생성하였으며 이는 예제에서 사용된 레지스터에 한정하여 생성된다. 표 5의 변환 규칙 중 일대일 매핑이 성립되는 않는 것이 존재하는 것을 볼 수 있다. 첫 번째로 SPARC v7 의 %i0과 %o0이다. 이는 서브루틴을 호출할 때 사용되 는 레지스터로, 서브루틴을 호출한 쪽에서는 %o0 레지 스터로 값에 접근하고 서브루틴 내부에서는 %i0 레지스 터를 이용하여 값에 접근한다. 즉, 같은 값을 다루지만 사용되는 위치가 다른 레지스터이다. SPARC v7를 제 외한 나머지 장치에서는 이와 같은 레지스터가 존재하 지 않기 때문에, 본 논문에서는 %i0와 %o0 레지스터
514 정보과학회논문지 : 소프트웨어 및 응용 제 41 권 제 7 호(2014.7) 표 5 레지스터 변환 규칙 Table 5 Register translation rules SPARC v7 TI ARM v5 %g0 A2 R0 %g1 A3 R3 %g2 A4 R4 %g3 A5 R5 %g4 A6 R6 %i0 / %o0 3 R8 %fp R11 SP %sp SP 를 하나의 레지스터로 간주하였다. 두 번째로 TI의 SP 이다. SPARC v7과 ARM v5에서는 스택 포인터(SP: Stack pointer)와 프레임 포인터(FP: Frame pointer)가 각기 존재한다. 하지만 TI에서는 프레임 포인터가 따로 존재하지 않고 스택 포인터를 활용한다. 따라서 표 5와 같은 변환 규칙을 갖도록 하였다. 5.1 팩토리얼 알고리즘 본 논문에서 사용된 팩토리얼 알고리즘은 그림 17의 내용과 같으며, 실제 결과를 알아보기 위해 5!에 대한 값을 계산하도록 작성하였다. 그림 17의 코드를 컴파일 하여 얻은 SPARC v7 명령어 기반의 이진 코드는 그림 18(a)와 같다. 그림 17 팩토리얼 알고리즘 코드 Fig. 17 Factorial algorithm code 표 3과 4의 변환 규칙을 바탕으로 생성된 ARM v5와 TI를 위한 이진 코드는 각각 그림 18(b), (c)와 같다. 그 림 18(a)의 이진 코드의 실행을 통해 도출되는 결과는 120이며, 그림 18(b), (c)에서도 동일한 결과가 도출되는 지 확인한다. 이를 확인하기 위해서는 레지스터의 값을 확인하여야 한다. 결과를 확인할 수 있는 부분은 그림 18(b)의 32번째 줄과 그림 18(c)의 52번째 줄로, 화살표 로 표시된 부분을 말한다. 각각은 그림. 17의 17번째 줄 에 해당하며, 팩토리얼 함수로부터 반환 값을 넘겨받는 그림 18 팩토리얼 알고리즘에 대한 이진 코드 Fig. 18 inary code for Factorial algorithm
재목적성을 고려한 직접 매핑 기반의 이진 변환 규칙 생성 도구 515 그림 19 팩토리얼 알고리즘 수행 결과 Fig. 19 Execution result for Factorial algorithm 부분에 해당한다. 해당 부분에 대한 레지스터 값은 그림 19 와 같으며, 모두 120의 값을 갖는 것을 알 수 있다. 5.2 버블정렬 알고리즘 본 논문에서 사용된 버블정렬 알고리즘은 그림 20의 내용과 같으며, 실제 결과를 알아보기 위해 {7, 4, 11, 9, 2} 에 대해 오름차순 정렬을 수행하도록 작성하였다. 그림 20 의 코드를 컴파일하여 얻은 SPARC v7 명령어 기반의 이진 코드는 그림 21(a)와 같다. 버블정렬 알고리즘을 통해 생성된 이진 코드는 팩토리얼에 비해 양이 많아 일부만을 첨부한다. 첨부된 이진코드는 그림 20의 11번 째 줄부터 16번째 줄까지의 내용이다. 표 3과 4의 변환 규칙을 바탕으로 생성된 ARM v5와 TI를 위한 이진 코드는 각각 그림 21(b), (c)와 같다. 그림 21(a)의 이진 코드의 실행을 통해 도출되는 결과 그림 20 버블정렬 알고리즘 코드 Fig. 20 ubble sort algorithm code 는 {2, 4, 7, 9, 11}이며, 그림 21(b), (c)에서도 동일한 결과가 도출되는지 확인한다. 이를 확인하기 위해서는 마찬가지로 레지스터의 값을 확인하여야 한다. 결과를 확인하기 위해서 별도의 코드가 필요하며, 각각은 그림 22 와 같다. 그림 22의 코드는 배열이 저장된 값을 하나씩 그림 21 버블정렬 알고리즘에 대한 이진 코드 Fig. 21 inary code for ubble sort algorithm
516 정보과학회논문지 : 소프트웨어 및 응용 제 41 권 제 7 호(2014.7) References 그림 22 실행 결과 확인을 위한 추가 코드 Fig. 22 Additional code for checking execution result 그림 23 버블정렬 알고리즘 수행 결과 Fig. 23 Execution result for ubble sort algorithm 불어오는 연산이며, 이를 통해서 해당 시점에 레지스터 값을 확인할 수 있다. 해당 시점에 대한 레지스터 값은 그림 23의 내용이 모두 같으며, 실행 화면은 배열의 내 용을 순차적으로 보인 결과이다. 즉, 1번 그림은 첫 번째 배열의 원소를 보여준다. 따라서 그림 23의 실행 결과 모두 {2, 4, 7, 9, 11}의 배열을 갖는 것을 알 수 있다. 실험을 통해 본 논문에서 제안한 방법을 통해 생성된 변환 규칙이 정상적으로 수행됨을 알 수 있다. 산술 연 산에 대한 한정적인 지원이 아닌 비교 연산, 논리 연산, 분기 연산에 대한 변환이 가능함을 알 수 있다. 또한 한 번 생성된 중간 규칙은 다른 중간 규칙과 병합되어 새 로운 변환 규칙을 생성할 수 있음을 확인할 수 있으며, 이는 곧 변환 규칙 생성에 소요되는 비용을 줄일 수 있 음을 의미한다. 6. 결 론 본 논문에서는 재목적성을 고려한 직접 매핑 기반의 변환 규칙 생성 방법을 제시하였다. 이 방법은 가상 ISA를 기반으로 직접 매핑을 통해 재목적성을 함께 달 성할 수 있다. 제안한 방법을 증명하기 위하여 도구를 구현하였으며, 이를 통해 변환 규칙을 생성할 수 있음을 그 실행 결과로 보여주었다. 본 논문은 명령어의 변환에 초점을 맞추어 진행되었다. 그러나 이진 변환에서는 명 령어의 변환 외에도 레지스터와 메모리 변환도 중요한 요소이다. 따라서 추후에 레지스터와 메모리 변환에 대 한 연구를 진행할 예정이다. [1] M. Probst, "Dynamic inary Translation," Proc. of the UKUUG Linux Developers Conference, ristol, United Kingdom, Jul. 2002. [2] V. arrio, "Study of the techniques for emulation programming," 2001. [3] J. Choi, Y. Cheon, "Development of Prototype Hypervisor for ERC32 using DT Engine for LEON3," Proc. of the KSAS Fall Conference, pp. 699-705, 2013. [4] M. Souza, D. Nicacio, G. Araujo, "ISAMAP: Instruction Mapping Driven by Dynamic inary Translation," 3rd Workshop on Architectural and Microarchitectural Support for inary Translation, 2010. [5] L. Michel, N. Fournel, F. Petrot, "Fast Simulation of Systems Embedding VLIW Processors," In Proc. of the 10th IEEE/ACM Int l Conf. on Hardware/ Software Codesign and System Synthesis, 2012. [6] D. Ung, C. Cifuentes, "Machine-Adaptable Dynamic inary Translation," IEICE Trans. Fundamentals, vol.e79-a, no.9, pp.1338-1353, Sep., 1996. [7] C. Cifuentes,. Lewis, D. Ung, "Walkabout : A Retargetable Dynamic inary Translation," IEICE Trans. Fundamentals, vol.e79-a, no.9, pp.1338-1353, 1996. [8] Y. Yang, H. Guan, E. Zhu, H. Yang,. Liu, "Crossit : A Multi-Sources and Multi-Targets DT," 1st Int l Conf. on Cloud Computing, GRIDs, and Virtualization, pp.41-47, 2010. [9] D. Hong, C. Hsu, P. Yew, J. Wu, W. Hsu, P. Liu, C. Wang, Y. Chung, "HQEMU: A Multi-Threaded and Retargetable Dynamic inary Translator on Multicores," In CGO 12: Proc. of the 10th annual IEEE/ACM int l symposium on Code generation and optimization, 2012. [10] M. Choi, S. Lim, "x86-android performance improvement for x86 smart mobile devices," Concurrency and Computation: Practice and Experience, doi: 10.1002/cpe.3189, 2014. [11] X. Liu, J. Pang, M. Yin, L. ai, W. Chen, "MSI- SDL : A Semantic Description Language for Multisource inary Translation Systems," The 8th Int l Conf. on Computer Science & Education, 2013. [12] J. Lee, Y. Seo, H. Kim, D. Mun, "Automatic Generation of inary Code Translation Rule for Embedded System," Proc. of the 40th KIISE Fall Conference, pp.498-500, 2013. [13] C. Codere, The Virtual Instruction Set (VIS) [Online]. Available: http://www.optimasc.com/pro ducts/vis/fvis.pdf (downloaded 2014, April 20) [14] ANTLR v4 [Internet], http://www.antlr.org (downloaded 2014, April 10) [15] SPARC v7 [Internet], http://aerosupport.atmel.co m/atmel/doc4168.pdf (downloaded 2014, April 20)
재목적성을 고려한 직접 매핑 기반의 이진 변환 규칙 생성 도구 517 서 용 진 정보과학회논문지 : 소프트웨어 및 응용 제 41 권 제 1 호 참조 김 현 수 정보과학회논문지 : 소프트웨어 및 응용 제 41 권 제 1 호 참조