Kahn 프로세스 네트워크

Kahn process networks

Kahn 프로세스 네트워크(KPN 또는 프로세스 네트워크)는 결정론적 순차 프로세스 그룹이 무한의 퍼스트 아웃 채널을 통해 통신하는 분산된 연산 모델이다.이 모델은 쓰기가 차단되지 않는 동안 채널의 판독이 차단되도록 요구한다.이러한 주요 제한 때문에, 결과 프로세스 네트워크는 계산의 타이밍이나 통신 지연에 좌우되지 않는 결정론적 행동을 보인다.

Kahn 프로세스 네트워크는 원래 병렬 프로그램을 모델링하기 위해 개발되었지만 임베디드 시스템, 고성능 컴퓨팅 시스템, 신호 처리 시스템, 스트림 처리 시스템, 데이터 흐름 프로그래밍 언어 및 기타 컴퓨팅 작업을 모델링하는 데 편리함이 입증되었다.KPN은 1974년 길레스 칸에 의해 소개되었다.[1]

세 개의 프로세스(수직)와 세 개의 통신 채널(에지)을 가진 칸 프로세스 네트워크.그 실행 중에 공정 P는 채널 A와 B에서 판독하여 채널 C에 기록한다.

실행 모델

KPN은 데이터의 무한 스트림이 시퀀스 또는 병렬로 실행되는 프로세스에 의해 증분적으로 변환되는 신호 처리 시스템을 설명하기 위한 공통 모델이다.병렬 프로세스에도 불구하고 이 모델을 실행하기 위해 멀티태스킹이나 병렬화가 필요하지 않다.

KPN에서 프로세스는 무한 FIFO 채널을 통해 통신한다.프로세스는 토큰이라고도 하는 원자 데이터 요소를 읽고 쓰며, 채널 간을 오간다.채널에 쓰는 것은 비차단적이다. 즉, 채널에서 읽는 것이 차단되는 동안 항상 성공하고 프로세스를 지연시키지 않는다. 즉, 빈 채널에서 읽는 프로세스가 정지하며 채널에 충분한 데이터 항목(토큰)이 포함되어 있을 때만 계속할 수 있다.프로세스는 토큰을 소비하지 않고 입력 채널의 존재 여부를 테스트할 수 없다.FIFO는 여러 프로세스에 의해 소비될 수 없으며, 여러 프로세스가 단일 FIFO에 쓰일 수도 없다.공정에 대한 특정 입력(토큰) 이력을 부여하면 공정이 항상 동일한 출력(토큰)을 생산하도록 결정론적이어야 한다.프로세스의 타이밍이나 실행 순서는 결과에 영향을 미치지 않아야 하므로 토큰에 대한 입력 채널 테스트는 금지된다.

프로세스에 대한 참고 사항

  • 프로세스는 순수한 데이터 소스로 작용할 수 있으므로 입력을 읽거나 입력 채널을 가질 필요가 없다.
  • 프로세스는 어떤 출력도 쓸 필요가 없으며 어떤 출력 채널도 가지고 있지 않다.
  • 입력 채널의 빈 공간(또는 비차단 읽기)을 최적화할 목적으로 테스트할 수 있지만 출력에 영향을 주어서는 안 된다.채널을 기다리는 것보다 미리 무언가를 하는 것이 유익하거나 가능할 수 있다.예를 들어 서로 다른 채널에서 두 번의 읽기가 있었다고 가정해 보십시오.첫 번째 읽기가 중단되지만(토큰을 기다림) 두 번째 읽기가 직접 성공할 수 있다면, 읽기 자체가 종종 시간을 소비하기 때문에(예: 메모리 할당 또는 복사 시간) 시간을 절약하기 위해 두 번째 읽기를 먼저 읽는 것이 유익할 수 있다.

Petri nets로서 프로세스 발사 의미론

위의 이미지에 표시된 페트리 네트로 모델링된 프로세스 P의 점화 의미

위의 KPN의 프로세스 P가 채널 A에서 데이터를 먼저 읽고, 채널 B에서 무언가를 계산하고, 채널 C에 데이터를 쓰도록 구성되었다고 가정하면, 프로세스의 실행 모델은 오른쪽에 보이는 페트리 네트로 모델링할 수 있다.[2]PE 리소스 플레이스의 단일 토큰은 다른 입력 데이터에 대해 프로세스가 동시에 실행되는 것을 금지한다.데이터가 채널 A 또는 B에 도착하면 토큰은 각각 FIFO A와 FIFO B 위치에 배치된다.Petri net의 전환은 각각의 I/O 운영 및 계산과 연관된다.데이터가 채널 C에 기록되면, PE 자원은 새로운 데이터를 읽을 수 있도록 초기 표시로 다시 채워진다.

유한 상태 기계로서의 공정

공정의 유한 상태 기계

공정은 다음 두 상태 중 하나에 있는 유한 상태 기계로 모델링할 수 있다.

  • 활성, 프로세스에서 데이터 계산 또는 쓰기
  • 대기, 프로세스가 데이터에 대해 차단됨(대기 중)

유한 상태 기계가 프로세스와 관련된 프로그램 요소를 읽는다고 가정하면, 그것은 세 가지 종류의 토큰을 읽을 수 있는데, 그것은 "계산", "읽기", "쓰기 토큰"이다.또한 Wait 상태에서는 대기와 관련된 통신 채널에 읽을 수 있는 데이터가 포함되어 있음을 의미하는 특수 "Get token"을 읽어야만 활성 상태로 돌아올 수 있다.

특성.

채널의 경계성

채널이 가능한 실행에 대해 b 개의 미합치 토큰을 가지고 있는 경우, 은b {\ b로 엄격히 제한된다.모든 채널이 b로 제한되는 경우 은 b b로 엄격히 제한된다

미합치 토큰 수는 프로세스의 실행 순서(스케줄링)에 따라 달라진다.스케줄러가 토큰을 소비하는 프로세스를 실행하지 않을 경우 자발적 데이터 소스는 채널로 임의로 많은 토큰을 생성할 수 있다.

실제 애플리케이션은 무한의 FIFO를 가질 수 없으므로, FIFO의 스케줄링과 최대 용량을 실제 구현으로 설계해야 한다.FIFO의 최대 용량은 다음과 같은 여러 가지 방법으로 처리할 수 있다.

  • FIFO 한계를 수학적으로 도출하여 FIFO 오버플로를 방지할 수 있다.그러나 이것은 모든 KPN에 대해서는 가능하지 않다.KPN이 에 의해 엄격하게 경계되는지 여부를 시험하는 것은 이해할 수 없는 문제다[citation needed] 더욱이 실제 상황에서는 경계가 데이터에 의존할 수 있다.
  • FIFO 한계는 수요에 따라 증가될 수 있다.[3]
  • FIFO가 가득 차면 프로세스가 차단되도록 차단 쓰기를 사용할 수 있다.설계자가 FIFO에 대한 안전 한도를 적절히 도출하지 않는 한 이러한 접근방식은 불행히도 인위적인 교착 상태를 초래할 수 있다(Parks, 1995).정확한 산출물의 생산을 보장하기 위해 런타임에서의 국소 인공 검출이 필요할 수 있다.[4]

폐쇄형 및 개방형 시스템

폐쇄된 KPN에는 외부 입력 또는 출력 채널이 없다.입력 채널이 없는 프로세스는 데이터 소스로, 출력 채널이 없는 프로세스는 데이터 싱크로 작용한다.열린 KPN에서 각 프로세스는 최소한 하나의 입력 및 출력 채널을 가진다.

결정론

KPN의 과정은 결정론적이다.동일한 입력 내역에 대해 항상 정확하게 동일한 출력을 생성해야 한다.프로세스는 결정론적 속성이 보존되는 한 어떤 순서나 양으로도 포트에 읽고 쓰는 순차적 프로그램으로 모델링할 수 있다.결과적으로, KPN 모델은 다음과 같은 요인이 시스템의 출력을 완전히 결정하도록 결정론적이다.

  • 과정
  • 네트워크
  • 이니셜 토큰

따라서 프로세스의 타이밍은 시스템의 출력에 영향을 미치지 않는다.

단조도

KPN 과정은 단조롭다.토큰을 더 많이 읽는 것은 토큰을 더 많이 쓰는 것으로 이어질 수 있다.미래에 읽은 토큰은 미래에 쓰여진 토큰에만 영향을 미칠 수 있다.KPN에서는 신호 내부에 총 이벤트[clarification needed] 순서가 있다.[clarification needed]그러나 서로 다른 신호의 사건들 사이에는 순서 관계가 없다.따라서, KPN은 부분적으로만 순서가 정해지지 않은 모델로 분류된다.

적용들

높은 표현성과 간명성 때문에, 연산 모델의 기초가 되는 KPN은 특정 속성(예: 데이터 흐름 지향, 스트림 기반)을 가진 스트리밍 애플리케이션을 나타내기 위해 여러 학술 모델링 도구에 적용되고 있다.

라이덴대 라이덴임베디드연구센터가 유지하는 오픈소스 다이달러스 프레임워크는[5] C로 작성된 순차 프로그램을 받아들여 해당 KPN을 생성한다.예를 들어, 이 KPN은 FPGA 기반 플랫폼에 KPN을 체계적으로 매핑하는 데 사용될 수 있다.

Ambric Am2045 대량 병렬 프로세서 어레이는 실제 실리콘에 구현된 KPN이다.[6]336개의 32비트 프로세서는 전용 FIFO의 프로그램 가능한 인터커넥트로 연결된다.따라서 그것의 채널은 쓰기 차단으로 엄격히 제한되어 있다.

참고 항목

참조

  1. ^ Kahn, G. (1974). Rosenfeld, Jack L. (ed.). The semantics of a simple language for parallel programming (PDF). Proc. IFIP Congress on Information Processing. North-Holland. ISBN 0-7204-2803-3.
  2. ^ Bernardeschi, C.; De Francesco, N.; Vaglini, G. (1995). "A Petri nets semantics for data flow networks". Acta Informatica. 32: 347–374.
  3. ^ Parks, Thomas M. (1995). Bounded Scheduling of Process Networks (Ph. D.). University of California, Berkeley.
  4. ^ Geilen, Marc; Basten, Twan (2003). Degano, P. (ed.). Requirements on the Execution of Kahn Process Networks. Proc. 12th European Symposium on Programming Languages and Systems (ESOP). Springer. pp. 319–334. CiteSeerX 10.1.1.12.7148.
  5. ^ http://daedalus.liacs.nl LIACS 다이달로스 프레임워크
  6. ^ Mike Buts, Anthony Mark Jones, Paul Wasson, "재구성이 가능한 컴퓨팅을 위한 구조적 객체 프로그래밍 모델, 아키텍처, 칩 및 도구", FCCM의 Processions of FCCM, 2007년 4월, IEEEE Computer Society

추가 읽기

  • Lee, E.A.; Parks, T.M. (1995). "Dataflow process networks" (PDF). Proceedings of the IEEE. 83 (5): 773–801. doi:10.1109/5.381846. ISSN 0018-9219. Retrieved 2019-02-13.
  • Josephs, Mark B. (2005). "Models for Data-Flow Sequential Processes". In Abdallah, Ali E.; Jones, Cliff B.; Sanders, Jeff W. (eds.). Communicating Sequential Processes. The First 25 Years: Symposium on the Occasion of 25 Years of CSP, London, UK, July 7-8, 2004. Revised Invited Papers. Lecture Notes in Computer Science. Vol. 3525. Berlin, Heidelberg: Springer Berlin Heidelberg. pp. 85–97. CiteSeerX 10.1.1.60.5694. doi:10.1007/11423348_6. ISBN 978-3-540-32265-8.