증분 컴퓨팅

증분 계산이라고도 하는 증분 컴퓨팅은 데이터가 변경될 때마다 변경된 ^[1]^[2]^[3]데이터에 의존하는 출력만 재계산함으로써 시간을 절약하는 소프트웨어 기능입니다.증분 컴퓨팅이 성공하면 새로운 출력을 순진하게 계산하는 것보다 훨씬 더 빠를 수 있습니다.예를 들어 스프레드시트 소프트웨어 패키지는 재계산 기능에 증분 계산을 사용하여 변경된 셀에 직접 또는 간접적으로 의존하는 수식을 포함하는 셀만 업데이트할 수 있습니다.

증분 컴퓨팅을 다양한 코드에 대해 자동으로 구현할 수 있는 툴로 구현하면 이 툴은 최적화를 위한 프로그램 분석 툴의 한 예입니다.

증분 컴퓨팅은 하나 이상의 오래된 입출력 관계에서 새로운 입출력 쌍을 도출합니다.그러기 위해서는, δP 는 입력의 변경과 출력의 변경을 관련지을 필요가 있습니다.결과의 소비자는 완전히 갱신된 출력 또는 델타 출력, 또는 둘 다에 관심이 있을 수 있습니다.

스태틱과 다이내믹

증분 컴퓨팅 기술은 크게 두 가지 유형의 접근 방식으로 나눌 수 있습니다.

정적 접근법은 예를 들어 수동 설계 및 리팩터링 또는 자동 프로그램 변환을 사용하여 기존 프로그램 P에서 증분 프로그램을 도출하려고 시도한다.이러한 프로그램 변환은 입력 또는 입력 변경을 제공하기 전에 이루어집니다.

동적 어프로치는, 특정의 입력(I1)에 대해서 프로그램 P를 실행하는 것에 관한 정보를 기록해, 출력(O1에서O2)을 갱신하기 위해서 입력이 변경되었을 때에(I2로) 이 정보를 이용한다.그림에서는 프로그램 P와 증분 프로그램의 핵심을 구성하는 변화 계산 함수 δP와 입력 및 출력 쌍 I1, O1, I2, O2의 관계를 보여 줍니다.

전문적 접근법과 범용적 접근법

증분 컴퓨팅에 대한 일부 접근방식은 전문적이며 다른 접근방식은 범용적입니다.전문화된 접근법에서는 프로그래머가 변경되지 않은 하위 계산을 보존하기 위해 사용되는 알고리즘과 데이터 구조를 명시적으로 지정해야 합니다.반면 범용 접근법은 언어, 컴파일러 또는 알고리즘 기술을 사용하여 증분하지 ^[4]않은 프로그램에 증분 동작을 제공합니다.

정적 방식

파생상품 프로그램

$C=f(x_{1},x_{2},\dots x_{n})$ C $=$ $C=f(x_{1},x_{2},\dots x_{n})$ ( $C=f(x_{1},x_{2},\dots x_{n})$ , $C=f(x_{1},x_{2},\dots x_{n})$ , $C=f(x_{1},x_{2},\dots x_{n})$ n $){displaystyle$ C $x_{j}:=\Delta _{x_{j}}$ $f(x_{1},$ $x_{j}:=\Delta _{x_{j}}$ ${2},\dots$ $x_{j}:=\Delta _{x_{j}}$ ${n}}}$ 및 $C=f(x_{1},x_{2},\dots x_{n})$ 잠재적 $x_{j}:=\Delta _{x_{j}}$ x $:=\$ }=\ $Delta$ _ ${x_{j$ 의 전후에 코드를 삽입할 수 있습니다. $스타일$ C가 $C$ $재실행$ 속도보다 빠릅니다 $f$ 페이지가 서브셋L에 ^[5]프로그램의 정식 차별화를 위한 규칙 목록을 적어두었습니다.

유지 보수 보기

DBToaster와 같은 데이터베이스 시스템에서 뷰는 관계 대수로 정의됩니다.증분 뷰 유지보수는 관계 대수를 정적으로 분석하여 ^[6]행 삽입 등 작은 업데이트가 있는 경우 뷰를 신속하게 유지하는 업데이트 규칙을 만듭니다.

동적 방식

증분 계산은 재계산이 필요할 수 있는 모든 데이터 요소의 종속성 그래프를 구축함으로써 달성할 수 있습니다.단일 요소가 변경될 때 업데이트해야 하는 요소는 그래프의 종속성 관계의 전이적 닫힘에 의해 제공됩니다.즉, 변경된 요소에서 다른 요소로의 경로가 있는 경우, 후자는 (변경이 최종적으로 요소에 도달하는지 여부에 따라) 갱신될 수 있습니다.의존관계 그래프는 의존관계가 변경되거나 요소가 시스템에 추가 또는 삭제될 때 업데이트해야 할 수 있습니다.구현에서 내부적으로 사용되며 일반적으로 사용자에게 표시할 필요가 없습니다.

의존관계를 추적할 수 있는 중요한 값의 서브셋(집약 결과 등)을 식별하고 다른 의존변수를 점진적으로 재계산함으로써 가능한 모든 값에 대한 의존관계를 파악할 수 있으므로 추적하는 의존관계 정보의 양과 실행하는 재계산량의 균형을 맞출 수 있다.입력 변경 ^[7]시.

부분평가는 가능한 한 간단한 증분컴퓨팅의 자동화를 위한 방법으로 볼 수 있습니다.이 방법에서는 프로그램 데이터를 2개의 카테고리로 나누려고 시도합니다.프로그램의 입력에 따라 달라질 수 있는 것과 그렇지 않은 것(그리고 가장 작은 변경 단위는 단순히 "변화할 수 있는 모든 데이터"입니다).부분 평가는 다른 증분 컴퓨팅 기술과 결합할 수 있습니다.

의존관계 그래프의 사이클에서는 그래프를 한 번 통과해도 고정점에 도달하기에 충분하지 않을 수 있습니다.경우에 따라서는 시스템에 대한 완전한 재평가는 의미론적으로 증분평가와 동등하며 ^[8]이론적으로는 아니더라도 실제로 더 효율적일 수 있다.

기존 시스템

컴파일러 및 언어 지원

자동 증분화("자기 조정 계산", "적응 기능 프로그래밍"^[9]이라고도 함), 델타 ML, Haskell Adaptive
코넬 신시사이저 제너레이터^[10]
IceDust - 커스텀 도메인 고유의 언어.

프레임워크 및 라이브러리

Adapton^[11] - 여러 언어로 구현
단방향 데이터 흐름 제약(C++에서의 액티브 계산)
차등 데이터 흐름
제인 스트리트 증분
증분 데이터로그(Logicblox)
증분 프롤로그(XSB)^[12]
도메인 고유의 접근법:
- 증분 유형 검사

적용들

데이터베이스(보기 유지 보수)
시스템 구축
스프레드시트^[13]
개발 환경
재무 계산
속성 문법 평가
그래프 계산 및 쿼리
GUI(React 및 DOM 확산 등)
과학적 응용 프로그램

「」를 참조해 주세요.

레퍼런스

^ Carlsson, Magnus (2002). "Monads for incremental computing". Proceedings of the seventh ACM SIGPLAN international conference on Functional programming. New York: ACM. pp. 26–35. doi:10.1145/581478.581482. ISBN 1-58113-487-8.
^ Umut A. Acar (2005). Self-Adjusting Computation (PDF) (Ph.D. thesis).
^ Camil Demetrescu; Irene Finocchi; Andrea Ribichini (2011). "Reactive Imperative Programming with Dataflow Constraints". Proceedings of the 26th ACM International Conference on Object-Oriented Programming Systems Languages and Applications (OOPSLA 2011). ACM. pp. 407–426. arXiv:1104.2293. doi:10.1145/2048066.2048100. ISBN 978-1-4503-0940-0.
^ Yan Chen; Joshua Dunfield; Matthew A. Hammer; Umut A. Acar. Implicit self-adjusting computation for purely functional programs. ICFP '11. pp. 129–141. Archived from the original on 2016-10-30. Retrieved 2018-03-12.
^ Paige, Robert (1981). Formal Differentiation: A Program Synthesis Technique. UMI Research Press. ISBN 978-0-8357-1213-2.
^ Ahmad, Yanif; Kennedy, Oliver; Koch, Christoph; Nikolic, Milos (2012-06-01). "DBToaster: Higher-order Delta Processing for Dynamic, Frequently Fresh Views". Proc. VLDB Endow. 5 (10): 968–979. arXiv:1207.0137. doi:10.14778/2336664.2336670. ISSN 2150-8097.
^ Mugilan Mariappan; Keval Vora (2019). "GraphBolt: Dependency-Driven Synchronous Processing of Streaming Graphs". In European Conference on Computer Systems (EuroSys'19). pp. 25:1–25:16. doi:10.1145/3302424.3303974.
^ Kimberley Burchett; Gregory H. Cooper; Shriram Krishnamurthi (2007). "Lowering: A static optimization technique for transparent functional reactivity". In ACM SIGPLAN Symposium on Partial Evaluation and Semantics-Based Program Manipulation. pp. 71–80. CiteSeerX 10.1.1.90.5866. ISBN 978-1-59593-620-2.
^ Hammer, Matthew A.; Acar, Umut A.; Chen, Yan (2009). "CEAL". Proceedings of the 2009 ACM SIGPLAN conference on Programming language design and implementation - PLDI '09. p. 25. doi:10.1145/1542476.1542480. ISBN 9781605583921.
^ Reps, Thomas; Teitelbaum, Tim (1984). "The synthesizer generator". Proceedings of the first ACM SIGSOFT/SIGPLAN software engineering symposium on Practical software development environments - SDE 1. pp. 42–48. doi:10.1145/800020.808247. ISBN 978-0897911313.
^ "Adapton: Programming Language Abstractions for Incremental Computation". adapton.org. Retrieved 2016-10-07.
^ Saha, Diptikalyan; Ramakrishnan, C. R. (2005). "Incremental Evaluation of Tabled Prolog: Beyond Pure Logic Programs". Practical Aspects of Declarative Languages. Lecture Notes in Computer Science. Vol. 3819. pp. 215–229. CiteSeerX 10.1.1.111.7484. doi:10.1007/11603023_15. ISBN 978-3-540-30947-5. ISSN 0302-9743.
^ Hammer, Matthew; Phang, Khoo; Hicks, Michael; Foster, Jeffrey (2014). ADAPTON: Composable, Demand-Driven Incremental Computation (PDF). PLDI.

[monads-for-incremental-1] Carlsson, Magnus (2002). "Monads for incremental computing". Proceedings of the seventh ACM SIGPLAN international conference on Functional programming. New York: ACM. pp. 26–35. doi:10.1145/581478.581482. ISBN 1-58113-487-8.

[2] Umut A. Acar (2005). Self-Adjusting Computation (PDF) (Ph.D. thesis).

[3] Camil Demetrescu; Irene Finocchi; Andrea Ribichini (2011). "Reactive Imperative Programming with Dataflow Constraints". Proceedings of the 26th ACM International Conference on Object-Oriented Programming Systems Languages and Applications (OOPSLA 2011). ACM. pp. 407–426. arXiv:1104.2293. doi:10.1145/2048066.2048100. ISBN 978-1-4503-0940-0.

[4] Yan Chen; Joshua Dunfield; Matthew A. Hammer; Umut A. Acar. Implicit self-adjusting computation for purely functional programs. ICFP '11. pp. 129–141. Archived from the original on 2016-10-30. Retrieved 2018-03-12.

[5] Paige, Robert (1981). Formal Differentiation: A Program Synthesis Technique. UMI Research Press. ISBN 978-0-8357-1213-2.

[6] Ahmad, Yanif; Kennedy, Oliver; Koch, Christoph; Nikolic, Milos (2012-06-01). "DBToaster: Higher-order Delta Processing for Dynamic, Frequently Fresh Views". Proc. VLDB Endow. 5 (10): 968–979. arXiv:1207.0137. doi:10.14778/2336664.2336670. ISSN 2150-8097.

[7] Mugilan Mariappan; Keval Vora (2019). "GraphBolt: Dependency-Driven Synchronous Processing of Streaming Graphs". In European Conference on Computer Systems (EuroSys'19). pp. 25:1–25:16. doi:10.1145/3302424.3303974.

[8] Kimberley Burchett; Gregory H. Cooper; Shriram Krishnamurthi (2007). "Lowering: A static optimization technique for transparent functional reactivity". In ACM SIGPLAN Symposium on Partial Evaluation and Semantics-Based Program Manipulation. pp. 71–80. CiteSeerX 10.1.1.90.5866. ISBN 978-1-59593-620-2.

[HammerAcar2009-9] Hammer, Matthew A.; Acar, Umut A.; Chen, Yan (2009). "CEAL". Proceedings of the 2009 ACM SIGPLAN conference on Programming language design and implementation - PLDI '09. p. 25. doi:10.1145/1542476.1542480. ISBN 9781605583921.

[RepsTeitelbaum1984-10] Reps, Thomas; Teitelbaum, Tim (1984). "The synthesizer generator". Proceedings of the first ACM SIGSOFT/SIGPLAN software engineering symposium on Practical software development environments - SDE 1. pp. 42–48. doi:10.1145/800020.808247. ISBN 978-0897911313.

[11] "Adapton: Programming Language Abstractions for Incremental Computation". adapton.org. Retrieved 2016-10-07.

[SahaRamakrishnan2005-12] Saha, Diptikalyan; Ramakrishnan, C. R. (2005). "Incremental Evaluation of Tabled Prolog: Beyond Pure Logic Programs". Practical Aspects of Declarative Languages. Lecture Notes in Computer Science. Vol. 3819. pp. 215–229. CiteSeerX 10.1.1.111.7484. doi:10.1007/11603023_15. ISBN 978-3-540-30947-5. ISSN 0302-9743.

[adapton-pldi2014-13] Hammer, Matthew; Phang, Khoo; Hicks, Michael; Foster, Jeffrey (2014). ADAPTON: Composable, Demand-Driven Incremental Computation (PDF). PLDI.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

Search

증분 컴퓨팅

네임스페이스

더

목차

스태틱과 다이내믹

전문적 접근법과 범용적 접근법

정적 방식

파생상품 프로그램

유지 보수 보기

동적 방식

기존 시스템

컴파일러 및 언어 지원

프레임워크 및 라이브러리

적용들

「」를 참조해 주세요.

레퍼런스

Search

증분 컴퓨팅

스태틱과 다이내믹

전문적 접근법과 범용적 접근법

정적 방식

파생상품 프로그램

유지 보수 보기

동적 방식

기존 시스템

컴파일러 및 언어 지원

프레임워크 및 라이브러리

적용들

「 」를 참조해 주세요.

레퍼런스

「」를 참조해 주세요.