개발하는 멍정이야기

Time for Moving Valid Pages 그렇다면. erase하기 위해서 옮기고 지우고 해야하는데 얼마나 시간이 걸릴까? The Intrinsic Latencies of Flash Memory 대략적으로 읽기는 25ns ~ 65us 쓰기는 300us ~ 1.5ms 지우기는 2ms ~ 5ms Time for Reclaiming a Victim Block 피해 블록 회수 시간. 읽기 : 40나노초 * 200pages = 8밀리초 쓰기 : 800나노초 * 200pages = 160밀리초 지우기 : 3밀리초 * 1block = 3밀리초 Time for Reclaiming Multiple Victim Blocks 여러개의 블럭을 한 번에 쓰고 지울 수 있지만 쓰고 지우는걸 동시에는 못한다는걸까? ?? I..

Consequence of Out-of-Place Updates 덮어쓰기가 안되기 때문에 clean page에 값을 넣다보면 언젠가 자리가 없어질 것이다. -> 그럼 write가 안되니까 invalid를 지우자! How about Erasing Invalid Page? invalid값을 다 지워버리자! -> but erase는 block단위이기 때문에 불가능! < 읽기쓰기 기본 단위는 page지만 삭제는 block! What of a To-Be-Erased Block Holds Valid Page? - block단위로 삭제할 수 있으니 valid값을 새로운 block에 넣고 전부 invalid해진 block을 지워버리자! Valid Page Movement 새로운 block에 값을 옮겼다면 mapping..

Flash Translation Layer(FTL) Host system과 I/O를 처리할 때 SSD는 flash memory의 특성이 있기 때문에 HDD와 다른 방식으로 처리해야한다. flash memory 특징 - Asymmetric operation units (reads/writes가 blocks단위로 지우고 page 단위로 작성 - Program-after-erase property(덮어쓰기가 안됨) - Limited flash memory lifetime(수명이 제한적임-> 아마 wear leveling관련?) Various Functionalities(Modules) of FTL - Address mapping - Garbage collestion(GC) - wear leveling //fe..

Chained Matrix Multiplication (연쇄 행렬 곱셈) : 행렬 i x j와 행렬 j x k 처럼 열의 갯수와 행의 갯수가 같은 연속적인 행렬의 곱셈 - 행렬의 곱은 결합법칙이 적용하기 때문에 곱하는 순서는 상관없지만 곱하는 횟수가 달라지기 때문에 최적의 순서를 구해야한다. e.g. A1 x A2 x A3. A1은 10 x 100, A2는 100 x 5, A3은 5 x 50. (A1 x A2) x A3 10 x 100 x 5 + 10 x 5 x 50 = 7,500 A1 x (A2 x A3) 100 x 5 x 50 + 10 x 100 x 50 = 75,000 //100을 2번 계산하기 때문에 연산 횟수가 증가함 Brute force algorithm : 전부 해보기 이런 방법에 대한 시간..

Graph Theory - 그래프는 G = (V, E)의 두 요소로 구성된다. - vertex : 정점 - E : 간선들의 집합 | 간선들은 2개의 endpoint를 가진다. - directed graph(digraph) : 방향성이 있는 그래프 - weighted graph(weights) : 값이 있는 그래프 - path : digraph에서 정점에서 목적지로 가는 방법(정점들을 담고 있는?) - cycle : path가 돌아서 시작점으로 돌아옴 ㄴcycle인 그래프를 cyclic, 그렇지 않으면 acyclic - simple : 같은 정점을 다시 돌아오지 않는 경우 - length : weighted graph에서 weights들의 합 Example : A weighted, directed grap..

Dynamic Programming (동적 계획법) Bottom up 방식으로 작은 값 부터 구하기 시작하여 결과를 도출한다. 작은 값부터 시작하는건 DIvide and Conquer랑 비슷하시지만 밑에서부터 시작한다는 점에서 차이점이 있다. Bottom up 방식이기 때문에 한 번 계산한 결과를 다시 계산할 필요 없이 저장된 결과를 불러서 사용한다. The Binamial Conefficient(이항계수) 조합 n​Cr n개에서 r개를 순서 상관없이 골라내는 경우의 수 전체 경우의 수 n! 에서 필요없는 나머지 경우의 수 (n-1)!을 나누고 순서가 상관 없기 때문에 뽑은 갯수 k!만큼 또 나눠주기~ Pascal's Triangle 대각선 위에 있는? 값들의 합은 아래에 있는 값이 된다! 조합을 사용해..

Matrix Multiplication : 행렬의 곱은 어떻게 계산 할까 //Matrix Multiplication //Standard Algorithm void matrixmult(int n, const number A[][], const number B[][], number C[][]) { index i, j, k; for (i = 1; i 결과적으로 DIvide and Conquer이 되는 것!! strassen(행렬 A, 행렬 B, 새로운 행렬 C) { if(일반적인 계산이 더 이득일 것 같은 경우) 일반적으로 C = A * B를 계산해줌 else { //계산이 복잡한 경우 행렬 A를 4개의 행렬로 나눠줌 행렬 B를 4개의 행렬로 나눠줌 step1. M1부터 M7까지의 경우를 호출함 ex1. st..

Quicksort 가장 첫번째 array의 값(pivot)을 기준으로 더 작은 값과 큰 값으로 나누어 정렬함 //Quicksort void quicksort(index low, index high) { index pivotpoint; if(high > low) { partition(low, high, pivotpoint); //pivotpoint를 기준으로 정렬 quicksort(low, pivotpoint-1); // pivot보다 큰거 quicksort(pivotpoint+1, high); //pivot보다 작은거 //partition void parititon(index low, index high, index &pivotpoint) { index i, j; keytype pivotitem; piv..

The Master Theorem(마스터 정리) 이런 경우에서 시간복잡도를 편하게 구할 수 있는 공식! where a > b> 1 and n is a no -negative integer. case1. a - ε라면 시간복잡도는 오른쪽과 같다. case2. a랑ε가 같은 경우 시간복잡도는 오른쪽과 같다. case3. a + ε이고 중간의 수식을 만족하는 C가 1보다 작다면 시간복잡도는 오른쪽과 같다. Example case1 case2 case3 Auxiliary Master Theorem case3의 C < 1을 만족하지 못하는 경우

DIvide and Conquer Approach - Divide : 인스턴스가 너무 커서 계산이 힘들다면 작게 쪼개서 계산한다. - Conquer : 작아진 인스턴스를 해결한다. - Combine : 해결한 인스턴스를 재조립한다. -> Top-down approach(하향식 접근법) Binary Search Algorithm Design - 검색 범위를 줄여가며 탐색 - Problem : 크기가 n인 sorted array S에서 key x는 어디에 있는가? - Input(parameter) : 양수 n, 1부터 n까지의 값을 갖고 있는 정렬된 내림차순이 아닌 배열 S(sorted array) + non-decreasing order(비내림차순) : 내림차순이 아니다 != 오름차순 ex. 1, 5, 6..