Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Question about basis_convert function #5

Open
halfmanli opened this issue Jun 22, 2024 · 0 comments
Open

Question about basis_convert function #5

halfmanli opened this issue Jun 22, 2024 · 0 comments

Comments

@halfmanli
Copy link

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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant