1 |
1
루프(loop)가 포함하는 명령어들 간의 의존성을 포함하는 데이터 의존성 그래프(data dependence graph)를 획득하는 데이터 의존성 그래프 획득부; 상기 데이터 의존성 그래프에서, 사이클을 형성하는 명령어들의 집합인 리커런스(recurrence)를 탐색하는 리커런스 탐색부; 및상기 리커런스의 처리 순서를 결정하는 스케줄링부를 포함하고,상기 리커런스 탐색부는 이터레이션 디스턴스(Iteration Distance)의 합이 소정의 임계값보다 작은 리커런스만을 탐색하고, 상기 이터레이션 디스턴스는 상기 리커런스에 포함된 소정의 명령어를 처리한 후 상기 소정의 명령어의 처리 결과에 의존하는 다른 명령어를 처리할 수 있을 때까지 소요되는 이터레이션 횟수인 것을 특징으로 하는 모듈로 스케줄링 장치
|
2 |
2
제1항에 있어서, 상기 리커런스 탐색부는,소스 노드(Source Node)가 S 인 경우, 상기 소스 노드 S로부터 출발하여 상기 소스 노드 S로 되돌아가는 경로인 리커런스를 탐색하고,상기 탐색을 시작하기 전에 사용 가능한 이터레이션 디스턴스인 가용 이터레이션 디스턴스(available iteration distance)를 상기 임계값으로 초기화하고,
상기 노드 S의 하나 이상의 후속 노드 방향으로 리커런스를 탐색하는 동안에, 상기 이터레이션 디스턴스를 차감해가면서 상기 가용 이터레이션 디스턴스를 갱신하고, 상기 가용 이터레이션 디스턴스가 0 보다 작아지면 탐색을 중단하는 것을 특징으로 하는 모듈로 스케줄링 장치
|
3 |
3
제2항에 있어서, 상기 리커런스 탐색부는,
상기 탐색이 중단된 경우, 방문하지 않은 후속 노드를 재귀적으로 방문하여 리커런스 탐색을 시도하는 것을 특징으로 하는 모듈로 스케줄링 장치
|
4 |
4
제2항에 있어서, 상기 리커런스 탐색부는,현재 방문 중인 노드가 V 이고, 상기 노드 V의 후속 노드가 W 이며, 상기 노드 V와 상기 후속 노드 W 사이에 존재하는 이터레이션 디스턴스가 D 인 경우,
상기 노드 W가 상기 소스 노드 S가 아니고, 상기 가용 이터레이션 디스턴스가 상기 D 보다 작거나 같으면 상기 후속 노드 W 방향으로 탐색하지 않는 것을 특징으로 하는 모듈로 스케줄링 장치
|
5 |
5
제2항에 있어서, 상기 리커런스 탐색부는,현재 방문 중인 노드가 V 이고, 상기 노드 V의 후속 노드가 W 이며, 상기 노드 V와 상기 후속 노드 W 사이에 존재하는 이터레이션 디스턴스가 D이고, 상기 노드 W 에서 상기 소스 노드 S에 도달할 수 있는 경로 상에 존재하는 이터레이션 디스턴스의 합이 A인 경우,
상기 D에 상기 A 를 더한 값보다 상기 가용 이터레이션 디스턴스가 작으면, 상기 후속 노드 W 방향으로 탐색하지 않는 것을 특징으로 하는 모듈로 스케줄링 장치
|
6 |
6
제1항에 있어서, 상기 리커런스 탐색부는,
현재 방문 중인 노드가 V이고, 상기 노드 V의 후속 노드가 W 인 경우, 상기 노드W가 소스 노드가 아니고 노드 W가 현재까지의 경로에 기 저장되어 있으면, 상기 노드W방향으로 탐색하지 않는 것을 특징으로 하는 모듈로 스케줄링 장치
|
7 |
7
제1항에 있어서, 상기 스케줄링부는,상기 탐색된 하나 이상의 리커런스를 상기 최소 시작 간격(Minimum Initiation Interval: MII)이 큰 순서대로 처리되도록 스케줄링하고,
상기 최소 시작 간격은 상기 각각의 리커런스를 반복하여 처리하기 위해 필요한 최소의 시간 간격인 것을 특징으로 하는 모듈로 스케줄링 장치
|
8 |
8
루프(loop)가 포함하는 명령어들 간의 의존성을 포함하는 데이터 의존성 그래프(dependence graph)를 획득하는 단계; 상기 데이터 의존성 그래프에서, 사이클을 형성하는 명령어들의 집합인 리커런스(recurrence)를 탐색하는 단계; 및상기 리커런스의 처리 순서를 결정하는 스케줄링 단계를 포함하고,상기 리커런스를 탐색하는 단계는 이터레이션 디스턴스(Iteration Distance)의 합이 소정의 임계값보다 작은 리커런스만을 탐색하고,
상기 이터레이션 디스턴스는 상기 리커런스에 포함된 소정의 명령어를 처리한 후 상기 소정의 명령어의 처리 결과에 의존하는 다른 명령어를 처리할 수 있을 때까지 소요되는 이터레이션 횟수인 것을 특징으로 하는 모듈로 스케줄링 방법
|
9 |
9
제8항에 있어서, 상기 리커런스를 탐색하는 단계는,소스 노드(Source Node)가 S 인 경우, 상기 소스 노드 S로부터 출발하여 상기 소스 노드 S로 되돌아가는 경로인 리커런스를 탐색하고,상기 탐색을 시작하기 전에 사용 가능한 이터레이션 디스턴스인 가용 이터레이션 디스턴스(available iteration distance)를 상기 임계값으로 초기화하고,
상기 노드 S의 하나 이상의 후속 노드 방향으로 리커런스를 탐색하는 동안에, 상기 이터레이션 디스턴스를 차감해가면서 상기 가용 이터레이션 디스턴스를 갱신하고, 상기 가용 이터레이션 디스턴스가 0 보다 작아지면 탐색을 중단하는 것을 특징으로 하는 모듈로 스케줄링 방법
|
10 |
10
제9항에 있어서, 상기 리커런스를 탐색하는 단계는,
상기 탐색이 중단된 경우, 방문하지 않은 후속 노드를 재귀적으로 방문하여 리커런스 탐색을 시도하는 단계를 더 포함하는 모듈로 스케줄링 방법
|
11 |
11
제9항에 있어서, 상기 리커런스를 탐색하는 단계는, 현재 방문 중인 노드가 V 이고, 상기 노드 V의 후속 노드가 W 이며, 상기 노드 V와 상기 후속 노드 W 사이에 존재하는 이터레이션 디스턴스가 D 인 경우,
상기 노드 W가 상기 소스 노드 S가 아니고, 상기 가용 이터레이션 디스턴스가 상기 D 보다 작거나 같으면 상기 후속 노드 W 방향으로 탐색하지 않는 것을 특징으로 하는 모듈로 스케줄링 방법
|
12 |
12
제9항에 있어서, 상기 리커런스를 탐색하는 단계는,
현재 방문 중인 노드가 V 이고, 상기 노드 V의 후속 노드가 W 이며, 상기 노드 V와 상기 후속 노드 W 사이에 존재하는 이터레이션 디스턴스가 D이고, 상기 노드 W 에서 상기 소스 노드 S에 도달할 수 있는 경로 상에 존재하는 이터레이션 디스턴스의 합이 A인 경우,
상기 D에 상기 A 를 더한 값보다 상기 가용 이터레이션 디스턴스가 작으면, 상기 후속 노드 W 방향으로 탐색하지 않는 것을 특징으로 하는 모듈로 스케줄링 방법
|
13 |
13
제8항에 있어서, 상기 리커런스 탐색하는 단계는,
현재 방문 중인 노드가 V이고, 상기 노드 V의 후속 노드가 W 인 경우, 상기 노드W가 소스 노드가 아니고 노드 W가 현재까지의 경로에 기 저장되어 있으면, 상기 노드W방향으로 탐색하지 않는 것을 특징으로 하는 모듈로 스케줄링 방법
|
14 |
14
제8항에 있어서, 상기 스케줄링 하는 단계는,
상기 탐색된 하나 이상의 리커런스를 상기 최소 시작 간격(Minimum Initiation Interval: MII)이 큰 순서대로 처리되도록 스케줄링하는 단계를 포함하고,
상기 최소 시작 간격은 상기 각각의 리커런스를 반복하여 처리하기 위해 필요한 최소의 시간 간격인 것을 특징으로 하는 모듈로 스케줄링 방법
|
15 |
15
제 8항 내지 14항 중 어느 한 항에서 수행되는 방법을 컴퓨터에서 실행시키기 위한 프로그램을 기록한 컴퓨터로 읽을 수 있는 기록매체
|