-
[Digital Logic] Timing Violation 해결 방법
Digital design 설계를 하다보면 timing violation이 나는 경우가 종종 있다. 해결 방법은 다양하지만 대표적인 방법 몇 가지만 소개한다. Set-up Time Violation 1. Data path buffer 개수 줄이기 말 그대로 data path delay를 줄이기…
-
[Algorithm] Knuth-Morris-Pratt (KMP) 알고리즘
효과적인 설명을 위해 notation은 다음과 같다.x: 찾고자 하는 문자열m: x의 길이y: 본문의 문자열n: y의 길이 Morris-Pratt 알고리즘은 패턴 매칭을 하는데 유용한 알고리즘 중 하나다. Shift OR 함수처럼 매칭 시작전에 lookup table을 만드는 작업이…
-
[Algorithm] Pattern Matching
패턴매칭은 우리가 평소에 작업을 할 때 많이 사용한다. 예를 들면 strstr() 함수라던지 vim에서 / 동작, word에서 Ctrl+F 등 많은 utility에서 사용되고 있다. 패턴 매칭을 위해서 많은 loop을 돌아야하기 때문에 시간 복잡도는 O(n*m)이 된다.…
-
Full Coherency vs. IO Coherency
Coherency Definition Coherency의 정의는 하나의 시스템에 있는 모든 processor 또는 bus master들이 같은 memory view를 가지는 것을 의미한다. 특히 옛날과 다르게 요즘은 private cache를 사용하는 multi-core, heterogeneous system이 많기 때문에 더욱 중요해졌다. 그럼…
-
[Algorithm] Flexible Array
자동으로 자라는 array 구조를 설명한다. 위 코드처럼 C에선 처음 array size가 내부 값을 초기화하면서 고정된다. 이 크기를 유동성 있게 사용하기 위해선 struct 내부로 넣으면 된다. 위 구조체를 잡아서 크기를 확인해보면 4 bytes만 나오게…
-
간격 트리 (Interval Tree)
Kernel에서도 많이 쓰이는 구조로, key 값으로 특정 하나의 값이 아니라 구간이 들어간다. Interval tree는 OS에서 프로세스 address영역을 관리 할 때 용이하게 쓰인다. 만약 위와 같은 tree 구조가 있을 때, 특정 구간 (예를 들면…
-
증강 트리 (Augmented Tree)
소개 Augmented Tree (증강 트리)는 기존 binary search tree에서 확장된 구조다. Binary search tree에서 이론상 특정 값을 검색 할 때, log2(N)만큼의 시간복잡도를 가지기 때문에 balance만 맞춰져 있다고 하면 빠르게 찾을 수 있다. 그러나…
-
Red-Black Tree 개선된 구조
Red-Black Tree – 삽입 글에서 설명한 것 처럼, RB tree에서 사용하는 구조체의 그림과 코드는 다음과 같다. 위 그림에서 rb_color는 단순하게 color값을 나타내는 값인데, 4 bytes를 가지는 int 타입이다. 따라서 parent의 주소값을 가지는 rb_parent의…
-
Red-Black Tree – 삭제
만약 아래 그림과 같은 RB tree 구조가 존재했을 때, node 1을 삭제하면 다음과 같을 것이다. 위 그림과 같이 됐을 때, tree의 균형은 맞는 것 처럼 보일 수 있지만 실제 균형이 맞지 않는 것이다.…
-
Red-Black Tree – 삽입
일명 RB tree라고 부르는 Red Black Tree는 binary search tree의 종류로 모태가 되는 구조는 B tree다. RB tree는 kernel의 메모리를 찾을 때도 사용되고 scheduling 할 때도 많이 사용된다. 큰 장점은 매 새로운 노드를…
