One: [onert] Improve performance of WICPlanner

[periannath]

This issue comes from https://github.com/Samsung/ONE/issues/2610#issuecomment-654663283

It seems there is room for optimization for WICPlanner.

Current implementation of WICPlanner::buildMemoryPlans

1. Sort operands in descending order of size
2. Allocate memory block for sorted operands
   
   
   
   1. Traverse whole allocated memory plans to find interfered operands
   
   
   2. Use FirstFit algorithm to find memory block which does not overlap with interfered operands
   
   

Time complexity

• N : Number of operands, M : Maximum number of interference for operands
  
  
  
  • Ideally, M can become N. However, M is usually much less than N.
  
  
• Step 1. : O(NlogN)
• Step 2. i : O(N^2)
• Step 2. ii : O(NM)
• Whole process : O(N^2)

I'll find a way to remove O(N^2) in Step 2. i

[periannath]

Trial 1 : Efficient memory plan traverse

• _mem_plans has operand to {offset,size} map
• Use _mem_plans instead of _claimed_plans
• Find live and interference plans and sort them
  
  
  
  • Time complexity : O(NMlogM)
  
  

Result

Base c892e701a9bf88d70263c5b137aeaa1616c6e15c

[WICPlanner] claim takes 0 ms
[WICPlanner] buildMemoryPlan takes 0 ms
[WICPlanner] claim takes 92 ms
[WICPlanner] buildMemoryPlan takes 147 ms
===================================
MODEL_LOAD   takes 23.942 ms
PREPARE      takes 443.932 ms
EXECUTE      takes 9.454 ms
- MEAN     :  9.454 ms
- MAX      :  9.454 ms
- MIN      :  9.454 ms
- GEOMEAN  :  9.454 ms
===================================

• Planning time : 239 ms

Trial 1 6505c1d0c207bb370f96bfa084dff7a8abedc9e1

[WICPlanner] claim takes 0 ms
[WICPlanner] buildMemoryPlan takes 0 ms
[WICPlanner] claim takes 92 ms
[WICPlanner] buildMemoryPlan takes 99 ms
===================================
MODEL_LOAD   takes 21.785 ms
PREPARE      takes 373.272 ms
EXECUTE      takes 9.680 ms
- MEAN     :  9.680 ms
- MAX      :  9.680 ms
- MIN      :  9.680 ms
- GEOMEAN  :  9.680 ms
===================================

• Planning time : 191 ms

[periannath]

Trial 2 : Using std::vector for _interference_graph

• Inference will be inserted only once in WICPlanner::claim
• Don't have to use std::unordered_set for _interference_graph
• Additional memory allocated for std::unordered_set will be removed
  
  
  
  • vector : 4 byte for entry
  
  
  • unordered_set : 36 byte for entry
  
  
  • https://lemire.me/blog/2016/09/15/the-memory-usage-of-stl-containers-can-be-surprising/
  
  

Trial 2 577c32eb0363e6c4785cec0d9daa52b6227c651e

[WICPlanner] claim takes 0 ms
[WICPlanner] buildMemoryPlan takes 0.007 ms
[WICPlanner] claim takes 16.205 ms
[WICPlanner] buildMemoryPlan takes 54.898 ms
===================================
MODEL_LOAD   takes 23.002 ms
PREPARE      takes 241.202 ms
EXECUTE      takes 9.484 ms
- MEAN     :  9.484 ms
- MAX      :  9.484 ms
- MIN      :  9.484 ms
- GEOMEAN  :  9.484 ms
===================================

• Planning time : 16.2 + 54.9 = 71.1 ms
  
  
  
  • 3.36x faster than base
  
  

[periannath]

Done.