처치 곤란 병렬
1. 개요
처치 곤란 병렬은 "처치 곤란하게 쉬운" 병렬화 문제를 의미하며, 개발자나 컴파일러에게 난처함을 야기할 수 있는 문제를 지칭한다. 1986년 클리브 몰러가 처음 사용한 용어로, 여러 처리 장치가 독립적으로 작업을 수행할 수 있는 문제들을 포함한다. 몬테카를로 방법, 컴퓨터 그래픽스 렌더링, 암호학의 무차별 대입 공격 등이 예시이며, R 프로그래밍 언어의 SNOW 패키지 등을 통해 구현될 수 있다.
| 정의 | '처치 곤란 병렬(Embarrassingly parallel)은 계산 문제를 독립적인 부분으로 나눌 수 있어서 동시에 실행할 수 있는 경우를 말한다.' |
|---|---|
| 특징 | 부분 간 통신이나 의존성이 거의 또는 전혀 없음 병렬화 구현이 간단 높은 효율성을 달성 가능 |
| 브루트 포스 공격 | '키 공간을 여러 프로세서에 분할하여 암호 해독 시도' |
|---|---|
| 렌더링 | '컴퓨터 그래픽에서 각 프레임을 독립적으로 렌더링' |
| 몬테카를로 시뮬레이션 | '각 시뮬레이션 실행은 독립적' |
| 이미지 처리 | '각 이미지를 독립적으로 처리' |
| 유전자 알고리즘 | '각 개체를 독립적으로 평가' |
| 대규모 데이터베이스 검색 | '데이터베이스의 여러 부분을 동시에 검색' |
| SETI@home | '데이터 분석 작업을 분산 처리' |
-
병렬 컴퓨팅 -
슈퍼컴퓨터
슈퍼컴퓨터는 일반 컴퓨터보다 훨씬 높은 성능을 가진 컴퓨터로, 복잡한 계산과 시뮬레이션을 수행하며, 프로세서, 메모리, 스토리지, 네트워크 등으로 구성되어 병렬 처리를 통해 높은 성능을 구현하고, 군사, 기상 예측, 과학 기술 분야, 인공지능 등 다양한 분야에서 활용되고 있다. -
병렬 컴퓨팅 -
컴퓨터 클러스터
-
분산 컴퓨팅 문제 -
교착 상태
교착 상태는 둘 이상의 프로세스가 자원을 점유하고 서로의 자원을 요청하여 더 이상 진행할 수 없는 상태를 의미하며, 상호 배제, 점유 대기, 비선점, 순환 대기 네 가지 조건이 모두 충족되어야 발생하고, 운영 체제는 이를 예방, 회피, 무시, 발견하는 방법으로 관리한다. -
분산 컴퓨팅 문제 -
비잔티움 장애 허용
비잔틴 장애 허용(BFT)은 분산 컴퓨팅 시스템에서 일부 구성 요소가 오류나 악의적인 행위를 하더라도 시스템 전체가 정상적으로 작동하도록 보장하는 속성으로, 비잔틴 장애에 대한 대응책으로 합의 알고리즘을 통해 신뢰성을 확보하며, 블록체인, 항공, 군사, 암호화폐 등 다양한 분야에서 활용된다.
2. 어원
"처치 곤란"이라는 용어는 "처치 곤란하게 쉬운" 병렬화 문제를 가리키는 데 사용된다. 이 용어는 개발자나 컴파일러 입장에서 보면 문제를 쉽게 해결할 수 있다는 의미를 내포하고 있다. "근본적인 계산 복잡성으로 인해 해결되지 않은 중요한 문제들이 많기 때문에, 다항식 호모토피 연속 방법의 병렬 구현을 개발하지 않는 것은 처치 곤란한 일일 것이다." 이 용어는 MATLAB 개발자인 클리브 몰러가 1986년에 출판한 멀티프로세서 관련 서적에서 처음 등장했으며, 그는 이 용어를 직접 만들었다고 주장한다.
"만족스러운 병렬"이라는 용어도 사용되는데, 이는 "처치 곤란"이라는 부정적인 뉘앙스를 피하고 문제의 병렬화 가능성에 대한 긍정적인 측면을 강조하기 위한 것으로 보인다. "물론, 이러한 프로그램에 대해 전혀 처치 곤란한 점은 없다."
3. 예시
* 몬테카를로 방법
* [http://www.mysqlperformanceblog.com/2011/05/14/distributed-set-processing-with-shard-query/ 분산 집합 처리]를 사용한 분산 관계형 데이터베이스 쿼리.
* 수치 적분
* 사진 갤러리 크기 조정 및 변환과 같이 유사한 특성의 관련 없는 파일의 일괄 처리.
* 각 점이 독립적으로 계산되는 만델브로 집합, 펄린 노이즈 및 유사한 이미지.
* 컴퓨터 그래픽스의 렌더링. 컴퓨터 애니메이션에서 각 프레임 또는 픽셀은 독립적으로 렌더링될 수 있습니다 (병렬 렌더링 참조).
* 암호학의 일부 무차별 대입 공격. 주목할만한 실제 예로는 distributed.net과 암호화폐에 사용되는 작업 증명 시스템이 있습니다.
* 분할된 데이터베이스를 사용한 생물 정보학의 BLAST 검색.
* 수천 개의 임의로 획득한 얼굴 (예: 폐쇄 회로 텔레비전을 통한 보안 또는 감시 비디오)을 이와 유사한 수의 이전에 저장된 얼굴 (예: 수배자 명부 또는 유사한 관찰 목록)과 비교하는 대규모 얼굴 인식 시스템
* 많은 독립적인 시나리오를 비교하는 컴퓨터 시뮬레이션.
* 유전자 알고리즘
* 앙상블 계산 of 수치 일기 예보.
* 입자 물리학에서 사건 시뮬레이션 및 재구성.
* 마칭 스퀘어 알고리즘.
* 이차 체 및 수론 체의 체질 단계.
* 랜덤 포레스트 머신 러닝 기술의 트리 성장 단계.
* 각 고조파가 독립적으로 계산되는 이산 푸리에 변환.
* GPU에서 실행되는 컨볼루션 신경망.
* 제약 프로그래밍의 병렬 검색
4. 구현
R (프로그래밍 언어)의 SNOW (Simple Network of Workstations) 패키지는 워크스테이션 또는 비어울프 클러스터 집합을 사용하여 처치 곤란 병렬 계산을 수행하는 간단한 메커니즘을 구현한다. 이와 유사한 R 패키지로는 "future", "parallel" 등이 있다.