KR101867286B1 - 작업 부하를 고려한 하드웨어 가속화 기반의 대규모 데이터의 분산 처리 장치 및 방법 - Google Patents

Abstract

작업 부하를 고려한 하드웨어 가속화 기반의 대규모 데이터의 분산 처리 장치에 관한 것이다. 일 실시예에 따른 데이터 분산 처리 장치는 하나 이상의 정제노드에 대응되는 하나 이상의 파티션을 포함하는 메모리 버퍼와, 각 파티션의 분배 비율 계획에 기초하여 입력된 매핑 결과를 각 파티션에 분배하는 파티션 유닛을 포함하는 하나 이상의 셔플노드 및 메모리 버퍼의 대응되는 파티션의 내용을 입력받아 정제 처리하여 최종 결과를 생성하는 하나 이상의 정제노드를 포함할 수 있다. 본 실시예에 따르면, 최종 분산 처리 결과를 제공하는 작업 노드들의 처리 속도 등의 자원 상황을 고려하여 작업을 적응적으로 분배함으로써 데이터 분산 처리 성능을 크게 향상시킬 수 있다.

Description

작업 부하를 고려한 하드웨어 가속화 기반의 대규모 데이터의 분산 처리 장치 및 방법{DISTRIBUTED PROCESSING APPARATUS AND METHOD FOR BIG DATA USING HARDWARE ACCELERATION BASED ON WORK LOAD}

작업 부하를 고려한 하드웨어 가속화 기반의 대규모 데이터의 분산 처리 기술과 관련된다.

최근 인터넷 기술의 발전과 더불어 대규모의 데이터들이 생성 유통되고 있다. 각종 포털 회사 등, 각 기업들은 엄청난 양의 데이터를 축적하고 최대한 신속하게 의미 있는 정보를 추출하여 요청한 사용자 등에게 제공하는 것이 기업의 경쟁력이 되고 있다. 이로 인해, 최근에는 저비용으로 대규모 클러스터를 구축하여 대용량 데이터 분산 처리 및 작업 분산 병렬 처리 기술이 연구되고 있으며, 미국 구글(Google)사의 맵리듀스(MapReduce) 모델이 가장 대표적이다.

맵리듀스 모델은 구글사가 저비용 대규모 노드로 구성된 클러스터 상에 저장된 대용량 데이터의 분산 병렬 연산을 지원하기 위하여 제안한 분산 병렬 처리 프로그래밍 모델인데, 이는 사용자가 작성하는 맵(Map) 함수가 주축이 되는 맵 단계와 사용자가 작성하는 리듀스(Reduce) 함수가 주축이 되는 리듀스 단계의 2단계로 구성되어 순차적으로 수행된다.

그러나, 데이터의 대규모화가 갈수록 심화되고, 데이터의 분석 소요 처리 시간에 대한 단축 요구 또한 커지면서 현재의 MapReduce의 성능 수준을 넘어설 수 있게 하는 고속화 기술이 필요하게 되었다.

최종 분산 처리 결과를 제공하는 작업 노드들의 처리 속도 등의 자원 상황을 고려하여 작업을 적응적으로 분배하고, 하드웨어 가속화를 통해 데이터 분산 처리 성능을 크게 향상시키는 장치 및 방법이 제시된다.

일 양상에 따르면, 데이터의 분산 처리 장치는 하나 이상의 파티션을 포함하는 메모리 버퍼와, 각 파티션의 분배 비율 계획에 기초하여 입력된 매핑 결과를 각 파티션에 분배하는 파티션 유닛을 포함하는 하나 이상의 셔플노드 및 메모리 버퍼의 대응되는 파티션의 내용을 입력받아 정제 처리하여 최종 결과를 생성하는 하나 이상의 정제노드를 포함할 수 있다.

추가적인 양상에 따르면, 데이터 분산 처리 장치는 각 정제노드의 처리 성능을 측정하여 각 파티션의 분배 비율 계획을 생성하는 잡제어노드를 더 포함할 수 있다.

한편, 파티션 유닛은 입력된 매핑 결과를 이용하여 고정 크기의 중간 코드를 생성하는 주처리부 및 그 중간 코드를 이용하여 파티션의 분배 비율 계획에 맞도록 매핑 결과의 분배 파티션을 결정하여 대응되는 파티션 코드를 생성하는 비율조절부를 포함할 수 있다.

추가적인 양상에 따르면, 셔플노드는 메모리 버퍼의 파티션의 내용을 정렬하여 정렬 결과를 출력하는 정렬 유닛을 더 포함할 수 있다.

추가적인 양상에 따르면, 데이터 분산 처리 장치는 메모리 버퍼 관리 정보를 저장하는 메모리 버퍼 관리 테이블을 포함하는 메모리 버퍼 관리 유닛을 더 포함할 수 있다.

이때, 메모리 버퍼 관리 정보는 메모리 버퍼의 시작 주소, 파티션의 수, 잔여 레코드의 수, 최대 레코드의 수, 메모리 섹션 사이즈, 메모리 섹션 헤더 정보 및 파티션 룩업 테이블 중의 하나 이상을 포함할 수 있다.

추가적인 양상에 따르면, 메모리 버퍼 관리 유닛은 파티션유닛에 의해 분배된 매핑 결과를 메모리 버퍼에 전송하는 데이터 전송 제어부를 더 포함할 수 있다.

추가적인 양상에 따르면, 데이터의 분산 처리 장치는 입력 데이터를 병렬 처리하여 매핑 결과를 출력하는 하나 이상의 매핑노드를 더 포함할 수 있다.

한편, 데이터의 분산 처리 장치는 FPGA(Field Programmable Gate Array) 기반의 하드웨어 가속화를 통해 구현될 수 있다.

일 양상에 따르면, 데이터의 분산 처리 방법은 하나 이상의 셔플노드가 메모리 버퍼의 각 파티션의 분배 비율 계획에 기초하여 입력된 매핑 결과를 각 파티션에 분배하는 셔플 단계 및 하나 이상의 정제노드가 메모리 버퍼의 대응되는 파티션의 내용을 입력받아 정제 처리하여 최종 결과를 생성하는 정제 단계를 포함할 수 있다.

추가적인 양상에 따르면, 데이터의 분산 처리 방법은 잡제어노드가 각 정제노드의 처리 성능을 측정하여 각 파티션의 분배 비율 계획을 생성하는 단계를 더 포함할 수 있다.

한편, 셔플 단계는 입력된 매핑 결과를 이용하여 고정 크기의 중간 코드를 생성하는 주처리 단계 및 그 중간 코드를 이용하여 파티션의 분배 비율 계획에 맞도록 매핑 결과의 분배 파티션을 결정하여 대응되는 파티션 코드를 생성하는 비율 조절 단계를 포함할 수 있다.

추가적인 양상에 따르면, 셔플 단계는 셔플노드가 메모리 버퍼의 파티션의 내용을 정렬하여 정렬 결과를 출력하는 단계를 포함할 수 있다.

추가적인 양상에 따르면, 하나 이상의 매핑 노드가 입력 데이터를 병렬 처리하여 매핑 결과를 출력하는 매핑 단계를 더 포함할 수 있다.

한편, 데이터의 분산 처리 방법은 FPGA(Field Programmable Gate Array) 기반의 하드웨어 가속화를 통해 구현될 수 있다.

최종 분산 처리 결과를 제공하는 작업 노드들의 처리 속도 등의 자원 상황을 고려하여 작업을 적응적으로 분배함으로써 데이터 분산 처리 성능을 크게 향상시킬 수 있는 하드웨어 가속화 기반의 데이터 분산 처리 장치 및 방법을 제공할 수 있다.

도 1은 일 실시예에 따른 데이터 분산 처리 장치의 블록도이다.
도 2는 일 실시예에 따른 데이터 분산 처리 장치의 셔플노드를 설명하기 위한 도면이다.
도 3은 일 실시예에 따른 데이터 분산 처리 장치의 메모리 버퍼 관리 테이블의 예시도이다.
도 4는 일 실시예에 따른 데이터 분산 처리 방법의 흐름도이다.
도 5는 일 실시예에 따른 파티션 분배 비율 계획을 수립하는 절차이다.
도 6은 일 실시예에 따른 셔플단계에서 파티션유닛이 수행하는 절차이다.
도 7은 일 실시예에 따른 셔플단계에서 정렬유닛이 수행하는 절차이다.

기타 실시예들의 구체적인 사항들은 상세한 설명 및 도면들에 포함되어 있다. 본 발명의 이점 및 특징, 그리고 그것들을 달성하는 방법은 첨부되는 도면과 함께 상세하게 후술되어 있는 실시예들을 참조하면 명확해질 것이다. 그러나 본 발명은 이하에서 개시되는 실시예들에 한정되는 것이 아니라 서로 다른 다양한 형태로 구현될 수 있으며, 단지 본 실시예들은 본 발명의 개시가 완전하도록 하고, 본 발명이 속하는 기술분야에서 통상의 지식을 가진 자에게 발명의 범주를 완전하게 알려주기 위해 제공되는 것이며, 본 발명은 청구항의 범주에 의해 정의될 뿐이다. 명세서 전체에 걸쳐 동일 참조 부호는 동일 구성 요소를 지칭한다.

이하, 본 발명의 실시예들에 따른 작업 부하를 고려한 하드웨어 가속화 기반의 대규모 데이터 분산 처리 장치 및 방법을 도면들을 참고하여 자세히 설명하도록 한다.

도 1은 일 실시예에 따른 데이터 분산 처리 장치의 블록도이다. 본 실시예에 따른 데이터 분산 처리 장치(1)는 데이터 분산 처리 성능을 높이기 위해 하드웨어 가속화, 예컨대, FPGA(Field Programmable Gate Array) 기반의 하드웨어 가속화를 통해 구현될 수 있다.

데이터 분산 처리 장치(100)는 모든 작업 노드들을 하나의 FPGA 칩 내에 배치하여 구현되도록 설계할 수 있으며, 일부 작업 노드들은 별도의 FPGA 칩에 배치하여 구현되도록 설계할 수 있다.

도 1을 참조하면 데이터 분산 처리 장치(1)는 매핑노드(100), 셔플노드(200) 및 정제노드(300)를 포함할 수 있다. 이때, 매핑노드(100), 셔플노드(200) 및 정제노드(300)는 각각 복수 개로 구성될 수 있으며, 이를 통해 노드들 간의 병렬 처리(inter-node parallelization)를 수행함으로써 대규모 데이터의 효율적인 분산 처리가 가능해진다.

매핑노드(100)는 입력 데이터를 연산하여 매핑 결과를 출력하며 그 매핑 결과는 키-값(Key-Value) 쌍의 형태일 수 있다.

셔플노드(200)는 입력되는 매핑 결과들을 하나 이상의 정제노드(300)에 분배하는 기능을 수행할 수 있다.

하나 이상의 정제노드(300)는 셔플노드(200)에서 분배된 결과에서 중복 데이터 제거 등의 정제 처리를 하여 최종 결과를 출력할 수 있다.

추가적인 양상에 따르면, 데이터 분산 처리 장치(1)는 잡제어노드(400)를 더 포함할 수 있다. 잡제어노드(400)는 각 노드(100, 200, 300)들의 작업 환경 정보를 관리하는 잡 버퍼(job buffer)를 포함할 수 있다. 또한, 잡제어노드(400)는 처리할 전체 잡(job)들을 모니터링하며, 최종 결과를 출력하는 정제노드(300)들의 작업 부하, 컴퓨팅 성능 등의 자원 상황을 측정하여 관리한다. 또한, 측정된 자원 상황에 따라 셔플노드(200)가 각 정제노드(300)에 분배할 파티션 분배 비율 계획(410)을 수립하고 셔플노드(200)에 제공할 수 있다. 잡제어노드(400)가 정제노드(300)들의 성능 측정 및 파티션 분배 비율 계획을 수립하는 절차에 대해서는 도 5를 참조하여 자세히 설명한다.

도 2는 일 실시예에 따른 데이터 분산 처리 장치의 셔플노드를 설명하기 위한 도면이다. 도 3은 일 실시예에 따른 데이터 분산 처리 장치(1)의 메모리 버퍼 관리 테이블의 예시도이다. 도 1 내지 도 3을 참조하여 데이터 분산 처리 장치(1)를 좀 더 구체적으로 설명한다.

도 1에 도시된 바와 같이, 셔플노드(200)는 파티션유닛(210), 메모리 버퍼 관리 유닛(220), 메모리 버퍼(230) 및 정렬유닛(240)을 포함할 수 있다. 파티션유닛(210)은 매핑노드(100)에서 출력되는 매핑 결과, 예컨대, 매핑노드(100)의 키-값(Key-Value) 쌍의 매핑 결과에서 키(Key)를 입력으로 받아 그 키(Key)에 대해 해당하는 파티션을 할당할 수 있다. 이때, 매핑 결과의 키(Key)는 가변적일 수 있으므로 효율적인 하드웨어 기반 처리를 위해서, 도 2에 도시된 바와 같이, 그 키(Key)의 최소 의미 비트(M_in-비트)만을 파티션유닛(210)의 입력으로 사용할 수 있다.

도 2의 (a)는 키(Key)가 최소 의미 비트(M_in-비트)보다 큰 경우 나머지 비트(버림 비트)를 버리는 것을 나타내었으며, (b)는 키(Key)가 최소 의미 비트(M_in-비트)보다 작은 경우 부족한 비트(채움 비트)를 임의의 값(예: 0)으로 채워 최소 의미 비트(M_in-비트)가 되도록 하여 그 최소 의미 비트(M_in-비트)를 파티션유닛(210)에 입력하는 것을 예시하였다.

추가적인 양상에 따르면, 파티션유닛(210)은 주처리부(211)와 비율조절부(212)를 포함할 수 있다. 주처리부(211)는 키(Key)의 최소 의미 비트(M_in-비트) 입력에 대해 연산을 수행하여 고정된 크기의 중간 코드를 생성할 수 있다. 주처리부(211)는 일 예로서 임의의 길이의 입력에 대해 고정 길이의 출력을 생성하는 암호화 해시함수(cryptographic hash function) 또는 고정 길이의 입력에 대해 고정 길이의 출력을 생성하는 전용 해시함수(hash function)를 사용하여 연산을 수행하여 고정된 크기의 해시코드를 생성할 수 있다. 다만, 이는 하나의 예시에 불과하며 어떠한 길이의 입력에 대해 고정 길이의 출력을 생성하는 모든 함수가 이용될 수 있음은 자명하다.

비율조절부(212)는 주처리부(211)의 출력인 중간 코드와 잡제어노드(400)에서 생성된 파티션 분배 비율 계획(410)에 기초하여 매핑노드(100)의 매핑 결과들이 분배될 파티션을 할당한 파티션 코드를 출력할 수 있다. 예를 들어, 도 2에 도시된 바와 같이 잡제어노드(400)는 3개의 정제노드(300)에 대해 자원 상황을 측정하여 자원 상황이 상대적으로 우수한 정제노드 3(파티션 3에 대응)에 작업의 50%를 분배하고, 자원 상황이 상대적으로 저조한 정제노드 1(파티션 1에 대응)과 정제노드 2(파티션 2에 대응)에 각각 30%, 와 20%를 분배하는 파티션 분배 비율 계획(410)을 생성할 수 있다. 비율조절부(212)에 의해 출력되는 파티션 코드를 통해 각 매핑 결과가 분배될 파티션을 알 수 있으며, 각 매핑 결과들은 파티션 1: 30%, 파티션 2: 20%, 파티션 3: 50%의 비율로 분배된다.

도 1을 참조하면, 메모리 버퍼 관리 유닛(220)은 메모리 버퍼 관리 테이블(221)과 데이터 전송 제어부(222)를 포함할 수 있다. 메모리 버퍼 관리 테이블(221)은 파티션유닛(210) 또는 정렬유닛(240)이 메모리 버퍼(230)를 사용하는데 필요한 정보를 저장하고 있으며, 데이터 전송 제어부(222)는 파티션유닛(210)의 출력 결과인 파티션 코드를 메모리 버퍼(230)에 전송하고, 정렬유닛(240)에 메모리 버퍼(240)의 데이터를 전송하는 기능을 수행할 수 있다. 데이터 분산 처리 장치(1)의 셔플노드(200)는 데이터 전송 제어부(222)를 통해 CPU의 직접적이고도 반복적인 로드/스토어(Load/Store) 기반의 I/O 인텐시브 연산(Intensive Operation) 없이도 데이터의 전송을 수행할 수 있다.

도 3은 메모리 버퍼 관리 테이블(221)을 예시한 것이다. 메모리 버퍼 관리 테이블(221)은 메모리 버퍼(230)의 사용에 필요한 각종 메모리 버퍼 관리 정보들을 저장할 수 있다. 이때, 메모리 버퍼 관리 정보는 메모리 버퍼의 시작 주소, 메모리 버퍼의 총 파티션(섹션)의 수, 잔여 레코드의 수, 매핑 결과 플래그, 최대 레코드 수, 섹션 사이즈, 파티션 룩업 테이블, 섹션 헤더 정보를 포함할 수 있다. 잔여 레코드의 수는 매핑 결과의 전체 레코드 중 처리되고 남은 레코드의 수에 대한 정보이다. 매핑 결과 플래그는 셔플노드(200)에서 더 이상 처리해야 할 매핑 결과가 없음을 나타내는 정보이다. 최대 레코드 수는 메모리 버퍼의 각 섹션에 기록될 수 있는 최대 레코드의 수를 의미한다. 섹션 사이즈는 섹션의 크기를 바이트 단위로 나타낸 정보이다.

파티션 룩업 테이블은 파티션 코드와, 그 파티션 코드와 섹션 헤더의 쌍(Pair) 목록을 가지는 섹션 헤더 링크를 포함할 수 있다. 섹션 헤더 링크를 통해 파티션 코드 정보가 있을 때 해당되는 메모리 버퍼 섹션의 헤더를 바로 찾을 수 있다. 섹션 헤더는 메모리 버퍼 섹션에 대한 정보를 관리하며, 그 섹션에 대한 정보로는 그 섹션의 기본 주소로 사용될 섹션의 시작 주소, 그 섹션의 정렬 여부를 나타내는 정렬 플래그, 그 섹션의 시작 주소에서 일정 바이트 오프셋 된 다음 기록 주소, 현재까지 그 섹션에 기록된 레코드의 수 정보를 포함할 수 있다.

메모리 버퍼(230)는 하나 이상의 정제노드(300)에 대응되는 하나 이상의 파티션(섹션)으로 이루어질 수 있다. 각 파티션은 전술한 바와 같이 대응되는 정제노드(300)의 처리 성능에 따른 분배 비율을 가지며, 각 정제노드(300)는 대응되는 파티션의 내용을 읽어 중복 키를 제거하고 정제 처리하여 최종 결과를 생성한다. 따라서, 각 정제노드(300)들은 서로 다른 처리 성능을 가지더라도 서로 다른 비율의 작업을 처리하기 때문에 어느 하나의 정제노드(300)에서 병목이 발생하여 처리 지연이 되는 것을 방지할 수 있다.

이때, 메모리 버퍼(230)의 파티션(섹션)의 내용은 정렬유닛(240)에 의해 정렬되어 정제노드(300)에 입력될 수 있다. 정렬유닛(240)은 메모리 버퍼 관리 테이블(221)의 정렬 플래그를 체크하고 정렬 플래그가 세팅되어 있으면 해당 섹션을 정렬하여 정렬된 레코드를 출력할 수 있다.

도 4는 일 실시예에 따른 데이터 분산 처리 방법의 흐름도이다. 도 4를 참조하여 데이터 분산 처리 방법을 설명한다. 전술한 바와 같이 대규모 데이터의 분산 처리 방법은 하드웨어 가속화를 통해 구현될 수 있으며, 예컨대, 각 노드들의 모든 기능들은 FPGA(Field Programmable Gate Array) 칩 내에 구현하여 하드웨어 가속화를 구현할 수 있다.

데이터 분산 처리 방법은 먼저, 잡제어노드(400)가 각 정제노드(300)의 처리 성능 등의 자원 상황을 측정하고, 그 측정 결과에 따라 파티션의 분배 비율 계획(410)을 생성할 수 있다(단계 510).

그 다음, 매핑노드(100)가 입력데이터를 병렬 처리하여 매핑 결과를 출력할 수 있다(단계 520). 매핑 결과는 키-값(Key-Value) 쌍(pair) 형식일 수 있으며, 도 2에 도시된 바와 같이 그 키(Key)의 최소 의미 비트(M_in-비트)는 셔플노드(200)의 파티션유닛(210)에 입력될 수 있다. 셔플노드(200)의 파티션유닛(210)은 파티션의 분배 비율 계획(410)에 기초하여 매핑 결과를 각 파티션에 분배하고, 정렬유닛(240)은 메모리 버퍼(230)에 기록된 섹션의 내용을 정렬하여 정렬된 레코드를 출력할 수 있다(단계 530). 정제노드(300)는 메모리 버퍼(230)의 파티션의 내용을 입력받아 중복 키 제거 등 정제 처리하여 최종 결과를 생성할 수 있다(단계 540).

도 5는 일 실시예에 따른 파티션 분배 비율 계획을 수립하는 절차이다. 도 5를 참조하여 잡제어노드(400)가 파티션의 분배 비율 계획을 수립하는 단계(510)에 대해 상세히 설명한다.

먼저, 잡제어노드(400)는 잡 버퍼(job buffer)로부터 잡 환경을 추출하여 정제노드(300)들의 리스트를 획득할 수 있다(단계 511). 그 다음, 현재 성능을 측정할 정제노드(300)를 결정하고(단계 512), 그 정제노드(512)가 현재까지 처리한 레코드의 수(rec_rd_1) 정보를 추출한다(단계 513). 그 다음, 미리 정의된 일정 시간(prd_time)이 경과한 후 다시 그때까지 처리한 레코드의 수(rec_rd_2) 정보를 추출한다(단계 514). 그 다음, 측정된 레코드의 수 정보(rec_rd_1, rec_rd_2)를 이용하여 [성능 = (rec_rd_2 - rec_rd_1)/prd_time] 와 같은 수식에 의해 그 정제노드(300)의 처리 성능을 계산할 수 있다(단계 515). 이와 같은 과정을 반복하여 전체 정제노드(300)에 대해 처리 성능을 계산한다.

그 다음, 측정된 정제노드(300)의 처리 성능을 바탕으로 메모리 버퍼(230)의 각 파티션의 분배 비율을 계산한다(단계 516). 예를 들어, 수식 [i 번째 파티션의 분배 비율 = 100 * (i 번째 정제노드의 현재 성능) / (전체 정제노드들의 현재 성능의 합)]에 의해 각 파티션의 분배 비율을 계산할 수 있다.

도 6은 일 실시예에 따른 셔플단계에서 파티션유닛이 수행하는 절차이다. 도 7은 일 실시예에 따른 셔플단계에서 정렬유닛이 수행하는 절차이다. 도 6과 도 7을 참조하여 셔플노드가 파티션을 분배하고 정렬하는 셔플단계(530)에 대해 상세히 설명한다.

먼저, 셔플노드(200)의 파티션유닛(210)은 처리할 매핑 결과 레코드가 존재하는지 체크한다(단계 531). 파티션유닛(210)은 메모리 버퍼 관리 테이블(221)의 잔여 레코드 수 필드를 체크하여 그 값이 0인 경우 더 이상 처리할 레코드가 없는 것으로 판단할 수 있다. 만약, 처리할 잔여 레코드가 존재하지 않는 경우 매핑 결과 플래그와 모든 섹션 헤더의 정렬 플래그를 세팅한다(단계 539). 더 이상 처리할 잔여 레코드가 존재하지 않으면, 후술하는 바와 같이 정렬유닛(240)이 그 정렬 플래그를 체크하여 메모리 버퍼(230)의 내용을 정렬하게 된다.

만약, 처리할 잔여 레코드가 더 존재하면, 전술한 바와 같이 그 레코드의 키(Key)를 최소 의미 비트(M_in-비트)로 최적화할 수 있다(단계 532). 그 다음, 파티션유닛(210)의 주처리부(211)가 그 M_in-비트를 이용하여 고정 크기의 중간코드를 생성할 수 있다(단계 533). 그 다음, 비율조절부(212)가 그 중간코드와 파티션 분배 비율 계획(410)을 이용하여 매핑 결과 레코드가 분배될 파티션을 결정하여 대응되는 파티션 코드를 생성할 수 있다(단계 534).

그 다음, 메모리 버퍼 관리 유닛(220)의 데이터 전송 제어부(222)는 그 파티션 코드에 근거하여 매핑 결과(키-값 쌍)를 메모리 버퍼(230)의 해당하는 섹션에 전송한다(단계 535). 그 다음, 그 섹션 헤더의 기록 레코드 수를 업데이트하고, 기록 레코드 수가 최대 레코드 수에 도달했는지 체크할 수 있다(단계 536). 만약, 기록 레코드 수가 최대 레코드 수에 도달하였으면 현재 섹션의 정렬 플래그를 세팅하고(단계 537), 그렇지 않으면 다음 기록 주소 필드를 업데이트할 수 있다(단계 538).

셔플노드(200)는 위 과정(단계 531 이하)을 잔여 레코드가 더 이상 존재하지 않을 때까지 반복 수행하며, 이후 정렬유닛(240)에 의한 정렬 처리 절차가 진행될 수 있다.

정렬유닛(240)은 섹션 헤더의 정렬 플래그가 세팅되어 있는지 체크한다(단계 631). 만약, 해당 섹션 헤더의 정렬 플래그가 세팅되어 있지 않으면, 다음 섹션 헤더 정보를 추출하고(단계 637), 마지막 섹션 여부를 확인하여(단계 638) 마지막 섹션이라면 종료하고, 마지막 섹션이 아니라면 다시 단계 631 이하를 수행한다.

만약, 해당 섹션 헤더의 정렬 플래그가 세팅되어 있으면 상위 슬롯부터 해당 섹션의 현재 레코드를 입력하고(단계 632), 정렬유닛(240)을 구동하여 그 레코드를 정렬할 수 있다(단계 635). 이때, 정렬 단계(635)를 수행하기 전에 현재 레코드 수가 최대 레코드 수보다 작은지, 즉, 정렬유닛에 빈 슬롯이 존재하는지 체크하여(단계 633) 빈 슬롯이 존재하면 그 빈 슬롯에 임의의 수 예컨대, 가장 큰 수로 채우는 단계(단계 634)가 선행될 수 있다. 이는 정렬유닛(240)의 하드웨어적 처리 효율을 높이면서 그 가장 큰 수가 정렬 결과의 가장 끝쪽에 위치하도록 하여 쉽게 제거할 수 있도록 하기 위함이다.

그 다음, 해당 섹션의 모든 레크드에 대해 정렬이 완료되었는지 체크하고(단계 636), 정렬이 완료되지 않았으면 단계 632 이하를 반복하여 나머지 레코드에 대해 정렬을 수행한다. 만약, 정렬이 완료되었으면 다음 섹션 헤더 정보를 추출하고(단계 637), 마지막 섹션 여부를 확인하여(단계 638) 마지막 섹션이라면 종료하고, 마지막 섹션이 아니라면 다시 단계 631 이하를 수행한다.

한편, 본 발명의 실시 예들은 컴퓨터로 읽을 수 있는 기록 매체에 컴퓨터가 읽을 수 있는 코드로 구현하는 것이 가능하다. 컴퓨터가 읽을 수 있는 기록 매체는 컴퓨터 시스템에 의하여 읽혀질 수 있는 데이터가 저장되는 모든 종류의 기록 장치를 포함한다.

컴퓨터가 읽을 수 있는 기록 매체의 예로는 ROM, RAM, CD-ROM, 자기 테이프, 플로피디스크, 광 데이터 저장장치 등이 있으며, 또한 캐리어 웨이브(예를 들어 인터넷을 통한 전송)의 형태로 구현하는 것을 포함한다. 또한, 컴퓨터가 읽을 수 있는 기록 매체는 네트워크로 연결된 컴퓨터 시스템에 분산되어, 분산 방식으로 컴퓨터가 읽을 수 있는 코드가 저장되고 실행될 수 있다. 그리고 본 발명을 구현하기 위한 기능적인(functional) 프로그램, 코드 및 코드 세그먼트들은 본 발명이 속하는 기술 분야의 프로그래머들에 의하여 용이하게 추론될 수 있다.

본 발명이 속하는 기술분야의 통상의 지식을 가진 자는 본 발명이 그 기술적 사상이나 필수적인 특징을 변경하지 않고서 다른 구체적인 형태로 실시될 수 있다는 것을 이해할 수 있을 것이다. 그러므로 이상에서 기술한 실시예들은 모든 면에서 예시적인 것이며 한정적이 아닌 것으로 이해해야만 한다. 본 발명의 범위는 상기 상세한 설명보다는 후술하는 특허청구의 범위에 의하여 나타내어지며, 특허청구의 범위의 의미 및 범위 그리고 그 균등 개념으로부터 도출되는 모든 변경 또는 변형된 형태가 본 발명의 범위에 포함되는 것으로 해석되어야 한다.

1: 데이터 분산 처리 장치 100: 매핑노드
200: 셔플노드 210: 파티션유닛
211: 주처리부 212: 비율조절부
220: 메모리 버퍼 관리 유닛 221: 메모리 버퍼 관리 테이블
230: 메모리 버퍼 222: 데이터 전송 제어부
240: 정렬유닛 300: 정제노드
400: 잡제어노드 410: 파티션 분배 비율 계획

Claims (15)

1. 하나 이상의 파티션을 포함하는 메모리 버퍼 및 각 파티션의 분배 비율 계획에 기초하여 입력된 매핑 결과를 상기 각 파티션에 분배하는 파티션 유닛을 포함하는 하나 이상의 셔플노드; 및
   상기 메모리 버퍼에 대응되는 파티션의 내용을 입력받아 정제 처리하여 최종 결과를 생성하는 하나 이상의 정제노드;를 포함하되,
   상기 파티션 유닛은,
   상기 입력된 매핑 결과를 이용하여 고정 크기의 중간 코드를 생성하는 주처리부; 및
   상기 중간 코드를 이용하여 상기 파티션의 분배 비율 계획에 맞도록 상기 매핑 결과의 분배 파티션을 결정하여 대응되는 파티션 코드를 생성하는 비율조절부;를 포함하는 데이터의 분산 처리 장치.
2. 제1항에 있어서,
   상기 각 정제노드의 처리 성능을 측정하여 상기 각 파티션의 분배 비율 계획을 생성하는 잡제어노드;를 더 포함하는 데이터의 분산 처리 장치.
3. 삭제
4. 제1항에 있어서, 상기 셔플노드는,
   상기 메모리 버퍼의 파티션의 내용을 정렬하여 정렬 결과를 출력하는 정렬 유닛;을 더 포함하는 데이터의 분산 처리 장치.
5. 제1항에 있어서,
   메모리 버퍼 관리 정보를 저장하는 메모리 버퍼 관리 테이블을 포함하는 메모리 버퍼 관리 유닛;을 더 포함하는 데이터의 분산 처리 장치.
6. 제5항에 있어서, 상기 메모리 버퍼 관리 정보는,
   메모리 버퍼의 시작 주소, 파티션의 수, 잔여 레코드의 수, 최대 레코드의 수, 메모리 섹션 사이즈, 메모리 섹션 헤더 정보 및 파티션 룩업 테이블 중의 하나 이상을 포함하는 데이터의 분산 처리 장치.
7. 제5항에 있어서, 상기 메모리 버퍼 관리 유닛은,
   상기 파티션유닛에 의해 분배된 매핑 결과를 상기 메모리 버퍼에 전송하는 데이터 전송 제어부;를 더 포함하는 데이터의 분산 처리 장치.
8. 제1항에 있어서,
   입력 데이터를 병렬 처리하여 상기 매핑 결과를 출력하는 하나 이상의 매핑노드;를 더 포함하는 데이터의 분산 처리 장치.
9. 제1항에 있어서, 상기 데이터의 분산 처리 장치는
   FPGA(Field Programmable Gate Array) 기반의 하드웨어 가속화를 통해 구현되는 데이터의 분산 처리 장치.
10. 하나 이상의 셔플노드가 메모리 버퍼의 각 파티션의 분배 비율 계획에 기초하여 입력된 매핑 결과를 상기 각 파티션에 분배하는 셔플 단계; 및
    하나 이상의 정제노드가 상기 메모리 버퍼의 대응되는 파티션의 내용을 입력받아 정제 처리하여 최종 결과를 생성하는 정제 단계;를 포함하되,
    상기 셔플 단계는,
    상기 입력된 매핑 결과를 이용하여 고정 크기의 중간 코드를 생성하는 단계와,
    상기 중간 코드를 이용하여 상기 파티션의 분배 비율 계획에 맞도록 상기 매핑 결과의 분배 파티션을 결정하여 대응되는 파티션 코드를 생성하는 단계를 포함하는 데이터의 분산 처리 방법.
11. 삭제
12. 삭제
13. 삭제
14. 삭제
15. 삭제

Images