KR101458028B1 - 병렬 처리 장치 및 방법 - Google Patents

Abstract

본 발명은 병렬 처리 장치 및 방법에 관한 것으로서, 다중 스레드에 의하여 복수 개의 작업이 병렬 처리되는 경우 작업 분할 제어 블록(work sharing control block)을 동적으로 생성함에 있어서 그 재사용성을 향상시키는 병렬 처리 장치 및 방법에 관한 것이다.

본 발명의 실시예에 따른 병렬 처리 장치는 적어도 하나의 스레드에 의한 작업이 진행되는 방향에 존재하는 제 1 컨테이너에 포함된 제어 블록으로의 접근 가능 여부를 판단하는 제어부와, 상기 판단 결과에 따라 적어도 하나의 제어 블록이 포함된 제 2 컨테이너를 생성하는 컨테이너 생성부 및 상기 제 1 컨테이너에 포함된 제어 블록 또는 상기 제 1 컨테이너 및 상기 제 2 컨테이너에 포함된 제어 블록이 상기 스레드가 작업 중인 제어 블록과 함께 링형으로 연결되도록 구성하는 컨테이너 관리부를 포함한다.

OpenMP, 병렬 처리, 작업 분할(Work Sharing), 제어 블록(Control Block)

Description

병렬 처리 장치 및 방법{Apparatus and method for parallel processing}

도 1은 본 발명의 실시예에 따른 병렬 처리 장치를 나타낸 블록도이다.

도 2는 본 발명의 실시예에 따른 컨테이너를 나타낸 도면이다.

도 3은 본 발명의 실시예에 따른 컨테이너의 프로그래밍 코드이다.

도 4는 본 발명의 실시예에 따라 복수 개의 컨테이너가 링형으로 연결된 것을 나타낸 도면이다.

도 5는 본 발명의 실시예에 따른 컨테이너에 포함된 복수 개의 제어 블록에 복수 개의 스레드가 접근한 것을 나타낸 도면이다.

도 6은 본 발명의 실시예에 따라 제어 블록이 재사용되는 것을 나타낸 도면이다.

도 7은 본 발명의 실시예에 따라 컨테이너가 생성된 것을 나타낸 도면이다.

도 8은 본 발명의 실시예에 따른 병렬 처리 과정을 나타낸 흐름도이다.

<도면의 주요 부분에 관한 부호의 설명>

110 : 스레드 생성부 120 : 스레드 관리부

130 : 저장부 140 : 제어부

150 : 컨테이너 관리부 160 : 컨테이너 생성부

본 발명은 병렬 처리 장치 및 방법에 관한 것으로서, 더욱 상세하게는 다중 스레드에 의하여 복수 개의 작업이 병렬 처리되는 경우 작업 분할 제어 블록(work sharing control block)을 동적으로 생성함에 있어서 그 재사용성을 향상시키는 병렬 처리 장치 및 방법에 관한 것이다.

OpenMP는 공유메모리 환경에서 다중 스레드(multi-thread) 병렬 프로그램을 작성하기 위한 응용 프로그램 인터페이스(API; Application Program Interface)로서, 공유메모리 병렬성을 표현하기 위한 컴파일러 지시어들의 집합이다.

OpenMP를 이용한 병렬 프로그램밍은 순차코드에 필요한 부분만 지시어를 삽입하는 컴파일러 지시어 기반으로 구현된다. 사용자는 병렬화가 필요한 부분에 적절한 OpenMP 지시어를 삽입하고 컴파일러는 삽입된 지시어를 참고하여 다중 스레드 코드를 생성한다.

컴파일러 지시자로 프로그램 코드 내에서 병렬 구간을 지정하면 OpenMP 런타임 라이브러리 호출을 통해 마스터 스레드(master thread)는 추가로 스레드를 생성하여 병렬 프로그래밍이 가능하도록 한다. 이렇게 생성된 스레드들에 의해 수행되는 병렬 영역은 부 작업(sub task) 형태로 나뉘고 각 스레드들은 할당된 부분만큼 작업을 수행하므로 병렬 구간의 작업 분할(work sharing)이 가능하게 된다.

기본적으로 OpenMP의 작업 분할에는 하나의 스레드가 먼저 작업이 종료되더라도 다른 모든 스레드들이 작업을 완료할 때까지 대기하여야 하는 암시적 장 벽(implied barrier)이 내재되어 있으며, 만약 NOWAIT 명령어가 프로그램 내에 명시되면 암시적 장벽은 제거되어 각 스레드는 대기 없이도 바로 이후 작업으로 진행할 수 있게 된다.

각 스레드에 의한 공유를 위하여 작업 분할에 필요한 정보는 제어 블록(control block)에 명시될 수 있다. 이 때, 전술한 NOWAIT 명령어가 프로그램 내에 명시되면 복수 개의 작업 분할을 각각 관리하는 복수 개의 제어 블록이 필요하게 된다.

예를 들어, 하나의 병렬 구간 내에 4개의 NOWAIT 작업 분할 영역이 존재한다고 하고, 이를 4개의 스레드들이 수행하는 경우, 하나의 스레드가 첫 번째 NOWAIT 작업 분할 영역에서 작업을 수행하고 있고, 다른 스레드들이 두 번째 NOWAIT 작업 분할 영역에서 작업을 수행하게 되면 두 개의 제어 블록이 필요하게 된다. 같은 방법으로, 연속된 NOWAIT 명령어에 따라 스레드들이 각 작업 분할 영역에서 작업을 수행하고 있다면 추가적인 제어 블록이 필요하게 된다.

장벽 동기화(barrier synchronization)가 발생하기 전까지 각 스레드가 작업 분할을 수행함에 있어서 필요한 제어 블록의 수는 모든 스레드에 의해 완료되지 않은 작업 분할의 수에 의하여 결정되고, 이는 런타임시에만 알 수 있다.

다시 말해, 제어 블록의 수는 런타임시에만 알 수 있는 것으로서 이에 따른 메모리의 낭비가 발생할 수 있다.

제어 블록의 생성을 통한 메모리의 낭비를 방지하기 위하여 제어 블록들을 일정 크기의 정적 배열로 관리하는 방법, 제어 블록들을 동적 배열로 관리하는 방 법, 그리고 일정한 크기로 정적 배열을 생성하고 필요에 따라 동적으로 추가하는 방법 등이 이용될 수 있으나, 정적 배열로 관리하는 방법의 경우에는 메모리 오버 플로우(memory over flow)의 위험이 있고, 동적으로 생성하는 방법의 경우에는 새롭게 제어 블록을 생성함에 있어서 모든 스레드를 동기화시켜야 하는 단점이 있다.

따라서, 제어 블록의 생성을 제한하면서도 모든 작업 분할 영역에서의 작업이 원활하게 수행될 수 있도록 하는 발명의 등장이 요구된다.

본 발명은 다중 스레드에 의하여 복수 개의 작업이 병렬 처리되는 경우 작업 분할 제어 블록을 동적으로 생성함에 있어서 그 재사용성을 향상시키는데 그 목적이 있다.

본 발명의 목적들은 이상에서 언급한 목적으로 제한되지 않으며, 언급되지 않은 또 다른 목적들은 아래의 기재로부터 당업자에게 명확하게 이해되어질 수 있을 것이다.

상기 목적을 달성하기 위하여, 본 발명의 실시예에 따른 병렬 처리 장치는 적어도 하나의 스레드에 의한 작업이 진행되는 방향에 존재하는 제 1 컨테이너에 포함된 제어 블록으로의 접근 가능 여부를 판단하는 제어부와, 상기 판단 결과에 따라 적어도 하나의 제어 블록이 포함된 제 2 컨테이너를 생성하는 컨테이너 생성부 및 상기 제 1 컨테이너에 포함된 제어 블록 또는 상기 제 1 컨테이너 및 상기 제 2 컨테이너에 포함된 제어 블록이 상기 스레드가 작업 중인 제어 블록과 함께 링형으로 연결되도록 구성하는 컨테이너 관리부를 포함한다.

본 발명의 실시예에 따른 병렬 처리 방법은 적어도 하나의 스레드에 의한 작업이 진행되는 방향에 존재하는 제 1 컨테이너에 포함된 제어 블록으로의 접근 가능 여부를 판단하는 단계와, 상기 판단 결과에 따라 적어도 하나의 제어 블록이 포함된 제 2 컨테이너를 생성하는 단계 및 상기 제 1 컨테이너에 포함된 제어 블록 또는 상기 제 1 컨테이너 및 상기 제 2 컨테이너에 포함된 제어 블록이 상기 스레드가 적업 중인 제어 블록과 함께 링형으로 연결되도록 구성하는 단계를 포함한다.

기타 실시예들의 구체적인 사항들은 상세한 설명 및 도면들에 포함되어 있다.

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

이하, 첨부된 도면을 참조하여 본 발명의 바람직한 실시예를 상세히 설명하기로 한다.

도 1은 본 발명의 실시예에 따른 병렬 처리 장치를 나타낸 블록도로서, 병렬 처리 장치(100)는 스레드 생성부(110), 스레드 관리부(120), 저장부(130), 제어 부(140), 컨테이너 관리부(150) 및 컨테이너 생성부(160)를 포함하여 구성된다.

본 발명에서 컨테이너는 적어도 하나의 제어 블록을 포함하는 구조체로 이해될 수 있다. 또한, 컨테이너에는 다른 컨테이너와의 연결 관계 및 제어 블록의 재사용을 위하여 파라미터가 명시되어 있는데, 파라미터에는 연결된 다른 컨테이너의 포인터 및 구비된 모든 제어 블록에서의 작업을 완료한 스레드의 수가 포함된다.

여기서, 연결된 다른 컨테이너란 논리적으로 인접한 컨테이너로서 스레드의 작업 진행 방향에 존재하는 컨테이너를 의미한다. 즉, 스레드의 작업이 진행됨에 따라 또 다른 제어 블록이 필요하게 되는 경우 논리적으로 인접한 제어 블록에 접근하여 스레드는 작업을 수행하게 되는데, 이렇게 스레드의 작업 대상이 되는 제어 블록을 포함하는 컨테이너가 연결된 다른 컨테이너인 것이다.

또한, 구비된 모든 제어 블록에서의 작업을 완료한 스레드의 수(이하, 재사용 카운트라 한다)는 하나의 컨테이너에 포함된 모든 제어 블록에서의 작업을 완료한 후 다른 컨테이너의 제어 블록에 접근한 스레드의 수를 의미한다.

재사용 카운트는 해당 컨테이너에서의 작업을 완료하고 다른 컨테이너로 이동한 스레드에 의하여 지속적으로 갱신되는데, 만일 프로그래밍상의 모든 스레드에 의하여 해당 컨테이너에서의 작업이 완료된 경우 재사용 카운트는 초기화된다. 그리고, 초기화가 수행됨에 따라 해당 컨테이너에 포함된 제어 블록은 다른 컨테이너에서 작업 중이던 스레드의 작업 대상이 될 수 있게 된다. 즉, 제어 블록의 재사용이 가능하게 되는 것으로서, 이에 따라 메모리 자원의 낭비가 감소될 수 있게 된다.

스레드 생성부(110)는 스레드를 생성하는 역할을 한다. 여기서, 스레드는 OpenMP의 Fork-Join 모델에 따라 마스터 스레드 및 슬레이브 스레드로 구성될 수 있다.

마스터 스레드가 직렬 처리 구간에서 작업을 수행하다가 병렬 처리를 나타내는 지시어에 따라 병렬 처리 구간에 도달하게 되면, 스레드 생성부(110)에 의하여 복수 개의 슬레이브 스레드가 생성되는 것이다. 여기서, 슬레이브 스레드의 수는 사용자에 의하여 설정될 수 있다. 또한, OpenMP 규격에 따라 스레드를 생성하는 경우 스레드 생성부(110)는 OpenMP를 지원하는 컴파일러를 이용할 수 있다.

스레드는 컨테이너에 포함된 제어 블록에 접근하여 작업 분할에 필요한 정보를 읽거나 쓰는 작업을 수행하는데, 스레드 관리부(120)는 스레드에 의한 제어 블록으로의 접근을 제어하는 역할을 수행한다. 예를 들어, 하나의 제어 블록에는 복수 개의 스레드가 접근하여 작업을 수행할 수도 있는데, 이 때 복수 개의 스레드에 의하여 읽기 작업이 수행되는 것은 허용될 수 있으나 복수 개의 스레드에 의하여 쓰기 작업이 수행되는 것은 허용되지 않으므로, 스레드 관리부(120)는 복수 개의 스레드에 의한 쓰기 작업이 발생되지 않도록 스레드들을 제어하는 것이다.

또한, 스레드 관리부(120)는 스레드가 특정 제어 블록에서의 작업을 완료한 경우 다음 제어 블록으로 진행하도록 하는 역할도 수행한다. 이 때, 스레드에 의하여 작업 진행 중인 제어 블록이 컨테이너의 마지막 제어 블록인 경우, 스레드 관리부(120)는 이를 나타내는 메시지를 제어부(140)로 전달한다.

제어부(140)는 적어도 하나의 스레드에 의한 작업이 진행되는 방향에 존재하 는 컨테이너(이하, 제 1 컨테이너라 한다)에 포함된 제어 블록의 접근 가능 여부를 판단하는 역할을 한다.

이를 위하여 제어부(140)는 제 1 컨테이너의 파라미터인 재사용 카운트와 현재 프로그래밍상에서 작업 중인 스레드의 수를 비교하여 제 1 컨테이너에 포함된 제어 블록으로의 접근 가능 여부를 판단할 수 있다. 즉, 재사용 카운트가 작업 중인 스레드의 수보다 작으면 제 1 컨테이너에 포함된 제어 블록으로의 접근이 불가능한 것으로 판단하고, 재사용 카운트가 작업 중인 스레드의 수와 같으면 제 1 컨테이너에 포함된 제어 블록으로의 접근이 가능한 것으로 판단하는 것이다.

여기서, 제 1 컨테이너로의 접근이 가능하다는 것은 현재 제 1 컨테이너의 제어 블록에서 작업을 수행하는 스레드가 없으므로 제 1 컨테이너가 재사용될 수 있다는 것을 의미한다.

한편, 제 1 컨테이너로의 접근이 불가능하다는 것은 현재 제 1 컨테이너의 제어 블록에서 작업을 수행하는 스레드가 존재하는 것을 의미하므로, 새로운 컨테이너가 필요하게 된다. 이에 따라, 제어부(140)는 컨테이너 생성부(160)로 제어 명령을 전달하여 새로운 컨테이너가 생성되도록 한다.

또한, 제어부(140)는 스레드 생성부(110), 스레드 관리부(120), 저장부(130), 컨테이너 관리부(150), 컨테이너 생성부(160) 및 병렬 처리 장치(100)의 전반적인 제어를 수행한다.

컨테이너 생성부(160)는 제어부(140)의 판단 결과에 따라 적어도 하나의 제어 블록이 포함된 컨테이너를 생성하는 역할을 한다. 즉, 제어부(140)에 의하여 스 레드의 진행 방향에 존재하는 컨테이너의 재사용 카운트가 작업 중인 스레드의 수보다 작은 것이 확인되는 경우 컨테이너 생성부(160)는 새로운 컨테이너를 생성하는 것이다.

제어부(140)는 각 컨테이너의 재사용 카운트와 현재 작업 중인 스레드의 작업 진행 상황을 참조하여 새로운 컨테이너 생성의 필요 여부를 판단할 수도 있다. 예를 들어, 현재 프로그래밍상에서 작업 중인 4개의 스레드가 3개의 제어 블록에 접근하여 작업을 수행하는 경우 하나의 제어 블록이 더 필요하게 될 수 있다. 이 때, 3개의 제어 블록이 하나의 컨테이너에 포함되어 있는 경우 새로운 컨테이너의 생성은 필연적인 것으로 예상될 수 있으므로 제어부(140)는 새로운 컨테이너 생성의 필요 여부를 판단한 후 그 결과에 따라 제어 명령을 컨테이너 생성부(160)로 전달하여 새로운 컨테이너가 생성되도록 할 수 있다. 이하, 컨테이너 생성부(160)에 의하여 새롭게 생성된 컨테이너를 제 2 컨테이너라 한다.

컨테이너 관리부(150)는 제 1 컨테이너에 포함된 제어 블록 또는 제 1 컨테이너 및 제 2 컨테이너에 포함된 제어 블록이 현재 스레드가 작업 중인 제어 블록과 함께 링형으로 연결되도록 구성하는 역할을 한다. 즉, 컨테이너 관리부(150)는 각 컨테이너에 구비된 파라미터인 인접 컨테이너의 포인터를 설정하여 복수 개의 컨테이너를 링형으로 구성하는 것이다.

이 때, 생성된 컨테이너가 하나인 경우 컨테이너 관리부(150)는 해당 컨테이너의 포인터를 해당 컨테이너로 설정할 수 있다. 이에 따라, 하나의 컨테이너를 지속적으로 재사용할 수 있게 된다.

저장부(130)는 동적으로 생성된 컨테이너 구조체를 저장하는 역할을 하는데, 컨테이너 관리부(150)는 저장부(130)에 접근하여 현재 존재하고 있는 컨테이너를 관리할 수 있다. 저장부(130)는 하드 디스크, 플래시 메모리, CF 카드(Compact Flash Card), SD 카드(Secure Digital Card), SM 카드(Smart Media Card), MMC(Multimedia Card) 또는 메모리 스틱(Memory Stick) 등 정보의 입출력이 가능한 모듈로서 병렬 처리 장치(100)의 내부에 구비되어 있을 수도 있고, 별도의 장치에 구비되어 있을 수도 있다. 이 때, 저장부(130)가 별도의 장치에 구비되어 있는 경우 병렬 처리 장치(100)에는 별도의 장치와 통신을 수행할 수 있는 통신부(미도시)가 구비될 수 있다.

도 2는 본 발명의 실시예에 따른 컨테이너를 나타낸 도면으로서, 컨테이너(200)는 일련의 제어 블록(210, 220, 230)을 포함하고, 파라미터로서 다음 컨테이너의 포인터(241) 및 재사용 카운트(242)를 포함하여 구성된다.

작업 분할에 필요한 작업을 수행하기 위하여 스레드는 제어 블록(210, 220, 230)에 접근하게 되는데, 스레드 관리부(120)의 제어에 따라 스레드는 컨테이너(200)에 구비된 제어 블록(210, 220, 230)을 순차적으로 접근하게 된다. 예를 들어, 스레드는 제어 블록 1(210), 제어 블록 2(220), 제어 블록 3(2300의 순서로 접근할 수 있는 것이다.

그리고, 제어부(140)의 판단 결과에 따라 스레드는 연결된 다른 컨테이너에 구비된 제어 블록에 접근하여 작업을 수행할 수 있는데, 이 때 다음 컨테이너의 포인터(241)에 명시된 컨테이너의 제어 블록에 접근할 수 있다. 한편, 도 2는 다음 컨테이너와의 연결 관계(250)가 회귀하는 것으로 도시되어 있는데, 이는 존재하는 컨테이너가 하나인 것 즉, 최초로 생성된 컨테이너임을 의미한다.

도 3은 본 발명의 실시예에 따른 컨테이너의 프로그래밍 코드(300)로서, 구조체 형식의 컨테이너를 나타내고 있다.

컨테이너(310)에는 구조체 형식의 제어 블록의 행렬(320)이 명시되며, 컨테이너에 포함되는 제어 블록의 수(330)가 명시된다. 또한, 다음 컨테이너의 포인터(340) 및 재사용 카운터(350)가 파라미터로서 컨테이너(310)에 명시된다.

결국, 컨테이너 생성부(160)는 이와 같은 컨테이너 구조체(300)를 동적으로 생성하는 것으로서, 다음 컨테이너의 포인터(340) 및 재사용 카운터(350)는 컨테이너 관리부(150)에 의하여 갱신된다.

도 4는 본 발명의 실시예에 따라 복수 개의 컨테이너가 링형으로 연결된 것을 나타낸 도면이다. 도시된 바와 같이, 복수 개의 컨테이너(410, 420, 430, 440, 450, 460)는 링형으로 서로 연결되어 있다.

컨테이너 관리부(150)는 각 컨테이너의 파라미터인 다음 컨테이너의 포인터를 설정함으로써 도 4와 같은 링형의 컨테이너 그룹을 구성하는 것이다.

예를 들어, 컨테이너 관리부(150)는 컨테이너 1(410)의 다음 컨테이너를 컨테이너 2(420)로 설정하고, 컨테이너 2(420)의 다음 컨테이너를 컨테이너 3(430)로 설정하며, 마지막으로 컨테이너 6(460)의 다음 컨테이너를 컨테이너 1(410)로 설정하는 것이다.

제어부(140)의 판단 결과에 따라 새로운 컨테이너의 생성이 요구되는 경우 새로운 컨테이너인 컨테이너 N(470)이 컨테이너 생성부(160)에 의하여 생성되고, 이는 링형의 컨테이너 그룹에 참여하게 된다. 즉, 컨테이너 관리부(150)는 이전에 존재하고 있던 컨테이너(410, 420, 430, 440, 450, 460) 중 하나의 다음 컨테이너를 컨테이너 N(470)으로 설정하고, 컨테이너 N(470)의 다음 컨테이너를 이전에 존재하고 있던 컨테이너 중 다른 하나로 설정하는 것이다.

예를 들어, 컨테이너 N(470)이 컨테이너 4(440)와 컨테이너 5(450)의 사이에 삽입되는 경우 컨테이너 관리부(150)는 컨테이너 4(440)의 다음 컨테이너를 컨테이너 N(470)으로 설정하고, 컨테이너 N(470)의 다음 컨테이너를 컨테이너 5(450)로 설정하는 것이다.

새로운 컨테이너 N(470)의 삽입 위치는 임의로 결정될 수 있다. 예를 들어, 컨테이너 4(440)의 제어 블록에서 작업 중이던 스레드가 다른 컨테이너의 제어 블록으로 이동하고자 하는 경우 다른 컨테이너(410, 420, 430, 450, 460)의 제어 블록이 다른 스레드에 의하여 작업 중에 있으면 새로운 컨테이너 N(470)의 생성이 요구되는데, 새롭게 생성된 컨테이너 N(470)는 컨테이너 4(440)와 컨테이너 5(450)의 사이에 삽입될 수 있으며 다른 위치에 삽입될 수도 있는 것이다. 다시 말해, 컨테이너 N(470)은 컨테이너 5(450)와 컨테이너 6(460)의 사이에 삽입되거나 컨테이너 1(410)과 컨테이너 2(420)의 사이에 삽입될 수도 있는 것이다.

컨테이너 N(470)이 컨테이너 4(440)와 컨테이너 5(450)의 사이에 삽입된 경우가 아니더라도, 스레드 관리부(120)는 컨테이너 4(440)에서 작업 중이던 스레드가 컨테이너 N(470)에 포함된 제어 블록으로 접근할 수 있도록 하므로, 컨테이너 N(470)의 삽입 위치는 다른 컨테이너로 이동하고자 하는 스레드의 위치에 구애 받지 않을 수 있다.

도 5는 본 발명의 실시예에 따른 컨테이너에 포함된 복수 개의 제어 블록에 복수 개의 스레드가 접근한 것을 나타낸 도면으로서, 4개의 스레드(510, 520, 530, 540)가 컨테이너 1(610)에 구비된 3개의 제어 블록에 각각 접근한 것은 나타낸 도면이다.

도시된 바와 같이, 각 스레드(510, 520, 530, 540)는 하나의 제어 블록에 접근할 수 있으며, 하나의 제어 블록에 둘 이상의 스레드가 접근할 수도 있다. 즉, 스레드 3(530)과 스레드 4(540)는 각각 하나의 제어 블록에 접근하였지만, 스레드 1(510)과 스레드 2(520)는 하나의 제어 블록에 접근할 수 있는 것이다. 이 때, 스레드 1(510)과 스레드 2(520)는 읽기 작업을 동시에 수행할 수는 있지만, 쓰기 작업은 스레드 관리부(120)에 의하여 지정된 하나의 스레드에 의해서만 수행될 수 있다.

각 스레드는 구비된 모든 제어 블록에 접근하여 작업을 수행하며 마지막 위치에 존재하는 제어 블록에서의 작업을 완료한 스레드는 다른 컨테이너의 제어 블록으로 이동하여 작업을 계속 수행하게 된다.

도 5에서 다음 컨테이너의 포인터는 자신을 가리키고 있고 이에 따라 다음 컨테이너와의 연결 관계가 회귀하는 것으로 도시되어 있는데, 이는 존재하는 컨테이너가 하나인 것 즉, 최초로 생성된 컨테이너임을 의미하며, 재사용 카운트가 0으로 표시되어 있는 것은 컨테이너 1(610)에 구비된 모든 제어 블록에서의 작업을 완 료한 스레드가 하나도 없음을 의미한다.

이 때, 스레드 1, 2, 3, 4(510, 520, 530, 540)중 하나가 작업을 완료하고 다른 제어 블록으로 이동하고자 하는 경우 현재 컨테이너 1(610)에 구비된 제어 블록은 작업 중에 있으므로 새로운 컨테이너의 생성이 요구된다.

도 6은 본 발명의 실시예에 따라 제어 블록이 재사용되는 것을 나타낸 도면으로서, 2개의 컨테이너(610, 620)가 링형으로 구성되고 4개의 스레드(510, 520, 530, 540)가 2개의 컨테이너(610, 620)에 구비된 제어 블록에 접근하여 작업을 수행하는 것을 나타낸 도면이다.

스레드 1, 2, 3, 4(510, 520, 530, 540)는 컨테이너 1(610)에 구비된 제어 블록에서 작업을 수행하다가, 컨테이너 1(610)에서의 작업을 완료한 스레드 1, 2, 3, 4(510, 520, 530, 540)가 새롭게 생성된 컨테이너 2(620)로 이동하여 작업을 수행하게 된다. 그리고, 스레드 1, 2, 3, 4(510, 520, 530, 540)가 컨테이너 1(610)에서 컨테이너 2(620)로 이동을 함에 따라 컨테이너 1(610)의 재사용 카운터는 4가 된다.

이 때, 스레드 2(520)가 컨테이너 2(620)에서의 작업을 모두 마치는 시점에 제어부(140)는 컨테이너 2(620)에 연결된 컨테이너 즉, 컨테이너 1(610)의 재사용 카운트를 확인한다. 그리하여, 컨테이너 1(610)의 재사용 카운트가 4이고, 현재 프로그램이상에서 동작 중인 스레드(510, 520, 530, 540)의 수가 4이므로 컨테이너 관리부(150)는 컨테이너 1(610)의 재사용 카운트를 초기화하여 0으로 갱신한다.

이에 따라, 스레드 2(520)는 컨테이너 1(610)의 제어 블록에 접근하여 작업 을 수행할 수 있게 된다. 도 6은 이를 나타낸 도면으로서, 컨테이너 관리부(150)에 의하여 컨테이너 1(610)의 파라미터가 초기화됨에 따라 그 재사용 카운트가 0이 된 것을 나타내고 있으며, 스레드 2(520)가 컨테이너 2(620)에서의 작업을 완료하고 컨테이너 1(610)로 이동함에 따라 컨테이너 2(620)의 재사용 카운트가 1이 된 것을 나타내고 있다.

도 7은 본 발명의 실시예에 따라 컨테이너가 생성된 것을 나타낸 도면으로서, 컨테이너 1 (610)및 컨테이너 2(620)가 구비된 상태에서 스레드 1, 2, 3, 4(510, 520, 530, 540)가 작업을 진행함에 따라 컨테이너 3(630)이 새롭게 생성되어 링형의 컨테이너 그룹에 삽입된 것을 나타낸 도면이다.

우선, 스레드 1, 2, 3, 4(510, 520, 530, 540)는 컨테이너 1(610)에 구비된 제어 블록에 접근하여 작업을 수행한다. 그러다가 스레드 2, 3, 4(520, 530, 540)가 컨테이너 2(620)의 제어 블록으로 이동하고 이에 따라 컨테이너 1(610)의 재사용 카운트는 3으로 갱신된다.

그리고, 컨테이너 2(620)의 제어 블록에서 작업을 수행 중이던 스레드 2, 3, 4(52, 530, 540)중 스레드 2(520)가 컨테이너 2(620)에서의 작업을 완료하게 되면 스레드 2(520)는 다른 컨테이너의 제어 블록으로 이동하게 되는데, 이 때 연결된 컨테이너인 컨테이너 1(610)의 제어 블록이 스레드 1(510)에 의하여 작업 중에 있으므로 제어부(140)는 컨테이너 생성부(160)로 하여금 새로운 컨테이너를 생성하게 한다.

그리하여, 새롭게 생성된 컨테이너 3(630)이 컨테이너 그룹에 참여하게 되 고, 스레드 2(520)는 컨테이너 3(630)에 구비된 제어 블록으로 이동하여 작업을 수행하게 된다. 이 때, 컨테이너 2(620)의 재사용 카운트는 스레드 2(520)가 컨테이너 3(630)으로 이동함에 따라 1로 갱신된다.

도 8은 본 발명의 실시예에 따른 병렬 처리 과정을 나타낸 흐름도이다. 병렬 처리를 수행하기 위하여 스레드 생성부(110)는 우선 스레드를 생성한다(S810). 스레드 생성부(110)에 의하여 생성되는 스레드는 마스터 스레드 및 슬레이브 스레드를 포함하는데, 마스터 스레드가 작업을 수행하다가 병렬 처리 구간을 만나게 되면 스레드 생성부(110)는 병렬 처리 작업에 대응하는 개수의 슬레이브 스레드를 생성한다.

스레드가 생성되면 컨테이너 생성부(160)는 적어도 하나의 제어 블록이 포함된 컨테이너를 생성한다(S820). 여기서, 생성되는 컨테이너는 최초로 생성되는 컨테이너로서, 그 파라미터인 다음 컨테이너의 포인터는 자신을 가리키도록 설정된다.

컨테이너가 생성됨에 따라, 스레드는 생성된 컨테이너의 제어 블록에 접근하여 읽기 또는 쓰기 작업을 수행한다(S830). 하나의 제어 블록에서의 작업을 완료한 스레드는 다음 제어 블록으로 이동하여 작업을 진행하는데, 본 발명에서의 프로그래밍 코드는 NOWAIT 명령어가 프로그램 내에 명시되어 있는 것을 가정하므로, 암시적 장벽은 제거되어 각 스레드는 대기 없이도 바로 이후 작업으로 진행할 수 있게 된다.

복수 개의 컨테이너가 생성되고, 그 중 하나의 컨테이너에 구비된 모든 제어 블록에서의 작업을 완료한 스레드가 발생함에 따라, 제어부(140)는 작업 진행 방향의 제어 블록으로으로 스레드가 접근 가능한지 확인한다(S840). 이 때, 제어부(140)는 작업 진행 방향에 존재하는 컨테이너의 재사용 카운트와 현재 프로그래밍상에서 작업 진행 중인 스레드의 수 즉, 슬레이브 스레드의 수를 비교하여 접근 가능 여부를 확인할 수 있다.

이 때, 제어부(140)는 컨테이너의 재사용 카운트와 현재 작업 진행 중인 스레드의 수를 비교하는데, 현재 작업 진행 중인 스레드의 수가 재사용 카운트보다 큰 경우 작업 진행 방향의 제어 블록으로의 접근이 불가능한 것으로 판단하여 컨테이너 생성부(160)로 하여금 새로운 컨테이너를 생성하게 한다.

제어부(140)의 제어 명령에 따라 컨테이너 생성부(160)는 새로운 컨테이너를 생성한다(S850). 새롭게 생성된 컨테이너는 컨테이너 관리부(150)에 의하여 기 구성된 링형의 컨테이너 그룹에 참여하게 되는데, 이 때 삽입되는 위치는 임의로 결정될 수 있다.

그리고, 컨테이너 관리부(150)는 기 존재하는 컨테이너의 파라미터 및 새롭게 삽입되는 컨테이너의 파라미터를 설정하여 모든 컨테이너가 링형이 되도록 구성한다(S860).

새로운 컨테이너가 링형 컨테이너 그룹에 삽입됨에 따라 다른 컨테이너로 이동하고자 하는 스레드는 삽입된 컨테이너의 제어 블록에 접근하여 작업을 진행할 수 있다(S870).

한편, 제어부(140)는 별도의 스레드를 이용하여 각 컨테이너의 파라미터인 재사용 카운트와 작업 중인 스레드의 작업 진행 상황을 참조하여 새로운 컨테이너 생성의 필요 여부를 판단할 수 있다. 그리하여, 새로운 컨테이너의 생성이 필요하다고 판단하는 경우 다른 컨테이너로 이동하고자 하는 스레드가 발생하지 않더라도 컨테이너 생성부(160)로 하여금 새로운 컨테이너를 생성하게 하고, 컨테이너 관리부(150)로 하여금 컨테이너 그룹에 삽입하도록 한다. 이에 따라, 컨테이너 생성에 따른 오버헤드를 분산할 수 있게 된다.

이상 첨부된 도면을 참조하여 본 발명의 실시예를 설명하였지만, 본 발명이 속하는 기술분야에서 통상의 지식을 가진 자는 본 발명이 그 기술적 사상이나 필수적인 특징을 변경하지 않고서 다른 구체적인 형태로 실시될 수 있다는 것을 이해할 수 있을 것이다. 그러므로 이상에서 기술한 실시예들은 모든 면에서 예시적인 것이며 한정적이 아닌 것으로 이해해야만 한다.

상기한 바와 같은 본 발명의 병렬 처리 장치에 따르면 다음과 같은 효과가 하나 혹은 그 이상 있다.

첫째, 복수 개의 작업이 병렬 처리되는 경우 작업 분할 제어 블록을 동적으로 생성함에 있어서 그 재사용성을 향상시킴으로써, 메모리의 낭비를 방지하는 장점이 있다.

둘째, 스레드의 동기화를 수행하지 않으므로 지연 시간의 발생을 방지하는 장점도 있다.

Claims (20)

1. 적어도 하나의 스레드에 의한 작업이 진행되는 방향에 존재하는 제 1 컨테이너에 포함된 제어 블록으로의 접근 가능 여부를 판단하는 제어부;

   상기 판단 결과에 따라 적어도 하나의 제어 블록이 포함된 제 2 컨테이너를 생성하는 컨테이너 생성부; 및

   상기 제 1 컨테이너에 포함된 제어 블록 또는 상기 제 1 컨테이너 및 상기 제 2 컨테이너에 포함된 제어 블록이 상기 스레드가 작업 중인 제어 블록과 함께 링형으로 연결되도록 구성하는 컨테이너 관리부를 포함하는데,

   상기 제 1 컨테이너 및 상기 제 2 컨테이너는 연결된 다른 컨테이너의 포인터 및 구비된 모든 제어 블록에서의 작업을 완료한 스레드의 수를 파라미터로 갖는 병렬 처리 장치.
2. 삭제
3. 제 1항에 있어서,

   상기 컨테이너 관리부는 상기 포인터를 설정하여 상기 제 1 컨테이너에 포함된 제어 블록 또는 상기 제 1 컨테이너 및 상기 제 2 컨테이너에 포함된 제어 블록이 상기 스레드가 작업 중인 제어 블록과 함께 링형으로 연결되도록 구성하는 병렬 처리 장치.
4. 제 1항에 있어서,

   상기 제어부는 상기 제 1 컨테이너의 파라미터인 작업을 완료한 스레드의 수와 상기 작업 중인 스레드의 수를 비교하여 상기 제 1 컨테이너에 포함된 제어 블록으로의 접근 가능 여부를 판단하는 병렬 처리 장치.
5. 제 4항에 있어서,

   상기 제어부는 상기 제 1 컨테이너의 파라미터인 작업을 완료한 스레드의 수가 상기 작업 중인 스레드의 수보다 작으면 상기 제 1 컨테이너에 포함된 제어 블록으로의 접근이 불가능한 것으로 판단하는 병렬 처리 장치.
6. 제 1항에 있어서,

   상기 제어부는 상기 제 1 컨테이너의 파라미터인 작업을 완료한 스레드의 수와 상기 작업 중인 스레드의 작업 진행 상황을 참조하여 상기 제 2 컨테이너 생성의 필요 여부를 판단하는 병렬 처리 장치.
7. 제 6항에 있어서,

   상기 제어부는 별도의 스레드를 이용하여 상기 제 1 컨테이너의 파라미터인 작업을 완료한 스레드의 수와 상기 작업 중인 스레드의 작업 진행 상황을 확인하는 병렬 처리 장치.
8. 제 1항에 있어서,

   상기 컨테이너 생성부는 제 1 컨테이너에 포함된 제어 블록으로의 접근이 불 가능한 것으로 판단되는 경우 상기 제 2 컨테이너를 생성하는 병렬 처리 장치.
9. 제 1항에 있어서,

   상기 스레드는 마스터 스레드로부터 복수 개로 분기된 슬레이브 스레드를 포함하는 병렬 처리 장치.
10. 제 9항에 있어서,

    상기 마스터 스레드 및 상기 슬레이브 스레드를 생성하는 스레드 생성부를 더 포함하는 병렬 처리 장치.
11. 적어도 하나의 스레드에 의한 작업이 진행되는 방향에 존재하는 제 1 컨테이너에 포함된 제어 블록으로의 접근 가능 여부를 판단하는 단계;

    상기 판단 결과에 따라 적어도 하나의 제어 블록이 포함된 제 2 컨테이너를 생성하는 단계; 및

    상기 제 1 컨테이너에 포함된 제어 블록 또는 상기 제 1 컨테이너 및 상기 제 2 컨테이너에 포함된 제어 블록이 상기 스레드가 작업 중인 제어 블록과 함께 링형으로 연결되도록 구성하는 단계를 포함하는데,

    상기 제 1 컨테이너 및 상기 제 2 컨테이너는 연결된 다른 컨테이너의 포인터 및 구비된 모든 제어 블록에서의 작업을 완료한 스레드의 수를 파라미터로 갖는 병렬 처리 방법.
12. 삭제
13. 제 11항에 있어서,

    상기 링형으로 연결되도록 구성하는 단계는 상기 포인터를 설정하여 상기 제 1 컨테이너에 포함된 제어 블록 또는 상기 제 1 컨테이너 및 상기 제 2 컨테이너에 포함된 제어 블록이 상기 스레드가 작업 중인 제어 블록과 함께 링형으로 연결되도록 구성하는 단계를 포함하는 병렬 처리 방법.
14. 제 11항에 있어서,

    상기 접근 가능 여부를 판단하는 단계는 상기 제 1 컨테이너의 파라미터인 작업을 완료한 스레드의 수와 상기 작업 중인 스레드의 수를 비교하여 상기 제 1 컨테이너에 포함된 제어 블록으로의 접근 가능 여부를 판단하는 단계를 포함하는 병렬 처리 방법.
15. 제 14항에 있어서,

    상기 접근 가능 여부를 판단하는 단계는 상기 제 1 컨테이너의 파라미터인 작업을 완료한 스레드의 수가 상기 작업 중인 스레드의 수보다 작으면 상기 제 1 컨테이너에 포함된 제어 블록으로의 접근이 불가능한 것으로 판단하는 단계를 포함하는 병렬 처리 방법.
16. 제 11항에 있어서,

    상기 제 1 컨테이너의 파라미터인 작업을 완료한 스레드의 수와 상기 작업 중인 스레드의 작업 진행 상황을 참조하여 상기 제 2 컨테이너 생성의 필요 여부를 판단하는 단계를 더 포함하는 병렬 처리 방법.
17. 제 16항에 있어서,

    상기 제 2 컨테이너 생성의 필요 여부를 판단하는 단계는 별도의 스레드를 이용하여 상기 제 1 컨테이너의 파라미터인 작업을 완료한 스레드의 수와 상기 작업 중인 스레드의 작업 진행 상황을 확인하는 단계를 포함하는 병렬 처리 방법.
18. 제 11항에 있어서,

    상기 제 2 컨테이너를 생성하는 단계는 제 1 컨테이너에 포함된 제어 블록으로의 접근이 불가능한 것으로 판단되는 경우 상기 제 2 컨테이너를 생성하는 단계를 포함하는 병렬 처리 방법.
19. 제 11항에 있어서,

    상기 스레드는 마스터 스레드로부터 복수 개로 분기된 슬레이브 스레드를 포함하는 병렬 처리 방법.
20. 제 19항에 있어서,

    상기 마스터 스레드 및 상기 슬레이브 스레드를 생성하는 단계를 더 포함하는 병렬 처리 방법.

Images