[go: up one dir, main page]

KR101413049B1 - 그래프 기반 계산에서의 계산 자원의 관리 - Google Patents

그래프 기반 계산에서의 계산 자원의 관리 Download PDF

Info

Publication number
KR101413049B1
KR101413049B1 KR1020087030136A KR20087030136A KR101413049B1 KR 101413049 B1 KR101413049 B1 KR 101413049B1 KR 1020087030136 A KR1020087030136 A KR 1020087030136A KR 20087030136 A KR20087030136 A KR 20087030136A KR 101413049 B1 KR101413049 B1 KR 101413049B1
Authority
KR
South Korea
Prior art keywords
data processing
processing element
processing elements
elements
graph
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Active
Application number
KR1020087030136A
Other languages
English (en)
Other versions
KR20090018113A (ko
Inventor
요셉 스케핑튼 3 홀리
이고르 쉬에르브
에프라임 메리웨더 비슈니아크
Original Assignee
아브 이니티오 테크놀로지 엘엘시
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by 아브 이니티오 테크놀로지 엘엘시 filed Critical 아브 이니티오 테크놀로지 엘엘시
Publication of KR20090018113A publication Critical patent/KR20090018113A/ko
Application granted granted Critical
Publication of KR101413049B1 publication Critical patent/KR101413049B1/ko
Active legal-status Critical Current
Anticipated expiration legal-status Critical

Links

Images

Classifications

    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F9/00—Arrangements for program control, e.g. control units
    • G06F9/06—Arrangements for program control, e.g. control units using stored programs, i.e. using an internal store of processing equipment to receive or retain programs
    • G06F9/46—Multiprogramming arrangements
    • G06F9/50—Allocation of resources, e.g. of the central processing unit [CPU]
    • G06F9/5061—Partitioning or combining of resources
    • G06F9/5066—Algorithms for mapping a plurality of inter-dependent sub-tasks onto a plurality of physical CPUs
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F9/00—Arrangements for program control, e.g. control units
    • G06F9/06—Arrangements for program control, e.g. control units using stored programs, i.e. using an internal store of processing equipment to receive or retain programs
    • G06F9/46—Multiprogramming arrangements
    • G06F9/50—Allocation of resources, e.g. of the central processing unit [CPU]
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F9/00—Arrangements for program control, e.g. control units
    • G06F9/06—Arrangements for program control, e.g. control units using stored programs, i.e. using an internal store of processing equipment to receive or retain programs
    • G06F9/46—Multiprogramming arrangements
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06T—IMAGE DATA PROCESSING OR GENERATION, IN GENERAL
    • G06T1/00—General purpose image data processing

Landscapes

  • Engineering & Computer Science (AREA)
  • Theoretical Computer Science (AREA)
  • Software Systems (AREA)
  • Physics & Mathematics (AREA)
  • General Physics & Mathematics (AREA)
  • General Engineering & Computer Science (AREA)
  • Stored Programmes (AREA)
  • Information Retrieval, Db Structures And Fs Structures Therefor (AREA)
  • Complex Calculations (AREA)
  • Apparatus For Radiation Diagnosis (AREA)
  • Magnetic Resonance Imaging Apparatus (AREA)
  • Medicines That Contain Protein Lipid Enzymes And Other Medicines (AREA)
  • Management, Administration, Business Operations System, And Electronic Commerce (AREA)
  • Executing Machine-Instructions (AREA)
  • Advance Control (AREA)
  • Multi Processors (AREA)
  • Debugging And Monitoring (AREA)

Abstract

그래프 기반 계산(graph-based computation)을 실행하는 것은, 링크 요소(linking element)에 의해 데이터 처리 요소가 결합되는 계산 그래프의 사양을 받아들이는 단계, 데이터 처리 요소를, 하나 이상의 세트가 데이터 처리 요소를 복수 개 포함하는 세트로 분할하는 단계, 각각의 세트에 상이한 계산 자원을 할당하는 단계, 및 할당된 계산 자원을 이용하여 데이터 처리 요소에 대응하는 계산을 수행하는 것을 포함하는, 계산 그래프에 따라 데이터를 처리하는 단계를 포함한다.
데이터 기억부, 실행 모듈, 런타임 모니터링 모듈, 사전 실행 모듈, 보고 모듈

Description

그래프 기반 계산에서의 계산 자원의 관리{MANAGING COMPUTING RESOURCES IN GRAPH-BASED COMPUTATIONS}
본 발명은 그래프 기반 계산에서의 계산 자원의 관리에 관한 것이다.
복잡한 계산은 간혹 계산의 성분이 그래프의 정점과 연관되는 방향성 그래프(directed graph)를 통한 데이터 흐름 및 그래프의 링크(호, 에지)에 대응하는 성분 간의 데이터 흐름으로서 표현될 수 있다. 이러한 그래프 기반 계산을 구현하는 시스템은 "EXECUTING COMPUTATIONS EXPRESSED AS GRAPHS"를 발명의 명칭으로 하는 미국 특허 번호 5,966,072호에 개시되어 있다. 그래프 기반 계산을 실행하는 한 가지 방식은 각각 그래프의 상이한 정점(vertex)과 관련되는 다수의 프로세스를 실행하고 그래프의 링크에 대응하는 프로세스 간의 통신 경로를 구축하는 것이다. 예컨대, 통신 경로는 네임드 파이프(named pipe), TCP/IP 또는 UNIX, 또는 프로세스 간에 데이터를 넘겨주기 위한 공유 메모리를 사용할 수 있다.
일특징에서, 전반적으로, 본 발명은 그래프 기반 계산(graph-based computation)을 실행하는 방법을 특징으로 한다. 상기 방법은, 링크 요소(linking element)에 의해 데이터 처리 요소가 결합되는 계산 그래프의 사양(specification)을 받아들이는 단계, 상기 데이터 처리 요소를, 하나 이상의 세트가 상기 데이터 처리 요소를 복수 개 포함하는 세트로 분할하는 단계, 각각의 상기 세트에 상이한 계산 자원을 할당하는 단계, 및 할당된 상기 계산 자원을 이용하여 상기 데이터 처리 요소에 대응하는 계산을 수행하는 단계를 포함하는, 상기 계산 그래프에 따라 데이터를 처리하는 단계를 포함한다.
또 다른 특징에서, 전반적으로, 본 발명은 컴퓨터 판독 가능 매체에 기억되고, 그래프 기반 계산을 실행하기 위한 컴퓨터 프로그램을 특징으로 한다. 상기 컴퓨터 프로그램은, 컴퓨터 시스템으로 하여금, 링크 요소에 의해 데이터 처리 요소가 결합되는 계산 그래프의 사양을 받아들이는 단계, 상기 데이터 처리 요소를, 하나 이상의 세트가 상기 데이터 처리 요소를 복수 개 포함하는 세트로 분할하는 단계, 각각의 상기 세트에 상이한 계산 자원을 할당하는 단계, 및 할당된 상기 계산 자원을 이용하여 상기 데이터 처리 요소에 대응하는 계산을 수행하는 단계를 포함하는, 상기 계산 그래프에 따라 데이터를 처리하는 단계를 행하도록 하는 명령을 포함한다.
또 다른 특징에서, 전반적으로, 본 발명은 그래프 기반 계산을 수행하는 시스템을 특징으로 한다. 상기 시스템은, 링크 요소에 의해 데이터 처리 요소가 결합되는 계산 그래프의 사양을 받아들이고, 또한 상기 데이터 처리 요소를, 하나 이상의 세트가 상기 데이터 처리 요소를 복수 개 포함하는 세트로 분할하기 위한 회로를 포함하는 사전 실행(pre-execution) 모듈을 포함한다. 또한, 상기 시스템은, 각각의 상기 세트에 상이한 계산 자원을 할당하고, 또한 할당된 상기 계산 자원을 이용하여 상기 데이터 처리 요소에 대응하는 계산을 수행하는 것을 포함한, 상기 계산 그래프에 따라 데이터를 처리하기 위한 회로를 포함하는 실행 모듈을 포함한다.
본 발명의 특징은 이하의 특징 중 하나 이상을 포함할 수 있다.
상기 세트에 할당된 하나 이상의 상기 계산 자원은 프로세스를 포함한다.
각각의 상기 링크 요소는 상류측 데이터 처리 요소의 출력에서부터 하류측 데이터 처리 요소의 입력으로의 데이터 흐름과 연관된다.
상기 데이터를 처리하는 단계는, 상기 세트의 하나 이상의 세트에 대하여, 상기 세트 내의 상기 데이터 처리 요소를 결합시키는 상기 링크 요소에 의해 정해지는 시퀀스에 따라 상기 세트 내의 상기 데이터 처리 요소에 대응하는 계산을 수행하는 단계를 포함한다.
상기 세트에 할당된 상기 계산 자원은, 상기 하류측 데이터 처리 요소에 연관된 함수를 호출함으로써, 상기 상류측 데이터 처리 요소의 출력으로부터의 데이터 흐름에 연관된 작업 요소를 상기 상류측 데이터 처리 요소와 동일한 세트 내의 상기 하류측 데이터 처리 요소의 입력으로 전달한다.
상기 함수는, 상기 작업 요소가 상기 상류측 데이터 처리 요소에 연관된 함수에 의해 기입된 기억 지점으로부터 상기 작업 요소를 읽어들인다.
상기 상류측 데이터 처리 요소에 연관된 함수 및 상기 하류측 데이터 처리 요소에 연관된 함수는, 동일한 프로세스에 의해 호출된다.
상기 데이터를 처리하는 단계는, 각각의 세트 내의 개개의 상기 데이터 처리 요소에 연관된 각각의 활동의 정도(quantity of activity)의 특성을 기술하는 정보를 유지하는 단계를 더 포함한다.
각각의 상기 활동의 정도는 각각의 상기 데이터 처리 요소에 따라 처리된 데이터의 양을 포함한다.
각각의 상기 활동의 정도는 각각의 상기 데이터 처리 요소에 대응하는 계산을 수행하는 상기 세트에 할당된 계산 자원에 의해 소비된 시간의 양을 포함한다.
상기 세트 내의 상기 데이터 처리 요소는 상기 계산 그래프의 연결된 방향성 서브그래프(connected directed subgraph)를 형성한다.
상기 서브그래프는 트리(tree)를 포함한다.
복수의 입력을 갖는 상기 세트 내의 각각의 상기 데이터 처리 요소에 대하여, 그 데이터 처리 요소의 입력에 링크된 상류측 데이터 처리 요소의 전부가 또한 그 세트 내에 있다.
서브그래프에 상류측 요소를 갖지 않는 서브그래프 내의 상기 데이터 처리 요소에 대한 제어 메시지의 수신에 응답하여, 상기 제어 메시지를 상기 서브그래프의 외측에 전파하기 전에, 상기 서브그래프 내의 각각의 상기 데이터 처리 요소에 대한 상태 정보를 비휘발성 기억부에 저장하기 위해, 상기 서브그래프 내의 다른 데이터 처리 요소의 각각에 연관된 함수가 호출된다.
상기 서브그래프 내의 각각의 상기 데이터 처리 요소에 대한 상태 정보는 하나의 파일에 저장된다.
상기 데이터 처리 요소는 지정된 정도의 병렬 계산(parallelism)을 갖는다.
상기 세트 내의 각각의 상기 데이터 처리 요소는 동일한 정도의 병렬 계산을 갖는다.
상기 계산 그래프의 상기 사양은 각각의 상기 데이터 처리 요소에 연관된 실행의 단계(phase)를 나타낸다.
상기 세트 내의 각각의 상기 데이터 처리 요소는 동일한 실행 단계(same phase of execution)에 연관된다.
본 발명의 특징은 이하의 장점 중의 하나 이상을 가질 수 있다.
데이터 처리 어플리케이션을 데이터 흐름 계산 그래프로서 표현하는 것은 어플리케이션을 구축하고 수반된 계산을 이해 및 분석하는 프로세스에서 개발자에게 도움을 준다. 계산은 프로세스에 의해 호스트 운영 체제에서 수행된다. 각각의 프로세스는 처리 시간 및 메모리 등의 계산 자원에 연관된다. 각각의 프로세스에 연관된 오버헤드로 인해, 계산 시스템에 의해 사용된 전체적인 계산 자원은 통상적으로 동시에 실행하는 프로세스의 수와 함께 증가한다(일부 경우에는 모든 자원이 프로세스의 수와 선형적으로 비례하지는 않음). 프로세스 카운트를 감소시키기 위해, 계산은 계산 그래프 프로그래밍의 일부 장점(예컨대, 사용의 편의, 이해의 용이 등)이 희생되기는 하지만 "수동(by hand)"으로 더 작은 수의 프로세스로 조합될 수 있다.
계산 프로세스로서 구현된 데이터 흐름 계산 그래프에서, 버퍼링은 전체 레이턴시(end-to-end latency)가 증가하되기는 하지만 처리 오버헤드를 감소시킬 수 있다. 버퍼링이 없다면, 레이턴시는 감소될 수 있지만, 더 작은 양의 데이터를 이동시키기 위해 더 큰 운영 체제 자원이 이용되므로, 오버헤드는 증가될 것이다.
과도한 오버헤드와 과도한 레이턴시 간의 이러한 상충을 경감시키기 위해, 복수의 그래프 성분은, 데이터를 카피 없이 메모리에 넘겨주거나 또는 프로세스 간에 데이터를 이동시켜야 하는 것과 같이 한 번에 하나의 성분의 작업을 수행하는 하나의 프로세스로서 실행될 수 있다(또는 하나의 프로세스로 폴딩될(folded) 수 있다). 이러한 방식에서, 데이터는 단일 프로세스 내의 성분의 네트워크를 통해 푸시(push)된다.
예컨대, 폴딩되지 않은 실행에서, 데이터 흐름에 의해 연결되고 각각 별도의 프로세스에서 실행되는 2개의 성분은 버퍼를 이용하여 통신한다. 제1 성분은 자신이 생성한 출력(예컨대, 복수의 출력 작업 요소의 누적)을 버퍼에 기억시킨다. 제1 성분은 예컨대 운영 체제 호출을 이용하여 버퍼를 제2 성분에 넘겨준다. 제2 성분은 그 버퍼 내의 데이터를 처리한다. 2개의 프로세스가 동일한 프로세스에서 함께 폴딩되면, "폴딩된 실행(folded execution)"에서, 폴딩된 프로세스는 작업 요소를 생성하고 받아들이는 연관된 과정(procedure)을 제어하므로 작업 요소를 버퍼링할 필요가 없다. 폴딩된 프로세스는, 제1 성분에 연관된 과정에 의해 생성된 각각의 작업 요소를 생성된 그대로 제2 입력 성분에 연관된 과정에, 데이터 흐름이 제어 흐름으로서 실현되는 입력 아규먼트(input argument)로서 넘겨준다.
폴딩된 실행 또는 폴딩되지 않은 실행 중의 어느 하나에서, 성분은 연관된 정도의 병렬 계산을 가질 것이다. 폴딩되지 않은 실행에서, 성분의 병렬 계산의 정도와 동일한 다수의 프로세스가 작성될 수 있다. 폴딩된 프로세스에서, 동일한 정도의 병렬 계산을 갖는 연결된 성분은 동일한 프로세스에서 개시될 수도 있으며, 이로써 일반적인 정도의 병렬 계산과 동일한 수의 프로세스가 생성된다.
복수의 성분을 단일 프로세스로 폴딩하는 것은, 프로세스 동안의 데이터 이동을 감소시키고 또한 계산 그래프의 개시 시간 및 시스템 점유공간(system footprint)을 감소시킴으로써 성능을 향상시킨다(실행하는 전체 프로세스가 더 적기 때문에). 데이터를 버퍼링하지 않고 또한 레이턴시를 증가시키지 않고서도 과도한 문맥 전환이 방지된다. 이 모두는 표현성(expressibility), 사용의 편의, 및 그래프 모델에 대한 데이터 흐름 계산의 명료성을 희생시키지 않고서도 이루어진다.
본 발명의 기타 특징 및 장점은 이하의 상세한 설명 및 첨부된 청구범위로부터 더욱 명확하게 될 것이다.
도 1은 그래프 기반 계산을 위한 시스템의 블록도이다.
도 2a 및 도 2b는 계산 그래프이다.
도 3a 및 도 3b는 병렬 계산 그래프이다.
도 4는 폴딩된 세트에 성분을 할당하기 위한 과정의 흐름도이다.
1. 시스템 개요(System Overview)
도 1을 참조하면, 그래프 기반 계산을 실행하기 위한 시스템(100)은 데이터 기억부(102)에 연결된 개발 환경(104) 및 데이터 기억부(102)에 연결된 런타임 환 경(106)을 포함한다. 개발자(101)는 개발 환경(102)을 이용하여 어플리케이션을 구축한다. 어플리케이션은 개발자가 개발 환경을 사용한 결과로서 데이터 기억부에 기입될 수도 있는 데이터 기억부(102) 내의 데이터 구조에 의해 특정된 하나 이상의 계산 그래프와 관련된다. 데이터 구조는 예컨대 계산 그래프의 정점(성분 또는 데이터 세트) 및 정점 간의 링크(데이터 흐름)를 특정한다. 데이터 구조는 또한 그래프의 성분, 데이터 세트, 및 데이터 흐름의 각종 특성을 포함할 수 있다. 데이터 처리 어플리케이션은 예컨대 하나 이상의 입력 데이터 세트로부터 성분을 처리하는 그래프를 통해 하나 이상의 출력 데이터 세트로 흐르는 데이터에 수행된 계산을 구현하는 계산 그래프와 관련될 수도 있다.
런타임 환경(106)은 UNIX 운영 체제와 같은 적합한 운영 체제의 제어 하에 하나 이상의 범용 컴퓨터 상에 호스팅될 수 있다. 예컨대, 런타임 환경(106)은 복수의 중앙 처리 장치(CPU)를 로컬(예컨대, SMP 컴퓨터 등의 멀티프로세서 시스템), 로컬 분산(예컨대, 클러스터 또는 MPP로서 연결된 복수의 프로세서), 원격, 원격 분산(예컨대, LAN 또는 WAN 네트워크를 통해 연결된 복수의 프로세서), 또는 이들의 임의의 조합으로 이용하는 컴퓨터 시스템의 구성을 포함한 복수 노드 병렬 계산 환경을 포함할 수 있다. 런타임 환경(106)에 의해 액세스되는 입력, 출력 또는 중간 데이터 세트는 병렬 파일 시스템(예컨대, 데이터 기억부(102), 또는 통신 링크를 통해 시스템(100)에 로컬 또는 원격으로 연결된 외부 데이터 기억부)에 기억된 병렬 "멀티파일(multifile)"이 될 수 있다.
그래프에서의 복수의 성분의 동시 실행은 병렬 계산의 한 형태를 제공한다. 추가의 병렬 계산은 그래프의 상이한 성분을 상이한 계산 노드에 분배함으로써 달성될 수 있다. 그래프의 요소(예컨대, 데이터 세트, 성분 및 흐름)는 런타임 환경(106)에 추가의 병렬 계산을 제공하기 위해 명시적으로(explicitly) 또는 암묵적으로(implicitly) 복사(replication)될 수 있다.
런타임 환경(106)은 기억된 스크립트로부터의 제어 입력 또는 계산을 실행하고 구성하기 위한 사용자(103)로부터의 입력을 수신하도록 구성된다. 제어 입력은 기억된 그래프 데이터 구조에서 특정되는 대응하는 계산 그래프를 이용하여 특정 데이터 세트를 처리하기 위한 명령을 포함할 수 있다. 사용자(103)는 예컨대 명령 라인 또는 그래프 인터페이스를 이용하여 런타임 환경(106)과 대화(interaction)할 수 있다.
런타임 환경(106)은, 소정의 계산 그래프를 특정하는 기억된 그래프 데이터 구조를 판독하고 또한 성분의 계산을 수행하기 위한 프로세스(예컨대, 호스트 운영 체제 내에서의 실행의 프로세스 또는 쓰레드(thread))와 같은 자원 계산을 할당 및 구성하기 위해 사전 실행 모듈(110)을 포함한다. 아래에 더욱 상세하게 설명된 바와 같이 계산 그래프를 실행할 때에 프로세스에 성분을 할당하는 여러 가지의 방식이 있다.
사전 실행 모듈(110)은 또한 성분(예컨대, 네임드 파이프 또는 공유 메모리) 간의 데이터 흐름을 구현하기 위해 성분간 통신 자원을 할당하고, 프로세스가 아직 새로운 작업 요소를 받아들일 준비가 안된 성분의 입력 포트에 도착하는 작업 요소를 위해 저장 공간을 할당한다. 성분 간의 데이터 흐름을 통해 작업 요소를 넘겨 주기 위한 자원은 시스템(100)의 처리 및 기억 오버헤드에 기여한다. 일부 방식에서, 성분간 통신은 이러한 오버헤드를 감소시키는 펑션 콜(function call)을 통해 구현된다.
런타임 환경(106)은 사전 실행 모듈(110)에 의해 계산 그래프에 할당된 프로세스의 실행을 스케줄하고 제어하기 위해 실행 모듈(112)을 포함한다. 실행 모듈(112)은 데이터베이스 엔진, 데이터 기억부, 또는 그래프 성분과 연관된 처리 동안에 액세스되는 기타 모듈과 같은 시스템(100)에 연결된 외부 계산 자원과 대화할 수 있다.
계산 그래프의 실행 후 또는 실행 중의 소정 구간에서, 보고 모듈(114)은 계산 그래프의 개개의 성분과 연관된 통계자료(statistics)와 같은 소정의 계산의 특성을 기술하는 정보를 제공한다. 보고 모듈(114)에 의해 보고된 정보의 일부분은 계산 그래프에 의해 생성된 출력으로부터 획득된다. 보고된 정보의 일부분은 계산 그래프의 실행을 모니터링함으로써 획득된다.
런타임 모니터링 모듈(RMM)(116)은 계산 그래프에 할당된 하나 이상의 프로세스의 실행을 모니터하고, 정보를 보고 모듈(114)에 제공한다. 이러한 정보는 예컨대 각각의 성분을 동작시키도록 예정된 중앙 처리 장치(CPU) 시간, 또는 각각의 성분에 의해 처리된 데이터의 양을 포함한다.
2. 그래프 실행(Graph Execution)
도 2a를 참조하면, 계산 그래프(200)의 예는 계산 그래프(200)의 성분(204A∼204J)에 의해 처리될 일련의 작업 요소를 제공하는 입력 데이터 세트(202)를 포 함한다. 예컨대, 데이터 세트(202)는 데이터베이스 시스템에 연관된 데이터 레코드 또는 트랜잭션 처리 시스템(transaction processing system)과 연관된 트랜잭션을 포함할 수 있다. 각각의 성분은 전체적인 계산 그래프(200)에 의해 정해진 계산의 일부분에 연관된다. 작업 요소(예컨대, 개개의 데이터 레코드)는 성분의 하나 이상의 입력 포트에 진입하며, 출력 작업 요소(일부 경우에는 입력 작업 요소이거나 또는 입력 작업 요소의 처리된 버젼임)는 통상적으로 성분의 하나 이상의 출력 포트에서 빠져나온다. 그래프(200)에서, 성분(204E, 204G, 204J)으로부터의 출력 작업 요소는 출력 데이터 세트(206A∼206C)에 기억된다.
그래프(200)에서, 제1 필터 성분(204A)은 입력 포트를 통해 수신된 작업 요소의 서브세트를 선택하여 제2 필터 성분(204B)에 보내고, 선택되지 않은 작업 요소를 성분(204C)에 보내며, 이 성분은 성분(204D)에 입력된다. 제2 필터 성분(204B)은 입력 포트를 통해 수신된 작업 요소의 서브세트를 선택하여 성분(204E)에 보내며, 이 성분은 출력 데이터 세트(206A)에 입력된다. 제2 필터 성분(204B)으로부터의 선택되지 않은 작업 요소는 복사 성분(204F)에 보내지며, 복사 성분은 각각의 작업 요소의 카피를 출력 데이터 세트(206B)에 입력되는 성분(204G)과 인터페이스 성분(204H)에 보낸다. 인터페이스 성분(204H)은 런타임 환경(106)에 완전히 내재되지 않은 "외부 프로그램"의 실행을 트리거하기 위한 인터페이스를 제공한다. 예컨대, 이 외부 프로그램은 런타임 환경(106)에 완전히 통합되지 않은 언어로 작성된 리가시 프로그램(legacy program)일 수도 있다. 인터페이스 성분(204H)은 외부 프로그램이 개발 환경의 본래 언어를 이용하여 기록될 필요없이 외부 프로 그램을 계산 그래프(200)의 일부로서 실행하기 위한 메카니즘을 제공한다. 집합 성분(gather component)(204I)은 인터페이스 성분(204H) 및 성분(204D)으로부터의 데이터 흐름을 조합하고, 작업 요소의 조합된 데이터 흐름을 성분(204J)에 보내며, 이 성분은 출력 데이터 세트(206C)에 입력된다.
2.1 별도의 프로세스(Seperate Process)
계산 그래프를 실행하는 제1 유형의 방식에서, 사전 실행 모듈(110)은 각각의 성분에 대하여 별도의 프로세스를 할당한다. 예컨대, "성분 당 하나의 프로세스" 방식에서는, 각각의 성분에 대하여 하나의 프로세스가 할당된다. 성분에 대응하는 프로세스는 그 성분에 의해 규정된 데이터 액세스, 계산, 및 데이터 변환 태스크를 처리한다. 실행 모듈(112)은 호스트 운영 체제에서의 프로세스를 착수(launching)시키고, 성분의 프로세스에 의해 수행되지 않은 계산 그래프에 연관된 태스크를 처리한다.
그래프 성분이 연관된 정도의 병렬 계산을 가질 때, 사전 실행 모듈(110)은 그래프 성분의 상이한 인스턴스(instance)에 대하여 성분의 병렬 계산의 정도와 동일한 개수의 별도의 프로세스를 할당한다. 예컨대, 성분은 옵션으로 N-방향 병렬 성분으로서 지정된다(예컨대, 개발자(101)에 의해). N-방향 병렬 성분에 대하여, 성분의 N개의 인스턴스의 각각은 N개의 노드 중의 한 노드에서의 프로세스로서(또는 멀티-쓰레디드 프로세서에서의 가벼운 프로세스의 쓰레드 또는 다른 형태로서) 실행된다. 이들의 경우에, 병렬 성분의 인스턴스 당 하나의 프로세스 또는 쓰레드가 존재한다.
도 3a를 참조하면, 병렬 그래프(300)는 출력 멀티파일(306)에 연결된 일련의 3개의 N-방향 병렬 성분(304A, 304B, 304C)에 연결된 입력 멀티파일(302)을 포함한다. 이 예에서, 입력(출력) 멀티파일은 N개의 프로세스에 의한 병렬 액세스가 N개의 파티션된 데이터 흐름을 제공하도록(받아들이도록) 하는 N-방향 병렬형이다. 이와 달리, 입력 및 출력 데이터 세트는 직렬로 액세스된 데이터 파일이거나, 또는 입력(302)과 최초 성분(304A) 간의 및/또는 최종 성분(304C)과 출력(306) 간의 데이터 흐름에 대하여 리파티셔닝 성분(repartitioning component)을 이용하여 N개보다 많거나 적은 파티션을 갖는 멀티파일일 수 있다. 그래프(300)가 성분 인스턴스 당 하나의 프로세스를 이용하여 실행될 때, 동시에 동작하는 3N개의 프로세스가 존재한다.
전술한 성분 당 하나의 프로세스 또는 인스턴스 당 하나의 프로세스 방식은 시스템(100)이 파이프라인 병렬 계산의 이점을 이용하도록 하여 복수의 성분이 데이터를 동시에 처리하도록 함으로써 계산 그래프의 처리량을 증가시킨다. 그러나, 각각의 프로세스와 연관된 오버헤드는 시스템 성능을 제한할 수 있다. 예컨대, 개시 시간(startup time)은 일부 경우에는 성분 프로세스를 개시하기 위해 요구되는 시간에 의해 좌우된다. 따라서, 더 많은 성분을 갖는 그래프는 개시하는데 더 오래 걸릴 수도 있다. 이러한 그래프는 동시에 동작될 수 있는 계산 그래프의 수를 제한하는 대형 메모리 점유공간(larger memory footprint)을 가질 수도 있다. 개발자(101)는 일부 경우에 복수의 성분에 구현된 로직을 하나의 더욱 복잡한 성분 내에 통합함으로써 그래프 내의 성분의 수를 감소시킬 수도 있을 것이다. 그러나, 이러한 수동 그래프 조작은 항상 가능하거나 항상 바람직한 것은 아닐 수도 있다(예컨대, 성분의 사용의 편의, 이해가능성, 또는 재사용 가능성을 유지하기 위해).
2.2 성분 폴딩(Component Folding)
계산 그래프를 실행하는 제2 유형의 방식에서, 사전 실행 모듈(110)은 옵션으로 복수의 성분을 실행하기 위해 일부 프로세스를 할당한다. 예컨대, "성분 폴딩" 방식에서, 사전 실행 모듈(110)은 그래프의 성분을 각각 하나 이상의 성분을 포함하는 하나 이상의 세트로 분할한다. 각각의 세트는 상이한 프로세스가 할당된다. 그러므로, 동일한 세트로 "함께 폴딩된" 성분에 대하여, 이들 성분에 의해 표현된 계산은 동일한 프로세스에 의해 실행된다. 복수의 성분을 갖는 세트에 대하여, 실행 모듈(112)은 호스트 운영 체제에서의 "폴딩된 프로세스"를 착수시킨다.
폴딩된 프로세스는 세트 내의 각각의 성분에 의해 규정된 데이터 액세스, 계산, 및 데이터 변환 태스크를 처리하고, 세트 내의 성분들 간의 링크를 통한 통신을 펑션 콜로서 구현한다. 폴딩된 프로세스는 소정의 입력으로 제1 "루트" 성분의 계산을 발생시키는 계산 함수(compute function)를 호출한다. 루트 성분 계산이 출력 포트에 연관된 결과를 발생한 후, 폴딩된 프로세스는 그 결과를 하류측 성분에 대한 입력으로 이용하여 링크된 하류측 성분의 계산 함수를 호출한다. 따라서, 데이터가 루트 성분으로부터 서브세트 내의 하류측 "내측" 성분으로 푸시된다. 일부 경우에, 서브세트는 서브세트의 내측 성분에 작업 요소를 공급하는 2개 이상의 루트 성분을 가질 수 있다. 이러한 성분 폴딩 방식은, 개시 레이턴시를 감소시킬뿐만 아니라, 서브세트 내의 성분간 통신에 연관된 처리 및 저장 오버헤드와 레이 턴시를 감소시킨다.
예컨대, 하나의 작업 요소에 대하여 한 번에 리포맷팅 또는 필터링을 수행하는 일부 성분은 이러한 실행의 "푸시 모델"과 이미 호환 가능하다. 푸시 성분이 제1 작업 요소를 처리하는 것을 완료한 후, 푸시 성분은 새로운 작업 요소가 입력 포트에서 이용 가능하게 되는 즉시 새로운 작업 요소를 처리하려고 한다. 이 푸시 모델에서, 상류측 성분은 작업 요소를 하류측 성분에 푸시하고, 하류측 성분은 그 계산을 수행하며, 그리고나서 하류측 성분은 그 결과를 자신의 하류측 성분에 푸시하는 등등의 순서로 이루어진다.
다른 성분은 초기에는 이러한 푸시 모델에 따라 동작하도록 구성되지 않고, 그 대신 실행의 "풀 모델(pull model)"에 따라 동작하도록 구성될 수도 있다. 풀 성분의 예는 작업 요소가 도착하는 입력 포트에 좌우되는 계산을 수행하는 복수의 입력 포트를 갖는 성분이다. 성분은 제2 입력 포트에서 작업 요소를 대기하고 있기 때문에(예컨대, 분류 동작 또는 결합 동작을 수행하는 성분) 제1 입력 포트에서 작업 요소를 처리할 준비가 되어있지 않을 수도 있다. 다른 유형의 풀 성분(pull component)은 하나의 입력 포트를 가질 수도 있다. 그러므로, 폴딩된 프로세스가 풀 성분을 위한 입력 작업 요소에 대해 동작하기 위해 계산 함수를 호출할 수 있을 필요는 없을 것이다.
풀 성분은 처리의 순서에서의 일부 논리 브레이크(logical break)(예컨대, 파일의 종료, 또는 관련되지 않은 작업의 유닛 사이의 경계를 표시하는 일부 다른 이벤트)까지 자신의 입력의 전부가 버퍼를 갖도록 함으로써 푸시 성분으로서 수정 될 수 있다. 이 경우, 풀 성분에 대한 계산 함수는 각각의 인입 레코드를 버퍼에 삽입하고, 논리 브레이크에서, 계산 함수가 결정한 어떠한 순서로든 버퍼로부터 읽어들인 입력의 전부를 처리하도록 진행한다.
폴딩된 프로세스는 연관된 폴딩된 성분의 계산을 스케줄하기 위해 다른 방식을 사용할 수 있다. 예컨대, 폴딩된 프로세스는 어느 성분이 작동하려고 준비되는지를 결정하기 위해 상태 정보를 테스트할 수 있다.
2.2.1 폴딩 제한(Folding Constraints)
사전 실행 모듈(110)은, 옵션으로 개발자(101) 또는 사용자(103)에 의한 폴딩된 세트(folded set)로의 성분의 수동 할당 또는 성분이 동일한 폴딩된 세트에 있어야 하는지 아니면 상이한 폴딩된 세트에 있어야 하는지에 대한 기타 제한을 고려하여, 어느 성분이 동일한 세트로 함께 폴딩되어야 하는지를 결정하기 위해 그래프를 분석한다. 사전 실행 모듈(110)은 어느 성분이 함께 폴딩되어야 하는지를 결정하기 위해 이하의 제한을 고려할 수 있다. 일부 과정은 수반되는 추가의 처리를 다루기 위해 폴딩된 프로세스에 대한 메카니즘을 제공함으로써 이들 제한의 일부 또는 전부를 생략할 수도 있다.
첫 번째 제한은 성분이 "폴딩 가능(foldable)"으로 지정되는지 아니면 "폴딩 불가능(non-foldable)"으로 지정(예컨대, 개발자(101)에 의해)되는지의 여부에 좌우된다. 폴딩 가능으로 지정된 성분은 그 성분의 대응하는 계산을 호출하기 위해 폴딩된 프로세스에 의해 사용될 수 있는 피쳐(feature)를 포함한다. 예컨대, 폴딩 가능 성분은 그 성분과 연관된 계산을 호출하기 위해 런타임 환경(106)에서 작동하 는 폴딩된 프로세스에 의해 호출될 수 있는 계산 함수를 갖는다. 리가시 프로그램을 실행하는 인터페이스 성분은 이러한 펑션 콜과 호환되지 않을 수도 있고, 그에 따라 폴딩 불가능한 것으로서 지정될 수도 있다. 다른 성분은 수행되는 계산의 본질로 인해 폴딩 불가능한 것으로서 지정될 수도 있다(예컨대, 계산이 외부 환경과의 복잡한 대화를 수반함).
또 다른 제한은 그래프의 상이한 부분이 실행되는 단계(phase)의 지정에 좌우된다. 예컨대, 상류측 성분의 제1 그룹이 제1 단계에서 작동하도록 선택되며, 이들 성분이 작업 요소의 묶음(batch)으로 완료된 후, 하류측 성분의 제2 그룹이 제2 단계에서 그 묶음에 대해 작동하도록 선택된다. 일부 경우에, 소정의 단계에서의 성분에 대한 프로세스만이 소정 시각에 작동한다. 다른 경우에, 상이한 단계에서의 프로세스가 파이프라인 계산 처리를 달성하기 위해 상이한 묶음에 대해 동시에 작동될 수도 있지만, 단계는 소정 시각에 작업 요소의 소정의 묶음을 처리할 성분의 그룹을 지정하기 위해 이용될 수도 있다. 둘 중의 한 경우, 이러한 제한은 소정 단계에서의 성분이 동일한 단계에서의 성분과 함께 폴딩되어야 한다는 것을 유지시킨다.
또 다른 제한은 성분에 대하여 지정된 병렬 계산의 정도에 관련된다. 성분은 직렬형 또는 N-방향 병렬형으로서 지정된다. 전술한 바와 같이, N-방향 병렬 성분에 대하여, 성분의 N개의 인스턴스의 각각은 별도의 프로세스에서 실행된다. 성분 폴딩 방식(component folding approach)에서는, 병렬로 작동할 수 있는 N개의 성분 인스턴스가 있지만, 성분 인스턴스는 다른 성분 인스턴스와 함께 폴딩될 수 있다. 이 제한에서, 동일한 정도의 병렬 계산을 갖는 성분만이 함께 폴딩된다. 직렬 성분은 다른 직렬 성분과 함께 폴딩되며, N-방향 병렬 성분은 다른 N-방향 병렬 성분과 함께 폴딩된다. 예컨대, 도 3b는 도 3a에서의 병렬 성분이 함께 폴딩되는 방법을 예시하고 있다. 그래프(300')가 성분 폴딩을 이용하여 실행될 때, 동시에 작동하는 N개의 폴딩된 프로세스가 있다. 성분의 세트(312)의 N개의 인스턴스의 각각에 대해서는 하나의 폴딩된 인스턴스가 있다.
또 다른 관련된 제한은, 함께 폴딩된 성분이 그 데이터 흐름에 의해 표현된 작업 요소의 파티셔닝을 변경하지 않는 "직선(straight)" 데이터 흐름에 의해 연결된다는 것이다. 예컨대, 일부 데이터 흐름은 N-방향 병렬 성분으로부터 흐르는 작업 요소의 N개의 파티션을 M개의 파티션으로 리파티션할 수도 있다(여기서, M≠N이거나, 아니면 M=N이고, 작업 요소가 N개의 파티션 중에 리셔플(reshuffle)됨). 이 제한에서, 함께 폴딩된 성분은 동일한 정도의 병렬 계산을 가지며, 폴딩된 성분 중에서 작업 요소의 명시적 또는 암묵적 리파티셔닝이 없다.
그래프의 성분을 폴딩된 세트로 할당하기 위한 준비에서, 사전 실행 모듈(110)은 그래프 내의 어느 폴딩 가능 성분이 루트 성분(root component)이 될 수는 있지만 내측 성분이 될 수는 없는지와, 어느 폴딩 가능 성분이 루트 성분 또는 내측 성분이 될 수 있을지를 결정한다. 예컨대, 일부 성분은 폴딩된 프로세스에 의해 호출될 수 있는 연관된 계산 함수를 갖도록 구성되지 않을 수도 있다.
성분을 루트 성분이 될 수 있는 성분 및/또는 내측 성분이 될 수 있는 성분으로서 카테고리화하는 것은 예컨대 이들 성분이 개발되고 있을 때에와 같이 오프 라인으로 이루어질 수 있다. 그래프를 구축하는 데 이용 가능한 성분에 연관된 데이터 기억부(102)에 기억된 데이터 구조는, 그 성분이 폴딩 가능 성분인지 아니면 폴딩 가능하지 않은 성분인지의 여부 및 그 성분이 루트 성분이 될 수 있는 성분 및/또는 내측 성분이 될 수 있는 성분인지의 여부를 나타내는 메타데이터를 포함할 수 있다.
2.2.2 폴딩된 세트를 결정(Determining Folded Sets)
도 4는 그래프의 성분을 폴딩된 세트에 할당하기 위해 사전 실행 모듈(110)에 의해 사용되는 일례의 과정(400)에 대한 흐름도를 도시하고 있다. 과정(400)은 각각의 폴딩된 세트를 가능한 한 대형화하는 그리디 알고리듬(greedy algorithm)을 기반으로 한다. 이 과정(400)에 의해 발생된 폴딩된 세트는 그래프의 연결 서브그래프의 하나 이상의 내측 성분에 대한 데이터의 흐름을 제공하는 단일 루트 성분을 갖는다. 폴딩된 세트는 또한 중첩되지 않는다. 사전 실행 모듈(110)은 예컨대 실행 시각의 훨씬 전에 과정(400)을 수행하여 그 결과를 데이터 기억부(102)에 저장할 수 있거나, 또는 그래프가 실행 모듈(112)에 의해 실행되기 직전에 과정(400)을 수행할 수 있다. 예컨대, 사전 실행 모듈(110)은, 구체적으로 후술되는 바와 같이, 그래프가 실행되기 전이지만 조건부 성분이 그래프로부터 제거된 후에 실행시간(runtime)에 과정(400)을 수행할 수 있다.
과정(400)은 후술되는 폴딩 제한의 일부를 이용한다. 성분이 폴딩 가능한 것이고, 세트 내의 성분과 동일한 정도의 병렬 계산을 가지며, 세트 내의 성분과 동일한 단계에 있고, 직선 흐름에 의해 세트 내의 성분에 연결된다면, 이 성분은 폴딩된 세트에 대한 제한을 충족한다.
과정(400)은 그래프 내의 각각의 성분을 "할당되지 않음"으로 표시하는 단계(402)에 의해 개시된다. 과정(400)은 상류측 성분에서부터 하류측 성분으로의 지형적인 순서(예컨대, 깊이-우선 탐색(depth-first search) 순서)에 기초하여 그래프 내의 성분을 검사한다. 과정(400)은 입력 데이터 세트에 연결된 성분 또는 입력 포트를 갖지 않는 성분에서 출발하고, 이 성분을 루트로서 제1 세트에 할당한다(404). 과정은 루트가 폴딩 가능한지를 판정한다(406). 루트 성분이 폴딩 가능한 경우, 과정(400)은 제한을 충족하는 현재 세트 내의 성분의 바로 아래에 연결된 어떠한 할당되지 않은 폴딩 가능 성분이 있는지의 여부를 판정한다(408). 이러한 성분이 발견되면, 그 성분은 현재 세트에 추가되고(410), "할당됨"으로서 표시된다(412). 과정은 할당되지 않은 폴딩 가능 성분이 추가될 수 있는지를 판정한다(408). 일부 경우에, 세트에 할당된 폴딩 가능 루트 성분은 어떠한 다른 성분과 함께 폴딩되지 않으며, 그 성분 전용의 프로세스에 의해 실행될 독자 세트(singleton set)에 홀로 남겨진다.
현재 세트가 더 대형의 것으로 성장할 수 없을 때(예컨대, 세트에 연결된 잔여 성분이 이미 할당되었거나 또는 모든 제한을 충족하지 못할 때), 과정(400)은 그래프에 남겨진 어떠한 할당되지 않은 성분이 있는지를 판정하고(414), 그래프에 남겨진 어떠한 할당되지 않은 성분이 있다면, 입력 데이터 세트에 연결되거나 입력 포트를 갖지 않거나 또는 할당된 성분에 연결된 할당되지 않은 성분으로부터 새로운 루트 성분을 할당한다(404).
루트 성분이 폴딩 불가능한 성분이면, 과정(400)은 이 루트 성분을 그 성분 전용의 프로세스에 의해 실행될 자신의 세트에 홀로 남겨두고, 어떠한 할당되지 않은 성분이 남아있으면 새로운 루트 성분을 선택한다. 과정(400)은 할당되지 않은 성분이 남아있지 않을 때에는 종료된다(416).
도 2b는 과정(400)에 따른 그래프(200)에서 식별된 3개의 폴딩된 세트를 도시하고 있다. 과정(400)은 성분(204A)을 세트(210)의 루트로서 선택한다. 과정(400)은 성분(204B, 204E, 204F, 204G)을 폴딩된 세트(210)에 추가하는 지형적인 순서로 그래프를 진행해 간다. 성분(204H)은 폴딩 가능하여야 한다는 제한을 충족하지 못하므로 세트(210)에 추가되지 않는다. 과정(400)은 성분(204C, 204D)을 폴딩된 세트(210)에 추가한다. 세트(210)에 추가될 수 있는 다른 폴딩된 세트가 없으므로, 과정(400)은 폴딩 불가능한 성분(204H)을 갖는 제2 세트(211) 및 나머지 성분(204I, 204J)을 갖는 제3 세트(212)를 선택한다.
일부 계산 그래프에서, 성분은 그 자체가 계산 그래프로서 구현된다. 과정(400)은 그래프에서의 이러한 성분을 그래프 내의 서브그래프 내로 확장시킨다. 그러므로, 성분의 폴딩된 세트는 이러한 성분의 "부분 성분(sub-component)"의 어떠한 것도 포함하도록 이러한 삽입된 서브그래프의 경계에 걸치게 될 수도 있다.
일부 계산 그래프에서, 조건부 성분 메카니즘은 파라미터 값 및 계산된 메타데이터에 기초하여 그래프 구조로의 변경을 허용한다. 그래프의 조건부 성분은 그 성분이 실행시간에 그래프에서 나타날지의 여부를 제어하는 조건을 갖는다. 조건은 실행시간 파라미터를 통해 직접으로 또는 간접적으로 계산될 수 있다. 조건부 성분은 그래프를 최적화하거나 특수화하기 위해 사용될 수 있다. 조건부 성분은 본 명세서에 그 내용이 발명의 일부로서 원용되어 있는 2000년 7월 28일자로 출원된 미국 특허 출원 번호 09/627,252에 상세하게 개시되어 있다.
폴딩된 세트가 식별된 후, 사전 실행 모듈(110)은 폴딩된 세트 간의 버퍼 또는 어댑터와 같은 요소를 포함하도록 그래프를 수정할 수도 있다.
폴딩된 세트 내의 성분의 서브그래프의 지형에 대한 제한을 갖는 과정을 포함한 다른 과정이 폴딩된 세트를 결정하기 위해 이용될 수 있다. 예컨대, 일부 구현예에서, 폴딩된 세트 내의 성분의 연결된 서브그래프는 루트 성분 아래쪽의 하나의 입력 내측 성분을 갖는 트리 토폴로지(tree topology)를 갖는다. 일부 구현예에서, 폴딩된 프로세스는 폴딩된 세트 내에 복수 입력 성분을 허용하기 위한 동작을 수행할 수 있다. 예컨대, 복수 입력 성분이 루트 성분의 하류측이면, 폴딩된 프로세스는 복수 입력을 위한 데이터를 버퍼링하고, 모든 버퍼가 이용 가능한 데이터를 갖고 있다면 복수 입력 함수의 계산 함수를 호출한다. 폴딩된 세트는 세트 내의 각각의 복수 입력 성분의 각각에 대해 그 성분의 입력에 연결된 상류측 성분이 또한 그 세트 내에 있도록 하는 토폴로지를 가질 수도 있다.
2.2.3 폴딩된 프로세스를 실행(Executing Folded Process)
실행 모듈(112)은 사전 실행 모듈(110)에 의해 식별된 폴딩된 세트에 대응하는 폴딩된 프로세스를 개시한다. 사전 실행 모듈(110)은 각각의 폴딩된 세트 내의 성분을 식별하는 정보 및 이들 성분을 연결하는 데이터 흐름을 실행 모듈(112)에 제공한다. 실행 모듈(112)은 데이터 기억부(102) 내의 성분 객체(component object)에 대한 포인터를 포함하는 런타임 데이터 구조를 생성하고, 폴딩된 세트 내의 성분들 간에 통신될 작업 요소를 위한 저장 공간을 할당한다. 성분들 간에 작업 요소를 이동시키기 위해 할당된 저장 공간의 양 및 이를 위해 소요된 시간은, 폴딩된 프로세스가 상이한 성분에 대한 계산을 수행하면서 동일한 저장 공간을 액세스할 수 있기 때문에, 낮게 유지될 수 있다.
예컨대, 폴딩된 프로세스는 데이터 흐름에 대응하는 작업 요소를 기억하기 위해 할당된 저장 공간을 이용하여 상류측 성분으로부터 하류측 성분으로 데이터를 통신한다. 성분에 대한 계산 함수는 저장 공간 내의 적합한 위치를 지시하는 데이터 포인터 변수를 읽어들임으로써 작업 요소를 액세스할 수 있다.
상류측 성분의 계산 함수는, 하류측 성분에 대한 데이터 포인터 변수에 대응하는 저장 공간에 처리될 데이터가 포함되도록 한다. 일부 경우에, 이것은 상류측 성분이 단순히 하류측 성분에 의해 액세스될 저장 공간에 데이터를 기입하도록 하는 것을 수반한다. 그러나, 자신의 입력 데이터를 변경하지 못하는 성분(예컨대, 필터 성분)에 대하여, 데이터는 이미 액세스 가능한 위치에 기억될 수도 있고, 그 데이터는 이동될 필요가 없이 적합한 데이터 포인터 변수를 제공함으로써 준비될 수 있다.
각각의 폴딩된 프로세스는 폴딩된 세트 내의 성분을 연결하는 데이터 흐름에 의해 정해진 순서에 따라 계산 함수를 반복적으로 호출함으로써 성분에 대응하는 계산을 호출한다. 상류측 성분은 하류측 성분의 계산 함수를 호출한다. 계산 함수는 성분에 연관된 계산을 수행한다. 예컨대, 계산은 성분에 연관된 상태 변수를 갱신하고, 기억된 작업 요소를 변환하고, 새로운 작업 요소를 생성하고, 또는 출력 데이터가 적합한 저장 공간에 기억되도록 함으로써 하류측으로 데이터를 통신하는 것을 수반한다. 계산 함수가 폴딩된 프로세스에 대한 제어를 리턴할 때, 연관된 성분은 그 데이터 포인터 변수에 연관된 데이터를 처리한 것으로 간주된다.
루트 성분은 데이터가 폴딩된 세트에 공급되는 포인트이다. 다수의 경우에, 이것은 입력 스트림 또는 파일로부터 데이터를 판독함으로써 또는 데이터베이스 또는 큐(queue) 등의 외부 시스템으로부터 데이터를 추출함으로써 행해진다. 일부 경우에, 데이터는 루트 성분에 의해 생성된다. 루트 성분의 계산 함수는 폴딩된 프로세스에 대한 제어를 리턴하지 않고서는 폴딩된 세트를 통해 정해지지 않은 다량의 데이터를 푸시하지 못한다. 예컨대, 루트 성분의 계산 함수는 이하의 코드 중의 하나로 소정 구간에서 폴딩된 프로세스에 대한 제어를 리턴한다:
KEEP_GOING : 이 코드는 공급될 더 많은 데이터가 있다는 것을 나타낸다. 폴딩된 프로세스는 계산 함수를 다시 호출함으로써 응답한다.
ERROR : 이 코드는 에러가 발생하였다는 것을 나타낸다. 폴딩된 프로세스에 액세스 가능한 글로벌 "에러 상태" 변수는 상세한 에러 메시지를 포함한다. 폴딩된 프로세스는 예컨대 에러 메시지를 점멸함으로써 응답한다.
REACHED_EOF : 이 코드는 공급될 데이터가 더 이상 없다는 것을 나타낸다. 폴딩된 프로세스는 구체적으로 후술되는 바와 같이 폴딩된 세트를 셧다운함으로써 응답한다.
GOT_BLLP : 이 코드는 제어 메시지(블립(blip))가 수신되었다는 것을 나타낸 다(예컨대, 작업 요소의 연속 흐름에서의 체크포인트 메시지). 폴딩된 프로세스에 액세스 가능한 글로벌 "블립" 변수는 제어 메시지를 포함한다. 폴딩된 프로세스는 제어 메시지를 처리함으로써 응답하며, 제어 메시지가 처리된 후 계산 함수를 다시 호출한다.
루트 성분이 REACHED_EOF를 리턴할 때, 폴딩된 프로세스는 폴딩된 세트를 셧다운한다. 이것은 폴딩된 세트 내의 성분의 각각에 연관된 셧다운 함수(shutdown function)를 상류측 성분에서 하류측 성분으로의 지형적으로 기억된 순서로 호출함으로써 행해진다.
셧다운 함수는 하류측으로 푸시되는 데이터를 생성할 수도 있다. 예컨대, 해쉬 롤업 성분(hash rollup component)에 대한 계산 함수는 다양한 어큐뮬레이터 내에 데이터를 쌓아올리고, 셧다운 함수가 호출될 때까지 출력 데이터를 생성하지 않는다.
루트 성분이 GOT_BLIP를 리턴할 때, 폴딩된 프로세스는 블립을 하류측으로 전파한다. 이것은 폴딩된 세트 내의 각각의 성분에 연관된 프로세스 블립 함수(process blip function)를 호출함으로써 행해진다. 셧다운 함수에 관하여서는, 프로세스 블립 함수는 추가의 계산을 트리거할 수도 있다. 예컨대, 연속적인 흐름 롤업 성분은 프로세스 블립 함수가 호출될 때까지 데이터를 하류측으로 푸시하지 않는다.
블립은 예컨대 "CONTINUOUS FLOW CHECKPOINTING DATA PROCESSING"을 발명의 명칭으로 하는 미국 특허 번호 6,584,581호에 개시된 바와 같이 성분으로 하여금 자신의 상태를 체크포인트하도록 지시하며, 상기 특허는 본 명세서에 발명의 일부로서 원용되어 있다. 그 경우, 프로세스 블립 함수는 비휘발성 기억부 내의 체크포인트 파일에 현재 상태 정보를 기억시킬 책임을 갖는다. 폴딩된 세트 내의 성분은 체크포인트 파일을 공유할 수 있다(예컨대, 효율을 이유로). 공유된 체크포인트 파일이 채용되면, 폴딩된 세트 내의 모든 성분은 체크포인트 블립이 폴딩된 세트의 외측의 임의의 성분에 전파되기 전에 자신의 체크포인트를 완료한다. 이것은 예컨대 상류측 성분으로부터 하류측 성분으로 지형적으로 기억된 순서로 성분의 프로세스 블립 함수를 호출하거나 또는 체크포인팅이 완료된 후 별도의 경로로 폴딩된 세트의 외측의 성분에 블립을 전파함으로써 달성될 수 있다.
실행 모듈은 계산 함수가 예컨대 데이터베이스 또는 웹 서버를 포함하는 외부 장치와의 대화를 수반하는 성분을 통합하도록 확장될 수 있다.
외부 장치와의 대화는 일반적으로 비교적 크거나 및/또는 제한되지 않은 양의 시간을 소요할 수 있어, 어플리케이션의 처리량을 제한하는 효과가 있다. 성분 당 하나의 프로세스 실행에서의 처리량을 향상시키기 위한 한 가지 방안은, 입력 레코드가 성분에 의해 수신될 때에 이용 가능한 접속에 대한 요청을 발행하는 장치에 대하여 접속의 세트(또는 스풀)을 개방하는 것이다. 성분은 장치로부터 응답이 비동기적으로 리턴될 때에 응답을 캡쳐하고, 적절한 때에 출력 레코드를 생성한다. 그러나, 이러한 성분에 대한 계산 함수가 한 번에 하나의 입력 레코드를 수신하고, 성분이 리턴하기 전에 그 입력 레코드에 대한 대응하는 출력 레코드를 생성하기 때문에, 이 방식은 폴딩된 실행의 일부 구현예와는 호환되지 않을 수도 있다.
폴딩된 실행에서의 풀링된 접속(pooled connection) 및 비동기적 결과 캡쳐를 이용하기 위해, 이러한 요청을 행하는 성분은 2개의 성분, 즉 입력 레코드 및 발행자 요청(issuer request)을 받아들이는 제1 성분 및 응답을 수신하고 출력 레코드를 구축하는 제2 성분으로 나누어지는 것이 효과적이다. 제2 성분은 단일 프로세스에 의해 실행되는 폴딩된 성분의 세트에 대한 추가의 "루트"로서 취급되며, 대응하는 외부 장치로부터의 응답이 제2 성분에 대한 입력으로서 취급된다. 폴딩된 세트를 실행하는 프로세스는 어떠한 소스로부터의 입력, 즉 원래의 루트 성분에의 입력 또는 외부 장치로부터의 응답을 수신하고, 적합한 루트 성분에 대한 계산 함수를 호출한다.
폴딩되지 않은 실행 또는 폴딩된 실행 중의 하나에서, 원격 장치에 연결하는 성분으로부터의 결과의 순서가 입력의 순서에 대응할 필요가 있으면, 그 결과는 하류측 성분에 넘겨지기 전에 누적되어 기록될 수도 있다.
3. 모니터링(Monitoring)
RMM(116)은 그래프의 실행에 대한 정보를 개발자(101) 및/또는 사용자(103)에게 제공한다. RMM(116)은 이들 성분이 실행 동안 함께 폴딩되는 경우에도 그래프의 개개의 성분의 런타임 특성에 대한 정보를 제공한다. 그러므로, 그래프의 성분에 연관된 계산의 특징이, 계산을 수행하는 프로세스의 수가 그래프 내의 성분의 수와 일치하게 될 필요없이, 그래프의 논리 구조에 따라 분석될 수 있다. 예컨대, RMM(116)은 성분 폴딩 방식을 이용하거나 또는 성분 당 하나의 프로세스 방식을 이용하여 실행된 그래프에 대해 대략 동일한 런타임 특성을 나타낼 수 있다.
하나의 성분만을 갖는 폴딩된 세트에 대해 및 성분 당 하나의 프로세스 방식에서, RMM(116)은 성분에 대응하는 프로세스에 기초하여 CPU 시간과 같은 특성을 추적하며, 성분 내로의 데이터 흐름 또는 성분 외부로의 데이터 흐름을 지원하는 데이터 통신 채널에 기초하여 처리된 데이터의 양을 추적한다.
하나 이상의 성분을 갖는 폴딩된 세트에 대하여, RMM(116)은 폴딩된 프로세스에 대한 CPU 시간 및 폴딩된 세트에 대해 처리된 데이터의 양을 추적하고, 이들 전부를 성분 단위(component-by-component basis)로 나눈다. 간편한 방식은 전체 양을 폴딩된 세트 내의 성분의 수로 나누는 것이다. 그러나, 다수의 경우에, 모니터링된 양의 더욱 정확한 나눔이 요구된다.
폴딩된 프로세스는, 추적 정보를, 대응하는 폴딩된 세트 내에 제공된 성분 및 데이터 흐름에 대응하는 방식으로, 기억된 변수에 기입한다. 예컨대, 성분 내로의(또는 성분 외부로의) 데이터 흐름에 대응하는 데이터 포인터 변수가 판독(또는 기입)될 때마다, 대응하는 레코드-카운트 및 바이트-카운트 추적 값이 증가된다.
RMM(116)은 인터럽트 방식을 이용하여 CPU 시간의 더욱 정확한 나눔을 달성할 수 있다. 타이머는 폴딩된 프로세스가 폴딩된 세트 내의 각종 성분에 연관된 함수를 호출하는 데 소요되는 시간의 비율을 샘플링하기 위해 인터럽트를 트리거한다. 각각의 함수가 호출될 때, 예컨대 함수는 대응하는 성분이 "활성상태(active)"라는 것을 글로벌 변수에 기입한다. 타이머가 경과할 때, 인터럽트가 트리거되고, 폴딩된 프로세스가 활성상태의 성분에 연관된 카운터를 증가시킨다. 폴딩된 세트 내의 각각의 성분에 대한 CPU 시간을 보고하기 위해, 폴딩된 세트에 대한 전체 시간은 이들 카운트에 따라 비례하여 분할된다.
CPU 시간의 정확한 나눔을 달성하기 위한 다른 방식은 각각의 폴딩된 성분의 계산 함수 및 프로세스 블립 함수의 호출을 시간에 맞추는 것이다. 타이밍에 맞는 모든 호출이 수용 가능하지 않은 오버헤드를 유발할 수 있으므로, 시스템은 호출의 단편(fraction)에 시간을 맞출 수 있다(예컨대, 최초 100번마다, 그리고나서 그후에는 1000번째마다). 그 후, 수집된 시간은 폴딩된 성분 중에 비례하여 프로세스에 대한 전체 CPU 시간을 분할하기 위해 사용된다.
전술한 성분 폴딩 방식은 컴퓨터 상에서 실행하기 위한 소프트웨어를 이용하여 구현될 수 있다. 예컨대, 소프트웨어는 하나 이상의 프로세서, 하나 이상의 데이터 기억 시스템(휘발성 및 비휘발성 메모리 및/또는 기억 요소를 포함), 하나 이상의 입력 장치 또는 포트, 및 하나 이상의 출력 장치 또는 포트를 각각 포함하는 하나 이상의 프로그래밍된 또는 프로그래밍 가능한 컴퓨터 시스템(분산형, 클라이언트/서버, 또는 그리드 등의 다양한 아키텍쳐로 이루어질 수 있는)을 실행하는 하나 이상의 컴퓨터 프로그램에서의 과정을 형성한다. 소프트웨어는 예컨대 계산 그래프의 설계 및 구성에 관련된 다른 서비스를 제공하는 더 큰 프로그램의 하나 이상의 모듈을 형성할 수도 있다. 그래프의 노드 및 요소는 컴퓨터 판독 가능 매체에 저장된 데이터 구조 또는 데이터 저장부에 기억된 데이터 모델을 따르는 다른 구성의 데이터로서 구현될 수 있다.
소프트웨어는 범용 또는 특수 용도의 프로그래밍 가능한 컴퓨터에 의해 판독 가능한 CD-ROM 등의 매체 상에 제공되거나 또는 그 소프트웨어가 실행되는 컴퓨터에 네트워크를 통해 전달(전파 신호로 인코딩됨)될 수도 있다. 함수의 전부는 특수 용도의 컴퓨터 상에서 수행되거나 또는 코프로세서 등의 특수 용도의 하드웨어를 이용하여 수행될 수도 있다. 소프트웨어는 소프트웨어에 의해 지정된 계산의 상이한 부분이 상이한 컴퓨터에 의해 수행되는 분산 방식으로 구현될 수도 있다. 각각의 이러한 컴퓨터 프로그램은 범용 또는 특수 용도의 프로그래밍 가능한 컴퓨터에 의해 판독 가능한 기억 매체 또는 장치(예컨대, 고체 상태 메모리, 고체 상태 매체, 자기 매체, 또는 광 매체)에 기억되거나 다운로드되어, 기억 매체 또는 기억 장치가 본 명세서에서 설명된 과정을 수행하기 위해 컴퓨터 시스템에 의해 판독될 때에 컴퓨터를 구성 및 작동시키는 것이 바람직하다. 본 발명의 시스템은 컴퓨터 프로그램과 함께 구성된 컴퓨터 판독 가능한 기억 매체로서 구현되도록 고려되어, 이와 같이 구성된 기억 매체가 컴퓨터 시스템으로 하여금 본 명세서에서 설명된 함수를 수행하기 위해 특정의 사전 결정된 방식으로 동작하도록 한다.
본 발명의 여러 실시예를 설명하였지만, 본 발명의 사상 및 요지를 벗어나지 않고 다양한 수정이 이루어질 수 있다. 예컨대, 전술한 단계의 일부는 독립적인 순서로 될 수 있으며, 그에 따라 설명된 것과는 상이한 순서로 수행될 수 있다. 전술한 설명은 본 발명의 범위를 예시하기 위한 것으로 본 발명을 제한하기 위한 것은 아니며, 본 발명의 범위는 첨부된 청구범위의 범위에 의해 정해진다. 이러한 실시예는 이하의 청구범위의 범위 내에 포함되는 것임은 자명하다.

Claims (119)

  1. 그래프 기반 계산(graph-based computation)을 실행하는 방법에 있어서,
    링크 요소(linking element)에 의해 데이터 처리 요소가 결합되는 계산 그래프의 사양(specification)을 받아들이는 단계;
    상기 데이터 처리 요소를, 적어도 제1 세트가 상기 데이터 처리 요소를 복수 개 포함하는 세트로 분할하는 단계;
    각각의 상기 세트에 상이한 계산 자원을 할당하는 단계; 및
    할당된 상기 계산 자원을 이용하여 상기 데이터 처리 요소에 대응하는 계산을 수행하는 단계를 포함하는, 상기 계산 그래프에 따라 데이터를 처리하는 단계
    를 포함하고,
    상기 데이터 처리 요소의 제1 세트에 할당된 상기 계산 자원 중 하나는, 하류측 데이터 처리 요소와 연관된 함수를 호출함으로써, 상류측 데이터 처리 요소의 출력으로부터의 데이터 흐름과 연관된 작업 요소를 상기 하류측 데이터 처리 요소의 입력으로 전달하며, 상기 상류측 데이터 처리 요소와 상기 하류측 데이터 처리 요소는 양자 모두 상기 데이터 처리 요소의 제1 세트 내에 있는, 그래프 기반 계산을 실행하는 방법.
  2. 제1항에 있어서,
    상기 세트에 할당된 하나 이상의 상기 계산 자원은 프로세스를 포함하는, 그래프 기반 계산을 실행하는 방법.
  3. 제1항에 있어서,
    각각의 상기 링크 요소는 상류측 데이터 처리 요소의 출력에서부터 하류측 데이터 처리 요소의 입력으로의 데이터 흐름과 연관되는, 그래프 기반 계산을 실행하는 방법.
  4. 제3항에 있어서,
    상기 데이터를 처리하는 단계는, 상기 세트의 하나 이상의 세트에 대하여, 상기 세트 내의 상기 데이터 처리 요소를 결합시키는 상기 링크 요소에 의해 정해지는 시퀀스에 따라 상기 세트 내의 상기 데이터 처리 요소에 대응하는 계산을 수행하는 단계를 포함하는, 그래프 기반 계산을 실행하는 방법.
  5. 삭제
  6. 제1항에 있어서,
    상기 함수는, 상기 작업 요소가 상기 상류측 데이터 처리 요소에 연관된 함수에 의해 기입된 기억 지점으로부터 상기 작업 요소를 읽어들이는, 그래프 기반 계산을 실행하는 방법.
  7. 제6항에 있어서,
    상기 상류측 데이터 처리 요소에 연관된 함수 및 상기 하류측 데이터 처리 요소에 연관된 함수는, 동일한 프로세스에 의해 호출되는, 그래프 기반 계산을 실행하는 방법.
  8. 제1항에 있어서,
    상기 데이터를 처리하는 단계는, 각각의 세트 내의 개개의 상기 데이터 처리 요소에 연관된 각각의 활동의 정도(quantity of activity)의 특성을 기술하는 정보를 유지하는 단계를 더 포함하는, 그래프 기반 계산을 실행하는 방법.
  9. 제8항에 있어서,
    각각의 상기 활동의 정도는 각각의 상기 데이터 처리 요소에 따라 처리된 데이터의 양을 포함하는, 그래프 기반 계산을 실행하는 방법.
  10. 제8항에 있어서,
    각각의 상기 활동의 정도는 각각의 상기 데이터 처리 요소에 대응하는 계산을 수행하는 상기 세트에 할당된 계산 자원에 의해 소비된 시간의 양을 포함하는, 그래프 기반 계산을 실행하는 방법.
  11. 제1항에 있어서,
    상기 세트 내의 상기 데이터 처리 요소는 상기 계산 그래프의 연결된 방향성 서브그래프(connected directed subgraph)를 형성하는, 그래프 기반 계산을 실행하는 방법.
  12. 제11항에 있어서,
    상기 서브그래프는 트리(tree)를 포함하는, 그래프 기반 계산을 실행하는 방법.
  13. 제11항에 있어서,
    복수의 입력을 갖는 상기 세트 내의 각각의 상기 데이터 처리 요소에 대하여, 그 데이터 처리 요소의 입력에 링크된 상류측 데이터 처리 요소의 전부가 또한 그 세트 내에 있는, 그래프 기반 계산을 실행하는 방법.
  14. 제11항에 있어서,
    서브그래프에 상류측 요소를 갖지 않는 서브그래프 내의 상기 데이터 처리 요소에 대한 제어 메시지의 수신에 응답하여, 상기 제어 메시지를 상기 서브그래프의 외측에 전파하기 전에, 상기 서브그래프 내의 각각의 상기 데이터 처리 요소에 대한 상태 정보를 비휘발성 기억부에 저장하기 위해, 상기 서브그래프 내의 다른 데이터 처리 요소의 각각에 연관된 함수를 호출하는 단계를 더 포함하는, 그래프 기반 계산을 실행하는 방법.
  15. 제14항에 있어서,
    상기 서브그래프 내의 각각의 상기 데이터 처리 요소에 대한 상태 정보는 하나의 파일에 저장되는, 그래프 기반 계산을 실행하는 방법.
  16. 제1항에 있어서,
    상기 데이터 처리 요소는 미리결정된 정도의 병렬 계산(parallelism)을 갖는, 그래프 기반 계산을 실행하는 방법.
  17. 제16항에 있어서,
    상기 세트 내의 각각의 상기 데이터 처리 요소는 동일한 정도의 병렬 계산을 갖는, 그래프 기반 계산을 실행하는 방법.
  18. 제1항에 있어서,
    상기 계산 그래프의 상기 사양은 각각의 상기 데이터 처리 요소에 연관된 실행 단계(phase of execution)를 나타내는, 그래프 기반 계산을 실행하는 방법.
  19. 제18항에 있어서,
    상기 세트 내의 각각의 상기 데이터 처리 요소는 동일한 실행 단계에 연관되는, 그래프 기반 계산을 실행하는 방법.
  20. 삭제
  21. 삭제
  22. 삭제
  23. 그래프 기반 계산을 실행하는 시스템에 있어서,
    링크 요소에 의해 데이터 처리 요소가 결합되는 계산 그래프의 사양을 받아들이고, 또한 상기 데이터 처리 요소를, 적어도 제1 세트가 상기 데이터 처리 요소를 복수 개 포함하는 세트로 분할하기 위한 회로를 포함하는 사전 실행(pre-execution) 모듈; 및
    각각의 상기 세트에 상이한 계산 자원을 할당하고, 또한 할당된 상기 계산 자원을 이용하여 상기 데이터 처리 요소에 대응하는 계산을 수행하는 것을 포함한, 상기 계산 그래프에 따라 데이터를 처리하기 위한 회로를 포함하는 실행 모듈
    을 포함하고,
    상기 데이터 처리 요소의 제1 세트에 할당된 상기 계산 자원 중 하나는, 하류측 데이터 처리 요소와 연관된 함수를 호출함으로써, 상류측 데이터 처리 요소의 출력으로부터의 데이터 흐름과 연관된 작업 요소를 상기 하류측 데이터 처리 요소의 입력으로 전달하며, 상기 상류측 데이터 처리 요소와 상기 하류측 데이터 처리 요소는 양자 모두 상기 데이터 처리 요소의 제1 세트 내에 있는, 그래프 기반 계산을 실행하는 시스템.
  24. 제23항에 있어서,
    상기 세트에 할당된 하나 이상의 상기 계산 자원은 프로세스를 포함하는, 그래프 기반 계산을 실행하는 시스템.
  25. 제23항에 있어서,
    각각의 세트 내의 개개의 상기 데이터 처리 요소에 연관된 각각의 활동의 정도의 특성을 기술하는 정보를 유지하기 위한 회로를 포함하는 런타임 모니터링 모듈을 더 포함하는, 그래프 기반 계산을 실행하는 시스템.
  26. 그래프 기반 계산을 실행하는 시스템에 있어서,
    링크 요소에 의해 데이터 처리 요소가 결합되는 계산 그래프의 사양을 받아들이기 위한 수단;
    상기 데이터 처리 요소를, 적어도 제1 세트가 상기 데이터 처리 요소를 복수 개 포함하는 세트로 분할하는 수단;
    각각의 상기 세트에 상이한 계산 자원을 할당하는 수단; 및
    할당된 상기 계산 자원을 이용하여 상기 데이터 처리 요소에 대응하는 계산을 수행하는 것을 포함한, 상기 계산 그래프에 따라 데이터를 처리하는 수단
    을 포함하고,
    상기 데이터 처리 요소의 제1 세트에 할당된 상기 계산 자원 중 하나는, 하류측 데이터 처리 요소와 연관된 함수를 호출함으로써, 상류측 데이터 처리 요소의 출력으로부터의 데이터 흐름과 연관된 작업 요소를 상기 하류측 데이터 처리 요소의 입력으로 전달하며, 상기 상류측 데이터 처리 요소와 상기 하류측 데이터 처리 요소는 양자 모두 상기 데이터 처리 요소의 제1 세트 내에 있는, 그래프 기반 계산을 실행하는 시스템.
  27. 제26항에 있어서,
    상기 세트에 할당된 하나 이상의 상기 계산 자원은 프로세스를 포함하는, 그래프 기반 계산을 실행하는 시스템.
  28. 제26항에 있어서,
    각각의 세트 내의 개개의 상기 데이터 처리 요소에 연관된 각각의 활동의 정도의 특성을 기술하는 정보를 유지하는 수단을 더 포함하는, 그래프 기반 계산을 실행하는 시스템.
  29. 제23항에 있어서,
    각각의 상기 링크 요소는 상류측 데이터 처리 요소의 출력에서부터 하류측 데이터 처리 요소의 입력으로의 데이터 흐름과 연관되는, 그래프 기반 계산을 실행하는 시스템.
  30. 제29항에 있어서,
    상기 데이터를 처리하는 것은, 상기 세트의 하나 이상의 세트에 대하여, 상기 세트 내의 상기 데이터 처리 요소를 결합시키는 상기 링크 요소에 의해 정해지는 시퀀스에 따라 상기 세트 내의 상기 데이터 처리 요소에 대응하는 계산을 수행하는 것을 포함하는, 그래프 기반 계산을 실행하는 시스템.
  31. 제30항에 있어서,
    상기 함수는, 상기 작업 요소가 상기 상류측 데이터 처리 요소에 연관된 함수에 의해 기입된 기억 지점으로부터 상기 작업 요소를 읽어들이는, 그래프 기반 계산을 실행하는 시스템.
  32. 제31항에 있어서,
    상기 상류측 데이터 처리 요소에 연관된 함수 및 상기 하류측 데이터 처리 요소에 연관된 함수는, 동일한 프로세스에 의해 호출되는, 그래프 기반 계산을 실행하는 시스템.
  33. 제25항에 있어서,
    각각의 상기 활동의 정도는 각각의 상기 데이터 처리 요소에 따라 처리된 데이터의 양을 포함하는, 그래프 기반 계산을 실행하는 시스템.
  34. 제25항에 있어서,
    각각의 상기 활동의 정도는 각각의 상기 데이터 처리 요소에 대응하는 계산을 수행하는 세트에 할당된 계산 자원에 의해 소비된 시간의 양을 포함하는, 그래프 기반 계산을 실행하는 시스템.
  35. 제23항에 있어서,
    세트 내의 상기 데이터 처리 요소는 상기 계산 그래프의 연결된 방향성 서브그래프를 형성하는, 그래프 기반 계산을 실행하는 시스템.
  36. 제35항에 있어서,
    상기 서브그래프는 트리를 포함하는, 그래프 기반 계산을 실행하는 시스템.
  37. 제35항에 있어서,
    복수의 입력을 갖는 세트 내의 각각의 상기 데이터 처리 요소에 대하여, 그 데이터 처리 요소의 입력에 링크된 상류측 데이터 처리 요소의 전부가 또한 그 세트 내에 있는, 그래프 기반 계산을 실행하는 시스템.
  38. 제35항에 있어서,
    상기 데이터를 처리하는 것은, 서브그래프에 상류측 요소를 갖지 않는 서브그래프 내의 데이터 처리 요소에 대한 제어 메시지의 수신에 응답하여, 상기 제어 메시지를 상기 서브그래프의 외측에 전파하기 전에, 상기 서브그래프 내의 각각의 상기 데이터 처리 요소에 대한 상태 정보를 비휘발성 기억부에 저장하기 위해, 상기 서브그래프 내의 다른 데이터 처리 요소의 각각에 연관된 함수를 호출하는 것을 포함하는, 그래프 기반 계산을 실행하는 시스템.
  39. 제38항에 있어서,
    상기 서브그래프 내의 각각의 상기 데이터 처리 요소에 대한 상태 정보는 하나의 파일에 저장되는, 그래프 기반 계산을 실행하는 시스템.
  40. 제23항에 있어서,
    상기 데이터 처리 요소는 미리결정된 정도의 병렬 계산을 갖는, 그래프 기반 계산을 실행하는 시스템.
  41. 제40항에 있어서,
    세트 내의 각각의 상기 데이터 처리 요소는 동일한 정도의 병렬 계산을 갖는, 그래프 기반 계산을 실행하는 시스템.
  42. 제23항에 있어서,
    상기 계산 그래프의 상기 사양은 각각의 상기 데이터 처리 요소에 연관된 실행 단계를 나타내는, 그래프 기반 계산을 실행하는 시스템.
  43. 제42항에 있어서,
    세트 내의 각각의 상기 데이터 처리 요소는 동일한 실행 단계에 연관되는, 그래프 기반 계산을 실행하는 시스템.
  44. 제26항에 있어서,
    각각의 상기 링크 요소는 상류측 데이터 처리 요소의 출력에서부터 하류측 데이터 처리 요소의 입력으로의 데이터 흐름과 연관되는, 그래프 기반 계산을 실행하는 시스템.
  45. 제44항에 있어서,
    상기 데이터를 처리하는 수단은, 상기 세트의 하나 이상의 세트에 대하여, 상기 세트 내의 상기 데이터 처리 요소를 결합시키는 상기 링크 요소에 의해 정해지는 시퀀스에 따라 상기 세트 내의 상기 데이터 처리 요소에 대응하는 계산을 수행하기 위한 수단을 포함하는, 그래프 기반 계산을 실행하는 시스템.
  46. 제45항에 있어서,
    상기 함수는, 상기 작업 요소가 상기 상류측 데이터 처리 요소에 연관된 함수에 의해 기입된 기억 지점으로부터 상기 작업 요소를 읽어들이는, 그래프 기반 계산을 실행하는 시스템.
  47. 제46항에 있어서,
    상기 상류측 데이터 처리 요소에 연관된 함수 및 상기 하류측 데이터 처리 요소에 연관된 함수는, 동일한 프로세스에 의해 호출되는, 그래프 기반 계산을 실행하는 시스템.
  48. 제28항에 있어서,
    각각의 상기 활동의 정도는 각각의 상기 데이터 처리 요소에 따라 처리된 데이터의 양을 포함하는, 그래프 기반 계산을 실행하는 시스템.
  49. 제28항에 있어서,
    각각의 상기 활동의 정도는 각각의 상기 데이터 처리 요소에 대응하는 계산을 수행하는 세트에 할당된 계산 자원에 의해 소비된 시간의 양을 포함하는, 그래프 기반 계산을 실행하는 시스템.
  50. 제26항에 있어서,
    세트 내의 상기 데이터 처리 요소는 상기 계산 그래프의 연결된 방향성 서브그래프를 형성하는, 그래프 기반 계산을 실행하는 시스템.
  51. 제50항에 있어서,
    상기 서브그래프는 트리를 포함하는, 그래프 기반 계산을 실행하는 시스템.
  52. 제50항에 있어서,
    복수의 입력을 갖는 세트 내의 각각의 상기 데이터 처리 요소에 대하여, 그 데이터 처리 요소의 입력에 링크된 상류측 데이터 처리 요소의 전부가 또한 그 세트 내에 있는, 그래프 기반 계산을 실행하는 시스템.
  53. 제50항에 있어서,
    상기 데이터를 처리하는 수단은, 서브그래프에 상류측 요소를 갖지 않는 서브그래프 내의 데이터 처리 요소에 대한 제어 메시지의 수신에 응답하여, 상기 제어 메시지를 상기 서브그래프의 외측에 전파하기 전에, 상기 서브그래프 내의 각각의 상기 데이터 처리 요소에 대한 상태 정보를 비휘발성 기억부에 저장하기 위해, 상기 서브그래프 내의 다른 데이터 처리 요소의 각각에 연관된 함수를 호출하기 위한 수단을 더 포함하는, 그래프 기반 계산을 실행하는 시스템.
  54. 제53항에 있어서,
    상기 서브그래프 내의 각각의 상기 데이터 처리 요소에 대한 상태 정보는 하나의 파일에 저장되는, 그래프 기반 계산을 실행하는 시스템.
  55. 제26항에 있어서,
    상기 데이터 처리 요소는 미리결정된 정도의 병렬 계산을 갖는, 그래프 기반 계산을 실행하는 시스템.
  56. 제55항에 있어서,
    세트 내의 각각의 상기 데이터 처리 요소는 동일한 정도의 병렬 계산을 갖는, 그래프 기반 계산을 실행하는 시스템.
  57. 제26항에 있어서,
    상기 계산 그래프의 상기 사양은 각각의 상기 데이터 처리 요소에 연관된 실행의 단계를 나타내는, 그래프 기반 계산을 실행하는 시스템.
  58. 제57항에 있어서,
    세트 내의 각각의 상기 데이터 처리 요소는 동일한 실행 단계에 연관되는, 그래프 기반 계산을 실행하는 시스템.
  59. 제1항에 있어서,
    상기 계산 자원 중 하나는, 하류측 데이터 처리 요소와 연관된 함수를 호출함으로써, 제2의 상류측 데이터 처리 요소의 출력으로부터의 데이터 흐름과 연관된 작업 요소를 상기 하류측 데이터 처리 요소의 입력으로 전달하는, 그래프 기반 계산을 실행하는 방법.
  60. 제59항에 있어서,
    상기 계산 자원 중 하나는, 제1의 상류측 데이터 처리 요소의 출력으로부터의 데이터 흐름과 연관된 작업 요소와 제2의 상류측 데이터 처리 요소의 출력으로부터의 데이터 흐름과 연관된 작업 요소를 동시에 전달하는, 그래프 기반 계산을 실행하는 방법.
  61. 제1항에 있어서,
    상기 하류측 데이터 처리 요소의 입력으로 전달되는 작업 요소는, 전달될 전체 수의 작업 요소 중 선택된 서브세트인, 그래프 기반 계산을 실행하는 방법.
  62. 제61항에 있어서,
    상기 선택된 서브세트 내에 있지 않은 작업 요소는 제2의 하류측 데이터 처리 요소로 전달되는, 그래프 기반 계산을 실행하는 방법.
  63. 제1항에 있어서,
    데이터 처리 요소의 세트 내에 있는 각각의 데이터 처리 요소는 데이터 처리 요소의 단지 하나의 세트 내에 있는, 그래프 기반 계산을 실행하는 방법.
  64. 제1항에 있어서,
    상기 하류측 데이터 처리 요소와 연관된 함수는 상기 하류측 데이터 처리 요소와 연관된 계산을 수행하는 계산 함수(compute function)인, 그래프 기반 계산을 실행하는 방법.
  65. 제64항에 있어서,
    상기 계산은, 상기 데이터 처리 요소와 연관된 상태 변수를 갱신하는 것, 기억된 작업 요소를 변환하는 것, 새로운 작업 요소를 생성하는 것, 또는 데이터를 보다 하류측의 데이터 처리 요소로 통신하는 것 중 적어도 하나를 포함하는, 그래프 기반 계산을 실행하는 방법.
  66. 제1항에 있어서,
    데이터 처리 요소의 각각의 세트 내에서 각각의 데이터 처리 요소와 연관된 활동의 정도를 추적하는 단계를 더 포함하는, 그래프 기반 계산을 실행하는 방법.
  67. 제23항에 있어서,
    상기 계산 자원 중 하나는, 하류측 데이터 처리 요소와 연관된 함수를 호출함으로써, 제2의 상류측 데이터 처리 요소의 출력으로부터의 데이터 흐름과 연관된 작업 요소를 상기 하류측 데이터 처리 요소의 입력으로 전달하는, 그래프 기반 계산을 실행하는 시스템.
  68. 제67항에 있어서,
    상기 계산 자원 중 하나는, 제1의 상류측 데이터 처리 요소의 출력으로부터의 데이터 흐름과 연관된 작업 요소와 제2의 상류측 데이터 처리 요소의 출력으로부터의 데이터 흐름과 연관된 작업 요소를 동시에 전달하는, 그래프 기반 계산을 실행하는 시스템.
  69. 제23항에 있어서,
    상기 하류측 데이터 처리 요소의 입력으로 전달되는 작업 요소는, 전달될 전체 수의 작업 요소 중 선택된 서브세트인, 그래프 기반 계산을 실행하는 시스템.
  70. 제69항에 있어서,
    상기 선택된 서브세트 내에 있지 않은 작업 요소는 제2의 하류측 데이터 처리 요소로 전달되는, 그래프 기반 계산을 실행하는 시스템.
  71. 제23항에 있어서,
    데이터 처리 요소의 세트 내에 있는 각각의 데이터 처리 요소는 데이터 처리 요소의 단지 하나의 세트 내에 있는, 그래프 기반 계산을 실행하는 시스템.
  72. 제23항에 있어서,
    상기 하류측 데이터 처리 요소와 연관된 함수는 상기 하류측 데이터 처리 요소와 연관된 계산을 수행하는 계산 함수인, 그래프 기반 계산을 실행하는 시스템.
  73. 제72항에 있어서,
    상기 계산은, 상기 데이터 처리 요소와 연관된 상태 변수를 갱신하는 것, 기억된 작업 요소를 변환하는 것, 새로운 작업 요소를 생성하는 것, 또는 데이터를 보다 하류측의 데이터 처리 요소로 통신하는 것 중 적어도 하나를 포함하는, 그래프 기반 계산을 실행하는 시스템.
  74. 제23항에 있어서,
    데이터 처리 요소의 각각의 세트 내에서 각각의 데이터 처리 요소와 연관된 활동의 정도를 추적하는 것을 더 포함하는, 그래프 기반 계산을 실행하는 시스템.
  75. 제26항에 있어서,
    상기 계산 자원 중 하나는, 하류측 데이터 처리 요소와 연관된 함수를 호출함으로써, 제2의 상류측 데이터 처리 요소의 출력으로부터의 데이터 흐름과 연관된 작업 요소를 상기 하류측 데이터 처리 요소의 입력으로 전달하는, 그래프 기반 계산을 실행하는 시스템.
  76. 제75항에 있어서,
    상기 계산 자원 중 하나는, 제1의 상류측 데이터 처리 요소의 출력으로부터의 데이터 흐름과 연관된 작업 요소와 제2의 상류측 데이터 처리 요소의 출력으로부터의 데이터 흐름과 연관된 작업 요소를 동시에 전달하는, 그래프 기반 계산을 실행하는 시스템.
  77. 제26항에 있어서,
    상기 하류측 데이터 처리 요소의 입력으로 전달되는 작업 요소는, 전달될 전체 수의 작업 요소 중 선택된 서브세트인, 그래프 기반 계산을 실행하는 시스템.
  78. 제77항에 있어서,
    상기 선택된 서브세트 내에 있지 않은 작업 요소는 제2의 하류측 데이터 처리 요소로 전달되는, 그래프 기반 계산을 실행하는 시스템.
  79. 제26항에 있어서,
    데이터 처리 요소의 세트 내에 있는 각각의 데이터 처리 요소는 데이터 처리 요소의 단지 하나의 세트 내에 있는, 그래프 기반 계산을 실행하는 시스템.
  80. 제26항에 있어서,
    상기 하류측 데이터 처리 요소와 연관된 함수는 상기 하류측 데이터 처리 요소와 연관된 계산을 수행하는 계산 함수인, 그래프 기반 계산을 실행하는 시스템.
  81. 제80항에 있어서,
    상기 계산은, 상기 데이터 처리 요소와 연관된 상태 변수를 갱신하는 것, 기억된 작업 요소를 변환하는 것, 새로운 작업 요소를 생성하는 것, 또는 데이터를 보다 하류측의 데이터 처리 요소로 통신하는 것 중 적어도 하나를 포함하는, 그래프 기반 계산을 실행하는 시스템.
  82. 제26항에 있어서,
    데이터 처리 요소의 각각의 세트 내에서 각각의 데이터 처리 요소와 연관된 활동의 정도를 추적하는 것을 더 포함하는, 그래프 기반 계산을 실행하는 시스템.
  83. 데이터 처리 요소에 할당되어 계산을 수행하는데 이용될 수 있는 계산 자원을 제공하는 컴퓨터 시스템을 이용하여 그래프 기반 계산을 실행하는 방법에 있어서,
    링크 요소에 의해 데이터 처리 요소가 결합되는 계산 그래프의 사양을 받아들이는 단계로서, 각각의 상기 링크 요소는 상류측 데이터 처리 요소의 출력으로부터 하류측 데이터 처리 요소의 입력으로의 데이터 흐름과 연관되는, 계산 그래프의 사양을 받아들이는 단계;
    각각의 데이터 처리 요소가 폴딩 가능(foldable)한지 또는 폴딩 불가능(non-foldable)한지를 결정하는 단계로서, 모든 폴딩 가능한 데이터 처리 요소는 폴딩 가능한 데이터 처리 요소의 대응하는 계산을 호출하기 위해 사용되는 컴퓨터 인터페이스를 포함하며, 모든 폴딩 불가능한 데이터 처리 요소는 폴딩 불가능한 데이터 처리 요소의 대응하는 계산을 호출하기 위해 사용되는 컴퓨터 인터페이스를 포함하지 않는, 결정 단계;
    상기 폴딩 가능한 데이터 처리 요소를 데이터 처리 요소의 하나 이상의 세트로 분할하는 단계로서, 데이터 처리 요소의 세트 중 적어도 하나가 복수의 상기 폴딩 가능한 데이터 처리 요소를 포함하는, 분할 단계;
    상기 컴퓨터 시스템의 상이한 계산 자원을 데이터 처리 요소의 각각의 세트에 할당하는 단계; 및
    할당된 상기 계산 자원을 이용하여 상기 데이터 처리 요소에 대응하는 계산을 수행하는 단계를 포함하는, 상기 계산 그래프에 따라 데이터를 처리하는 단계
    를 포함하고,
    상기 데이터 처리 요소의 세트 중 하나에 할당되는 상기 계산 자원 중 하나는, 폴딩 가능한 하류측 데이터 처리 요소와 연관된 함수를 호출함으로써, 제1의 폴딩 가능한 상류측 데이터 처리 요소의 출력으로부터의 데이터 흐름과 연관된 작업 요소를 폴딩 가능한 하류측 데이터 처리 요소의 입력으로 전달하며, 상기 제1의 폴딩 가능한 상류측 데이터 처리 요소와 상기 폴딩 가능한 하류측 데이터 처리 요소는 데이터 처리 요소의 동일한 세트 내에 있는, 그래프 기반 계산을 실행하는 방법.
  84. 제83항에 있어서,
    적어도 하나의 데이터 처리 요소가 폴딩 가능하고 적어도 하나의 데이터 처리 요소는 폴딩 불가능하다고 결정하는 단계를 더 포함하는, 그래프 기반 계산을 실행하는 방법.
  85. 제83항에 있어서,
    데이터 처리 요소의 세트에 할당되는 상기 계산 자원 중 적어도 하나는 프로세스를 포함하는, 그래프 기반 계산을 실행하는 방법.
  86. 제83항에 있어서,
    데이터 처리 요소의 각각의 세트 내에서 각각의 데이터 처리 요소와 연관된 각각의 활동의 정도의 특성을 기술하는 정보를 유지하는 단계를 더 포함하는, 그래프 기반 계산을 실행하는 방법.
  87. 제83항에 있어서,
    상기 데이터를 처리하는 단계는, 상기 데이터 처리 요소의 세트 중 적어도 하나에 대하여, 상기 데이터 처리 요소의 세트 내의 상기 데이터 처리 요소를 결합시키는 상기 링크 요소에 의해 정해지는 시퀀스에 따라 상기 데이터 처리 요소의 세트 내의 상기 데이터 처리 요소에 대응하는 계산을 수행하는 단계를 포함하는, 그래프 기반 계산을 실행하는 방법.
  88. 제83항에 있어서,
    상기 하류측 데이터 처리 요소와 연관된 함수는, 상기 작업 요소가 상기 상류측 데이터 처리 요소에 연관된 함수에 의해 기입된 기억 지점으로부터 상기 작업 요소를 읽어들이는, 그래프 기반 계산을 실행하는 방법.
  89. 제88항에 있어서,
    상기 상류측 데이터 처리 요소에 연관된 함수를 호출하는 프로세스는 상기 하류측 데이터 처리 요소와 연관된 함수를 호출하는 프로세스인, 그래프 기반 계산을 실행하는 방법.
  90. 제83항에 있어서,
    복수의 입력을 갖는 데이터 처리 요소의 세트 내의 임의의 데이터 처리 요소에 대하여, 그 데이터 처리 요소의 입력에 링크된 상류측 데이터 처리 요소의 전부가 또한 그 데이터 처리 요소의 세트 내에 있는, 그래프 기반 계산을 실행하는 방법.
  91. 제83항에 있어서,
    각각의 상기 데이터 처리 요소는 미리결정된 정도의 병렬 계산을 갖는, 그래프 기반 계산을 실행하는 방법.
  92. 제91항에 있어서,
    데이터 처리 요소의 세트 내의 상기 데이터 처리 요소 모두는 동일한 정도의 병렬 계산을 갖는, 그래프 기반 계산을 실행하는 방법.
  93. 제83항에 있어서,
    상기 계산 그래프의 사양은 각각의 상기 데이터 처리 요소에 연관된 실행 단계를 나타내는, 그래프 기반 계산을 실행하는 방법.
  94. 제93항에 있어서,
    데이터 처리 요소의 세트 내의 각각의 상기 데이터 처리 요소는 동일한 실행 단계에 연관되는, 그래프 기반 계산을 실행하는 방법.
  95. 그래프 기반 계산을 실행하기 위한 컴퓨터 프로그램을 저장한 컴퓨터 판독가능 매체로서,
    상기 컴퓨터 프로그램은 컴퓨터 시스템으로 하여금, 제1항 내지 제4항, 제6항 내지 제19항, 제59항 내지 제66항, 및 제83항 내지 제94항 중 어느 한 항의 방법을 수행하도록 하기 위한 명령을 포함하는, 그래프 기반 계산을 실행하기 위한 컴퓨터 프로그램을 저장한 컴퓨터 판독가능 매체.
  96. 그래프 기반 계산을 실행하는 시스템에 있어서,
    사전 실행 모듈; 및
    실행 모듈
    을 포함하고,
    상기 사전 실행 모듈은:
    링크 요소에 의해 데이터 처리 요소가 결합되는 계산 그래프의 사양을 받아들이는 동작으로서, 각각의 상기 링크 요소는 상류측 데이터 처리 요소의 출력으로부터 하류측 데이터 처리 요소의 입력으로의 데이터 흐름과 연관되는, 계산 그래프의 사양을 받아들이는 동작;
    각각의 데이터 처리 요소가 폴딩 가능한지 또는 폴딩 불가능한지를 결정하는 동작으로서, 모든 폴딩 가능한 데이터 처리 요소는 폴딩 가능한 데이터 처리 요소의 대응하는 계산을 호출하기 위해 사용되는 컴퓨터 인터페이스를 포함하며, 모든 폴딩 불가능한 데이터 처리 요소는 폴딩 불가능한 데이터 처리 요소의 대응하는 계산을 호출하기 위해 사용되는 컴퓨터 인터페이스를 포함하지 않는, 결정 동작; 및
    상기 폴딩 가능한 데이터 처리 요소를 데이터 처리 요소의 하나 이상의 세트로 분할하는 동작으로서, 데이터 처리 요소의 세트 중 적어도 하나가 복수의 상기 폴딩 가능한 데이터 처리 요소를 포함하는, 분할 동작
    을 수행하기 위한 회로를 포함하고,
    상기 실행 모듈은:
    상기 컴퓨터 시스템의 상이한 계산 자원을 데이터 처리 요소의 각각의 세트에 할당하는 동작; 및
    할당된 상기 계산 자원을 이용하여 상기 데이터 처리 요소에 대응하는 계산을 수행하는 동작을 포함하는, 상기 계산 그래프에 따라 데이터를 처리하는 동작
    을 수행하기 위한 회로
    를 포함하고,
    상기 데이터 처리 요소의 세트 중 하나에 할당되는 상기 계산 자원 중 하나는, 폴딩 가능한 하류측 데이터 처리 요소와 연관된 함수를 호출함으로써, 제1의 폴딩 가능한 상류측 데이터 처리 요소의 출력으로부터의 데이터 흐름과 연관된 작업 요소를 폴딩 가능한 하류측 데이터 처리 요소의 입력으로 전달하며, 상기 제1의 폴딩 가능한 상류측 데이터 처리 요소와 상기 폴딩 가능한 하류측 데이터 처리 요소는 데이터 처리 요소의 동일한 세트 내에 있는, 그래프 기반 계산을 실행하는 시스템.
  97. 제96항에 있어서,
    적어도 하나의 데이터 처리 요소가 폴딩 가능하고 적어도 하나의 데이터 처리 요소는 폴딩 불가능한, 그래프 기반 계산을 실행하는 시스템.
  98. 제96항에 있어서,
    데이터 처리 요소의 세트에 할당되는 상기 계산 자원 중 적어도 하나는 프로세스를 포함하는, 그래프 기반 계산을 실행하는 시스템.
  99. 제96항에 있어서,
    상기 데이터를 처리하는 것은, 데이터 처리 요소의 각각의 세트 내에서 각각의 데이터 처리 요소와 연관된 각각의 활동의 정도의 특성을 기술하는 정보를 유지하는 것을 포함하는, 그래프 기반 계산을 실행하는 시스템.
  100. 제96항에 있어서,
    상기 데이터를 처리하는 것은, 상기 데이터 처리 요소의 세트 중 적어도 하나에 대하여, 상기 데이터 처리 요소의 세트 내의 상기 데이터 처리 요소를 결합시키는 상기 링크 요소에 의해 정해지는 시퀀스에 따라 상기 데이터 처리 요소의 세트 내의 상기 데이터 처리 요소에 대응하는 계산을 수행하는 것을 포함하는, 그래프 기반 계산을 실행하는 시스템.
  101. 제96항에 있어서,
    상기 하류측 데이터 처리 요소와 연관된 함수는, 상기 작업 요소가 상기 상류측 데이터 처리 요소에 연관된 함수에 의해 기입된 기억 지점으로부터 상기 작업 요소를 읽어들이는, 그래프 기반 계산을 실행하는 시스템.
  102. 제101항에 있어서,
    상기 상류측 데이터 처리 요소에 연관된 함수를 호출하는 프로세스는 상기 하류측 데이터 처리 요소와 연관된 함수를 호출하는 프로세스인, 그래프 기반 계산을 실행하는 시스템.
  103. 제96항에 있어서,
    복수의 입력을 갖는 데이터 처리 요소의 세트 내의 임의의 데이터 처리 요소에 대하여, 그 데이터 처리 요소의 입력에 링크된 상류측 데이터 처리 요소의 전부가 또한 그 데이터 처리 요소의 세트 내에 있는, 그래프 기반 계산을 실행하는 시스템.
  104. 제96항에 있어서,
    각각의 상기 데이터 처리 요소는 미리결정된 정도의 병렬 계산을 갖는, 그래프 기반 계산을 실행하는 시스템.
  105. 제104항에 있어서,
    데이터 처리 요소의 세트 내의 상기 데이터 처리 요소 모두는 동일한 정도의 병렬 계산을 갖는, 그래프 기반 계산을 실행하는 시스템.
  106. 제96항에 있어서,
    상기 계산 그래프의 사양은 각각의 상기 데이터 처리 요소에 연관된 실행 단계를 나타내는, 그래프 기반 계산을 실행하는 시스템.
  107. 제106항에 있어서,
    데이터 처리 요소의 세트 내의 각각의 상기 데이터 처리 요소는 동일한 실행 단계에 연관되는, 그래프 기반 계산을 실행하는 시스템.
  108. 그래프 기반 계산을 실행하는 시스템에 있어서,
    링크 요소에 의해 데이터 처리 요소가 결합되는 계산 그래프의 사양을 받아들이기 위한 수단으로서, 각각의 상기 링크 요소는 상류측 데이터 처리 요소의 출력으로부터 하류측 데이터 처리 요소의 입력으로의 데이터 흐름과 연관되는, 계산 그래프의 사양을 받아들이기 위한 수단;
    각각의 데이터 처리 요소가 폴딩 가능(foldable)한지 또는 폴딩 불가능(non-foldable)한지를 결정하기 위한 수단으로서, 모든 폴딩 가능한 데이터 처리 요소는 폴딩 가능한 데이터 처리 요소의 대응하는 계산을 호출하기 위해 사용되는 컴퓨터 인터페이스를 포함하며, 모든 폴딩 불가능한 데이터 처리 요소는 폴딩 불가능한 데이터 처리 요소의 대응하는 계산을 호출하기 위해 사용되는 컴퓨터 인터페이스를 포함하지 않는, 결정 수단;
    상기 폴딩 가능한 데이터 처리 요소를 데이터 처리 요소의 하나 이상의 세트로 분할하기 위한 수단으로서, 데이터 처리 요소의 세트 중 적어도 하나가 복수의 상기 폴딩 가능한 데이터 처리 요소를 포함하는, 분할 수단;
    상기 컴퓨터 시스템의 상이한 계산 자원을 데이터 처리 요소의 각각의 세트에 할당하기 위한 수단; 및
    할당된 상기 계산 자원을 이용하여 상기 데이터 처리 요소에 대응하는 계산을 수행하는 것을 포함하는, 상기 계산 그래프에 따라 데이터를 처리하기 위한 수단
    을 포함하고,
    상기 데이터 처리 요소의 세트 중 하나에 할당되는 상기 계산 자원 중 하나는, 폴딩 가능한 하류측 데이터 처리 요소와 연관된 함수를 호출함으로써, 제1의 폴딩 가능한 상류측 데이터 처리 요소의 출력으로부터의 데이터 흐름과 연관된 작업 요소를 폴딩 가능한 하류측 데이터 처리 요소의 입력으로 전달하며, 상기 제1의 폴딩 가능한 상류측 데이터 처리 요소와 상기 폴딩 가능한 하류측 데이터 처리 요소는 데이터 처리 요소의 동일한 세트 내에 있는, 그래프 기반 계산을 실행하는 시스템.
  109. 제108항에 있어서,
    적어도 하나의 데이터 처리 요소가 폴딩 가능하고 적어도 하나의 데이터 처리 요소는 폴딩 불가능한, 그래프 기반 계산을 실행하는 시스템.
  110. 제108항에 있어서,
    데이터 처리 요소의 세트에 할당되는 상기 계산 자원 중 적어도 하나는 프로세스를 포함하는, 그래프 기반 계산을 실행하는 시스템.
  111. 제108항에 있어서,
    상기 데이터를 처리하는 것은, 데이터 처리 요소의 각각의 세트 내에서 각각의 데이터 처리 요소와 연관된 각각의 활동의 정도의 특성을 기술하는 정보를 유지하는 것을 포함하는, 그래프 기반 계산을 실행하는 시스템.
  112. 제108항에 있어서,
    상기 데이터를 처리하는 것은, 상기 데이터 처리 요소의 세트 중 적어도 하나에 대하여, 상기 데이터 처리 요소의 세트 내의 상기 데이터 처리 요소를 결합시키는 상기 링크 요소에 의해 정해지는 시퀀스에 따라 상기 데이터 처리 요소의 세트 내의 상기 데이터 처리 요소에 대응하는 계산을 수행하는 것을 포함하는, 그래프 기반 계산을 실행하는 시스템.
  113. 제108항에 있어서,
    상기 하류측 데이터 처리 요소와 연관된 함수는, 상기 작업 요소가 상기 상류측 데이터 처리 요소에 연관된 함수에 의해 기입된 기억 지점으로부터 상기 작업 요소를 읽어들이는, 그래프 기반 계산을 실행하는 시스템.
  114. 제113항에 있어서,
    상기 상류측 데이터 처리 요소에 연관된 함수를 호출하는 프로세스는 상기 하류측 데이터 처리 요소와 연관된 함수를 호출하는 프로세스인, 그래프 기반 계산을 실행하는 시스템.
  115. 제108항에 있어서,
    복수의 입력을 갖는 데이터 처리 요소의 세트 내의 임의의 데이터 처리 요소에 대하여, 그 데이터 처리 요소의 입력에 링크된 상류측 데이터 처리 요소의 전부가 또한 그 데이터 처리 요소의 세트 내에 있는, 그래프 기반 계산을 실행하는 시스템.
  116. 제108항에 있어서,
    각각의 상기 데이터 처리 요소는 미리결정된 정도의 병렬 계산을 갖는, 그래프 기반 계산을 실행하는 시스템.
  117. 제116항에 있어서,
    데이터 처리 요소의 세트 내의 상기 데이터 처리 요소 모두는 동일한 정도의 병렬 계산을 갖는, 그래프 기반 계산을 실행하는 시스템.
  118. 제108항에 있어서,
    상기 계산 그래프의 사양은 각각의 상기 데이터 처리 요소에 연관된 실행 단계를 나타내는, 그래프 기반 계산을 실행하는 시스템.
  119. 제118항에 있어서,
    데이터 처리 요소의 세트 내의 각각의 상기 데이터 처리 요소는 동일한 실행 단계에 연관되는, 그래프 기반 계산을 실행하는 시스템.
KR1020087030136A 2006-05-16 2007-05-15 그래프 기반 계산에서의 계산 자원의 관리 Active KR101413049B1 (ko)

Applications Claiming Priority (3)

Application Number Priority Date Filing Date Title
US11/434,623 2006-05-16
US11/434,623 US7870556B2 (en) 2006-05-16 2006-05-16 Managing computing resources in graph-based computations
PCT/US2007/068946 WO2007137034A2 (en) 2006-05-16 2007-05-15 Managing computing resources in graph-based computations

Publications (2)

Publication Number Publication Date
KR20090018113A KR20090018113A (ko) 2009-02-19
KR101413049B1 true KR101413049B1 (ko) 2014-06-30

Family

ID=38713244

Family Applications (1)

Application Number Title Priority Date Filing Date
KR1020087030136A Active KR101413049B1 (ko) 2006-05-16 2007-05-15 그래프 기반 계산에서의 계산 자원의 관리

Country Status (8)

Country Link
US (1) US7870556B2 (ko)
EP (1) EP2021920B1 (ko)
JP (2) JP2009537908A (ko)
KR (1) KR101413049B1 (ko)
CN (2) CN103778015B (ko)
AU (1) AU2007253862C1 (ko)
CA (1) CA2650143C (ko)
WO (1) WO2007137034A2 (ko)

Families Citing this family (82)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US7877350B2 (en) * 2005-06-27 2011-01-25 Ab Initio Technology Llc Managing metadata for graph-based computations
CN101501678B (zh) * 2006-08-10 2013-10-16 起元科技有限公司 在基于图的计算中分配服务
US8904391B2 (en) * 2007-04-23 2014-12-02 International Business Machines Corporation Policy-based access control approach to staff activities of a business process
WO2009015342A1 (en) * 2007-07-26 2009-01-29 Ab Initio Technology Llc Transactional graph-based computation with error handling
WO2009039352A1 (en) * 2007-09-20 2009-03-26 Ab Initio Technology Llc Managing data flows in graph-based computations
US8069210B2 (en) * 2008-10-10 2011-11-29 Microsoft Corporation Graph based bot-user detection
CN102232212B (zh) * 2008-12-02 2015-11-25 起元技术有限责任公司 在数据管理系统中映射数据集的实例
CN105843684B (zh) 2009-02-13 2020-03-03 起元技术有限责任公司 管理任务执行
KR20150038757A (ko) * 2009-02-13 2015-04-08 아브 이니티오 테크놀로지 엘엘시 데이터 저장 시스템과의 통신
US8266289B2 (en) * 2009-04-23 2012-09-11 Microsoft Corporation Concurrent data processing in a distributed system
US8205113B2 (en) * 2009-07-14 2012-06-19 Ab Initio Technology Llc Fault tolerant batch processing
KR101656813B1 (ko) * 2009-09-16 2016-09-12 아브 이니티오 테크놀로지 엘엘시 데이터세트 요소의 매핑
US8667329B2 (en) * 2009-09-25 2014-03-04 Ab Initio Technology Llc Processing transactions in graph-based applications
US8549523B2 (en) 2009-11-23 2013-10-01 International Business Machines Corporation Performing runtime analysis and control of folding identified threads by assuming context of another thread and executing in lieu of another thread folding tool
US8832663B2 (en) 2009-11-23 2014-09-09 International Business Machines Corporation Thread serialization and disablement tool
CN107102848B (zh) * 2009-12-14 2020-11-24 起元技术有限责任公司 规定用户界面元素
US9665620B2 (en) 2010-01-15 2017-05-30 Ab Initio Technology Llc Managing data queries
US8555265B2 (en) 2010-05-04 2013-10-08 Google Inc. Parallel processing of data
CA2801573C (en) 2010-06-15 2018-08-14 Ab Initio Technology Llc Dynamically loading graph-based computations
US20110314075A1 (en) * 2010-06-18 2011-12-22 Nokia Corporation Method and apparatus for managing distributed computations within a computation space
EP2609507B1 (en) * 2010-08-25 2019-05-15 Ab Initio Technology LLC Evaluating dataflow graph characteristics
CN103180826B (zh) 2010-10-25 2017-04-05 起元技术有限责任公司 在代表计算机程序的数据流图中管理数据集对象
WO2012097278A1 (en) 2011-01-14 2012-07-19 Ab Initio Technology Llc Managing changes to collections of data
US9021299B2 (en) 2011-02-18 2015-04-28 Ab Initio Technology Llc Restarting processes
US9116759B2 (en) 2011-02-18 2015-08-25 Ab Initio Technology Llc Restarting data processing systems
US8782656B2 (en) * 2011-02-24 2014-07-15 International Business Machines Corporation Analysis of operator graph and dynamic reallocation of a resource to improve performance
US9116955B2 (en) 2011-05-02 2015-08-25 Ab Initio Technology Llc Managing data queries
US8606615B2 (en) * 2011-06-27 2013-12-10 Bank Of America Corporation System for managing and tracking an inventory of elements
US9503512B2 (en) 2012-03-21 2016-11-22 Intertrust Technologies Corporation Distributed computation systems and methods
JP6004818B2 (ja) * 2012-08-07 2016-10-12 インターナショナル・ビジネス・マシーンズ・コーポレーションＩｎｔｅｒｎａｔｉｏｎａｌ Ｂｕｓｉｎｅｓｓ Ｍａｃｈｉｎｅｓ Ｃｏｒｐｏｒａｔｉｏｎ 並列化方法、システム、及びプログラム
US10489360B2 (en) 2012-10-17 2019-11-26 Ab Initio Technology Llc Specifying and applying rules to data
US9507682B2 (en) * 2012-11-16 2016-11-29 Ab Initio Technology Llc Dynamic graph performance monitoring
US10108521B2 (en) 2012-11-16 2018-10-23 Ab Initio Technology Llc Dynamic component performance monitoring
US9274926B2 (en) 2013-01-03 2016-03-01 Ab Initio Technology Llc Configurable testing of computer programs
US9811233B2 (en) 2013-02-12 2017-11-07 Ab Initio Technology Llc Building applications for configuring processes
US11061539B2 (en) 2013-03-15 2021-07-13 The Mathworks, Inc. Reference nodes in a computational graph
AU2014257132B2 (en) 2013-04-23 2018-03-29 Ab Initio Technology Llc Controlling tasks performed by a computing system
CN106170762B (zh) 2013-12-05 2020-01-14 起元技术有限责任公司 管理包括子图的数据流图所用的接口
WO2015085291A1 (en) 2013-12-06 2015-06-11 Ab Initio Technology Llc Source code translation
CN104954823B (zh) * 2014-03-31 2018-06-15 华为技术有限公司 一种图计算预处理的装置、方法及系统
AU2015289442B2 (en) 2014-07-18 2019-07-11 Ab Initio Technology Llc Managing lineage information
US9330199B2 (en) 2014-07-21 2016-05-03 Facebook, Inc. Striping of directed graphs and nodes with improved functionality
EP3189420B1 (en) 2014-09-02 2023-08-23 AB Initio Technology LLC Managing execution state of components in a graph-based program specification for controlling their associated tasks
US9747112B2 (en) 2014-09-02 2017-08-29 Ab Initio Technology, Llc Managing invocation of tasks
US9785419B2 (en) * 2014-09-02 2017-10-10 Ab Initio Technology Llc Executing graph-based program specifications
WO2016036824A1 (en) * 2014-09-02 2016-03-10 Ab Initio Technology Llc Visually specifying subsets of components in graph-based programs through user interactions
US9830343B2 (en) * 2014-09-02 2017-11-28 Ab Initio Technology Llc Compiling graph-based program specifications
US9933918B2 (en) 2014-09-02 2018-04-03 Ab Initio Technology Llc Specifying control and data connections in graph-based programs
KR20170046777A (ko) * 2014-09-02 2017-05-02 아브 이니티오 테크놀로지 엘엘시 데이터 처리 태스크의 제어
US9760406B2 (en) 2014-09-02 2017-09-12 Ab Initio Technology Llc Controlling data processing tasks
US9626393B2 (en) 2014-09-10 2017-04-18 Ab Initio Technology Llc Conditional validation rules
JP6375201B2 (ja) * 2014-10-24 2018-08-15 株式会社野村総合研究所 データフローの自動並列化システム
US9880818B2 (en) * 2014-11-05 2018-01-30 Ab Initio Technology Llc Application testing
US10055333B2 (en) 2014-11-05 2018-08-21 Ab Initio Technology Llc Debugging a graph
US10437819B2 (en) 2014-11-14 2019-10-08 Ab Initio Technology Llc Processing queries containing a union-type operation
JP6413789B2 (ja) * 2015-01-22 2018-10-31 富士通株式会社 ジョブ管理プログラム、ジョブ管理方法及びジョブ管理装置
US10417281B2 (en) 2015-02-18 2019-09-17 Ab Initio Technology Llc Querying a data source on a network
WO2016154460A1 (en) * 2015-03-24 2016-09-29 Kyndi, Inc. Cognitive memory graph indexing, storage and retrieval
US20160342396A1 (en) * 2015-05-20 2016-11-24 Ab lnitio Technology LLC Visual program specification and compilation of graph-based computation
US10657134B2 (en) 2015-08-05 2020-05-19 Ab Initio Technology Llc Selecting queries for execution on a stream of real-time data
JP6598981B2 (ja) * 2015-08-11 2019-10-30 アビニシオ テクノロジー エルエルシー データ処理グラフのコンパイル
US10425273B2 (en) 2015-09-03 2019-09-24 Hitachi, Ltd. Data processing system and data processing method
KR102204887B1 (ko) * 2015-10-28 2021-01-19 구글 엘엘씨 연산 그래프 수정
US11151446B2 (en) * 2015-10-28 2021-10-19 Google Llc Stream-based accelerator processing of computational graphs
SG11201803929YA (en) 2015-12-21 2018-06-28 Ab Initio Technology Llc Sub-graph interface generation
JP6698177B2 (ja) * 2016-05-17 2020-05-27 アビニシオ テクノロジー エルエルシー 再構成可能な分散処理
CN110268422B (zh) * 2017-03-24 2023-12-01 谷歌有限责任公司 利用强化学习的设备布局优化
EP4198731B1 (en) * 2017-03-29 2025-07-30 Ab Initio Technology LLC Systems and methods for performing data processing operations using variable level parallelism
US10817310B2 (en) 2017-09-01 2020-10-27 Ab Initio Technology Llc Executing graph-based program specifications
US11423083B2 (en) 2017-10-27 2022-08-23 Ab Initio Technology Llc Transforming a specification into a persistent computer program
US11188434B2 (en) 2017-12-08 2021-11-30 Ab Initio Technology Llc Systems and methods for monitoring execution of structured query language (SQL) queries
US10559276B2 (en) * 2018-02-03 2020-02-11 Facebook Technologies, Llc Apparatus, system, and method for mitigating motion-to-photon latency in head-mounted displays
CN110297699B (zh) 2018-03-23 2021-09-14 华为技术有限公司 调度方法、调度器、存储介质及系统
US12032631B2 (en) 2018-05-30 2024-07-09 Ab Initio Technology Llc Systems and methods for dataflow graph optimization
US10978176B2 (en) 2018-06-29 2021-04-13 pulseData Inc. Machine learning systems and methods for predicting risk of renal function decline
CN114008594A (zh) * 2019-07-17 2022-02-01 谷歌有限责任公司 调度计算图上的操作
US11093223B2 (en) 2019-07-18 2021-08-17 Ab Initio Technology Llc Automatically converting a program written in a procedural programming language into a dataflow graph and related systems and methods
GB202004594D0 (en) 2020-03-30 2020-05-13 Microsoft Technology Licensing Llc Partitioning for an execution pipeline
DE112022000878T5 (de) 2021-01-31 2024-02-15 Ab Initio Technology Llc Datensatzmultiplexer für datenverarbeitungssystem
CA3209125A1 (en) 2021-01-31 2022-08-04 Ab Initio Technology Llc Data processing system with manipulation of logical dataset groups
WO2024086674A1 (en) * 2022-10-18 2024-04-25 The Regents Of The University Of California Systems and methods for subgraph matching using active learning
US20240168758A1 (en) * 2022-10-21 2024-05-23 C Squared Ip Holdings Llc Systems and methods of automatically constructing directed acyclic graphs (dags)

Citations (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US4491909A (en) * 1981-03-18 1985-01-01 International Business Machines Corporation Data processing system having shared memory
US20020129340A1 (en) * 1999-10-28 2002-09-12 Tuttle Douglas D. Reconfigurable isomorphic software representations

Family Cites Families (27)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US4972314A (en) 1985-05-20 1990-11-20 Hughes Aircraft Company Data flow signal processor method and apparatus
JPH04227589A (ja) * 1990-08-10 1992-08-17 Sharp Corp データフロープログラムの割付け装置および割付け方法
US5694546A (en) 1994-05-31 1997-12-02 Reisman; Richard R. System for automatic unattended electronic information transport between a server and a client by a vendor provided transport software with a manifest list
US5768594A (en) * 1995-07-14 1998-06-16 Lucent Technologies Inc. Methods and means for scheduling parallel processors
US5996019A (en) * 1995-07-19 1999-11-30 Fujitsu Network Communications, Inc. Network link access scheduling using a plurality of prioritized lists containing queue identifiers
US7028088B1 (en) * 1996-04-03 2006-04-11 Scientific-Atlanta, Inc. System and method for providing statistics for flexible billing in a cable environment
US5966072A (en) 1996-07-02 1999-10-12 Ab Initio Software Corporation Executing computations expressed as graphs
US6330008B1 (en) 1997-02-24 2001-12-11 Torrent Systems, Inc. Apparatuses and methods for monitoring performance of parallel computing
US6110220A (en) * 1997-02-24 2000-08-29 Lucent Technologies Inc. Concurrent hardware-software co-synthesis of hard real-time aperiodic and periodic specifications of embedded system architectures
US5933640A (en) 1997-02-26 1999-08-03 Digital Equipment Corporation Method for analyzing and presenting test execution flows of programs
US5999729A (en) 1997-03-06 1999-12-07 Continuum Software, Inc. System and method for developing computer programs for execution on parallel processing systems
US6088716A (en) 1997-04-28 2000-07-11 Ab Initio Software Corporation Method for preventing buffer deadlock in dataflow computations
US6437796B2 (en) 1998-02-17 2002-08-20 Sun Microsystems, Inc. Multiple processor visibility search system and method
US6480876B2 (en) 1998-05-28 2002-11-12 Compaq Information Technologies Group, L.P. System for integrating task and data parallelism in dynamic applications
US6675189B2 (en) 1998-05-28 2004-01-06 Hewlett-Packard Development Company, L.P. System for learning and applying integrated task and data parallel strategies in dynamic applications
US6101599A (en) * 1998-06-29 2000-08-08 Cisco Technology, Inc. System for context switching between processing elements in a pipeline of processing elements
SE515820C3 (sv) 1998-09-01 2001-12-11 Ericsson Telefon Ab L M Mobiltelefonapparat och metod för vidarekoppling av samtal
US6983463B1 (en) * 1998-10-02 2006-01-03 Microsoft Corporation Network independent profiling of applications for automatic partitioning and distribution in a distributed computing environment
US6608628B1 (en) 1998-11-06 2003-08-19 The United States Of America As Represented By The Administrator Of The National Aeronautics And Space Administration (Nasa) Method and apparatus for virtual interactive medical imaging by multiple remotely-located users
US6449711B1 (en) 1999-02-04 2002-09-10 Sun Microsystems, Inc. Method, apparatus, and article of manufacture for developing and executing data flow programs
US6748440B1 (en) * 1999-05-12 2004-06-08 Microsoft Corporation Flow of streaming data through multiple processing modules
US6584581B1 (en) * 1999-12-06 2003-06-24 Ab Initio Software Corporation Continuous flow checkpointing data processing
US6848100B1 (en) 2000-03-31 2005-01-25 Intel Corporation Hierarchical software path profiling
US6813761B1 (en) 2000-06-30 2004-11-02 Microsoft Corporation Methods for enhancing flow analysis
GB2376094A (en) 2001-05-30 2002-12-04 Ibm Flexible navigation of a workflow graph in a data processing system
JP3719509B2 (ja) * 2002-04-01 2005-11-24 株式会社ソニー・コンピュータエンタテインメント シリアル演算パイプライン、演算装置、算術論理演算回路およびシリアル演算パイプラインによる演算方法
US7167850B2 (en) 2002-10-10 2007-01-23 Ab Initio Software Corporation Startup and control of graph-based computation

Patent Citations (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US4491909A (en) * 1981-03-18 1985-01-01 International Business Machines Corporation Data processing system having shared memory
US20020129340A1 (en) * 1999-10-28 2002-09-12 Tuttle Douglas D. Reconfigurable isomorphic software representations

Also Published As

Publication number Publication date
WO2007137034A2 (en) 2007-11-29
WO2007137034A9 (en) 2009-01-15
EP2021920A2 (en) 2009-02-11
CA2650143C (en) 2017-06-13
HK1122627A1 (en) 2009-05-22
EP2021920A4 (en) 2013-01-23
JP5940503B2 (ja) 2016-06-29
CN101443733B (zh) 2013-10-30
CN103778015A (zh) 2014-05-07
AU2007253862B2 (en) 2012-07-12
JP2009537908A (ja) 2009-10-29
US7870556B2 (en) 2011-01-11
US20070271381A1 (en) 2007-11-22
KR20090018113A (ko) 2009-02-19
AU2007253862C1 (en) 2013-03-21
AU2007253862A1 (en) 2007-11-29
JP2014029718A (ja) 2014-02-13
WO2007137034A3 (en) 2008-10-30
CN103778015B (zh) 2017-06-09
CA2650143A1 (en) 2007-11-29
CN101443733A (zh) 2009-05-27
EP2021920B1 (en) 2017-03-01

Similar Documents

Publication Publication Date Title
KR101413049B1 (ko) 그래프 기반 계산에서의 계산 자원의 관리
CN105164638B (zh) 控制由计算系统执行的任务
Pautasso et al. Parallel computing patterns for grid workflows
JP6763072B2 (ja) データ処理グラフのコンパイル
JPWO2008120367A1 (ja) 並列化プログラム生成方法、並列化プログラム生成装置、及び並列化プログラム生成プログラム
KR20090089327A (ko) 파이프라인 컴퓨터 처리의 병렬화를 위한 방법 및 시스템
JP2005508029A (ja) リコンフィギュアラブルアーキテクチャのためのプログラム変換方法
Zimmermann et al. An approach to machine-independent parallel programming
Ruggiero Throttle Mechanisms for the Manchester Dataflow Machine
JP4946323B2 (ja) 並列化プログラム生成方法、並列化プログラム生成装置、及び並列化プログラム生成プログラム
AU2012241069B2 (en) Managing computing resources in graph-based computations
Krebs et al. A translation framework from RVC-CAL dataflow programs to OpenCL/SYCL based implementations
HK1122627B (en) Managing computing resources in graph-based computations
HK1192782A (en) Managing computing resources in graph-based computations
Arafath et al. A novel instruction scheduling scheme for clustered VLIW architecture
HK1192782B (en) Managing computing resources in graph-based computations
Falk et al. Integrated modeling using finite state machines and dataflow graphs
Anders Complexity analysis of code generation for the SCAD machine
Gebrewahid et al. Actor fission transformations for executing dataflow programs on manycores
Sells A Code Architecture to Streamline the Missile Simulation Life Cycle
Sobral et al. A SCOOPP evaluation on packing parallel objects in run-time
CHᴀIᴍᴏᴠ Performance Analysis of Many-Task Runtimes
Monjau et al. Analysing non-functional requirements of embedded systems
Kempf et al. Simulation of scientific programs on parallel architectures with MIMESIS environment
HK1256053B (en) Data processing graph compilation

Legal Events

Date Code Title Description
PA0105 International application

Patent event date: 20081210

Patent event code: PA01051R01D

Comment text: International Patent Application

PG1501 Laying open of application
N231 Notification of change of applicant
PN2301 Change of applicant

Patent event date: 20100323

Comment text: Notification of Change of Applicant

Patent event code: PN23011R01D

A201 Request for examination
PA0201 Request for examination

Patent event code: PA02012R01D

Patent event date: 20111122

Comment text: Request for Examination of Application

E902 Notification of reason for refusal
PE0902 Notice of grounds for rejection

Comment text: Notification of reason for refusal

Patent event date: 20130605

Patent event code: PE09021S01D

E701 Decision to grant or registration of patent right
PE0701 Decision of registration

Patent event code: PE07011S01D

Comment text: Decision to Grant Registration

Patent event date: 20140327

GRNT Written decision to grant
PR0701 Registration of establishment

Comment text: Registration of Establishment

Patent event date: 20140623

Patent event code: PR07011E01D

PR1002 Payment of registration fee

Payment date: 20140623

End annual number: 3

Start annual number: 1

PG1601 Publication of registration
FPAY Annual fee payment

Payment date: 20170613

Year of fee payment: 4

PR1001 Payment of annual fee

Payment date: 20170613

Start annual number: 4

End annual number: 4

FPAY Annual fee payment

Payment date: 20180612

Year of fee payment: 5

PR1001 Payment of annual fee

Payment date: 20180612

Start annual number: 5

End annual number: 5

FPAY Annual fee payment

Payment date: 20190613

Year of fee payment: 6

PR1001 Payment of annual fee

Payment date: 20190613

Start annual number: 6

End annual number: 6

PR1001 Payment of annual fee

Payment date: 20220614

Start annual number: 9

End annual number: 9

PR1001 Payment of annual fee

Payment date: 20240617

Start annual number: 11

End annual number: 11

PR1001 Payment of annual fee

Payment date: 20250616

Start annual number: 12

End annual number: 12