🖥 Computer Science

🧐 부분 수열(Subsequence) 길이 n인 수열(sequence, ordered list) $S = a_1, a_2, ... a_n$ 이 주어졌을 때, 수열 $S' (= a_{i1}, a_{i2}, ..., a_{ik})$ 가 $1 \leq i1 < i2 < ... < ik \leq n$ 를 만족할 경우, $S'$ 를 $S$ 의 subsequence라 합니다. 🧐 증가 수열(Increasing sequence) 수열 S = $a_1, a_2, ..., a_n$ 에 대하여 $a_1 < a_2 < ... < a_n$ 일 때, increasing sequence라 합니다. 🧐 감소하지 않는 수열(Non-decreasing sequence) 수열 S = $a_1, a_2, ..., a_n$ 에 대하여 $a..

🧐 Memoization 재귀적으로 반복되는 어떠한 함수의 중간 결과를 저장하는 기법을 의미합니다. 🧐 Dynamic Programming Recursion(재귀)과 Memoization을 사용하여 문제를 해결하는 기법을 의미합니다. DP의 본질은 재귀를 올바르고 똑똑하게 하는 것이므로, 재귀를 위한 Recurrence Relation을 올바르게 세우는 것이 중요합니다. 🧐 DP 문제 해결 순서 1. 문제를 정확하게 정의합니다. 2. 정의된 문제에 대하여 부분 문제(Subproblem)을 정의합니다. 3. Subproblem을 이용하여 Recurrence Relation을 세웁니다. 4. Memoization을 이용하여 Recurrence Relation을 계산합니다. - 중간 결과물들들 저장할 자료구조..

앞선 글에서 살펴본 데이터패스의 제어를 자세히 살펴보도록 하겠습니다. 🧐 ALU 제어 유닛 RISC-V ALU는 제어 입력 4개를 사용하는 다음 4개의 조합을 정의합니다. ALU는 명령어 종류에 따라 위의 네 가지 기능들 중 하나를 수행하게 됩니다. ld, sd 명령어인 경우에는 메모리 주소를 계산하기 위한 덧셈용으로 ALU를 사용합니다. R 타입 명령어의 경우에는 명령어의 funct7 필드([31 : 25])와 funct3 필드([14:12])값에 따라서 네 가지 연산(AND, OR, add, sub)들 중 하나를 수행하게 됩니다. 조건부 분기 명령어(beq)의 경우 ALU는 두 피연산자에 뺄셈을 한 후 결과가 0인지 아닌지를 테스트합니다. 따라서 이들을 통해 ALU 제어 유닛을 만들 수 있습니다. A..

🧐 기본적인 RISC-V 구현 개요 이제부터 다음 핵심적인 명령어들을 실행하기 위한 프로세서를 설계하는 과정을 통해, 프로세서에 대해 알아보도록 하겠습니다. 메모리 참조 명령어 : ld, sd 산술 논리 명령어 : add, sub, and, or 조건부 분기 명령어 : beq 이러한 명령어를 구현하는 데 필요한 것의 대부분은 명령어가 어떤 명령어인지와 상관없이 동일합니다. 모든 명령어의 첫 두단계는 다음과 같이 동일합니다. 1. 프로그램 카운터(PC)를 프로그램이 저장되어 있는 메모리에 보내서 메모리로부터 명령어를 가져옵니다. 2. 읽을 레지스터를 선택하는 명령어 필드를 사용하여 하나 또는 2개의 레지스터를 읽습니다. 그러나 이 이후부터는 명령어의 종류에 따라 수행해야 할 행동들이 달라집니다. RISC-..

🧐 프로세스의 제어 Unix는 C 프로그램으로부터 프로세스를 제어하기 위해 많은 시스템 콜을 제공합니다. 다음은 대표적인 기능들입니다. 프로세스 ID 가져오기 프로세스 생성과 종료 자식 프로세스 제거 프로그램의 로딩과 실행 🧐 프로세스 ID 가져오기 getpid : 호출하는 프로세스의 PID를 반환합니다. getppid : 부모 프로세스의 PID를 반환합니다. (즉 호출하는 프로세스를 만든 프로세스를 반환합니다.) 각각의 프로세스는 고유한 프로세스 ID (PID)를 갖습니다. 위의 함수들을 통해 PID를 얻어올 수 있습니다. 이때 반환 타입은 pid_t 타입의 정수 값이며, 이는 리눅스 시스템에서 types.h에 정수로 저장되어 있습니다. 🧐 프로세스의 상태 프로그래머의 관점에서 프로세스는 다음과 같은 ..

🧐 프로세스 프로세스는 운영체제가 만들어 주는 실행 프로그램의 인스턴스입니다. 프로그램은 오늘날 시스템에서 실행될 때, 마치 단 한 개의 프로그램만이 시스템에서 돌아가고 있는 것 같은 착각이 들게 합니다. 이러한 착각은 프로세스라는 개념에 의해 이루어집니다. 시스템 내의 각 프로그램은 어떤 프로세스의 문맥(context)에서 돌아갑니다. 문맥은 프로그램이 정확하게 돌아가기 위해서 필요한 상태로 구성되며, 문맥 속에는 메모리에 저장된 프로그램의 코드와 데이터, 스택, 범용 레지스터의 내용, 프로그램 카운터, 환경변수, 열려 있는 파일의 식별자가 포함됩니다. 사용자가 실행 목적파일의 이름을 쉘에 입력하여 프로그램을 돌릴 때마다 쉘은 새로운 프로세스를 생성하고, 실행 목적파일을 새로운 프로세스의 문맥에서 실행..

🧐 제어흐름 CPU에 전원을 처음 공급하는 시점부터, 전원이 꺼지는 시점까지 프로그램 카운터(PC)는 연속된 (인스트럭션의) 주소값들을 실행합니다. 명령어 1 명령어 2 명령어 3 ... 명령어 n 명령어 1에서 명령어 2로의 전환을 제어이동이라 부릅니다. 그리고 위와 같은 제어이동의 배열을 (프로세서의) 제어흐름이라 부릅니다. 🧐 예외적인 제어 흐름, ECF 가장 간단한 유형의 제어흐름은 명령어 1과 명령어 2가 메모리에 서로 나란히 있는 경우입니다. 제어흐름 속에서 jump, branches, call, return 등의 명렁어가 실행되면 위와 같은 점진적인 제어흐름이 변경되고, 서로 나란히 존재하지 않는 명령어가 실행됩니다. 그러나 시스템은 위처럼 명령어로 인한 상태 변화가 아닌, 프로그램의 실행과..

🧐 부동소수점 덧셈 덧셈의 경우에는 다음과 같은 과정을 통해 이루어집니다. 1. 더해지는 두 수 중 지수가 큰 수에 맞추어, 지수가 작은 수를 변경합니다. 이때 자리이동 이후 버려지는 수가 있을 수 있습니다. 2. 유효자리(frac)을 서로 더합니다. 3. 이 합은 정규화되지 않았을 수 있으므로, 이를 정규화 시킵니다. 이때 오버/언더플로우 여부를 확인하여야 합니다. 4. 비트 수의 표현범위가 넘어가는 경우 근사를 통해 자리수를 맞추어 주고, 또한 다시 정규화가 필요하다면 3, 4의 과정을 반복하여 진행합니다. 예를 들어 다음 두 부동소수점을 더해보도록 하겠습니다. $ 1.000 \times 2^{-1} + -1.110 \times 2^{-2} \;\;\;(0.5 + -0.4375)$ 1. 큰 수의 지수..