레드의 노트

TLB - Translation Lookaside Buffer TLB는 Virtual Memory Address를 Physical Memory Address로 전환하는 역할을 하는 장치. TLB가 필요한 이유 Virtual Memory는 Main Memory를 Storage의 Cache Memory로 사용하는 기술이다. [ CPU - Cache Memory - Main Memory ] [ CPU - Main Memory - Storage Memory ] 두 순서가 같은 관계로 구성되도록 하는 기술이 Virtual Memory이다. 64Bit CPU를 이용하는 경우, Register가 가질 수 있는 주소의 길이는 2^64 = 2^4 x 2^60 = 16EB ( 1 EB = 1,000,000 TB ) Vir..

CPU마다 Lv1 Cache를 가지고있기에, 같은 주소에 다른 데이터를 저장할 가능성이 있다. (Lv1의 같은 주소에 서로다른 데이터를 저장 -> Lv2는 Update되지 않아 서로 꼬이는 경우) : Cache Coherence Problem => MESI protocol Lv1 Cache #1, Cache #2가 참조하는 메모리주소가 같은 경우, 건드리지 않는다. Handling Writes on Cache Memory Read Miss ( 읽기에 실패 ) : 메모리에서 해당 데이터를 가져오면 해결 Write Miss ( 쓰고자하는 메모리주소가 Cache에 없는 경우 ) : ??? 아래는 HardWare가 알아서 처리해주는 문제에 해당한다. 원리를 알아두자. Write Allocated - Write ..

Data Structure : 최소비용신장트리 - Sollin's Algorithm ( Boruvka's Algorithm ) Sollin의 알고리즘은 Greedy Strategy로, 각 스텝마다 가능한 최선의 선택지를 고르는 것을 반복하여 결과를 얻어낸다. 규칙 시작하면서 모든 정점을 Tree로 정의한다. ( Forest 상태 ) 하나의 Tree에 대해 외부의 Vertex와 연결 가능한 가장 비용이 작은 edge를 선택해 추가한다. edge가 중복되는 경우에는 하나만 추가한다. Tree가 하나로 이어질 때 까지 2를 반복한다. ( Forest 상태 X ) Sollin 알고리즘 모든 Vertex를 one-vertex Tree로 정의 while(tree가 하나가 아니면) { 모든 tree에 대해서 각각 T..

Data Structure : 최소비용신장트리 - Prim's Algorithm Prim의 알고리즘은 Greedy Strategy로, 각 스텝마다 가능한 최선의 선택지를 고르는 것을 반복하여 결과를 얻어낸다. 규칙 하나의 정점에서 시작함. 한번에 하나씩 Tree에 간선을 추가하고, 추가한 결과는 Tree를 이루어야 한다. Tree가 여러 개이면 Forest Tree에 추가한 간선이 Cycle을 구성하지 않도록, 간선을 고를 때 Tree에 속해있는 Vertex 하나와 속하지 않은 Vertex 하나가 만드는 간선을 골라야 한다. Tree에 속한 edge의 개수가 vertex 개수 - 1인 경우 ( Spanning Tree 조건을 만족 ) 또는 추가할 edge가 없는 경우 ( Spanning Tree X ) ..

Data Structure : 최소비용신장트리 - Kruskal's Algorithm Kruskal의 알고리즘은 Greedy Strategy로, 각 스텝마다 가능한 최선의 선택지를 고르는 것을 반복하여 결과를 얻어낸다. Kruskal 알고리즘은 주어진 가중치 그래프에서 최소비용인 신장트리를 뽑아내는 것을 목표로 한다. ( 신장트리 : vertex를 모두 연결하면서 edge의 개수가 n-1개인 트리 ) 규칙 한 번에 하나씩 간선을 추가한다. 추가되는 간선의 순서는 비용의 크기를 기준으로 선택한다. 간선을 추가했을때 사이클이 형성되지 않는 간선만 추가 가능하다. 사이클이 형성되는가? 에 대해서는 'Union-Find'를 이용한다. 간선의 개수가 n-1인 경우 ( Spanning Tree 만족 ) 또는 남은 ..

Cache Memory CPU에는 Level 1 Cache, Level 2 Cache, Level 3 Cache 등이 존재한다. ( 발전할수록 추가된다. 현재 L3까지 온 상태! ) Lv1 Cache는 32KB로, L1I ( Instruction 저장 ) L1D ( data 저장 ) 두 종류가 있다. CPU내에 각각 존재한다. Lv2 Cache는 256KB로, CPU내에 각각 존재한다. 범용 저장공간에 해당 Lv3 Cache는 MB단위, System에 하나 존재한다. Register와 Memory는 Compiler에 의해 오가지만, Cache와 Memory사이는 HW가 자동으로 오가기에 SW가 필요 없다. Cache의 필요성 Cache Memory는 메모리에서 레지스터로의 읽고쓰는 성능향상을 위해 둘 사..

가장 단순한 IO Interrupt 형태 : 모든 IO Device들이 OR gate로 묶여있다. IO Interrupt가 발생했다는 신호가 CPU에 들어오면, CPU는 누가 이 신호를 보냈는지 IO Device를 추적한다. 이를 통해 해당 Interrupt를 실행한다. Priority는 Status Register를 먼저 읽어 Check 한다. - 누가 보냈는지, Priority는 어떤지를 알기 위해서는 모든 IO에 접근 ... 응답시간이 길고 효율이 낮다. 더 나은 Interrupt 처리가 필요하다. INTC ( Interrupt Controller ) / PIC ( Programmable Interrupt Controller ) / APIC ( Advanced PIC ) / GIC ( Generic..

Interrupt는 CPU와 Peripheral Devices 사이의 소통이다. Interrupt: IO Device가 generate 하는 것 둘은 미세한 차이가 등장한다. Exception: CPU가 Internally generates 하는 것 둘 다 CPU에서 신호에 대해 처리한다는 공통점이 있다. Interrupt Asynchronous Signal ( HW ), Synchronous Event ( SW : System Call - SVC ( SuperViser Call ) Instruction 을 제공 ) ex) OS의 Scheduling은 time interrupt를 이용한다. IRQ : Normal Interrupt Request PC가 0x08로 이동 → Branch로 이동하여 원하는 I..

ARM은 세 가지 Instruction Set을 제공한다. ARM ISA : 32bit Instruction Thumb2 : 16bit & 32bit Instruction Thumb은 16bit Instruction으로 구성되어있고, 이를 확장하여 32bit Instruction을 덧붙여 Thumb2를 제공한다. Special Perpose의 Embedded System을 목적으로 디자인되었다. 따라서, Reduced-Cost Row-Performance를 만족시키기 위해 Low memory Set을 제공한다. Jazelle : Java ByteCode ( ByteCode 실행에 JVM이 필요없다 ) CPSR의 J,T bit을 통해 어떤 Inst Set으로 번역될 지 설정 가능하다. Compiler가 알..

Real Time Clock - RTC : 2^15Hz = 32768 Hz = 32.768 kHz = 1 Sec RTC를 2^15로 나누면 1Hz 에 1 Sec인 Clock을 만들어 1초를 Count할 수 있다. 타이머는 Task Scheduler 등의 작업에서 App에게 시간 배정으로 동시에 작업을 수행하도록 만들기 위해 사용된다. ( event Interrupt를 통해 Count한 1ms의 경과를 CPU에게 알린다. ) Private Timer Timer Load Register, Timer Count Register, Timer Control Register, Timer Status Register로 구성되어있다. - Timer Load Register 초기값에 해당하는 값. - Timer Coun..