---
# System prepended metadata

title: Triton_Part_Exploration

---

# 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>