플롭 (Flop)

선형대수 수치 알고리즘의 복잡성을 표현하는 방법 중의 하나로 알고리즘을 수행하는 데 필요한 부동소수점 연산의 총 횟수를 사용한다. 부동소수점 연산 (floating point operation)을 간단히 플롭(flop)이라고 하는데, flop은 두 개의 부동소수점 숫자의 덧셈, 뺄셈, 곱셈 또는 나눗셈 등을 한 번 수행하는 것으로 정의한다.

컴퓨터의 성능을 수치로 나타내는 단위로서 사용되는 FLOPS도 있다. 이 때의 FLOPS는 FLoating point Operations Per Second의 약자로 해당 컴퓨터가 처리할 수 있는 초당 얼마나 많은 연산을 처리하는 지를 나타내는 단위다.

 

 

여기서는 부동소수점 연산(flop)의 횟수(count) 라는 의미의 flops에 대해서 설명한다.

플롭의 횟수, 즉 flops는 원래 부동소수점 연산이 상대적으로 느렸던 예전에 대중화되었기 때문에 당시에는 알고리즘의 총 계산 시간을 잘 예측할 수 있었지만, 현대의 컴퓨터 경우는 연산 속도가 빨라져서 연산 횟수 보다는 그 외적인 요인이 알고리즘 계산 시간에 더 큰 영향을 미치기 때문에 flop 횟수만으로 수치 알고리즘의 계산 시간을 예측하는 것은 부정확할 수 있다. 그럼에도 flop 횟수가 알고리즘 계산 시간에 대한 대략적인 추정치를 제공하고 알고리즘 상호간의 상대적인 계산 시간 비교를 할 수 있는 기준 단위가 될 수 있기 때문에 여전히 사용된다.

대신에 flop 횟수를 정확히 카운트하기 보다는 가장 큰 지수 항을 제외한 다른 항은 무시하여 횟수의 표현을 단순화한다.

 

 

예를 들어보자. 두 벡터 \(\mathbf{x}, \ \mathbf{y} \in \mathbb{R}^n\) 의 내적 연산은 곱하기가 \(n\) 번, 더하기는 \(n-1\) 번이므로 flop 수는 \(2n-1\) 이다. \(n\) 이 크다면 flop 수는 \(2n\) 으로 본다.

벡터 \(\mathbf{x} \in \mathbb{R}^n\) 와 행렬 \(A \in \mathbb{R}^{m \times n}\) 의 곱셈 연산 \(A\mathbf{x}\) 에서는 \(2n-1\) 번의 내적 연산을 \(m\) 번 반복하는 것이기 때문에 flop 수는 \(m(2n-1)\) 이다. \(n\) 이 크다면 flop 수는 \(2mn\) 으로 본다.

두 행렬 \(A \in \mathbb{R}^{m \times n}\), \(B \in \mathbb{R}^{n \times p}\) 의 곱셈 연산 \(AB\) 에서는 \(m(2n-1)\) 번의 행렬/벡터 곱셈 연산을 \(p\) 번 반복하는 것이기 때문에 flop 수는 \(mp(2n-1)\) 이다. \(n\) 이 크다면 flop 수는 \(2mnp\) 로 본다.