Add an importer for AutoHoG json netlists

[j2kun]

We're discussing integration with AutoHoG (see https://www.x-mol.net/paper/article/1761273823319789568).

The authors have a json spec for their optimized circuit output, and we want to enable this as an entry point to the rest of the compiler. Later, we will likely add an exit point to go from HEIR to AutoHoG's input specification.

[asraa]

Just to CC @sbian3 @Lavendes

[Lavendes]

The AutoHog JSON file is formatted as:

{
    "circuit_name": <circuit_name>
    "ports": {
        <node_id>: <port_details>,
        ...
    },
    "cells": {
        <node_id>: <cell_details>,
        ...
    },
}

Where is:

{
    "direction":  <"input" | "output">,
    "bits": <bit_vector>              // a node id list that defines the nodes (gates) connect from the input or connect to the output
}

and is:

{
    "hide_name": <1 | 0>
    "type": <cell_type>               // the gate type, including the conventional gates "AND", "OR", "XOR"... as well as our "HomGateS", "HomGateM"
    "parameters":{}                   // built-in parameters of yosys, default is empty
    "attributes":{}                   // built-in attributes of yosys, default is empty
    "port_directions":                // the inputs and outputs of the gate 
    {
        <port_name>: <"input" | "output">,
        ...
    },                                 
    "connections":                    // node id of the inputs and outputs
    {
        <port_name>: <bit_vector>,
        ...
    },
    "weights":                        // the weight for each input port
    {
        <port_name>: <weight>,        // weight is a int
        ...
    },
    "tableT":                         // the tableT (LUT) for each output port
    {
        <port_name>: <tableT>,        // Lut is a list of a 0-1 sequence, with a maximum length of 32 (under the parameter n=2048). If not full, 0s are padded for the remaining positions during PBS
        ...
    }                                 // If "type" is not "HomGate", both "weights" and "tableT" are empty
}

[asraa]

Hey @Lavendes , Thank you for the spec! Two quick questions about it

1. Where is the constant offset for the linear combo of the HomGate? Is it contained in weights but with some no-op input port?
2. Are HomGateS and HomGateM the single and multiple output gates? Or is it something else? (So I should expect one tableT for HomGateS and multiple for HomGateM?)

If you have any example inputs you can paste or commit into a test file, that would be greatly appreciated! I can work on the ingestion pass.

[Lavendes]

Hi

1. The offset for the linear combination is calculated as $(\text{sum(weights)} + 1) \cdot \mu$, where $\mu$ is the encoding parameter. For example, in TFHE the ciphertext is encoded as $(0,1) \rightarrow (-\frac{1}{4},\frac{1}{4})$ , the value of $\mu$ would be $\frac{1}{4}$
2. Yes. HomGateS refers to the single output gate, and HomGateM refers to the multiple output gates.

Here is a simple example of a 3-bit * 2-bit multiplier composed of one HomGateM and one HomGateS:

{  
"circuit_name": "3-2-Multiplier",
"ports": {
      "3": {
        "direction": "input",
        "bits": [7]
      },
      "6": {
        "direction": "input",
        "bits": [10, 7]
      },
      "5": {
        "direction": "input",
        "bits": [10, 7]
      },
      "4": {
        "direction": "input",
        "bits": [10, 7]
      },
      "2": {
        "direction": "input",
        "bits": [10, 7]
      },
      "c_1": {
        "direction": "output",
        "bits": [7]
      },
      "c_2": {
        "direction": "output",
        "bits": [7]
      },
      "c_3": {
        "direction": "output",
        "bits": [7]
      },
      "c_4": {
        "direction": "output",
        "bits": [10]
      },
      "c_5": {
        "direction": "output",
        "bits": [7]
      }
  },
"cells": {
    "7": {
      "hide_name": 1,
      "type": "HomGateM",
      "parameters": {
      },
      "attributes": {
      },
      "port_directions": {
        "$0$": "input",
        "$1$": "input",
        "$2$": "input",
        "$3$": "input",
        "$4$": "input",
        "$5$": "output",
        "$6$": "output",
        "$7$": "output",
        "$8$": "output",
        "$9$": "output",
        "$10$": "output"
      },
      "connections": {
        "$0$": 2,
        "$1$": 3,
        "$2$": 4,
        "$3$": 5,
        "$4$": 6,
        "$5$": "c_1",
        "$6$": "c_2",
        "$7$": "c_3",
        "$8$": "c_5",
        "$9$": 10,
        "$10$": 10
      },
      "weights": {
        "$0$": 16,
        "$1$": 8,
        "$2$": 4,
        "$3$": 2,
        "$4$": 1
      },
      "tableT": {
        "$5$": [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1],
        "$6$": [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0],
        "$7$": [0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 0, 0, 1, 1, 1],
        "$8$": [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
        "$9$": [0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1],
        "$10$": [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 0, 0]
      }
    },
    "10": {
      "hide_name": 1,
      "type": "HomGateS",
      "parameters": {
      },
      "attributes": {
      },
      "port_directions": {
        "$0$": "input",
        "$1$": "input",
        "$2$": "input",
        "$3$": "input",
        "$4$": "input",
        "$5$": "input",
        "$6$": "output"
      },
      "connections": {
        "$0$": 2,
        "$1$": 4,
        "$2$": 5,
        "$3$": 6,
        "$4$": 7,
        "$5$": 7,
        "$6$": "c_4"
      },
      "weights": {
        "$0$": 1,
        "$1$": 4,
        "$2$": 1,
        "$3$": 8,
        "$4$": 1,
        "$5$": 8
      },
      "tableT": {
        "$6$": [0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1]
      }
    }
  }
}

[j2kun]

Some notes on the spec:

• Port and cell names are sometimes strings and sometimes ints. It would be helpful if the identifier of an entity is always the same type (always string) no matter where it shows up in the document. E.g., in the above comment, document["ports"][port_name]["bits"] field, as well as document["cells"][cell_name]["connections"] use integers and strings intermixed.
• The endianness of the lookup table is not specified. Is the first entry in the list the output value for 0 or 2^n - 1?
• It's not clear how one cell's output is mapped to another cell's input. For example, cell "7" has two outputs $9$ and $10$ that both connect to 10, and cell "10" has two inputs $4$ and $5$ that connect from 7, but it's not specified whether $9$ connects to $4$ or $5$ and similarly for $10$.

Will update this comment further as I encounter other issues.

[Lavendes]

• Port and cell names can always be strings. We will modify the JSON file to output the port and cell names as strings.
• The first entry in the list outputs the value for 0.
• In the DAG, a 'key' attribute is utilized to differentiate between two wires connecting the same cells. When generating output files, we order them based on the key's sequence and make this attribute invisible. For the example here, there are 2 wires between cell "7" and cell "10": The first wire, with key=0, outputs from cell "7" at output $9$ and connects to cell "10"at input$4$. The second wire, with key=1, outputs from cell "7" at output $10$ and connects to cell "10"at input$5$.

[j2kun]

When generating output files, we order them based on the key's sequence and make this attribute invisible.

The problem is that JSON object keys are unordered, so there is no guarantee that they remain in the same order when reading the file. A JSON parser may read the keys into a data structure that does not preserve order, and iteration order can be (and is often, in practice) based on arbitrary hash values.

Are you relying on the numerical ordering implicit to the string "$9$ here? Should I be stripping out the dollar signs and converting it to an integer to get an explicit ordering?

It might just be simpler to link them explicitly. Something like

"connections": {
  "$0$": { "port": "2" },  // "cell" is optional in this case because it's an input port
  ...
  "$9$": { "cell": 10, "port": "$4$"},
  "$10$": { "cell": 10, "port": "$5$"},
},

[Lavendes]

I modified the ”connections“. Here is an example of a 4bit-4bit adder:

{
  "circuit_name": "Example Circuit",
  "ports": {
    "5": {
      "direction": "input",
      "bits": ["13"]
    },
    "9": {
      "direction": "input",
      "bits": ["13"]
    },
    "4": {
      "direction": "input",
      "bits": ["23", "13"]
    },
    "8": {
      "direction": "input",
      "bits": ["23", "13"]
    },
    "3": {
      "direction": "input",
      "bits": ["23", "10"]
    },
    "7": {
      "direction": "input",
      "bits": ["23", "10"]
    },
    "2": {
      "direction": "input",
      "bits": ["23", "10"]
    },
    "6": {
      "direction": "input",
      "bits": ["23", "10"]
    },
    "c_1": {
      "direction": "output",
      "bits": ["10"]
    },
    "c_2": {
      "direction": "output",
      "bits": ["11"]
    },
    "c_3": {
      "direction": "output",
      "bits": ["11"]
    },
    "c_4": {
      "direction": "output",
      "bits": ["13"]
    },
    "c_5": {
      "direction": "output",
      "bits": ["13"]
    }
  },
  "cells": {
    "23": {
      "hide_name": 1,
      "type": "HomGateS",
      "parameters": {
      },
      "attributes": {
      },
      "port_directions": {
        "$0$": "input",
        "$1$": "input",
        "$2$": "input",
        "$3$": "input",
        "$4$": "input",
        "$5$": "input",
        "$6$": "output"
      },
      "connections": {
        "$0$": {
          "port": "2"
        },
        "$1$": {
          "port": "3"
        },
        "$2$": {
          "port": "4"
        },
        "$3$": {
          "port": "6"
        },
        "$4$": {
          "port": "7"
        },
        "$5$": {
          "port": "8"
        },
        "$6$": {
          "cell": "13",
          "port": "$4$"
        }
      },
      "weights": {
        "$0$": 1,
        "$1$": 2,
        "$2$": 8,
        "$3$": 1,
        "$4$": 2,
        "$5$": 8
      },
      "tableT": {
        "$6$": [1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1]
      }
    },
    "11": {
      "hide_name": 1,
      "type": "HomGateM",
      "parameters": {
      },
      "attributes": {
      },
      "port_directions": {
        "$0$": "input",
        "$1$": "input",
        "$2$": "input",
        "$3$": "input",
        "$4$": "output",
        "$5$": "output"
      },
      "connections": {
        "$0$": {
          "cell": "10",
          "port": "$5$"
        },
        "$1$": {
          "cell": "10",
          "port": "$6$"
        },
        "$2$": {
          "cell": "10",
          "port": "$7$"
        },
        "$3$": {
          "cell": "13",
          "port": "$7$"
        },
        "$4$": {
          "port": "c_2"
        },
        "$5$": {
          "port": "c_3"
        }
      },
      "weights": {
        "$0$": 8,
        "$1$": 4,
        "$2$": 2,
        "$3$": 1
      },
      "tableT": {
        "$4$": [0, 0, 1, 1, 0, 0, 1, 1, 1, 1, 0, 0, 1, 1, 0, 0],
        "$5$": [0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0]
      }
    },
    "13": {
      "hide_name": 1,
      "type": "HomGateM",
      "parameters": {
      },
      "attributes": {
      },
      "port_directions": {
        "$0$": "input",
        "$1$": "input",
        "$2$": "input",
        "$3$": "input",
        "$4$": "input",
        "$5$": "output",
        "$6$": "output",
        "$7$": "output"
      },
      "connections": {
        "$0$": {
          "port": "4"
        },
        "$1$": {
          "port": "5"
        },
        "$2$": {
          "port": "8"
        },
        "$3$": {
          "port": "9"
        },
        "$4$": {
          "cell": "23",
          "port": "$6$"
        },
        "$5$": {
          "port": "c_4"
        },
        "$6$": {
          "port": "c_5"
        },
        "$7$": {
          "cell": "11",
          "port": "$3$"
        }
      },
      "weights": {
        "$0$": 16,
        "$1$": 8,
        "$2$": 4,
        "$3$": 2,
        "$4$": 1
      },
      "tableT": {
        "$5$": [1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1, 1, 1, 0, 0, 0, 1, 1, 0, 0, 0, 1, 1],
        "$6$": [0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 0, 0, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1],
        "$7$": [0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0]
      }
    },
    "10": {
      "hide_name": 1,
      "type": "HomGateM",
      "parameters": {
      },
      "attributes": {
      },
      "port_directions": {
        "$0$": "input",
        "$1$": "input",
        "$2$": "input",
        "$3$": "input",
        "$4$": "output",
        "$5$": "output",
        "$6$": "output",
        "$7$": "output"
      },
      "connections": {
        "$0$": {
          "port": "2"
        },
        "$1$": {
          "port": "3"
        },
        "$2$": {
          "port": "6"
        },
        "$3$": {
          "port": "7"
        },
        "$4$": {
          "port": "c_1"
        },
        "$5$": {
          "cell": "11",
          "port": "$0$"
        },
        "$6$": {
          "cell": "11",
          "port": "$1$"
        },
        "$7$": {
          "cell": "11",
          "port": "$2$"
        }
      },
      "weights": {
        "$0$": 8,
        "$1$": 4,
        "$2$": 2,
        "$3$": 1
      },
      "tableT": {
        "$4$": [0, 0, 1, 1, 0, 0, 1, 1, 1, 1, 0, 0, 1, 1, 0, 0],
        "$5$": [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 1],
        "$6$": [0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 1, 1],
        "$7$": [0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0]
      }
    }
  }
}

[j2kun]

Thanks! I think I should be able to finish the importer in https://github.com/google/heir/pull/756 this week.

[j2kun]

For the same reason, it would be helpful if the cells object was instead a list with the name as a value instead of an object key. The reason is that it seems that the cells are intended to be topologically sorted, but that is not preserved by the use of an object. If that's not the case, I can toposort the cells when I read it in.

On Sun, Jul 7, 2024, 4:48 AM Lavendes @.***> wrote:

I modified the to make the link explicit. Here is a modified example of a 4bit-4bit adder:

''' { "circuit_name": "Example Circuit", "ports": { "5": { "direction": "input", "bits": ["13"] }, "9": { "direction": "input", "bits": ["13"] }, "4": { "direction": "input", "bits": ["23", "13"] }, "8": { "direction": "input", "bits": ["23", "13"] }, "3": { "direction": "input", "bits": ["23", "10"] }, "7": { "direction": "input", "bits": ["23", "10"] }, "2": { "direction": "input", "bits": ["23", "10"] }, "6": { "direction": "input", "bits": ["23", "10"] }, "c_1": { "direction": "output", "bits": ["10"] }, "c_2": { "direction": "output", "bits": ["11"] }, "c_3": { "direction": "output", "bits": ["11"] }, "c_4": { "direction": "output", "bits": ["13"] }, "c_5": { "direction": "output", "bits": ["13"] } }, "cells": { "23": { "hide_name": 1, "type": "HomGateS", "parameters": { }, "attributes": { }, "port_directions": { "$0$": "input", "$1$": "input", "$2$": "input", "$3$": "input", "$4$": "input", "$5$": "input", "$6$": "output" }, "connections": { "$0$": { "port": "2" }, "$1$": { "port": "3" }, "$2$": { "port": "4" }, "$3$": { "port": "6" }, "$4$": { "port": "7" }, "$5$": { "port": "8" }, "$6$": { "cell": "13", "port": "$4$" } }, "weights": { "$0$": 1, "$1$": 2, "$2$": 8, "$3$": 1, "$4$": 2, "$5$": 8 }, "tableT": { "$6$": [1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1] } }, "11": { "hide_name": 1, "type": "HomGateM", "parameters": { }, "attributes": { }, "port_directions": { "$0$": "input", "$1$": "input", "$2$": "input", "$3$": "input", "$4$": "output", "$5$": "output" }, "connections": { "$0$": { "cell": "10", "port": "$5$" }, "$1$": { "cell": "10", "port": "$6$" }, "$2$": { "cell": "10", "port": "$7$" }, "$3$": { "cell": "13", "port": "$7$" }, "$4$": { "port": "c_2" }, "$5$": { "port": "c_3" } }, "weights": { "$0$": 8, "$1$": 4, "$2$": 2, "$3$": 1 }, "tableT": { "$4$": [0, 0, 1, 1, 0, 0, 1, 1, 1, 1, 0, 0, 1, 1, 0, 0], "$5$": [0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0] } }, "13": { "hide_name": 1, "type": "HomGateM", "parameters": { }, "attributes": { }, "port_directions": { "$0$": "input", "$1$": "input", "$2$": "input", "$3$": "input", "$4$": "input", "$5$": "output", "$6$": "output", "$7$": "output" }, "connections": { "$0$": { "port": "4" }, "$1$": { "port": "5" }, "$2$": { "port": "8" }, "$3$": { "port": "9" }, "$4$": { "cell": "23", "port": "$6$" }, "$5$": { "port": "c_4" }, "$6$": { "port": "c_5" }, "$7$": { "cell": "11", "port": "$3$" } }, "weights": { "$0$": 16, "$1$": 8, "$2$": 4, "$3$": 2, "$4$": 1 }, "tableT": { "$5$": [1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1, 1, 1, 0, 0, 0, 1, 1, 0, 0, 0, 1, 1], "$6$": [0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 0, 0, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1], "$7$": [0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0] } }, "10": { "hide_name": 1, "type": "HomGateM", "parameters": { }, "attributes": { }, "port_directions": { "$0$": "input", "$1$": "input", "$2$": "input", "$3$": "input", "$4$": "output", "$5$": "output", "$6$": "output", "$7$": "output" }, "connections": { "$0$": { "port": "2" }, "$1$": { "port": "3" }, "$2$": { "port": "6" }, "$3$": { "port": "7" }, "$4$": { "port": "c_1" }, "$5$": { "cell": "11", "port": "$0$" }, "$6$": { "cell": "11", "port": "$1$" }, "$7$": { "cell": "11", "port": "$2$" } }, "weights": { "$0$": 8, "$1$": 4, "$2$": 2, "$3$": 1 }, "tableT": { "$4$": [0, 0, 1, 1, 0, 0, 1, 1, 1, 1, 0, 0, 1, 1, 0, 0], "$5$": [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 1], "$6$": [0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 1, 1], "$7$": [0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0] } } } } '''

— Reply to this email directly, view it on GitHub https://github.com/google/heir/issues/686#issuecomment-2212421441, or unsubscribe https://github.com/notifications/unsubscribe-auth/AAS2PKWTSUI62M7ZVL5M2CLZLETJBAVCNFSM6AAAAABIEA2PSWVHI2DSMVQWIX3LMV43OSLTON2WKQ3PNVWWK3TUHMZDEMJSGQZDCNBUGE . You are receiving this because you authored the thread.Message ID: @.***>

[Lavendes]

It's not necessary to toposort the cells, but it could be beneficial. We modified the key for the cells and added a 'cell_name' to each cell with the 'node_id' as the value.

{
  "circuit_name": "Example Circuit",
  "ports": {
    "d_5": {
      "direction": "input",
      "bits": ["13"]
    },
    "d_9": {
      "direction": "input",
      "bits": ["13"]
    },
    "d_4": {
      "direction": "input",
      "bits": ["23", "13"]
    },
    "d_8": {
      "direction": "input",
      "bits": ["23", "13"]
    },
    "d_3": {
      "direction": "input",
      "bits": ["23", "10"]
    },
    "d_7": {
      "direction": "input",
      "bits": ["23", "10"]
    },
    "d_2": {
      "direction": "input",
      "bits": ["23", "10"]
    },
    "d_6": {
      "direction": "input",
      "bits": ["23", "10"]
    },
    "c_1": {
      "direction": "output",
      "bits": ["10"]
    },
    "c_4": {
      "direction": "output",
      "bits": ["13"]
    },
    "c_5": {
      "direction": "output",
      "bits": ["13"]
    },
    "c_2": {
      "direction": "output",
      "bits": ["11"]
    },
    "c_3": {
      "direction": "output",
      "bits": ["11"]
    }
  },
  "cells": {
    "G1": {
      "cell_name": "23",
      "hide_name": 1,
      "type": "HomGateS",
      "parameters": {
      },
      "attributes": {
      },
      "port_directions": {
        "$0$": "input",
        "$1$": "input",
        "$2$": "input",
        "$3$": "input",
        "$4$": "input",
        "$5$": "input",
        "$6$": "output"
      },
      "connections": {
        "$0$": {
          "port": "d_2"
        },
        "$1$": {
          "port": "d_3"
        },
        "$2$": {
          "port": "d_4"
        },
        "$3$": {
          "port": "d_6"
        },
        "$4$": {
          "port": "d_7"
        },
        "$5$": {
          "port": "d_8"
        },
        "$6$": {
          "cell": "13",
          "port": "$4$"
        }
      },
      "weights": {
        "$0$": 1,
        "$1$": 2,
        "$2$": 8,
        "$3$": 1,
        "$4$": 2,
        "$5$": 8
      },
      "tableT": {
        "$6$": [1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1]
      }
    },
    "G2": {
      "cell_name": "10",
      "hide_name": 1,
      "type": "HomGateM",
      "parameters": {
      },
      "attributes": {
      },
      "port_directions": {
        "$0$": "input",
        "$1$": "input",
        "$2$": "input",
        "$3$": "input",
        "$4$": "output",
        "$5$": "output",
        "$6$": "output",
        "$7$": "output"
      },
      "connections": {
        "$0$": {
          "port": "d_2"
        },
        "$1$": {
          "port": "d_3"
        },
        "$2$": {
          "port": "d_6"
        },
        "$3$": {
          "port": "d_7"
        },
        "$4$": {
          "port": "c_1"
        },
        "$5$": {
          "cell": "11",
          "port": "$0$"
        },
        "$6$": {
          "cell": "11",
          "port": "$1$"
        },
        "$7$": {
          "cell": "11",
          "port": "$2$"
        }
      },
      "weights": {
        "$0$": 8,
        "$1$": 4,
        "$2$": 2,
        "$3$": 1
      },
      "tableT": {
        "$4$": [0, 0, 1, 1, 0, 0, 1, 1, 1, 1, 0, 0, 1, 1, 0, 0],
        "$5$": [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 1],
        "$6$": [0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 1, 1],
        "$7$": [0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0]
      }
    },
    "G3": {
      "cell_name": "13",
      "hide_name": 1,
      "type": "HomGateM",
      "parameters": {
      },
      "attributes": {
      },
      "port_directions": {
        "$0$": "input",
        "$1$": "input",
        "$2$": "input",
        "$3$": "input",
        "$4$": "input",
        "$5$": "output",
        "$6$": "output",
        "$7$": "output"
      },
      "connections": {
        "$0$": {
          "port": "d_4"
        },
        "$1$": {
          "port": "d_5"
        },
        "$2$": {
          "port": "d_8"
        },
        "$3$": {
          "port": "d_9"
        },
        "$4$": {
          "cell": "23",
          "port": "$6$"
        },
        "$5$": {
          "port": "c_4"
        },
        "$6$": {
          "port": "c_5"
        },
        "$7$": {
          "cell": "11",
          "port": "$3$"
        }
      },
      "weights": {
        "$0$": 16,
        "$1$": 8,
        "$2$": 4,
        "$3$": 2,
        "$4$": 1
      },
      "tableT": {
        "$5$": [1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1, 1, 1, 0, 0, 0, 1, 1, 0, 0, 0, 1, 1],
        "$6$": [0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 0, 0, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1],
        "$7$": [0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0]
      }
    },
    "G4": {
      "cell_name": "11",
      "hide_name": 1,
      "type": "HomGateM",
      "parameters": {
      },
      "attributes": {
      },
      "port_directions": {
        "$0$": "input",
        "$1$": "input",
        "$2$": "input",
        "$3$": "input",
        "$4$": "output",
        "$5$": "output"
      },
      "connections": {
        "$0$": {
          "cell": "10",
          "port": "$5$"
        },
        "$1$": {
          "cell": "10",
          "port": "$6$"
        },
        "$2$": {
          "cell": "10",
          "port": "$7$"
        },
        "$3$": {
          "cell": "13",
          "port": "$7$"
        },
        "$4$": {
          "port": "c_2"
        },
        "$5$": {
          "port": "c_3"
        }
      },
      "weights": {
        "$0$": 8,
        "$1$": 4,
        "$2$": 2,
        "$3$": 1
      },
      "tableT": {
        "$4$": [0, 0, 1, 1, 0, 0, 1, 1, 1, 1, 0, 0, 1, 1, 0, 0],
        "$5$": [0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0]
      }
    }
  }
}

[j2kun]

For MLIR it is necessary to toposort, because MLIR represents programs in SSA form and can't construct an operation until all the operands have existing SSA values. So I will toposort it in the importer.

On Thu, Jul 11, 2024, 4:16 AM Lavendes @.***> wrote:

It's not necessary to toposort the cells, but it could be beneficial. We modified the key for the cells and added a 'cell_name' to each cell with the 'node_id' as the value.

{ "circuit_name": "Example Circuit", "ports": { "d_5": { "direction": "input", "bits": ["13"] }, "d_9": { "direction": "input", "bits": ["13"] }, "d_4": { "direction": "input", "bits": ["23", "13"] }, "d_8": { "direction": "input", "bits": ["23", "13"] }, "d_3": { "direction": "input", "bits": ["23", "10"] }, "d_7": { "direction": "input", "bits": ["23", "10"] }, "d_2": { "direction": "input", "bits": ["23", "10"] }, "d_6": { "direction": "input", "bits": ["23", "10"] }, "c_1": { "direction": "output", "bits": ["10"] }, "c_4": { "direction": "output", "bits": ["13"] }, "c_5": { "direction": "output", "bits": ["13"] }, "c_2": { "direction": "output", "bits": ["11"] }, "c_3": { "direction": "output", "bits": ["11"] } }, "cells": { "G1": { "cell_name": "23", "hide_name": 1, "type": "HomGateS", "parameters": { }, "attributes": { }, "port_directions": { "$0$": "input", "$1$": "input", "$2$": "input", "$3$": "input", "$4$": "input", "$5$": "input", "$6$": "output" }, "connections": { "$0$": { "port": "d_2" }, "$1$": { "port": "d_3" }, "$2$": { "port": "d_4" }, "$3$": { "port": "d_6" }, "$4$": { "port": "d_7" }, "$5$": { "port": "d_8" }, "$6$": { "cell": "13", "port": "$4$" } }, "weights": { "$0$": 1, "$1$": 2, "$2$": 8, "$3$": 1, "$4$": 2, "$5$": 8 }, "tableT": { "$6$": [1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1] } }, "G2": { "cell_name": "10", "hide_name": 1, "type": "HomGateM", "parameters": { }, "attributes": { }, "port_directions": { "$0$": "input", "$1$": "input", "$2$": "input", "$3$": "input", "$4$": "output", "$5$": "output", "$6$": "output", "$7$": "output" }, "connections": { "$0$": { "port": "d_2" }, "$1$": { "port": "d_3" }, "$2$": { "port": "d_6" }, "$3$": { "port": "d_7" }, "$4$": { "port": "c_1" }, "$5$": { "cell": "11", "port": "$0$" }, "$6$": { "cell": "11", "port": "$1$" }, "$7$": { "cell": "11", "port": "$2$" } }, "weights": { "$0$": 8, "$1$": 4, "$2$": 2, "$3$": 1 }, "tableT": { "$4$": [0, 0, 1, 1, 0, 0, 1, 1, 1, 1, 0, 0, 1, 1, 0, 0], "$5$": [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 1], "$6$": [0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 1, 1], "$7$": [0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0] } }, "G3": { "cell_name": "13", "hide_name": 1, "type": "HomGateM", "parameters": { }, "attributes": { }, "port_directions": { "$0$": "input", "$1$": "input", "$2$": "input", "$3$": "input", "$4$": "input", "$5$": "output", "$6$": "output", "$7$": "output" }, "connections": { "$0$": { "port": "d_4" }, "$1$": { "port": "d_5" }, "$2$": { "port": "d_8" }, "$3$": { "port": "d_9" }, "$4$": { "cell": "23", "port": "$6$" }, "$5$": { "port": "c_4" }, "$6$": { "port": "c_5" }, "$7$": { "cell": "11", "port": "$3$" } }, "weights": { "$0$": 16, "$1$": 8, "$2$": 4, "$3$": 2, "$4$": 1 }, "tableT": { "$5$": [1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1, 1, 1, 0, 0, 0, 1, 1, 0, 0, 0, 1, 1], "$6$": [0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 0, 0, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1], "$7$": [0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0] } }, "G4": { "cell_name": "11", "hide_name": 1, "type": "HomGateM", "parameters": { }, "attributes": { }, "port_directions": { "$0$": "input", "$1$": "input", "$2$": "input", "$3$": "input", "$4$": "output", "$5$": "output" }, "connections": { "$0$": { "cell": "10", "port": "$5$" }, "$1$": { "cell": "10", "port": "$6$" }, "$2$": { "cell": "10", "port": "$7$" }, "$3$": { "cell": "13", "port": "$7$" }, "$4$": { "port": "c_2" }, "$5$": { "port": "c_3" } }, "weights": { "$0$": 8, "$1$": 4, "$2$": 2, "$3$": 1 }, "tableT": { "$4$": [0, 0, 1, 1, 0, 0, 1, 1, 1, 1, 0, 0, 1, 1, 0, 0], "$5$": [0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0] } } } }

— Reply to this email directly, view it on GitHub https://github.com/google/heir/issues/686#issuecomment-2222662181, or unsubscribe https://github.com/notifications/unsubscribe-auth/AAS2PKW7QZUCMBCPREBCKQ3ZLZSPTAVCNFSM6AAAAABIEA2PSWVHI2DSMVQWIX3LMV43OSLTON2WKQ3PNVWWK3TUHMZDEMRSGY3DEMJYGE . You are receiving this because you authored the thread.Message ID: @.***>

[j2kun]

"G4": { "cell_name": "11",

Sorry, can a cell have just one identifier? If I'm topologically sorting the cells internally, and the connections refer to cells by their cell_name, it would be least surprising to have the cell_name key the object.

[Lavendes]

Yes, the cell_name can be used as the unique identifier for each cell.

Jeremy Kun @.***> 于2024年7月14日周日 11:51写道：

"G4": { "cell_name": "11",

Sorry, can a cell have just one identifier? If I'm topologically sorting the cells internally, and the connections refer to cells by their cell_name, it would be least surprising to have the cell_name key the object.

— Reply to this email directly, view it on GitHub https://github.com/google/heir/issues/686#issuecomment-2227185391, or unsubscribe https://github.com/notifications/unsubscribe-auth/APNPLMP62ARCAYVRBFTNPUDZMHYUVAVCNFSM6AAAAABIEA2PSWVHI2DSMVQWIX3LMV43OSLTON2WKQ3PNVWWK3TUHMZDEMRXGE4DKMZZGE . You are receiving this because you were mentioned.Message ID: @.***>

[j2kun]

@Lavendes the importer is ready for review in https://github.com/google/heir/pull/756, but there is still one problem with the port ordering. Because it's an object in the JSON, the ordering of the ports is arbitrary, but the generated MLIR function has to pick some ordering of inputs (in the case of the importer I wrote, the ciphertexts are organized into a tensor). While the function itself is correct, someone calling it will have no way to tell how to organize inputs or unpack outputs.

I recommend changing the ports top level field to an array:

  "ports": [
    {
      "name": "5",
      "direction": "input",
      "bits": ["13"]
    },
    {
      "name": "9",
      "direction": "input",
      "bits": ["13"]
    },
    ...
  ]

Then the generated function will have the first input being corresponding to port "5", the second to "9", etc.

[Lavendes]

Ok, we will change the ports to an array to ensure the input order is preserved.

Jeremy Kun @.***> 于2024年7月15日周一 03:24写道：

@Lavendes https://github.com/Lavendes the importer is ready for review in #756 https://github.com/google/heir/pull/756, but there is still one problem with the port ordering. Because it's an object in the JSON, the ordering of the ports is arbitrary, but the generated MLIR function has to pick some ordering of inputs (in the case of the importer I wrote, the ciphertexts are organized into a tensor). While the function itself is correct, someone calling it will have no way to tell how to organize inputs or unpack outputs.

I recommend changing the ports top level field to an array:

"ports": [ { "name": "5", "direction": "input", "bits": ["13"] }, { "name": "9", "direction": "input", "bits": ["13"] }, ... ]

Then the generated function will have the first input being corresponding to port "5", the second to "9", etc.

— Reply to this email directly, view it on GitHub https://github.com/google/heir/issues/686#issuecomment-2227458615, or unsubscribe https://github.com/notifications/unsubscribe-auth/APNPLMPJST6WCKXDSULMFSDZMLF5XAVCNFSM6AAAAABIEA2PSWVHI2DSMVQWIX3LMV43OSLTON2WKQ3PNVWWK3TUHMZDEMRXGQ2TQNRRGU . You are receiving this because you were mentioned.Message ID: @.***>

[github-actions[bot]]

[!NOTE] Re-commenting because this issue was closed with unresolved TODOs.

This issue has 1 outstanding TODOs:

• lib/Source/AutoHog/AutoHogImporter.cpp:296: detect proper minBitWidth from the circuit

This comment was autogenerated by todo-backlinks

[j2kun]

@Lavendes the last thing I'd like to do here is determine what LWE parameters to use for the ciphertexts. Since AutoHoG is picking coefficients, that implies some constraints on the plaintext encoding (e.g., you need at least 4 plaintext bits to multiply a ciphertext by 8, and some of the linear combinations have 8 as coefficients).

Does AutoHoG have this analysis internally? If so, can it be exported to the JSON? Otherwise, is there anything you think I should consider when picking the parameters besides the largest coefficient present in a linear combination?

[Lavendes]

In AutoHoG, the plaintext encoding is fixed. For instance, in our paper, we set $\mu = \frac{1}{2^7}$ and encode $(0,1)$ as $\left(-\frac{1}{2^7}, \frac{1}{2^7}\right)$. This encoding ensures that with $N = 2048$, we can have up to 32 slots for LUTs, allowing 32 different values in the test vector. If tableT does not reach 32, it can be padded with 0s or 1s.

Additionally, when utilizing the Negacyclic Property in PBS, the offset should be modified from $(\text{sum(weights)} + 1) \cdot \mu$ to $(\text{sum(weights)} + 1 + 2 \cdot (32 - \text{len(tableT)})) \cdot \mu.$ The last number in tableT should fill the lower bits of the test vector, and if tableT does not reach 32 elements, the higher bits can be padded with 0s or 1s.

[j2kun]

It may take us some more time to support this older style of encoding. IMO, the newer style of encodings are quite a bit simpler. I wonder if there's a way we can all use the newer kind.

[asraa]

IMO, the newer style of encodings are quite a bit simpler. I wonder if there's a way we can all use the newer kind.

Is the encoding really any different besides a scale and shift factor being applied to the message? For e.g. in this encoding we can consider it as reserving a padding bit P, a carry bit C for the linear combination, and 5 message bits. A 0 is mapped to [P | C | 00001] and the 1 is mapped to [P | C | 11110]. Am I reading into this correct?

Do you mean it's difficult to model this in the LWE ciphertext type? I would think encode maps the 0 -> 00001 and 1 to 11110 and then encrypt handles placing it in the correct message space of the 32-bit ciphertext.

[Lavendes]

I think encoding [0, 1] to [-1/(2^n), 1/(2^n)] and to n-bit cleartext like 000001 and 111110 are essentially the same.

Would it be feasible to set the cleartext_bitwidth to n and place these n bits in the MSB of the message space? We have considered the carry bit when choosing n, so there is no need for an extra carry bit.

asraa @.***> 于2024年7月31日周三 23:14写道：

IMO, the newer style of encodings are quite a bit simpler. I wonder if there's a way we can all use the newer kind.

Is the encoding really any different besides a scale and shift factor being applied to the message? For e.g. in this encoding we can consider it as reserving a padding bit P, a carry bit C for the linear combination, and 5 message bits. A 0 is mapped to [P | C | 00001] and the 1 is mapped to [P | C | 11110]. Am I reading into this correct?

Do you mean it's difficult to model this in the LWE ciphertext type? I would think encode maps the 0 -> 00001 and 1 to 11110 and then encrypt handles placing it in the correct message space of the 32-bit ciphertext.

— Reply to this email directly, view it on GitHub https://github.com/google/heir/issues/686#issuecomment-2260764107, or unsubscribe https://github.com/notifications/unsubscribe-auth/APNPLMMSELK2LFFLOGCMLSLZPD5MPAVCNFSM6AAAAABIEA2PSWVHI2DSMVQWIX3LMV43OSLTON2WKQ3PNVWWK3TUHMZDENRQG43DIMJQG4 . You are receiving this because you were mentioned.Message ID: @.***>