병렬 알고리즘-소개
안 algorithm사용자로부터 입력을 받고 계산 후 출력을 생성하는 일련의 단계입니다. ㅏparallel algorithm 다른 처리 장치에서 여러 명령을 동시에 실행 한 다음 모든 개별 출력을 결합하여 최종 결과를 생성 할 수있는 알고리즘입니다.
동시 처리
인터넷의 성장과 함께 컴퓨터의 쉬운 가용성은 우리가 데이터를 저장하고 처리하는 방식을 변화 시켰습니다. 우리는 데이터가 풍부한 시대에 살고 있습니다. 매일 우리는 복잡한 컴퓨팅을 필요로하는 엄청난 양의 데이터를 신속하게 처리합니다. 때로는 동시에 발생하는 유사하거나 상호 관련된 이벤트에서 데이터를 가져와야합니다. 이것이 우리가 요구하는 곳입니다concurrent processing 복잡한 작업을 분할하고 여러 시스템을 처리하여 빠른 시간에 출력을 생성 할 수 있습니다.
작업이 대량의 복잡한 데이터를 처리하는 경우 동시 처리가 필수적입니다. 예 : 대규모 데이터베이스 액세스, 항공기 테스트, 천문학 계산, 원자 및 핵 물리학, 생물 의학 분석, 경제 계획, 이미지 처리, 로봇 공학, 날씨 예보, 웹 기반 서비스 등.
병렬 처리 란 무엇입니까?
Parallelism여러 명령 세트를 동시에 처리하는 프로세스입니다. 총 계산 시간이 줄어 듭니다. 병렬 처리는 다음을 사용하여 구현할 수 있습니다.parallel computers,즉, 프로세서가 많은 컴퓨터. 병렬 컴퓨터에는 멀티 태스킹을 지원하는 병렬 알고리즘, 프로그래밍 언어, 컴파일러 및 운영 체제가 필요합니다.
이 튜토리얼에서는 parallel algorithms. 더 나아 가기 전에 먼저 알고리즘과 그 유형에 대해 논의하겠습니다.
알고리즘이란?
안 algorithm문제를 해결하기 위해 따르는 일련의 지침입니다. 알고리즘을 설계 할 때 알고리즘이 실행될 컴퓨터의 아키텍처를 고려해야합니다. 아키텍처에 따라 두 가지 유형의 컴퓨터가 있습니다.
- 순차 컴퓨터
- 병렬 컴퓨터
컴퓨터 아키텍처에 따라 두 가지 유형의 알고리즘이 있습니다.
Sequential Algorithm − 문제를 해결하기 위해 몇 가지 연속적인 명령 단계가 시간순으로 실행되는 알고리즘.
Parallel Algorithm− 문제는 하위 문제로 나뉘어 개별 출력을 얻기 위해 병렬로 실행됩니다. 나중에 이러한 개별 출력을 함께 결합하여 원하는 최종 출력을 얻습니다.
큰 문제를 다음과 같이 나누는 것은 쉽지 않습니다. sub-problems. 하위 문제에는 데이터 종속성이있을 수 있습니다. 따라서 프로세서는 문제를 해결하기 위해 서로 통신해야합니다.
프로세서가 서로 통신하는 데 필요한 시간은 실제 처리 시간보다 더 많은 것으로 밝혀졌습니다. 따라서 병렬 알고리즘을 설계하는 동안 효율적인 알고리즘을 얻으려면 적절한 CPU 사용률을 고려해야합니다.
알고리즘을 올바르게 설계하려면 기본에 대한 명확한 아이디어가 있어야합니다. model of computation 병렬 컴퓨터에서.
계산 모델
순차 및 병렬 컴퓨터는 모두 알고리즘이라는 명령 집합 (스트림)에서 작동합니다. 이러한 지침 (알고리즘) 집합은 각 단계에서 수행해야하는 작업에 대해 컴퓨터에 지시합니다.
명령어 스트림과 데이터 스트림에 따라 컴퓨터는 네 가지 범주로 분류 될 수 있습니다.
- 단일 명령 스트림, 단일 데이터 스트림 (SISD) 컴퓨터
- 단일 명령 스트림, 다중 데이터 스트림 (SIMD) 컴퓨터
- 다중 명령 스트림, 단일 데이터 스트림 (MISD) 컴퓨터
- 다중 명령 스트림, 다중 데이터 스트림 (MIMD) 컴퓨터
SISD 컴퓨터
SISD 컴퓨터에는 one control unit, one processing unit, 과 one memory unit.
이러한 유형의 컴퓨터에서 프로세서는 제어 장치로부터 단일 스트림의 명령을 수신하고 메모리 장치의 단일 데이터 스트림에서 작동합니다. 계산하는 동안 각 단계에서 프로세서는 제어 장치로부터 하나의 명령을 수신하고 메모리 장치에서 수신 된 단일 데이터에 대해 작동합니다.
SIMD 컴퓨터
SIMD 컴퓨터에는 one control unit, multiple processing units, 과 shared memory or interconnection network.
여기서 하나의 단일 제어 장치는 모든 처리 장치에 명령을 보냅니다. 계산하는 동안 각 단계에서 모든 프로세서는 제어 장치로부터 단일 명령 세트를 수신하고 메모리 장치의 다른 데이터 세트에서 작동합니다.
각 처리 장치에는 데이터와 명령어를 모두 저장하는 자체 로컬 메모리 장치가 있습니다. SIMD 컴퓨터에서 프로세서는 서로 통신해야합니다. 이것은shared memory 또는 interconnection network.
일부 프로세서는 명령 집합을 실행하지만 나머지 프로세서는 다음 명령 집합을 기다립니다. 제어 장치의 지침에 따라 처리 할 프로세서가 결정됩니다.active (지시 실행) 또는 inactive (다음 지시를 기다리십시오).
MISD 컴퓨터
이름에서 알 수 있듯이 MISD 컴퓨터에는 multiple control units, multiple processing units, 과 one common memory unit.
여기에서 각 프로세서에는 자체 제어 장치가 있으며 공통 메모리 장치를 공유합니다. 모든 프로세서는 자체 제어 장치에서 개별적으로 명령을 받고 각 제어 장치에서받은 명령에 따라 단일 데이터 스트림에서 작동합니다. 이 프로세서는 동시에 작동합니다.
MIMD 컴퓨터
MIMD 컴퓨터에는 multiple control units, multiple processing units, 그리고 shared memory 또는 interconnection network.
여기에서 각 프로세서에는 자체 제어 장치, 로컬 메모리 장치, 산술 및 논리 장치가 있습니다. 그들은 각각의 제어 장치로부터 다른 명령 세트를 수신하고 다른 데이터 세트에서 작동합니다.
노트
공통 메모리를 공유하는 MIMD 컴퓨터는 multiprocessors, 상호 연결 네트워크를 사용하는 사람들은 multicomputers.
프로세서의 물리적 거리에 따라 다중 컴퓨터는 두 가지 유형이 있습니다.
Multicomputer − 모든 프로세서가 서로 매우 가까이있을 때 (예 : 같은 방에 있음).
Distributed system − 모든 프로세서가 서로 멀리 떨어져있는 경우 (예 : 다른 도시)