Framework Concepts - Synchronization

단순히 문서 해석과 궁금한 점을 덧붙여 작성하였습니다.

시리즈는 아래와 같습니다.

Framework Concepts

1. Calculators

2. Graphs

3. Packets

4. Synchronization

5. GPU

6. Real-time Streams

 

Framework Concepts - Synchronization

Scheduling mechanics

Mediapipe graph에서 Data processing은 CalculatorBase 서브클래스들로써 정의된 processing nodes 안에서 발생합니다. 스케줄링 시스템은 각 calculator가 실행되어야할 때 결정합니다.

각 그래프는 최소한 하나의 scheduler queue를 가지고 있습니다. 각 scheduler queue는 정확히 하나의 executor 를 가지고 있습니다. Nodes 들은 큐에 고정적으로 할당됩니다.(그리고 그러므로 executor 에게 할당됩니다.) 기본적으로 하나의 queue가 있고, 그 queue의 executor는 시스템의 가능성들을 기반으로 하는 다수의 쓰레드와 함께 있는 thread pool 입니다.

각 노드는 scheduling state를 가지고 있고, 그 scheduling state는 not ready, ready, 혹은 running 이 될 수 있습니다. 이 준비된 function은 노드가 실행할 준비가 되어있는지 결정합니다. 이 function은 graph initialization에서 발생되며, 노드가 실행이 끝날 때마다, 그리고 노드 inputs의 상태가 변경될 때마다 발생합니다.

이 준비된 function은 노드의 타입에 따라 사용됩니다. stream input이 없는 노드는 source node라고 알려져 있는데, 이 source nodes들은 항상 실행하기 위해 준비되어있으며, 이 준비는 그들이 닫히는 시점인 output을 위한 더 이상의 데이터가 없다고 프레임워크에 말할 때까지 입니다.

Non-source nodes 들은 만약 그들이 process 할 inputs들을 가지고 있고, 그래서 만약 그 inputs들이 타당한 input set 을 (아래 논의될) 노드의 input policy에 의한 conditions set에 따라 구성한다면, 준비되어있습니다. 대부분의 노드들은 기본 input policy를 사용하지만, 일부 노드들은 다른 것을 지정합니다.

Note: input policy를 변경하는 것은 calculator의 코드가 그것의 inputs 로부터 예상가능함을 보장함을 변경하기 때문에, 이것은 일반적으로 임의의 input policy 들과 뒤섞인 calculators 들은 가능하지 않습니다. 그러므로 특별한 input policy를 사용하는 calculator 는 그것을 위해 쓰여져야 하며, 그리고 그것의 계약 안에서 선언됩니다.

노드가 준비 될 때, task는 해당하는 scheduler queue에 추가되고, 그 queue는 priority queue 입니다. 그 priority function은 현재는 고정되어있고, 노드의 account static properties 와 그래프 내의 기하학 정렬을 고려합니다. 예를 들어, 노드들은 높은 우선순위를 가지고 있는 그래프의 output 면에 더 가깝습니다. 왜냐하면 source nodes는 낮은 우선순위를 갖고 있기 때문입니다.

각  queue 는 executor에 의해 실행되며, 그 executor는 실제로 돌아가는 calculator의 코드에 의해 실행되는 task를 실행하는데에 책임이 있습니다. 다른 executors 들은 제공되거나 설정될 수 있습니다; 이것은 실행되는 자원들의 사용을 사용에 맞게 변경하는 데에 사용될 수 있습니다. 예를 들면 낮은 우선순위의 쓰레드들에서 실행되고 있는 확실한 노드들입니다.

Timestamp Synchronization

Mediapipe 그래프 실행은 탈중앙화되어있습니다. global clock이 없고, 다른 노드들은 동시에 다른 timestamp으로부터 데이터를 처리할 수 있습니다. 이것은 pipelining을 거쳐 더 높은 처리량을 허락합니다.

그러나, 시간 정보는 많은 perception 흐름에서 매우 중요합니다. 여러 input streams를 받는 노드들은 대개 특정한 방법으로 그들을 조정하는 것이 필요합니다. 예를 들어, object detector는 프레임으로부터 경계진 사각형들의 리스트를 출력하고, 이 정보는 아마도 원래 프레임과 함께 처리되야 하는 렌더링 노드들에 필요할 겁니다. 

그래서, 하나의 mediapipe 프레임워크의 중요한 의무 중 하나는 노드를 위한 input synchronization을 제공하는 것입니다. 프레임워크 mechanics 의 측면에서, timestamp의 우선적 역할은 synchronization key로써 제공되는 것이빈다.

더 나아가서, Mediapipe는 결정적인 기능들을 제공하도록 설계되었는데, 이것은 많은 시나리오들(테스팅, 시뮬레이션, 배치 프로세싱 등등)에서 중요합니다. 그래프 작성자들들이 실시간 제약조건을 충족하는데 필요한 결정론을 완화할 수 있도록 허용하기 때문입니다.

synchronization과 determinism 의 두 가지 측면에서 몇 가지 설계 원칙들을 내포합니다. 특히, 주어진 stream 안으로 push되는 그 packets는 단일적으로 timestamps를 증가시켜야만 합니다: 이것은 많은 노드들을 위해 유용한 가정에 국한되지 않고, 동기화 로직에 의거하기도 합니다. 각 stream은 timestamp 경계를 가지고 있고, 이 경계는 stream에서 새로운 packet을 위해 허용된 가능한 가장 낮은 timestamp입니다. timestamp T가 함께있는 packet이 도착할 때, 그 경계는 단조로운 요구사항을 반영하여 자동적으로 T+1이 됩니다. 이것은 T 보다 더 낮은 timestamp를 가진 packet이 더이상 없다는 것을 확실히 하기 위함을 알 수 있도록 프레임워크에게 허용합니다.

Input policies

동기화는 노드에 의해 서술된 input policy를 사용함으로써 각 노드에서 지역적으로 다뤄집니다. 

기본 input policy 은 DefaultInputStreamHandler에 의해 정의되고, inputs의 결정론적인 동기화를 이후에 따라오는 보장들과 함께 제공됩니다.

• 만약 같은 timestamp를 가진 packets이 다양한 input streams로 제공될 때, 그들은 항상 그들의 실시간 도착 순서에 상관없이 함께 처리됩니다.
• Input sets들은 엄격하게 timestamp 순서로 처리됩니다.
• Packets는 삭제되지 않으며, 처리가 완전히 deterministic 입니다.
• 노드는 위의 보장이 주어지면 최대한 빨리 데이터를 처리할 준비가 됩니다.

Note: 이것의 중요한 결론은 만약 calculator가 항상 packets를 출력할 때 현재의 input timestamp에 사용한다면, 출력은 본질적으로 단조롭게 증가하는 timestamp 요구사항을 준수합니다.

Warning: 다른 면에서, 이것은 input packet이 모든 streams를 위해 항상 가능하다는 것을 보장하지 않습니다.

이것이 어떻게 동작하는지를 설명하기 위해서, 우리는 고정된 timestamp의 정의를 소개할 필요가 있습니다. 우리는 stream 안에 있는 timestamp가 만약 timestamp bound 보다 낮을 경우 고정되었다고 말합니다. 다른 말로, timestamp 는 한번 timestamp의 input의 상태가 변경될 수 없다고 알려지면 stream 을 위해서 고정됩니다: packet이 있는 경우, 혹은 확실하게 그 timestamp를 가지고 있는 packet이 도착하지 않는 경우입니다.

Note: 이러한 이유 때문에, Mediapipe 는 또한 마지막 packet이 암시하는 것보다 timestamp bound를 더 명시적으로 진행시키기 위해서 stream producer를 허용합니다. 예를 들어 tighter bound를 제공하는 것입니다. 이것은 downstream nodes를 그들의 inputs에 가능한 빨리 고정시키기 위한 것을 허용합니다.

timestamp는 만약 timestamp가 이 streams의 각각에 고정된다면 여러 개의 streams를 가로질러 고정됩니다. 더 나아가서, 만약 timestamp가 고정되었다면, 그것은 이전 모든 timestamps가 또한 고정되었다는 것을 암시합니다. 그러므로 고정된 timestamps 는 오름차순 순서로 결정적으로 처리될 수 있습니다.

이 정의대로, 만약 고정되어 모든 input streams를 가로지르고 최소한 하나의 input stream에 packet을 포함하고 있는 timestamp 가 있다면 기본 input policy를 가지는 calculator 가 준비됩니다. 그 input policy는 calculator를 위한 하나의 input set 으로써 고정된 timestamp를 위한 모든 가능한 packets를 제공합니다.

이 결정론적인 행동의 하나의 결과로, 여러 input streams와 함께하는 nodes를 위해, timestamp를 고정되도록 하기 위한 이론상으로 경계가 없는 기다림이 있을 수 있습니다, 그리고 경계없는 무제한 패킷의 수는 그 동안 버퍼에 쌓일 수 있습니다. (두 개의 input streams 를 포함하는 노드를 가정하고, 그 중 하나는 packets을 계속 보냅니다. 왜냐하면 그 나머지는 아무것도 보내지 않고 경계에서 벗어나지 않습니다.)

결국, 우리는 또한 custom input policy 들을 제공합니다: 예를 들어, SyncSetInputStreamHandler라고 정의된 다른 동기화 집합에서 inputs 을 쪼개는 것, 혹은 전적으로 동기화를 피하는 것 그리고 ImmediateInputStreamHandler라고 정의된 inputs이 오는 즉시 처리하는 것입니다.

Flow control

두 개의 메인 흐름 제어 메카니즘이 있습니다. backpressure 메카니즘은 packets가 CalculatorGraphConfig::max_queue_size에 의해 정의된 (설정가능한) 한계에 도달한 stream이 버퍼처리 되었을 때 upstream 노드의 실행을 억제합니다. 이 메카니즘은 결정론적인 행동을 유지하고, 필요할 때 설정된 제한을 유연하게 하는 데드락 방지 시스템을 포함합니다.

두번째 시스템은 FlowLimiterCalculator에 의해 정의된 (전형적으로 custom input policies에 사용되는) 실시간 제약사항에 따른 packets을 버릴 수 있는 특별한 노드를 삽입하는 것으로 구성됩니다. 예를 들어, 일반적인 패턴은 최종 ouput으로부터 흐름-제어 node까지 loopback 연결이 되어있는 subgraph의 input에서 흐름-제어 node 를 위치시킵니다. 흐름-제어 node는 이와 같이 downstream graph에서 얼마나 많은 timestamps 가 처리되는지에 대해 계속 추적할 수 있고, 만약 이 개수가 (설정가능한) 한계에 도달할 때 packets을 버릴 수 있게 합니다; 그리고 packets이 upstream에 의해 버려지기 때문에, 우리는 timestamp를 부분적으로 처리해서 중간 stages 사이에서 packets을 버리는 것으로부터 얻게되는 낭비되는 일을 피할 수 있습니다. 

이 calculator-based 접근은 graph author가 어디로 packets이 떨어질지 조절하고, 자원 제약조건에 의거하여 graph의 행동을 조절하고 커스터마이징하는 유연성을 허용합니다.

 

References

https://google.github.io/mediapipe/framework_concepts/synchronization.html