# TRITON PARTITIONER EXPLORATION **To DO:** - [x] Basic installation of TritonPart? - [x] What is a hypergraph format? - [x] Requirements of Dot format? - [ ] Demo of TritonPart? - [ ] List of actions for modifying cost functon of TritonPart!! - [ ] List to actions for converting hypergraph format to dot format!! <!--- - [ ] Understanding the partitioner algorithm!! ---> --- <details open> <summary><b> <span style="color:red;"> Installation of Triton Part:</span> </b></summary> - Triton Part is a part of OpenRoad and has lots of dependecies with it. - So we will need to install all the dependecies of OpenRoad first. - <span style="color:red;"> [NOTE: I am using TOFC server which has Ubuntu OS compared to my local system which has Pop_OS. The reason for this being OpenRoad supports only handful of Operating systems currently (Linux, Red_Hat etc.).]</span> ``` git clone --recursive https://github.com/The-OpenROAD-Project/OpenROAD.git cd OpenROAD sudo ./etc/DependencyInstaller.sh ``` - Now that all the dependencies are resolved, we could install Triton_Part: - <span style="color:red;"> [NOTE: Installation may took around 15-30 minutes!!]</span> ``` git clone https://github.com/ombhilare999/TritonPart.git cd TritonPart mkdir build cd build cmake ../OpenROAD/ make ``` - How to test Triton_Part? ``` cd TritonPart/test ../build/src/openroad run_openroad.tcl | tee run.log ``` - Output should like this: ``` ========================================= [STATUS] Running FC multilevel coarsening ========================================= [COARSEN] Level 0 :: num_vertices = 109, num_hyperedges = 111 [COARSEN] Level 1 :: num_vertices = 108, num_hyperedges = 110 [INFO PAR-0001] Hierarchical coarsening time 0.000294701 seconds [Cutcost of partition : 525.0] [Vertex balance of block_0 : 0.34596 ( 38478.00000 ) [Vertex balance of block_1 : 0.31945 ( 35529.00000 ) [Vertex balance of block_2 : 0.33460 ( 37214.00000 ) [Refinement] Level 1 :: num_vertices = 109, num_hyperedges = 111, cutcost = 525.0, best_solution_id = 0 [INFO PAR-0158] Statistics of cut-overlay solution: [Cutcost of partition : 539.0] [Vertex balance of block_0 : 0.34596 ( 38478.00000 ) [Vertex balance of block_1 : 0.31945 ( 35529.00000 ) [Vertex balance of block_2 : 0.33460 ( 37214.00000 ) [Cutcost of partition : 539.0] [Vertex balance of block_0 : 0.34596 ( 38478.00000 ) [Vertex balance of block_1 : 0.31945 ( 35529.00000 ) [Vertex balance of block_2 : 0.33460 ( 37214.00000 ) Satisfy the balance constraint : true Satisfy the group constraint : true Satisfy the fixed vertices constraint : true [INFO PAR-0109] The runtime of multi-level partitioner : 47.304750635000005 seconds =============================================== Exiting TritonPart ``` </details> <details open> <summary><b> <span style="color:blue;"> What is a hypergraph format?</span> </b></summary> ### Info about hypergraph format: - HGraphFile for unweighted hypergraph: ![image](https://hackmd.io/_uploads/SyHNmdS2T.png) ``` 4 7 %(Number_of_hypergraphs, Number_of_vertices) 1 2 %hyper_graph 1 1 7 5 6 %h2 5 6 4 %h3 2 3 4 %h4 ``` - HGraphFile for weighted hyperedges (**fmt (type of hypergraph) := 1**): ![image](https://hackmd.io/_uploads/SkhhQuHnT.png) ``` 4 7 1 %(nhedges. nvtxs, fmt --> Type of hypergraph) 2 1 2 %[Weight of hypergraph], followed by vertices in a hypergraph 3 1 7 5 6 %[weight of h2], h2 8 5 6 4 %[weight of h3], h3 7 2 3 4 %[weight of h4], h4 ``` - HGraphFile for unweighted hyperedges but with weighted vertices (**fmt (type of hypergraph) := 10**): ![image](https://hackmd.io/_uploads/H1O6KOSna.png) ``` 4 7 10 %(nhedges. nvtxs, fmt --> Type of hypergraph) 1 2 %hyper_graph 1 1 7 5 6 %hyper_graph 2 5 6 4 %hyper_graph 3 2 3 4 %hyper_graph 4 5 %Weight of v1 1 %Weight of v2 8 %Weight of v3 7 %.. 3 %.. 9 %.. 3 %Weight of v7 ``` - HGraphFile for both weighted hyperedges and vertices (**fmt (type of hypergraph) := 11**): ![image](https://hackmd.io/_uploads/r12CK_B3T.png) ``` 4 7 11 %(nhedges. nvtxs, fmt --> Type of hypergraph) 2 1 2 %[Weight of hypergraph], followed by vertices in a hypergraph 3 1 7 5 6 %[weight of h2], h2 8 5 6 4 %[weight of h3], h3 7 2 3 4 %[weight of h4], h4 5 %Weight of v1 1 %Weight of v2 8 %Weight of v3 7 %.. 3 %.. 9 %.. 3 %Weight of v7 ``` - How are these hgr files are stored: ![image](https://hackmd.io/_uploads/Hy2s9_rnp.png) - More information could be find in the hMetis manual [link](https://janders.eecg.utoronto.ca/1387/ex2_circuits/manual_hmetis.pdf) ### Visualizer of .hgr format: > None available <b> <span style="color:green;"> Good Idea will be to creat one from scratch!!</span> </b> </details> <details open> <summary><b> <span style="color:orange;"> Requirements of Dot format?</span> </b></summary> ### Needed features by a dot file? - How does a dot file look? ![graphviz](https://hackmd.io/_uploads/S1p4eKrna.png) - What are required features? - **Different type of nodes**: - Load - Store - fadd - fsub - Const - **Each node may have different type of attributes**: - Example: `Load_0 [shape=record,opcode=input,data=in_re,label="{Load_0}"];` - `shape|data|label` seems dot format specific properties which could be ignored from functional point of view - Primary attribute of a node is a opcode. In CGRA-ME following Opcodes are supported. [<b> <span style="color:red;"> TODO: Not sure whether these opcodes are supported by Elastic CGRAs also. </span> </b>] ``` enum class OpCode : signed char { NOP = -1, SEXT = 1, ZEXT, TRUNC, INPUT, INPUT_PRED, OUTPUT_PRED, OUTPUT, PHI, CONST, ADD, SUB, MUL, DIV, AND, OR, XOR, SHL, ASHR, LSHR, LOAD, STORE, GEP, ICMP, CMP, BR, SQRT, FADD, FMUL, FDIV, FP2INT, INT2FP, MULU_FULL_LO, MULU_HALF_LO, MULU_QUART_LO, MULU_FULL_HI, MULU_HALF_HI, MULU_QUART_HI, MULS_FULL_LO, MULS_HALF_LO, MULS_QUART_LO, MULS_FULL_HI, MULS_HALF_HI, MULS_QUART_HI, ADD_FULL, ADD_HALF, ADD_QUART, SELECT }; ``` - **Connection between each nodes. These connections are also tagged via a operand to determine mapping in CAD flow** - Example: `Const_8 -> fmul_22[operand=any2input];` - In CGRA-ME following operands are supported. [<b> <span style="color:red;"> TODO: Not sure whether these operands are supported by Elastic CGRAs also. </span> </b>] ``` namespace Operands { static constexpr auto& UNTAGGED = ""; static constexpr auto& PREDICATE = "pred"; static constexpr auto& BINARY_LHS = "LHS"; static constexpr auto& BINARY_RHS = "RHS"; static constexpr auto& BINARY_ANY = "any2input"; static constexpr auto& TERNARY_ANY = "any3input"; static constexpr auto& MEM_ADDR = "addr"; static constexpr auto& MEM_DATA = "data"; static constexpr auto& BR_TRUE = "branch_true"; static constexpr auto& BR_FALSE = "branch_false"; }; ``` --- <!--- - Important question: How to transform these properties of a dot file into a hgr format which is partitionable by TritonPart? - My Thoughts: ---> </details> <!--- <details open> <summary><b> <span style="color:green;"> Understanding the partitioner algorithm!!</span> </b></summary> There are five main steps in the main algorithm, mainly 1) constraints-driven coarsening, 2) initial partitioning, 3) refinement, 4) cut-overlay clustering and partitioning (COCP), and 5) V-cycle refinement. </details> ---> <details open> <summary><b> <span style="color:green;"> TritonPart Exploration </span> </b></summary> ### Converting following .dot file into hgr manually: ![image](https://hackmd.io/_uploads/BJIofC02a.png) * Number of loads : 08 * Number of stores : 01 * Number of fadds : 08 * Number of fmuls : 09 * Number of constants : 09 </details>