전체보기

Java 면접대비 질문

Data type더보기종류string ? 더보기primitive : stack에 저장. byte, char, short, int, long, float, double, booleanreference : 주소값 가리킴.  string : reference이지만 primitive처럼 동작. immutable이기 때문new로 생성: heap에 새 객체, literal :  string constant pool에서 intern() method 호출  Pass by value더보기primitive, reference, wrapper, string은 각각 어떻게 넘어가는지더보기primitive는 값 자체를 복사해 넘김reference는 참조하는 주소를 복사해서 넘김string을 넘긴 후 assign하면 주소가 바뀐..

[Spring] DTO와 Entity 간의 변환

Spring을 쓴다면 MVC 구조를 사용한다는 것을 전제로 깔고 갈 것이다. 따라서 Controller, Service, Repositoy, DB 순으로 flow가 이동하며, 이 과정에서 entity라는 객체와 DTO라는 객체를 사용한다. 정의를 먼저 살펴보자면, entity는 DB의 row 하나와 매핑되는 객체인 반면, DTO는 Data Transfer Object, 데이터를 옮기는 데 사용하는 객체이다. DTO의 필요성 DTO의 필요성에 대해서는 말할 필요도 없다. 만약 DTO가 없다고 가정해 보자. 그러면 entity를 사용자에게 노출시켜야 하는데, entity는 DB의 모든 column에 대한 정보를 가지고 있기 때문에 이를 사용자에게 노출시키는 것은 좋지 않다. 또한 entity에 내용이 부족해..

[이종병렬컴퓨팅] 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을..

[RAFT] RAFT consensus algorithm specification

중간고사가 끝난 이후부터는 RAFT 알고리즘을 maude를 사용해 formal modeling을 진행할 것입니다. 그에 앞서 어떠한 specification을 모델링할지 결정해야 합니다. 따라서, 이 글에서는 RAFT consensus algorithm에 대해 간단히 소개하고 modeling하고자 하는 specification을 작성하고자 합니다. RAFT consensus algorithm RAFT consensus algorithm은 모든 node가 동일한 상태를 유지하며, tolerance를 보장하기 위해 고안된 알고리즘이다. 때문에 일부 node에 문제가 생겨도 전체 system이 잘 동작해야만 한다. 구성 모든 node는 아래 3가지 상태 중 한 가지를 가진다. cluster란 여러 subsys..

Spring 면접대비 질문

Spring더보기정의뭐 지원하는지더보기IoC(bean)DIAOP등의 특징을 가지는 프레임워크 Bean더보기정의더보기spring에서 plain old java object - 그냥 객체 - 를 bean이라고 한다. IoC Container가 관리 및 생성한다.@Component를 사용한 class들만 bean으로 정의된다. 이 bean들은 기본적으로 singleton이다.IoC Container가 DI해주기도 한다. IoC더보기정의더보기제어 역전 - 프로그램 제어권이 programmer가 아니라 framework인 spring에 있는 것. 개발자는 framework의 형식에 맞춰 개발하게 된다. AOP더보기정의더보기aspect oriented programming 공통 관심사를 분리해 모듈화하는 것. 인증..

[이종병렬컴퓨팅] 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할 수..

[Maude] Token Ring 검증

이 글에서는 Designing Reliables Distributes Systems, 225p에 있는 Token Ring을 maude를 사용해 formal modeling하고 원하는 검증을 진행합니다. 원 프로젝트는 RAFT consensus algorithm을 모델링하는 것이지만, 그 전에 손풀기 느낌으로 좀 더 쉬운 token ring을 모델링합니다. Token Ring In the “token ring” mutual exclusion algorithm, the nodes logically form a “ring” structure, as shown in Figure 13.1 where a node only knows the next node in this ring. The algorithm work..

[Model Checking] Designing Reliable Distributed Systems

TODO Ch. 2 : 자연수, 정수, list, binary tree, multiset 등 data type 정의 Ch. 3 : equational specification이 만족하는지 확인 Ch. 8 : rewrite logic을 사용해서 concurrent behavior 작성 방법을 설명 Ch. 9 : rewriting logic을 사용해서 system의 동작 하나를 분석하는 방법 FREE Ch. 10 : concurrent Ch. 11 : communication Ch. 12 : TCP와 같은 transport protocol 모델링 Ch. 13 : distributed DB 모델링 Ch. 2 Data Types Module fmod MODULE_NAME is MODULE_BODY endfm o..

기타 면접대비 질문

간단한 자기소개지원동기장단점나의 비전 : 사람들에게 긍정적인 영향을 줄 수 있는 사람이 되는 것.프로젝트 하면서 어려움 극복 : bizkicks 얘기?회사에 대해 궁금한 점협업 방식각 프로젝트인성   개발지식객체지향더보기정의class vs instance특징 4가지장단점더보기객체들의 상호작용으로 프로그램을 구현하는 방법.객체는 어떤 개념을 추상화하고 모델링한 요소. state와 behavior를 가짐.- 추상화란 불필요한 정보는 숨기고 중요한 정보만을 보여주는 것(컴퓨터 과학)class : 설계도, instance : class로 만들어진 메모리에 올라간 실체. 특징abstraction : OOP에서 abstraction은 불필요한 정보는 private으로 숨기고 중요한 정보를 public으로 노출하고,..

자료구조 면접대비 질문

Hash Table 더보기 정의 collision 해결 방식 hash function 더보기 어떤 key가 주어졌을 때 hash function으로 매핑하고, 거기에 값을 저장하는 key-value store. 메모리에 쓰는 경우, 값이 유한하기 때문에 collision이 발생한다. separate chaining : 해당 bucket에 linked list 추가하는 방식. 쏠릴 수 있어 worst O(n) open addressing : 해당 위치가 아니라 빈 공간을 사용하는 방식. 예외가 많아 어렵다. hash function은 임의의 길이 data를 고정 길이 data로 매핑하는 함수. Quick Sort 더보기 pivot 기준으로 왼쪽에는 작은 수, 오른쪽에는 큰 수 둔다. pivot은 적당한 값..

네트워크 면접대비 질문

URL vs URI더보기URL : uniform resource locator, resource의 위치URI : uniform resource identifier, resource의 식별자 HTTP더보기정의특징http request message / response message에 들어가는 것들더보기hypertext transfer protocol의 약자client-server model, TCP 사용, stateless(상태 저장 x) 등의 특징이 있다.stateless를 해결하기 위해 cookie나 session을 사용한다. HTTP request message에는 request, header, body가 있다.method는 GET, POST, PUT, PATCH, DELETE 등이 있다.GET의 경..

OS 면접대비 질문

Floating Point더보기어떻게 표현하는지case 3개변환방식rounding더보기2진수를 유효숫자 형태로 표현한 것(-1)$^s$M2$^E$s : sign bit. signed integer와 동일하게 0이면 양수, 1이면 음수이다.M : significand(유효숫자). 일반적으로 [1.0, 2.0)의 범위를 가진다.E : exponent(승수). 2의 승수를 나타낸다. Floating Point to Number수를 정해진 형식에 따라 sign bit, exp bit, frac bit로 분류한다.exp bit, frac bit을 이용해 normalized / denormalized / special 분류를 한다.exp bit로 E값을, frac bit로 M값을 구한다. (-1)$^s$M2$^E$..

DB 면접대비 질문

Transaction더보기transaciton의 정의, 특성(ACID)commit / rollbackstate더보기transaction : DBMS의 상호작용 단위. transaction은 다음 4가지 성질을 가지고 있다.Atomicity : transction은 실행되거나, 실행되지 않거나 둘 중 하나의 상태만 가진다. 중간에 끊기지 않는다.Consistency : transaction의 실행 결과는 항상 일관성이 있다. (정해둔 규칙을 위배하지 않는다.)Isolation : transaction 사이에 다른 trasnaction이 낄 수 없다.Durability : DBMS가 꺼져도 수행된 transaction은 반영되어 있어야 한다.  commit은 모든 작업이 정상적으로 수행되었다는 명령이며, 실..

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..

23.09.25. 풀었던 문제들

Programmers Lv. 3 입국심사, 8분 parametric search. typedef long long ll; vector times; // t시간동안 심사할 수 있는 인원 수 ll calculateNumPass(ll t){ ll num_pass = 0; for(int time : times){ num_pass += ((ll) t / time); } return num_pass; } long long solution(int n, vector t) { ll start = 0, end = 1e18; times = t; while(start = n..

23.09.24. 풀었던 문제들

Programmers Lv. 3 보석 쇼핑, 19분 two-pointer를 활용하면 되는 문제. 유의할 점은 start와 end 사이에 있는 보석 개수를 세야 하는데, map으로 숫자를 세면 count에 O(보석 개수)만큼의 시간이 걸리고, multiset을 쓰면 identical한 보석 개수를 셀 수 없기 때문에 map과 set을 같이 썼다. set cur_gems; int num; map cur_gem_count; bool isContainAll(){ return cur_gems.size() == num; } void insert(string gem){ cur_gem_count[gem]++; cur_gems.insert(gem); } void erase(string gem){ cur_gem_count..