RNS

‘rns’ Dialect

The rns dialect represents types and ops related to residue number system (RNS) representations of ring-like types, such as integers or polynomials decomposed from high-bit width to lower-bit-width prime moduli. Sometimes RNS is referred to as CRT, for “Chinese Remainder Theorem.”

This dialect is intended to be as generic as possible in terms of its interaction with standard MLIR. However, because of upstream MLIR constraints, we do not have the ability to override, say, arith.addi to operate on an rns type. So such situations require dedicated ops, canonicalization patterns, etc.

RNS types

RNSType

A residue number system representation

Syntax:

!rns.rns<
  ::llvm::ArrayRef<mlir::Type>   # basisTypes
>

Parameters:

RNS ops

rns.extract_slice (heir::rns::ExtractSliceOp)

Extracts a slice of RNS limbs

Syntax:

operation ::= `rns.extract_slice` $input attr-dict `:` type($input) `->` type($output)

Given an RNS-typed value with $k$ basis types (limbs), extract the slice of RNS components starting at start and having size size.

The result type is an RNS type containing the subset of basis types corresponding to the extracted slice. This is useful for operations like truncating or partitioning a modulus chain.

Traits: AlwaysSpeculatableImplTrait, Elementwise, Scalarizable, Tensorizable, Vectorizable

Interfaces: ConditionallySpeculatable, InferTypeOpInterface, NoMemoryEffect (MemoryEffectOpInterface)

Effects: MemoryEffects::Effect{}

Attributes:

Operands:

Results:

RNS additional definitions

TypeInterface definitions

RNSBasisTypeInterface (RNSBasisTypeInterface)

This interface is required for a type to be used as a parameter to an rns type.

Methods:

isCompatibleWith

bool isCompatibleWith(::mlir::Type otherRnsBasisType);

Returns true if this type is compatible with another type in the same RNS basis. In particular, the set of types used for a single RNS basis are never equal as types, but instead have some common attribute that must be checked here. For example, an RNS type where the basis types are polynomials would return true if the two types are both polynomial types, even if they have different coefficient moduli.

Another example is using mod arith types as the basis types, where by the nature of chinese reminder theorem, it is required that the modulus of them must be mutually coprime.

isCompatibleWith must be commutative, in the sense that type1.isCompatibleWith(type2) if and only if type2.isCompatibleWith(type1).

NOTE: This method must be implemented by the user.