CS

[이종병렬컴퓨팅] Accelerators for Deep Learning

이 글은 포스텍 성효진 교수님의 이종병렬컴퓨팅(CSED490C) 강의를 기반으로 재구성한 것입니다. 이 글에서는 deep learning을 위한 가속의 motivation, domain-specific accelerator의 기본, efficiency metric 그리고 4가지 case study(Google TPU, GraphCore, DianNao series, Reconfigurable accerlerator)를 살펴본다. heterogeneity의 Motivation single core CPU의 경우 moore의 법칙/dennard의 scaling이 거의 끝이 났을 정도로 발전이 끝에 다다랐다. 때문에 performance와 watt를 향상시키기 위해 single core CPU를 넘어, mul..

[이종병렬컴퓨팅] Heterogeneous Parallel Computer를 위한 기술 스택

이 글은 포스텍 성효진 교수님의 이종병렬컴퓨팅(CSED490C) 강의를 기반으로 재구성한 것입니다. 이 글에서는 이종 시스템을 위한 고수준 프로그래밍을 가능하게 하는 software stack에 대해 설명한다. compiler-based, library-based, framework-based로 나눠 설명하고, OpenCL에 대한 compile/runtime 지원을 살펴본다. Compiler란? compiler는 source code를 기계어로 번역하는 일을 한다. source code는 high level abstraction, low level detail을 숨긴다. 떄문에 알고리즘에 대한 이해가 쉽고, fine-grained performance tuning이 제한된다. 기계어는 코드를 짜고 유지보..

[이종병렬컴퓨팅] OpenMP

이 글은 포스텍 성효진 교수님의 이종병렬컴퓨팅(CSED490C) 강의를 기반으로 재구성한 것입니다. 이 글에서는 OpenMP 프로그래밍 모델의 기본 개념과 pragma, 간단한 예제들을 살펴본다. OpenMP OpenMP API는 pragma(컴파일러 지시문), library routine, 환경변수 등을 제공한다. 이를 통해 multithread parallel fortran이나 C/C++ 프로그램을 쓸 수 있다. programmability와 portability를 위한 high-level parallel structure를 제공한다. 때문에 low-level thread를 조작하는 것보다 parallel program을 쓰고 유지하는 것이 더 쉽다. SMP 관행을 표준화하며, vectorizatio..

[이종병렬컴퓨팅] Parallel Patterns : Sparse Computation

이 글은 포스텍 성효진 교수님의 이종병렬컴퓨팅(CSED490C) 강의를 기반으로 재구성한 것입니다. 이 글에서는 memory bandwidth를 절감가힉 위한 parallel sparse computation에서 input data를 압축하는 방법을 살펴본다. 이를 통해 memory의 utilization을 높일 수 있고, on-chip memory로 전송되는 data 크기를 줄일 수 있다. 또한 clamping으로 variation 제한, sorting, transposition 등으로 불규칙한 데이터를 규칙적으로 만드는 방법을 살핀다. Sparse Matrix 자연 상태의 많은 system들은 sparse하다. 보통 matrix의 80% 이상이 0이면 sparse matrix라고 한다. Sparse ..

[이종병렬컴퓨팅] Parallel Patterns : Scan

이 글은 포스텍 성효진 교수님의 이종병렬컴퓨팅(CSED490C) 강의를 기반으로 재구성한 것입니다. 이 글에서는 parallel scan (prefix sum)과 koggle-stone algorithm(work-inefficient)와 brent-kung(work-efficient) algorithm을 살펴본다. Scan Inclusive Scan 어떤 binary associative operator ⊕와 array [x$_0$, x$_1$, ... , x$_{n-1}$]에 대해, [x$_0$, x$_0$ ⊕ x$_1$, ... , (x$_0$ ⊕ x$_1$ ⊕ ... ⊕ x$_{n-1}$]을 리턴하는 것이 inclusive scan이다. scan은 radix sort, quick sort, 등등 다..

[이종병렬컴퓨팅] Parallel Patterns : Reduction

이 글은 포스텍 성효진 교수님의 이종병렬컴퓨팅(CSED490C) 강의를 기반으로 재구성한 것입니다. 이 글에서는 parallel reduction pattern을 살펴본다. parallel reduction pattern은 제일 많이 사용되는 패턴 중 하나이다. 추가로, control divergence와 thread utilization 등의 작업 효율성, shared memory bank conflict 등의 resource 효율성을 살펴본다. Reduction Reduction은 input value를 하나의 값으로 요약하는 연산이다. 예를 들어 max(), min(), sum() 등등이 있다. 기본적으로 associative(결합), commutative(교환)여야 하며, 잘 정의된 identit..

[이종병렬컴퓨팅] Parallel Patterns : Histogram

이 글은 포스텍 성효진 교수님의 이종병렬컴퓨팅(CSED490C) 강의를 기반으로 재구성한 것입니다. 이 글에서는 다음과 같은 내용들을 살펴본다. parallel한 histogram 계산 패턴 privatization Histogram histogram은 큰 data set에서 특징과 패턴을 추출하는 방법으로, 기본적으로는 dataset의 각 bin 요소에 대해 count를 증가하는 방법이다. 제일 기본적인 병렬 알고리즘은 아래와 같다. input을 section으로 나누기 각 thread는 하나의 section을 담당한다. 각 thread는 section에서 순회한다. 각 letter에 대해 bin counter를 증가시킨다. 효율적인 memory 접근을 위한 partitioning 방법 section을..

[이종병렬컴퓨팅] Parallel Patterns : Convolution

이 글은 포스텍 성효진 교수님의 이종병렬컴퓨팅(CSED490C) 강의를 기반으로 재구성한 것입니다. 이 글에서는 다음과 같은 내용을 다룬다. convolution과 tiled convolution : 1D/2D convolution과 tiled convolution (input tiling, output tiling) 2D convolution kernel을 작성하는 방법 : boundary condition 처리 tiled parallel convolution 알고리즘의 cost와 장점 Convolution 인접한 input data element의 weighted sum 연산. 이 때 weighted sum 연산에 사용하는 weight를 input mask array 또는 convolution ker..

[이종병렬컴퓨팅] Performance Considerations

이 글은 포스텍 성효진 교수님의 이종병렬컴퓨팅(CSED490C) 강의를 기반으로 재구성한 것입니다. 이 글에서는 GPU resource의 제약과, 이들이 성능에 미치는 영향을 알아본다. 최적화 목표 memory coalescing shared memory bank 충돌 점유율 thread granularity 최적화 목표 Performance 고려 사항 parallel한 코드와 hardware resource의 제약, 이 두가지를 관리하는 것이 고성능의 핵심이다. 그러나 먼저, 어디서 제일 많은 시간이 걸리는지 측정해야 한다. Amdahl의 법칙을 생각해야 한다. coarse grained한 부분부터 측정하고, 이후에 fine grained한 부분을 측정하면 된다. 다음으로 main resource의 병..

[이종병렬컴퓨팅] Thread Execution Efficiency

이 글은 포스텍 성효진 교수님의 이종병렬컴퓨팅(CSED490C) 강의를 기반으로 재구성한 것입니다. 이 글에서는 다음과 같은 내용들을 살핀다. SIMD hardware에서 GPU thread가 실행되는 방식 : warp partitioning, control divergence control divergence가 성능에 미치는 영향을 분석하는 방법 : boundary condition checking GPU thread execution을 겹치는 방법 : CUDA stream GPU의 synchronization primitive 동작 : warp synchronization, atomics SIMD hardware에서 GPU thread가 실행되는 방식 Scheduling Thread Blocks ha..

[이종병렬컴퓨팅] Memory와 Data Locality - Tiled Multiplication & Unified Memory

이 글은 포스텍 성효진 교수님의 이종병렬컴퓨팅(CSED490C) 강의를 기반으로 재구성한 것입니다. 이 글에서는 다음과 같은 내용들을 살핀다. CUDA memory를 효율적으로 사용하는 방법 memory access 효율이 performance에 미치는 영향 다양한 memory의 수명 tiled parallel algorithm matrix multiplication - tiled multiplication kernel unified memory Introduction Matrix Multiplication __global__ void MatrixMulKernel(float* M, float* N, float* P, int Width) { // Calculate the row index of the P ..

[이종병렬컴퓨팅] CUDA Basics

이 글은 포스텍 성효진 교수님의 이종병렬컴퓨팅(CSED490C) 강의를 기반으로 재구성한 것입니다. 이 글에서는 CUDA programming language를 사용하는 방법을 알아본다. CUDA CUDA는 NVIDIA GPU 전용 software이다. 기본적으로는 C/C++이며 여기에 몇몇 library를 추가해서 쓸 수 있다. CUDA kernel을 사용하고 실행하는 방법 GPU memory를 관리하는 방법 communication과 synchronization을 관리하는 방법 Host와 Device host memory : CPU의 memory device memory : GPU의 memory heterogeneous computing은 serialize한 부분과 parallel한 부분이 나뉜다. ..

[이종병렬컴퓨팅] GPU architectures - NVIDIA

이 글은 포스텍 성효진 교수님의 이종병렬컴퓨팅(CSED490C) 강의를 기반으로 재구성한 것입니다. 이 글에서는 다음과 같은 내용들을 살핀다. GPU architecture의 예시 - NVIDIA NVIDIA GPU Architecture 용어 정리 NVIDIA AMD 뜻 kernel kernel GPU의 multiple thread에 의해 동작하는 함수. CPU와 parallel하게 동작할 수 있다. thread block work group 다른 data에 대해 같은 kernel을 실행하는 thread의 그룹. 단일 SM/CU에서 warp의 그룹으로 실행된다. 내부의 thread끼리는 communicate할 수 있는데 이는 hardward에 의해 지원된다. thread work item / threa..

[이종병렬컴퓨팅] GPU architectures - SIMT와 SIMD

이 글은 포스텍 성효진 교수님의 이종병렬컴퓨팅(CSED490C) 강의를 기반으로 재구성한 것입니다. 이 글에서는 다음과 같은 내용들을 살핀다. GPU의 실행 모델인 SIMT와 SIMD Heterogeneous Computing 순서가 있는 instruction은 CPU에, parallel하게 돌릴 수 있는 instruction은 GPU에 할당해서 돌리는 것이 heterogeneous computing이다. GPU Architecture의 개요 CPU vs GPU CPU는 하나의 thread에서 발생하는 latency를 최소화하는 데 목적이 있으며, 때문에 cache가 매우 크다. 따라서 일반적으로 core의 개수가 적으며, 여러 종류의 instruction을 수행할 수 있는 general한 목적이다. G..

[이종병렬컴퓨팅] Parallel Computing Basics

이 글은 포스텍 성효진 교수님의 이종병렬컴퓨팅(CSED490C) 강의를 기반으로 재구성한 것입니다. 이 글에서는 다음과 같은 내용을 살핀다. parallel computing의 기본적인 개념 parallelism의 종류 parallel architecture 분류 parallel program을 어떻게 작성하고 어떤 기준으로 평가하는지 Parallelism의 종류 크게 3가지의 parallelism이 있다. ILP, Instruction Level Parallelism instruction들끼리 independent하다. hardware는 instruction window size 내내에서 implicit하게 찾을 수 있다. complier들은 window 내에 있는 명령어들이 independent할 수..

DB 기초 - 2

이 글은 포스텍 한욱신 교수님의 데이터베이스시스템(CSED421) 강의를 기반으로 재구성한 것입니다. Key 다음 4종류가 있다. Candidate Key : tuple을 unique하게 식별할 수 있는 attribute set. + minimality : attribute 1개를 지우면 식별할 수 없다. Super Key : key의 super set Primary Key : candidate key 중 지정된 것. Foreign Key : 다른 relation을 참조하기 위해 다른 relation의 key를 가져온 것. dangling을 알아서 처리해 준다. Normal Form / Normalization [1NF - 2NF - 3NF - BCNF - 4NF - 5NF] 순서로 더 higher하다...

DB 기초 - 1

이 글은 포스텍 한욱신 교수님의 데이터베이스시스템(CSED421) 강의를 기반으로 재구성한 것입니다. DBMS의 정의 DBMS란 database를 관리/유지시켜주는 소프트웨어이다. 사용 이유는 data independency와 효율적 접근, 보안, 동시 접근을 위해서이다. file system에 비해서 cost는 크지만 redundancy가 없고, constraint를 유지할 수 있다는 장점이 있다.   Transction & ACIDtransaction : DBMS의 상호작용 단위. transaction은 다음 4가지 성질을 가지고 있다.Atomicity : transction은 실행되거나, 실행되지 않거나 둘 중 하나의 상태만 가진다. 중간에 끊기지 않는다.Consistency : transactio..

[Network] 하향식 접근 네트워크 - 6. Mobile Networks

이 글은 이화여자대학교 이미정 교수님의 2014년 2학기 컴퓨터 네트워크 강의를 기반으로 재구성한 것입니다. 삽화는 링크를 출처로, 저작권은 J.F Kurose and K.W. Ross에게 있다는 것을 밝힙니다. 이 글에서는 다음과 같은 내용들을 살펴본다. wireless basics multiple access protocol CSMA/CA CDMA mobility - indirect routing wireless vs mobile 둘은 비슷하지만 엄밀하게는 다르다. wireless는 link가 wireless하게 연결된 경우를 말하고, mobile은 사용자가 움직이는 것을 의미한다. Wireless Basics Wireless Network Element wireless network는 아래 3개의 ..

[Network] 하향식 접근 네트워크 - 5. Link Layer

이 글은 이화여자대학교 이미정 교수님의 2014년 2학기 컴퓨터 네트워크 강의를 기반으로 재구성한 것입니다. 삽화는 링크를 출처로, 저작권은 J.F Kurose and K.W. Ross에게 있다는 것을 밝힙니다. link layer에서는 다음과 같은 내용들을 살펴본다. MAC addressing ARP web request senario MAC address network layer에 있는 IP까지는 32bit의 IP address를 사용해 destination을 표현했고, 이 정보를 사용해 forwarding table에 정보를 작성했다. network layer 아래에 있는 link layer는 datagram을 frame으로 encapsulate한다. internet의 경우 MAC layer가 en..

[Network] 하향식 접근 네트워크 - 4. Network Layer - (6) Broadcast, Multicast

이 글은 이화여자대학교 이미정 교수님의 2014년 2학기 컴퓨터 네트워크 강의를 기반으로 재구성한 것입니다. 삽화는 링크를 출처로, 저작권은 J.F Kurose and K.W. Ross에게 있다는 것을 밝힙니다. network layer principles virtual circuit, datagram network router의 내부 IP datagram format IPv4 addressing ICMP IPv6 routing algorithm link state distance vector hierarchical routing routing in the internet RIP OSPF BGP broadcast, multicast broadcast와 multicast는 간단하게 개념만 짚고 넘어간다. ..

[Network] 하향식 접근 네트워크 - 4. Network Layer - (5) Routing in the Internet

이 글은 이화여자대학교 이미정 교수님의 2014년 2학기 컴퓨터 네트워크 강의를 기반으로 재구성한 것입니다. 삽화는 링크를 출처로, 저작권은 J.F Kurose and K.W. Ross에게 있다는 것을 밝힙니다. network layer에서는 다음과 같은 내용들을 살펴본다. network layer principles virtual circuit, datagram network router의 내부 IP datagram format IPv4 addressing ICMP IPv6 routing algorithm link state distance vector hierarchical routing routing in the internet RIP OSPF BGP broadcast, multicast 지난 포스..

[Network] 하향식 접근 네트워크 - 4. Network Layer - (4) Routing Protocol

이 글은 이화여자대학교 이미정 교수님의 2014년 2학기 컴퓨터 네트워크 강의를 기반으로 재구성한 것입니다. 삽화는 링크를 출처로, 저작권은 J.F Kurose and K.W. Ross에게 있다는 것을 밝힙니다. network layer에서는 다음과 같은 내용들을 살펴본다. network layer principles virtual circuit, datagram network router의 내부 IP datagram format IPv4 addressing ICMP IPv6 routing algorithm link state distance vector hierarchical routing routing in the internet RIP OSPF BGP broadcast, multicast Routi..

[Network] 하향식 접근 네트워크 - 4. Network Layer - (3) Internet Protocol

이 글은 이화여자대학교 이미정 교수님의 2014년 2학기 컴퓨터 네트워크 강의를 기반으로 재구성한 것입니다. 삽화는 링크를 출처로, 저작권은 J.F Kurose and K.W. Ross에게 있다는 것을 밝힙니다. network layer에서는 다음과 같은 내용들을 살펴본다. network layer principles virtual circuit, datagram network router의 내부 IP datagram format IPv4 addressing ICMP IPv6 routing algorithm link state distance vector hierarchical routing routing in the internet RIP OSPF BGP broadcast, multicast IP, I..

[Network] 하향식 접근 네트워크 - 4. Network Layer - (2) Router의 내부

이 글은 이화여자대학교 이미정 교수님의 2014년 2학기 컴퓨터 네트워크 강의를 기반으로 재구성한 것입니다. 삽화는 링크를 출처로, 저작권은 J.F Kurose and K.W. Ross에게 있다는 것을 밝힙니다. network layer에서는 다음과 같은 내용들을 살펴본다. network layer principles virtual circuit, datagram network router의 내부 IP datagram format IPv4 addressing ICMP IPv6 routing algorithm link state distance vector hierarchical routing routing in the internet RIP OSPF BGP broadcast, multicast Route..

[Network] 하향식 접근 네트워크 - 4. Network Layer - (1) Principles, Virtual Circuit & Datagram Network

이 글은 이화여자대학교 이미정 교수님의 2014년 2학기 컴퓨터 네트워크 강의를 기반으로 재구성한 것입니다. 삽화는 링크를 출처로, 저작권은 J.F Kurose and K.W. Ross에게 있다는 것을 밝힙니다. network layer에서는 다음과 같은 내용들을 살펴본다. network layer principles virtual circuit, datagram network router의 내부 IP datagram format IPv4 addressing ICMP IPv6 routing algorithm link state distance vector hierarchical routing routing in the internet RIP OSPF BGP broadcast, multicast Netwo..

[Network] 하향식 접근 네트워크 - 3. Transport Layer - (2) TCP

이 글은 이화여자대학교 이미정 교수님의 2014년 2학기 컴퓨터 네트워크 강의를 기반으로 재구성한 것입니다. 삽화는 링크를 출처로, 저작권은 J.F Kurose and K.W. Ross에게 있다는 것을 밝힙니다. Transport Layer에서는 아래와 같은 내용들을 살펴본다. transport layer service principle multiplexing, demultiplexing UDP : connectionless transport TCP: connection oriented reliable transport reliable data transfer connection, disconnection flow control, congestion control performance TCP에 관한 내용..

[Network] 하향식 접근 네트워크 - 3. Transport Layer - (1) Principles & UDP

이 글은 이화여자대학교 이미정 교수님의 2014년 2학기 컴퓨터 네트워크 강의를 기반으로 재구성한 것입니다. 삽화는 링크를 출처로, 저작권은 J.F Kurose and K.W. Ross에게 있다는 것을 밝힙니다. Transport Layer에서는 아래와 같은 내용들을 살펴본다. transport layer service principle multiplexing, demultiplexing UDP : connectionless transport TCP: connection oriented reliable transport reliable data transfer connection, disconnection flow control congestion control Transport Layer Princip..

[Network] 하향식 접근 네트워크 - 2. Application Layer - (6) Socket Programming

이 글은 이화여자대학교 이미정 교수님의 2014년 2학기 컴퓨터 네트워크 강의를 기반으로 재구성한 것입니다. 삽화는 링크를 출처로, 저작권은 J.F Kurose and K.W. Ross에게 있다는 것을 밝힙니다. Application Layer에서는 크게 3가지를 살펴본다. application principle client-server 구조 peer-to-peer (P2P) 구조 transport layer service model internet protocol - HTTP, electronic mail(SMTP, POP3, IMAP), DNS, P2P network application의 작성을 위한 interface - socket, UDP, TCP 이 글에서는 socket interface를 살..

[Network] 하향식 접근 네트워크 - 2. Application Layer - (5) P2P

이 글은 이화여자대학교 이미정 교수님의 2014년 2학기 컴퓨터 네트워크 강의를 기반으로 재구성한 것입니다. 삽화는 링크를 출처로, 저작권은 J.F Kurose and K.W. Ross에게 있다는 것을 밝힙니다. Application Layer에서는 크게 3가지를 살펴본다. application principle client-server 구조 peer-to-peer (P2P) 구조 transport layer service model internet protocol - HTTP, electronic mail(SMTP, POP3, IMAP), DNS, P2P network application의 작성을 위한 interface - socket, UDP, TCP 이 글에서는 P2P가 왜 빠른지, 그리고 P2P..

[Network] 하향식 접근 네트워크 - 2. Application Layer - (4) DNS

이 글은 이화여자대학교 이미정 교수님의 2014년 2학기 컴퓨터 네트워크 강의를 기반으로 재구성한 것입니다. 삽화는 링크를 출처로, 저작권은 J.F Kurose and K.W. Ross에게 있다는 것을 밝힙니다. Application Layer에서는 크게 3가지를 살펴본다. application principle client-server 구조 peer-to-peer (P2P) 구조 transport layer service model internet protocol - HTTP, electronic mail(SMTP, POP3, IMAP), DNS, P2P network application의 작성을 위한 interface - socket, UDP, TCP 이 글에서는 DNS를 살펴본다. DNS에 관한 ..