Optimize graph#

Change topology (model isomorphism)#

These optimizations update the topology of the computation graph however they do not change its mathematical properties (i.e. for the same output the model before and after optimization will provide the same result), that is what we call model isomorphism.

Fuse MatMul & added#

ONNX graph can export Dense / FC operator as two operator, MatMul and Add. This recipie replace these two operator and create a FC operator, reusing the Producers attached to the MatMul and Add operator.

Tiling#

Proposed implementation#

Graph transformation:

flowchart LR B(Before) -.-> Conv(Conv) -.-> After(After)

Before#

flowchart LR B(Before) -.- IN(( )) ----> Stripe_1(Stripe_1) & Stripe_2(Stripe_2) & Stripe_3(Stripe_3) & Stripe_4(Stripe_4) & Stripe_5(Stripe_5) style IN fill:#000 Stripe_1(Stripe_1) ----> ConvStripe_1(ConvStripe_1) Stripe_2(Stripe_2) ----> ConvStripe_2(ConvStripe_2) Stripe_3(Stripe_3) ----> ConvStripe_3(ConvStripe_3) Stripe_4(Stripe_4) ----> ConvStripe_4(ConvStripe_4) Stripe_5(Stripe_5) ----> ConvStripe_5(ConvStripe_5) ConvStripe_1(ConvStripe_1) & ConvStripe_2(ConvStripe_2) & ConvStripe_3(ConvStripe_3) & ConvStripe_4(ConvStripe_4) & ConvStripe_5(ConvStripe_5) ----> Unstripe(Unstripe) -.-> After(After)

After#

Scheduling:

sequenceDiagram autonumber Stripe->>ConvStripe: inputsReq = convLoadBufferIn() memTransferWait(inputsReq) inputsReq = convLoadBufferIn() ConvStripe->>Unstripe: outputsReq = bufferToMemTransfer2D() Stripe->>ConvStripe: memTransferWait(inputsReq) inputsReq = convLoadBufferIn() ConvStripe->>Unstripe: memTransferWait(outputsReq) outputsReq = bufferToMemTransfer2D() Stripe->>ConvStripe: memTransferWait(inputsReq) inputsReq = convLoadBufferIn() ConvStripe->>Unstripe: memTransferWait(outputsReq) outputsReq = bufferToMemTransfer2D() Stripe->>ConvStripe: memTransferWait(inputsReq) inputsReq = convLoadBufferIn() ConvStripe->>Unstripe: memTransferWait(outputsReq) outputsReq = bufferToMemTransfer2D() Stripe->>ConvStripe: memTransferWait(inputsReq) ConvStripe->>Unstripe: memTransferWait(outputsReq) outputsReq = bufferToMemTransfer2D() memTransferWait(outputsReq)

gantt dateFormat s axisFormat %S title Scheduling Stripe_1 :crit, s1, 0, 2.05s Stripe_2 :s1b, after s1, 2s ConvStripe_1 :crit, c1, after s1, 3s Unstripe(1) :crit, u1, after c1, 0.05s Unstripe(1) :u1b, after u1, 1.5s Stripe_2 :crit, s2, after u1, 0.05s Stripe_3 :s2b, after s2, 2s ConvStripe_2 :crit, c2, after s2, 3s Unstripe(2) :crit, u2, after c2, 0.05s Unstripe(2) :u2b, after u2, 1.5s Stripe_3 :crit, s3, after u2, 0.05s Stripe_4 :s3b, after s3, 2s ConvStripe_3 :crit, c3, after s3, 3s Unstripe(3) :crit, u3, after c3, 0.05s Unstripe(3) :u3b, after u3, 1.5s Stripe_4 :crit, s4, after u3, 0.05s Stripe_5 :s4b, after s4, 2s ConvStripe_4 :crit, c4, after s4, 3s Unstripe(4) :crit, u4, after c4, 0.05s Unstripe(4) :u4b, after u4, 1.5s Stripe_5 :crit, s5, after u4, 0.05s ConvStripe_5 :crit, c5, after s5, 3s Unstripe(5) :crit, u5, after c5, 1.55s

Multi-layer spatial tiling#

Goal: tile spatially multiple layers.

Proposed method:

Specify the required tile’s position and size at some place in the block;
Propagate backward the required spatial tile’s position and size (with a mechanism similar to receptive field in N2D2);
Create the tiling operators and duplicate the subgraph.

flowchart LR B(Before) -.-> Conv_1(Conv 3x3) ----> ReLU_1(ReLU) ----> Conv_2(Conv 1x1) ----> ReLU_2(ReLU) ----> Pad(Pad 1 1 1 1) ----> Conv_3(Conv 3x3) ----> ReLU_3(ReLU) -.-> After(After)

Multiple layers tiling example#

flowchart LR B(Before) -. 50x50 .-> Conv_1(Conv 3x3) ----> ReLU_1(ReLU) -- 48x48 --> Conv_2(Conv 1x1) ----> ReLU_2(ReLU) -- 48x48 --> Pad(Pad 1 1 1 1) -- 50x50 --> Conv_3(Conv 3x3) -- 48x48 --> ReLU_3(ReLU) -.-> After(After) style Pad fill:#fbb

Initial dimensions#

When computing tile sizes, Pad operators must be handled specifically. Only edge tiles should keep the padding corresponding to the position of the tile on edge. An offset may be required on the final relative tile’s position and size to take into account dimensions reduction due to the convolution.

flowchart LR B(Before) -. 50x50 .- branch(( )) branch -.-> Tiling_0x0_19x19 -- -1x-1_18x18 --> Conv_1_1(Conv 3x3) ----> ReLU_1_1(ReLU) -- 0x0_17x17 --> Conv_2_1(Conv 1x1) ----> ReLU_2_1(ReLU) -- 0x0_17x17 --> Pad_1(Pad 1 1 0 0) -- -1x-1_17x17 --> Conv_3_1(Conv 3x3) -- 0x0_16x16 --> ReLU_3_1(ReLU) -.-> Untiling branch -.-> Tiling_15x0_35x19 -- 14x-1_34x18 --> Conv_1_2(Conv 3x3) ----> ReLU_1_2(ReLU) -- 15x0_33x17 --> Conv_2_2(Conv 1x1) ----> ReLU_2_2(ReLU) -- 15x0_33x17 --> Pad_2(Pad 1 0 0 0) -- 15x-1_33x17 --> Conv_3_2(Conv 3x3) -- 16x0_32x16 --> ReLU_3_2(ReLU) -.-> Untiling branch -.-> Tiling_31x0_50x19 -- 30x-1_49x18 --> Conv_1_3(Conv 3x3) ----> ReLU_1_3(ReLU) -- 31x0_48x17 --> Conv_2_3(Conv 1x1) ----> ReLU_2_3(ReLU) -- 31x0_48x17 --> Pad_3(Pad 1 0 0 1) -- 31x-1_49x17 --> Conv_3_3(Conv 3x3) -- 32x0_48x16 --> ReLU_3_3(ReLU) -.-> Untiling branch -.-> Tiling_0x15_19x35 -- -1x14_18x34 --> Conv_1_4(Conv 3x3) ----> ReLU_1_4(ReLU) -- 0x15_17x33 --> Conv_2_4(Conv 1x1) ----> ReLU_2_4(ReLU) -- 0x15_17x33 --> Pad_4(Pad 0 1 0 0) -- -1x15_17x33 --> Conv_3_4(Conv 3x3) -- 0x16_16x32 --> ReLU_3_4(ReLU) -.-> Untiling branch -.-> Tiling_15x15_35x35 -- 14x14_34x34 --> Conv_1_5(Conv 3x3) ----> ReLU_1_5(ReLU) -- 15x15_33x33 --> Conv_2_5(Conv 1x1) ----> ReLU_2_5(ReLU) -- 15x15_33x33 --> Pad_5(Pad 0 0 0 0) -- 15x15_33x33 --> Conv_3_5(Conv 3x3) -- 16x16_32x32 --> ReLU_3_5(ReLU) -.-> Untiling branch -.-> Tiling_31x15_50x35 -- 30x14_49x34 --> Conv_1_6(Conv 3x3) ----> ReLU_1_6(ReLU) -- 31x15_48x33 --> Conv_2_6(Conv 1x1) ----> ReLU_2_6(ReLU) -- 31x15_48x33 --> Pad_6(Pad 0 0 0 1) -- 31x15_49x33 --> Conv_3_6(Conv 3x3) -- 32x16_48x32 --> ReLU_3_6(ReLU) -.-> Untiling branch -.-> Tiling_0x31_19x50 -- -1x30_18x49 --> Conv_1_7(Conv 3x3) ----> ReLU_1_7(ReLU) -- 0x31_17x48 --> Conv_2_7(Conv 1x1) ----> ReLU_2_7(ReLU) -- 0x31_17x48 --> Pad_7(Pad 0 1 1 0) -- -1x31_17x49 --> Conv_3_7(Conv 3x3) -- 0x32_16x48 --> ReLU_3_7(ReLU) -.-> Untiling branch -.-> Tiling_15x31_35x50 -- 14x30_34x49 --> Conv_1_8(Conv 3x3) ----> ReLU_1_8(ReLU) -- 15x31_33x48 --> Conv_2_8(Conv 1x1) ----> ReLU_2_8(ReLU) -- 15x31_33x48 --> Pad_8(Pad 0 0 1 0) -- 15x31_33x49 --> Conv_3_8(Conv 3x3) -- 16x32_32x48 --> ReLU_3_8(ReLU) -.-> Untiling branch -.-> Tiling_31x31_50x50 -- 30x30_49x49 --> Conv_1_9(Conv 3x3) ----> ReLU_1_9(ReLU) -- 31x31_48x48 --> Conv_2_9(Conv 1x1) ----> ReLU_2_9(ReLU) -- 31x31_48x48 --> Pad_9(Pad 0 0 1 1) -- 31x31_49x49 --> Conv_3_9(Conv 3x3) -- 32x32_48x48 --> ReLU_3_9(ReLU) -.-> Untiling Untiling -. 48x48 .-> After(After) style Pad_1 fill:#fbb style Pad_2 fill:#fbb style Pad_3 fill:#fbb style Pad_4 fill:#fbb style Pad_5 fill:#f00 style Pad_6 fill:#fbb style Pad_7 fill:#fbb style Pad_8 fill:#fbb style Pad_9 fill:#fbb style branch fill:#000

Tile size computation#