-
[Algorithm] Dijkstra Algorithm
Dijkstra algorithm은 한 점 (vertex)에서 모든 점까지 최단거리를 구하는 알고리즘이다. 자료구조에서는 graph 이론을 배우면서 반드시 알아야 할 내용이다. 각 vertex까지 최단거리를 구하는 과정은 다음과 같다. 초기화: 아직 방문하지 않는 vertex에 대해서는 거리는 무한대,…
-
[Algorithm] Union-Find Algorithm
Union-Find 알고리즘은 그래프 알고리즘 중 하나로 “합집합 찾기”를 위해 사용되는 대표적인 알고리즘이다. 사용되는 연산 과정은 다음과 같다. Find: x가 어떤 집합에 속해있는지 찾는 연산 Union: x와 y가 속한 집합을 합치는 연산 Example Step…
-
[Algorithm] Kruskal’s Algorithm
Introduction (including Spanning Tree) Kruskal 알고리즘이란 최소한의 비용으로 다수의 노드를 연결을 greedy하게 할 때 사용하는 알고리즘이다. 이 알고리즘은 보통 Spanning Tree를 만들 때 사용되는데, Spanning Tree란 graph 구조에서 모든 vertex가 서로 연결이 되는데…
-
[Computer Arch.] x86 Flags (Condition Code) & Registers
1. Flags x86 machine에서 사용되는 condition code flags들에 대한 정보는 내부 architecture를 분석하는데 매우 중요하다. 내부 register name은 eflags 라는 이름으로 가져간다. 비트 약어 이름 설명 0 CF Carry Flag 연산시 최상위 비트…
-
[Computer Architecture] rep; ret Instruction for x86-64
x86-64 assembly를 보다 다음과 같은 instruction stream에서 rep; ret라는 instruction이 나왔다. 일단 rep instruction이 쓰이는 이유는 AMD processors’ branch predictors에 문제가 있었다고 한다. ret instruction은 single-byte instruction으로 conditional jump instruction 뒤에 있는 경우…
-
[Compiler] Compiler Pipeline 구성
Computer system에서 compiler란 high level languages (C, C++, Python 등)을 hardware에서 이해 할 수 있는 형태로 전환하는 프로그램이다. Compiler와 비슷한 interpreter 또한 존재하는데, 간단한 차이는 다음과 같다. Compiler Interpreter Compiler는 전체 program을 분석한다.…
-
[OS] Memory Layout of C Program
C program이 compile되고 난 뒤 memory에 load 될 때 layout은 다음과 같다. 크게 총 다섯 가지 영역으로 나눌 수 있다. Text (Code) Data (Initialized) BSS (Uninitialized) Heap Stack 1. Text (Code) Segment Read…
-
[Digital Logic] Clock Gating 관련 용어
Clock gating은 현대 digital logic에서 power consumption 절감을 위해서 필수적인 scheme이다. Clock gating을 평가하기 위한 여러가지 지표가 있어서 이를 소개한다. 1. Clock Gating Ratio (CGR) 전체 register 중 clock-gated register의 비율을 나타낸다. 이상적인…
-
[OS] Process vs. Thread
1. Process Process란 disk에 있는 program이 memory로 올라온 상태의 것을 의미한다. Process별로 code, data, stack, heap memory 영역을 가지며 하나의 CPU를 점유하여 수행하게 된다. Process간 context switching을 하기 위해선 Process Control Block (PCB)를…
-
[OS] Deadlock
OS에서 deadlock이란 용어는 하나 또는 여러 개의 프로세스가 일어날 수 없는 event를 기다리며 영원한 대기하는 상태를 말한다. 실제로 위 그림을 보면, process 1 (P1)은 resource 1 (R1)을 요구하지만, R1은 이미 process 2 (P2)에…
