KR102819972B1

KR102819972B1 - 동기식 프로세서를 위한 샤딩

Info

Publication number: KR102819972B1
Application number: KR1020227004916A
Authority: KR
Inventors: 라이너 포프; 허먼 슈미트; 마이클 앨런 군터
Original assignee: 구글 엘엘씨
Priority date: 2019-08-22
Filing date: 2020-08-20
Publication date: 2025-06-13
Anticipated expiration: 2040-08-20
Also published as: TW202111562A; CN114270307A; KR20220031717A; KR20250086806A; JP7423757B2; EP3987394A1; US20220300450A1; US20250045032A1; JP7787212B2; US12147793B2; WO2021035055A1; TWI776212B; JP2022544842A; JP2024040198A

Abstract

방법, 시스템 및 디바이스. 방법은 다수의 동기식 타일을 갖는 디바이스에 대한 데이터 흐름 그래프를 샤딩하기 위한 컴퓨터 저장 매체에 인코딩된 컴퓨터 프로그램을 포함한다. 방법 중 하나는 복수의 동기식 타일을 갖는 디바이스에 의해 수행될 개별 행렬 연산을 각각 나타내는 복수의 노드를 포함하는 데이터 흐름 그래프의 표현을 수신하는 단계를 포함한다. 복수의 동기식 타일의 각 타일에 대한 데이터 흐름 그래프의 개별 부분의 후보 할당은 디바이스의 하나 이상의 자원 제약에 따라 평가된다. 후보 할당들 중 하나는 각 후보 할당을 평가하는 것에 기초하여 선택된다.

Description

동기식 프로세서를 위한 샤딩

본 명세서는 집적 회로 가속기용 컴파일러 기술에 관한 것이다.

동기식 집적 회로 가속기는 고도의 병렬 동기식 동작들을 수행하기 위해 설계된 주문형 집적 회로(ASIC)이다. 병렬 처리는 동시에 실행할 수 있는 많은 다른 독립 프로세싱 엘리먼트를 통합하여 이루어진다.

이러한 디바이스는 예를 들어 가중치가 있는 계층 입력의 다른 곱셈 또는 가산을 수행하는 각각의 독립 프로세싱 엘리먼트가 있는 신경망을 통한 추론 경로를 가속화하는데 적합하다. 신경망은 하나 이상의 입력으로부터 하나 이상의 출력을 예측하기 위해 다수의 동작 계층을 사용하는 기계 학습 모델이다. 신경망은 일반적으로 입력 계층과 출력 계층 사이에 위치한 하나 이상의 은닉 계층을 포함한다. 각 계층의 출력은 네트워크의 다른 계층, 예를 들어, 다음 은닉 계층 또는 출력 계층의 입력으로 사용된다.

가속기는 다수의 독립적인 프로세싱 타일을 사용할 수 있다. 본 명세서에서, 타일은 적어도 부분적으로 병렬로 행렬의 일부에 대해 계산을 수행할 수 있는 셀의 계산 어레이를 갖는 임의의 적절한 디바이스를 지칭한다. 따라서 각 셀은 셀이 수학적 또는 다른 계산을 수행할 수 있도록 하는 회로를 포함한다. 일반적인 시나리오에서, 타일은 입력 벡터를 수신하고, 계산 어레이를 사용하여 입력 벡터에 가중치 행렬을 곱하고, 출력 벡터를 생성한다.

본 명세서에서, 타일이 동기식이라는 것은 계산 어레이에 의해 수행되는 동작들이 명령형 프로그램의 if/else 문과 같이 분기 실행을 수행하지 않음을 의미한다. 오히려 동작들은 부분적으로 또는 전체적으로 사전 예약될 수 있다. 예를 들어, 일부 동기식 프로세서의 동작들은 개별 주기 수준으로 예약할 수 있는데, 이는 매번 프로세싱 엘리먼트의 매번 동작이 실행 주기의 시퀀스에서 특정 슬롯에 할당된다는 것을 의미한다.

본 명세서는 다수의 동기식 프로세서가 있는 시스템용으로 작성된 프로그램을 컴파일하는 기술을 설명한다. 위에서 설명된 바와 같이, 간결함을 위해 이러한 디바이스들은 본 명세서에서 타일로 지칭될 것이다.

컴파일러는 다수의 동기식 프로세서를 통해 실행되는 프로그램의 동작들이 스케줄링될 수 있는 주기-수준 정밀도를 활용할 수 있다. 이는 동작들의 정밀한 샤딩(sharding, 분할)뿐만 아니라 다른 성능 향상을 가능하게 한다. 본 명세서에서 설명된 기술은 각 타일이 선형 어레이에서 인접 타일과만 통신하는 선형 어레이의 다중 타일을 작동하는 시스템에서 동작들을 스케줄링하는데 특히 유용하다. 그러나, 이러한 하드웨어 배열이 없는 시스템에서도 동일한 기술이 사용될 수 있다.

본 명세서에 기술된 주제의 특정 실시예는 다음 이점들 중 하나 이상을 실현하도록 구현될 수 있다. 컴파일러는 다양한 샤딩 기술을 활용하여 다수의 컴퓨팅 타일이 있는 디바이스의 성능을 향상시킬 수 있다. 이러한 디바이스상의 태스크 실행은 샤딩 기술을 사용하여 디바이스 사양/제약에 맞게 조정될 수 있다. 컴파일러는 서브계층 샤딩을 사용하여 디바이스의 활용도를 높일 수 있다. 컴파일러는 또한 평행사변형 시간 슬라이싱을 사용하여 타일들이 어떤 일이 일어나기를 기다리고 있기 때문에 아무 작업도 수행하지 않는 유휴 영역을 줄이거나 제거할 수 있다. 컴파일러는 또한 오버샤딩을 사용하여 타일 간의 로드 밸런싱을 개선하고 컴파일 시간에 예측할 수 없는 로드 밸런싱 상황을 처리할 수 있다. 컴파일러는 또한 지그재그 샤딩을 사용하여, 타일들 간의 메모리와 계산 요구 사항의 균형을 맞출 수 있다.

본 명세서의 주제에 대한 하나 이상의 실시예의 세부 사항은 첨부 도면 및 아래의 설명에 기재되어 있다. 주제의 다른 특징, 측면 및 이점은 설명, 도면 및 청구범위로부터 명백해질 것이다.

도 1은 다중 타일을 갖는 디바이스에 대한 샤딩 행렬 연산을 위한 예시적인 프로세스의 흐름도이다.
도 2a-2b는 서브계층 샤딩의 예를 도시한다.
도 3a 내지 도 3d는 평행사변형 시간 슬라이싱의 예를 도시한다.
도 4a 내지 도 4c는 오버샤딩의 예를 도시한다.
도 5a 내지 도 5c는 지그재그 샤딩으로 지칭되는 다른 버전의 오버샤딩의 예를 도시한다.
도 6은 다수의 동기식 프로세서를 갖는 시스템의 프로세싱을 구현하는데 사용될 수 있는 타일의 예를 도시한다.
다양한 도면에서 유사한 참조 번호 및 명칭은 유사한 요소를 나타낸다.

도 1은 다중 타일을 갖는 디바이스에 대한 행렬 연산을 샤딩(분할)하기 위한 예시적인 프로세스의 흐름도이다. 전술한 바와 같이, 타겟(대상) 디바이스는 배열된 타일들을 가질 수 있거나 각 타일이 자신의 인접 타일과만 통신하는 선형 어레이로서 작동하도록 구성될 수 있다. 따라서, 데이터 흐름 그래프를 수신하는 것에 응답하여, 시스템은 선형 어레이내의 타일의 순서를 고려하여 그래프의 노드와 타일간의 할당을 생성할 수 있다. 편의를 위해, 예시적인 프로세스는 하나 이상의 위치에 위치되고 본 명세서에 따라 적절하게 프로그래밍된 하나 이상의 컴퓨터의 시스템에 의해 수행되는 것으로 설명될 것이다.

시스템은 복수의 타일을 갖는 디바이스에 의해 수행될 행렬 연산을 지정하는 데이터 흐름 그래프의 표현을 수신한다(110). 이러한 맥락에서, 행렬 연산은 행렬 또는 벡터 연산을 포함하는 것으로 이해되어야 한다. 데이터 흐름 그래프의 각 노드는 해당 노드 전용 행렬에서 수행할 행렬 연산을 지정한다. 예를 들어, 그래프의 각 노드는 해당 계층에 대해 학습하고 사용할 가중치를 저장하는 행렬이 있는 신경망의 계층을 나타낼 수 있다. 그래프의 각 에지는 한 노드의 출력이 다음 노드의 입력이 되는 데이터 전파를 나타낸다. 시스템은 복수의 타일의 각 타일에 대한 데이터 흐름 그래프 일부의 복수의 후보 할당을 생성한다(120). 샤딩의 문제는 복수의 후보 할당 중에서 디바이스의 타일들에 대한 데이터 흐름 그래프 부분의 최상의 할당을 찾기 위한 검색 문제로서 공식화될 수 있다. 평가할 후보를 생성하는 것과 관련된 다양한 기술이 아래에서 더 자세히 설명된다. 실제로 가장 적합한 후보 할당은 데이터 흐름 그래프와 특정 애플리케이션에 따라 크게 달라진다.

시스템은 디바이스의 하나 이상의 자원 제약에 따라 각각의 후보 할당을 평가한다(130). 중요한 자원 제약에는 메모리 제약 및 대역폭 제약이 포함된다.

기계 학습 가속기에 대한 하나의 예시적인 메모리 제약은 특정 타일에 할당된 모든 행렬의 모든 가중치가 타일에 로컬인 정적 랜덤 액세스 메모리(SRAM) 내에 맞아야(fit) 한다는 것이다.다시 말해, 각 타일은 통합된 양의 상주 SRAM이 있을 수 있으며, 이는 샤딩을 수행할 때 메모리 제약이 된다. 이 제약의 이유는 속도 및 대역폭과 관련이 있다. 먼저, 기계 학습 가속기는 가능한 한 빨리 모델을 통해 추론 경로를 수행하도록 설계되었다. 그리고 일부 애플리케이션의 경우, 동적 랜덤 액세스 메모리(DRAM Memory)는 충분히 빠르지 않다. 게다가, 행렬들의 가중치는 커서 주위로 이동시키기 어려울 수 있다. 따라서, 특정 타일에 할당된 모든 행렬의 모든 가중치가 타일의 로컬 SRAM내에 들어갈 수 있는 경우, 타일은 추론 경로 또는 트레이닝 업데이트 중에 가중치를 읽고 쓰는데 시간을 소비할 필요가 없다.

다른 예시적인 메모리 제약은 대역폭 제약이다. 대역폭 제약은 데이터가 그래프의 노드들 간에 이동해야 하는 속도를 지정한다. 제안된 할당이 그래프의 특정 에지에 대한 대역폭 임계값을 초과하는 경우, 시스템은 대역폭 제약이 위반되었다고 결정할 수 있다.

시스템은 각각의 후보 할당을 평가하는 것에 기초하여 후보 할당 중 하나를 선택한다(140). 일 예로서, 시스템은 입력 프로그램의 상이한 계층으로부터의 상이한 행렬이 상이한 개별 타일에 할당되는 계층 샤딩을 수행할 수 있다. 따라서, 예를 들어, 8개의 계층이 있는 신경망에는 각각 8개의 타일에 할당된 가중치 행렬이 있을 수 있다.

하나 이상의 자원 제약을 충족하는 후보 할당들의 경우, 시스템은 디바이스의 타일 활용을 가장 최적화하는 할당을 결정할 수 있다. 일반적으로, 여기에는 모든 타일에 대한 최대 계산 시간량을 계산하는 것 및 이어서 최소 최대 계산 시간량을 갖는 후보 할당을 선택하는 것이 포함된다. 주기(cycle) 수준까지 사전에 스케줄될 수 있는 동기식 타일이 있는 디바이스의 경우, 이러한 계산은 다른 종류의 디바이스에 대한 컴파일러 추정치보다 훨씬 더 정확할 수 있다.

후보 할당을 선택한 후, 시스템은 디바이스의 타일들에 의해 실행될 하드웨어 명령들을 생성함으로써 데이터 흐름 그래프 프로그램을 추가로 낮추는 것을 수행할 수 있다. 그런 다음 시스템은 행렬들의 가중치와 함께 하드웨어 명령들을 디바이스에 로드하고, 데이터 흐름 그래프가 나타내는 동작들을 실행하기 위해 디바이스의 하드웨어 명령들을 실행할 수 있다.

도 2a-2b는 서브계층 샤딩의 예를 도시한다. 서브계층 샤딩은 데이터 흐름 그래프에서 특정 노드의 하나의 행렬을 분할하고 다른 타일에 다른 부분을 할당하는 것을 지칭한다. 도 2a는 행렬(200)의 요소들이 대각선을 따라 분할되는 하나의 예시적인 후보 분할을 도시한다. 도 2b는 행렬(200)의 요소들이 열 사이에서 분할되는 다른 예시적인 후보 분할을 도시한다. 대안적으로 또는 추가적으로, 행렬(200)는 행 사이에서 분할될 수 있다. 일부 구현에서, 시스템은 행렬이 크기 임계값을 초과할 때마다 서브계층 샤딩을 사용하여 후보 할당을 생성한다.

서브계층 샤딩을 위한 후보 할당을 생성하려면, 데이터 흐름 그래프에 몇 가지 추가 복잡성이 추가되어야 한다. 특히, 각 계층에 대한 벡터 입력은 종종 서브계층 샤딩 결과의 일부를 수신하는 모든 타일에 브로드캐스트되어야 한다. 또한, 개별 타일에 의해 생성된 부분 합 또는 활성화는 동일한 타일 또는 다른 타일에서 나중 단계(stage)에서 최종 합 또는 활성화로 병합되어야 한다. 컴파일러는 서브계층 샤딩과 관련된 후보 할당을 평가할 때 이러한 추가 복잡성을 고려할 수 있다.

도 3a 내지 도 3c는 평행사변형 시간 슬라이싱의 예를 도시한다. 평행사변형 시간 슬라이싱은 타일들이 상이한 실행 슬로프(slope, 경사)를 갖는 상이한 경로에서 특정 동작을 실행할 때 유리할 수 있다. 실행 슬로프는 타일들이 시퀀스의 모든 동작을 얼마나 빨리 완전히 수행할 수 있는지를 나타낸다. 이러한 애플리케이션은 예를 들어 모든 타일을 통한 단일 경로가 네트워크를 통한 하나의 추론 경로를 나타낼 수 있는 신경망에 일반적이다.

도 3a는 상이한 실행 슬로프로부터 발생하는 충돌을 도시한다. 도 3a에서 가로축은 시간을 나타낸다. 도 3a의 타일들은 각 타일이 2개의 바로 이웃에만 데이터를 제공할 수 있고 2개의 바로 이웃으로부터만 데이터를 수신할 수 있도록 선형 어레이 구조로 배열된다. 일부 구현에서, 선형 어레이 구조는 예를 들어 링 구조로서 둘러싸여서, 마지막 타일이 첫 번째 타일과 통신할 수 있고 그 반대의 경우도 마찬가지이다.

따라서, 타일들은 먼저 타일 0부터 시작하여 타일 7까지의 경로 A를 순차적으로 수행한다. 경로 A는 각 타일이 이전 타일의 출력을 수신할 때까지 실행을 시작할 수 없다는 기계 학습 모델의 공통 속성을 가진다. 따라서, 타일 1은 타일 0이 완료될 때까지 기다려야 하고, 타일 2는 타일 1이 완료될 때까지 기다려야 한다.

도 3a의 점선들은 이 공통 패턴이 경로 A에 대한 평행사변형을 형성하는 방법을 도시한다.

도 3a는 또한 제2 경로인 경로 B를 도시한다. 경로 B의 동작들은 경로 A만큼 시간이 걸리지 않으므로 경로 B는 경로 A보다 실행 슬로프가 더 가파르다.

이 예에서 경로 A와 경로 B의 상이한 실행 슬로프는 타일 5와 타일 6 사이에 충돌을 일으킨다. 이 충돌은 타일 5가 경로 B를 완료할 때까지 타일 6이 경로 A의 해당 부분을 아직 완료하지 않았기 때문에 발생한다. 따라서, 컴파일러 또는 런타임에 의해 스톨(stall, 정지)(301 및 302)이 도입되어야 하며, 이로 인해 타일 5는 타일 6이 경로 A의 동작들을 완료할 때까지 경로 B에 대한 결과를 제공하기를 기다리게 된다.

도 3b는 상이한 실행 슬로프를 관리하기 위한 대안적인 전략을 도시하며, 이는 경로 B가 시작되기 전에 단일 스톨(303)을 도입하여 타일 7에서 경로 B의 마지막 동작이 경로 A의 마지막 동작 직후에 실행될 수 있도록 하는 것이다.

이러한 전략 모두는 타일들이 임의의 작업을 수행하지 않고 유휴 상태로 있는 유휴 영역(310 및 320)을 생성한다. 유휴 영역(310)은 유휴 영역(320)보다 작지만, 다수의 스톨을 도입하면 도 3b의 전략에 없는 추가적인 컴파일 시간 또는 런타임 제어 복잡성이 도입된다.

도 3c는 상이한 실행 슬로프가 실제로 어떻게 추가적인 유휴 영역을 도입할 수 있는지를 예시한다. 도 3c에서, 더 가파른 실행 슬로프를 갖는 경로 B는 제1 유휴 영역(330)을 초래한다. 그러나 경로 A가 경로 B 이후에 다시 실행된다면 제2 유휴 영역(340)이 도입된다.

도 3d는 상이한 실행 슬로프들을 관리하기 위해 평행사변형 시간 슬라이싱을 사용하는 방법을 도시한다. 상이한 실행 슬로프에 의해 도입되는 유휴 영역을 줄이기 위해, 컴파일러는 모든 경로가 효과적으로 동일한 실행 슬로프를 갖도록 강제하는 스케줄을 생성할 수 있다. 따라서 상이한 경로들이 서로 잘 맞아서 유휴 영역이 제거된다.

컴파일러는 스톨들 또는 버퍼링을 사용하여 더 얕은 실행 슬로프를 강제할 수 있다. 예를 들어, 도 3d에 도시된 바와 같이, 경로 B의 실행 슬로프는 상이한 타일 사이에 버퍼링을 도입함으로써 낮아졌다. 즉, 타일 0가 경로 B를 완료한 후 결과는 버퍼(360)에 저장된다. 그러면 타일 0는 즉시 경로 A의 제2 반복 처리를 시작할 수 있다. 대안적으로 또는 추가적으로, 컴파일러는 경로 B의 끝과 경로 A의 제2 반복 시작 사이에 스톨을 삽입할 수 있다. 이 솔루션은 도 3a에 도시된 접근 방식보다 더 많은 스톨을 도입하지만, 전체 유휴 영역은 훨씬 작다.

얕은 실행 슬로프를 강제하면 컴파일러가 후보 할당들을 평가할 때 고려할 수 있는 추가적인 제어 복잡성을 도입한다. 특히, 강제된 얕은 실행 슬로프는 특정 경로에 대한 타이밍 제약을 도입한다. 예를 들어, 도 3d에서, 타이밍 제약은 타일 1의 경로 B가 타일 0의 경로 B 직후에 시작될 수 없다는 것이다.

도 4a 내지 도 4c는 오버샤딩의 예를 도시한다. 오버샤딩은 하드웨어에서 요구하는 것보다 더 미세하게 행렬을 샤딩하는 기술을 말한다. 즉, 계산은 단일 타일에 의해 수행될 수 있지만 행렬은 다른 이유로 인해 샤딩(분할(된다. 종종 이러한 다른 이유는 로드 밸런싱과 관련이 있다.

도 4a는 8개의 타일에 걸쳐 9개의 계층을 갖는 단일 경로 A를 수행하는 것을 도시한다. 따라서, 이 예에서 제9 계층은 타일 0에 완전히 할당된다. 타일 0는 제9 계층의 모든 동작을 완전히 수행할 수 있는 가용성과 메모리 용량을 가지고 있지만, 이 시간 동안 나머지 타일은 완전히 비어 있다.

도 4b는 경로 A의 제9 계층의 오버샤딩을 도시한다. 즉, 단일 타일이 제9 계층의 모든 동작을 수행할 수 있다고 해도, 제9 계층은 오버샤딩되어 다른 8개 타일 모두에 배포된다. 계층내(intralayer) 데이터 종속성이 있거나 없을 수 있으므로 제9 계층의 다른 부분이 부분적으로 또는 전체적으로 병렬로 실행될 수 있다.

따라서, 디바이스는 하나의 타일만 제9 계층을 수행하는 경우보다 더 나은 로드 밸런싱을 갖는다. 이것은 디바이스가 다른 계산도 수행할 때 특히 유리할 수 있다.

도 4c는 런타임 로드 밸런싱을 처리하기 위한 오버샤딩의 또 다른 애플리케이션을 예시한다. 일부 애플리케이션의 경우, 타일의 런타임 로드를 미리 알 수 없다. 그러한 예 중 하나는 디바이스를 사용하여 다양한 번역에 대해 트레이닝된 다양한 모델을 사용하여 자동 기계 번역을 제공할 수 있다는 것이다. 예를 들어, 도 4c의 좌측에 도시된 바와 같이, 타일 0는 모델 A를 실행하기 위해 할당될 수 있고, 타일 1은 모델 B를 실행하기 위해 할당될 수 있다. 그러나, 이러한 모델이 사용되는 실제 순서는 컴파일 시 알 수 없으며, 특히 디바이스가 인입(incoming) 인터넷 트래픽을 서비스하는 백엔드 서버에서 사용되는 경우에는 더욱 그렇다.

따라서, 이는 타일 0가 대부분의 요청을 처리하고 다른 타일은 거의 사용되지 않는 경우일 수 있다.

일부 런타임 로드 밸런싱을 제공하기 위해, 컴파일러는 도 4c의 우측에 도시된 바와 같이 모델들을 오버샤딩하고 모든 모델을 모든 칩에 배포할 수 있다.

이제 런타임에서, 모든 타일은 런타임 로드의 실제 배포에 관계없이 실질적으로 동일한 활용도를 가질 수 있다.

도 5a 내지 도 5c는 지그재그 샤딩으로 지칭되는 오버샤딩의 다른 버전의 예를 도시한다. 신경망을 포함한 많은 기계 학습 애플리케이션의 경우, 계층의 계산 복잡성은 감소하지만 메모리 요구 사항은 증가한다는 공통 패턴이 나타난다.

따라서, 도 5a에 도시된 바와 같이, 메모리 패턴은 각각의 후속 타일이 점점 더 많은 메모리를 필요로 하는 결과를 초래할 수 있다. 그리고 도 5b에 도시된 바와 같이, 계산 패턴은 점점 더 적은 계산 자원을 필요로 한다.

컴파일러는 지그재그 샤딩을 사용하여 모든 타일이 보다 밸런싱된 메모리와 계산 할당을 갖도록 할 수 있다. 지그재그 샤딩은 기본적으로 다른 보완 계층을 함께 페어링하여 그들이 동일한 타일에 의해 실행되도록 한다. 따라서, 예를 들어 지그재그 샤딩은 동일한 타일이 제1 계층과 제8 계층, 제2 계층과 제7 계층, 제3 계층과 제6 계층, 제4 계층과 제5 계층을 실행할 것임을 보장할 수 있다. 이 할당은 계산 패턴이 지그재그 형태를 취하는 도 5c에 도시되어 있다.

도 5c에 도시된 바와 같이, 제1 계층인 계층 1은 오버샤딩되고 타일 0-3 사이에 배포되어 제1 계층의 계산 복잡도를 분할한다. 유사하지만 보완적인 방식으로, 제8 계층도 분할되어 동일한 타일 0-3사이에 배포되어 제8 계층의 메모리 요구 사항을 분할한다.

마찬가지로, 제2 계층은 항상 제7 계층과 동일한 타일에 할당되고, 제3 계층은 항상 제6 계층과 동일한 타일에 할당되며, 제4 계층은 항상 제5 계층과 동일한 타일에 할당된다.

도 2 내지 도 4와 관련하여 위에서 설명한 샤딩 기술의 예 각각은 단독으로 또는 다른 샤딩 기술 중 임의의 하나 이상과 조합하여 사용될 수 있다.

도 6은 다수의 동기식 프로세서를 갖는 시스템의 프로세싱을 구현하는데 사용될 수 있는 타일(600)의 예를 도시한다. 예를 들어, 타일(600)은 타일의 선형 어레이에서 또는 타일들이 타일의 선형 어레이로서 동작하는 시스템의 하나의 타일로서 사용될 수 있다.

각 타일(600)은 로컬 메모리(602) 및 그 메모리(602)에 연결된 계산 어레이(604)를 포함한다. 로컬 메모리(602)는 계산 어레이(604)에 근접하게 위치된 물리적 메모리를 포함한다. 계산 어레이(604)는 다수의 셀(606)을 포함한다. 계산 어레이(604)의 각 셀(606)은 셀(606)에 대한 활성화 입력 및 가중치 입력과 같은 데이터 입력에 기초하여 계산(예를 들어, 곱셈 및 누적 연산)을 수행하도록 구성된 회로를 포함한다. 각 셀은 클럭 신호의 사이클에 대한 계산(예를 들어, 곱셈 및 누적 연산)을 수행할 수 있다. 계산 어레이(604)는 열보다 더 많은 행, 행보다 더 많은 열, 또는 동일한 수의 열 및 행을 가질 수 있다. 예를 들어, 도 6에 도시된 예에서, 계산 어레이(604)는 8행 및 8열로 배열된 64개의 셀을 포함한다. 16개 셀, 32개 셀, 128개 셀 또는 256개 셀을 갖는 계산 어레이와 같은 다른 계산 어레이 크기도 가능한다. 각 타일은 동일한 수의 셀 및/또는 동일한 크기의 계산 어레이를 포함할 수 있다.

타일(600)에 포함된 메모리(602)는 예를 들어, SRAM과 같은 랜덤 액세스 메모리(RAM)를 포함할 수 있다. 각 메모리(602)는 다수의 타일을 갖는 시스템의 n개의 타일(502)과 관련된 총 메모리의 (1/n)을 저장하도록 구성될 수 있다. 메모리(602)는 단일 칩으로 또는 다중 칩으로 제공될 수 있다. 예를 들어, 도 6에 도시된 메모리(602)는 4개의 단일 포트 SRAM으로 제공되며, 이들 각각은 계산 어레이(604)에 연결된다. 대안적으로, 메모리(602)는 다른 구성 중에서도 2개의 단일 포트 SRAM 또는 8개의 단일 포트 SRAM으로 제공될 수 있다. 메모리의 결합 용량은 오류 정정 코딩 후, 예를 들어 16kB, 32kB, 64kB, 또는 128kB일 수 있지만 이에 한정되지 않는다. 물리적 메모리(602)를 계산 어레이에 국부적으로 제공함으로써, 배선의 밀도가 크게 감소될 수 있다.

타일(600)은 또한 제어 가능한 버스 라인들을 포함한다. 제어 가능한 버스 라인은 다수의 다른 그룹으로 분류될 수 있다. 예를 들어, 제어 가능한 버스 라인들은 각 기본 방향으로 타일 간에 데이터를 전달하도록 구성된 제1 그룹의 범용 제어 가능한 버스 라인(610)을 포함할 수 있다. 즉, 제어 가능한 버스 라인(610)의 제1 그룹은 타일 그리드의 제1 차원(501)을 따라 제1 방향(도 6에서 "동쪽"으로 지칭됨)으로 데이터를 전송하도록 구성된 버스 라인(610a); 타일 그리드의 제1 차원(101)을 따라 제1 방향과 반대인 제2 방향(도 6에서 "서쪽"으로 지칭됨)으로 데이터를 전송하도록 구성된 버스 라인(610b); 타일 그리드의 제2 차원(103)을 따라 제3 방향(도 6에서 "북쪽"으로 지칭됨)으로 데이터를 전송하도록 구성된 버스 라인(610c); 및 타일 그리드의 제2 차원(103)을 따라 제3 방향과 반대인 제4 방향(도 6에서 "남쪽"으로 지칭됨)으로 데이터를 전송하도록 구성된 버스 라인(610d)을 포함할 수 잇다. 범용 버스 라인(610)은 제어 데이터, 활성화 입력 데이터, 통신 인터페이스로/부터의 데이터, 벡터 처리 유닛으로/로부터의 데이터, 및 타일(600)에 의해 저장 및/또는 사용될 데이터(예를 들어, 가중치 입력)를 운반하도록 구성될 수 있다. 타일(600)은 제어 가능한 버스 라인을 제어하여 타일(600)로/로부터 및/또는 메모리(602)로부터 데이터를 라우팅하기 위한 하나 이상의 제어 엘리먼트(621)(예를 들어, 플립플롭 및 멀티플렉서)를 포함할 수 있다.

제어 가능한 버스 라인은 또한 본 명세서에서 계산 어레이 부분 합 버스 라인(620)으로 지칭되는 제2 그룹의 제어 가능한 버스 라인을 포함할 수 있다. 계산 어레이 부분 합 버스 라인(620)은 계산 어레이(604)에 의해 수행된 계산으로부터 데이터 출력을 전달하도록 구성될 수 있다. 예를 들어, 버스 라인(620)은 도 6에 도시된 바와 같이, 계산 어레이(604)의 행들로부터 획득된 부분 합 데이터를 전달하도록 구성될 수 있다. 그러한 경우에, 버스 라인(620)의 수는 어레이(604)의 행의 수와 일치할 것이다. 예를 들어, 8×8 계산 어레이의 경우, 8개의 부분 합 버스 라인(620)이 있을 것이며, 이들 각각은 계산 어레이(604)의 대응하는 행의 출력에 연결된다. 계산 어레이 출력 버스 라인(620)은 예를 들어 타일의 선형 어레이에서 이웃 타일의 계산 어레이에 대한 입력으로서 시스템 내의 다른 타일에 연결하도록 추가로 구성될 수 있다. 예를 들어, 타일(600)의 어레이 부분 합 버스 라인(620)은 타일(600)로부터 적어도 하나의 타일 떨어져 위치된 제2 타일의 계산 어레이의 입력(예를 들어, 부분 합(620a))을 수신하도록 구성될 수 있다. 계산 어레이(604)의 출력은 타일(600)로부터 출력될 수 있는 새로운 부분 합(620b)을 생성하기 위해 부분 합 라인(620)에 추가된다. 그런 다음 부분 합(620b)은 다른 타일로 또는 대안적으로 벡터 처리 유닛으로 전달될 수 있다. 예를 들어, 각 버스 라인(620)은 벡터 프로세싱 유닛의 대응하는 세그먼트(도 5의 세그먼트(506)와 같은)에 연결될 수 있다.

본 명세서에 기술된 주제 및 기능적 동작의 실시예는 디지털 전자 회로, 유형적으로 구현된 컴퓨터 소프트웨어 또는 펌웨어, 본 명세서에 개시된 구조 및 그의 구조적 등가물을 포함하는 컴퓨터 하드웨어 또는 이들 중 하나 이상의 조합으로 구현될 수 있다. 본 명세서에 기술된 주제의 실시예는 하나 이상의 컴퓨터 프로그램, 즉 데이터 처리 장치에 의해 실행되거나 데이터 처리 장치의 작동을 제어하기 위해 유형의 비-일시적 저장 매체에 인코딩된 컴퓨터 프로그램 명령들의 하나 이상의 모듈로 구현될 수 있다. 컴퓨터 저장 매체는 기계 판독 가능 저장 디바이스, 기계 판독 가능 저장 기판, 랜덤 또는 직렬 액세스 메모리 디바이스 또는 이들 중 하나 이상의 조합일 수 있다. 대안적으로 또는 추가적으로, 프로그램 명령들은 데이터 처리 장치에 의한 실행을 위해 적절한 수신기 장치로의 전송을 위해 정보를 인코딩하도록 생성되는 인공적으로 생성된 전파 신호, 예를 들어 기계 생성 전기, 광학 또는 전자기 신호에 인코딩될 수 있다.

"데이터 처리 장치"라는 용어는 데이터 처리 하드웨어를 지칭하며, 예를 들어 프로그램 가능 프로세서, 컴퓨터, 또는 다중 프로세서 또는 컴퓨터를 비롯하여 데이터를 처리하기 위한 모든 종류의 장치, 디바이스 및 기계를 포함한다. 장치는 또한 예를 들어 FPGA(필드 프로그램 가능 게이트 어레이) 또는 주문형 집적회로(ASIC)와 같은 특수 목적 논리 회로일 수 있거나 이를 추가로 포함할 수 있다. 장치는 하드웨어 외에 컴퓨터 프로그램을 위한 실행 환경을 생성하는 코드, 예를 들어 프로세서 펌웨어, 프로토콜 스택, 데이터베이스 관리 시스템, 운영 체제 또는 이들 중 하나 이상의 조합을 구성하는 코드를 선택적으로 포함할 수 있다.

프로그램, 소프트웨어, 소프트웨어 애플리케이션, 앱, 모듈, 소프트웨어 모듈, 스크립트 또는 코드라고도 하거나 설명할 수 있는 컴퓨터 프로그램은 컴파일된 또는 해석된 언어, 또는 선언적 또는 절차적 언어를 비롯한 임의의 형태의 프로그래밍 언어로 작성할 수 있으며, 독립 실행형 프로그램이나 모듈, 컴포넌트, 서브루틴 또는 컴퓨팅 환경에서 사용하기에 적합한 기타 단위를 포함하여 임의의 형태로 배포될 수 있다. 프로그램은 파일 시스템의 파일에 대응할 수 있지만 반드시 그런 것은 아니다. 프로그램은 다른 프로그램이나 데이터, 예를 들어 마크업 언어 문서에 저장된 하나 이상의 스크립트, 문제의 프로그램 전용 단일 파일 또는 다수의 조정 파일(예를 들어, 하나 이상의 모듈, 서브 프로그램 또는 코드의 일부를 저장하는 파일)을 보유하는 파일의 일부에 저장될 수 있다. 컴퓨터 프로그램은 하나의 컴퓨터 또는 한 사이트에 있거나 여러 사이트에 분산되어 있고 데이터 통신 네트워크에 의해 상호 연결된 여러 컴퓨터에서 실행되도록 배포될 수 있다.

하나 이상의 컴퓨터로 구성된 시스템이 특정 동작들 또는 액션들을 수행하도록 구성된다는 것은 시스템에 동작시 시스템으로 하여금 동작들 또는 액션들을 수행하게 하는 소프트웨어, 펌웨어, 하드웨어 또는 이들의 조합이 설치되어 있음을 의미한다. 하나 이상의 컴퓨터 프로그램이 특정 동작들 또는 액션들을 수행하도록 구성된다는 것은 하나 이상의 프로그램이 데이터 처리 장치에 의해 실행될 때 장치로 하여금 동작들 또는 액션들을 수행하게 하는 명령들을 포함한다는 것을 의미한다.

본 명세서에서 사용되는 바와같이, "엔진" 또는 "소프트웨어 엔진"은 입력과 다른 출력을 제공하는 소프트웨어로 구현된 입/출력 시스템을 의미한다. 엔진은 라이브러리, 플랫폼, 소프트웨어 개발 키트("SDK") 또는 오브젝트와 같은 인코딩된 기능 블록일 수 있다. 각 엔진은 서버, 휴대폰, 태블릿 컴퓨터, 노트북 컴퓨터, 음악 플레이어, 전자책 리더, 랩탑 또는 데스크탑 컴퓨터, PDA, 스마트폰 또는 하나 이상의 프로세서와 컴퓨터 판독 가능 매체를 포함하는 기타 고정형 또는 휴대용 디바이스와 같은 적절한 유형의 컴퓨팅 디바이스에서 구현될 수 있다. 추가로, 둘 이상의 엔진이 동일한 컴퓨팅 디바이스 또는 다른 컴퓨팅 디바이스에서 구현될 수 있다.

본 명세서에 설명된 프로세스 및 논리 흐름은 입력 데이터에 대해 작동하고 출력을 생성함으로써 기능을 수행하기 위해 하나 이상의 컴퓨터 프로그램을 실행하는 하나 이상의 프로그래밍 가능한 컴퓨터에 의해 수행될 수 있다. 프로세스 및 논리 흐름은 FPGA 또는 ASIC과 같은 특수 목적 논리 회로 또는 특수 목적 논리 회로와 하나 이상의 프로그래밍된 컴퓨터의 조합에 의해 수행될 수도 있다.

컴퓨터 프로그램의 실행에 적합한 컴퓨터는 범용 또는 특수 목적 마이크로프로세서 또는 둘 다, 또는 다른 종류의 중앙 처리 장치를 기반으로 할 수 있다. 일반적으로, 중앙 처리 장치는 판독 전용 메모리나 랜덤 액세스 메모리 또는 둘 다로부터 명령과 데이터를 수신한다. 컴퓨터의 필수 엘리먼트는 명령을 수행하거나 실행하기 위한 중앙 처리 장치와 명령 및 데이터를 저장하기 위한 하나 이상의 메모리 디바이스이다. 중앙 처리 장치와 메모리는 특수 목적 논리 회로에 의해 보완되거나 통합될 수 있다. 일반적으로, 컴퓨터는 또한 데이터를 저장하기 위한 하나 이상의 대용량 저장 디바이스, 예를 들어 자기, 광자기 디스크 또는 광 디스크로부터 데이터를 수신하거나 이들로 데이터를 전송하거나 둘 모두를 포함하거나 작동 가능하게 연결된다. 그러나, 컴퓨터에는 그러한 디바이스들이 필요하지 않다. 또한, 컴퓨터는 다른 디바이스, 예를 들어 이동 전화, 개인 휴대 정보 단말기(PDA), 모바일 오디오 또는 비디오 플레이어, 게임 콘솔, GPS 수신기 또는 휴대용 저장 디바이스(예를 들어 USB 플래시 드라이브)에 내장될 수 있다.

컴퓨터 프로그램 명령 및 데이터를 저장하기에 적합한 컴퓨터 판독 가능 매체는 예를 들어 반도체 메모리 디바이스(EPROM, EEPROM 및 플래시 메모리 디바이스); 자기 디스크(예를 들어, 내부 하드 디스크 또는 이동식 디스크); 광자기 디스크; 및 CD-ROM 및 DVD-ROM 디스크를 비롯하여 모든 형태의 비-휘발성 메모리, 매체 및 메모리 디바이스를 포함한다.

사용자와의 상호 작용을 제공하기 위해, 본 명세서에 기술된 주제의 실시예는 사용자에게 정보를 표시하기 위한 디스플레이 디바이스(예를 들어, CRT(음극선 관) 또는 LCD(액정 디스플레이) 모니터) 및 사용자가 컴퓨터에 입력을 제공할 수 있는 키보드 및 포인팅 디바이스(예를 들어, 마우스 또는 트랙볼)를 갖는 컴퓨터 상에 구현될 수 있다. 사용자와의 상호 작용을 제공하기 위해 다른 종류의 디바이스가 사용될 수도 있는데, 예를 들어, 사용자에게 제공되는 피드백은 예를 들어 시각적 피드백, 청각적 피드백 또는 촉각적 피드백과 같은 임의의 형태의 감각 피드백일 수 있으며, 사용자로부터의 입력은 음향, 음성 또는 촉각 입력을 포함하여 임의의 형태로 수신될 수 있다. 또한, 컴퓨터는 사용자가 사용하는 디바이스로 문서를 전송하고 그로부터 문서를 수신함으로써 예를 들어, 웹 브라우저로부터 수신된 요청에 응답하여 사용자의 클라이언트 디바이스상의 웹 브라우저로 웹 페이지를 전송함으로써 사용자와 상호 작용할 수 있다.

본 명세서에 기술된 주제의 실시예는 백엔드 컴포넌트(예를 들어, 데이터 서버)를 포함하거나, 미들웨어 컴포넌트(예를 들어, 애플리케이션 서버)를 포함하거나 프런트 엔드 컴포넌트(예를 들어, 사용자가 본 명세서에 설명된 주제의 구현과 상호 작용할 수 있는 그래픽 사용자 인터페이스 또는 웹 브라우저를 갖는 클라이언트 컴퓨터)를 포함하거나 이러한 백엔드, 미들웨어 또는 프런트 엔드 컴포넌트 중 하나 이상의 조합을 포함하는 컴퓨팅 시스템에서 구현될 수 있다. 시스템의 컴포넌트는 디지털 데이터 통신의 임의의 형태 또는 매체, 예를 들어 통신 네트워크에 의해 상호 연결될 수 있다. 통신 네트워크의 예에는 근거리 통신망("LAN") 및 광역 네트워크("WAN"), 인터-네트워크(예를 들어, 인터넷) 및 피어-투-피어 네트워크(예를 들어, 애드혹 피어-투-피어 네트워크)가 포함될 수 있다.

컴퓨팅 시스템은 클라이언트 및 서버를 포함할 수 있다. 클라이언트와 서버는 일반적으로 서로 떨어져 있으며 일반적으로 통신 네트워크를 통해 상호 작용한다. 클라이언트와 서버의 관계는 개별 컴퓨터에서 실행되고 서로 클라이언트-서버 관계를 갖는 컴퓨터 프로그램으로 인해 발생한다. 일부 실시예에서, 서버는 (클라이언트 디바이스와 상호 작용하는 사용자에게 데이터를 표시하고 사용로부터 사용자 입력을 수신하기 위해) 데이터(예를 들어, HTML 페이지)를 클라이언트 디바이스로 전송한다. 클라이언트 디바이스에서 생성된 데이터(예를 들어, 사용자 상호 작용 결과)는 서버에서 클라이언트 디바이스로부터 수신될 수 있다.

위에서 설명한 실시예에 추가하여 다음 실시예 또한 혁신적이다.

실시예 1: 방법은 복수의 동기식 타일을 갖는 디바이스에 의해 수행될 개별 행렬 연산을 각각 나타내는 복수의 노드를 포함하는 데이터 흐름 그래프의 표현을 수신하는 단계와; 복수의 동기식 타일의 각 타일에 대한 데이터 흐름 그래프의 개별 부분의 복수의 후보 할당을 생성하는 단계와; 디바이스의 하나 이상의 자원 제약에 따라 복수의 후보 할당의 각 후보 할당을 평가하는 단계와; 그리고 각 후보 할당을 평가하는 것에 기초하여 후보 할당들 중 하나를 선택하는 단계를 포함한다.

실시예 2: 실시예 1에 있어서, 복수의 동기식 타일의 각 타일은 독립적인 처리 엘리먼트의 계산 어레이를 포함한다.

실시예 3: 실시예 1과 2 중 어느 하나에 있어서, 하나 이상의 자원 제약에 따라 복수의 후보 할당을 생성하는 단계는 관련 동작들의 모든 가중치가 대응하는 동기식 타일에 로컬인 로컬 SRAM 내에 맞아야 함을 지정하는 SRAM 메모리 제약에 따라 후보 할당을 생성하는 단계를 포함한다.

실시예 4: 실시예 3에 있어서, 각 로컬 SRAM은 동작을 수행할 동일한 동기식 타일에 통합된 상주 메모리이다.

실시예 5: 실시예 1 내지 4 중 어느 하나에 있어서, 복수의 후보 할당을 생성하는 단계는 상이한 개별 계층의 행렬을 상이한 개별 타일에 할당하는 단계를 포함한다.

실시예 6: 실시예 1 내지 5 중 어느 하나에 있어서, 복수의 후보 할당을 생성하는 단계는 행렬의 상이한 블록을 상이한 개별 동기식 타일에 할당하는 단계를 포함하여, 프로그램의 특정 노드에 대한 행렬에 대해 서브계층 샤딩을 수행하는 단계를 포함한다.

실시예 7: 실시예 6에 있어서, 행렬의 다른 블록을 다른 개별 동기식 타일에 할당하는 단계는 행 또는 열을 따라 행렬을 분할하는 단계 또는 행렬을 대각선으로 분할하는 단계를 포함한다.

실시예 8: 실시예 7에 있어서, 동작들은 크기 임계값을 초과하는 임의의 행렬에 대해 서브계층 샤딩을 수행하는 단계를 더 포함한다.

실시예 9: 실시예 1 내지 8 중 어느 하나에 있어서, 복수의 후보 할당을 생성하는 단계는 초기에 상이한 실행 슬로프를 갖는 상이한 경로가 실질적으로 유사한 실행 슬로프를 갖도록 평행사변형 시간 슬라이싱을 수행하는 단계를 포함한다.

실시예 10: 실시예 9에 있어서, 시간 슬라이싱을 수행하는 단계는 2개의 상이한 경로 각각에 대한 개별 실행 슬로프를 계산하는 단계; 제1 경로가 제2 경로보다 더 작은 실행 슬로프를 갖는다고 결정하는 단계; 및 이에 응답하여, 제1 경로가 더 얕은 실행 슬로프를 갖도록 후보 할당을 수정하는 단계를 포함한다.

실시예 11: 실시예 10에 있어서, 후보 할당을 수정하는 단계는 버퍼링 또는 스톨들(sta11)을 후보 할당에 삽입하는 단계를 포함한다.

실시예 12: 실시예 1 내지 11 중 어느 하나에 있어서, 복수의 후보 할당을 생성하는 단계는 타일들 중 하나에 의해 완전히 수행될 수 있는 데이터 흐름 그래프의 노드가 다수의 상이한 타일로 분할되도록 오버샤딩을 수행하는 단계를 포함한다.

실시예 13: 실시예 12에 있어서, 오버샤딩을 수행하는 단계는 하나의 개별 계층을 각 타일에 할당하는 단계 및 모든 타일 중에서 마지막 계층을 분할하는 단계를 포함한다.

실시예 14: 실시예 12에 있어서, 오버샤딩을 수행하는 단계는 모든 타일에 걸쳐 복수의 행렬을 분할하는 단계를 포함한다.

실시예 15: 실시예 1 내지 14 중 어느 하나에 있어서, 복수의 후보 할당을 생성하는 단계는 상이한 메모리 및 계산 요구 사항을 갖는 상이한 계층들을 함께 페어링함으로써 지그재그 샤딩을 수행하는 단계를 포함한다.

실시예 16: 실시예 15에 있어서, 상이한 계층들을 함께 페어링하는 단계는 동일한 타일이 제1 계층 및 마지막 계층 둘 다를 실행하도록 제1 계층을 마지막 계층과 페어링하는 단계를 포함한다.

실시예 17: 실시예 16에 있어서, 제1 계층은 가장 큰 계산 요구 사항을 가지며, 마지막 계층은 가장 큰 메모리 요구 사항을 갖는다.

실시예 18: 실시예 1 내지 17 중 어느 하나에 있어서, 타일들은 각 타일이 하나 또는 두 개의 이웃 타일에만 데이터를 제공하도록 구성되도록 선형 어레이로 배열된다.

실시예 19: 시스템은 하나 이상의 컴퓨터 및 하나 이상의 컴퓨터에 의해 실행될 때 하나 이상의 컴퓨터로 하여금 실시예 1 내지 18 중 어느 하나의 방법을 수행하게 하도록 동작 가능한 명령들을 저장하는 하나 이상의 저장 디바이스를 포함한다.

실시예 20: 컴퓨터 프로그램으로 인코딩된 컴퓨터 저장 매체로서, 프로그램은 데이터 처리 장치에 의해 실행될 때 데이터 처리 장치로 하여금 실시예 1 내지 18 중 어느 하나의 방법을 수행하게 하도록 동작 가능한 명령들을 포함한다.

본 명세서에는 많은 특정 구현 세부 사항이 포함되어 있지만, 이들은 임의의 발명의 범위 또는 청구될 수 있는 것에 대한 제한으로 해석되어서는 안되며, 오히려 특정 발명의 특정 실시예에 특정된 특징들의 설명으로 해석되어야 한다. 별도의 실시예의 맥락에서 본 명세서에 설명된 특정 특징들은 또한 단일 실시예에서 조합하여 구현될 수 있다. 반대로, 단일 실시예의 맥락에서 설명된 다양한 특징은 또한 다중 실시예에서 개별적으로 또는 임의의 적절한 서브 조합으로 구현될 수 있다. 더욱이, 특징들이 특정 조합으로 작용하는 것으로 위에서 설명될 수 있고 심지어 처음에 그렇게 주장될 수도 있지만, 청구된 조합으로부터의 하나 이상의 특징은 일부 경우 조합으로부터 제외될 수 있고, 청구된 조합은 하위 조합 또는 하위 조합의 변형에 대한 것일 수 있다.

유사하게, 동작들은 특정 순서로 도면에 도사되지만, 이는 바람직한 결과를 달성하기 위해 그러한 동작들이 특정 순서 또는 순차적 순서로 수행되거나 모든 예시된 동작들이 수행될 것을 요구하는 것으로 이해되어서는 안된다. 특정 상황에서, 멀티 태스킹 및 병렬 처리가 유리할 수 있다. 더욱이, 위에서 설명된 실시예에서 다양한 시스템 컴포넌트의 분리는 모든 실시예에서 그러한 분리를 요구하는 것으로 이해되어서는 안되며, 설명된 프로그램 컴포넌트 및 시스템은 일반적으로 단일 소프트웨어 제품으로 함께 통합되거나 다수의 소프트웨어 제품으로 패키징될 수 있음을 이해해야 한다.

주제의 특정 실시예가 설명되었다. 다른 실시예는 다음 청구항의 범위 내에 있다. 예를 들어, 청구범위에 언급된 동작은 다른 순서로 수행될 수 있으며 여전히 바람직한 결과를 얻을 수 있다. 일 예로서, 첨부 도면에 도시된 프로세스는 바람직한 결과를 달성하기 위해 도시된 특정 순서 또는 순차적인 순서를 반드시 필요로 하지는 않는다. 어떤 경우에는 멀티태스킹과 병렬 처리가 유리할 수 있다.

Claims

시스템으로서,
하나 이상의 컴퓨터 및 하나 이상의 컴퓨터에 의해 실행될 때 하나 이상의 컴퓨터로 하여금 동작들을 수행하게 하는 명령들을 저장한 하나 이상의 저장 디바이스를 포함하고, 상기 동작들은,
복수의 동기식 타일을 갖는 디바이스에 의해 수행될 개별 행렬 연산을 각각 나타내는 복수의 노드를 포함하는 데이터 흐름(dataflow) 그래프의 표현을 수신하는 동작;
프로그램의 특정 노드에 대한 행렬의 서브계층 샤딩(sharding)에 기초하여, 복수의 동기식 타일의 각 타일에 대한 데이터 흐름 그래프의 개별 부분의 복수의 후보 할당을 생성하는 동작 - 상기 서브계층 샤딩은 행렬의 상이한 블록을 상이한 각각의 동기식 타일에 할당하는 것을 포함함 -;
디바이스의 하나 이상의 자원 제약에 따라 복수의 후보 할당의 각각의 후보 할당을 평가하는 동작; 및
각각의 후보 할당을 평가하는 것에 기초하여 후보 할당들 중 하나를 선택하는 동작을 포함하는 것을 특징으로 하는 시스템.
제1항에 있어서,
상기 복수의 동기식 타일의 각 타일은,
독립적인 프로세싱 엘리먼트의 계산 어레이를 포함하는 것을 특징으로 하는 시스템.
제1항에 있어서,
상기 복수의 후보 할당을 생성하는 동작은,
관련 연산들의 가중치 크기가 해당 동기식 타일에 로컬인 로컬 SRAM(Static Random Access Memory)의 용량을 초과해서는 안 됨을 지정하는 SRAM 제약에 따라 후보 할당을 생성하는 동작을 포함하는 것을 특징으로 하는 시스템.
제3항에 있어서,
각 로컬 SRAM은 동작들을 수행할 동일한 동기식 타일에 통합된 상주 메모리인 것을 특징으로 하는 시스템.
제1항에 있어서,
상기 복수의 후보 할당을 생성하는 동작은,
상이한 개별 계층의 행렬을 상이한 개별 타일에 할당하는 동작을 포함하는 것을 특징으로 하는 시스템.
삭제
제1항에 있어서,
상기 행렬의 상이한 블록을 상이한 개별 동기식 타일에 할당하는 것은,
행 또는 열을 따라 행렬을 분할하는 동작 또는 행렬을 대각선으로 분할하는 것을 포함하는 것을 특징으로 하는 시스템.
제7항에 있어서,
상기 동작들은,
크기 임계값을 초과하는 임의의 행렬에 대해 서브계층 샤딩을 수행하는 동작을 더 포함하는 것을 특징으로 하는 시스템.
제1항에 있어서,
상기 복수의 후보 할당을 생성하는 동작은,
초기에 상이한 실행 슬로프를 갖는 상이한 경로가 대응하는 실행 슬로프를 갖도록 평행사변형 시간 슬라이싱을 수행하는 동작을 포함하는 것을 특징으로 하는 시스템.
제9항에 있어서,
상기 평행사변형 시간 슬라이싱을 수행하는 동작은,
2개의 상이한 경로 각각에 대한 개별 실행 슬로프를 계산하는 동작;
제1 경로가 제2 경로보다 더 작은 실행 슬로프를 갖는다고 결정하는 동작; 및
이에 응답하여, 제1 경로가 더 얕은 실행 슬로프를 갖도록 후보 할당을 수정하는 동작을 포함하는 것을 특징으로 하는 시스템.
제10항에 있어서,
상기 후보 할당을 수정하는 동작은,
버퍼링 또는 스톨을 후보 할당에 삽입하는 동작을 포함하는 것을 특징으로 하는 시스템.
제1항에 있어서,
상기 복수의 후보 할당을 생성하는 동작은,
타일들 중 하나에 의해 완전히 수행될 수 있는 데이터 흐름 그래프의 노드가 다수의 상이한 타일로 분할되도록 오버샤딩을 수행하는 동작을 포함하는 것을 특징으로 하는 시스템.
제12항에 있어서,
상기 오버샤딩을 수행하는 동작은,
하나의 개별 계층을 각 타일에 할당하는 동작 및 모든 타일 중에서 마지막 계층을 분할하는 동작을 포함하는 것을 특징으로 하는 시스템.
제12항에 있어서,
상기 오버샤딩을 수행하는 동작은,
모든 타일에 걸쳐 복수의 행렬을 분할하는 동작을 포함하는 것을 특징으로 하는 시스템.
제1항에 있어서,
상기 복수의 후보 할당을 생성하는 동작은,
상이한 메모리 및 계산 요구사항을 갖는 상이한 계층들을 함께 페어링함으로써 지그재그 샤딩을 수행하는 동작을 포함하는 것을 특징으로 하는 시스템.
제15항에 있어서,
상기 상이한 계층들을 함께 페어링하는 것은,
동일한 타일이 제1 계층 및 마지막 계층 모두를 실행하도록 제1 계층을 마지막 계층과 페어링하는 것을 포함하는 것을 특징으로 하는 시스템.
제16항에 있어서,
상기 제1 계층은 가장 큰 계산 요구사항을 가지며 그리고 마지막 계층은 가장 큰 메모리 요구사항을 갖는 것을 특징으로 하는 시스템.
제1항에 있어서,
상기 타일들은 각 타일이 하나 또는 두 개의 인접 타일에만 데이터를 제공하도록 구성되도록 선형 어레이로 배열되는 것을 특징으로 하는 시스템.
컴퓨터 구현 방법으로서,
데이터 처리 장치에 의해, 복수의 동기식 타일을 갖는 디바이스에 의해 수행될 개별 행렬 연산을 각각 나타내는 복수의 노드를 포함하는 데이터 흐름 그래프의 표현을 수신하는 단계;
데이터 처리 장치에 의해 프로그램의 특정 노드에 대한 행렬의 서브계층 샤딩에 기초하여, 복수의 동기식 타일의 각 타일에 대한 데이터 흐름 그래프의 개별 부분의 복수의 후보 할당을 생성하는 단계 - 상기 서브계층 샤딩은 행렬의 상이한 블록을 상이한 각각의 동기식 타일에 할당하는 것을 포함함 -;
데이터 처리 장치에 의해, 디바이스의 하나 이상의 자원 제약에 따라 복수의 후보 할당의 각각의 후보 할당을 평가하는 단계; 및
데이터 처리 장치에 의해, 각각의 후보 할당을 평가하는 것에 기초하여 후보 할당들 중 하나를 선택하는 단계를 포함하는 것을 특징으로 하는 컴퓨터 구현 방법.
동작들을 수행하도록 데이터 처리 장치에 의해 실행될 수 있는 명령들을 포함하는 컴퓨터 프로그램으로 인코딩된 컴퓨터 저장 매체로서, 상기 동작들은,
복수의 동기식 타일을 갖는 디바이스에 의해 수행될 개별 행렬 연산을 각각 나타내는 복수의 노드를 포함하는 데이터 흐름 그래프의 표현을 수신하는 동작;
프로그램의 특정 노드에 대한 행렬의 서브계층 샤딩에 기초하여, 복수의 동기식 타일의 각 타일에 대한 데이터 흐름 그래프의 개별 부분의 복수의 후보 할당을 생성하는 동작 - 상기 서브계층 샤딩은 행렬의 상이한 블록을 상이한 각각의 동기식 타일에 할당하는 것을 포함함 -;
디바이스의 하나 이상의 자원 제약에 따라 복수의 후보 할당의 각각의 후보 할당을 평가하는 동작; 및
각각의 후보 할당을 평가하는 것에 기초하여 후보 할당들 중 하나를 선택하는 동작을 포함하는 것을 특징으로 하는 컴퓨터 저장 매체.