바이너리 모듈러 데이터 플로우 머신

Binary Modular Dataflow Machine
다양한 운영 체제에서 실행되는 BMDFM
리눅스
윈도 10
MacOS
안드로이드

Binary Modular Dataflow Machine(BMDFM; 바이너리 모듈러 데이터 플로우 머신)은 여러 프로세서를 사용하여 공유 메모리 대칭 멀티프로세서(SMP) 컴퓨터에서 응용 프로그램을 병렬로 실행하여 단일 응용 프로그램의 실행을 가속화하는 소프트웨어 패키지입니다.BMDFM은 이전의 시퀀셜 프로그램에서 파생된 데이터 흐름명령 시퀀스의 정적 및 주로 동적 스케줄링에 의해 병렬화를 자동으로 식별하고 이용합니다.

BMDFM 다이내믹스케줄링 서브시스템은 태그 부착 데이터 플로우머신의 Symmetric Multiprocessing(SMP; 대칭 멀티프로세서) 에뮬레이션을 실행하여 애플리케이션에 투과적인 데이터 플로우의 의미를 제공합니다.병렬 실행에 대한 지침은 필요하지 않습니다.

배경

현재의 병렬 공유 메모리 SMP는 복잡한 머신으로 고성능을 실현하기 위해 많은 아키텍처 측면의 동시 처리를 필요로 합니다.최근의 테크니컬 컴퓨팅용 범용 SMP 머신에는 긴밀하게 결합된 코어가 다수 탑재되어 있을 가능성이 있습니다(좋은 예로는 인텔(Core 또는 Xeon) 또는 IBM(Power)의 멀티코어 프로세서를 탑재한 SMP 머신이 있습니다).SMP 노드당 코어 수는 컴퓨터 제조사의 발표에 따라 몇 년마다 두 배씩 증가할 예정입니다.

멀티코어 프로세서는 소프트웨어로 식별되는 스레드 수준의 병렬 처리를 이용하기 위한 것입니다.따라서 가장 어려운 작업은 애플리케이션 프로그램을 병렬로 처리하기 위해 멀티코어 프로세서의 성능을 효율적으로 활용하는 방법을 찾는 것입니다.Fork-join 런타임 라이브러리를 사용한 정적 병렬화의 기존 OpenMP 패러다임은 루프 집약적인 일반 어레이 기반 계산에서만 잘 작동하지만 컴파일 시간 병렬화 방법은 일반적으로 약하고 불규칙한 애플리케이션에는 거의 적용되지 않습니다.

  • 비결정적인 시간이 걸리는 작업이 많아 언제 특정 데이터를 사용할 수 있게 될지 정확히 알 수 없습니다.
  • 멀티레벨 캐시가 있는 메모리 계층에는 예측할 수 없는 메모리 액세스 지연이 있습니다.
  • 멀티 유저 모드에서는, 다른 유저의 코드가 자원을 소비하거나, 컴파일러가 설명할 수 없는 계산의 일부를 늦출 수 있습니다.
  • 컴파일러는 조건부 호출이 어느 방향으로 진행되는지 또는 함수 호출을 최적화할 수 없기 때문에 컴파일 타임의 프로시저간 최적화와 교차 조건 최적화는 매우 어렵습니다(대개 불가능).

BMDFM의 투명한 데이터 흐름 의미

BMDFM 테크놀로지는 주로 동적 스케줄링을 사용하여 애플리케이션 프로그램의 병렬화를 이용하므로 BMDFM은 컴파일 타임 [1][2]방식의 단점을 회피합니다.BMDFM은 멀티코어 SMP를 위한 병렬 프로그래밍 환경으로서 다음과 같은 기능을 제공합니다.

  • 병렬 실행을 위한 지침이 필요하지 않은 기존 프로그래밍 패러다임입니다.
  • 시스템에서 사용 가능한 모든 멀티코어 프로세서를 사용하여 자연스럽게 로드밸런싱된 방법으로 병렬 처리를 투명하게(암시적으로) 이용합니다.

BMDFM은 알려진 아키텍처 원칙의 장점을 단일 하이브리드 아키텍처에 결합합니다. 이 아키텍처는 동적 스케줄링 오버헤드가 거의 없고 병목 현상이 없는 애플리케이션의 암묵적 병렬화를 활용할 수 있습니다.주로 기본 데이터 흐름 원리를 사용합니다.데이터 흐름 원칙은 다음과 같습니다. "인수가 모두 준비되면 명령 또는 함수를 실행할 수 있습니다.데이터 플로우 머신은 런타임에 모든 데이터의 태그를 관리합니다.데이터가 계산되면 데이터는 준비 태그로 표시됩니다.ready 인수가 있는 명령은 결과 데이터를 ready로 표시하여 실행됩니다."

BMDFM의 주요 특징은 최상위 수준에서 기존의 프로그래밍 패러다임, 이른바 투명한 데이터 흐름 시멘틱스를 제공하는 것입니다.사용자는 BMDFM을 가상 머신(VM)으로 이해하고 있습니다.가상 머신(VM)은 애플리케이션 프로그램의 모든 문을 병렬로 실행하고 모든 병렬화 및 동기화 메커니즘을 완전히 투명하게 유지합니다.응용 프로그램 문장은 일반 연산자로, 변수 할당, 조건부 처리, 루프, 함수 호출 등 단일 스레드 프로그램으로 구성될 수 있습니다.

다음과 같은 코드 fragment가 있다고 가정합니다.

(설정 a (foo0 i))        # a = foo0(i); (설정 b (foo1 (+ i 1)))  # b = foo1(i+1); (설정 b (++ b))          # b++; (아웃풋 "a = %d\n" a)      # 인쇄물("a = %d\n", a); (아웃풋 "b = %d\n" b)      # 인쇄물("b = %d\n", b);

두 개의 첫 번째 문은 독립적이기 때문에 BMDFM의 데이터 플로우엔진은 서로 다른 프로세서 또는 프로세서의 코어로 실행할 수 있습니다.두 개의 마지막 문도 병렬로 실행할 수 있지만 "a"와 "b"가 계산된 후에만 실행됩니다.데이터 흐름 엔진은 런타임에 동적으로 데이터 흐름 그래프를 작성할 수 있기 때문에 종속성을 자동으로 인식합니다.또한 데이터 흐름 엔진은 출력 스트림에 결과를 순차적으로 출력하도록 올바르게 명령합니다.따라서 순서가 잘못된 처리 후에도 결과는 자연스럽게 나타납니다.

위의 코드 프래그먼트가 루프에 네스트 되어 있다고 합니다.

(위해서 i 1 1 N (예후        # 위해서 (i = 1; i <=> N; i++) {   (설정 a (foo0 i))        #   a = foo0(i);   (설정 b (foo1 (+ i 1)))  #   b = foo1(i + 1);   (설정 b (++ b))          #   b++;   (아웃풋 "a = %d\n" a)      #   인쇄물("a = %d\n", a);   (아웃풋 "b = %d\n" b)      #   인쇄물("b = %d\n", b); ))                         # }

BMDFM의 데이터 플로우엔진은 변수 "a"와 "b"를 각 반복마다 고유한 컨텍스트 아래에 유지합니다.사실, 이것은 변수의 다른 복사본입니다.컨텍스트 변수는 명령 소비자가 참조할 때까지 존재합니다.이후 참조되지 않은 컨텍스트는 런타임에 가비지가 수집됩니다.따라서 데이터 플로우엔진은 반복 내의 로컬 병렬 처리와 글로벌 병렬 처리의 양쪽 모두를 이용할 수 있을 뿐만 아니라 동시에 여러 번의 반복을 실행할 수도 있습니다.

아키텍처

BMDFM의 기본 개념

BMDFM은 여러 아키텍처 패러다임(von-Neumann, SMP 및 데이터 흐름)의 MIMD 통합으로 인해 멀티 코어 SMP를 위한 편리한 병렬 프로그래밍 환경이자 효율적인 런타임 엔진입니다.

  • 처음에는 범용 SMP 상에서 멀티스레드 동작하는 하이브리드 데이터 플로우 에뮬레이터입니다.SMP는 MIMD를 보증하고 데이터 플로우는 암묵적인 병렬 처리를 이용합니다.
  • 둘째, von-Neumann 프론트 엔드 VM에 의해 제어되는 하이브리드 멀티스레드 데이터 흐름 런타임 엔진입니다.데이터 플로우 런타임엔진은 (제한된 포크 조인 패러다임과는 반대로) 태그가 달린 컨텍스트 병렬 명령을 실행하는 반면 von-Neumann 프론트 엔드 VM은 컨텍스트를 초기화하고 명령의 마셜 클러스터를 데이터 플로우 런타임엔진에 공급합니다.
  • 셋째, 정적 병렬화와 동적 병렬화의 하이브리드입니다.von-Neumann 프론트 엔드 VM은 애플리케이션을 병렬 마샬링된 명령 클러스터로 정적으로 분할하려고 하며, dataflow 런타임 엔진은 정적인 병렬화 방법을 동적으로 보완합니다.

BMDFM은 (기존의 포크 조인 런타임 라이브러리가 아닌) 불규칙한 애플리케이션을 병렬로 자동으로 실행할 수 있는 병렬 런타임 엔진의 역할로 사용하기 위한 것입니다.BMDFM은 투명한 데이터 흐름의 의미론 때문에 애플리케이션 프로그래머를 위한 단순한 병렬화 기술이며, 동시에 멀티 코어 SMP 컴퓨터를 위한 훨씬 더 나은 병렬 프로그래밍 및 컴파일 기술입니다.

BMDFM의 기본 개념은 시중에서 구할 수 있는 기본 상용 SMP 하드웨어에 의존합니다.일반적으로 SMP 벤더는 자체 SMP 운영체제(OS)에 SVR4/POSIX 인터페이스(Linux, HP-UX, SunOS/Solaris, Tru64OSF1, IRIX, AIX, BSD, MacOS 등)를 제공합니다.SMP OS 상에서 멀티스레드 데이터 플로우 런타임엔진은 데이터 플로우머신의 소프트웨어 에뮬레이션을 수행합니다.이러한 가상 시스템에는 가상 시스템 언어 및 C에 대한 인터페이스가 있어 기존 프로그래밍의 투명한 데이터 흐름 의미론을 제공합니다.

BMDFM은 다음과 같은 몇 가지 아키텍처 원리의 하이브리드로 구축됩니다.

  • MIMD(Multiple Instruction Streams, Multiple Data Streams)는 상용 SMP에 의해 유지됩니다.
  • 암묵적인 병렬 실행은 데이터 흐름 에뮬레이션에 의해 보증됩니다.
  • Von-Neumann 계산 원리는 프런트 엔드 제어 가상 머신을 구현하는 데 적합합니다.
BMDFM의 아키텍처

애플리케이션 프로그램(입력 시퀀셜 프로그램)은 예비 코드 재구성(코드 재구성), 스테이트먼트의 정적 스케줄링(스태틱 스케줄러) 및 컴파일/로드(컴파일러, 로더)의 3단계로 처리된다.스태틱 스케줄링 단계 후의 출력은 병목현상을 회피하도록 설계된 인터페이스를 통해 멀티스레드 엔진에 공급되는 다중 클러스터 흐름입니다.여러 클러스터 흐름은 모든 주소가 컨텍스트 정보로 해결되고 확장되는 마셜화된 클러스터로 분할된 컴파일된 입력 프로그램으로 간주할 수 있습니다.마샬링된 클러스터로 분할하면 멀티스레드로 로드할 수 있습니다.컨텍스트 정보를 통해 반복을 병렬로 처리할 수 있습니다.리스너 스레드는 순서가 잘못된 처리 후에 출력 스트림을 정렬합니다.

BMDFM 다이내믹스케줄링 서브시스템은 태그 부착 토큰 데이터 플로우머신의 효율적인 SMP 에뮬레이터입니다.Shared Memory Pool은 Input/Output Ring Buffer Port(IORP; 입력/출력 링버퍼 포트), Data Buffer(DB; 데이터 버퍼), Operation Queue(OQ; 동작 큐)의 3가지 주요 부분으로 나뉩니다.프런트 엔드 제어 가상 시스템은 입력 애플리케이션 프로그램을 정적으로 스케줄링하고 입력 프로그램의 클러스터된 명령과 데이터를 IORP에 넣습니다.링 버퍼 서비스 프로세스(IORBP PROC)는 데이터를 DB로, 명령을 OQ로 이동합니다.Operation Queue Service Processes(OQ PRO)는 필요한 오퍼랜드의 데이터에 액세스할 수 있는 경우 명령을 실행 준비 완료로 태그 붙입니다.실행 프로세스(CPU PROC)는 ready로 태그 지정된 명령을 실행하여 계산된 데이터를 DB 또는 IORP로 출력합니다.또, 콘텍스트가 처리되면, IORBP PROC와 OQ PROC가 메모리를 해방합니다.컨텍스트는 태그 부착 토큰 데이터 흐름아키텍처에 따라 다른 반복 본문 내의 데이터 복사본을 나타내는 특별한 고유 식별자입니다.이것에 의해, 다이나믹 스케줄러는 복수의 반복을 병렬로 처리할 수 있습니다.

SMP OS에서 실행되는 프로세스에서는 사용 가능한 모든 실제 머신 프로세서와 프로세서 코어가 사용됩니다.여러 프로세스가 동시에 동일한 데이터에 액세스할 수 있도록 BMDFM 다이내믹스케줄러는 SVR4/POSIX 세마포어 조작을 통해 공유 메모리 풀 내의 개체를 잠급니다.잠금 정책은 여러 읽기 전용 액세스와 변경을 위한 배타적 액세스를 제공합니다.

지원되는 플랫폼

ANSI C 및 POSIX; UNIX System V(SVR4)를 지원하는 모든 머신은 BMDFM을 실행할 수 있습니다.

BMDFM은 다음을 위해 완전한 멀티 스레드 버전으로 제공됩니다.

  • x86: Linux/32, FreeBSD/32, OpenBSD/32, NetBSD/32, MacOS/32, SunOS/32, UnixWare/32, Minix/32, Android/32, Win-Cygwin/32, Win-UWIN/32, Win-SFUA/32;
  • x86-64: Linux/64, FreeBSD/64, OpenBSD/64, NetBSD/64, MacOS/64, SunOS/64, Android/64, Win-Cygwin/64,
  • VAX: Ultrix/32;
  • 알파: Tru64OSF1/64, Linux/64, FreeBSD/64, OpenBSD/64
  • IA-64: HP-UX/32, HP-UX/64, Linux/64, FreeBSD/64
  • XeonPhiMIC: Linux/64;
  • MCST-Elbrus: Linux/32, Linux/64;
  • PA-RISC: HP-UX/32, HP-UX/64, Linux/32;
  • SPARC: SunOS/32, SunOS/64, Linux/32, Linux/64, FreeBSD/64, OpenBSD/64
  • MIPS: IRIX/32, IRIX/64, Linux/32, Linux/64
  • MIPSel: Linux/32, Linux/64, Android/32, Android/64
  • PowerPC: AIX/32, AIX/64, MacOS/32, MacOS/64, Linux/32, Linux/64, FreeBSD/32, FreeBSD/64
  • PowerPCle: Linux/32, Linux/64
  • S/390: Linux/32, Linux/64
  • M68000: Linux/32;
  • ARM: Linux/32, Linux/64, FreeBSD/64, Android/32, Android/64, MacOS/64
  • ARMBE: Linux/64;
  • RISC-V: Linux/32, Linux/64
  • 및 x86용 싱글 스레드 버전: Win/32 한정.

「 」를 참조해 주세요.

레퍼런스

  1. ^ "BMDFM: A Hybrid Dataflow Runtime Parallelization Environment for Shared Memory Multiprocessors". Technical University of Munich (TUM), Germany. February 25, 2006.
  2. ^ "urn:nbn:de:bvb:91-diss20060316-1748151609". URN NBN Resolver for Germany and Switzerland. March 22, 2006.

외부 링크