-
Binary Search Tree
일반적인 Tree는 검색용으로 적합하지 않다. 왜냐하면 어떤 값을 tree 구조에 저장 할 때 항상 tree에 노드가 균일하게 배치가 된다는 보장이 없기 때문이다. 이를 위해서 Binary Search Tree 구조는 balance 함수를 통해서 항상 log(2)N의…
-
[Algorithm] Generic Tree
Tree 기본 구조 및 용어 Tree 구조의 특징은 어떤 데이터를 찾고자 할 때 좀 더 빠른 시간 내에 찾을 수 있는 장점을 가진다. 구조는 아래 그림과 같이 root를 기점으로 좌 우 노드와 연결되어…
-
[Digital Logic] Static Timing Analysis (STA)
Definition 회로 설계하는 분야에서 Static timing analysis (STA)는 회로의 모든 타이밍 위배가 발생 할 수 있는 경로에 대해서 확인함으로서 성능을 검증하는 방법이다. 또 다른 검증 방법으론 dynamic simulation이 있는데, 이 방법은 모든 입력…
-
[Algorithm] Generic Hash
Linked List 구조에서 특정 데이터를 찾고자 할 때, head가 가리키는 노드부터 찾을텐데 만약 데이터가 가장 마지막 노드에 있다면 시간복잡도 기준으로 O(N)이 된다. Hash에선 bucket이라는 구조가 사용되는데, hash function을 거쳐 나온 값을 통해서 bucket을…
-
타입 의존성 제거 (Loose Coupling)
C언어를 사용하는 환경에서 만약 linked list 구조에 우리가 원하는 구조체를 가지는 instance를 저장하고 싶을 때는 쉽게 되지 않는다. 위 코드처럼 SAWON 이라는 구조체가 있는데, 해당 구조체를 linked list에 삽입하려고 할 때, 위 코드에서…
-
SAIF Format
Switching Activity Interchange Format (SAIF)의 약자로 디지털 회로 설계 과정 중 사용되는 data format 중 하나다. 매우 단순하지만, 위 그림처럼 우리가 일반적으로 아는 설계 data들을 다음과 같이 변화시키는데, Pre-Net에서 Post-Net으로 변환하는 과정을 Place…
-
[Computer Arch.] Difference between CAM and Fully-associative Cache?
Computer architecture 분야에서 두 개의 단어는 많이 사용한다. 이 두개는 실제 헷갈릴 수 있는 단어다. Content-addressable Memory (CAM) 이름 그대로 content를 가지고 access를 하여 address를 얻는 메모리 구조를 말한다. Input으로 특정 content data가…
-
[Paper Review] Freeway: Maximizing MLP for Slice-Out-of-Order Execution
Motivation CPU 성능을 높이기 위해, long latency memory access를 hiding 하여 Memory Level Parallelism (MLP) 를 활용하는 연구가 많이 진행됐다. 본 논문은 그 중 Slice-out-or-order (sOoO) 를 revisit 한다. sOoO에선 에너지 효율성을 높일…
-
Analysis, Elaboration and Synthesis
Hardware design을 하시는 분들이면 다음 단어들을 많이 듣고 사용할 것이다. 각 단어들의 정의를 잘 쓰인 글이 있어서 첨부해봤다. Analysis Analysis is the process where the design files are checked for syntactic and semantic…
-
[Paper Review] The Load Slice Core Microarchitecture
Motivation Microprocessor core는 Instruction Level Parallelism (ILP)를 올리기 위해 in-order pipeline에서 superscalar out-of-order pipeline으로 진화해왔으며, side-effect로 memory Level Parallelism (MLP) 또한 높여왔다. 참고: Memory-level parallelism (MLP) is a term in computer architecture referring to the ability…
