디지털 라이브러리[ 검색결과 ]
C와 유사한 언어에서 정수-포인터 변환 지원을 위한 메모리 모델 설계: 이중 비결정성을 사용하여
http://doi.org/10.5626/JOK.2024.51.7.643
시스템 프로그래밍에서 포인터는 매우 중요한 요소이며, 정수-포인터 변환(Integer-Pointer Casting)을 포함한 프로그램에 정형 검증을 적용하는 것은 중요한 과제이다. 정수-포인터 변환을 포함한 프로그램을 정형 검증하기 위해서는 정수-포인터 변환을 지원하는 수학적으로 정의된 메모리 모델과 검증 에 사용할 증명 방법이 필요하다. 우리는 Coq 증명 도구 안에서 정수-포인터 변환을 지원하는 메모리 모델을 정의했다. 이 모델은 끝에서 한 칸 벗어난 포인터(one-past-the-end pointer)를 포함한 정수-포인터 연산과 관련된 패턴을 제대로 지원한다. 또한 우리가 정의한 모델을 프로그램 검증에 사용할 수 있도록 시뮬레이션 기반 증명 방법론을 새로 정의하고 적합성(Adequacy)을 증명했다. 마지막으로 우리의 접근 방법 이 타당함을 확인하기 위해 검증된 C 컴파일러인 CompCert의 메모리 모델과 의미 구조를 우리가 정의한 것으로 변경한 후 시뮬레이션을 통해서 CompCert의 최적화 검증 증명 중 두 개를 업데이트했다. 우리는 이 메모리 모델이 컴파일러와 정수-포인터 연산을 포함하는 프로그램 검증에 적용되기를 기대하고 있다.
리스트 스케줄링 시뮬레이터를 이용한 인스트럭션 우선도 함수 성능 분석
http://doi.org/10.5626/JOK.2023.50.12.1048
인스트럭션 스케줄링은 병렬 처리를 통해 프로그램 실행 시간을 줄인다는 측면에서 중요한 컴파일러 최적화 기법이다. 그러나 아직까지도 대부분의 스케줄링 기법이 휴리스틱에 의존하기 때문에, 제한적인 성능만을 보여준다. 본 연구에서는 리스트 스케줄링(list scheduling)에서, 인스트럭션 우선도 함수(priority function)가 스케줄 길이에 미치는 영향을 시뮬레이션을 통해 알아본다. 결과적으로, 의존성 그래프(dependency graph)의 전체적인 구조를 반영하는 우선도 함수를 사용할 때, 기존 순서를 사용하는 우선도 함수에 비해 스케줄 길이가 약 4% 감소한다는 것을 확인할 수 있다. 해당 결과는 향후에 강화학습 기반의 스케줄링 모델을 구현할 때 사용해야 하는 입력 특성에 대한 방향성을 제시한다.
Processing-in-Memory를 위한 코드 생성 및 데이터 레이아웃 변형 기법
http://doi.org/10.5626/JOK.2023.50.8.639
Processing-in-Memory(PIM)은 메모리 내부의 병렬성과 대역폭을 활용하여 메모리 집약적인 연산에서 CPU 또는 GPU와 비교하여 좋은 성능을 달성한다. 그러나, 다양한 PIM 구조가 제안된 것에 비해 PIM 컴파일러에 대한 연구는 부족한 상황이다. 다양한 PIM의 구조를 고려하여 코드를 생성하기 위해서는 일반적인 PIM 스케줄 프리미티브와 PIM 메모리에 데이터를 저장하는 레이아웃을 고려해야 한다. 또한, PIM과 호스트 사이에 발생하는 데이터 이동을 최소화해야 한다. 본 논문에서 제안하는 PIM 컴파일러는 일반적인 PIM 구조를 정의하여 이러한 고려 사항을 해결하고, 추가로 레지스터 재사용 최적화를 통해 다양한 GEMV 연산에서 최대 2.49배 성능 개선을 달성한다.
4세대 CKKS 동형암호 틀을 지원하는 딥뉴럴넷 특화 동형암호 최적화 컴파일러 HedgeHog
이동권, 이계진, 김수찬, 송우성, 이도형, 김훈, 조승한, 박규연, 이광근
http://doi.org/10.5626/JOK.2022.49.9.743
우리는 기존보다 사용하기 쉬운 상위 입력언어를 사용하면서도 결과물 코드의 성능이 뛰어난 새로운 4세대 동형암호 최적화 컴파일러 HedgeHog를 개발하였다. 동형암호 기술은 그 유용성에도 불구하고 동형암호에 대한 전문지식이 없는 사용자의 입장에서는 직접 성능 좋은 동형암호 코드를 작성하는 것이 매우 어렵기 때문에, 상위 입력언어를 동형연산 코드로 자동변환해주는 동형 컴파일러 기술의 중요도는 매우 높다. 하지만 대부분의 기존 동형 컴파일러들은 4세대 이전의 동형암호 틀을 기반으로 하여 실수연산을 지원하지 못하기 때문에 뉴럴넷이나 통계분석 등의 분야에 쓰일 수는 없는 실정이다. 또한 4세대 동형암호 틀을 기반으로 하는 기존 동형 컴파일러들도 덧셈, 곱셈 등의 하위 연산자들을 기반으로 한 입력언어를 사용하고 있기에 뉴럴넷 모델 등의 상위 프로그램을 기술하기 어렵다는 단점이 있고, 이 과정에서 불필요한 연산자들이 사용되어 비효율적인 결과물 코드를 생성할 위험성이 높다. 우리는 이러한 문제를 해결하기 위해 뉴럴넷 핵심 상위 연산자를 포함하는 입력언어 코드를 동형연산 코드로 자동변환해주는 최적화 컴파일러 HedgeHog를 개발하였다. HedgeHog는 기존 최고수준 4세대 동형 컴파일러인 EVA에 비해 최대 22%의 성능향상을 보인다.
Equi-LR 오토마타
http://doi.org/10.5626/JOK.2021.48.3.352
LR 구문분석은 대표적인 상향식 구문분석방법이며, LR 오토마타를 이용하여 구문분석을 수행한다. 본 논문에서는 보편적으로 사용되어 왔던 LR 오토마타의 LR 아이템에 대한 동치 클래스를 정의하고, 이를 사용한 Equi-LR 오토마타의 생성 방법을 제시한다. Equi-LR 오토마타의 상태는 새롭게 정의된 동치클래스를 아이템으로 사용하여 구성되기에, 보편적으로 사용되었던 기존 LR 오토마타에 비해서 Equi-LR 오토마타의 생성 시간이 줄어든다. 본 논문에서는 Equi-LR 오토마타와 기존 보편적 LR 오토마타의 생성시간 복잡도를 정형적으로 비교 분석한 결과를 제시한다. 또한 Equi-LR 오토마타를 이용하면 기존 보편적인 LR 오토마타상에서의 LR 파서 크기의 복잡도보다 더 엄격한 복잡도를 제시할 수 있음을 보인다.
LR 오토마타 생성 모듈을 공유하고 범용 프로그래밍언어로 명세를 작성하는 파서 생성 도구
http://doi.org/10.5626/JOK.2020.47.1.52
본 논문은 LR 파서를 쉽게 개발하기 위하여 두 가지 아이디어를 제안한다. 첫째, 오토마타 생성을 모듈화하여 새로운 프로그래밍 언어를 위한 파서 생성 도구를 쉽게 개발 할 수 있다. 둘째, 파서 명세를 일반 프로그래밍언어로 작성하도록 구성하여 이 언어 개발 환경에서 제공하는 구문 오류, 자동 완성, 타입 오류 검사 기능들을 이용하여 파서 명세의 오류를 바로잡을 수 있다. 이 연구에서 제안한 아이디어로 Python, Java, C++, Haskell로 파서를 작성할 수 있는 도구를 개발하였고, 실험을 통하여 위 두 가지 장점을 보였다.
64-bit 자바스크립트 적시 컴파일러를 위한 상수 값 생성 최적화
자바스크립트는 웹 페이지에서 HTML과 더불어 널리 사용되고 있다. 많은 자바스크립트 수행엔진들은 성능 향상을 위해 적시 컴파일러를 채택하고 있다. 최근에는 32-bit 뿐만 아니라 64-bit 마이크로프로세서가 탑재된 다양한 기기가 소개되고 있으며 이를 위한 적시 컴파일러도 개발되고 있다. 하지만 64-bit 적시 컴파일러는 아직 문제점이 많으며, 특히 메모리 주소와 값들이 64-bit을 사용하여 코드의 크기가 증가하는 문제점이 있다. 본 논문은 64-bit 환경에서 생성되는 코드, 특히 주소와 상수 값들이 더 많은 공간을 사용함을 보여주고, 적시 컴파일러가 64-bit 값들의 생성을 최적화하여 메모리 사용량을 줄이는 기법들을 제안한다. 이를 V8 자바스크립트 엔진에 적용하여, Octane과 SunSpider 벤치마크에서 생성되는 코드의 크기와 성능을 평가하였다. 성능은 각각 3.6%와 0.32% 향상되었으며, 코드 크기는 0.7%와 2.8% 감소하였다.
