코딩하는 감자

서로 다른 알고리즘을 분석할 때 우리는 더 효율적인 프로그램을 만들기 위해서 어떤 알고리즘이 낫다, 더 나쁘다를 객관적으로 비교해야 한다. 하지만 단순하게 프로그램을 실행시켜서 속도를 비교하기엔 입출력과 HW성능, 환경 등 실행 속도에 너무 많은 변수들이 있다. 이를 위해 좀 더 객관적인 환경에서 비교할 수 있도록 개발된 표기법이 Big-O표기법이다. 빅오 표기법에 대해 먼저 간단하게 말하자면 앞서 말했던 실행 속도의 개념보단 수행되는 연산의 개수를 대략적으로 판단하는 느낌이다. 예를들어 다음과 같은 코드가 있다고 치자 for(int i = 0; i < N; i++){ for(int i = 0; i < N; i++){ } } for(int i = 0; i < N; i++){ } int a = 0; 이러한..

컴퓨터 단어는 이진수로 표현된다. 어떻게 컴퓨터에서 이진수로 산술 연산을 효율적으로 수행하도록 설계할 수 있을까? 덧셈 뺄셈 두 번째 피연산자를 부정하여 이진 덧셈을 수행한다. (2의 보수에서는 양수(음수)를 부정하는 것이 쉽다.) 더보기 XOR연산은 둘 중 하나만 참일 때 참, 둘다 참이거나 둘 다 거짓이면 거짓 half adder 캐리 입력이 없는 1비트 가산기 입력 : 2개의 1비트 데이터 A, B 출력 : 합S, 캐리C 더보기 Carry input(캐리 인풋)은 일반적으로 Full adder(풀 애더)라고 알려진 논리 회로에서 사용됩니다. Full adder는 Half adder를 확장한 것으로, 3개의 입력 (A, B, Carry input)와 2개의 출력 (Sum, Carry)을 가지며, 두 ..

더보기 "Offset"은 컴퓨터 구조 및 데이터 구조에서 자주 사용되는 용어로, 주로 메모리 주소 또는 데이터 구조에서 특정 위치의 상대적인 위치를 나타냅니다. Offset은 일반적으로 다음과 같은 맥락에서 사용됩니다: 메모리 주소: 프로그램이나 데이터가 메모리에 저장될 때, 각 항목은 메모리 주소를 가집니다. "Offset"은 이 메모리 주소에서 특정 위치까지의 거리를 의미합니다. 예를 들어, 특정 배열의 요소에 접근하려면 배열의 시작 주소와 해당 요소의 offset을 합산하여 원하는 위치에 접근할 수 있습니다. 구조체 및 레코드: 프로그래밍 언어에서 구조체(struct)나 레코드(record)를 사용할 때, 각 필드는 상대적인 오프셋을 가집니다. 이것은 구조체 또는 레코드 내에서 필드의 위치를 정의하..

Instruction Set Architecture (ISA) 컴퓨터의 언어, 또는 SW와 HW간의 인터페이스는 명령어의 유형 ( 산술, 조건, 데이터 전송, 분기 등), 명령어에 데이터를 사용하는 방법, 데이터 형식, 명령어의 형식을 정의한다. 전 포스트에서 말했듯이 명령어는 프로그램의 성능에 영향을 미친다. 우리는 컴퓨터마다 다르긴 하지만 매우 유사한 instruction set을 사용하여 ISA의 설계를 연구할 것이다. 이를 통해 컴퓨터의 성능을 높일 수 있을 것이다. 우리는 이에대한 ISA의 설계는 MIPS를 이용한다. 아래는 MIPS의 기본 설계 원칙이다. 1. 단순성은 규칙성에 우호적이다. 2. 작을수록 빠르다. 3. 일반적인 사례를 빠르게 만든다. 디자인 원리1. 단순성은 규칙성에 우호적이다..

성능을 정의하기 위한 두 가지 지표가 있다. 1. 응답시간 response time 작업의 시작부터 완료까지의 시간 ex) 단일작업을 수행하는 데 걸리는 시간 2. 처리량 throughput 단위 시간당 수행된 작업의 총량 ex) 시간당 작업, DB서버의 시간당 쿼리 처리량 하지만 우리는 주로 응답시간에 대해 중점을 두어 공부할 것이다. 성능 performance은 실행시간(응답시간)의 역수이다. 프로그램을 실행하는 동안 일어나는 일(실행시간 동안)을 나타낸 그림이다. 여기서 경과시간 elapsed time = 시스템 성능 = t1 + t2 + t3 + t4 모든 것을 포함하여 작업 시작부터 완료까지의 총 시간 CPU시간 = CPU 성능 = t1 + t4 프로세서에서 특정 작업을 처리하는 데 소요된 시간..

프로그램의 performance를 증가시키는 컴퓨터 구조를 설계하기 위해 이 과목을 배운다. 이에 앞서, 우리는 먼저 컴퓨터에서 프로그램의 실행이 일어나는 절차와, 프로그램의 performance에 영향을 미칠 수 있는 컴퓨터의 기초적인 구성요소에 대해 알아야 한다. HW와 SW의 구성을 단순화하여 알아보자. 가장 안쪽에 있는 하드웨어는 프로세서, 메모리, I/O 장치로 이루어져 있다. 그 위에 있는 시스템 소프트웨어는 고급언어를 기계어로 번역하는 컴파일러와 입출력 작업, 리소스 관리( ex)storage, memory), 프로세서 예약을 하는 운영체제로 이루어져 있다. 가장 상위에 있는 응용 소프트웨어는 고급 언어로 작성됐다. 프로그램이 실행되면 1. 언어를 고급언어에서 기계어로 번역한다. 2. 다음으..

일반적으로 프로세스는 실행 중인 프로그램으로 정의한다. 프로그램 자체는 디스크 상에 존재하는 명령어와 정적 데이터의 묶음 덩어리일 뿐, 운영체제가 실행하여 프로그램에 생명을 불어넣는 것이다. 우리는 이러한 프로세스를 동시에, 사용 가능한 cpu가 있는지 없는지 신경 쓰지 않고 여러가지를 실행시키고 싶다. 이러기 위해서 실제로 적은 개수의 cpu 밖에 없더라도 cpu가 여러 개 존재한다는 환상을 심어줘야 한다. 이를 가상화한다고 한다. 하나의 프로세스를 실행하고, 얼마 후 중단시키고 다른 프로세스를 실행하는 작업을 반복하면서 실제 하나 또는 소수의 cpu로 여러 개의 가상 cpu가 존재하는 듯한 환상을 만들어 낸다. 시분할 (time sharing)이라 불리는 이 기법은 원하는 수 만큼의 프로세스를 동시에..

폰 노이만의 컴퓨팅 모델은 쉽게 말하자면 반입, 해석, 실행의 반복이다. 운영체제는 이러한 시스템을 사용하기 쉽게 하기위해 여러가지 일이 발생하는 과정들을 배울 것이다. 다시 말하자면 프로그램을 쉽게 실행하고, 프로그램 간의 메모리 공유를 가능케 하고, 여러가지 일을 처리할 수 있는 시스템을 사용하기 편리하면서 올바르게 동작시킬 책임이 있기 때문에 소프트웨어를 운영체제 operating system이라고 부른다 사용하기 쉽게 하는 일 중 하나는 가상화이다. 운영체제는 프로세서, 메모리, 디스크같은 물리적인 자원을 이용하여 사용이 편리한 가상 형태의 자원을 생성한다. 이 때문에 운영체제를 가상머신이라고 부른다. 사용자 프로그램의 실행, 메모리 할당, 파일 접근과 같은 가상 머신과 관련된 기능들을 운영체제에..

그래픽은 실제같은 느낌의 표면을 모델링 하기 위해 텍스쳐 매핑을 사용한다. 텍스쳐 매핑은 각 지점에 색을 할당하는 기능을 원한다. 표면은 2d 영역이므로 기본적으로 이미지이다. 텍스쳐(질감) 맵의 각 픽셀을 텍셀이라고 한다. 각 텍셀은 (u,v)2d 텍스쳐 좌표와 연관된다. 정규화로 인해 u,v의 범위는 [0.0 , 1.0]이다. 이와 같은 u,v의 범위에서 이미지 너비와 높이를 곱한다. i=0,…,N, j=0,…,M 인 경우 F[i,j] 를 두고 u,v좌표 위에서 우리가 계산하려는 가장 가까운 점 F(u,v) = F[ round(N*u), round(M*v) ] 선형 보간 Linear Interpolation은 위의 nearest neighbor 점을 구하기 위해 i = floor(N*u) , j = ..

1-1) mathematical proof의 정의 chain of logical deductions leading to the proposition from a base set of axioms 1-2) predicate 의 정의 proposition whose truth depends on the value of one or more variables 1-3) Proposition 의 정의 statement that is either true or false 1-4) good proof의 ‘조건’ basis of deduction is the mathematical consistency Correct, Complete, Clear, Brief, Elegant, Well organized, Inorder..