개요

병렬 컴퓨팅, Parallel computing이란 여러가지의 명령어를 동시에 병렬적으로 시행하는 최적화 기법을 말한다. GPU나 CPU의 multi-core와 같이 여러개의 instruction을 동시에 시행할 수 있는 하드웨어에서 시행된다. 인공지능에서 병렬 컴퓨팅은 매우 중요한 기법으로서 사용된다. 인공지능이나 컴퓨터 그래픽스에서 기본 연산은 행렬연산이기 때문이다. 행렬 연산은 매우 병렬화 하기 쉬우며 병렬화 되었을 경우 속도를 비약적으로 향상시킬 수 있어서 병렬 컴퓨팅의 주 목적이 된다. 특히 인공지능은 단순한 계산을 매우 많은 곳에서 사용한다는 점에서 병렬 처리에 최적화 되어 있다고 할 수 있다. 따라서 ML은 하드웨어의 지원을 통해서 매우 빠르게 가속화 될 수 있다. 물론 인공지능, 컴퓨터 그래픽스와 같이 행렬 처리나 수식의 단순 계산외에도, mutliple instruction fetch 와 같은 기법을 이용하여 병렬성을 달성할 수 도 있다. 또한 여러 Procedural Generation알고리즘과 같이 병렬 처리에 의해서 속도가 향상될 수 있는 알고리즘도 존재하며, 병렬 컴퓨팅을 이용하여 어떻게 알고리즘을 효율적으로 재 구성하느냐는 프로그램의 성능 향상에 있어서 매우 중요한 요소이다.

A parallel computer is a collection of processing elements that can communicate and cooperate to solve a large problem fast

무어의 법칙에 의해서 지속적으로 증가하던 CPU의 처리 속도에 한계가 도달하자, 병렬 처리의 중요성 또한 매우 커졌다. 그러나 이러한 병렬 처리는 프로그래머에게 매우 많은 생각할 거리를 제공한다. 병렬 처리에서는 쓰레드레벨 그리고 프로그램레벨에서의 동시성을 고려한 프로그램을 짜야 하는 것이다. 옜날에는 한 칩에서 명령어의 동시 처리를 생각하면 되었기에 이러한 작업은 하드웨어 제조사가 담당하고 프로그래머는 동시성을 고려할 필요가 없었지만 결국 프로그래머도 동시성을 생각하여 프로그램을 작성해야 하는 시대가 오게 되었다.

병렬 컴퓨팅에서의 프로그래밍

사실 사람은 병렬적으로 생각을 한다. 뇌의 각각의 뉴런들은 이러한 신호를 병렬적으로 모든 뉴런에 퍼트리면서 계산을 하고 그 결과로 우리가 행동하는 것일 것이다. 그러나 처음 프로그래밍을 배울떄 우리 모두는 선형적으로 연산을 처리하는 것을 학습해 왔다. 사실 이러한 선형 처리는 배우기 쉽고 이해하기 쉽지만, 병렬 컴퓨팅을 사용할 수 있는 환경에서는 매우 느리다는 단점이 있다. 따라서 이러한 선형 처리에서 사용하던 많은 습관들을 버리고 병렬 처리에 맞추어 다시 생각하는 기법이 필요하다.

Programming Parallel program.png
  • Identifying parallel task: 코드를 분석하여, parallel하게 될수 있는 task들을 파악한다.
  • Determining variable scopes: 코드 분석과 알고리즘 분석으로 Shared memory, Private Memory, Reduction을 계산한다. 예를 들어서 loop에서 index는 private이며, loop에서 처리되는 array이는 shared라고 할 수 있다. shared의 조건에서 reading은 괜찮지만 writing에 대해서 동기화가 일어나는지, 혹시 변수의 값이 적절하지 않게 참조되는 지를 파악하여야 한다.
  • Task synchronization: Memory Accessing Sequence, Static, Dynamic, Block or Cyclic data access와 같은 태스크의 구조적인 방향을 체크한다.

Loop level parallelism

  • True dependency: Read after Write, 순서를 바꾸지 않아도 문제가 생긴다.
  • Anti dependency: Write after Read, 순서를 바꾸면 문제가 생긴다.
  • Output dependency: Write after Write, 순서를 바꾸면 문제가 생긴다.
  • Loop carried dependence: Loop이 없으면 dependence가 사라진다.
  • Loop independent dependence: Loop이 없어도 의존성이 지속된다.

즉 Loop level 병렬화에서 신경써야할 부분은 True dependency와 Loop carried dependence이다.

ITG

ITG.png

ITG는 iteration이 일어나는 것을 visual로 보여줌으로 어떠한 일이 일어나고 있는지 한눈에 알 수 있도록 한다. 시작 포인트를 Node로 하여, 각각의 edge들이 어떠한 순서로 일어나는지를 확인 할 수있도록 한다.

  1. Loop carried Dependence Graph (LDG): LDG는 true/anti/output dependence관계를 그래픽적으로 보여준다.