행렬과 벡터 연산 (5) - numpy 배열 메모리 최적화

행렬과 벡터 연산 (1) - 확산 방정식 예제

행렬과 벡터 연산 (2) - 확산 방정식 순수 파이썬 구현

행렬과 벡터 연산 (3) - 파이썬 리스트와 numpy 연산 속도 차이

행렬과 벡터 연산 (4) - numpy 배열을 이용한 확산 방정식

---

그렇다면 numpy 배열로 메모리 할당 횟수 (캐시 미스)를 줄인 이후에 메모리 할당 부분은 어떻게 최적화할 수 있을까요? 필요한 데이터를 캐시에서 찾지 못하면 메모리 할당은 단순히 메모리를 찾아보는 대시니 필요한 크기만큼의 데이터를 운영체제에 요청하게 됩니다. 캐시를 채우는 과정은 하드웨어적으로 최적화된 것에 반해 운영체제에 무언가를 요청할 때 발생하는 오버헤드는 (특히 메모리 할당) 커널과 통신해야 하므로 매우 큽니다.

제자리 연산 (in-place operation)

그렇다면 미리 할당한 메모리에 제자리 연산 (in-place) 연산을 사용하면 어떨까요? 제자리 연산은 +=, *= 처럼 입력 중 하나가 위치한 메모리에 결괏값을 다시 저장하는 연산을 말하며, 계산 결과를 저장하는 메모리 공간을 따로 할당하지 않고 덮어쓰게 됩니다. 예를 들어 array1, array2 numpy 배열이 있을 때 array1 = array1 + array2 연산 결과는 새로운 메모릭 공간을 할당하여 array1 변수에 덮어쓰지만 array1 += array2 연산은 본래 array1 메모리 공간을 그대로 사용하고 데이터만 바뀌게 됩니다. 특히, 제자리 연산은 배열의 크기가 커질수록 메모리 할당에 시간이 더 오래 걸리므로 효과적입니다. 하지만 배열 크기가 매우 작아 입출력 배열이 모두 캐시에 들어갈 수 있으면 벡터화의 이점을 누릴 수 있으므로 제자리 연산 대신 일반 연산이 속도가 더 빠릅니다.

---

지난 포스트의 numpy 코드를 제자리 연산을 사용하도록 변경해 보겠습니다.

def laplacian(grid, out):
    np.copyto(out, grid)
    out *= -4
    out += np.roll(grid, 1, 0)
    out += np.roll(grid, -1, 0)
    out += np.roll(grid, 1, 1)
    out += np.roll(grid, -1, 1)

@profile
def evolve(grid, dt, out, D=1):
    laplacian(grid, out)
    out *= D*dt
    out += grid

def run_experiment(num_iterations):
    next_grid = np.zeros(grid_shape)
    grid = np.zeros(grid_shape)

    ## 초기 조건
    block_low = int(grid_shape[0]*0.4)
    block_high = int(grid_shape[0]*0.5)
    for i in range(block_low, block_high):
        for j in range(block_low, block_high):
            grid[i][j] = 0.005

    for i in range(num_iterations):
        evolve(grid, 0.1, next_grid)
        grid, next_grid = next_grid, grid

• grid, next_grid 변수를 numpy zero 배열로 생성하고 next_grid는 evolve가 실행되면 갱신된 정보를 포함하여 grid에 전달됩니다.
• 마지막의 grid, next_grid 변수 사이의 swap 부분은 데이터 자체를 바꾸는 것이 아니라 데이터에 대한 참조만 바꾸는 것이므로 부담이 없습니다.

이렇게 제자리 연산을 이용해 코드를 변경하면 가독성이 떨어지지만 이미 할당된 메모리 공간을 재활용하여 메모리 할당 횟수를 줄이기 때문에 페이지 폴트 (page fault) 가 감소하게 됩니다. 메모리가 할당됐을 때, 커널은 메모리에 대한 참조를 프로그램에 알려주고 나중에 그 메모리가 처음 사용되면 운영체제는 가벼운 (minor) 페이지 폴트 인터럽트를 발생시켜 실행 중이던 프로그램을 멈추고 실제 필요한 메모리를 할당하는데, 이 과정을 페이지 폴트라 합니다. 당연히 커널과의 통신이 포함되며, 프로그램의 영역 밖에서 최적화, 캐시 내용 등을 비롯해 수행 중인 모든 내용을 포기하고 메모리를 할당받아야 하므로 실행 비용이 많이 듭니다.

line_profiler

이 상태에서 더 개선할 부분이 있을 지 line_profiler를 통해 확인해봅시다. evolve 함수에 @profile 데코레이터로 살려본 결과 확산 방정식을 계산하는데 laplacian 함수가 소비한 시간의 93.4% 차지합니다.

>>> kernprof -lv diffusion_np.py 
Total time: 2.43078 s
File: diffusion_np.py
Function: evolve at line 13

Line #      Hits         Time  Per Hit   % Time  Line Contents
==============================================================
    13                                           @profile
    14                                           def evolve(grid, dt, out, D=1):
    15       500    2271202.1   4542.4     93.4      laplacian(grid, out)
    16       500      55548.4    111.1      2.3      out *= D*dt
    17       500     104027.8    208.1      4.3      out += grid

laplacian 함수를 살펴보면 numpy roll 함수로 제자리 연산을 수행하는데, roll 함수를 호출하면서 새로운 배열을 할당하게 됩니다. 또한, roll 함수 자체가 매우 범용적인 함수라서 특수한 경우를 처리하기 위한 코드를 많이 포함해서 축을 따라 쉬프트하면 되는 우리 작업 이외의 불필요한 작업이 포함되어 있습니다. 따라서 roll 함수의 로직을 indexing 기능과 덧셈을 합쳐서 메모리 할당을 최소화하도록 개선할 수 있습니다.

def roll_add(rollee, shift, axis, out):
    if shift == 1 and axis == 0:
        out[1:,:] += rollee[:-1,:]
        out[0,:] += rollee[-1,:]
    elif shift == -1 and axis == 0:
        out[:-1,:] += rollee[1:,:]
        out[-1,:] += rollee[0,:]
    elif shift == 1 and axis == 1:
        out[:,1:] += rollee[:,:-1]
        out[:,0] += rollee[:,-1]
    elif shift == -1 and axis == 1:
        out[:,:-1] += rollee[:,1:]
        out[:,-1] += rollee[:,0]

def laplacian(grid, out):
    np.copyto(out, grid)
    out *= -4
    roll_add(grid, 1, 0, out)
    roll_add(grid, -1, 0, out)
    roll_add(grid, 1, 1, out)
    roll_add(grid, -1, 1, out)

이 코드를 프로파일링 하면 0.832 초 정도가 소요되어 앞선 것보다 3배 정도 빨라졌습니다. 이는 행렬을 시프트할 때 numpy에 전적으로 의존하는 대신 제자리에서 데이터를 갱신하는 함수 roll_add 함수를 작성했기 때문인데, numpy는 배열을 바로 내보내지 않고, 경계 검사나 오류 처리 등 작업에 필요한 다른 검사를 실행한 후 결과를 추가하기 때문입니다. 앞선 개선은 이미 할당된 메모리를 재활용을 해서 페이지 폴트를 줄였다면, 여기서는 roll 함수를 roll_add 함수로 개선하여 메모리 할당 자체를 줄인 것이죠 (캐시 미스 감소). 따라서 numpy나 파이썬 내부 함수를 사용하더라도 불필요한 부분을 덜어내는 방식으로 성능 최적화를 추구할 수 있습니다.

 

---

행렬과 벡터 연산 (6) - numexpr 모듈 이용하기