-
GNN을 이용한 컴파일러 기원 문제 해결 방법
1. Introduction 프로그래머가 작성한 코드는 컴파일 과정을 거쳐 기계가 해석 가능한 코드로 변환됩니다. 이 때 동일한 소스 코드임에도 불구하고 컴파일러의 종류에 따라 최종 결과물인 실행 파일에는 차이가 있을 수 있습니다. 하지만 일반적으로 실행 파일로부터 컴파일러의 종류와 버전, 최적화 옵션 등을 알아맞추는 것은 다소 난이도가 있는 작업이고 특히 디버깅 심볼을 포함한 여러 메타 데이터가 제거된 실행 파일에서는 파일에 포함된 문자열 등을 활용할 수 없이 오로지 데이터 영역의 값만을 통해 컴파일러를 유추해야 합니다. 한편, 실행 파일로부터 컴파일러의...
-
Efficient Primal-Dual Algorithms for MapReduce
Efficient Primal-Dual Algorithms for MapReduce 1. Introduction MapReduce 라는 프로그래밍 프레임워크는 대용량의 데이터를 처리하는 데 있어서 높은 성능을 보여주고, Apache Hadoop과 같은 오픈 소스 구현체들을 통해서 실용적으로도 그 가치를 증명하였다. 이 글에서는 그래프 최적화 문제를 푸는 데 효과적인 방법 중 하나인 Primal-Dual Method를 MapReduce 프레임워크에서 적용하는 새로운 프레임워크를 소개하고, 이를 통해서 Densest Subgraph Problem의 Near-linear time algorithm을 얻고자 한다. 정확히는, 이 글에서는 $O(\frac{\log n}{\epsilon^2})$ 번의 MapReduce iteration을 통하여 Densest Subgraph problem의 $(1 + \epsilon)$ approximation을...
-
구글의 야심작 QUIC
목차 목차 서론 배경지식 TCP TCP의 구조 TCP의 특징 UDP UDP의 구조 UDP의 특징 OSI 7계층 SSL/TLS HTTP의 역사 HTTP/1.1 HTTP/2 HTTP/2 with push 구글의 야심작 QUIC 기존 프로토콜의 단점 QUIC이란 QUIC의 단점 추가적인 내용 정리 서론 최근 구글이 새로운 프로토콜을 만들었습니다 그리고 구글은 이를 적극적으로 활용하고 있습니다. 사진을 보면 구글을 들어갔을 때 빨간색으로 표시한 것처럼 프로토콜이 h3라고 표시되어 있습니다. 이는 HTTP/3의 약자이며 HTTP/3라고 불리는 QUIC을 한 번 알아봅시다. 배경지식 TCP 우리가 사용하는 인터넷은 전송할...
-
Bostan-Mori Algorithm
Table Of Contents Introduction Review of the Kitamasa’s Method Bostan-Mori Algorithm Optimization under the DFT Setting Review of DFT DFT Doubling Bostan-Mori Algorithm under the DFT Setting Benchmarking Introduction 안녕하세요, Aeren입니다! 주어진 commutative ring $R$과 어떤 positive integer $d$에 대하여 $\begin{align} a _ {i + d} = \sum _ {j = 0} ^ {d - 1} c _ j \cdot a _ {i + j} \end{align}$ 꼴의 recurrence relation으로 표현되는 sequence $a : \mathbb{Z} _...
-
알고리즘 문제 접근 과정 6
알고리즘 문제 접근 과정 6 이번 포스트에서도 ‘알고리즘 문제 접근 방법’ 시리즈에서 진행했듯이 특정 문제를 해결하기 위해 가장 낮은 단계의 접근에서부터 최종 해법까지 해결해나가는 과정을 작성합니다. 최대한 다양한 유형의 문제들을 다루어, 많은 문제 유형에서의 접근 방법에 대한 실마리를 드리는 역할을 하려 합니다. Exhibition - JOI 2019 2번 주어진 문제가 영문이기 때문에 번역을 하여 문제를 첨부하겠습니다. 문제 알고박물관에서는 새해를 맞이해 여러 작품들을 특별 전시하려 합니다. 이번 특별 전시는 매우 귀한 작품들을 가지고 전시할 것이기 때문에, 전시하는...