KR100368350B1

KR100368350B1 - 다중 스레드를 이용하는 처리 시스템과 다중 스레드 이용방법, 다중 독립 스레드 실행 방법과 스레드 실행 제어장치, 스레드와 연계한 프리페치 버퍼 이용 방법, 및스레드 실행 콘트롤러

Info

Publication number: KR100368350B1
Application number: KR10-2001-0011116A
Authority: KR
Inventors: 데이비스고던테일러; 헤더스마르코씨; 리이벤스로스보이드; 베르플랜켄페이브리스진
Original assignee: 인터내셔널 비지네스 머신즈 코포레이션
Priority date: 2000-04-04
Filing date: 2001-03-05
Publication date: 2003-01-24
Also published as: US8006244B2; DE10110504B4; US6931641B1; DE10110504A1; CA2334393A1; KR20010094951A; JP2001350638A; US20050022196A1

Abstract

실행이 유휴 스레드에 대해 제공될 때 즉시 정지를 피하도록 하는 방식으로 다수의 독립적인 스레드 처리와 연계하여 프리페치 버퍼가 이용된다. 보다 효율적인 프로세서 자원의 활용을 성취하기 위해, 프로세서 내부에서 하나의 스레드를 다른 것으로 스위칭하는 것을 제어하도록 메커니즘이 설정된다. 이 메커니즘은 단 대기시간 이벤트(a short latency event)와 대면했을 때에는 다른 실행 스레드로 일시 제어(temporary control)를 승인하고, 장 대기시간 이벤트(a long latency event)와 대면했을 때에는 다른 실행 스레드로 전 제어(full control)를 승인할 것이다. 이 스레드 제어 메커니즘은 우선 순위 FIFO를 포함하는데, 이것은 그 출력이, 각 실행 스레드가 FIFO 내에서 상주하는 시간 길이에 근거하여, 프로세서 내에서 2개 이상의 실행 스레드에 대해 실행 우선 순위를 제어하도록 구성된다. FIFO에는 새로운 태스크(예컨대, 네트워크 내에서 분류와 라우팅을 필요로 하는 네트워킹 패킷)가 처리를 위해 디스페치될 때마다 실행 스레드 번호가 적재되는데, FIFO에 적재된 실행 스레드 번호는 태스크를 처리하기 위해 배정된 스레드 번호에 대응한다. 어떤 실행 스레드가 어떤 태스크의 처리를 완료하고 추후의 처리를 위해 그 결과를 큐잉(enqueue)할 때, 우선 순위 FIFO는 FIFO에서 그에 상응하는 실행 스레드 번호를 제거하도록 제어된다. 활성 실행 스레드가 장 대기시간 이벤트와 대면했을 때, FIFO 내에서 그에 상응하는 스레드 번호는 FIFO 내의 높은 우선 순위 위치에서 제거되어, FIFO 내의 최하위 우선 순위 위치에 배열된다. 또한, 이러한 스레드 제어 메커니즘은 프로세서에 의해 지원되는 각각의 실행 스레드용 스레드 제어 상태 머신(thread control state machine)을 포함한다. 스레드 제어 상태 머신은 4개의 상태를 포함한다. 초기(Initial) 상태는 실행 스레드가 처리를 위해 태스크를 대기하는 동안 이용된다. 일단 태스크가 처리를 위해 큐잉되면, 준비(Ready) 상태가 실행 사이클을 요구하기 위해 이용된다. 일단 프로세서에 대한 액세스가 승인되면, 실행(Execute) 상태가 실제 프로세서 실행을 지원하기 위해 이용된다. 추가 프로세서 사이클에 대한 요구는 준비 상태와 실행 상태 모두에서 이루어진다. 상태 머신은 일단 배정된 태스크에 대한 처리가 완료되면 초기 상태로 복귀한다. 대기(Wait) 상태는 실행 스레드가 장 대기시간 이벤트나 단 대기시간 이벤트로 인해 정지되는 동안에 실행 사이클에 대한 요구를 일시 중지시키기 위해 이용된다. 이러한 스레드 제어 메커니즘은 또한 프로세서 자원에 대한 액세스를 위해 어떤 실행 스레드가 승인되어야 하는지를 결정하기 위해 우선 순위 FIFO로부터의 스레드 번호를 이용하는 중재기(arbiter)를 더 포함한다. 중재기는 또한 각각의 실행 스레드로부터의 실행 제어에 대한 요구를 처리하고, 요구 실행 스레드로부터의 스레드 번호와 우선 순위 FIFO 내의 대응하는 스레드 번호를 매칭시킴으로써 각 프로세서 실행 사이클동안에 프로세서 자원에 대해 액세스가 승인될 하나의 실행 스레드를 선택한다.

Description

다중 스레드를 이용하는 처리 시스템과 다중 스레드 이용 방법, 다중 독립 스레드 실행 방법과 스레드 실행 제어 장치, 스레드와 연계한 프리페치 버퍼 이용 방법, 및 스레드 실행 콘트롤러{CONTROLLER FOR MULTIPLE INSTRUCTION THREAD PROCESSORS}

본 출원은 "NETWORK PROCESSOR WITH MULTIPLE INSTRUCTION THREADS"란 명칭의 미국 특허 출원 제 _______호(문서 번호 RAL9-2000-0008-US1)과 관련된 것이다.

본 발명은 전반적으로 컴퓨터 시스템에 관한 것으로, 보다 구체적으로는, 데이터 특히 트리 구조(tree structures)로 포맷된 데이터를 액세스함에 있어서 대기시간(latency)의 영향을 최소화시키도록 컴퓨터가 다중 인스트럭션 스레드(multiple threads of instruction)를 실행하는 컴퓨터 시스템에 관한 것이다.

네트워크 프로세서는 스위칭(switching)과 라우팅 기능을 효율적으로 구현하도록 설계된다. 네트워크 프로세서와 관련한 주요 성능 측정은 전형적인 패킷 혹은 데이터 프레임을 처리하는데 필요한 머신 사이클의 수(the number of machine cycles)이다. 처리는 전형적으로 두 부분으로 나뉘어지는데, 즉, 네트워크 프로세서 CPU(중앙 처리 장치)에 의해 실행되는 인스트럭션과, 몇몇 네트워크 프로세서 CPUs들 사이에 공유되어 있는 메모리 소스에 전형적으로 기억되는 라우팅 및 제어 테이블에 대한 액세스로 나뉘어진다. CPU 인스트럭션 실행은 전형적으로 라우팅 테이블에 대한 액세스 동안 정지(stall)되고, 따라서 패킷을 처리하는데 필요한 머신 사이클의 수를 상당히 증가시킨다. 사실상, 이러한 트리 구조중 하나에 대한액세스를 완료하는 시간은 CPU가 액세스를 설정하고 액세스된 데이터를 처리하는데 필요한 시간보다 2배 혹은 3배 더 오래 걸릴 수도 있다. 이러한 라우팅 및 제어 테이블을 위한 데이터는 흔히 트리 구조로 포맷되는데, 트리 구조에서 원하는 테이블 엔트리를 효율적으로 액세스하기 위해서는 전용 코프로세서나 트리 서치 엔진(tree-search engine;TSE)이 필요하다. 로컬 데이터 기억장치와 함께 작업하도록 설정된 다른 코프로세서들도 마찬가지로 CPU를 정지시키지만, 그 기간은 보다 짧다.

종래 기술에서는, 이전에 특허된 구현물로서 다중 스레드를 이용하는 다수의 시스템을 볼 수 있다.

미국 특허 제 5,357,617호(데이비스 등)-이 특허는 어떤 실행 스레드(execution thread)를 0 오버헤드(zero overhead)로 다른 것으로 스위칭하는 것을 다룬다. 더 구체적으로, CPU는 CPU 자원의 시분할 다중화 할당으로 다중 인스트럭션 스레드 사이를 계속해서 스위칭한다. 다시 말하면, 다중 인스트럭션 스레드는 정적 인터리빙 메커니즘(static interleaving mechanism)을 통해 제어된다.

미국 특허 제 5,404,469호-이 특허는 CPU 자원의 시분할 다중화 할당의 개념을 VLIW(very long instruction word) 아키텍처를 갖는 프로세서에 대해 확대한다.

미국 특허 제 5,694,604호-이 특허는 전형적인 소프트웨어 멀티프로세싱 해결법을 기술하는데, 이 방법에서는 선택된 인스트럭션 스레드가 특정 길이의 실행 시간에 할당되고, 그 뒤에 그 콘텍스트(context)가 저장되고, 다음 인스트럭션 스레드와 관련해 이전 콘텍스트가 복원(restored)된다. 이런 유형의 시스템에서는,어떤 스레드를 다른 것으로 스위칭할 때 머신 콘텍스트를 저장 및 복원하는데 상당한 비용(머신 사이클에 있어서)이 들기 때문에, 각각의 스레드는 전형적으로 확장된 주기동안 실행된다.

미국 특허 제 5,812,811호-이 특허는 프로그램의 완료를 가속화하기 위해 동일한 프로그램의 부분인 다중 인스트럭션 스레드를 병렬로 실행하는 것을 언급한다. 또한 이 특허는 프로그램의 실행을 완료하기 위해 필요할 수도 있고 필요하지 않을 수도 있는 경로의 투기적 실행(speculative execution)을 다룬다.

미국 특허 제 5,933,627호-이 특허는 필요한 데이터가 로컬 캐시에서 발견되지 않아서 CPU가 정지될 때 다른 스레드(an alternate thread)로 스위칭하는 것을 설명한다. 이 시스템은 어떤 스레드가 CPU의 제어를 획득할 것인지를 CPU가 명시적으로 제어하는 것을 요구한다. 또한 이 특허는 독립적인 프로세스가 아닌 동일한 프로그램의 조각들로서 다중 스레드를 설명한다.

미국 특허 제 5,694,603호-이 특허는 또다른 전형적인 소프트웨어 멀티프로세싱 해결법을 설명하는데, 이 방법은 어떤 스레드를 다른 것으로 선점형 스위칭(preemptive switching)하는 것을 포함한다.

본 발명의 목적은, 프로세서 자원의 보다 효율적인 활용을 달성하기 위해 프로세서(예컨대 네트워크 프로세서)내에서 어떤 스레드를 다른 것으로 스위칭하는 것을 제어하는 것이다.

본 발명의 또다른 목적은, 단 대기시간 이벤트(a short latency event)와 대면했을 때에는 다른 실행 스레드로 일시 제어(temporary control)를 승인하고, 장 대기시간 이벤트(a long latency event)와 대면했을 때에는 다른 실행 스레드로 전 제어(full control)를 승인하는 것이다.

본 발명은 우선 순위 FIFO(priority FIFO)를 포함하는데, 이것은 그 출력이, 각 실행 스레드가 FIFO 내에서 상주하는 시간 길이에 근거하여, 프로세서 내에서 2개 이상의 실행 스레드에 대해 실행 우선 순위를 제어하도록 구성된다. FIFO에는 새로운 태스크(예컨대, 네트워크 내에서 분류와 라우팅을 필요로 하는 네트워킹 패킷)가 처리를 위해 디스페치될 때마다 실행 스레드 번호가 적재되는데, FIFO에 적재된 실행 스레드 번호는 태스크를 처리하기 위해 배정된 스레드 번호에 대응한다. 어떤 실행 스레드가 어떤 태스크의 처리를 완료하고 추후의 처리를 위해 그 결과를 큐잉(enqueue)할 때, 우선 순위 FIFO는 FIFO에서 그에 상응하는 실행 스레드 번호를 제거하도록 제어된다. 활성 실행 스레드가 장 대기시간 이벤트와 대면했을 때, FIFO 내에서 그에 상응하는 스레드 번호는 FIFO 내의 높은 우선 순위 위치에서 제거되어, FIFO 내의 최하위 우선 순위 위치에 배열된다.

또한 본 발명은 프로세서에 의해 지원되는 각각의 실행 스레드용 스레드 제어 상태 머신(thread control state machine)을 포함한다. 스레드 제어 상태 머신은 4개의 상태를 포함한다. 초기(Initial) 상태는 실행 스레드가 처리를 위해 태스크를 대기하는 동안 이용된다. 일단 태스크가 처리를 위해 큐잉되면, 준비(Ready) 상태가 실행 사이클을 요구하기 위해 이용된다. 일단 프로세서에 대한 액세스가 승인되면, 실행(Execute) 상태가 실제 프로세서 실행을 지원하기 위해 이용된다. 추가 프로세서 사이클에 대한 요구는 준비 상태와 실행 상태 모두에서 이루어진다. 상태 머신은 일단 배정된 태스크에 대한 처리가 완료되면 초기 상태로 복귀한다. 대기(Wait) 상태는 실행 스레드가 장 대기시간 이벤트나 단 대기시간 이벤트로 인해 정지되는 동안에 실행 사이클에 대한 요구를 일시 중지시키기 위해 이용된다.

또한 본 발명은 프로세서 자원에 대한 액세스를 위해 어떤 실행 스레드가 승인되어야 하는지를 결정하기 위해 우선 순위 FIFO로부터의 스레드 번호를 이용하는 중재기(arbiter)를 더 포함한다. 중재기는 또한 각각의 실행 스레드로부터의 실행 제어에 대한 요구를 처리하고, 요구 실행 스레드로부터의 스레드 번호와 우선 순위 FIFO 내의 대응하는 스레드 번호를 매칭시킴으로써 각 프로세서 실행 사이클동안에 프로세서 자원에 대해 액세스가 승인될 하나의 실행 스레드를 선택한다. 중재기의 논리 함수는 또한 다음의 불 수식(Boolean expression)으로 정의된다.

여기에서 G_n은 주어진 스레드 n으로부터의 승인이고, R_n은 주어진 스레드 n으로부터의 요구이며, P_A, P_B, P_C는 우선 순위에 따라 알파벳순의 첨자로 정렬된 스레드를 나타내며, n은 비트 혹은 2진수로 스레드를 식별하는 첨자이다.

또한 본 발명은 유휴 스레드에 대해 실행이 승인될 때에 즉시정지(immediate stall)를 막아주도록 다수의 독립적인 스레드 프로세서와 연계하여 프리페치 버퍼를 이용하는 것과도 관련이 있다. 이것은 버퍼가 활성 실행 스레드에 의해 활용되는 중이었는지 결정하는 것을 수반한다. 버퍼가 활성 실행 스레드에 의해 이용되고 있지 않는 동안에는, 버퍼가 유휴 실행 스레드에 대한 인스트럭션을 프리페치할 수 있다.

도 1은 2개의 코프로세서를 갖는 네트워크 프로세서 아키텍처의 예시도,

도 2는 본 발명의 일 실시예의 예시도,

도 3은 스레드 실행 제어도,

도 4는 2개의 실행 스레드와 단일 CPU에 대한 파형도.

도면의 주요 부분의 부호 설명

10, 110 : CPU 12, 112 : 범용 레지스터

16 : 인스트럭션 메모리 18, 118 : 프리페치 큐

20, 24 : 코프로세서 22 : 공유 원격 기억장치

26, 126 : 로컬 기억장치 30 : 스레드 실행 제어장치

46 : 중재기 120 : 파이프라인형 코프로세서

본 발명은, 본 발명이 특히 각각의 인스트럭션 실행 스레드에서 독립적인 프로세스들과 관련이 있다(즉, 각각의 인스트럭션 실행 스레드는 처리중인 상이한 패킷과 관련이 있다)는 점과, 본 발명이 특히 데이터 액세스시 대기시간을 다룬다는 점에서 종래 기술과는 다르다. 스레드는 프로세서 하드웨어에 대한 액세스를 획득하도록 허용되므로, 각각의 실행 스레드는 인스트럭션의 시퀀스를 실행하는 독립적인 프로세스이다. 본 발명의 추가적인 양상은, 트리 서치 코프로세서가 파이프라인 연결되어, 다중 실행 스레드가 각기 트리 서치 파이프라인의 다른 페이즈(phases)(중첩 처리)에서 동시에 액세스를 할 수 있게 된다는 것이다. 바람직하게는, 본 발명이 어떤 스레드에서 다음으로 실행을 스위칭하는데 0 오버헤드로 다중 인스트럭션 실행 스레드를 채용한다. 스레드들은 공유 메모리에 대한 신속한 액세스 분산을 제공하도록 큐잉(queued)된다. 스레드의 큐잉(queueing)은 최상위 우선 순위의 스레드를 가능한 재빨리 장 대기시간 이벤트에 두도록 한다.

본 발명의 다른 양상은 각각의 실행 스레드마다 하나씩인 다중 인스트럭션프리페치 버퍼와 관련이 있다. 이 프리페치 버퍼는 인스트럭션 대역폭이 활성 실행 스레드에 의해 완전하게 활용되지 않는 구간(intervals) 동안에 유휴 실행 스레드를 위한 인스트럭션의 프리페치를 가능하게 한다. 이것은 새로운 실행 스레드로 제어가 스위칭될 때, 그 스레드를 위한 인스트럭션 프리페치 버퍼가 가득차도록 해서, 새로운 스레드가 실행에 이용가능한 인스트럭션의 결핍으로 인한 즉시 정지를 유발시킬 가능성을 없애도록 돕는다. 따라서, 인스트럭션 메모리에 대한 액세스 우선 순위는 현재 실행중인 스레드가 최상위 우선 순위를 수신하도록 제어되는 반면, 현재 스레드가 정지하면 제어를 갖도록 위치된 실행 스레드에는 두 번째 우선 순위가 제공된다. 마찬 가지로, 실행 큐의 최하위의 실행 스레드에는 인스트럭션 페치 액세스의 마지막 우선 순위가 제공된다.

본 발명의 추가 양상은 스레드 제어 상태 머신에 관한 것인데, 이 스레드 제어 상태 머신은 현재의 활성 실행 스레드를 결정하고, 활성 스레드의 실행이 장 대기시간 이벤트(즉, 트리 서치)로 인해 정지될 때에는, 다음 스레드에 대한 전 제어를 승인하고, 또는 실행이 단 대기시간 이벤트(즉, 로컬 데이터 기억장치에서의 코프로세서 활동이나 인스트럭션 페치 대기시간)로 인해 정지될 때에는, 다음 스레드에 대한 일시 제어를 승인한다. 만약 다른 스레드에 대해 일시 제어가 승인되면, 원 스레드(original thread)에 대한 차단이 해제되는 즉시, 제어는 원 스레드로 복귀된다. 대조적으로, 다른 스레드에 대해 전 제어가 승인되면, 다른 스레드는 차단될 때까지 계속 제어 상태로 남는다. 이것은 단 대기시간 이벤트를 위해서 사이클을 소모하는 것을 막아주면서 주 실행 스레드(primary execution thread)가 장대기시간 이벤트에 곧장 도달하도록 해준다. 그렇지 않으면, 다중 실행 스레드가 장 대기시간 이벤트에 도달은 하겠지만 어떤 스레드의 CPU 실행을 다른 스레드의 트리 서치와 중첩하는 이점은 축소될 것이다.

도 1은 하나의 스레드 중앙 처리 장치(CPU)(10)와, 이 CPU와 양방향 통신하는 단일 레지스터 어레이로 구현된 다수의 범용 레지스터(12)를 포함하는 전형적인 네트워크 프로세서 구성을 도시한다. 인스트럭션들은 CPU에 접속된 단일 프리페치 큐(18)와 인스트럭션 메모리(16) 사이에 전송된다. 제 1 코프로세서(20)는 CPU(10)와 통신하고, 원격 기억장치(22)에 있는 데이터를 액세스한다. 이 원격 기억장치는 코프로세서(20)를 통해 다수의 다른 프로세서(도시안됨)와 데이터를 공유할 수 있다. 로컬 데이터 기억장치(26)는 코프로세서(24)에 의해 배타적으로 이용되며, 다른 프로세서들과 공유되지 않는다. 다중 스레드의 경우, 모든 스레드들은 로컬 데이터 기억장치에 대한 액세스를 갖는다.

이제 도 2를 살펴보면, 도 1과 동일한 구성 요소는 동일한 도면 부호를 이용해 언급하며, 도 2는 다중 실행 스레드를 갖도록 구성된 CPU(110)를 도시하고 있다. 인스트럭션들은 CPU(110)에 접속된 프리페치 큐(118)와 인스트럭션 메모리(16) 사이에서 전송된다. 각각의 독립적인 실행 스레드마다 하나의 프리페치 큐가 이용된다. 다수의 범용 레지스터(112)는 CPU를 위해 일하는 단일의 레지스터 어레이로 구현된다. 이 어레이는 레지스터 어레이의 어떤 부분이 스레드에 의해 이용되는지를 결정하는 스레드 실행 제어장치(TEC)(30)에 의해 제어를 받는 하나의 어드레스 비트를 갖는다. 나머지 어드레스 비트(들)는 CPU에 의해 제어된다. 바람직한 실시예에서, 로컬 기억장치(126)는 각각의 스레드가 로컬 기억장치내에 자신의 논리적인 전용 공간(logical private space)을 갖도록 세그먼트화된다. 예를 들면, 두 개의 스레드는 각각 공간의 1/2씩을 공유할 수 있고, 네 개의 스레드는 각각 논리 기억 공간의 1/4씩을 가질 수 있다. TEC(30)는 또한 논리 데이터 기억장치(126)의 어떤 세그먼트가 어떤 스레드에 이용될 것인지를 결정한다. 데이터는 논리 데이터 기억장치(126)와 CPU(110) 사이에 직접 교환될 수 있다. 로컬 데이터 기억장치는 범용 레지스터 어레이 내부의 인덱스 레지스터에 의해 식별되는 작업 영역과 함께 CPU에 의해 완전히 어드레스 지정 가능하다. 제 1 코프로세서(120)는 CPU(110)와 공유 원격 기억장치(22) 사이에 파이프라인 연결된다. 제 2 코프로세서(24)는 로컬 데이터 기억장치(126)를 액세스하고 CPU(110)와 통신한다.

도 2를 참조하면, CPU는 비록 이것이 다중 스레드를 지원하더라도 도 1의 단일 스레드형 CPU와 사실상 다르지 않다. 다중 스레드를 지원하기 위해 필요한 주요 차이점은 스레드 실행 제어장치(TEC)(30)의 기능에서 발견된다. TEC 내부의 제어 로직은 현재 실행 스레드를 항상 감시하고, 만약 현재 스레드가 정지하면, 제어 로직은 다른 실행 스레드로 제어를 스위칭한다. 또한, 제어 로직은 활성 실행 스레드를 정지시키는 이벤트의 성질을 식별하고, 이벤트의 길이에 따라 일시 혹은 전 제어중 하나로 이행한다.

도 3은 FIFO(52)와, 중재기(46)와, 다수의 스레드 제어장치 #0 내지 #N을 포함하는 스레드 실행 제어장치(TEC)(30)를 도시한다. 각각의 스레드 제어장치는 스레드 제어 상태 머신(38)을 포함한다. 상태 머신(38)과 다른 제어장치도 본 발명의 요지를 벗어나지 않으면서 이용될 수 있다.

스레드 실행 제어장치는 다음과 같은 방식으로 동작한다. 컴퓨터가 먼저 파워-업되면, 각각의 스레드는 초기 상태(40)에 있다. 패킷(42)이 프로세서에 디스페치되면, 대응하는 스레드는 실행을 위해 사이클을 요구하기 시작하는 준비 상태(44)로 이동된다.

중재기(46)는 스레드에 대해 실행 사이클을 승인하는 장치이다. 만약 사이클이 승인되면, 스레드는 준비 상태(44)에서 실행 상태(48)로 이동한다. 실행 상태에서, 스레드는 대기시간 이벤트로 인해 실행이 정지되거나 혹은 처리중인 패킷이 큐잉되어 해당 패킷에 대한 코드 작업이 완료됨을 의미할 때까지 요구를 계속한다. 만약 사이클이 더이상 승인되지 않으면, 이것은 다른 스레드가 제어 상태에 있음을 의미한다. 이것이 중재기(46)가 스레드 제어 상태 머신(38)에 대해 사이클을 승인하지 않는 유일한 이유다. 그러나 이 두 상태중 하나(준비 혹은 실행)에서, 패킷 처리의 종료에 도달하여 다음 패킷(42)이 중재기에 디스페치되기 위해 큐될 때까지 스레드는 대기시간 이벤트를 위해 중단하는 새로운 실행 사이클을 계속해서 요구할 것이다. 다음, 시스템은 초기상태로 되돌아가서 다음 패킷(42)을 대기한다.

대기 상태(50)는 장 혹은 단 대기시간 이벤트를 다룬다. 어떤 이벤트가 발생했느냐와 무관하게, 프로세서는 정지하고, 활성 스레드는 대기 상태로 디폴트된다. 다음, 스레드는 대기시간 이벤트가 완료될 때까지 실행 사이클 요구를 그만둔다.

스레드를 초기 상태(40)에서 준비 상태(44)로 이동시키는 것과 동일한 디스페치 행위가 제 1 패킷이 디스페치되는 스레드가 최상위 우선 순위 스레드 P_A로 되도록 스레드 번호를 FIFO(52)에 입력하는 것이다. 이후의 디스페치 행위는 FIFO에 추가의 스레드 번호를 공급한다. FIFO의 최상위 우선 순위 위치의 스레드 번호는 장 대기시간 이벤트와 대면할 때까지 그 위치에 머무를 것이며, 그 후에 이 스레드는 FIFO의 처음으로 순환하여 되돌아가서 최상위 우선 순위 P_A에서 최하위 우선 순위 스레드 P_X로 된다. 단 대기시간 이벤트는 스레드가 FIFO내에서 자신의 우선 순위를 잃어버리지 않도록 할 것이다.

만약 스레드가 패킷(42)의 처리로 완료되면, 이 패킷은 출력 포트로의 전송을 위해 큐잉되고, 스레드 제어 상태 머신은 실행 상태에서 초기 상태로 천이하고, 스레드 번호는 FIFO(52)에서 제거된다.

새로운 패킷이 고 레벨 콘트롤러(도시안됨)로부터 디스페치된다. 프로세서 외부의 이 콘트롤러는 각 패킷을 취급할 스레드와 프로세서를 결정하고, 이 결정으로 FIFO(52)에는 입력 코맨드가 제공된다. 또한 상태 머신(38)에도 초기 상태에서 준비 상태로 이동하라고 머신에게 지시하는 입력이 제공된다. 외부 콘트롤러로부터의 이 커맨드에 따라 어떤 패킷이 디스페치될 것인지에 대한 스레드 번호가 콘트롤러에서 FIFO로 보내진다. 4개의 스레드를 이용할 때를 예로 들면, 2비트 이진 코드(00;01;10 혹은 11)가 디스페치되고 있는 패킷을 다룰 스레드를 식별한다. 만약 시스템이 2개의 스레드를 이용한다면, 이들은 단일 비트 이진 코드(0 또는 1)에 의해 식별된다.

만약 모든 스레드가 활성이면, 각 스레드에 대해 다중 출력이 FIFO로부터 중재기로 보내진다. 이러한 출력들중 두 개가 도시되어 있는데, 도면 부호(60)은 최상위 우선 순위 스레드 P_A에 대한 것이고, 도면 부호(62)는 최하위 우선 순위 스레드 P_X에 대한 것이다. 두 개의 스레드의 경우, P_A=P_X이고, 두 개의 출력이 존재한다. 4개의 스레드인 경우에는, P_X=P_D이고, 4개의 출력을 초래한다. 대부분의 시스템은 2의 배수(multiples)로 스레드를 다룬다. 그러나 3이나 다른 수를 이용하는 것도 가능하다.

전술한 바와 같이, 4개의 스레드로 되는 것이 성능에 있어서 어떤 이득을 만들어내지만, 추가의 하드웨어를 필요로 하며 그에 따라 비용도 비싸진다. 4개의 스레드는 다른 설계 파라미터를 의미한다. 그러나, 본 발명의 바람직한 실시예는 2개의 스레드를 활용한다. 2개의 스레드를 이용할 것인지 혹은 4개의 스레드를 이용할 것인지에 대한 결정에는 다수의 요인이 존재한다. 한가지 요인으로서, 로컬 기억장치의 사이즈를 들 수 있다. 기억장치의 용량이 작을수록, 4개의 스레드를 이용하기 위해서는 훨씬 더 많은 논리가 필요하다. 또한 코드 실행 경로의 길이에 비해 대기시간 이벤트를 얼마나 길게 할 것인지에 관한 문제도 요인이 될 수 있다.

스레드 실행 제어장치로 실행 사이클을 특정 스레드에게 인증하는 것은 다음의 불 수식을 기초로 하는 중재기의 논리 함수에 근거한다.

이 수학식은 상태 머신(38)으로부터 보내진 요구(R)가 있을 때 승인 신호(G)를 활성화시킬 것인지의 여부를 중재기가 어떻게 결정하는지에 대한 일반화된 수학식이다. 이 식에서, G_n은 얼마나 많은 스레드가 존재하느냐에 따라서 G₀, G₁등이 될 수 있다. 스레드에게 주어지는 우선 순위는 (P)로 표시된다. 이 식은 2개의 스레드인 경우 2개의 항목으로 줄어들고, 4개의 스레드인 경우에는 4개의 항목으로 늘어난다.

요구가 R₀와 G₀에 대한 커맨드인 경우에는 승인에 대해 다수의 요소가 존재한다. R₀를 살펴보면, 이것은 시스템이 승인 G₀을 발행하는 것을 고려하기 전에 활성으로 되어야 한다. 다음, 시스템은 요구가 활성인 것을 가정하고 승인을 실행할 것인지 결정하기 위해 다수의 방법을 조사한다. 만약 스레드가 최상위 우선 순위이라면, 다른 스레드들중 어떤 것이 진행중인지를 조사할 필요가 없다. 중재기는 그 스레드 번호에 대해 즉시 승인을 신호하여 실행을 허용한다. 그렇지 않을 경우에는, 스레드 번호 P_A로 시스템은 그 스레드에 대한 요구 번호 R_PA를 찾는데, 이것은 최고 우선 순위를 갖는 요구이다. 만약 최고 우선 순위를 갖는 요구가 활성이 아니면, 두 번째로 높은 우선 순위를 갖는 요구(R_PB)를 조사하여, 이것을 시스템이 관심을 갖고 있는 스레드(P_B)와 비교한다. 이 스레드 번호는 1비트(2개의 스레드인경우)로 표현되거나 2비트(4개의 스레드인 경우)로 표현된다. 2개의 스레드가 존재하는 경우에는 이 식이 2개의 항목으로 끝나고, 4개의 스레드가 존재하는 경우에는 이 식은 4개의 항목으로 끝난다.

도 4를 참조하면, 동 도면에는 일반적으로 트리 서치와 CPU 실행의 중첩(overlap)을 2개의 스레드 파형상에서 보여주는 2개의 트리 서치 스레드와 관련한 2개의 타이밍도가 도시되어 있다. 파형이 낮을 때에는 CPU가 실행중이다. 파형이 높을 때에는 CPU가 트리 서치를 위해 대기중이다. 2개의 스레드에 대해 타이밍도의 파형을 비교할 때 이들 파형이 동시에 낮아질 수는 없음을 유의하자. 이 둘은 동일한 CPU를 공유하고 있으므로, 이들이 동시에 CPU 사이클을 실행중일 수는 없다는 것을 직관적으로 알 수 있다. 한편, 트리 서치 엔진의 파이프라인 연결로 인해, 이들은 다양한 트리 서치 중첩 단계를 동시에 할 수 있다.

실행을 정지시킬 수 있는 두 가지 유형의 이벤트가 기본적으로 존재하는데, 이들은 단시간 인터럽션(short interruption)을 초래하는 것과 현재 프로그램 흐름의 연장 인터럽션(extended interruption)을 초래하는 것이다. 단시간 인터럽션은 프로그램 흐름의 변화로 인해 다시 채워질 인스트럭션 프리페치 큐를 필요로하는 브랜치 인스트럭션(branch instruction)에 의해 초래될 수도 있다. 선택적으로, 코프로세서가 프로세서의 로컬 메모리내의 데이터와 관련한 태스크를 수행하기 위해 대기하는 동안에 프로그램은 정지할 수도 있다. 이 일예로서, 수정된 헤더 필드상에서 새로운 체크섬(checksum)을 계산하는 체크섬 코프로세서의 경우를 들 수 있다. 대기시간이 25 프로세서 사이클 미만이면 이 이벤트는 단시간 인터럽션으로간주된다. 장 대기시간 이벤트들은 전형적으로 그 대기시간이 25를 초과하는데, 흔히 50~100 프로세서 사이클이다. 이들은 전체 성능에 훨씬 큰 영향을 미친다.

장 대기시간 이벤트인지 혹은 단 대기시간 이벤트인지를 결정하는 것으로 다양한 다른 수단이 존재한다. 대기시간의 길이는 프로그래머의 제어하에 있을 수 있으므로, 하드웨어나 혹은 그 구성은 결정에 있어서 요인이 아니다. 한편, 임계치 레지스터는 25 사이클 임계치로 설정될 수 있으며, 하드웨어는 동작에 얼마만큼의 사이클이 요구되는지를 결정하고, 그 결정에 따라 자동 판정을 수행할 것이다.

코프로세서 인스트럭션은 프로세서가 실행하는 인스트럭션의 한 유형이다. 필드내의 몇몇 비트들은 어떤 코프로세서가 의도되고 있는지를 식별한다. 어떤 한 비트는 특별한 인스트럭션을 장 대기시간 이벤트 혹은 단 대기시간 이벤트로 정의한다. 따라서 프로그래머가 제어 메모리에 대해 두 개의 동일한 액세스를 정의할 수 있게 되는데, 하나는 장 대기시간 이벤트로, 다른 하나는 단 대기시간 이벤트로 정의할 수 있다. 스레드 실행 제어 기능은 이러한 장 대기시간 이벤트의 영향을 최소화시키도록 설계된다. 따라서, 장 대기시간 이벤트는 다른 실행 스레드로 스위칭시키는 전 제어를 초래하는 반면, 단 대기시간 이벤트는 다른 스레드로 일시 스위칭시키기만 할 것이다.

다중 스레드 CPU가 사실상 단일 스레드형 CPU로서 동일한 것이더라도, 다수의 주변 기능들이 각각의 실행 스레드에 대해 복제된다. 범용 레지스터와 로컬 데이터 기억장치는 도 2에 예시된 것처럼 둘 다 각각의 인스트럭션 스레드에 대해 복제된다. 이것은 (프로세서 시이클의 견지에서) 0 오버헤드로 완전한 콘텍스트 스위칭을 허용한다. 바람직한 실시예에서, 범용 레지스터의 다중 세트는 사실상 단일의 큰 레지스터 어레이로 구현되는데, 하나(스레드의 수가 2를 초과하면, 하나 이상이 됨)의 어드래스 비트가 스레드 실행 제어 로직에 의해 제어되고, 다른 어드레스 비트들은 실행중인 인스트럭션에 따라 CPU에 의해 제어된다.

선택적으로, 두 개의 레지스터 어레이가 CPU에 의해 동시에 어드레스 지정될 수 있고, 스래드 실행 제어 로직은 어레이 선택이나, CPU로 전송될 어레이 출력을 결정하는 멀티플렉서 회로를 제어할 수 있다. 단일의 큰 메모리 어레이를 이용함으로써, 각각의 실행 스레드는 로컬 데이터 기억장치내의 완전히 독립적인 작업 영역에 제공될 수도 있는데, 하나(스레드 번호가 2를 초과하면 하나 이상이 됨)의 어드레스 비트는 스레드 실행 제어 로직에 의해 제어되고, 다른 어드레스 비트들은 실행중인 인스트럭션에 따라 CPU에 의해 제어된다. 선택적으로, 로컬 데이터 기억장치는 CPU에 의해 완전히 어드레스 지정가능하며, 각각의 작업 영역은 범용 레지스터 어레이 내부의 인덱스 레지스터에 의해 식별된다. 이것은 예컨대 테이블같은 몇몇 공용의 공유 메모리가 가능해지는 이점을 갖지만, 전용 공간에 대한 모든 액세스는 인덱스 어드레스 모드로 행해지는 것이 필요하여, 이용 가능한 인스트럭션의 융통성을 제한할 수도 있다.

비록 인스트럭션 메모리에 대한 공통 경로가 존재하더라도, 각각의 인스트럭션 스레드는 다른 인스트럭션 포인터 및 인스트럭션 프리페치 큐와 연관되고, 이들 각각은 장래의 실행을 위해 진입된 다중 인스트럭션 워드를 포함할 수도 있다. 바람직한 실시예에서, 두 개의 실행 스레드가 존재한는데, 이들 각각은 8-인스트럭션프리페치 큐를 갖는다. 활성 실행 스레드는 인스트럭션을 페칭하기 위해 제 1 우선 순위로 제공된다. 바람직한 실시예에서, 다중 네트워크 프로세서는 동일한 칩상에서 구현되어 공용 인스트럭션 기억장치를 공유한다. 따라서, 만약 다중 프로세서가 동시에 인스트럭션 메모리로의 액세스를 요구하면, 유휴 스레드로부터의 요구가 먼저 있을지라도, 활성 스레드와 관련한 인스트럭션 페치 요구가 항상 유휴 스레드와 관련한 것보다 우선적으로 제공될 것이다.

작업중인 레지스터와 로컬 기억장치가 각각의 인스트럭션 스레드에 대해 복제되더라도, 모든 스레드는 공용 CPU(그 코프로세서도 포함)와 인스트럭션 메모리로에 대한 경로를 공유함을 유의하자. 인스트럭션 페칭에 대한 피크 대역폭 요구는 증가하지 않지만, 인스트럭션 페칭과 관련한 이용 가능한 대역폭의 효율적인 활용은 다중 실행 스레드로 상당히 증가된다.

네트워크 처리 시스템에서 요구되는 전형적인 처리는 서치 설정과 그 결과의 처리에 필요한 머신 사이클의 수가 2배 혹은 3배인 트리 서치 액세스를 초래한다. 이것은 중요한 2가지를 의미한다. 첫 째, 두 개의 스레드의 각각과 관련한 CPU 실행이 다른 스레드와 관련한 트리 서치 사이클과 쉽게 중첩될 수 있다. 사실상, 단 두 개의 스레드이면, 두 스레드가 모두가 정지되는 CPU 사이클은 여전히 상당한 수 이지만, 3 혹은 4개의 스레드가 되면, CPU의 활용은 더 더욱 개선될 것이다. 하나에서 두 개로 스레드를 배가하는 것은 반드시 CPU 활용을 배가시키지만, 적어도 본 발명의 바람직한 실시예의 구조에서는, 거기에 다시 스레드 번호를 배가한다고 해서 CPU 활용의 효율이 4배가 되는 것은 아니다. 이것은 4개의 스레드일 경우라도트리 서치 대기시간이 다른 세 개의 스레드가 실행되는 것을 보장할 정도로 길지 않기 때문이다. 바람직한 실시예는 2개의 스레드로 제한되는데, 그 이유는 추가 스레드에 대한 추가 비용(즉, 더 큰 로컬 데이터 기억장치와 범용 레지스터 어레이)이 CPU를 복제하지 않음으로써 절약되는 비용보다 훨씬 더 많기 때문이다. 따라서, 스레드를 배가하는 것이 그에 상응하는 처리력의 배가를 초래하더라도, 스레드의 수를 배가하는 것이 그 처리력을 배가시키지 않고 그에 약간 못미치는 정도로만 증가시킬 때(예를 들면, 1.5배)에는, 추가의 독립적인 CPU를 부가하는 것이 바람직함을 알 수 있다. 얼마나 많은 스레드가 바람직한지에 대한 결정은 당업자의 능력에 따른 것으로, 고려중인 처리 시스템과 관련한 CPU 클록 사이클과 트리 서치 클록 사이클 간의 상대적인 차이에 의존하며, 더불어 코어 CPU의 구현 비용 대 범용 레지스터 및 로컬 데이터 기억장치의 복제 비용에 의존한다.

CPU 실행과 트리 서치 간에 머신 사이클을 분배하는 것의 두 번째 의미는, 만약 다음 것이 시작될 수 있기 전에 인터리빙이 하나의 트리 서치를 종료하려는 요구로 구현되는 경우에는, 두 인스트럭션 스레드의 중첩이 효율적이지 못할 것이라는 것이다. 각각의 패킷 처리는 실제로, 트리 서치가 CPU에 의해 개시되기는 했지만 다른 스레드로부터의 트리 서치가 종료되기를 기다리며 정지되는 다양한 사례들로 인해 연장될 것이다. 이러한 불리한 조건을 피하기 위해, 트리 서치 코프로세서는 다수의 파이프라인형 페이즈를 포함하도록 수정된다. 따라서, 어떤 스레드로부터의 트리 서치는 다른 스레드의 트리 서치가 종료하기를 기다릴 필요없이, 이 다른 스레드의 트리 서치가 그 파이프라인의 두 번째 페이즈로 진행하기만 기다리면 된다. 실제로, 두 번째 스레드가 트리 서치를 설정하는 인스트럭션을 실행 완료하는 시간까지, 다른 스레드로부터의 이전의 트리 서치는 아마도 그 첫 번째 파이프라인 페이즈를 지나고 있을 것이고, 그 결과 트리 서치 처리에서의 정지를 완벽하게 피할 수 있게 된다. 이것은 당연히 동일한 파이프라인 페이즈를 경쟁하는 두 개의 다른 스레드로부터의 트리 서치를 실행하지 않도록 하기 위해 전술한 단 대기시간 이벤트상에서 일시적으로 스레드를 스위칭시키는 것에 대한 추가적인 동기이기도 하다.

다른 해결법은 더 많은 단일 스레드형 CPU를 복제하는 것이다. 이 방법의 단점은 동일한 정도의 성능을 달성하기 위해 비용이 더 많이 든다는 것이다. 또한 이것은 다양한 버스(즉, 인스트럭션 메모리 혹은 공유 원격 기억장치)에 대한 피크 대역폭 요구를 증가시킨다. 다중 스레드는 동일한 평균 대역폭을 초래하지만, 이들 공유 자원에 대한 경쟁으로 인해 성능에 중요한 부차적인 영향을 미칠 수 있는 피크 대역폭의 반감(2개의 스레드인 경우)을 초래한다.

본 발명은 네트워크 프로세서와 트리 서치 구조를 이용하는 것과 연계하여 설명되었다. 그러나, 본 발명은 트리 서치 엔진이 아닌 소스로부터 데이터를 검색하는 다른 프로세서 시스템과도 유용함을 유의해야 한다. 예를 들면, 스레드 실행 제어는 다른 코프로세서를 액세스하는데도 이용될 수 있다.

본 발명이 그 실시예로 설명되었을지라도, 당업자에게는 전술한 요지의 관점에서 많은 대체물, 수정물 및 변형물들이 명백할 것임이 자명하다. 따라서, 본 발명은 이러한 모든 대체물, 수정물 및 변형물들을 첨부된 특허청구범위의 사상과 범주내에 있는 것으로 포함하도록 의도되었다.

따라서, 본 발명에 따르면, 트리 구조(tree structures)로 포맷된 데이터를 액세스함에 있어서 대기시간(latency)의 영향이 최소화되고, 프로세서 자원이 보다 효율적으로 활용된다.

Claims

프로세서(a processor) 및 액세스 가능 데이터와 연관되어 다중 스레드(multiple threads)를 이용하는 방법에 있어서,

다중 인스트럭션 실행 스레드를 순차 시간 프레임(sequential time frame)으로 독립적인 프로세스로서 제공하는 단계와,

상기 액세스 가능 데이터에 대한 중첩(overlapping) 액세스를 하도록 상기 다중 실행 스레드를 큐잉(queueing)하는 단계와,

큐(queue)에서 제 1 스레드를 실행하는 단계와,

상기 제 1 스레드의 실행을 정지시키는 이벤트(event)의 출현시, 실행의 제어(control of the execution)를 상기 큐내의 다음 스레드로 양도(transferring)하는 단계를 포함하는

다중 스레드 이용 방법.
제 1 항에 있어서,

상기 실행의 제어는 실행이 단 대기시간 이벤트(a short latency event)로 인해 정지되었을 때에는 상기 다음 스레드로 일시적으로 양도되었다가, 상기 이벤트가 종료되면, 상기 제어는 원래의 스레드로 복귀되는 다중 스레드 이용 방법.
제 2 항에 있어서,

프로세서 인스트럭션(processor instruction)이 단 대기시간 이벤트를 선택하도록 엔코드되는 다중 스레드 이용 방법.
제 1 항에 있어서,

상기 제 1 스레드의 실행이 장 대기시간 이벤트(a long latency event)로 인해 정지될 때에는 실행의 전 제어(full control of the execution)가 상기 다음 스레드로 양도되는 다중 스레드 이용 방법.
제 4 항에 있어서,

프로세서 인스트럭션이 장 대기시간 이벤트를 선택하도록 엔코드되는 다중 스레드 이용 방법.
제 1 항에 있어서,

공유 메모리에 대한 액세스의 신속한 배분을 제공하기 위해 상기 스레드를 큐잉하는 단계를 더 포함하는 다중 스레드 이용 방법.
제 1 항에 있어서,

각각의 실행 스레드에 대해 개별의 인스트럭션 프리페치 버퍼를 제공하고, 상기 스레드가 유휴(idle)이고 인스트럭션 대역폭이 완전히 활용되고 있지 않을 때, 인스트럭션을 해당 실행 스레드와 관련한 프리페치 버퍼에 수집하는 단계를 더 포함하는 다중 스레드 이용 방법.
제 1 항에 있어서,

상기 스레드는 하나의 스레드에서 다른 스레드로 실행을 스위칭(switch)하는데 0 오버헤드(overhead)로 이용되는 다중 스레드 이용 방법.
제 8 항에 있어서,

0 오버헤드로 스위칭을 가능하게 하기 위해 각각의 스레드는 범용 레지스터 및 로컬 데이터 기억장치에 액세스하도록 제공되는 다중 스레드 이용 방법.
데이터를 액세스하는데 다중 스레드를 이용하는 처리 시스템에 있어서,

순차 시간 프레임(sequential time frame)에서 독립적인 프로세스인 다중 인스트럭션 실행 스레드로 구성된 CPU와,

액세스 가능 데이터에 대한 중첩 액세스를 하도록 상기 다중 실행 스레드를 큐잉하고, 큐에서 제 1 스레드를 실행하며, 상기 제 1 스레드의 실행을 정지시키는 이벤트의 출현시에는, 실행의 제어를 상기 큐내의 다음 스레드로 양도하는 스레드 실행 제어 장치(thread execution control)를 포함하는

처리 시스템.
제 10 항에 있어서,

상기 스레드 실행 제어 장치는,

실행이 단 대기시간 이벤트로 인해 정지되었을 때에는 제어를 상기 다음 스레드로 일시적으로 양도했다가, 상기 단 대기시간 이벤트가 종료되면, 제어를 원래의 스레드로 복귀시키는 제어 로직(control logic)을 포함하는 처리 시스템.
제 10 항에 있어서,

프로세서 인스트럭션이 단 대기시간 이벤트를 선택하도록 엔코드되는 처리 시스템.
제 10 항에 있어서,

상기 제어 양도는 상기 제 1 스레드의 실행이 장 대기시간 이벤트로 인해 정지될 때에 실행의 전 제어(full control)를 상기 다음 스레드로 양도하는 것을 포함하는 처리 시스템.
제 13 항에 있어서,

프로세서 인스트럭션이 장 대기시간 이벤트를 선택하도록 엔코드되는 처리 시스템.
제 10 항에 있어서,

각각의 실행 스레드를 위한 개별적 인스트럭션 프리페치 버퍼와, 인스트럭션 대역폭이 완전히 활용되고 있지 않을 때 유휴 인스트럭션 스레드와 관련해 프리페치 버퍼에 인스트럭션을 수집하는 수단을 더 포함하는 처리 시스템.
제 10 항에 있어서,

상기 프로세서는 네트워크 프로세서인 처리 시스템.
제 10 항에 있어서,

상기 프로세서는 하나의 스레드에서 다른 스레드로 실행을 스위칭하는데 0 오버헤드를 이용하는 처리 시스템.
제 17 항에 있어서,

0 오버헤드로 스위칭을 가능하게 하기 위해 각각의 스레드는 범용 레지스터의 어레이 및 로컬 데이터 기억장치에 액세스하도록 제공되는 처리 시스템.
제 18 항에 있어서,

상기 범용 레지스터 및 상기 로컬 데이터 기억장치는, 상기 스레드 실행 제어 로직의 제어하에 하나의 어드레스 비트를 제공하고 상기 프로세서의 제어하에 나머지 어드레스 비트를 제공함으로써, 상기 프로세서에 대해 이용 가능하게 되는 처리 시스템.
제 18 항에 있어서,

상기 프로세서는 다중 레지스터 어레이를 동시에 어드레스 지정하는 것이 가능하고, 상기 스레드 실행 제어 로직은 주어진 스레드와 관련해 어떤 어레이가 상기 프로세서로 보내질 것인지 선택하는 선택기(selector)를 더 포함하는 처리 시스템.
제 18 항에 있어서,

상기 로컬 데이터 기억장치는 상기 프로세서에 의해 완전히 어드레스 지정 가능하고, 상기 레지스터 어레이 내부에는 인덱스 레지스터(index register)가 포함되며, 상기 스레드 실행 제어 장치는 상기 로컬 데이터 기억장치나 상기 레지스터 어레이에 대해 어드레스 제어를 하지 않는 처리 시스템.
스레드 실행 제어 장치에 있어서,

소정 대기시간 이벤트가 제 1 스레드의 실행을 정지시킬 때, 상기 제 1 스레드에서 제 2 스레드로 실행의 제어를 양도하는 스레드 제어 상태 머신(thread control state machine)을 포함하되, 상기 제어 양도는 상기 대기시간 이벤트가 단 대기시간 정지(a short latency stall)를 초래할 경우에는 일시적인 제어를 위한 것이고, 상기 대기시간 이벤트가 장 대기시간 정지(a long latency stall)를 초래할 경우에는 전 제어(full control)를 위한 것인

스레드 실행 제어 장치.
제 22 항에 있어서,

상기 단 대기시간 이벤트가 종료되면 상기 제 1 스레드로 제어를 복귀시키는 수단을 더 포함하는 스레드 실행 제어 장치.
제 22 항에 있어서,

전 제어가 상기 제 2 스레드로 양도된 이후에, 상기 제 2 스레드가 대기시간 이벤트를 초래할 때까지, 상기 제 2 스레드에 의해 제어가 유지되도록 하는 수단을 더 포함하는 스레드 실행 제어 장치.
프로세서에서 다중 독립 스레드의 실행 방법에 있어서,

우선 순위 FIFO를 이용하여, 다수의 스레드중 하나에 대해 우선 순위를 부여하는 단계와,

중재기(arbiter)를 이용하여, 상기 우선 순위가 부여된 스레드의 실행을 제어하는 단계와,

대기시간 이벤트의 출현시, 스레드간에 실행 제어를 시프팅(shifting)하는 스레드 제어 상태 머신(thread control state machine)을 이용하는 단계를 포함하는

다중 독립 스레드 실행 방법.
제 25 항에 있어서,

상기 FIFO를 이용해 스레드 우선 순위를 부여하는 단계는,

태스크가 상기 프로세서에 디스페치될 때, 스레드 번호를 FIFO에 적재(loading)하는 단계와,

태스크가 완료될 때, 상기 FIFO로부터 스레드 번호를 적재해제하는(unloading) 단계와,

장 대기시간 이벤트가 발생시, 상기 FIFO에서 최상위 우선 순위에서 최하위 우선 순위로 스레드 번호를 순환(circulating)시키는 단계와,

상기 FIFO의 스레드 출구(outlets)를 이용하여, 스레드가 상기 FIFO내에 존재한 시간 길이에 따라 우선 순위를 결정하는 단계를 포함하는

다중 독립 스레드 실행 방법.
제 25 항에 있어서,

상기 다중 독립 스레드의 실행의 우선 순위를 제어하는 단계는,

다음의 불 수식(Boolean expression)

에 따른 상기 중재기의 논리 함수에 근거하여 이루어지되(단, G는 승인이고, R_n은 주어진 스레드로부터의 요구이며, P_A, P_B, P_C는 우선 순위에 따라 알파벳순의 첨자로 정렬된 스레드를 나타내며, n은 비트 혹은 2진수로 스레드를 식별(identifying)하는 첨자임),

요구 R이 활성인지 혹은 비활성인지을 결정하는 단계와,

상기 스레드 P의 상기 우선 순위를 결정하는 단계와,

상기 요구를 대응하는 스레드 P와 매칭시키는 단계와,

상기 요구가 활성이고 상기 대응하는 스레드 P가 최상위 우선 순위를 가질 경우에, 실행에 대한 요구를 승인하는 단계를 포함하는

다중 독립 스레드 실행 방법.
제 25 항에 있어서,

상기 스레드 제어 상태 머신(thread control state machine)을 이용하는 단계는,

태스크를 스레드에 디스페치하는 단계와,

초기 상태에서 준비 상태로 상기 스레드를 이동시키는 단계와,

상기 태스크를 위한 실행 사이클을 요구하는 단계와,

상기 실행 사이클의 상기 중재기에 의한 승인시, 상기 스레드를 실행상태로 이동시키는 단계와,

상기 태스크가 상기 실행 상태에 큐잉된 동안에는 실행 사이클을 계속 요구하는 단계와,

대기시간 이벤트가 존재하지 않을 경우에는 상기 스레드를 상기 초기 상태로 복귀시키고, 대기시간 이벤트의 출현시에는 상기 스레드를 대기 상태로 보내는 단계를 포함하는

다중 독립 스레드 실행 방법.
다수의 독립적인 인스트럭션 스레드와 연계하여 프리페치 버퍼를 이용하는 방법에 있어서,

각각의 스레드를 프리페치 버퍼와 연관시키는 단계와,

실행 스레드와 연관된 버퍼가 가득찼는지 결정하는 단계와,

상기 버퍼와 연관된 상기 스레드가 활성인지 결정하는 단계와,

버퍼가 활성 실행 스레드에 의해 이용되지 않는 동안에, 상기 버퍼가 상기 실행 스레드를 위한 인스트럭션을 프리페치할 수 있도록 하는 단계를 포함하는

다수의 독립적인 인스트럭션 스레드와 연계한 프리페치 버퍼 이용 방법.
스레드 실행 콘트롤러에 있어서,

우선 순위 FIFO와,

다중 스레드의 세트(a set of multiple threads)내의 각 스레드마다 하나씩인 다수의 스레드 제어 상태 머신과,

상기 FIFO 및 상기 다수의 스레드 제어 상태 머신과 동작적으로 접속되어, 상기 다수의 스레드 사이에 스레드 실행 우선 순위를 결정하는 중재기를 포함하는

스레드 실행 콘트롤러.
제 30 항에 있어서,

상기 FIFO는,

태스크가 프로세서에 디스페치될 때, 스레드 번호를 FIFO에 적재하는 수단과,

태스크가 종료될 때, FIFO로부터 스레드 번호를 적재해제하는 수단과,

장 대기시간 이벤트가 발생할 때, 스레드 번호를 FIFO에서 최상위 우선 순위로부터 최하위 우선 순위로 이동시키는 수단과,

스레드가 FIFO에 존재한 시간 길이에 따라 우선 순위를 결정하는데 이용되는 FIFO의 스레드 출구를 포함하는

스레드 실행 콘트롤러.
제 30 항에 있어서,

상기 중재기는 다음의 불 수식(Boolean expression)

에 따라 다중 독립 스레드의 실행의 우선 순위를 제어하되(단, G는 승인이고, R_n은 주어진 스레드로부터의 요구이며, P_A, P_B, P_C는 우선 순위에 따라 알파벳순의 첨자로 정렬된 스레드를 나타내며, n은 비트 혹은 2진수로 스레드를 식별(identifying)하는 첨자임),

요구 R이 활성인지 혹은 비활성인지을 결정하고,

상기 스레드 P의 상기 우선 순위를 결정하고,

상기 요구를 대응하는 스레드 P와 매칭시키고,

상기 요구가 활성이고 상기 대응하는 스레드 P가 최상위 우선 순위일 경우에, 실행에 대한 요구를 승인하는

스레드 실행 콘트롤러.
제 30 항에 있어서,

상기 스레드 제어 상태 머신은,

태스크를 스레드에 디스패치하고, 상기 스레드를 초기 상태에서 준비 상태로이동시키며, 상기 태스크를 위한 실행 사이클을 요구하고, 실행 사이클의 상기 중재기에 의한 승인시, 상기 스레드를 실행 상태로 이동시키며, 상기 태스크가 상기 실행 상태에 큐되는 동안에 실행 사이클을 계속 요구하고, 대기시간 이벤트가 존재하지 않을 경우에는 패킷을 상기 초기 상태로 복귀시키지만, 대기시간 이벤트의 출현시에는 상기 패킷을 대기 상태로 보내는 제어 로직을 포함하는

스레드 실행 콘트롤러.