10진수 소수 2진수 소수 상호 변환 이번 글에서부터는 컴퓨터가 '실수'를 어떻게 표현하는지 정리하고자 한다. 이진수를 다루는 컴퓨터가 실수를 어떻게 표현하는지를 알기 위해 먼저 10진수의 소수가 어떤 식으로 표현되고 있는지를 생각해보자. 10.155 라는 소수는 1 x 10^1 0 x 10^0 1 x 10^-1 5 x 10^-2 5 x 10^-3 이렇게 표현된다는 건 자연스럽게 알고 있다. 이는 이진수에서도 마찬가지로 작용한다. 10.111 이라는 이진수 소수는 1 x 2^1 0 x 2^0 1 x 2^-1 1 x 2^-2 1 x 2^-3 이렇게 표현된다. 그리고 이 값을 10진수로 잘 계산해주면 우리가 사용하는 10진수 소수값이 나온다. 그리고 이 과정을 통해 자연스럽게 2진수를 10진수로 변환하는 방..

이번에는 지금까지 정리한 내용에 더불어 C 라이브러리를 활용하여 버블소트를 SPARC로 구현할 것이다. C 코드 #include #incdlue #incdlue struct sort_info { unsigned int num_items; unsigned int max_value; }; unsigned int askNumber(char* message) { unsigned int val; register int result; do { printf("%s", message); result = scanf("%u", &val); } while (result != 1); return val; } struct sort_info askInfo() { struct sort_info si; si.num_items = a..

지난 글에서는 서브루틴에서 구조체를 다루는 방법을 정리하였다. %sp+64 위치에 구조체 시작 주소를 넘겨서 직접 해당 구조체를 다루는 것이 포인트였다. 서브루틴 내에서는 %fp+64로 접근하는 것이 차이점이었다. 이번 글에서는 리프 서브루틴에 대해 정리하고자 한다. Leaf Subroutine 트리에서 자식 노드가 없는, 즉, degree = 0 인 노드를 leaf 노드라고 한다. 함수의 call graph 를 그렸을 때, leaf 노드에 해당하는 함수는 가장 마지막에 호출되어 더 이상 함수를 추가로 호출하지 않는 함수를 의미한다. 리프노드는 그냥 평범한 서브루틴과 비슷하게 구현하면 된다. 그런데 만약 리프노드에서 수행하는 작업이 너무 간단해서 새 스택 프레임을 할당할 필요가 없어 save, resto..

지난 글에서는 6개를 넘는 매개변수를 서브루틴에 넘기는 방법과 그 예제를 살펴보았다. 이번 글에서는 서브루틴의 값 반환 중 '구조체'를 반환하는 경우를 중점적으로 정리해보고자 한다. 서브루틴의 값 반환 서브루틴에서 값을 반환할 때, word 하나 사이즈의 데이터를 반환하는 것은 %i0 레지스터를 통해 값을 넘기면 되었다. 그리고 서브루틴을 호출한 함수 입장에서는 %o0 위치에서 반환 값을 읽어올 수 있었다. 그렇다면 아래 C 코드와 같이 구조체를 반환하는 경우는 어떻게 받아올 수 있을까? struct point { int x; int y; }; struct point zero() { struct point local; local.x = 0; local.y = 0; return local; } struct..

Binary Search 이분 탐색은 어떤 정렬된 데이터에 대해 특정 값을 찾을 때, 반씩 나누어 탐색하여 log 시간에 데이터를 찾는 알고리즘이다. 사이즈 n 의 다음과 같은 배열이 있다고 해보자. K1 K 이면, 찾는 값은 Km 기준 왼쪽에 있다. 따라서 u = Km - 1 으로 설정한다. ..

지난 글에서는 register set 과 register window overflow / underflow 에 대해 정리하였다. SPARC는 CWP, WIM 2가지 값을 이용해 오버플로우나 언더플로우가 발생하는지 확인하고, 처리하였다. 이번 글에서는 서브루틴에 매개변수를 전달하는 방법을 정리하였다. 서브루틴의 매개변수 전달 서브루틴의 매개변수를 전달할 때, 전에는 그냥 %o0 ~ %o5 를 사용한다고 정리하였다. 그런데 만약 매개변수의 개수가 6개를 넘어가면 어떻게 해야할까? SPARC에서는 매개변수의 순번에 따라 데이터를 넘기는 방식이 다르다. 6번째 매개변수까지 6번째 매개변수까지는 전에 정리했던대로 o-register 를 이용하여 매개변수를 전달한다. %o0~%o5 를 사용할 수 있다. %o6 은 ..

자료구조와 탐색 시간 지금까지 자료구조를 정리하면서 주요하게 다뤘던 내용 중 하나는 바로 "탐색" 이었다. 그리고 원하는 자료를 탐색하기 위해 수행한 가장 근본적인 동작은 바로 키를 비교하는 것이었다. 어떤 키가 다른 키와 같은지 다른지, 혹은 큰 지 작은 지를 비교하여 원하는 값을 탐색해내갔다. 여기 3글자 알파벳 소문자로 이루어진 이름과 4개의 숫자 쌍을 저장하는 간단한 주소록 프로그램이 있다. 그리고 이 주소록 프로그램에서 주소록 정보를 BST를 이용해 저장한다고 해보자. 만약 1000개의 주소록 데이터를 BST에 저장한다면, 최적의 경우 BST의 높이는 log(1000) 이므로 대략 10이라고 할 수 있고, 최악의 경우의 높이는 대략 1000이 될 것이다. 또 평균적으로는 1000개의 데이터를 B..

지난 글에서는 함수를 호출하는 call 명령어와, 이와 비슷하게 코드의 실행을 조정하는 jmpl 명령어, 그리고 이전 주소로 복귀하는 ret 명령어와 retl 명령어에 대해 정리하였다. 이번 글에서는 call 명령어를 호출한 이후, 함수의 시작을 알리는 역할로 불리는 save 명령어에 대해 정리하고자 한다. 'Save' Instruction save 명령어는 서브루틴을 위한 공간을 할당하는 명령어로서, 함수의 시작을 나타낸다. save 명령어는 2가지 기능을 한다. 첫번째 기능은 스택 메모리에 사용자가 지정한 사이즈 (스택 프레임의 사이즈) 만큼 공간을 할당한다. 공간을 할당하는 것은 %fp, %sp 의 이동과 같다. %fp 은 스택 프레임의 시작점, %sp 는 스택 프레임의 끝 점을 의미한다. 스택 공..

지난 글에서는 우선순위 큐와 이를 효율적으로 구현하기 위한 자료구조인 Heap 에 대해 정리하여 보았다. 이번 글에서는 한번 파이썬의 Heapq 를 뜯어보고자 한다. 뜯어보는 방법은 간단하다. 파이썬의 heap 모듈인 heapq 를 선언하고, ctrl 키를 누르고 클릭하면, 해당 모듈의 코드를 읽어볼 수 있다. Heap 개념 설명 코드 상단부에는 이렇게 heapq 모듈에 대한 설명과 사용 방법이 소개되어 있다. 위에 정의를 보면 우선순위큐를 heap queue 알고리즘이라고도 표현하는 것을 볼 수 있다. 파이썬의 공식 모듈에서 정의한 Heap은 모든 k 에 대해 a[k]

우선순위 큐 우선순위 큐는 우선순위를 가지는 아이템들을 가지는 큐이다. 일반적인 큐와 마찬가지로 push(), pop() 두가지 기능을 제공하지만, 우선순위 큐는 데이터를 저장할 때 단순히 데이터의 값 뿐만 아니라 데이터의 우선순위를 같이 저장하는 점이 다르다. 그래서 우선순위 큐에는 push(x, p) 와 같은 형태로 데이터를 저장한다. x 는 저장하는 데이터, p 는 저장하는 데이터의 우선순위이다. 그리고 pop을 할 때는 우선순위가 높은 데이터부터 나온다. 우선순위 큐의 구현 우선순위 큐의 개념은 간단하다. 그런데 우선순위 큐의 구현은 간단하지 않다. 만약 일반적인 큐를 구현할 때처럼 연결 리스트를 사용한다면 어떨까? 데이터를 pop 할 때, 우선순위가 높은 순부터 뽑아야 하므로 아래 2가지 방법중..