[SPARC] 28. 다차원 배열과 이진수 곱셈 계산

지난 글에서는 일차원 배열에 대한 내용을 정리하였다.

일차원배열을 스택에 선언하는 경우, 배열의 주소는 낮은곳부터 높은 곳순으로 증가하지만, 배열 공간이 선언되는 위치는 지역변수가 선언되는 것과 마찬가지로 높은 주소부터 쌓이는 식으로 선언되었다.

 

이번 글에서는 다차원 배열에 대해 정리하고자 한다.

---

다차원 배열의 표현

다차원배열은 결국 선형구조인 메모리에 저장되어야 한다.

이때 선형 구조인 메모리에 어떻게 저장하느냐에 따라 크게 2가지로 나눌 수 있다.

 

1. row major

2. column major

 

row major 는 우리가 흔히 사용하는 방식으로, 먼저 row 를 기준으로 구역을 나눈 뒤, column 인덱스가 증가할 때 메모리 주소가 순차적으로 증가하고, 모든 column이 다 차면 그때 row 인덱스가 증가하는 방식이다.

 

column major 는 OpenGL, MATLAB, R 과 같은 언어에서 사용하는 방식으로, Column을 기준으로 구역을 설정한뒤, Row가 증가할 때 메모리 주소가 순차적으로 증가하고, 모든 Row가 다 증가하고나면 그때 column의 메모리 주소가 증가하는 방식이다.

---

다차원 배열의 주소 계산

다차원 배열의 경우에도, 우리가 이해하기 쉽게 다차원으로 표현하지만, 사실은 선형적인 메모리 공간에 데이터가 들어있다.

그래서 주어진 인덱스가 선형적인 메모리 공간에 펼쳐놓았을 때, 그 원소까지 몇개의 원소가 들어있었는지 원소 개수를 계산하면, 이 값에 각 원소의 사이즈(이 글에서 W로 표현한다.) 를 곱하여 주소를 계산할 수 있다.

 

만약 int 형의 배열이라면 W 값은 4가 될 것이고,

만약 short 형의 배열이라면 W 값은 2가 될 것이다.

선언되는 자료형의 사이즈를 잘 보고 W 값을 설정하자.

---

우선 2차원 배열부터 생각해보자.

0 <= i < R / 0 <= j < C 범위 일 때, A[i][j] 의 주소는 어떻게 계산할 수 있을까?

주소 계산 방법은 row-major 와 column-major 에 따라 달라진다.

row-major 방식인 경우

A[i][j] 에서 i 가 증가하는 조건은 모든 j 가 다 찼을 때이다.

즉, C 개의 원소가 배열에 찰 때마다 i 가 증가한다고 볼 수 있다.

따라서 A[i] 인 경우에는 메모리에 i*C 개의 원소가 이미 들어있다는 말이다.

여기에 j 개의 원소가 더 있는 것을 고려해주면, 메모리에는 i * C + j 개의 원소가 들어있음을 알 수 있다.

주소값은 바이트 단위이므로, 원소 하나의 사이즈를 곱해주면 주소값을 알 수 있다.

 

따라서

 

A[i][j] 의 주소값은 (&A[0][0]) + (i*C+j) * W

 

i 개의 row에 대해서 C (row 당 Column 개수) 만큼 곱하고, 추가적으로 j 개의 단위 메모리 공간을 앞서 차지하고 있다.

따라서 실제 차지 공간은 단위 메모리 공간 * 각 단위 메모리 사이즈(W) 를 하면 된다.

column-major 방식인 경우

A[i][j] 에서 i 가 증가하는 것은, 메모리에 원소가 하나 새로 추가되었다는 의미이다.

j 가 증가하는 것은, 메모리에 R개의 원소가 찰 때마다 j 가 증가하므로, 메모리에 원소가 R개 추가되었다는 의미이다.

따라서 A[i][j] 원소까지 메모리에 들어있는 원소의 개수는 j * R + i 개 이다.

여기에 원소의 바이트값을 곱해주면 메모리 주소값을 구할 수 있다.

 

따라서

 

A[i][j] 의 주소값은 (&A[0][0]) + (j*R + i) * W

 

j 개의 column에 대해서 R (column 당 row 개수) 만큼 곱하고, 추가적으로 i 개의 단위 메모리 공간을 앞서 차지하고 있다.

마찬가지로 여기에 실제 단위 메모리 사이즈인 W 를 곱해주면 된다.

---

그렇다면 3차원 배열의 경우에는 어떻게 계산할까?

3차원 배열도 마찬가지로 생각해서 계산하면 된다.

 

0 <= i < R / 0 <= j < C / 0 <= k < H 범위의 3차원 배열을 생각해보자.

A[i][j][k] 위치의 원소까지 메모리에는 몇 개의 원소가 있을까?

i 가 1 증가하려면 j는 C까지 증가하여야 한다.

j 가 1 증가하려면 k는 H까지 증가하여야 한다.

 

따라서 i 가 1 증가하였다는 의미는 이전에 C*H 개의 원소가 있었음을 알 수 있다.

따라서 i 값을 통해서 메모리에 i * C * H 개의 원소가 우선 들어있음을 알 수 있다.

 

이제 j 를 고려해준다.

j 가 1 증가하려면 k는 H까지 증가하여야 하므로 (메모리에 원소가 H개 더 들어와야 하므로)

메모리에는 j * H 개의 원소가 추가적으로 더 들어있었음을 알 수 있다.

 

마지막으로 k 가 1 증가하려면 메모리에 원소가 1개 추가되면 되므로

메모리에는 k 개의 원소가 추가적으로 더 들어있었음을 알 수 있다.

 

따라서

 

A[i][j][k] 의 주소값은 { (i * C * H) + (j * H) + k } * W

---

프로그램 예제

앞서 다차원 배열의 전체 사이즈 범위를 알 때, 특정 위치 원소의 주소값을 계산할 수 있었다.

이제 다차원 배열과 관련된 다음 C 코드를 어셈블리로 바꾸어보자.

void main() {
    static int score[3][4] = {
        {68, 55, 90, 88},
        {78, 77, 89, 91},
        {93, 95, 89, 98},
    };
    
    int sum[3] = {0};
    
    register int i, j;
    
    for (i = 0; i < 3; i++) {
        for (j = 0; j < 4; j++) {
            sum[i] = sum[i] + score[i][j];
        }
    }
}

 

3 x 4 배열을 선언하고, 각 행의 합을 구해서 1차원 배열에 저장하는 코드이다.

이중 for문을 돌어야 하는 부분이 어셈블리로 구현하기 귀찮은 부분일 것 같다.

 

우선 항상 하던대로, stack 사이즈부터 계산해보자.

먼저 static int score[3][4] 의 경우, static 즉, 정적 메모리 공간에 저장하는 데이터이다.

따라서 이 공간은 스택과 관련이 없다.

 

int sum[3] 의 경우, 스택에 3개의 4byte 공간을 사용한다.

 

register int i, j 의 경우, 레지스터를 사용하므로 스택 사이즈와 관련이 없다.

 

주어진 코드에서는 스택 안에서 별도의 함수 호출이 없으므로, 스택의 최소사이즈인 64byte에 3개의 4byte 공간을 지역변수로 더하면 64 + 3*4 = 64 + 12 = 76 byte의 공간이 필요하다.

하지만 어셈블리 코드를 작성할 때는, printf 를 호출하여 그 합을 출력해보고자 하기 때문에, 92byte 에 12 byte 를 더해계산하기로 하자.

그러면 104byte의 스택프레임이 필요하고, 이는 8의 배수이다.

 

이제 이 사이즈를 8의 배수로 맞추어주면 선언해야하는 스택 프레임의 사이즈는 80 byte 이다.

 

이제 각 변수 공간을 선언하여 그림과 같이 기본틀을 잡을 수 있다.

i, j 는 각각 %l0, %l1 을 사용하는 것으로 하고, 이 두 l-register는 다른 용도로 사용하지 않도록 하자.

 

그럼 이제 각 변수 공간을 코드에 맞게 초기화시켜줄 수 있다.

 

sum 배열을 초기화 시켜주었다.

 

이제 이중 for 문에서 바깥쪽 loop를 돌아보자.

 

다음과 같이 작성할 수 있다.

i = 0 으로 초기화를 하고, i >= 3 이면 반복문을 빠져나오도록 코드를 작성하였다.

 

이제 반복문 내에서 또 다른 iner_loop를 돌아보자.

 

이렇게 작성할 수 있다.

inner_loop 를 돌기 전에 j 값을 0으로 초기화 해주고, j >= 4 가 되는 순간 inner_loop를 빠져나오도록 한다.

inner_loop 를나오는 순간 outer_loop의 마지막으로 가면 되므로 outer_loop 의 마지막 증감식 부분에 break_inner_loop 라벨을 달아주었다.

 

이제 score배열의 값을 읽어서 sum 배열에 값을 더해주는 코드를 짜보자.

 

코드가 조금 길지만 주석을 보면서 생각하면 어렵지 않다.

 

먼저 sum[i] 에 접근하기 위해 이 주소값을 계산한다. (이 부분은 사실 outer_loop 에서 수행하는 것이 더 효율적이긴 하다)

 

다음으로 score[i][j] 에 접근하기 위해 주소값을 계산한다.

위에서 정리하였던 다차원배열 주소값 계산 방식을 이용해 주소값을 계산한다.

 

이제 계산한 두 주소값을 이용하여 sum[i] += score[i][j] 를 수행한다.

 

이제 이것으로 주어진 C 코드를 수행하는 코드는 작성이 완료되었다.

각 i 루프에다가 breakpoint 를 걸고 코드를 실행해보자.

계산이 아주 잘 되었다.

 

 

그 다음 루프에서는 335가 나왔다.

 

아주 잘 나온다.

 

마지막 세번째 루프에서는 375라는 값이 나왔다.

 

마지막 루프까지 값을 잘 구했다.

 

매번 이걸 손수 출력하는 것은 귀찮다.

이제 inner_loop가 끝날 때마다, 구한 합 을 출력해보자.

 

이렇게 작성해주면 된다.

 

출력이 잘 된다.

 

만약 우리가 구하는 배열의 사이즈가 int 가 아니라 short, char, double 등으로 달라지게 되는 경우,

W 의 값 뿐만 아니라, ld / st 명령어도 ldsh / sth 등으로 바뀌는 것에 주의하자.

---

이진수를 사용하는 경우의, 효율적인 주소값 계산 방법

이진수를 사용하는 경우, 주소값을 어떻게 하면 더 효율적으로 계산할 수 있을까?

바로 bit shfit 연산을 사용하는 것이다.

 

만약 %l3 에 4를 곱해야 한다면

sll %l3, 2, %l3 을 하는 것이

mul 함수를 호출하여 곱셈을 계산하는 것보다 효율적이다.

 

만약 %l3 에 5를 곱해야 한다면,

기존 값에 4를 곱하고, %l3을 한번 더 더해주면 된다.

sll %l3, 2, %o0

add %o0, %l3, %l3

 

더 일반적인 이진수의 곱셈은, 곱하는 수 (Multiplier) 의 제일 오른쪽에 있는 비트부터 (rightmost-bit) 시작하여 왼쪽으로 비트를 하나씩 살펴보며 아래와 같은 과정을 반복한다.

 

만약 해당 비트가 1 이라면, 결과값에 곱해지는 수 (multiplicand) 를 더해주고, multiplicand 를 왼쪽으로 한번 shift 한다.

만약 해당 비트가 0 이라면, 그냥 multiplicand 를 왼쪽으로 한번 shift 한다.

 

즉, 초등학교때 배웠던 곱셈 연산을 이진수에 대해 적용시켜주는 것과 같다.

---

만약 %o0에 100을 곱한 결과를 %o1 에 저장한다고 해보자.

100 = 64 + 32 + 4 이므로, 이진수로 나타내면 1100100 으로 나타낼 수 있다.

 

1. 우선 %o1 을 0으로 설정한다.

clr %o1

 

2. 곱하는 수의 첫번째로 1이 나오는 비트는 제일 오른쪽에서 2번째에 있다.

 

곱해지는 수를 왼쪽으로 2번 shift 한다.

sll %o0, 2, %o0

 

곱해지는 수를 결과값인 %o1에 더한다.

add %o1, %o0, %o1

 

3. 곱하는 수의 두번째로 1이 나오는 비트는, 첫번째로 1이 나온 비트 위치에서 왼쪽으로 3번째에 있다.

 

따라서 곱해지는 수를 왼쪽으로 3번 shift 한다.

sll %o0, 3, %o0

 

곱해지는 수를 결과값인 %o1에 더한다.

add %o1, %o0, %o1

 

4. 곱하는 수의 세번째로 1이 나오는 비트는, 두번째로 1이 나온 비트에서 왼쪽으로 1번째에 있다.

따라서 곱해지는 수를 왼쪽으로 3번 shift 한다.

sll %o0, 1, %o0

 

곱해지는 수를 결과값인 %o1에 더한다.

add %o1, %o0, %o1

 

이렇게 bit-shift 연산과 덧셈만을 이용하여 곱셈을 계산할 수 있다.