KR102616212B1 - 다수의 컴퓨팅 코어들상의 데이터 드라이브 스케줄러 - Google Patents

Abstract

프로세서의 복수의 컴퓨팅 코어들의 데이터 드라이브 스케줄링을 위한 방법들, 디바이스들 및 시스템들. 복수의 쓰레드들은 디폴트 스케줄에 따라 복수의 컴퓨팅 코어들상에서 실행될 수 있다. 복수의 쓰레드들은 복수의 쓰레드들간에 상관관계들을 결정하기 위해 실행에 기초하여 분석될 수 있다. 데이터 드라이브 스케줄이 상관관계들에 기초하여 생성될 수 있다. 복수의 쓰레드들은 데이터 드라이브 스케줄에 따라 복수의 컴퓨팅 코어들상에서 실행될 수 있다.

Description

다수의 컴퓨팅 코어들상의 데이터 드라이브 스케줄러

관련 출원들에 대한 상호 참조

본 출원은, 2015년 12월 28일에 출원된, 미국 정규 특허 출원 번호 제14/981,257호의 이득을 주장하며, 이는 본 출원에 전체가 개시된 것 처럼 참조로서 통합된다.

개시된 실시예들은 전반적으로 프로세싱 디바이스들에 관한 것으로, 보다 상세하게는, 다수의 컴퓨트 유닛들을 갖는 프로세서들에 메모리 관리에 관한 것이다.

많은 최신 마이크로프로세서들은 멀티코어 프로세서를 형성하기 위해 단일 프로세서로 많은 프로세서 코어들을 결합시킨다. 멀티코어 프로세서들은 주로 병렬 컴퓨팅을 수행함으로써 장점을 제공한다. 예를 들어, 멀티코어 프로세서들은 프로세서내 상이한 병렬 코어들상에서 상이한 프로그램들, 또는 상이한 쓰레드들, 쓰레드 그룹들, 또는 단일 프로그램의 웨이브(wave)들을 실행시키기 위해 쓰레드-레벨 병렬 처리를 활용할 수 있다.

그래픽 프로세싱 유닛들 (GPU들)은 다양한 그래픽 프로세싱 태스크들이 특히 병렬 처리에 적합하기 때문에 멀티 코어 프로세서로 구현할 때 이점을 얻을 수 있다. 예를 들어, 3 차원 (3D) 프로젝션(projection)은 "완벽하게 평행하거나" 또는 "당혹스럽게(embarrassingly) 평행한"것으로 언급된 태스크들의 카테고리에 속할 수 있다.

멀티코어 아키텍처들에서, 각각의 코어는 로컬 메모리, 예컨대 L1 캐시를 가질 수 있다. 그러나 다이 사이즈의 감소와 같은 다양한 이유들 때문에, 멀티 코어 장치의 여러 코어 (또는 전부)는 공유 L2 또는 마지막 레벨 (LLC: last level) 캐시, 다른 유형의 캐시 또는 캐시 또는 메모리 계층의 다른 레벨과 같은 메모리를 공유 할 수 있다. 그러나, 메모리를 공유하는 것은 코어간에 메모리 자원들에 대한 경쟁으로 귀결될 수 있다.

일부 실시예들은 프로세서의 복수의 컴퓨팅 코어들의 데이터 드라이브 스케줄링(data driven scheduling)을 위한 방법을 제공한다. 복수의 쓰레드들은 디폴트 스케줄에 따라 상기 복수의 컴퓨팅 코어들상에서 실행될 수 있다. 상기 복수의 쓰레드들은 상기 복수의 쓰레드들간에 상관관계(correlation)들을 결정하기 위해 상기 실행에 기초하여 분석될 수 있다. 데이터 드라이브 스케줄은 상기 상관관계들에 기초하여 생성될 수 있다. 상기 복수의 쓰레드들은 상기 데이터 드라이브 스케줄에 따라 상기 복수의 컴퓨팅 코어들상에서 실행될 수 있다.

일부 실시예들은 데이터 드라이브 스케줄링(data driven scheduling)을 위해 구성된 프로세서를 제공한다. 상기 프로세서는 복수의 컴퓨팅 코어들 및 상기 컴퓨팅 코어들의 각각에 의해 공유되는 메모리를 포함한다. 상기 프로세서는 디폴트 스케줄에 따라 상기 복수의 컴퓨팅 코어들상에서 실행하기 위한 복수의 쓰레드들을 디스패치(dispatch)하도록 구성된 디스패칭 회로부(dispatching circuitry)를 포함한다. 상기 프로세서는 상기 복수의 쓰레드간에 상관관계들을 결정하기 위해 상기 실행에 기초하여 상기 복수의 쓰레드들을 분석하도록 구성된 상관관계 회로부를 포함한다. 상기 프로세서는 상기 상관관계들에 기초하여 데이터 드라이브 스케줄을 결정하도록 구성된 스케줄링 회로부를 포함한다. 상기 디스패칭 회로부는 상기 데이터 드라이브 스케줄에 따라 상기 복수의 컴퓨팅 코어들상에서 실행하기 위한 상기 복수의 쓰레드들을 디스패치하도록 더 구성된다.

일부 실시예들은 멀티코어 프로세서의 메모리 관리를 위한 시스템을 제공한다. 상기 시스템은 프로세서를 포함한다. 상기 프로세서는 복수의 컴퓨팅 코어들 및 상기 컴퓨팅 코어들의 각각에 의해 공유되는 메모리를 포함한다. 상기 프로세서는 디폴트 스케줄에 따라 상기 복수의 컴퓨팅 코어들상에서 실행하기 위한 복수의 쓰레드들을 디스패치(dispatch)하도록 구성된 디스패칭 회로부(dispatching circuitry)를 포함한다. 상기 프로세서는 상기 복수의 쓰레드간에 상관관계들을 결정하기 위해 상기 실행에 기초하여 상기 복수의 쓰레드들을 분석하도록 구성된 상관관계 회로부를 포함한다. 상기 프로세서는 상기 상관관계들에 기초하여 데이터 드라이브 스케줄을 결정하도록 구성된 스케줄링 회로부를 포함한다. 상기 디스패칭 회로부는 상기 데이터 드라이브 스케줄에 따라 상기 복수의 컴퓨팅 코어들상에서 실행하기 위한 상기 복수의 쓰레드들을 디스패치하도록 더 구성된다.

첨부 도면과 결부하여 예시의 방식으로 제공되는 후술하는 설명으로부터 더욱 상세한 이해를 가질 수 있다:
도 1은 하나 이상의 개시된 실시예가 구현될 수 있는 예시적인 디바이스의 블록도이다;
도 2는 멀티코어 프로세서의 다수의 코어들상에서의 실행을 위한 다수의 쓰레드들을 스케줄링하기 위한 예시 방법을 예시하는 플로우 차트이다;
도 3은 멀티코어 프로세서의 다수의 코어들상에서의 실행을 위한 다수의 쓰레드들을 스케줄링하기 위한 예시 방법을 예시하는 플로우 차트이다;
도 4는 데이터 드라이브 스케줄링을 구현하는 예제 시스템을 예시하는 블럭 다이어그램이다;
도 5는 상관관계 어레이의 예시 상태를 예시하는 표다;
도 6은 데이터 드라이브 스케줄링을 구현하는 다른 예제 시스템을 예시하는 블럭 다이어그램이다;
도 7은 상관관계 어레이의 다른 예시 상태를 예시하는 표다;
도 8은 데이터 드라이브 스케줄링을 구현하는 다른 예제 시스템을 예시하는 블럭 다이어그램이다;
도 9는 상관관계 어레이의 다른 예시 상태를 예시하는 표다;
도 10은 데이터 드라이브 스케줄링을 구현하는 다른 예제 시스템을 예시하는 블럭 다이어그램이다; 및
도 11은 상관관계 어레이의 다른 예시 상태를 예시하는 표다.

도 1은 하나 이상의 개시된 실시예가 구현될 수 있는 예시적인 디바이스(100)의 블록도이다. 디바이스(100)는 예를 들어, 컴퓨터, 게이밍 디바이스, 핸드헬드 디바이스, 셋톱 박스, 텔레비젼, 모바일 폰 또는 태블릿 컴퓨터를 포함할 수 있다. 디바이스(100)는 프로세서(102), 메모리(104), 스토리지(106), 하나 이상의 입력 디바이스(108) 및 하나 이상의 출력 디바이스(110)를 포함한다. 또한, 디바이스(100)는 선택적으로 입력 드라이버(112) 및 출력 드라이버(114)를 포함한다. 디바이스(100)가 도 1에 나타내어지지 않은 추가적인 요소를 포함할 수 있다는 것이 이해된다.

프로세서(102)는 중앙 처리 장치(CPU), 그래픽 프로세싱 유닛(GPU), 동일 다이 상에 위치된 CPU 및 GPU 또는 하나 이상의 프로세서 코어를 포함할 수 있으며, 각각의 프로세서 코어는 CPU 또는 GPU 또는 SE(shader engine), CU(compute unit) 또는 CPU 또는 GPU의 SIMD(single-instruction-multiple-data)일 수 있다. 메모리(104)는 프로세서(102)와 동일한 다이 상에 위치될 수 있거나, 프로세서(102)와는 별개로 위치될 수 있다. 메모리(104)는 휘발성 또는 비휘발성 메모리, 예를 들어 랜덤 액세스 메모리(RAM), 동적 RAM 또는 캐시를 포함할 수 있다. 각각의 프로세서 코어는 로컬 메모리, 예컨대 로컬 L1 캐시 메모리를 가질 수 있고, 및/또는 하나 이상의 다른 코어들을 갖는 메모리, 예컨대 공유된 L2 캐시 메모리를 공유할 수 있다.

스토리지(106)는 고정형 또는 제거가능 스토리지, 예를 들어 하드 디스크 드라이브, 솔리드 스테이트 드라이브, 광 디스크 또는 플래시 드라이브를 포함할 수 있다. 입력 디바이스(108)는 키보드, 키패드, 터치스크린, 터치패드, 검출기, 마이크로폰, 가속도계, 자이로스코프, 생체 측정 스캐너 또는 네트워크 접속(예를 들어, 무선 IEEE802 신호의 송신 및/또는 수신을 위한 무선 로컬 영역 네트워크 카드)을 포함할 수 있다. 출력 디바이스(110)는 디스플레이, 스피커, 프린터, 햅틱 피드백 디바이스, 하나 이상의 광, 안테나, 네트워크 접속(예를 들어 무선 IEEE802 신호의 송신 및/또는 수신을 위한 무선 로컬 영역 네트워크 카드)을 포함할 수 있다.

입력 드라이버(112)는 프로세서(102) 및 입력 디바이스(108)와 통신하며, 프로세서(102)가 입력 디바이스(108)로부터 입력을 수신할 수 있게 한다. 출력 드라이버(114)는 프로세서(102) 및 출력 디바이스(110)와 통신하고, 프로세서(102)가 출력 디바이스(110)에 출력을 전송할 수 있게 한다. 입력 드라이버(112) 및 출력 드라이버(114)는 선택적인 컴포넌트이며, 입력 드라이버(112) 및 출력 드라이버(114)가 존재하지 않는다면 디바이스(100)는 동일 방식으로 동작할 것이라는 것에 유의한다.

멀티-코어 프로세서에서, 캐시를 공유하는 두 개 의 (또는 그 이상의) 코어들이 상당한 양의 다른 정보를 메모리로부터 액세스하는 쓰레드 (또는 쓰레드 그룹, 웨이브 또는 다른 유형의 지시 그룹들)를 병렬로 (예를 들어, 동시에 또는 중첩 시간 기간 동안 동시에) 실행하는 경우 비효율적인 경우가 발생할 수 있다. 쓰레드들은 예를 들어, 쓰레드들간에 불충분한 참조의 지역성(locality of reference) 때문에 상이한 정보를 액세스할 수 있다. 이 콘텍스트(context)에서 참조의 지역성은 각각의 쓰레드들에 의해 참조되는 동일한 정보를 지칭할 수 있다.

이러한 상황에서, 쓰레드 중 하나의 실행으로 인해 공유 캐시로 로딩된 데이터는 다른 쓰레드의 실행으로 인해 공유 캐시로 로딩된 데이터에 의해 제거 될 수 있다. 이는 각 쓰레드가 필요로 하는 메모리 액세스의 수 및/또는 각 쓰레드가 다른 쓰레드에 의해 액세스 된 것과 다른 정보를 액세스하는지 여부에 의존할 수 있다. 이러한 축출(eviction)은 쓰레드의 실행을 통해 계속 왔다 갔다할 수 있고, 메모리 액세스 레이턴시의 실질적이고 바람직하지 않은 증가를 초래할 수 있다.

따라서, 가능하면 동일한 정보를 더 많이 사용하거나 및/또는 별개의 코어에서 병렬로 더 큰 메모리 재사용을 나타내는 해당 쓰레드를 우선적으로 실행하는 것이 멀티코어 프로세서를 구조화하는데 바람직하다. 이 콘텍스트에서 메모리 재사용은 다른 쓰레드에 의해 또한 사용되는 하나의 쓰레드에 의해 메모리로부터 검색된 정보를 지칭 할 수 있다. 이 쓰레드 중 하나가 하나의 코어에서 실행되고 다른 쓰레드가 다른 코어에서 실행되는 시나리오에서, 두 코어가 캐시를 공유하는 경우 둘 모두의 쓰레드에 의한 액세스를 위해 정보가 공유 캐시에 저장 될 수 있다. 따라서 주어진 시간 동안 실행되도록 스케줄된 쓰레드의 경우, 다른 쓰레드를 병렬로 실행하기 보다는 병렬로 더 많은 공유된 참조의 지역성을 보이는 해당 쓰레드를 실행하는 것이 바람직할 수 있다. 이것은 공유 데이터 캐시에서 축출 횟수를 줄이고 메모리 액세스 레이턴시를 줄이는 이점을 가질 수 있다. 예를 들어, 다수의 픽셀이 동일한 텍스처 데이터를 사용하고 다수의 프로세싱 유닛을 갖는 GPU에 의해 프로세스되는 경우에, 공유된 참조의 지역성을 이용하기 위해서 직렬 대신에 병렬로 텍스쳐 데이터를 공유하는 해당 픽섹들을 프로세스하는 것이 더 효율적일 수 있다.

도 2는 멀티코어 프로세서의 코어들의 개수 (Y) 상에서 실행을 위한 개수 (X)의 쓰레드를 스케줄링하기 위한 예시적인 방법 (200)을 도시하는 플로우 차트이묘, Y 코어들은 적어도 하나의 메모리, L2 캐시를 공유한다. 방법 (200)은 예를 들어, 디바이스 (100)의 일부 또는 전부를 이용하여 구현될 수 있다. 예를 들어, 프로세서는 도 1 에 도시된 프로세서 (102)에 대응할 수 있다.

단계 (210)에서, 예를 들어, 메모리 재사용 량 또는 이들 간에 또는 이들 사이의 "상관 관계(correlation)"를 결정하기 위해서 멀티코어 프로세서의 분석 모듈에 의해 쓰레드가 분석된다. 예를 들어, X = 4 및 Y = 2 인 경우, 어떤 쓰레드 쌍이 이들간에 가장 큰 상관 관계를 갖는지를 결정하기 위해 X 쓰레드들이 분석 될 수 있다. 상이한 예제에서, X = 8 및 Y = 4 인 경우, 네개의 쓰레드들 중 어떤 그룹들이 이들간에 가장 큰 상관 관계를 갖는지를 결정하기 위해 X 쓰레드들이 분석 될 수 있다. 이들 그룹들의 쓰레드들의 상관관계들이 예를 들어, 분석 모듈에 의해 순위 매김될 수 있다. 분석은 본 출원에 추가로 설명되는 해당 예제들을 포함하는 임의의 적절한 방식으로 수행될 수 있다.

단계 (220)에서, 예를 들어, 멀티코어 프로세서의 스케줄링 모듈에 의해 쓰레드가 스케줄링되어 가장 큰 상관 관계를 갖는 것으로서 단계 (210)에서 식별된 Y 쓰레드들이 Y 코어상에서 병렬로 실행된다. X = 2Y 인 경우, X 쓰레드의 나머지 쓰레드는 Y 코어들에서 병렬로 실행되도록 스케줄링될 수 있다. X>2Y 인 경우, X 쓰레드의 나머지 쓰레드는 그것들 간에 가장 큰 상관관계에 기초하여 병렬로 실행되도록 스케줄링될 수 있다.

Y 쓰레드들의 상이한 세트들이 상관관계의 균형에 기초하여 병렬 실행을 위해 스케줄링되도록 쓰레드들이 대안으로 스케줄링 될 수 있다는 것에 유의한다. 예를 들어, 병렬로 가장 큰 상관 관계를 갖는 것으로서 단계 (210)에서 식별된 Y 쓰레드를 실행하는 것이 잔여 쓰레드를 상이한 쓰레드 선택보다 더 열악한 상관 관계로 병렬로 실행하려는 상황에서, Y 쓰레드의 두 세트에 걸친 상관 관계가 최대화되도록 쓰레드의 Y 세트 각각이 선택 될 수 있다.

단계 (230)에서, X 쓰레드들은 단계 (220)에서 스케줄링된 Y 코어들상에서 실행된다. X 쓰레드는 가장 좋은 사용 가능한 상관 관계를 갖는 서브세트들에 Y 코어에서 실행되기 때문에, 공유된 메모리 (예를 들어, 공유된 L2 캐시)로부터 제거가 최소화되어 메모리 액세스 레이턴시를 최소화하고 성능을 향상시킬 수 있다.

그러나, 방법 (200)은 Y 코어들상에서 이들 쓰레드들의 실행 이전에 상관 관계를 위한 X 쓰레드들의 분석을 요구할 수 있다는 것에 유의한다. 예를 들어, X 쓰레드가 상관 관계 기반 멀티 코어 스케줄링을 이용하도록 프로그래밍되지 않은 경우 이것은 가능하지 않을 수 있다. 따라서, 상관관계들을 동적으로 결정하도록 하는 것이 유익할 수 있다.

도 3은 멀티코어 프로세서의 코어들 (Y) 상에서 실행을 위한 (X)의 쓰레드를 스케줄링하기 위한 예시적인 다른 방법 (300)을 도시하는 플로우 차트이며, Y 코어들은 적어도 하나의 메모리, L2 캐시를 공유한다. 방법 (300)에서, 상관관계가 동적으로 결정된다. 방법 (300)은 예를 들어, 디바이스 (100)의 일부 또는 전부를 이용하여 구현될 수 있다. 예를 들어, 프로세서는 도 1 에 도시된 프로세서 (102)에 대응할 수 있다.

단계 (310)에서, X 쓰레드들은 Y 코어들상에서 실행을 위해 스케줄링된다. 이 단계에서, X 쓰레드들 간에 상관관계들은 알려지지 않는다. 따라서, 디폴트 스케줄링 패턴, 예컨대 "라운드-로빈(round-robin)" 패턴이 처음에 사용된다. 따라서 X=4 및 쓰레드들이 T0, T1, T2, 및 T3이고, Y=2 및 코어들이 CU0 및 CU1인 예제에서, 라운드-로빈 방식에 스케줄링은 T0 = C0, T1 = C1, T2 = C0, T3 = C1일 것이다.

단계 (320)에서, X 쓰레드들은 그것들의 현재 스케줄링에 따라 Y 코어들상에서 실행된다. 따라서 만약 스케줄링이 단계 (310)의 라운드-로빈 패턴을 따르면, 쓰레드들 T0 및 T1은 개별적으로 C0 및 C1상에서 병렬로 실행할 것이고, 뒤이어 개별적으로 C0 및 C1상에서 T2 및 T3를 실행할 것이다.

단계 (330)에서, X 쓰레드들은 실행에 기초하여 상관관계가 분석된다. 단계 (330)의 분석은 실제로 실행 중에 단계 (320)와 결합하여 발생할 수 있거나 또는 실행 후 단계 (320) 동안 수집된 데이터에 대해 수행 될 수 있다. 상관관계들은 임의의 적절한 기술을 이용하여 결정될 수 있고, 예제들이 본 출원에 추가로 논의된다.

단계 (340)에서, X 쓰레드들은 단계(330)에서 결정된 상관관계들에 기초하여 Y 코어들상에서 실행을 위해 스케줄링된다. 이 단계에서, X 쓰레드들 간에 상관관계들은 알려진다. 따라서, 디폴트 스케줄링 패턴이 사용되지 않고; 오히려, 쓰레드들은 알려진 상관관계들에 따라 스케줄링된다. X=4 및 쓰레드들이 T0, T1, T2, 및 T3이고, Y=2 및 코어들이 CU0 및 CU1인 예제에서, 단계 (330)에서 다양한 가능한 쓰레드 쌍들 중 가장 높은 상관관계 값이 T0와 T2 사이에 있는 것으로 결정될 수 있다. 그런 다음 상관관계에 기초한 스케줄링은 T0 = C0, T2 = C1, T1 = C0, T3 = C1일 것이다. 이 스케줄링은 단계 (330)의 분석에 의해 생성 된 상관관계 데이터에 기초하기 때문에, 그러한 스케줄링은 데이터 - 드라이브 스케줄링(data-driven scheduling)이라 할 수 있고, 그러한 스케줄링을 구현하기위한 디바이스 또는 디바이스들의 조합은 데이터 - 드라이브 스케줄러로 지칭될 수 있다.

데이터-드라이브 스케줄링은 대안으로 모든 쓰레드들의 실행에 걸쳐 최대화되는 상관관계에 기반될 수 있다. 예를 들어, T1과 T3 사이의 상관 관계가 특히 낮은 경우, 스케줄 T0 = C0, T2 = C1, T1 = C0, T3 = C1에서 병렬로 이들 쓰레드들의 실행은 메모리 액세스 레이턴시로 귀결될 수 있고 이는 병렬로 T0 및 T2를 실행함으로써 제공되는 메모리 액세스 레이턴시에서 감소를 상쇄하거나 무효화 할 수 있다. 이를 해결하기 위해, 다양한 가능한 쓰레드 쌍 중 두 번째로 높은 상관관계 값 (또는 세 번째 또는 네 번째 등)이 데이터-드라이브 스케줄러에 의해 고려 될 수 있다. 일 예에서, 이 두번째로 높은 상관관계는 T0와 T3 사이일 수 있다. 스케줄링 실행을 위해 이 쌍을 이용하는 것은 T0 = C0, T3 = C1, T1 = C0, T2 = C1를 낳을 것이다. T1과 T3 사이의 열악한 상관 관계가 T0와 T2 사이의 가장 높은 상관관계를 상쇄하는 예제에서, 이 새로운 스케줄은 모든 X 쓰레드의 실행에 걸친 메모리 액세스 레이턴시를 최소화 할 수 있다. 이 스케줄 자체는 모든 쓰레드에 걸쳐 가장 높은 평균 상관관계를 제공하지 않을 수 있다는 것에 유의하고, 모든 쓰레드에 대해 최상의 평균 상관관계 및 / 또는 최소화된 메모리 액세스 레이턴시를 결정하기 위해 모든 가능한 조합이 분석 될 수 있다는 것에 유의한다. 이러한 방식으로 모든 X 쓰레드들 간의 상관관계를 최대화하도록 구성된 데이터-드라이브 스케줄러는 그러나 구현하기위해 추가적인 회로 및 / 또는 추가적인 지연을 필요로 할 수 있다.

단계 (350)에서, X 쓰레드들은 스케줄에 따라 Y 코어들상에서 실행된다. 따라서 만약 스케줄링이 T0 = C0, T2 = C1, T1= C0, T3 = C1을 따르면, 쓰레드들 T0 및 T2는 개별적으로 C0 및 C1상에서 병렬로 실행할 것이고, 뒤이어 개별적으로 C0 및 C1상에서 T1 및 T3를 실행할 것이다.

흐름은 실행 쓰레드들의 추가 분석을 위해 단계 (330)으로 ; 예를 들어, 실행중인 쓰레드의 메모리 액세스 사이로 되돌아 갈 수 있다. 이것은 실행 스케줄링에 대한 추가 동적 제어를 허용할 수 있다. 예를 들어, 일부 구현예들에서, 스케줄링은 현재 실행중인 쓰레드를 콘텍스트-저장하고, 업데이트된 스케줄에 기초하여 상이한 코어들에 쓰레드를 스케줄링 한 다음, 콘텍스트를 복원(restore)함으로써 쓰레드 (예를 들어, 상관관계 값을 변경함으로써 표시되는 경우)의 실행 중에 조정 될 수 있다.

도 4는 데이터 드라이브 스케줄링을 구현하는 예제 시스템(400)을 예시하는 블럭 다이어그램이다. 일 예제 구현예에서, 시스템 (400)은 프로세서 (102)의 특징부일 수 있다. 시스템 (400)은 프로세싱 유닛들 (410), 프로세싱 유닛들 (410)에 의해 공유되는 캐시 메모리 (420), 데이터 드라이브 스케줄러 (430), 및 쓰레드 그룹 디스패처(dispatcher) (440)를 포함한다. 시스템 (400)의 예제에서, 프로세싱 유닛들 (410)은 두개의 코어들, 이 경우에서, 셰이더 엔진(shader engine)들 SE0 및 SE1을 포함한다. 데이터 드라이브 스케줄러 (430)는 상관관계 어레이 (450) 및 결정 유닛 (460)을 포함하고, 쓰레드 그룹 레벨에 기하여 스케줄들을 결정한다. 셰이더 엔진에서 병렬로 실행되도록 그룹화된 쓰레드 그룹은 이 콘텍스트내 쓰레드 그룹으로 지칭될 수 있다.

셰이더 엔진들 SE0 및 SE1은 예를 들어 그래픽스 프로세서내 프로세싱 유닛들의 클러스터를 포함할 수 있다. 이러한 클러스터는 다양한 아키텍처에서 "셰이더 엔진(shader engine)"이외의 용어로 T0가 지칭될 수 있다.

이 예제에서 캐시 메모리 (420)는 L2 캐시이지만; 그러나, 캐시 메모리 (420)는 셰이더 엔진 SE0 및 SE1에 의해 공유되는 캐시 메모리 또는 다른 공유 메모리의 임의의 적절한 레벨 일 수 있다는 것에 유의한다. 캐시 메모리 (420)는 셰이더 엔진들 SE0 및 SE1에 의해 공유된다.

데이터 드라이브 스케줄러 (430)는 프로세싱 유닛들 (410)상에서의 실행을 위해 쓰레드 그룹들을 스케줄링한다. 상관관계 어레이 (450)는 쓰레드 그룹들간에 또는 그것들중에 상관관계를 계산한다. 결정 유닛 (460)은 특정 시간에 프로세싱 유닛들 (410) 중 특정 프로세싱 유닛에 어느 쓰레드 그룹을 디스패치할 것인지를 결정한다.

상관관계 데이터가 스케줄링에 이용 할 수 있기 전에, 데이터 드라이브 스케줄러 (430)는 디폴트 (예를 들어, 비-데이터-드라이브) 스케줄링 패턴을 사용하여 셰이더 엔진 SE0 및 SE1상에서 실행을 위해 쓰레드 그룹을 스케줄링한다. 이 디폴트 패턴은 라운드-로빈 패턴일 수 있다. 스케줄링은 4 개의 쓰레드 그룹 단위(granularity)로 수행된다. 따라서 첫번째 네개의 쓰레드 그룹들은 TG0TG1, TG2, 및 TG3로 지칭되는 경우, 첫번째 라운드-로빈 방식으로 4 쓰레드 그룹들에 대한 스케줄링은 TG0 = SE0, TG1 = SE1, TG2 = SE0, TG3 = SE1일 것이다. 그런 다음 쓰레드 그룹 디스패처 (440)는 디폴트 스케줄에 따라 SE0 및 SE1상에서 실행을 위해 쓰레드 그룹들을 디스패치한다.

SE0 및/또는 SE1로부터 캐시 (420) 로의 새로운 메모리 요청시에, 캐시 (420)는 메모리 요청에 대응하는 인덱스 및 캐시 태그를 상관관계 어레이 (450)로 포워딩할 수 있다. 인덱스는 요청 쓰레드 그룹의 아이덴티티, 예를 들어 TGID에 대응할 수 있고, 태그는 요청된 메모리 어드레스, 데이터 마스크(data mask) 및 / 또는 보조 정보를 포함 할 수 있다. 따라서, 캐시 (420)는 현재 실행중인 쓰레드 그룹이 요구하는 메모리 액세스에 관한 정보를 상관관계 어레이 (450)에 제공한다. 상관관계 어레이 (450)가 물리적 어드레스 공간에서 구현되는 경우, 예를 들어, 캐시라인 단위로 액세스되는 물리적 메모리의 어드레스는 적절한 상관관계 정보일 수 있다. 만약 상관관계 어레이 (450)가 가상의 어드레스 공간에 구현되면, 추가 정보, 예컨대 프로세스 ID의 일부 형태가, 요구될 수 있다.

상관관계 어레이 (450)는 인덱스 및 태그 정보를 저장할 수 있고, 이하에서 추가로 논의되는 쓰레드 그룹들에 대한 상관관계 값들을 계산하는데 이 정보를 사용할 수 있다. 상관관계 어레이 (450)는 이들 상관관계 값들을 결정 유닛 (460)에 보고할 수 있다. 결정 유닛 (460)은 SE0 및 SE1상에서 쓰레드 그룹들 TG0, TG1, TG2, TG3의 실행을 위해 데이터-드라이브 스케줄링을 결정하는데 보고된 상관관계 값들을 사용할 수 있다. 그런 다음 쓰레드 그룹 디스패처 (440)는 데이터-드라이브 스케줄에 따라 SE0 및 SE1상에서 실행을 위해 쓰레드 그룹들을 디스패치할 수 있다.

도 5 는 쓰레드 그룹들 TG0, TG1, TG2, 및 TG3의 실행 동안에 어떤 지점에서 상관관계 어레이 (450)의 예제 상태를 예시하는 표 (500)이다. 예제 시스템 (400)은 4 쓰레드 그룹들 단위로 스케줄링을 수행한다. 따라서, 표 (500)은 4 키들 (510, 510', 510", 510"')을 포함하고, 이의 각각은 쓰레드 그룹들 TG0, TG1, TG2, 및 TG3 중 하나에 대응한다.

각각의 키 (510, 510', 510", 510"')는 대응하는 태그 리스트 (미도시) 및 기여(contributing) 상관관계 값들 (520, 520', 520", 520"')의 세트를 포함한다. 기여 상관관계 값들 (520, 520', 520", 520"')의 세트는 쓰레드 그룹들 TG0, TG1, TG2, 및 TG3의 각각의 쌍의 상관관계를 반영한다. 예를 들어, 키 (510)는 TG0에 대한 기여 상관관계 값들 (520)의 세트를 저장한다. 기여 상관관계 값 세트 (520)는, TG0와 TG1간의 상관관계에 대응하는 기여 상관관계 값 C01과, TG0와 TG2간의 상관관계에 대응하는 기여 상관관계 값 C02와, TG0와 TG3간의 상관관계에 대응하는 기여 상관관계 값 C03을 저장한다. 각각의 다른 키들 (510', 510", 510"')은 도 5에 반영된 기여 상관관계 값들 (520', 510", 520"')의 유사한 세트를 저장한다. 상관관계 정보가 상관관계 어레이 (450)에 이용 가능할 수 있기 전에 (예를 들어, 방법 (300)의 단계 (310)에 유사한), 태그 리스트는 비어있을 수 있고 기여 상관관계 값들은 제로일 수 있다.

쓰레드 그룹의 실행동안에 SE0 또는 SE1에 의한 새로운 메모리 요청에 기해, 상관관계 어레이 (450)는 캐시로부터 메모리 요청의 태그 정보 및 대응하는 인덱스를 수신한다. 만약 인덱스 및 태그 정보가 표 (500)에 엔트리에 일치하면, 대응하는 기여 상관관계 값은 증분되거나, 증가되거나, 또는 그렇지 않으면, 증가된 상관관계를 반영하도록 변경될 수 있다. 예를 들어, 상관관계 어레이 (450)가 인덱스 TG1 및 태그 태그3를 수신하고, 상관관계 어레이 (450)가 TG0의 태그리스트가 또한 태그 3을 포함한다는 것을 반영하면, 그러면 TG0와 TG1 사이의 상관 관계를 반영하는 기여 상관관계 값 C01이 증가 될 수있다(예를 들어, 일 만큼 증분된다).

만약 수신된 인덱스가 표 (500)내 키에 일치하지만, 그러나 수신된 태그가 태그 리스트내 임의의 태그들에 일치하지 않으면, 수신된 태그는 해당 키를 위한 태그 리스트로 삽입될 수 있다. 만약 수신된 인덱스가 표 (500)내 키에 일치하지 않지만, 그러나 수신된 태그가 태그 리스트내 임의의 태그들에 일치하지 않으면 ...

TG0, TG1, TG2, 및 TG3가 SE0 및 SE1상에서 실행 끝난 후에, TG0와 TG1간의 상관관계를 반영하는 상관관계 값 c01를 결정하기 위해서 기여 상관관계 값들 C01 및 C10는 합산될 수 있다(또는 다른 식으로, 결합될 수 있다). 다른 일치하는 기여 상관관계 값들이 또한 다른 TG 쌍들을 위한 상관관계 값들을 찾기 위해서 유사하게 합산될 수 있다. 예를 들어, c02는 기여 상관관계 값들 C02 및 C20을 더함으로써 계산된 TG0 및 TG2를 위한 상관관계 값일 수 있고, 등등일 수 있다. 이들 상관관계 값들 c01, c02, c03, c12, c13, c23은 결정 유닛 (460)으로 보고될 수 있다.

TG0, TG1, TG2 및 TG3이 SE0 및 SE1상에서 실행을 완료 할 때까지 대기하는 것이 아니라, 소정의 간격, 예를 들어 1,000 프로세서 클럭 사이클 후에 기여하는 상관관계 값들이 합산 및 / 또는 보고 될 수 있음을 유의해야 한다. 따라서, 상관관계 값들은 TG0, TG1, TG2, 및 TG3의 몇몇의 실행들 후에 또는 실행 완료전에 계산될 수 있다. 이것은 더 높은 분해능(resolution) 데이터에 기초한 동적 스케줄링 및/또는 스케줄링을 허용할 수 있다.

도 4로 돌아가서, 결정 유닛 (460)은 보고된 상관관계 값들 c01, c02, c03...에 기초하여 다음 4 개의 TG들 TG0, TG1, TG2, TG3의 발행 순서 (즉, 데이터-드라이브 스케줄)을 결정할 수 있다. 표 1은 이 결정을 수행하기 위해 결정 유닛 (460)을 위한 부분 알고리즘의 예제를 반영하는 의사 코드(pseudo code)를 도시한다. 쓰레드 그룹 디스패처 (440)는 결정 유닛 (460)로부터 데이터-드라이브 스케줄을 수신하고 데이터-드라이브 스케줄에 따라 SE0 및 SE1로 쓰레드 그룹들을 디스패치한다. 일부 구현예들에서, 쓰레드 그룹 디스패처 (440)는 스케줄이 변화되었다는 결정에 기하여 그것의 스케줄을 업데이트만 할 수 있다. 일부 구현예들에서, 스케줄이 변경된 상태에 기하여, 현재 SE0 및 SE1에서 실행중인 쓰레드 그룹이 선점될 수 있고, 콘텍스트가 저장 될 수 있으며, 업데이트된 스케줄이 쓰레드 그룹에 적용될 수 있고 (즉, 쓰레드 그룹이 다른 셰이더 엔진 및/또는 실행 시간에 재할당 될 수 있음), 콘텍스트는 복원 될 수 있고, 업데이트 된 스케줄 하에서 실행이 재개 될 수 있다.

표 1

If(max{c01, c02, c03, ...} = = c0l)

{

group the next TG0 and TG2 to SE0;

group the next TG1 and TG3 to SE1;

}

else if(max{c01, c02, c03, ...} = = c02)

{

group the next TG0 and TG1 to SE0;

group the next TG2 and TG3 t0SE1;

}

else if(max{c01, c02, c03, ...} = = c03)

{

group the next TG0 and TG1 to SE0;

group the next TG3 and TG2 t0SE1;

}

...

다른 예제 시스템들에서, 스케줄링은 쓰레드 그룹이 아닌 베이시스(basis)에 기초할 수 있다. 예를 들어, 웨이브 레벨(wave level)에 근거한 스케줄링은 적절한 시스템 아키텍처에 의존할 수 있다.

도 6는 데이터 드라이브 스케줄링을 구현하는 예제 시스템(600)을 예시하는 블럭 다이어그램이다. 일 예제 구현예에서, 시스템 (600)은 프로세서 (102)의 특징부일 수 있다. 시스템 (600)은 프로세싱 유닛들 (610), 프로세싱 유닛들 (610)에 의해 공유되는 캐시 메모리 (620), 데이터 드라이브 스케줄러 (630), 및 웨이브 디스패처(wave dispatcher) (640)를 포함한다. 시스템 (600)의 예제에서, 프로세싱 유닛들 (610)은 두개의 코어들, 이 경우에서, 컴퓨트 유닛들 CU0 및 CU1을 포함한다. 데이터 드라이브 스케줄러 (630)는 상관관계 어레이 (650) 및 결정 유닛 (660)을 포함하고, 웨이브 레벨에 기하여 스케줄들을 결정한다.

컴퓨트 유닛들 CU0 및 CU1 각각은 SIMD(single-instruction multiple data) 코어를 포함할 수 있다. SIMD 코어상에서 병렬로 실행되는 쓰레드 그룹은 이 콘텍스트내 웨이브로 지칭될 수 있다.

이 예제에서 캐시 메모리 (620)는 L2 캐시이지만; 그러나, 캐시 메모리 (620)는 컴퓨트 유닛(compute unit)들 CU0 및 CU1에 의해 공유되는 캐시 메모리 또는 다른 공유 메모리의 임의의 적절한 레벨 일 수 있다는 것에 유의한다. 캐시 메모리 (620)는 컴퓨트 유닛들 CU0 및 CU1에 의해 공유된다.

데이터 드라이브 스케줄러 (630)는 프로세싱 유닛들 (610)상에서의 실행을 위해 웨이브들을 스케줄링한다. 상관관계 어레이 (650)는 웨이브들간에 또는 그것들중에 상관관계를 계산한다. 결정 유닛 (660)은 특정 시간에 프로세싱 유닛들 (610) 중 특정 프로세싱 유닛에 어느 웨이브를 디스패치할 것인지를 결정한다.

상관관계 데이터가 스케줄링에 이용 할 수 있기 전에, 데이터 드라이브 스케줄러 (630)는 디폴트 (예를 들어, 비-데이터-드라이브) 스케줄링 패턴을 사용하여 컴퓨트 유닛들 CU0 및 CU1상에서 실행을 위해 쓰레드 그룹을 스케줄링한다. 이 디폴트 패턴은 라운드-로빈 패턴일 수 있다. 예제 시스템(600)에서, 스케줄링은 4 개의 웨이브들의 단위(granularity)로 수행된다. 따라서 첫번째 네개의 웨이브들이 웨이브(wave) 0, 웨이브 1, 웨이브2, 및 웨이브3를 나타내는 경우에, 라운드-로빈 방식으로 첫번째 4 웨이브들에 대한 스케줄링은 웨이브0 = CU0, 웨이브1 = CU1, 웨이브2 = CU0, 웨이브3 = CU1일 것이다. 그런 다음 웨이브 디스패처 (640)는 디폴트 스케줄에 따라 CU0 및 CU1상에서 실행을 위해 웨이브들을 디스패치한다.

CU0 및/또는 CU1로부터 캐시 (620) 로의 새로운 메모리 요청시에, 캐시 (620)는 메모리 요청에 대응하는 인덱스 및 캐시 태그를 상관관계 어레이 (650)로 포워딩할 수 있다. 인덱스는 요청 웨이브의 아이덴티티, 예를 들어 웨이브 ID에 대응할 수 있고, 태그는 요청된 메모리 어드레스, 데이터 마스크 및 / 또는 보조 정보를 포함 할 수 있다. 따라서, 캐시 (620)는 현재 실행중인 웨이브가 요구하는 메모리 액세스에 관한 정보를 상관관계 어레이 (650)에 제공한다. 태그는 물리적 어드레스, 또는 가상 메모리 식별자로 조합한 가상 어드레스일 수 있다. 태그는 데이터 캐시에서 사용되는 태그에 유사할 수 있다.

상관관계 어레이 (650)는 인덱스 및 태그 정보를 저장할 수 있고, 이하에서 추가로 논의되는 웨이브들에 대한 상관관계 값들을 계산하는데 이 정보를 사용할 수 있다. 상관관계 어레이 (650)는 이들 상관관계 값들을 결정 유닛 (660)에 보고할 수 있다. 결정 유닛 (660)은 CU0 및 CU1상에서 웨이브들 웨이브0, 웨이브1, 웨이브 2, 웨이브3의 실행을 위해 데이터-드라이브 스케줄링을 결정하는데 보고된 상관관계 값들을 사용할 수 있다. 그런 다음 웨이브 디스패처 (640)는 데이터-드라이브 스케줄에 따라 CU0 및 CU1상에서 실행을 위해 웨이브들을 디스패치할 수 있다.

도 7은 웨이브들 웨이브0, 웨이브1, 웨이브2, 및 웨이브3의 실행 동안에 어떤 지점에서 상관관계 어레이 (650)의 예제 상태를 예시하는 표 (700)이다. 예제 시스템(600)은 4 개의 웨이브들 단위로 스케줄링을 수행한다. 따라서, 표 (700)은 4 키들 (710, 710', 710", 710"')을 포함하고, 이의 각각은 웨이브들 웨이브0, 웨이브1, 웨이브2, 및 웨이브3 중 하나에 대응한다.

각각의 키 (710, 710', 710", 710"')는 대응하는 태그 리스트 (미도시) 및 기여 상관관계 값들 (720, 720', 720", 720"')의 세트를 포함한다. 기여 상관관계 값들 (720, 720', 720", 720"')의 세트는 웨이브들 웨이브0, 웨이브1, 웨이브2, 및 웨이브3의 각각의 쌍의 상관관계를 반영한다. 예를 들어, 키 (710)는 웨이브0에 대한 기여 상관관계 값들 (720)의 세트를 저장한다. 기여 상관관계 값 세트 (720)는, 웨이브0와 웨이브1간의 상관관계에 대응하는 기여 상관 값 C01과, 웨이브0와 웨이브2간의 상관관계에 대응하는 기여 상관 값 C02와, 웨이브0와 웨이브3간의 상관관계에 대응하는 기여 상관 값 C03을 저장한다. 각각의 다른 키들 (710', 710", 710"')은 도 7에 반영된 기여 상관관계 값들 (720', 710", 720"')의 유사한 세트를 저장한다. 상관관계 정보가 상관관계 어레이 (750)에 이용 가능할 수 있기 전에 (예를 들어, 방법 (300)의 단계 (310)에 유사한), 태그 리스트는 비어있을 수 있고 기여 상관관계 값들은 제로일 수 있다.

웨이브의 실행동안에 CU0 또는 CU1에 의한 새로운 메모리 요청에 기해, 상관관계 어레이 (650)는 캐시로부터 메모리 요청의 태그 정보 및 대응하는 인덱스를 수신한다. 만약 인덱스 및 태그 정보가 표 (700)에 엔트리에 일치하면, 대응하는 기여 상관관계 값은 증분되거나, 증가되거나, 또는 그렇지 않으면, 증가된 상관관계를 반영하도록 변경될 수 있다. 예를 들어, 상관관계 어레이 (650)가 인덱스 웨이브1 및 태그 태그3를 수신하고, 상관관계 어레이 (650)가 웨이브0의 태그리스트가 또한 태그 3을 포함한다는 것을 반영하면, 그러면 웨이브0와 웨이브1 사이의 상관 관계를 반영하는 기여 상관관계 값 C01이 증가 될 수 있다(예를 들어, 일 만큼 증분된다).

만약 수신된 인덱스가 표 (700)내 키에 일치하지만, 그러나 수신된 태그가 태그 리스트내 임의의 태그들에 일치하지 않으면, 수신된 태그는 해당 키를 위한 태그 리스트로 삽입될 수 있다. 만약 수신된 인덱스가 표 (700)내 키에 일치하지 않으면, 그러나 수신된 태그가 태그 리스트내 임의의 태그들에 일치하지 않으면 새로운 키가 해당 인덱스에 대해 더해질 수 있고 만약 태그가 일치하여 다른 키들에 대한 상관관계들은 조정될 것이다.

웨이브0, 웨이브1, 웨이브2, 및 웨이브3가 CU0 및 CU1상에서 실행 끝난 후에, 웨이브0와 웨이브1간의 상관관계를 반영하는 상관관계 값 C01를 결정하기 위해서 기여 상관관계 값들 C01 및 C10는 가산될 수 있다(또는 다른식으로, 결합될 수 있다). 다른 일치하는 기여 상관관계 값들이 또한 다른 웨이브 쌍들을 위한 상관관계 값들을 찾기 위해서 유사하게 더해질 수 있다. 예를 들어, c02는 기여 상관관계 값들 C02 및 C20을 가산함으로써 계산된 웨이브0 및 웨이브2를 위한 상관관계 값일 수 있고, 등등일 수 있다. 이들 상관관계 값들 c01, c02, c03, c12, c13, c23은 결정 유닛 (660)으로 보고될 수 있다.

웨이브0, 웨이브1, 웨이브2 및 웨이브3이 CU0 및 CU1상에서 실행을 완료 할 때까지 대기하는 것이 아니라, 소정의 간격, 예를 들어 1,000 프로세서 클럭 사이클 후에 기여하는 상관관계 값들이 합산 및 / 또는 보고 될 수 있음을 유의해야 한다. 따라서, 상관관계 값들은 웨이브0, 웨이브1, 웨이브2, 및 웨이브3의 몇몇의 실행들 후에 또는 실행 완료전에 계산될 수 있다. 이것은 더 높은 분해능(resolution) 데이터에 기초한 동적 스케줄링 및/또는 스케줄링을 허용할 수 있다.

도 6으로 돌아가서, 결정 유닛 (660)은 보고된 상관관계 값들 c01, c02, c03...에 기초하여 다음정 유닛 (660)4 개의 웨이브들 웨이브0, 웨이브1, 웨이브2, 웨이브3의 발행 순서 (즉, 데이터-드라이브 스케줄)을 결정할 수 있다. 표 2는 이 결정을 수행하기 위해 결정 유닛 (660)을 위한 부분 알고리즘의 예제를 반영하는 의사 코드(pseudo code)를 도시한다. 웨이브 디스패처 (640)는 결로부터 데이터-드라이브 스케줄을 수신하고 데이터-드라이브 스케줄에 따라 CU0 및 CU1로 웨이브들을 디스패치한다. 일부 구현예들에서, 웨이브 디스패처 (640)는 스케줄이 변화되었다는 결정에 기하여 그것의 스케줄을 업데이트만 할 수 있다. 일부 구현예들에서, 스케줄이 변경된 상태에 기하여, 현재 CU0 및 CU1에서 실행중인 웨이브들이 선점될 수 있고, 콘텍스트가 저장 될 수 있으며, 업데이트된 스케줄이 웨이브들에 적용될 수 있고 (즉, 웨이브들이 다른 컴퓨트 유닛들 및/또는 실행 시간에 재할당 될 수 있음), 콘텍스트는 복원 될 수 있고, 업데이트 된 스케줄 하에서 실행이 재개 될 수 있다.

표 2

If(max{c01, c02, c03, ...} = = c0l)

{

group the next wave0 and wave2 to CU0;

group the next wave l and wave3 to CU1;

}

else if(max{c01, c02, c03, ...} = = c02)

{

group the next wave0 and wave1 to CU0;

group the next wave2 and wave3 to CU1;

}

else if(max{c01, c02, c03, ...} == c03)

{

group the next wave0 and wavel to CU0;

group the next wave3 and wave2 to CU1;

}

...

다른 예제 시스템들에서, 스케줄링은 쓰레드 그룹 또는 웨이브가 아닌 베이시스에 기초할 수 있다. 예를 들어, 쓰레드 레벨에 근거한 스케줄링은 적절한 시스템 아키텍처에 의존할 수 있다. 본 출원에서 설명된 기술들은 본 발명에서 벗어나지 않고서 쓰레드, 쓰레드 그룹, 또는 웨이브외에 추상적 개념의 다른 레벨들에서 적용될 수 있다는 것에 유의한다.

도 8은 데이터 드라이브 스케줄링을 구현하는 예제 시스템(800)을 예시하는 블럭 다이어그램이다. 일 예제 구현예에서, 시스템 (800)은 프로세서 (102)의 특징부일 수 있다. 시스템 (800)은 프로세싱 유닛들 (810), 두개의 캐시 메모리들 (820 및 825), 둘 모두 프로세싱 유닛들 (810)에 의해 공유됨, 데이터 드라이브 스케줄러 (830), 및 쓰레드 디스패처(thread dispatcher) (840)를 포함한다. 시스템 (800)의 예제에서, 프로세싱 유닛들 (810)은 두개의 코어들, 이 경우에서, SMID 유닛들 SIMD0 및 SIMD1을 포함한다. 데이터 드라이브 스케줄러 (830)는 상관관계 어레이 (850) 및 결정 유닛 (860)을 포함하고, 쓰레드 레벨에 기하여 스케줄들을 결정한다.

이 예에서, 캐시 메모리들 (820 및 825)은 개별적으로 L1및 L2 캐시이다. 그러나, 캐시 메모리들 (820 및 825)는 SIMD들 SIMD0 및 SIMD1에 의해 공유되는 캐시 메모리 또는 다른 공유 메모리의 임의의 적절한 레벨들 일 수 있다는 것에 유의한다. 캐시 메모리들 (820 및 825)은 SIMD 유닛들 SIMD0 및 SIMD1에 의해 공유된다.

데이터 드라이브 스케줄러 (830)는 프로세싱 유닛들 (810)상에서의 실행을 위해 쓰레드들을 스케줄링한다. 상관관계 어레이 (850)는 쓰레드들간에 또는 그것들중에 상관관계를 계산한다. 결정 유닛 (860)은 특정 시간에 프로세싱 유닛들 (810) 중 특정 프로세싱 유닛에 어느 쓰레드을 디스패치할 것인지를 결정한다.

상관관계 데이터가 스케줄링에 이용 할 수 있기 전에, 데이터 드라이브 스케줄러 (830)는 디폴트 (예를 들어, 비-데이터-드라이브) 스케줄링 패턴을 사용하여 SIMD 유닛들 SIMD0 및 SIMD1상에서 실행을 위해 쓰레드 그룹들을 스케줄링한다. 이 디폴트 패턴은 라운드-로빈 패턴일 수 있다. 예제 시스템(800)에서, 스케줄링은 4 개의 쓰레드들의 단위로 수행된다. 따라서 첫번째 네개의 쓰레드들이 쓰레드(thread) 0, 쓰레드1, 쓰레드2, 및 쓰레드3를 나타내는 경우에, 라운드-로빈 방식으로 첫번째 4 쓰레드들에 대한 스케줄링은 쓰레드= SIMD0, 쓰레드= SIMD1, 쓰레드2 = SIMD0, 쓰레드3 = SIMD1일 것이다. 그런 다음 쓰레드 디스패처 (840)는 디폴트 스케줄에 따라 SIMD0 및 SIMD1상에서 실행을 위해 쓰레드들을 디스패치한다.

SIMD0 및/또는 SIMD1로부터 캐시 (820) 또는 캐시(825) 로의 새로운 메모리 요청시에, 요청을 수신한 캐시는 메모리 요청에 대응하는 인덱스 및 캐시 태그를 상관관계 어레이 (850)로 포워딩할 수 있다. 인덱스는 요청 쓰레드의 아이덴티티, 예를 들어 쓰레드 ID에 대응할 수 있고, 태그는 요청된 메모리 어드레스, 데이터 마스크(data mask) 및 / 또는 보조 정보를 포함 할 수 있다. 따라서, 캐시 (820 또는 825)는 현재 실행중인 쓰레드가 요구하는 메모리 액세스에 관한 정보를 상관관계 어레이 (850)에 제공한다. 태그는 데이터 캐시에서 사용되는 태그에 유사할 수 있다. 태그는 예를 들어, 물리적 어드레스, 또는 가상 메모리 식별자로 조합한 가상 어드레스일 수 있다.

상관관계 어레이 (850)는 인덱스 및 태그 정보를 저장할 수 있고, 이하에서 추가로 논의되는 쓰레드들에 대한 상관관계 값들을 계산하는데 이 정보를 사용할 수 있다. 상관관계 어레이 (850)는 이들 상관관계 값들을 결정 유닛 (860)에 보고할 수 있다. 결정 유닛 (860)은 SIMD0 및 SIMD1상에서 쓰레드들 쓰레드0, 쓰레드1, 쓰레드2, 쓰레드3의 실행을 위해 데이터-드라이브 스케줄링을 결정하는데 보고된 상관관계 값들을 사용할 수 있다. 그런 다음 쓰레드 디스패처 (840)는 데이터-드라이브 스케줄에 따라 SIMD0 및 SIMD1상에서 실행을 위해 쓰레드들을 디스패치할 수 있다.

도 9는 쓰레드들 쓰레드0, 쓰레드1, 쓰레드2, 및 쓰레드3의 실행 동안에 어떤 지점에서 상관관계 어레이 (650)의 예제 상태를 예시하는 표 (900)이다. 예제 시스템(800)은 4 개의 쓰레드들의 단위로 스케줄링을 수행한다. 따라서, 표 (900)은 4 키들 (910, 910', 910", 910"')을 포함하고, 이의 각각은 쓰레드들 쓰레드0, 쓰레드1, 쓰레드2, 및 쓰레드3 중 하나에 대응한다.

각각의 키 (910, 910', 910", 910"')는 대응하는 태그 리스트 (미도시) 및 기여 상관관계 값들 (920, 920', 920", 920"')의 세트를 포함한다. 기여 상관관계 값들 (920, 920', 920", 920"')의 세트는 쓰레드들 쓰레드0, 쓰레드1, 쓰레드2, 및 쓰레드3의 각각의 쌍의 상관관계를 반영한다. 예를 들어, 키 (910)는 쓰레드0에 대한 기여 상관관계 값들 (920)의 세트를 저장한다. 기여 상관관계 값 세트 (920)는, 쓰레드0와 쓰레드1간의 상관관계에 대응하는 기여 상관 값 C01과, 쓰레드0와 쓰레드2간의 상관관계에 대응하는 기여 상관 값 C02와, 쓰레드0와 쓰레드3간의 상관관계에 대응하는 기여 상관 값 C03을 저장한다. 각각의 다른 키들 (910', 910", 910"')은 도 9에 반영된 기여 상관관계 값들 (920', 910", 920"')의 유사한 세트를 저장한다. 상관관계 정보가 상관관계 어레이 (850)에 이용 가능할 수 있기 전에 (예를 들어, 방법 (300)의 단계 (310)에 유사한), 태그 리스트는 비어있을 수 있고 기여 상관관계 값들은 제로일 수 있다.

쓰레드 그룹의 실행동안에 SIMD0 또는 SIMD1에 의한 새로운 메모리 요청에 기해, 상관관계 어레이 (850)는 캐시로부터 메모리 요청의 태그 정보 및 대응하는 인덱스를 수신한다. 만약 인덱스 및 태그 정보가 표 (900)에 엔트리에 일치하면, 대응하는 기여 상관관계 값은 증분되거나, 증가되거나, 또는 그렇지 않으면, 증가된 상관관계를 반영하도록 변경될 수 있다. 예를 들어, 상관관계 어레이 (850)가 인덱스 쓰레드1 및 태그 태그3를 수신하고, 상관관계 어레이 (850)가 쓰레드0의 태그리스트가 또한 태그 3을 포함한다는 것을 반영하면, 그러면 쓰레드0와 쓰레드1 사이의 상관 관계를 반영하는 기여 상관관계 값 C01이 증가 될 수 있다(예를 들어, 일 만큼 증분된다).

만약 수신된 인덱스가 표 (900)내 키에 일치하지만, 그러나 수신된 태그가 태그 리스트내 임의의 태그들에 일치하지 않으면, 수신된 태그는 해당 키를 위한 태그 리스트로 삽입될 수 있다. 만약 수신된 인덱스가 표 (900)내 키에 일치하지 않으면, 그러나 수신된 태그가 태그 리스트내 임의의 태그들에 일치하지 않으면 새로운 키가 해당 인덱스에 대해 더해질 수 있고 만약 태그가 일치하여 다른 키들에 대한 상관관계들은 조정될 수 있다.

쓰레드0, 쓰레드1, 쓰레드2, 및 쓰레드3가 SIMD0 및 SIMD1상에서 실행 끝난 후에, 쓰레드0와 쓰레드1간의 상관관계를 반영하는 상관관계 값 C01를 결정하기 위해서 기여 상관관계 값들 C01 및 C10는 가산될 수 있다(또는 다른식으로, 결합될 수 있다). 다른 일치하는 기여 상관관계 값들이 또한 다른 쓰레드 쌍들을 위한 상관관계 값들을 찾기 위해서 유사하게 합산될 수 있다. 예를 들어, c02는 기여 상관관계 값들 C02 및 C20을 가산함으로써 계산된 쓰레드0 및 쓰레드2를 위한 상관관계 값일 수 있고, 등등일 수 있다. 이들 상관관계 값들 c01, c02, c03, c12, c13, c23은 결정 유닛 (660)으로 보고될 수 있다.

쓰레드0, 쓰레드1, 쓰레드2 및 쓰레드3이 SIMD0 및 SIMD1상에서 실행을 완료 할 때까지 대기하는 것이 아니라, 소정의 간격, 예를 들어 1,000 프로세서 클럭 사이클 후에 기여하는 상관관계 값들이 합산 및 / 또는 보고 될 수 있음을 유의해야 한다. 따라서, 상관관계 값들은 쓰레드0, 쓰레드1, 쓰레드2, 및 쓰레드3의 몇몇의 실행들 후에 또는 실행 완료전에 계산될 수 있다. 이것은 더 높은 분해능(resolution) 데이터에 기초한 동적 스케줄링 및/또는 스케줄링을 허용할 수 있다.

도 8로 돌아가서, 결정 유닛 (860)은 보고된 상관관계 값들 c01, c02, c03...에 기초하여 다음 4 개의 웨이브들 웨이브0, 웨이브1, 웨이브2, 및 웨이브3의 발행 순서 (즉, 데이터-드라이브 스케줄)을 결정할 수 있다. 표 3은 이 결정을 수행하기 위해 결정 유닛 (860)을 위한 부분 알고리즘의 예제를 반영하는 의사 코드를 도시한다. 쓰레드 디스패처 (840)는 결정 유닛 (860)로부터 데이터-드라이브 스케줄을 수신하고 데이터-드라이브 스케줄에 따라 CU0 및 CU1로 쓰레드들을 디스패치한다. 일부 구현예들에서, 쓰레드 디스패처 (840)는 스케줄이 변화되었다는 결정에 기하여 그것의 스케줄을 업데이트만 할 수 있다. 일부 구현예들에서, 스케줄이 변경된 상태에 기하여, 현재 SIMD0 및 SIMD1에서 실행중인 쓰레드들이 선점될 수 있고, 콘텍스트가 저장 될 수 있으며, 업데이트된 스케줄이 쓰레드에 적용될 수 있고 (즉, 쓰레드들이 다른 SIMD들 및/또는 실행 시간에 재할당 될 수 있음), 콘텍스트는 복원 될 수 있고, 업데이트 된 스케줄 하에서 실행이 재개 될 수 있다.

표 3

If(max{c01, c02, c03, ...} = = c0l)

{

group the next thread0 and thread2 to SIMD0;

group the next thread1 and thread3 to SIMD1;

}

else if(max{c01, c02, c03, ...} = = c02)

{

group the next thread0 and thread1 to SIMD0;

group the next thread2 and thread3 to SIMD1;

}

else if(max{c01, c02, c03, ...} = = c03)

{

group the next thread0 and thread1 to SIMD0;

group the next thread3 and thread2 to CU1;

}

...

도 10는 데이터 드라이브 스케줄링을 구현하는 예제 시스템(1000)을 예시하는 블럭 다이어그램이다. 일 예제 구현예에서, 시스템 (1000)은 프로세서 (102)의 특징부일 수 있다. 시스템 (1000)은 프로세싱 유닛들 (1010), 프로세싱 유닛들 (1010)에 의해 공유되는 캐시 메모리 (1020) , 데이터 드라이브 스케줄러 (1030), 및 쓰레드 디스패처(thread dispatcher) (640)를 포함한다. 시스템 (1000)의 예제에서, 프로세싱 유닛들 (1010)은 네개의 코어들, 이 경우에서, 컴퓨트 유닛들 CU0, CU1, CU2, 및 CU3을 포함한다. 데이터 드라이브 스케줄러 (1030)는 상관관계 어레이 (1050) 및 결정 유닛 (1060)을 포함하고, 쓰레드 디스패처 레벨에 기하여 스케줄들을 결정한다.

이 예제에서, 캐시 메모리 (1020)는 L2 캐시이다. 캐시 메모리 (820)는 컴퓨트 유닛들 CU0, CU1, CU2, 및 CU3에 의해 공유되는 캐시 메모리는 또는 다른 공유 메모리의 임의의 적절한 레벨 일 수 있다는 것에 유의한다. 캐시 메모리 (1020)는 컴퓨트 유닛들 CU0, CU1, CU2, 및 CU3에 의해 공유된다.

데이터 드라이브 스케줄러 (1030)는 프로세싱 유닛들 (1010)상에서의 실행을 위해 웨이브들을 스케줄링한다. 상관관계 어레이 (1050)는 웨이브들간에 또는 그것들중에 상관관계를 계산한다. 결정 유닛 (1060)은 특정 시간에 프로세싱 유닛들 (1010) 중 특정 프로세싱 유닛에 어느 웨이브를 디스패치할 것인지를 결정한다.

상관관계 데이터가 스케줄링에 이용 할 수 있기 전에, 데이터 드라이브 스케줄러 (1030)는 디폴트 (예를 들어, 비-데이터-드라이브) 스케줄링 패턴을 사용하여 컴퓨트 유닛들 CU0, CU1, CU2, 및 CU3상에서 실행을 위해 웨이브들을 스케줄링한다. 이 디폴트 패턴은 라운드-로빈 패턴일 수 있다. 예제 시스템(1000)에서, 스케줄링은 8 개의 웨이브들의 단위로 수행된다. 따라서 첫번째 여덟개의 쓰레드들이 웨이브0, 웨이브1, 웨이브2, 웨이브3, 웨이브4, 웨이브5, 웨이브6, 및 웨이브7를 나타내는 경우에, 라운드-로빈 방식으로 첫번째 8 웨이브들에 대한 스케줄링은 웨이브0= CU0, 웨이브1= CU1, 웨이브2= CU2, 웨이브3= CU3 웨이브4= CU0, 웨이브5= CU1, 웨이브6= CU2, 웨이브7=CU3일 것이다. 그런 다음 쓰레드 디스패처 (1040)는 디폴트 스케줄에 따라 CU0, CU1, CU2, 및 CU3에서 실행을 위해 웨이브들을 디스패치한다.

CU0, CU1, CU2, 및/또는 CU3로부터 캐시 (1020) 로의 새로운 메모리 요청시에, 캐시 (1020)는 메모리 요청에 대응하는 인덱스 및 캐시 태그를 상관관계 어레이 (1050)로 포워딩할 수 있다. 인덱스는 요청 웨이브의 아이덴티티, 예를 들어 웨이브 ID에 대응할 수 있고, 태그는 요청된 메모리 어드레스, 데이터 마스크 및 / 또는 보조 정보를 포함 할 수 있다. 따라서, 캐시 (1020)는 현재 실행중인 웨이브가 요구하는 메모리 액세스에 관한 정보를 상관관계 어레이 (1050)에 제공한다. 태그는 물리적 어드레스, 또는 가상 메모리 식별자로 조합한 가상 어드레스일 수 있다.

상관관계 어레이 (1050)는 인덱스 및 태그 정보를 저장할 수 있고, 웨이브들에 대한 상관관계 값들을 계산하는데 이 정보를 사용할 수 있다. 상관관계 어레이 (1050)는 이들 상관관계 값들을 결정 유닛 (1060)에 보고할 수 있다. 결정 유닛 (1060)은 CU0, CU1, CU2, 및 CU3상에서 웨이브들 웨이브0, 웨이브l, 웨이브2, 웨이브3, 웨이브4, 웨이브5, 웨이브6, 및 웨이브7의 실행을 위해 데이터-드라이브 스케줄링을 결정하는데 보고된 상관관계 값들을 사용할 수 있다. 그런 다음 웨이브 디스패처 (1040)는 데이터-드라이브 스케줄에 따라 CU0, CU1, CU2, 및 CU3에서 실행을 위해 웨이브들을 디스패치할 수 있다.

도 11은 웨이브들 웨이브0, 웨이브l, 웨이브2, 웨이브3, 웨이브4, 웨이브5, 웨이브6, 및 웨이브7의 실행 동안에 어떤 지점에서 상관관계 어레이 (650)의 예제 상태를 예시하는 표 (1100)이다. 예제 시스템(1000)은 8 개의 웨이브들 단위로 스케줄링을 수행한다. 따라서, 표 (1100)는 8 키들 (1110a, 1110b, 1110c, 1110d, 1110e, 1110f, 1110g, 1110h)을 포함하고, 이의 각각은 개별적으로 웨이브들 웨이브0, 웨이브1, 웨이브2, 웨이브3, 웨이브4, 웨이브5, 웨이브6, 및 웨이브7 중 하나에 대응한다.

각각의 키 (1110a, 1110b, 1110c, 1110d, 1110e, 1110f, 1110g, 1110h)는 대응하는 태그 리스트 (미도시) 및 기여 상관관계 값들 (1120a, 1120b, 1120c, 1120d, 1120e, 1120f, 1120g, 1120h)의 세트를 포함한다. 기여 상관관계 값들 (1120a, 1120b, 1120c, 1120d, 1120e, 1120f, 1120g, 1120h)의 세트는 웨이브들 웨이브0, 웨이브1, 웨이브2, 웨이브3, 웨이브4, 웨이브5, 웨이브6, 및 웨이브7의 각각의 쌍의 상관관계를 반영한다. 예를 들어, 키 (1110a)는 웨이브0에 대한 기여 상관관계 값들 (1120a)의 세트를 저장한다. 기여 상관관계 값 세트 (1120a)는, 웨이브0와 웨이브1간의 상관관계에 대응하는 기여 상관 값 C01과, 웨이브0와 웨이브2간의 상관관계에 대응하는 기여 상관 값 C02와, 웨이브0와 웨이브3간의 상관관계에 대응하는 기여 상관 값 C03, 등등을 저장한다. 각각의 다른 키 (1110b, 1110c, 1110d, 1110e, 1110f, 1110g, 1110h)는 도 11에 반영된 유사한 기여 상관관계 값들 (1120b, 1120c, 1120d, 1120e, 1120f, 1120g, 1120h)의 세트를 저장한다. 상관관계 정보가 상관관계 어레이 (1050)에 이용 가능할 수 있기 전에 (예를 들어, 방법 (300)의 단계 (310)에 유사한), 태그 리스트는 비어있을 수 있고 기여 상관관계 값들은 제로일 수 있다.

웨이브의 실행동안에 CU0, CU1, CU2, 또는 CU3에 의한 새로운 메모리 요청에 기해, 상관관계 어레이 (1050)는 캐시로부터 메모리 요청의 태그 정보 및 대응하는 인덱스를 수신한다. 만약 인덱스 및 태그 정보가 표 (1100)에 엔트리에 일치하면, 대응하는 기여 상관관계 값은 증분되거나, 증가되거나, 또는 그렇지 않으면, 증가된 상관관계를 반영하도록 변경될 수 있다. 예를 들어, 상관관계 어레이 (1050)가 인덱스 웨이브1 및 태그 태그3를 수신하고, 상관관계 어레이 (1050)가 웨이브0의 태그리스트가 또한 태그 3을 포함한다는 것을 반영하면, 그러면 웨이브0와 웨이브1 사이의 상관 관계를 반영하는 기여 상관관계 값 C01이 증가 될 수 있다(예를 들어, 일 만큼 증분된다).

만약 수신된 인덱스가 표 (1100)내 키에 일치하지만, 그러나 수신된 태그가 태그 리스트내 임의의 태그들에 일치하지 않으면, 수신된 태그는 해당 키를 위한 태그 리스트로 삽입될 수 있다. 만약 수신된 인덱스가 표 (1100)내 키에 일치하지 않으면, 그러나 수신된 태그가 태그 리스트내 임의의 태그들에 일치하지 않으면 새로운 키가 해당 인덱스에 대해 더해질 수 있고 만약 태그가 일치하여 다른 키들에 대한 상관관계들은 조정될 수 있다.

웨이브0, 웨이브l, 웨이브2, 웨이브3, 웨이브4, 웨이브5, 웨이브6, 및 웨이브7이 CU0, CU1, CU2, 및 CU3상에서 실행 끝난 후에, 웨이브0와 웨이브1간의 상관관계를 반영하는 상관관계 값 C01를 결정하기 위해서 기여 상관관계 값들 C01 및 C10는 가산될 수 있다(또는 다른식으로, 결합될 수 있다). 다른 일치하는 기여 상관관계 값들이 또한 다른 쓰레드 쌍들을 위한 상관관계 값들을 찾기 위해서 유사하게 합산될 수 있다. 예를 들어, c02는 기여 상관관계 값들 C02 및 C20을 가산함으로써 계산된 웨이브0 및 웨이브2를 위한 상관관계 값일 수 있고, 등등일 수 있다. 이들 상관관계 값들 c01, c02, c03, c04, c05, c06, c07, c12, c13, c14, c15, c16, c17, c23, c24, c25, c26, c27, c34, c35, c36, c37, c45, c46, c47, c56, c57, c67은 결정 유닛 (660)에 보고될 수 있다.

웨이브들 웨이브0, 웨이브1, 웨이브2, 웨이브3, 웨이브4, 웨이브5, 웨이브6, 및 웨이브7이 CU0, CU1, CU2, 및 CU3에 대한 실행을 완료 할 때까지 대기하는 것이 아니라, 소정의 간격, 예를 들어 1,000 프로세서 클럭 사이클 후에 기여하는 상관관계 값들이 합산 및 / 또는 보고 될 수 있음을 유의해야 한다. 따라서, 상관관계 값들은 CU0, CU1, CU2, 및 CU3의 몇몇의 실행들 후에 또는 실행 완료전에 계산될 수 있다. 이것은 더 높은 분해능(resolution) 데이터에 기초한 동적 스케줄링 및/또는 스케줄링을 허용할 수 있다.

도 1000으로 돌아가서, 결정 유닛 (1060)은 보고된 상관관계 값들 c0l, c02, c03, c04, c05, c06, c07, c12, c13, c14, c15, c16, c17, c23, c24, c25, c26, c27, c34, c35, c36, c37, c45, c46, c47, c56, c57, c67에 기초하여 다음 8 개의 웨이브들 웨이브들 웨이브0, 웨이브l, 웨이브2, 웨이브3, 웨이브4, 웨이브5, 웨이브6, 및 웨이브7의 발행 순서 (즉, 데이터-드라이브 스케줄)을 결정할 수 있다. 표 4는 이 결정을 수행하기 위해 결정 유닛 (1060)을 위한 부분 알고리즘의 일 예를 도시한다. 웨이브 디스패처 (1040)는 결정 유닛 (1060)로부터 데이터-드라이브 스케줄을 수신하고 데이터-드라이브 스케줄에 따라 CU0, CU1, CU2, 및 CU3로 쓰레드들을 디스패치한다. 일부 구현예들에서, 웨이브 디스패처 (1040)는 스케줄이 변화되었다는 결정에 기하여 그것의 스케줄을 업데이트만 할 수 있다. 일부 구현예들에서, 스케줄이 변경된 상태에 기하여, 현재 CU0, CU1, CU2, 및 CU3에서 실행중인 쓰레드 그룹들이 선점될 수 있고, 콘텍스트가 저장 될 수 있으며, 업데이트된 스케줄이 웨이브들에 적용될 수 있고 (즉, 웨이브들이 다른 컴퓨트 유닛들 및/또는 실행 시간에 재할당 될 수 있음), 콘텍스트는 복원 될 수 있고, 업데이트 된 스케줄 하에서 실행이 재개 될 수 있다.

표 4

8 웨이브들 및 4CU들에 대하여:

1: 웨이브 X (X=0-7)에 대하여

2: 웨이브 X에 대한 가장 높은 상관관계를 갖는 쓰레드 Y를 획득하기 위해 서로 다른 쓰레드를 갖는 웨이브 X의 상관관계를 계산.

3: X 및 Y에 대한 가장 높은 상관관계를 갖는 웨이브 Z를 결정하기 위해 웨이브 X, 웨이브 Y, 및 서로 다른 웨이브 간에 세개의-변수 상관관계를 계산.

4: X, Y 및 Z에 대한 가장 높은 상관관계를 갖는 웨이브를 결정하기 위해 웨이브 X, 웨이브 Y, 웨이브 Z, 및 서로 다른 웨이브 간에 네개의-변수 상관관계를 계산.

5: 개별적으로 CU들 0, 1, 2, 3 상에서 병렬로 실행하기 위해 웨이브들 X, Y, Z을 스케줄링.

5a: 옵션으로, 가장 높은 4-변수 상관관계로 귀결되는 X의 값을 결정하고 해당 X의 값에 기초하여 개별적으로 CU들 0, 1, 2, 3 상에서 병렬로 실행하기 위해 웨이브들 X, Y, Z을 스케줄링.

임의의 이들 또는 다른 구현예들에 대하여, 데이터 드라이브 스케줄러는 클럭 게이트(clock gate), 파워 게이트될 수 있거나, 또는 예를 들어, 유휴상태일 때 상이한 적절한 파워 절감 메커니즘에 따를 수 있다는 것에 유의한다. 데이터 드라이브 스케줄러는 예를 들어, 새로운 셰이더가 실행될 때까지 유휴상태에 잔존할 수 있다.

추가로 임의의 이들 또는 다른 구현예들에 대하여, 태그 리스트는 예를 들어, 검색을 용이하게 하기 위하여 오름차순(ascending order)로 또는 내림차순(descending order)으로 저장될 수 있고, 압축 또는 비압축될 수 있다는 것에 유의한다.

다수의 변형이 본 출원에서의 개시에 기초하여 가능하다는 것이 이해되어야 한다. 특히 특징 및 요소가 조합하여 상술되었지만, 각 특징 또는 요소는 다른 특징 및 요소 없이 단독으로, 또는 다른 특징 및 요소와 함께 또는 이들 없이 다양한 조합으로 사용될 수 있다.

제공된 방법은 범용 컴퓨터, 프로세서, 또는 프로세서 코어로 구현될 수 있다. 적절한 프로세서는 예시의 방식으로, 범용 프로세서, 특수 목적 프로세서, 통상적인 프로세서, 디지털 신호 프로세서(DSP), 복수의 마이크로프로세서, DSP코어와 연관된 하나 이상의 마이크로프로세서, 컨트롤러, 마이크로컨트롤러, 어플리케이션 특정 집적 회로(ASIC), 필드 프로그래머블 게이트 어레이(FPGA) 회로, 임의의 다른 유형의 집적 회로(IC) 및/또는 상태 머신을 포함한다. 이러한 프로세서는 프로세싱된 하드웨어 기술 언어(HDL) 명령 및 넷리스트(컴퓨터 판독가능 매체에 저장될 수 있는 명령)를 포함하는 다른 중간 데이터의 결과를 사용하여 제조 프로세스를 구성함으로써 제조될 수 있다. 이러한 프로세싱의 결과는 실시예의 양태를 구현하는 프로세서를 제조하기 위해 반도체 제조 프로세스에서 사용되는 마스크워크일 수 있다.

본 출원에 제공되는 방법 또는 흐름도는 범용 컴퓨터 또는 프로세서에 의한 실행을 위해 비일시적 컴퓨터 판독가능 저장매체에 통합된 컴퓨터 프로그램, 소프트웨어 또는 펌웨어로 구현될 수 있다. 비-일시적 컴퓨터-판독가능한 스토리지 매체들의 예들은 판독 전용 메모리 (ROM), 랜덤 액세스 메모리 (RAM), 레지스터, 캐시 메모리, 반도체 메모리 디바이스들, 자기 미디어 예컨대 내부 하드 디스크들 및 착탈 가능한 디스크들, 광자기 매체, 및 광 매체 예컨대 CD-ROM 디스크들, 및 디지털 다기능 디스크들 (DVD들)을 포함한다.

Claims (51)

1. 프로세서의 복수의 컴퓨팅 코어들의 데이터 드라이브 스케줄링(data driven scheduling)을 위한 방법으로서, 상기 방법은:
   디폴트 스케줄(default schedule)에 따라 상기 복수의 컴퓨팅 코어들상에서 복수의 쓰레드들을 실행시키는 단계;
   상기 복수의 쓰레드들의 다양한 가능한 서브세트들에 대한 상관 값(correlation value)들을 결정하기 위해 상기 실행에 기초하여 상기 복수의 쓰레드들을 분석하는 단계 - 상기 상관 값들은 각각의 서브세트 내의 쓰레드들 간의 상관관계(correlation)들을 나타내고, 상기 상관관계들은 상기 복수의 쓰레드들의 상기 서브세트들 간의 메모리 재사용(memory re-use)의 양(amount)을 포함함 -;
   상기 상관 값들에 기초하여 데이터 드라이브 스케줄을 생성하는 단계 - 상기 복수의 쓰레드들의 상기 서브세트들 각각 내의 쓰레드들은, 상기 복수의 쓰레드들 전부의 실행에 걸쳐 상기 상관 값들이 최대화되도록 상기 복수의 컴퓨팅 코어들 상에서 병렬로 실행되도록 스케줄링됨 -; 및
   상기 데이터 드라이브 스케줄에 따라 상기 복수의 컴퓨팅 코어들상에서 상기 복수의 쓰레드들을 실행시키는 단계를 포함하는, 방법.
2. 삭제
3. 삭제
4. 청구항 1에 있어서, 상기 디폴트 스케줄은 라운드-로빈(round-robin) 스케줄을 포함하는, 방법.
5. 청구항 1에 있어서, 상기 상관관계들을 결정하기 위해 상기 복수의 쓰레드들을 분석하는 단계는:
   데이터-드라이브 스케줄링 회로부에 의해, 상기 컴퓨팅 코어들상에서의 상기 복수의 쓰레드들의 적어도 일부의 실행에 기인한 상기 컴퓨팅 코어들에 의한 메모리 액세스들의 정보를 수신하는 단계; 및
   상기 정보에 기초하여 상기 상관관계들을 도출하는 단계(deriving)를 포함하는, 방법.
6. 청구항 5에 있어서, 상기 메모리는 상기 복수의 컴퓨팅 코어들간에 공유되는, 방법.
7. 청구항 5에 있어서, 상기 메모리는 캐시 메모리를 포함하는, 방법.
8. 청구항 1에 있어서, 상기 복수의 쓰레드들의 각각이 상기 컴퓨팅 코어들상에서 실행을 완료된 후에 상기 데이터 드라이브 스케줄이 생성되는, 방법.
9. 청구항 1에 있어서,
   상기 컴퓨팅 코어들상에서 상기 복수의 쓰레드들의 실행이 시간 기간동안 진행된 후에 상기 데이터 드라이브 스케줄이 생성되는, 방법.
10. 청구항 1에 있어서, 상기 복수의 쓰레드들 전부가 상기 컴퓨팅 코어들상에서 실행을 완료하기 전에 상기 데이터 드라이브 스케줄이 생성되는, 방법.
11. 데이터-드라이브 스케줄링(data-driven scheduling)을 위해 구성된 프로세서에 있어서, 상기 프로세서는
    복수의 컴퓨팅 코어들;
    상기 컴퓨팅 코어들의 각각에 의해 공유되는 메모리;
    디폴트 스케줄(default schedule)에 따라 상기 복수의 컴퓨팅 코어들상에서 실행하기 위한 복수의 쓰레드들을 디스패치(dispatch)하도록 구성된 디스패칭 회로부(dispatching circuitry);
    상기 복수의 쓰레드들의 다양한 가능한 서브세트들에 대한 상관 값들을 결정하기 위해 상기 실행에 기초하여 상기 복수의 쓰레드들을 분석하도록 구성된 상관관계 회로부 - 상기 상관 값들은 각각의 서브세트 내의 쓰레드들 간의 상관관계들을 나타내고, 상기 상관관계들은 상기 복수의 쓰레드들의 상기 서브세트들 간의 메모리 재사용의 양을 포함함 -; 및
    상기 상관 값들에 기초하여 데이터 드라이브 스케줄을 결정하도록 구성된 스케줄링 회로부 - 상기 복수의 쓰레드들의 상기 서브세트들 각각 내의 쓰레드들은, 상기 복수의 쓰레드들 전부의 실행에 걸쳐 상기 상관 값들이 최대화되도록 상기 복수의 컴퓨팅 코어들 상에서 병렬로 실행되도록 스케줄링됨 - 를 포함하는, 상기 프로세서를 포함하되,
    상기 디스패칭 회로부는 상기 데이터 드라이브 스케줄에 따라 상기 복수의 컴퓨팅 코어들상에서 실행하기 위한 상기 복수의 쓰레드들을 디스패치하도록 더 구성된, 프로세서.
12. 삭제
13. 삭제
14. 청구항 11에 있어서, 상기 디폴트 스케줄은 라운드-로빈(round-robin) 스케줄을 포함하는, 프로세서.
15. 청구항 11에 있어서, 상기 상관관계 회로부는:
    상기 컴퓨팅 코어들상에서의 상기 복수의 쓰레드들의 적어도 일부의 실행에 기인한 상기 컴퓨팅 코어들에 의한 메모리 액세스들의 정보를 수신하고; 그리고
    상기 정보에 기초하여 상기 상관관계들을 도출하도록 더 구성된, 프로세서.
16. 청구항 15에 있어서, 상기 메모리는 상기 복수의 컴퓨팅 코어들간에 공유되는, 프로세서.
17. 청구항 15에 있어서, 상기 메모리는 캐시 메모리를 포함하는, 프로세서.
18. 청구항 11에 있어서, 상기 프로세서는:
    상기 데이터 드라이브 스케줄이 상기 디폴트 스케줄과 상이한지 여부를 결정하고; 및
    만약 상기 데이터 드라이브 스케줄이 상기 디폴트 스케줄과 상이하면:
    상기 컴퓨팅 코어들의 실행을 선점하고;
    현재 콘텍스트를 저장하고;
    상기 데이터 드라이브 스케줄에 따라 상기 복수의 쓰레드들을 디스패치하도록 더 구성된 회로부를 포함하는, 프로세서.
19. 청구항 11에 있어서, 상기 복수의 쓰레드들의 각각이 상기 컴퓨팅 코어들상에서 실행을 완료된 후에 상기 데이터 드라이브 스케줄이 생성되는, 프로세서.
20. 청구항 11에 있어서,
    상기 컴퓨팅 코어들상에서 상기 복수의 쓰레드들의 실행이 시간 기간동안 진행된 후에 상기 데이터 드라이브 스케줄이 생성되는, 프로세서.
21. 삭제
22. 삭제
23. 삭제
24. 삭제
25. 삭제
26. 삭제
27. 삭제
28. 삭제
29. 삭제
30. 삭제
31. 삭제
32. 삭제
33. 삭제
34. 삭제
35. 삭제
36. 삭제
37. 삭제
38. 삭제
39. 삭제
40. 삭제
41. 삭제
42. 삭제
43. 삭제
44. 삭제
45. 삭제
46. 삭제
47. 삭제
48. 삭제
49. 삭제
50. 삭제
51. 삭제

Images