-
CUDA를 이용한 행렬 곱셈
Introduction 행렬 곱셈은 병렬 프로그래밍에서 가장 중요한 연산 중 하나입니다. 행렬 곱셈은 컴퓨터 그래픽스, 인공 신경망 등 다양한 분야에서 기본적인 연산으로 사용되며, 사용하는 메모리에 비해 연산의 수가 많아 병렬화하기에 적합하기 때문입니다. GPU는 이러한 병렬 연산에 특화된 하드웨어입니다. GPU에는 단순한 연산 수천 개를 동시에 수행하도록 많은 연산 장치가 있으며 CPU의 cache 구조와 비슷하게 각 계층에서 공유되는 메모리가 있습니다. 행렬 곱셈을 위한 cuBLAS와 같은 라이브러리가 있으며, 이 글에서 소개할 내용은 해당 라이브러리를 구현하는 데 사용된 테크닉의 일부입니다....
-
read, write, mmap을 이용한 Fast I/O 구현 (2)
이번 글에서는 이전 글인 read, write, mmap을 이용한 Fast I/O 구현 (1)에 이어 Bit-Twiddling Hack을 적용한 더 빠른 입력 기법과 Lookup Table 및 SIMD를 활용한 출력 기법을 살펴보겠습니다. 1. Faster Input Implementation read 또는 mmap을 이용한 빠른 입력 방식은 입력 버퍼를 두고 버퍼 단위로 한 번에 입력을 읽어오며 입력 속도를 향상시킵니다. 대부분의 문제에서는 이 정도 최적화만으로 충분하지만, 한 번에 여러 문자를 처리할 수 있다면 입력 속도를 더욱 높일 수 있습니다. 1.1 8-Byte Parsing 앞서 소개한...
-
read, write, mmap을 이용한 Fast I/O 구현 (1)
1. Introduction 입출력 연산은 C++에서 가장 무거운 연산 중 하나입니다. 일반적인 산술 및 논리 연산은 대략 $1$초에 $1$억 번 정도 수행할 수 있는 것으로 알려져 있지만, 입출력 연산은 입력 또는 출력 값의 개수가 $10^5$ 이상만 되어도 입출력 속도가 전체 실행 시간에 상당한 영향을 줄 수 있습니다. (참고) 이럴 때 표준 스트림 함수인 cin, cout 대신 read, write와 같은 저수준 입출력 함수를 사용하면 입출력 시간을 유의미하게 줄일 수 있습니다. 다만 이 함수들은 문자열 이외의 자료형을 자동으로...
-
cracking mysql_hash_password
Intro 안녕하세요, kwoncycle입니다. 이번 글에서는 mysql_hash_password 라는 해시 함수를 crack하는 방법에 대해 다룹니다. mysql_hash_password 함수는 2000년 이전에 MySQL에서 사용된 비밀번호 해시 함수로, 해시 로직은 아래의 코드와 같습니다. def mysql_hash_password(password): nr = 1345345333 add = 7 nr2 = 0x12345671 for c in password: if c == 32 or c == 9: continue nr ^= (((nr & 63) + add) * c) + (nr << 8) & 0xFFFFFFFF nr2 = (nr2 + ((nr2 << 8) ^ nr))...
-
TFHE : Fully Homomorphic Encryption over the Torus - 2
Introduction 안녕하세요. 지난 게시글에서는 동형암호 scheme중 하나인 TFHE의 암호화 / 복호화 / 덧셈 연산에 대해서 다루었습니다. 그리고 다음 게시글에서는 TFHE의 곱셈에 대해 다루기 위해서 GSW scheme과 gadget decomposition을 다루었는데요, 이 글의 이해를 위해서는 두 게시글을 읽고 오시길 추천드립니다! 이번 글에서는 TFHE에서의 곱셈(external product)가 어떻게 진행되는지와, 그리고 이러한 연산을 통해서 최종적으로 TFHE의 bootstrapping이 어떤 식으로 진행되는지에 대한 개괄적 설명을 하고자 합니다! TFHE Multiplication(External Product) Gadget Decomposition Gadget decomposition을 처음 접하시는 분은 이 글 의 설명을 읽으신다면...