SimFHE icon indicating copy to clipboard operation
SimFHE copied to clipboard

Question about `basis_convert` function

Open halfmanli opened this issue 8 months ago • 0 comments

I am trying to understand the basis_convert function in evaluator.py, which is:

def basis_convert(
    input_ctxt: params.PolyContext,
    output_ctxt: params.PolyContext,
    arch_params: params.ArchParam,
):
    """
    Generate output_ctxt.limbs from input_ctxt.limbs
    This models the algorithm that takes in limbs x_1, ... , x_L and outputs
    x_j = sum_{i=1}^L [x_i * q_i'^{-1}] * q_i' mod p_j
    for each j from 1 to num_new_limbs.
    rd_in: handled by caller (includes constants), wr_out: handled by caller
    """

    ## No reads or writes in this function...

    stats = PerfCounter()

    stats.sw.add = input_ctxt.N * input_ctxt.limbs * output_ctxt.limbs
    stats.sw.mult = input_ctxt.N * input_ctxt.limbs * (1 + output_ctxt.limbs)

    stats.arch.add_cyc_fm = stats.sw.add / (arch_params.funits * arch_params.sets)
    stats.arch.add_cyc_sm = arch_params.add_lat + stats.arch.add_cyc_fm
    stats.arch.mult_cyc_fm = stats.sw.mult / (arch_params.funits * arch_params.sets)
    stats.arch.mult_cyc_sm = arch_params.mult_lat + stats.arch.mult_cyc_fm
    stats.arch.bsc_cyc_fm = stats.arch.mult_cyc_fm + stats.arch.add_cyc_fm
    stats.arch.bsc_cyc_sm = stats.arch.mult_cyc_sm + stats.arch.add_cyc_sm

    return stats

I am confused by:

    stats.sw.add = input_ctxt.N * input_ctxt.limbs * output_ctxt.limbs
    stats.sw.mult = input_ctxt.N * input_ctxt.limbs * (1 + output_ctxt.limbs)

How to understand the counter of modular add and modular multiplication? I think they should be:

    stats.sw.add = input_ctxt.N * (input_ctxt.limbs - 1) * output_ctxt.limbs  # we are accumulating input_ctxt.limbs polynomials
    stats.sw.mult = 2 * input_ctxt.N * input_ctxt.limbs * output_ctxt.limbs  #  there are two modular multiplications for each coefficient of polynomial in the equation

halfmanli avatar Jun 22 '24 07:06 halfmanli