Optimal Binary Search Tree (OBST) 최적 이진 검색 트리 Definitions (정의) Node Structure (노드의 구조) - \(\texttt{key}\) : 검색 대상이 되는 원소로, key는 검색 가능한 Ordered Set의 원소이어야 한다. - \(\texttt{probability}\) : 해당 노드의 key를 검색하게 될 확률이다. (\(p_{i}\) = \(Node_{i}\)를 검색할 확률) - \(\texttt{leftChild}\) : 해당 노드의 왼쪽 자식 노드를 가리키는 주솟값이다. - \(\texttt{rightChild}\) : 해당 노드의 오른쪽 자식 노드를 가리키는 주솟값이다. Average Search Time (AST, 평균 검색 시간) -..
ICMP Version 4 ICMP 버전 4 프로토콜 - ICMP : Internet Control Message Protocol - L3의 Support Protocol 중 하나로, 패킷 송수신 중 오류가 발생되어 패킷이 폐기되었음을 Source에게 알리는 데 사용되는 프로토콜이다. - ICMP 프로토콜 밑에 IP 프토콜이 위치해있는데, 이는 ICMP 메시지가 Frame(L2 패킷)으로 구성될 때, IP 프로토콜을 필히 거치게 됨을 의미한다. - IGMP는 Multi-Casting을 보조하기 위한 프로토콜이다. - ARP는 패킷의 NHA 주소에 해당되는 물리 주소로 변환하는 프로토콜이다. - IP 프로토콜은 패킷 송수신 과정 중 문제가 발생했을 때, 오류를 보고/보정하는 기능을 제공하지 않는다. ※ I..
Control Unit 제어 유닛 - Instruction Decoding에 의해, 명령어의 Opcode와 Funct가 파악된다. - R-Type 명령어의 6bits Opcode에 의해 그림의 6가지 Control Signal의 값이 결정된다. - R-Type 명령어의 6bits Funct에 의해 ALUControl값이 결정된다. ALUOp[1:0] Meaning 00 Add 01 Subtract 10 Look at \(\texttt{Funct}\) 11 Not Used - ALUOp = 10이라면 해당 명령어는 R-Type 명령어이기 때문에, Funct 코드까지 필히 확인해야되는 상황임을 의미한다. - lw, sw명령어는 OPcode만 파악하여, Add 연산을 지시할 수 있다. - bne, beq 명령..
ALU (Arithmetic and Logic Unit) 산술/논리 연산 장치 Abtracted ALU \(\texttt{A, B}\) : Operands (연산 대상, N bits) \(\texttt{Y}\) : 연산 결과 (N bits) \(\texttt{F}\) : ALU가 수행할 연산의 종류를 구분짓는 Contorl Signal (3 bits) ※ 32bits MIPS 시스템의 경우, N = 32가 될 것이다. ALU Details - 위 Diagram에서 ALU가 출력하는 Zero-Signal은 표현되지 않았다. - 7개의 연산 종류를 구분짓기 위해 ALU Control Signal(F)은 최소 3bits로 구현되어야 한다. - 8개의 F코드 중 011은 사용되지 않는다. - F2(F의 MSB)..
Lex and Yacc - 1970년대 벨 연구소에서 개발되어, 후에 UNIX 표준 유틸리티로 선정되었다. - Lex가 입력 문자열에 대한 일차적인 검색을 수행하고, 실질적인 분석은 Yacc가 수행한다. - Source → Lex Scanner → Yacc Parser 순서로 처리한다. - 즉, 입력 Syntax의 검색과 분석을 용이하게 위해 사용하는 언어들이다. - 수치와 연산자를 구분하는 계산기 프로그램, 컴파일러, 인터프리터 언어의 문장 검색, 문법 분석 기능, SQL 언어의 문법 검사와 같은 기능들을 Lex와 Yacc로 구현할 수 있다. Lex (Lexical Analyzer Generator, 어휘 분석 생성기) - 1975년 AT&T Bell 연구소의 Eric Schmidt와 Mark Lesk..
Instruction Processing Process 명령어 처리 과정 - Program Termination 전까지 아래 4단계가 반복된다. 1. Fetch - PC가 저장하고 있는, 실행될 명령어가 저장된 주소에서 해당 명령어를 CPU로 가져온다. 2. Decoding - Extract Op-Code : 해당 명령어가 어떤 종류의 연산을 지시하는지 해석한다. - Extract Operands : 명령어가 지시한 피연산자(Register, Immediate Field 등)를 해석한다. 3. Execution - 앞서 해석한 연산의 종류에 따라 ALU를 적절히 활용한다. - 산술/논리 연산의 경우, ALU를 산술/논리 연산에 활용한다. - Read/Write 연산의 경우, ALU를 접근하고자 하는 메모..
IP Package IP 패키지 - 노드에서 패킷이 처리되는 과정을 나타낸 가상의 그림이다. 외부에서 전송된 패킷 : 아래에서 올라오게 된다. (Data-Link 계층으로부터 패킷을 전달받는다.) 내가 전송할 패킷 : 위에서 내려오게 된다. (상위 계층으로부터 패킷*을 전달받는다.) * 상위 계층에서 받는 패킷은 TCP 패킷, UDP 패킷 혹은 ICMP 패킷, IGMP 패킷이 될 수 있다. 1. Header-Adding Module (헤더 추가 모듈) Header_Adding_Module (data, destination_address, service_type, data_length, TTL) { Encapsulate data in an IP-Datagram Calculate checksum and in..
