[Parallel Computing] (4-2) Arithmetic Operation(1)

이번 글에서는 전반적인 Arithmetic Operation에 대해서 살펴보겠다.

 

1. Modular Arithmetic
Modular Arithmetic은 정수의 합과 곱을 어떤 주어진 수의 나머지에 대하여 정의하는 방법이다. 나머지를 정의하는 방법이기 때문에, 나눗셈(Euclidean division)을 사용한다. 주로 mod라고 표현한다. 
Euclidean division은 두 개의 정수 m, n(0이 아닌)이 존재할 때, m = q*n + r 그리고 0 < r < |n| 을 만족시키는 유일한 정수 q, r이 존재한다. 다시 말하면, 정수 m <피제수>을 n <제수>으로 나눴을 때, 몫은 q, 나머지는 r이다. 0으로 나눌 수 없기 때문에 n은 0이 아니여야 하며, 나머지 r은 몫 q보다 작으므로 위와 같이 표기하였다. 또 특이한 점은 나머지 r은 양수로 기술되어 있다. 음수에서의 나눗셈이 이뤄지더라도 나머지는 양수가 되도록 표현해야 한다. 예제를 살펴보면, Euclidean division에서는 피제수 -7을 제수 3으로 나눈다면, -7 = 3*(-3) + 2 로 표현될 수 있다. 물론 일반적인 division에서는 -7 = 3*(-2) - 1로 표현될 수 있다. 수학적으로 몫을 구하는 방법을 사용하면, 아래와 같다. a를 b로 나눈 다음, 가장 가까운 제일 큰 정수로 치환하면 된다. 위의 예시로 살펴보면 -7/3 = -2.33이다. 해당 결과 값에 floor function을 수행하면 값을 얻을 수 있다. -2.33이므로 해당 값에 가장 가까운 작은 값은 -3이다. 

수학적 제수 표현

 x mod m = y mod m인 경우, 즉 나머지가 같으면 합동 관계(Congruence Relation)라 표현한다. 

Congruence Relastion

이를 활용하여 Modulo-m Operation을 수행할 수 있다. m개의 숫자(0,1,2,...,m-1)가 계산에 사용된다. 예를 들어 module-8 addition이라면 9 + 6을 수행하는 방법이 두 가지가 있다. 하나는 먼저 더하고 mod 8을 수행하거나 각각 mod8를 수행하고 더하는 경우가 있다. 즉, 9 mod 8 + 6 mod 6 = (9+6) mod 8이다.

 

2. Logical Operation on Binary Integers

N-bit binary 숫자 간에 logical operation(NOT, AND, OR, NOR, NAND, XOR, XNOR)은 bit-wise 연산을 수행한다. C 언어에서는 NOT(~), AND(&), OR(|)그리고 XOR(^)를 지원한다. 이 때, Operands는 Integer type이어야 한다. 

 

3. Shift Operation on Binary Intergers

Shift Operation은 특정한 방향(오른쪽 or 왼쪽)으로 주어신 값만큼 이동시키는 동작이다. 이를 표기하면

x >> m :: 오른쪽으로 m-bit만큼 이동.

x << m :: 왼쪽으로 m-bit만큼 이동.

해당 m-bit만큼 이동을 하고 나서 생각해보면, 이로 인해 빈 값들은 어떤 숫자로 채워야 하는지 결정해야 한다. 

예를 들어 1001 >> 2를 수행하면, xx10이고, x에 어떤 값을 채워야하는 지를 결정해야 한다. 채우는 방식에 따라 Logical shift와 arithmetic shift로 나뉜다. 

 logical shift는 채울 값을 무조건 '0'으로 채운다. 예를 들면, 아래와 같다.

1001 >> 2 = xx10 = 0010

1001 << 2 = 01xx = 01xx 

 arithmetic shift는 부호값을 유지하여 채울 값을 정한다. 예를 들면, 아래와 같다.

1001 >> 2 = xx10 = 1110

1001 << 2 = 01xx = 0100 

이 때, 왼쪽 이동으로는 무조건 '0'으로 채운다. 또 '0'으로 채우게 되면, left shift operation으로 2^n 곱하기 연산을 표현할 수 있어서 효율적이다. 그렇다면 right shift operation으로 2^n 나누기 연산을 표현할 수 있을까? 결론적으로 말하면, 몫을 구할 수 있다. 예를 들어, 아래와 같다. 

i) 119 / 8 = 14.875

   unsigned expression ::                       1110111(126) >> 3 = 0001110(14)

ii) -9 / 8 = -1.125 = -2 + 0.875

   2's complement signed expression :: 1110111(-9) >> 3  = 1111110(-2)

unsigned/signed expression에서의 나눗셈 연산을 살펴보면, shift operation 결과는 모두 몫에 해당되었다. 특히 2's complement signed expression은 위에서 언급한 일반적인 나눗셈이 아니라 Euclidean division의 형태로 수행되었다. 

c 언어(C99)에서는 negative number에 대한 right shift의 동작에서 대해서 정의하지 않았으므로 C compiler가 어떻게 수행되는 가에 따라 결정된다.

 

다음 글에서는 Addition, Multiplication 그리고 division 에 대해서 알아보겠다.