| 1 |
1
두 개의 정렬된 리스트를 합병하여 하나의 정렬된 리스트로 만드는 분할 합병 메쉬 장치에서 수행되는 분할 합병 방법에 있어서, 각 데이터가 속한 분할을 구하는 제 1 단계; 같은 분할에 속한 원소들을 같은 행으로 모으는 제 2 단계; 각 행에서 분할 별로 독립적으로 합병하는 제 3 단계; 및 합병 후 저장 위치로 이동하는 제 4 단계 를 포함하는 하는 분할 합병 메쉬 방법
|
| 2 |
2
제 1 항에 있어서, 상기 제 1 단계는, 전체 메쉬를 왼쪽 부분 메쉬(LM)와 오른쪽 부분 메쉬(RM)로 나누어 각 프로세서들이 왼쪽 부분 메쉬에 하나의 정렬된 리스트를 행우선 순서로 저장하고, 오른쪽 부분 메쉬에 다른 하나의 정렬된 리스트를 행우선 순서로 저장한 후, 1 열의 원소들을 기준으로 분할하는 것을 특징으로 하는 분할 합병 메쉬 방법
|
| 3 |
3
제 2 항에 있어서, m x 2m 개로 구성된 메쉬에서, 전체 메쉬를 m x m 의 왼쪽 부분 메쉬(LM)와 mxm 의 오른쪽 부분 메쉬(RM)로 나누고, 1 열의 원소들을 기준으로 2m 개의 분할로 나누는 것을 특징으로 하는 분할 합병 메쉬 방법
|
| 4 |
4
제 1 항에 있어서, 상기 제 2 단계는, 각 프로세서들이 분할된 1,2 번째 분할에 속하는 데이터를 1행으로, 3,4 번째 분할에 속하는 데이터를 2 행으로, 2i-1, 2i 번째 분할에 속하는 데이터는 i 행으로 이동시킴으로써 같은 분할에 속한 데이터들을 같은 행으로 이동시키는 것을 특징으로 하는 분할 합병 메쉬 방법
|
| 5 |
5
제 1 항에 있어서, 상기 제 3 단계는, 각 프로세서들이 이동된 i 행의 2i-1 번째 분할에 속하는 원소들을 합병하고, 2i 번째 분할에 속하는 원소들을 합병하여 하나의 행에서 두 번의 합병연산을 수행하는 것을 특징으로 하는 분할 합병 메쉬 방법
|
| 6 |
6
제 1 항에 있어서, 상기 제 4 단계는, 각 분할 내에서 합병한 후, 각 프로세서들이 홀수번째 분할에 속한 원소들을 먼저 목적 열로 행이동하고, 목적 행으로 열이동하며, 그 다음 짝수번째 분할에 속한 원소들을 목적 열로 행이동하고, 목적 행으로 열이동하여, 정렬된 순서대로 메쉬에 행우선 순서로 저장하는 것을 특징으로 하는 분할 합병 메쉬 방법
|
| 7 |
7
제 1 항에 있어서, 상기 분할 합병 메쉬 장치는, 프로세서들과 이 프로세서들 사이를 연결하는 간선들로 구성되며, 각 프로세서는 간단한 연산회로와 상수개의 데이터를 저장할 수 있는 메모리 소자를 가지고, 상하좌우 네 개의 프로세서와 간선을 통해 직접적으로 데이터를 저장할 수 있는 메모리 소자를 가지며, 상하좌우 네 개의 프로세서와 간선을 통해 직접적으로 데이터를 주고 받으면서 동작하는 것을 특징으로 하는 분할 합병 메쉬 방법
|
| 8 |
8
대용량 프로세서를 구비한 합병 연산 시스템에, 각 데이터가 속한 분할을 구하는 제 1 기능; 같은 분할에 속한 원소들을 같은 행으로 모으는 제 2 기능; 각 행에서 분할 별로 독립적으로 합병하는 제 3 기능; 및 합병 후 저장 위치로 이동하는 제 4 기능 을 실현시키기 위한 프로그램을 기록한 컴퓨터로 읽을 수 있는 기록 매체
|
