멀티 프로세서 시스템 및 그 정보처리방법 document_id A220623052973

사회 전체의 다양한 장소에 컴퓨터가 도입되어, 인터넷을 비롯한 네트워크가 침투된 오늘날은 여기저기에서 대규모의 데이터가 축적·처리되게 되었다. 한편, 대규모의 데이터를 처리하기 위하여, 양호한 효율의 알고리즘이 개발되고 있다. 대규모 데이터, 특히, 대규모의 표형식 데이터를 처리할 때 빈번히 출현하는 처리가 정렬(sort)이다. 효율적인 정렬 알고리즘으로서, 기수(基數)(RADIX) 정렬과 카운팅(COUNTING) 정렬(계수정렬, 분포계수정렬이라고도 부름)이 알려져 있다. 카운팅 정렬(counting sort)은 기수정렬의 각 자릿수를 정렬하는데 이용되는 경우가 있으며, 효율이 양호한 알고리즘이지만, 그 적용을 위해서는, 1) 정렬대상이 정수일 것 2) 정렬대상이 되는 정수의 상한과 하한을 알고 있을 것 3) 정렬대상이 되는 정수의 상한과 하한의 차이가 지나치게 크지 않을 것 이라는 전제조건이 있다. 이에 대하여, 본 발명자는, 대규모의 표형식 데이터를 고속으로 검색, 집계, 정렬(sort)하는데 적합한 데이터 관리기구를 제안한 바 있다(특허문헌 1 참조). 상기 데이터 관리기구는, 표형식 데이터 항목의 각 항목값을 나타내기 위한 정보블럭을 갖는다. 이 정보블럭에서는, 표형식 데이터의 항목에 속하는 항목값이, 각 항목값에 부여된 항목값 번호와, 항목값 번호를 순서대로 늘어놓은 실제 항목값의 배열에 의해 표시된다. 각 레코드의 항목값에 대응된 항목값 번호를 레코드 번호순으로 늘어놓은 배열이 준비되며, 각 레코드의 항목값은, 해당 레코드의 항목값 번호에 대응된 값을 항목값의 배열에서 찾음으로써 특정된다. 또한, 표형식 데이터중의 처리대상인 레코드는, 레코드 번호를 순서대로 늘어놓은 배열에 의해 특정된다. 정보블럭은, 표형식 데이터의 각 항목에 대하여, 그 항목에 속하는 항목값이 순서가 매겨진(정수화된) 항목값 번호의 순으로, 상기 항목값 번호에 대응된 항목값이 저장된 테이블이다. 항목값 자체는, 수치(정수, 고정 소수점, 부동 소수점 등), 문자열 등 어떠한 타입의 데이터여도 된다. 따라서, 상기 데이터 관리기구는, 모든 타입의 데이터의 값이 항목값 번호라는 정수로 취급될 수 있다는 특장점이 있다. 즉, 상기 데이터 관리기구에 따르면, 가령, 문자열 타입의 데이터를 정렬할 때, 문자열 타입의 데이터를 그대로 정렬대상으로 하여 정렬하는 것이 아니라, 문자열 타입의 데이터의 값에 대응된 항목값 번호를 정렬대상으로 하여 정렬할 수가 있다. 이 때, 정렬결과는 레코드 번호를 순서대로 늘어놓은 배열에 의해 표시된다. 이와 같이, 본 발명자가 제안한 정보블럭에 근거하는 데이터 관리기구는, 카운팅 정렬을 적용하기 위한 상기 1) 내지 3)의 전제조건을 충족시킨다는 점에서 우수하다. 다른 한편으로, 대규모 데이터를 처리하기 위해 필요한 방대한 계산을 고속으로 실행하기 위하여, 병렬처리의 도입이 시도되고 있다. 정렬에 관해서도 각종의 병렬정렬 알고리즘이 제안되고 있다. 일반적으로, 병렬 처리 아키텍처는 크게 「분산 메모리형]과 「공유 메모리형」으로 나뉜다. 분산 메모리형은, 각 프로세서가 각각 로컬 메모리를 가지고, 이것들을 결합하여 시스템을 구축한다. 이러한 방식에서는, 이론적으로 수 백～수 만대의 프로세서를 조립한 하드웨어 시스템의 설계가 가능하다. 그러나, 분산 메모리형은, 데이터의 분장관리가 복잡하고, 프로세서간 통신효율이 낮다는 등의 기술적 과제가 있다. 이에 반해, 공유 메모리형은 복수의 프로세서가 하나의 거대한 메모리 공간을 공유하는 방식이다. 이러한 방식에서는, 프로세서 그룹과 공유 메모리간의 트래픽이 병목(bottle neck)이 되므로, 현실적으로는 100대를 초과하는 프로세서를 이용하여 시스템을 구축하기가 용이하지 않은 것으로 여겨진다. 그러나, 이러한 상황 하에서 최근에는 복수의 CPU를 이용한 공유 메모리형 멀티 프로세서 시스템으로서 구성된 퍼스널 컴퓨터의 입수가 가능하다. 이러한 종류의 퍼스널 컴퓨터에 사용되는 표준적인 CPU는, 메모리버스의 5～6배 정도의 내부클럭으로 동작하고, 그 내부에 자동적인 병렬실행기능이나 파이프라인 처리기능이 장비되어 있어, 약 1데이터를 1클럭(메모리버스)으로 처리할 수 있다. 특허문헌 1 : 국제공개공보 ＷO00/10103호