multiplied.core package#

Subpackages#

Submodules#

multiplied.core.algorithm module#

class multiplied.core.algorithm.Algorithm(
bits: int,
*,
matrix: Any = None,
saturation: bool = False,
dadda: bool = False,
)[source]#

Bases: MultipliedMeta

Manages and sequences operations via a series of stages defined by templates and maps.

bits#

The bitwidth of the matrix to be multiplied.

Type:

int

matrix#

The matrix to be multiplied.

Type:

Matrix

dadda#

Whether to use the Dadda-Tree algorithm.

Type:

bool

state#

The current state of the algorithm.

Type:

int

algorithm#

The algorithm to be used.

Type:

dict[int, dict[str, Template | Matrix | Map]]

saturation#

Whether to use saturation arithmetic. Always to original bitwidth.

Type:

bool

auto_resolve_stage(*, recursive=True) → None[source]#

Automatically creates new algorithm stage to reduce the previous stage.

Parameters:

recursive (bool) – Recursively resolve until no partial products remain else resolve a single stage.

Return type:

None

exec(
a: int,
b: int,
) → dict[int, Matrix][source]#

Run entire algorithm with a single set of inputs then reset internal state.

Parameters:

  • a (int) – First operand

  • b (int) – Second operand

Returns:

resultant matrix indexed by stage, including initial state

Return type:

dict[int, Matrix]

push(
source: Template | Pattern,
map_: Any = None,
dadda: bool = False,
) → None[source]#

Populate algorithm stage based on template. Generates pseudo result to represent output matrix

Parameters:

  • source (Template | Pattern) – The template or pattern to be used for the algorithm stage.

  • map (Any, optional) – The map to be used for the algorithm stage, by default None

  • dadda (bool, optional) – Whether to use the Dadda-Tree algorithm, by default False

Return type:

None

Notes

Layout: >>> self.algorithm[x] = { >>> “template” : Template, >>> “pseudo” : Matrix, >>> “map” : Map}

reset(
matrix: Matrix,
) → None[source]#

Reset internal state and submit new initial matrix

step() → Matrix[source]#

Execute the next stage of the algorithm and update internal matrix

multiplied.core.algorithm.collect_template_units(
source: Template,
) → tuple[dict[str, Template], dict[str, list[tuple[int, int]]]][source]#

Return dict of isolated arithmetic units and their bounding box.

Parameters:

source (Template) – The source template to extract arithmetic units from.

Returns:

A tuple containing a dictionary of isolated arithmetic units and their bounding box.

Return type:

tuple[dict[str, Template], dict[str, list[tuple[int,int]]]]

Raises:

TypeError – If the source is not of type Template or Matrix.

multiplied.core.algorithm.hoist(
source: Matrix | Template,
*,
checksum: list[int] = [],
relative: bool = False,
) → Map[source]#

collect bits to the top of the matrix and produce corresponding map.

Parameters:

  • source (Matrix | Template) – The source matrix or template to hoist.

  • checksum (list[int], optional) – The checksum to use for hoisting, by default [].

  • relative (bool, optional) – Whether to use relative coordinates, by default False.

Returns:

The resulting map after hoisting.

Return type:

Map

multiplied.core.map module#

class multiplied.core.map.Map(map: list[Any] | int, *, dadda: bool = False)[source]#

Bases: MultipliedMeta

Generates Map object from row map or standard map.

Each Mapping is defined by a 2-bit hexadecimal value. Positive mappings move bits downwards, negative mappings move bits upwards.

Parameters:

map (list[Any]) – Simplified row map or 2D matrix.

Examples

>>> rmap = [00, FF, FF, 00]
>>> Map(rmap)
[[00,00,00,00,00,00,00,00],
 [FF,FF,FF,FF,FF,FF,FF,FF],
 [FF,FF,FF,FF,FF,FF,FF,FF],
 [00,00,00,00,00,00,00,00]]
build_map(rmap: list[str]) → list[list[str]][source]#

Use row map to generate standard map. Each element of simple map is a 2-bit, signed hex value. +ve = up, -ve = down.

Parameters:

rmap (list[str]) – Row map of the multiplied matrix.

Returns:

Standard map of the multiplied matrix.

Return type:

list[list[str]]

build_zero_map(bits: int) → list[list[str]][source]#

Build a zero map of the specified size.

multiplied.core.map.apply_complex_map(
matrix: list[list[str]],
map: Map,
unified_bounds: dict,
) → None[source]#

Applies a complex mapping to source Matrix

Parameters:

  • matrix (mp.Matrix) – Matrix to apply mapping to

  • map (mp.Map) – Multiplied Map object to apply mapping from

  • bounds (dict[str: list[int]]) – Unified bounds for all arithmetic units

multiplied.core.map.build_dadda_map(bits: int) → Map[source]#

Return map representing the starting point of Dadda tree algorithm.

multiplied.core.map.empty_map(bits: int) → Map[source]#

Return empty Multiplied Map object

multiplied.core.map.raw_dadda_map(bits: int) → list[list[str]][source]#

Returns a Dadda map of size bits.

multiplied.core.map.raw_zero_map(bits: int) → list[list[str]][source]#

Returns a zero-filled map of size bits.

multiplied.core.map.unify_bounds(bounds: dict) → dict[source]#

Returns a simplified bound for non empty characters

Parameters:

bounds (dict) – Bounding box for each arithmetic unit in Template object

Returns:

Unified bounds where {y : [x0, x1]}

Return type:

dict

See also

update_bounding_box()

multiplied.core.matrix module#

class multiplied.core.matrix.Matrix(
source: list[Any] | int,
*,
a: int = 0,
b: int = 0,
)[source]#

Bases: MultipliedMeta

Partial Product Matrix

Parameters:

  • matrix (list[Any] | int) – A 2D nested list or an integer representing the bitwidth.

  • a (int=0, optional) – First operand used in partial product generation(PPM)

  • b (int=0, optional) – Second operand used in PPM

apply_map(
map_: Map,
*,
unified_bounds: dict[str, list[int]] = {},
) → None[source]#

Use Multiplied Map object to apply mapping to matrix

Parameters:

  • map (Map) – Map object containing the generated row mapping

  • bounds (dict[str: list[int]]) – Unified bounds for all arithmetic units

Return type:

None

resolve_rmap(
*,
ignore_zeros: bool = True,
) → Map[source]#

Find empty rows, create simple map to efficiently pack rows

Parameters:

ignore_zeros (bool) – If True, ignore rows with only zeros

Returns:

Map object containing the generated row mapping

Return type:

Map

class multiplied.core.matrix.Slice(matrix: list[Any])[source]#

Bases: MultipliedMeta

Matrix slice which adheres to multiplied formatting rules. Retains metadata slice from source object:

Parameters:

matrix (list[Any]) – A slice from any Multiplied object.

multiplied.core.matrix.aggregate_bounds(
source: dict[str, Matrix],
template_bounds: dict[str, list[tuple[int, int]]],
) → dict[str, list[tuple[int, int]]][source]#
multiplied.core.matrix.empty_rows(matrix: Matrix) → int[source]#

Return the number of empty rows in a matrix

multiplied.core.matrix.matrix_merge(
source: dict[str, Matrix],
bounds: dict[str, list[tuple[int, int]]],
*,
complex: bool = False,
) → Matrix[source]#

Merge multiple matrices into a single matrix using pre calculated bounds

Parameters:

  • source (dict[str, Matrix]) – A dictionary of matrices to merge

  • bounds (dict[str, list[tuple[int, int]]]) – A dictionary of bounds for each matrix

  • complex (bool, optional, default: False) – Performs additional checks during merge

Return type:

Matrix

Examples

>>> source = {'A': Matrix([[1, _], [3, _]]),
              'B': Matrix([[_, 6], [_, 8]])}
>>> bounds = {'A': [(0, 0), (0, 0), (1, 1), (1, 1)],
>>>           'B': [(0, 1), (0, 1), (0, 1), (0, 1)]}
>>> matrix_merge(source, bounds)
Matrix([[1, 6], [4, 8]])
multiplied.core.matrix.matrix_scatter(
source: list[list],
bounds: dict[str, list[tuple[int, int]]],
fmt: str = 'auto',
) → dict[str, list[list]][source]#

Cast matrix subsets to initialised matrix. Each subset based on provided bounds.

Parameters:

  • source (list[list]) – Partial Product matrix to scatter.

  • bounds (dict[str, list[tuple[int, int]]]) – The bounds for each unit to extract from the source.

  • fmt (str, optional, default: "auto".) – “auto” : Infer format from source. “empty” : raw_empty_matrix() “zero” : raw_zero_matrix() “map” : raw_map_matrix()

Returns:

A dictionary of matrices containing the subset of source based on the provided bounds.

Return type:

dict[str, list[list]]

Notes

Each unit is extracted and placed at the same position within an initialised matrix with the same shape as the source.

See also

collect_template_units()

Examples

>>> source = [[0, 1, 2],
>>>           [3, 4, 5],
>>>           [6, 7, 8]]
>>> bounds = {"A": [(0, 0), (0, 1)],
>>>           "B": [(1, 1), (1, 2)]}
>>> matrix_scatter(source, bounds, fmt=empty)
[[[0, 1, _],
  [_, _, _],
  [_, _, _]],
 [[_, _, _],
  [_, 4, 5],
  [_, _, _]]]
multiplied.core.matrix.raw_empty_matrix(bits: int) → list[list[str]][source]#

Build an empty partial product matrix for a given bitwidth

Parameters:

bits (int) – The bitwidth of the matrix

Returns:

An empty 2d array for the given bitwidth

Return type:

list[list[str]]

Notes

An empty matrix is completely filled with underscores, following Multipied’s convention

Examples

>>> raw_zero_matrix(4)
[['_', '_', '_', '_', '_', '_', '_', '_'],
 ['_', '_', '_', '_', '_', '_', '_', '_'],
 ['_', '_', '_', '_', '_', '_', '_', '_'],
 ['_', '_', '_', '_', '_', '_', '_', '_']]
multiplied.core.matrix.raw_empty_row_pos(
matrix: list[list[str]],
row: int,
) → list[int][source]#

Return positions of empty rows in a raw matrix

multiplied.core.matrix.raw_empty_rows(matrix: list[list[str]]) → int[source]#

Return the number of empty rows in a raw matrix

multiplied.core.matrix.raw_zero_matrix(bits: int) → list[list[str]][source]#

Build a zero-filled partial product matrix for a given bitwidth

Parameters:

bits (int) – The bitwidth of the matrix

Returns:

A zero-filled 2d array for the given bitwidth

Return type:

list[list[str]]

Notes

A zero matrix is filled with zeros on the diagonal and underscores elsewhere, following Multipied’s convention

Examples

>>> raw_zero_matrix(4)
[['_', '_', '_', '_', '0', '0', '0', '0'],
 ['_', '_', '_', '0', '0', '0', '0', '_'],
 ['_', '_', '0', '0', '0', '0', '_', '_'],
 ['_', '0', '0', '0', '0', '_', '_', '_']]

multiplied.core.template module#

class multiplied.core.template.Pattern(pattern: list[str])[source]#

Bases: MultipliedMeta

Simplified representation of a Template.

Parameters:

pattern (list[str]) – Pattern to use for the template.

pattern#

Pattern to use for the template.

Type:

list[str]

bits#

Number of bits in the pattern.

Type:

int

get_runs() → list[tuple[int, int, int]][source]#

Returns list of tuples of length, position, and run of a given char in pattern

Examples

>>> Pattern(["A", "A", "A", "B", "B", "B", "B", "C", "C", "C", "C", "C"]).get_runs()
[(3, 0, 3), (4, 3, 4), (5, 7, 5)]
class multiplied.core.template.Template(
source: Pattern | list[list[str]],
*,
result: list[Any] | Matrix | None = None,
matrix: Any = None,
)[source]#

Bases: MultipliedMeta

A structure representing collections of arithmetic units using characters. Generated using a partial product matrix and a Pattern or custom template

Parameters:

  • source (Pattern | list[list[str]]) – The source of the template.

  • result (list[Any], optional) – The result of the template, by default [], automatically computed

  • matrix (Any, optional) – The matrix of the template, by default None

build_from_pattern(
pattern: Pattern,
matrix: Matrix,
) → None[source]#

Build a simple template and it’s result for a given bitwidth based on matrix. Defaults to empty matrix if matrix=None.

Parameters:

  • pattern (Pattern) – The pattern to build the template from.

  • matrix (Matrix) – The matrix to build the template from.

Return type:

None

Raises:

ValueError – If the pattern is not a valid Pattern object.

Examples

>>> [matrix] || [pattern] || [templ.] [result]
>>> ____0000 || [  'a',   || ____AaAa __aAaAaA
>>> ___0000_ ||    'a',   || ___AaAa_ ________
>>> __0000__ ||    'b',   || __BbBb__ bBbBbB__
>>> _0000___ ||    'b'  ] || _BbBb___ ________
update_bounding_box(
matrix: list[list[str]],
) → dict[str, list[tuple[int, int]]][source]#

Returns dictionary of arithmetic unit and coordinates for their boundaries.

No rigorous inter-row or intra-row boundary checking.

Notes

Bounds are in the form:

{“<unit>”: [(<start>, <end>), …]}

Where (<start>, <end>) are coordinate points in the matrix.

multiplied.core.template.build_adder(
char: str,
source_slice: Slice,
) → tuple[Slice, Slice][source]#

Create Adder template slice with zero initialised slice and chosen char.

Parameters:

  • char (str) – The character to use for the template.

  • source_slice (Slice) – The source slice to use for the template.

Returns:

The template “slices” for addition and the resulting slice.

Return type:

tuple[Slice, Slice]

Examples

>>> [slice-] || [adder-] || [result]
>>> ___0000_ || ___aAaA_ || _aAaAaA_
>>> __0000__ || __AaAa__ || ________
multiplied.core.template.build_csa(
char: str,
source_slice: Slice,
) → tuple[Slice, Slice][source]#

Create CSA template slice with source slice and chosen char.

Parameters:

  • char (str) – Character to use for the CSA template.

  • source_slice (Slice) – Source slice object to use for the CSA template.

Returns:

Template “slices” marked for a csa reduction and the resulting slice.

Return type:

tuple[Slice, Slice]

Examples

>>> [slice-] || [csa---] || [result]
>>> ____0000 || ____AaAa || __AaAaAa
>>> ___0000_ || ___aAaA_ || __aAaA__
>>> __0000__ || __AaAa__ || ________
multiplied.core.template.build_empty_slice(
source_slice: Slice,
) → tuple[Slice, Slice][source]#

Create an empty template slice. Returns template “slices” and resulting slice. Variable length, determined by source slice.

Parameters:

source_slice (Slice) – Source slice to use for the empty template.

Returns:

Tuple of template slices and resulting slice.

Return type:

tuple[Slice, Slice]

Notes

Used for building Templates with large runs of underscore characters. Underscores are used to represent empty spaces in the template.

Examples

>>> [slice-] || [empty-] || [result]
>>> ???????? || ________ || ________
>>> ???????? || ________ || ________
>>> ...      || ...      || ...
multiplied.core.template.build_noop(
char: str,
source_slice: Slice,
) → tuple[Slice, Slice][source]#

Create a No-op template slice with zero initialised slice and chosen char.

Parameters:

  • char (str) – Character to use for the No-op template.

  • source_slice (Slice) – Source slice to use for the No-op template.

Returns:

Template “slices” and resulting slice. Target row unaffected

Return type:

tuple[Slice, Slice]

Examples

>>> [slice-] || [noop--] || [result]
>>> ___0000_ || ___aAaA_ || ___aAaA_
multiplied.core.template.resolve_pattern(
matrix: Matrix,
) → Pattern[source]#

For a given matrix, progressively allocate CSAs then adders to pattern

Parameters:

matrix (Matrix) – The matrix to resolve the pattern for.

Returns:

The resolved pattern.

Return type:

Pattern

multiplied.core.truth module#

multiplied.core.truth.shallow_truth_table(
scope: Generator[tuple],
alg: Algorithm,
) → Generator[Matrix][source]#

Return Generator of partial product matrices for all operand tuples

multiplied.core.truth.truth_dataframe(
scope: Generator[tuple[int, int]],
alg: Algorithm,
) → DataFrame[source]#

Execute algorithm using each pair of operands from the scope.

Parameters:

  • scope (Generator[tuple[int, int]]) – A generator that yields pairs of integers (a, b) to be used as operands.

  • alg (Algorithm) – An instance of the Algorithm class representing the algorithm to be executed.

Returns:

A pandas DataFrame containing the truth table for the given algorithm.

Return type:

DataFrame

multiplied.core.truth.truth_multi_parquet(
dir: Path | str,
domain_: tuple[int, int],
range_: tuple[int, int],
alg: Algorithm,
workers: int = 4,
) → None[source]#

Generate a truth table and save it to a multi-part Parquet directory.

Parameters:

  • dir (Path | str) – Directory to store multi-part .parquet files

  • domain (tuple[int,int]) – The maximum range of values operands a and b can be.

  • range (tuple[int,int]) – Limit a and b to range_min <= a * b <= range_max

  • alg (Algorithm) – An instance of the Algorithm class.

  • workers (int=cpu_count()) – number of .parquet files to create in parallel

multiplied.core.truth.truth_scope(
domain_: tuple[int, int],
range_: tuple[int, int],
) → Generator[tuple[int, int]][source]#

Yields (a, b) from domain such that it’s product (ab) lies within range

Parameters:

  • domain (tuple[int,int]) – The maximum range of values operands a and b can be.

  • range (tuple[int,int]) – Limit a and b to range_min <= a * b <= range_max

Yields:

tuple – (operand_a, operand_b)

multiplied.core.truth.truth_table(
scope: Generator,
alg: Algorithm,
) → Generator[dict][source]#

A generator which yields all stages of an algorithm for a given set of operands a, b.

Parameters:

  • scope (Generator) – A generator which yields tuples of operands a, b.

  • alg (Algorithm) – An instance of the Algorithm class.

Returns:

A generator which yields all stages of an algorithm for a given set of operands a, b.

Return type:

Generator[dict]

Module contents#