수축기 어레이

병렬 컴퓨터 아키텍처에서 수축기 어레이는 셀 또는 노드라고 불리는 긴밀하게 결합된 데이터 처리 장치(DPU)의 동종 네트워크입니다.각 노드 또는 DPU는 업스트림네이버로부터 수신한 데이터의 함수로서 부분적인 결과를 독립적으로 계산해, 그 결과를 그 내부에 격납해 다운스트림으로 전달합니다.수축기 배열은 ^[1]제2차 세계대전 중 독일의 로렌츠 암호를 해독하기 위해 사용된 초기 컴퓨터인 콜로스에서 처음 사용되었다.골로스의 분류된 특성으로 인해, 그것들은 독립적으로 발명되거나 재발견되었으며, H. T. Kung과 Charles Leiserson은 밴드화된 행렬에 대한 많은 밀도 높은 선형 대수 계산(행렬 곱, 선형 방정식의 해결 시스템, LU 분해 등)을 위해 어레이를 기술했다.초기 적용에는 정수와 다항식의 ^[2]최대공약수 계산이 포함됩니다.Flynn의 분류법에 따라 MISD(Multiple Instruction Single Data) 아키텍처로 분류되기도 하지만, 이 분류는 이 기사의 뒷부분에서 설명한 바와 같이 SISD, SIMD, MIMD의 네 가지 범주 중 하나에서 수축기 어레이를 구별하는 강력한 주장이 제기될 수 있기 때문에 의문입니다.

병렬 입력 데이터는 유선 연결된 프로세서 노드 네트워크를 통해 흐르고 입력 데이터를 결합, 처리, 병합 또는 정렬하여 파생 결과를 생성합니다.수축기 어레이를 통해 데이터가 파동처럼 전파되는 것은 인간의 순환계 맥박과 유사하기 때문에 수축기라는 이름은 의학 용어에서 유래했습니다.그 이름은 심장에 의해 정기적으로 혈액이 뿜어져 나오는 것과 비유하여 수축기에서 유래되었다.

적용들

수축기 어레이는 대규모 병렬 통합, 컨볼루션, 상관관계, 매트릭스 곱셈 또는 데이터 정렬 태스크를 수행하기 위해 "다중 누적"과 같은 특정 작업을 위해 유선 연결되어 있는 경우가 많습니다.DNA 및 단백질 배열 분석에서 사용되는 동적 프로그래밍 알고리즘에도 사용됩니다.

아키텍처

수축기 어레이는 일반적으로 유선 연결 또는 특정 애플리케이션용으로 구성된 소프트웨어를 사용할 수 있는 원시 컴퓨팅 노드의 대규모 단일 네트워크로 구성됩니다.노드는 보통 고정되어 동일하지만 상호접속은 프로그램 가능합니다.반면 일반적인 웨이브 프론트 프로세서는 어레이의 크기와 설계 파라미터에 따라 획일적인 노드인지 아닌지를 불문하고 고도로 개별적으로 프로그래밍 가능한 노드를 사용합니다.또 다른 차이점은 수축기 어레이는 동기 데이터 전송에 의존하지만 파장은 비동기적으로 작동하는 경향이 있다는 것입니다.

일반적인 Von Neumann 아키텍처와는 달리 프로그램 실행은 공통 메모리에 저장된 명령 스크립트를 따르고 CPU의 프로그램 카운터(PC)에 의해 주소 지정 및 시퀀싱되며, 수축기 배열 내의 개별 노드는 새로운 데이터의 도착에 의해 트리거되며 항상 정확히 동일한 방식으로 데이터를 처리합니다.각 노드 내의 실제 처리는 유선 연결 또는 블록 마이크로 코딩될 수 있으며, 이 경우 공통 노드 속성을 블록 프로그래밍할 수 있습니다.

데이터 카운터에 의해 구동되는 데이터 스트림을 갖는 수축기 배열 패러다임은 프로그램 카운터에 의해 구동되는 명령 스트림을 갖는 Von Neumann 아키텍처의 대응 요소입니다.수축기 배열은 일반적으로 여러 데이터 스트림을 송수신하며 이러한 데이터 스트림을 생성하려면 여러 데이터 카운터가 필요하므로 데이터 병렬 처리를 지원합니다.

목표와 이점

수축기 어레이의 주요 장점은 모든 오퍼랜드 데이터와 부분 결과가 프로세서 어레이 내에 저장(패스스루)된다는 것입니다.Von Neumann 또는 Harvard의 시퀀셜 머신과 마찬가지로 각 작업 중에 외부 버스, 메인 메모리 또는 내부 캐시에 액세스할 필요가 없습니다.Amdahl의 법칙에 따라 병렬 퍼포먼스에 대한 순차적 제한도 동일한 방식으로 적용되지 않습니다.왜냐하면 데이터의 의존관계는 프로그래머블노드 인터커넥트에 의해 암묵적으로 처리되며 고도의 병렬 데이터 흐름을 관리하기 위한 순차적 단계가 없기 때문입니다.

따라서 수축기 배열은 인공지능, 이미지 처리, 패턴 인식, 컴퓨터 비전 그리고 동물의 뇌가 특히 잘 하는 다른 작업에 매우 능숙합니다.Wavefront 프로세서는 일반적으로 하드웨어에 자체 구성 뉴럴넷을 구현함으로써 머신러닝에도 매우 능숙합니다.

분류 논란

수축기 어레이는 공식적으로 MISD로 분류되지만 분류에는 다소 문제가 있습니다.일반적으로 입력은 독립된 값의 벡터이므로 수축기 배열은 SISD가 아닙니다.이들 입력값은 Marge되어 결과에 결합되며 SIMD 벡터 처리장치에서와 같이 독립성을 유지하지 않기 때문에 어레이는 그렇게 분류할 수 없습니다.따라서 어레이는 MIMD로도 분류할 수 없습니다.MIMD는 작은 SISD 및 SIMD 머신의 단순한 집합으로 간주될 수 있기 때문입니다.

마지막으로 데이터 스톰은 노드 간에 어레이를 통과할 때 변환되기 때문에 여러 노드가 동일한 데이터로 동작하지 않기 때문에 MISD 분류가 잘못됩니다.수축기 어레이가 MISD로 인정되지 않는 다른 이유는 SISD 카테고리에서 부적격인 어레이와 동일합니다.입력 데이터는 일반적으로 단일 데이터 값이 아닌 벡터이지만, 주어진 입력 벡터는 단일 데이터 항목이라고 주장할 수 있습니다.

위의 모든 것에도 불구하고, 수축기 어레이는 병렬 컴퓨팅 교과서 및 엔지니어링 수업에서 MISD 아키텍처의 전형적인 예로서 종종 제공됩니다.어레이가 외부에서 원자성으로 표시되는 경우 SFMuDMeR = 단일 기능, 다중 데이터, 병합 결과로 분류해야 합니다.

수축기 배열은 노드를 연결하는 사전 정의된 계산 흐름 그래프를 사용합니다.Kahn 프로세스 네트워크는 유사한 흐름 그래프를 사용하지만 수축기 어레이에서 잠금 스텝으로 작동하는 노드로 구분됩니다. Kahn 네트워크에서는 각 노드 사이에 FIFO 큐가 있습니다.

상세설명

수축기 배열은 셀이라고 불리는 데이터 처리 단위의 행렬과 같은 행으로 구성됩니다.데이터 처리 장치(DPU)는 중앙 처리 장치(CPU)와 유사합니다(연산이 데이터 객체의 도착에 의해 전송 트리거되기 때문에 프로그램 ^[3]카운터가 없는 것을 제외합니다).각 셀은 처리 직후 네이버와 정보를 공유합니다.수축기 어레이는 대부분의 경우 인접 DPU 간에 데이터가 어레이를 통해 흐르는 직사각형이며, 데이터가 서로 다른 방향으로 흐르는 경우가 많습니다.어레이 포트를 출입하는 데이터 스트림은 메모리 유닛(ASM)의 자동 시퀀싱에 의해 생성됩니다.각 ASM에는 데이터 카운터가 포함됩니다.임베디드 시스템에서는 외부 소스와 데이터 스트림을 입력 및/또는 출력할 수도 있습니다.

수축기 알고리즘의 예는 행렬 곱셈을 위해 설계될 수 있습니다.한쪽 매트릭스는 어레이의 선두에서 한 번에 열로 공급되어 어레이를 통과하고, 다른 한쪽 매트릭스는 어레이의 좌측에서 한 번에 열로 공급되어 좌측에서 우측으로 전달된다.그 후 각 프로세서가 하나의 행과 하나의 열을 모두 볼 때까지 더미 값이 전달됩니다.이 시점에서 곱셈 결과는 어레이에 저장되며,^[4] 이제 한 번에 행 또는 열을 출력하여 어레이를 흘러내리거나 어레이를 가로질러 흐를 수 있습니다.

수축기 어레이는 메시와 같은 토폴로지로 소수의 가장 가까운 인접 DPU에 접속되어 있는 DPU 어레이입니다.DPU는 DPU 간에 흐르는 데이터에 대해 일련의 조작을 수행합니다.기존의 수축기 배열 합성 방법은 대수 알고리즘에 의해 실행되었기 때문에 선형 파이프만 있는 균일한 배열만 얻을 수 있으므로 모든 DPU에서 아키텍처가 동일합니다.그 결과, 통상의 데이터 의존성을 가지는 애플리케이션만이, 기존의 수축기 어레이에 실장할 수 있게 됩니다.SIMD 머신과 마찬가지로 클럭된 수축기 어레이는 각 프로세서가 번갈아 컴퓨팅 통신 단계를 수행하면서 "잠금 단계"로 계산됩니다.단, DPU 간에 비동기 핸드쉐이크를 사용하는 수축기 어레이는 웨이브프런트 어레이라고 불립니다.잘 알려진 수축기 어레이 중 하나는 인텔이 제조한 Carnegie Mellon 대학의 iWarp 프로세서입니다.iWarp 시스템은 양방향으로 이동하는 데이터 버스에 의해 연결된 선형 어레이 프로세서를 가진다.

역사

수축기 어레이(웨이브프런트 프로세서라고도 함)는 H. T. Kung과 Charles E에 의해 최초로 설명되었습니다. 1979년에 수축기 배열에 대한 최초의 논문을 발표한 Leiserson씨.하지만, 비슷한 기술을 사용한 것으로 알려진 최초의 기계는 1944년 골로소스 마크 2호였다.

응용 프로그램 예시

이 섹션은 확장해야 합니다.추가하시면 됩니다. (2016년 5월)

다항식 평가

다항식을 평가하기 위한 호너의 규칙은 다음과 같습니다.

$\displaystyle y=(\ldots ((a_{n}\cdot x+a_{n-1}\cdot x+a_{n-2})\cdot x+a_{n-3}\cdot x+{1}\cdot x+a_{0}).}$

프로세서가 쌍으로 배열된 선형 수축기 배열입니다.하나는 입력에$$x(\$displaystyle$ x$)$를 곱하여 결과를 오른쪽으로 전달하고 다음으로 j$(\$를 $추가$하여 결과를 오른쪽으로 전달합니다.

장점과 단점

이 섹션은 어떠한 출처도 인용하지 않습니다. 신뢰할 수 있는 출처에 인용문을 추가하여 이 섹션의 개선에 도움을 주십시오. 조달되지 않은 자재는 제거될 수 있습니다.(2016년 12월) (이 템플릿메시지 삭제 방법 및 삭제 시기 확인)

장점

• 범용 프로세서보다 고속
• 스케일러블

단점

• 규모의 경제성이 낮기 때문에 고가
• 고도의 전문성을 갖춘 커스텀 하드웨어가 필요하며 애플리케이션 고유의 경우가 많습니다.
• 널리 구현되지 않음
• 프로그램 및 알고리즘의 코드 베이스가 한정되어 있습니다.(모든 알고리즘을 수축기 배열로 구현할 수 있는 것은 아닙니다.이러한 알고리즘을 수축기 어레이에 매핑하기 위해서는 트릭이 필요한 경우가 많습니다).

실장

• Cisco PXF 네트워크 프로세서는 내부적으로 수축기 ^[5]어레이로 편성되어 있습니다.
• 구글의 TPU는 또한 수축기 어레이를 중심으로 설계되었습니다.
• 파라셀 FDF4T TestFinder 텍스트 검색^[6] 시스템
• 파라셀 FDF4G 유전자 매처 생물(DNA 및 단백질) 검색 시스템
• Amazon Web^[7] Services의 추리 칩
• MIT Eyeriss는 컨볼루션 뉴럴 ^[8][9]네트워크용 수축기 어레이 액셀러레이터입니다.

「 」를 참조해 주세요.

• MISD – 다중 명령 단일 데이터, 예:수축기 어레이
• iWarp – 수축기 어레이 컴퓨터, VLSI, 인텔/CMU
• WARP(수축기 어레이)– 수축기 어레이 컴퓨터, GE/CMU
• 텐서 처리 장치 – AI 가속기 ASIC

메모들

레퍼런스

이 문서에는 일반적인 참조 목록이 포함되어 있지만 대응하는 충분한 인라인 인용이 없습니다. 좀 더 정확한 인용문을 도입하여 이 기사의 개선에 도움을 주십시오. (2011년 4월) (이 템플릿메시지의 삭제 방법 및 삭제 타이밍에 대해 알아보기)

• H. T. Kung, C. E. Leiserson:VLSI 프로세서어레이 알고리즘(C).미드, L. 콘웨이(eds):VLSI 시스템 개요; Adison-Wesley, 1979
• S. Y. Kung: VLSI 어레이 프로세서; 프렌티스 홀, 주식회사, 1988
• N. Petkov: 수축기 병렬 처리; North Holland Publishing Co., 1992

외부 링크

• 명령 수축기 어레이(ISA)
• '실시간 이미지 등록을 위한 VLSI 아키텍처'(수축기 어레이 기반), Vol. 15, 2007년 9월