KR20090006147A

KR20090006147A - 병렬 프로그램 생성 방법

Info

Publication number: KR20090006147A
Application number: KR1020087026647A
Authority: KR
Inventors: 유하나 헬로프오
Original assignee: 아토스텍 오이
Priority date: 2006-03-30
Filing date: 2006-03-30
Publication date: 2009-01-14
Anticipated expiration: 2026-03-30
Also published as: KR101279179B1; US20100306750A1; EP2016489A1; EP2016489A4; WO2007113369A1; US8527971B2

Abstract

정의되지 않은 실행 오더를 갖는 실행가능 컴퓨터 프로그램을 생성하는 컴파일 방법을 이용하여 병렬 컴퓨터 프로그램을 생성하는 방법에 관한 것이다. 실행 오더는 실행 아키텍처에 종속적인 프로그램의 실행 동안 정의된다. 이것은 상이한 아키텍처에서 가능한 가장 좋은 레벨의 동시 실행을 허용한다. 컴파일 방법은 실행가능한 코드 생성에 사용되는 데이터 종속성 및데이터 플로우 그래프를 생성하는 단계를 포함한다.

Description

병렬 프로그램 생성 방법{PARALLEL PROGRAM GENERATION METHOD}

본 발명은 병렬 프로그램 생성에 관한 것이다. 본 발명은 특히, 컴퓨터가 복수의 명령(instruction)을 동시에 실행할 수 있도록, 복수의 프로세서 또는 하나의 프로세서 내에 복수의 프로세싱 유닛 또는 코어를 가진 컴퓨터를 위한 컴퓨터 프로그램의 생성에 관한 것이다.

초기에는 컴퓨터에 순차 프로그램을 실행할 수 있는 단 하나의 프로세서만 있었다. 새로운 프로세서가 제작되었는데, 이 프로세서가 대체로 더 빨랐다. 이것은 초당 더 많은 명령을 실행할 수 있도록 프로세서의 클럭 주파수를 올림으로써 달성되었다. 또 다른 중요한 방법은, 실행할 명령들이 더 적은 클럭 사이클을 필요로 하도록 프로세서의 명령 세트를 최적화하는 것이었다. 그러나, 이것은 연산 필요의 증가로 인해 곧 부적절하다고 인식되었다.

이 문제는 병렬 연산 환경의 도입으로 접근되어 왔다. 여러 다른 접근 방법들이 존재한다. 전통적인 접근법들은, 다중의 연산 노드(node)를 갖는 연산 네트워크와 하나의 컴퓨터 내에 다중의 프로세서를 갖는 것을 포함한다. 최근에는 하나의 프로세서 내에 다중의 연산 유닛을 갖는 새로운 프로세서들이 도입되었다. 하나의 연산 유닛은 여러 개의 명령을 동시에 실행할 수가 있다. 이들을 조합함으로써, 다 중의 명령을 동시에 실행할 수 있는 복수의 프로세서를 노드 컴퓨터가 포함하고 있는 연산 네트워크를 구성할 수 있다. 노드 컴퓨터는 수십 개의 명령를 동시에 실행할 수 있고, 이 수는 앞으로 증가할 것으로 기대된다. 가장 큰 연산 네트워크는 수천 대의 컴퓨터를 포함한다. 그래서, 연산 내트워크는 수만 개 이상의 명령들을 동시에 실행할 수 있을 것이다.

명령들의 효율적인 병렬 실행을 허용하려면, 이러한 컴퓨터들의 프로그램들은 병렬로 실행되도록 설계되어야 한다. 이 문제를 극복하는 두 가지 서로 다른 전통적인 해법이 있다. 컴파일을 행하면서 순차 프로그램을 자동으로 병렬화하는 것이 가능하다. 더 좋은 해법은, 서로 통신할 수 있는 복수의 순차 프로그램들을 실제로 포함하도록 프로그램을 설계하여 실제 작업이 병렬로 실행되도록 하는 것이다. 그러나, 이 경우에도, 이 순차 프로그램들은 순차적인 것이고, 가능한 최고의 결과를 얻기 위해 더 병렬화되어야 한다.

자동 병렬화의 일 예는, 예를 들어 US6622302에 개시되어 있다. 이 해법의 결점은 순차 프로그램의 병렬화가 매우 어려운 작업이라는 것이다. 그래서, 이 작업은 시간 및 자원 소모적이며, 완벽한 해법에 도달하는 것은 여전히 불가능하다. 이 때문에, 자동 병렬화와 다른 자동 최적화는 코드의 품질과 자원의 활용 사이에서 절충된다.

복수의 순차 프로그램이 사용되는 전통적인 동시 프로그래밍의 예들은, 예를 들어 그레고리 알. 앤드류가 집필하여 에디슨-웨슬리에서 1991년에 출간된 "동시 프로그래밍: 원리와 실제"에서 볼 수 있다. 이 방법의 결점은 프로그램의 설계 과 정이 더 복잡하고 시간 소모적이며, 특별한 지식을 필요로 한다는 것이다.

이 방법들은 조합을 할 수 있다. 그 한 예가 US6993753에 개시되었었다. 그러나, 이 조합은 이러한 방법들의 근본적인 문제를 해결하지 못한다.

본 발명의 목적은 병렬 프로그램을 생성하는 새롭고 효율적인 방법과 이 방법을 실행하는 툴을 제공하는 것이다.

본 발명은 독립 청구항 1의 특징부에 따라 컴퓨터 프로그램을 소스 코드로부터 실행가능한 코드로 컴파일하는 방법을 개시한다. 본 발명은 독립 청구항 7 및 13에 따라 소프트웨어 제품 및 장치로서 실시될 수 있다. 다른 실시예들은 종속항들에 개시되어 있다.

이 방법에서는 먼저 소스 코드가 생성된다. 소스 코드는 프로그래머나 프로그래밍 툴에 의해 생성될 수 있다. 생성된 소스 코드는, 실행 오더가 정해져야 하는 그러한 서로 간의 데이터 종속성이 있는 명령들 사이에서만 실행 오더가 정의되도록 된 것이다. 그러한 종속성의 한 예는, 다음 연산의 입력으로서 사용될 결과를 생성하는 연산이다. 나머지 명령들에 대한 실행 오더는 실행가능 프로그램이 연산 장치에서 실행될 때까지 정의되지 않은 상태로 있는다. 만일 연산 장치의 아키텍처가 실행 시간(run time)에 실행 오더를 정의하는 것을 허용하지 않으면, 실행 오더는 컴파일의 마지막 단계로서 결정될 수 있다. 이때 실행 오더는 연산 장치의 성능에 따라 결정된다. 또한, 본 발명은 그러한 실행가능한 형태를 생성하는 컴퓨터 소프트웨어 제품을 개시한다.

일 실시예에서, 실행가능한 형태은 하기의 단계들을 수행함으로써 소스 코드에 의해 생성된다. 먼저, 추상 파스 트리(abstract parse tree)를 정의하기 위해 소스 코드가 파싱된다. 그 다음,데이터 플로우 및데이터 종속성 그래프를 정의하기 위해 추상 파스 트리가 합성된다. 그 다음, 오더링 제약(ordering constraints)을 형성하기 위해 이 그래프가 머신 데이터 플로우 그래프로 리파인(refined)된다. 그 다음, 부분 실행 오더가 오더링 제약의 제1 부분으로써 정의되게 되는데, 오더링 제약의 이 제1 부분은 데이터 플로우 및 종속 그래프에서의 종속성들을 만족시키기 위해 필요한 오더링 제약으로 구성된다. 그 다음, 오더링 제약의 제2 부분을 추가함으로써 머신 데이터 플로우 그래프에 있는 명령들이 병렬 실행가능한 코드로 그룹화되는데, 오더링 제약의 이 제2 부분은 머신 데이터 플로우 그래프를 연산 장치로 매핑하기 위해 필요한 오더링 제약으로 구성된다. 마지막으로, 실행가능한 형태가 생성된다.

일반적인 경우에는 코드의 몇몇 부분들이 종속성들을 따르도록 어떤 오더로 실행되어야 한다. 코드의 몇몇 부분들은, 이 종속성들에 의해 오더가 정해지지 않으며, 병렬적으로 실행될 수 있다. 병렬 실행가능한 코드는 명령들과 이들 사이의 오더링 제약으로 구성된다. 명령들은 연산 단계들이 어떤 것인지를 기술한다. 오더링 제약은 명령들이 어떤 오더로 실행되어야 하는지를 기술한다. 오더링 제약의 일부분은 소스 프로그램에 의해 규정되며, 프로그램을 실행 하드웨어에 맞추기 위해 오더링 제약의 제2 부분이 필요할 수 있다. 이 두 부분들 간의 분리를 유지함으로써, 실행 오더를 가능한 늦게 결정하는 것과 병렬성의 정도(degree of parallelism)를 증가시키는 것이 가능하다.

선행 기술의 해법에서는, 실행 오더가 조기에 결정되고, 오더링 제약의 두 부분 사이의 구분이 이루어지지 않는다. 자동화된 최적화는 이미 결정된 이들 실행 오더 제약들의 일부를 제거하는 것을 기초로 한다. 안전한 제약 제거의 선행 조건은 제약들을 상기의 두 부분들로 분류하는 것이다. 이것은 매우 복잡한 작업이다. 본 발명의 혜택은, 이 오더링 제약을 제거할 필요가 없고, 매우 복잡한 작업을 피할 수 있다는 것이다. 그래서, 생성된 실행가능한 것의 효율성 증가와 더불어, 컴파일 과정의 단순화에 따라 실행가능한 것의 생성의 증가도 있다.

본 발명의 다른 혜택은, 병렬 연산 장치의 최대 성능을 이용할 수 있는 병렬 프로그램을 생성하는 것이 더 쉬어진다는 것이다. 이 동일한 소스 코드는, 많은 다른 명령들을 동시에 실행시킬 수 있는 다른 장치들에서 양호한 성능을 보일 것이다.

본 발명에 대한 더 깊은 이해를 제공하기 위해 포함되고, 본 명세서의 일부분을 구성하는 첨부 도면들은 본 발명의 원리를 설명하는 도움 설명과 함께 본 발명의 실시예들을 도시한다.

도 1은 본 발명에 따른 컴파일 방법의 흐름도이다.

도 2는 본 발명에 따른 병렬 연산의 레벨을 도시한다.

도 3은 본 발명에 따른 컴파일 방법을 도시한다.

도 4는 본 발명에 따른 리파인 과정을 도시한다.

이제 본 발명의 실시예들을 상세히 살펴보게 되는데, 발명의 예들은 첨부 도면에 도시되어 있다.

도 1에 본 발명에 따른 컴파일 방법의 흐름도가 도시되어 있다. 도 1에서 컴퓨터 프로그램(10)의 소스 코드는 본 발명에 따른 컴파일 과정(11)을 이용하여 컴파일된다. 컴파일 과정은 추상 파스 트리(13)의 형성으로써 시작된다. 추상 파스 트리의 형성은 종래의 방법들과 유사하다. 컴파일 과정 중에 먼저 데이터 플로우 및 데이터 종속성 그래프(14)가 형성된다. 그 다음, 이 그래프는 머신 데이터 플로우 그래프(15)를 형성하기 위해 리파인된다. 이들 그래프에 기초하여, 컴파일 과정은 프로그램의 실행가능한 병렬 형식을 생성한다. 이것은, 특정한 실행 오더를 강제하는 종속성들을 갖지 않는 블록들이 특정한 실행 오더 없이 유지되도록, 코드의 명령들을 그룹화함으로써 달성된다. 실행 오더는 나중에 연산 장치에서 프로그램이 실행될 때 결정된다. 특정한 실행 오더를 정의하는 일은 자동으로, 또는 프로그래머에 의해 이루어질 수 있다. 어떤 오더로 실행되어야 하는 명령들을 찾기 위해, 종속 그래프를 분석하는 것이 가능하다. 또한, 순차 형식으로 컴파일 되어야 하는 소스 코드의 일부를 나타내는 다른 명령들을 프로그래밍 언어에 추가하는 것이 가능하다.

도 2에는 순차 오더와 부분적으로 동시적인 오더들 사이의 차이가 도시되어 있다. 본 발명의 목표는 가능한 한 병렬적인 오더가다. 경우 (a)는 전통적인 방법을 설명하는데, 여기에서는 프로그램이 완전히 순차적이다. 경우 (b)는 좀 더 병렬 적인 실행을 포함하지만, 본 발명의 목적은 경우 (c)에 따라 최대로 병렬적인 프로그램을 생성하는 것이다.

도 3은 본 발명에 따른 방법의 예제 동작을 개시한다. 본 발명에 따른 방법은 입력으로서 사용될 소스 코드(31)를 필요로 한다. 소스 코드(31)는 인간 판독형 텍스트 포맷으로 된 일반적인 소스 코드로서, 캐릭터 및 상이한 기호(34)들로 형성된 프로그래밍 언어 명령들을 포함한다. 그 후, 소스 코드(31)는 파싱되어 추상 파스 트리(32)로 변화된다. 그 후, 이 추상 파스 트리(32)는, 프로그램의 명령들과 상수 값들이 그래프의 노드(36)들에 의해 나타내어지도록 데이터 플로우 및 데이터 종속성 그래프(33)에 합성된다. 데이터 값들의 임시 저장을 위해 사용되는 변수들은 노드들 사이의 데이터 종속성(37, 38) 또는 데이터 플로우로 나타내어진다. 데이터 종속성들과 데이터 플로우들은 명칭이 부여되거나(38) 부여되지 않을 수 있다(37). 데이터 종속성 및데이터 플로우 그래프에서, 노드들은 연산 작업이고, 노드들 사이의 아치형 선들은 노드와 필요한 연산 명령 사이의데이터 이동을 나타낸다.

도 4는 본 발명에 따른 리파인 단계를 도시한다. 이 단계에서, 그래프(33)는, 단일 기계어 명령으로 변형될 수 없는 작업들을 나타내는 경우, 더 작은 부분들로 분기(split)하게 된다. 분기 시에 제거되는 임의의 명령은 기계어 명령들의 그룹에 의해 교체되는데, 이 그룹은 동일한 기능을 수행하도록 마련된다. 또한, 두 개의 머신 레벨 명령들(43, 411)이 직접적인 종속성을 가지면, 저장 위치(45)가 정의된다. 그러면, 저장 위치(45)는, 나중의 종속 작업(411)이 결과 값을 입력으로서 사용할 수 있도록, 제1 작업(43)에 의해 생성된 결과 값을 저장하는데 사용된다.

분기 과정의 결과로, 머신 데이터 종속성 그래프(41)가 얻어진다. 이것은 머신 레벨 명령(43, 411), 저장 위치(45), 머신 레벨 명령과 저장 위치 사이의 기준 종속성(44), 및 작업들 사이의 오더지정 제약(46)들을 포함한다. 머신 레벨 명령들은 프로그램이 어떤 연산을 포함하는지를 정의한다. 저장 위치들은 프로그램이 어느 저장 위치들을 사용하는지를 정의한다. 기준 종속성은 각 머신 레벨 명령이 어느 위치로부터데이터를 복원하고 각 명령이 어느 위치에데이터를 저장하는지를 정의한다. 오더링 제약은 명령들의 실행 오더에 대한 조건들을 정의한다.

마지막으로, 머신 데이터 종속성 그래프(41)를 병렬 머신 레벨 코드(42)로 그룹화함으로써 실행가능 프로그램이 생성된다. 머신 레벨 코드(42) 표현은 머신 코드 명령 그룹(47)들의 시퀀스를 포함한다. 각 그룹은 동시에 실행될 수 있는 적어도 하나의 머신 코드 명령(48)을 포함한다. 한 그룹 내에서는 명령들이 동시에 또는 정의되지 않은 오더로 실행되도록 정의될 수 있다. 그룹들은 도입되는 오더(49)로 실행된다. 일부 경우에는 타겟 아키텍처가 그룹들의 크기가 동일할 것을 요구한다. 이 경우, 그룹들은 이 요건을 자연스럽게 충족시키지 못할 경우 채워져야 한다.

본 발명의 바람직한 실시예는 상술한 컴파일 방법을 이용하여 소스 코드로부터 병렬 컴퓨터 프로그램을 생성하도록 마련된 소프트웨어 제품이다.

기술의 진보로, 본 발명의 기본적인 구상이 다양한 방식으로 실시될 수 있음은 당업자에게 분명하다. 따라서, 본 발명과 그 실시예들은 상술한 예들에 한정되 지 않고, 청구의 범위 내에서 변형될 수 있다.

Claims

추상 파스 트리(abstract parse tree)를 정의하기 위해 소스 코드를 파싱하는 단계를 포함하는, 컴퓨터 프로그램을 소스 코드로부터 실행가능한 코드로 컴파일하는 방법으로서,

데이터 플로우 및 데이터 종속성 그래프(data dependency graphs)를 정의하기 위해 상기 추상 파스 트리를 합성하는 단계;

오더링 제약(ordering constraints)을 형성하기 위해 상기 그래프을 머신 데이터 플로우 그래프로 리파인(refine)하는 단계;

상기 데이터 플로우 및 상기 데이터 종속성 그래프에서 종속성들을 만족하는데 필요한 오더링 제약으로 구성되는 상기 오더링 제약의 제1 부분으로 부분 실행 오더를 정의하는 단계;

상기 머신 데이터 플로우 그래프를 연산 장치에 매핑하는데 필요한 오더링 제약으로 구성되는 상기 오더링 제약의 제2 부분을 추가하여 상기 머신 데이터 플로우 그래프 내의 명령들을 병렬 실행가능한 코드로 그룹화하는 단계; 및

상기 병렬 실행가능한 코드로부터 실행가능한 형태를 생성하는 단계를 더 포함하는 것을 특징으로 하는, 컴퓨터 프로그램을 소스 코드로부터 실행가능한 코드로 컴파일하는 방법.
청구항 1에 있어서,

상기 실행가능한 코드가 연산 장치에서 실행될 때 상기 코드에 대한 실행 오더를 정의하는 단계를 더 포함하는, 컴퓨터 프로그램을 소스 코드로부터 실행가능한 코드로 컴파일하는 방법.
청구항 1 내지 3 중 어느 한 항에 있어서,

상기 명령들을 그룹화하는 단계에서, 상기 코드에 대한 실행 오더를 정의하는 단계를 더 포함하는, 컴퓨터 프로그램을 소스 코드로부터 실행가능한 코드로 컴파일하는 방법.
청구항 1 내지 3 중 어느 한 항에 있어서,

상기 그룹들은 오더 도입(order introduction)으로 실행되는, 컴퓨터 프로그램을 소스 코드로부터 실행가능한 코드로 컴파일하는 방법.
연산 장치에서 실행될 때 하기의 단계들을 실행하도록 구성되고, 추상 파스 트리를 정의하기 위해 소스 코드를 파싱하는 단계를 포함하는, 컴퓨터 프로그램을 소스 코드로부터 실행가능한 코드로 컴파일하는 컴퓨터 프로그램 제품으로서,

데이터 플로우 및 데이터 종속성 그래프를 정의하기 위해 상기 추상 파스 트리를 합성하는 단계;

오더링 제약을 형성하기 위해 상기 그래프을 머신 데이터 플로우 그래프로 리파인하는 단계;

상기 데이터 플로우 및 상기 데이터 종속성 그래프에서 종속성들을 만족하는데 필요한 오더링 제약으로 구성되는 상기 오더링 제약의 제1 부분으로 부분 실행 오더를 정의하는 단계;

상기 머신 데이터 플로우 그래프를 연산 장치에 매핑하는데 필요한 오더링 제약으로 구성되는 상기 오더링 제약의 제2 부분을 추가하여 상기 머신 데이터 플로우 그래프 내의 명령들을 병렬 실행가능한 코드로 그룹화하는 단계; 및

상기 머신 데이터 플로우 그래프로부터 실행가능한 형태를 생성하는 단계를 실행하도록 더 구성되는 것을 특징으로 하는, 컴퓨터 프로그램 제품.
청구항 5에 있어서,

상기 실행가능한 코드가 연산 장치에서 실행될 때 상기 코드의 제2 부분에 대한 실행 오더를 정의하는 단계를 실행하도록 더 구성되는, 컴퓨터 프로그램 제품.
청구항 5에 있어서,

상기 실행가능한 형태를 생성하는 단계에서 상기 코드의 제2 부분에 대한 실행 오더를 정의하는 단계를 실행하도록 더 구성되는, 컴퓨터 프로그램 제품.
청구항 5 내지 7 중 어느 한 항에 있어서,

상기 그룹들은 오더 도입으로 실행되는, 컴퓨터 프로그램 제품.
컴퓨터 프로그램 제품을 실행할 때 하기의 단계들을 실행하도록 구성되고, 추상 파스 트리를 정의하기 위해 소스 코드를 파싱하는 단계를 포함하는, 컴퓨터 프로그램을 소스 코드로부터 실행가능한 코드로 컴파일하는 컴퓨터 프로그램 제품을 포함하는 장치로서, 상기 프로그램이

데이터 플로우 및 데이터 종속성 그래프를 정의하기 위해 상기 추상 파스 트리를 합성하는 단계;

오더링 제약을 형성하기 위해 상기 그래프을 머신 데이터 플로우 그래프로 리파인하는 단계;

상기 데이터 플로우 및 상기 데이터 종속성 그래프에서 종속성들을 만족하는데 필요한 오더링 제약으로 구성되는 상기 오더링 제약의 제1 부분으로 부분 실행 오더를 정의하는 단계;

상기 머신 데이터 플로우 그래프를 연산 장치에 매핑하는데 필요한 오더링 제약으로 구성되는 상기 오더링 제약의 제2 부분을 추가하여 상기 머신 데이터 플로우 그래프 내의 명령들을 병렬 실행가능한 코드로 그룹화하는 단계; 및

상기 머신 데이터 플로우 그래프로부터 실행가능한 형태를 생성하는 단계를 실행하도록 더 구성되는 것을 특징으로 하는, 컴퓨터 프로그램 제품을 포함하는 장치.
청구항 9에 있어서,

상기 실행가능한 코드가 연산 장치에서 실행될 때, 상기 코드의 제2 부분에 대한 실행 오더를 정의하는 단계를 실행하도록 더 구성되는, 컴퓨터 프로그램 제품을 포함하는 장치.
청구항 9에 있어서,

상기 실행 형식을 생성하는 단계에서 상기 코드의 제2 부분에 대한 실행 오더를 정의하는 단계를 실행하도록 더 구성되는, 컴퓨터 프로그램 제품을 포함하는 장치.
청구항 9 내지 11 중 어느 한 항에 있어서,

상기 그룹들은 오더 도입으로 실행되는, 컴퓨터 프로그램 제품을 포함하는 장치.
청구항 9 내지 11 중 어느 한 항에 있어서,

상기 그룹들은 상기 코드의 상기 제1 및 제2 부분들로 형성되는, 컴퓨터 프로그램 제품을 포함하는 장치.