Question trying to understand the reuse keyword for architectures

[timzonb]

Summary

I am trying to use the reuse keyword, but cannot explain the results with a simple mental model. I have 2 examples that will show this difference.

Currently I understand the reuse keyword as something that controls how einsums are allowed to be computed on a specific architecture. I have used 2 mental models to explain the results:

• Mental model 1: Reuse means that each sub component must reuse the same value. So for an input of [1, 2, 3], all components must first use 1 for the first cycle, then all components use 2 for the second cycle, and last all components use 3 in the final cycle.
• Mental model 2: Reuse means that each sub component must reuse the same tensor, but has a different index. So for an input of [1, 2, 3], and a fanout of 3, the first component uses 1, the second component uses 2, and the last component uses 3. This can all the be done in the same cycle.

My Setup

Cachyos (7.2.0-1-cachyos)
Python 3.12
Accelforge 1.0.484
islpy-barvinok 2025.2.5.post1

Example / Mental model 1

I have tried to experimantally figure out how the reuse keyword works. This is with the following configuration:

workload: # vector matrix multiplication
  iteration_space_shape:
    i: 0 <= i < 4
    o: 0 <= o < 1
  bits_per_value: {All: 4}
  einsums:
    - einsum: "Output[o] = Input[i] * Weight[i, o]"
      renames: {input: Input, output: Output, weight: Weight}

arch:
  extra_attributes_for_all_component_models:
    tech_node: 22e-9 #22 nm
  nodes:
    - !Memory #main memory that does not limit the architecture
      name: MainMemory
      size: inf
      leak_power: 0
      area: 0
      actions:
        - {name: read, energy: 0, throughput: inf}
        - {name: write, energy: 0, throughput: inf}
      tensors: {keep: input | output | weight, may_keep: All}
    - !Container
      name: container
      spatial: #Only one of these is enabled for each test
        # - {name: reuse_output, fanout: 4, reuse: output, min_usage: 1}
        # - {name: reuse_input, fanout: 4, reuse: input, min_usage: 1}
    - !Memory # a memory that can only hold a single weight value
      name: Bit-Wise Multiplication Registers
      component_class: sram
      tensors: {keep: weight}
      size: 4
      extra_attributes_for_component_model:
        width: 4
        depth: 1
        n_rw_ports: 1
        n_banks: 1
    - !Compute
      name: FreeCompute
      component_class: Dummy
      enabled: len(All) == 3

There are 2 commented lines in the architecture, I enabled only one for each test. This generated the following 2 images:

Reuse on Output mapping:

Reuse on Input mapping:

Mental model 1 explains these 2 images clearly. We can see that if we reuse on the input, the workload is run sequentially. This since each component must use the same input value, thus since we only have 1 output value, we must compute the output in 4 cycles.

If we try to use mental model 2 to explain the results, we cannot do that. Since if we reuse on the input, then we would expect that it could have been computed spatially. This since each component uses a different input index, but the same tensor. Since this does not happen, mental model 2 must be wrong.

Example / Mental model 2

Looking at the "basic_analog.yaml" architecture in the cim examples (truncated to only relevant section):

  # Each column stores a different weight slice. Columns share inputs.
  - !Container
    name: Column
    spatial:
    # ARRAY_COLUMNS suffix used for used for counting the array size
    - name: column_ARRAY_COLUMNS 
      fanout: 32
      # Note: may_reuse here and not reuse because we may have columns that reuse some,
      # but not all, input values, so we want reuse to be optional and only for inputs.
      may_reuse: input
      min_usage: 1
      # n_weight_slices columns work in parallel to perform the computations for each
      # weight. Each column holds a different slice.
      usage_scale: n_weight_slices

  # Each row receives a different input slice. Rows share outputs.
  - !Container
    name: Row
    spatial:
    # ARRAY_ROWS suffix used for used for counting the array size
    - name: row_ARRAY_ROWS
      fanout: 32
      reuse: output
      min_usage: 1

  - !Memory
    name: CimUnit
    .........

  - !Compute
    name: FreeCompute
    component_class: Dummy
    enabled: len(All) == 3

Basic analog image, also used in the notebook to explain the architecture:

We can see that a row reuses the output. But if we use mental model 1, then we must use the same value of output across the row, but that is not the case. We reuse the same input value. So the first mental model does not hold for this example.

Mental model 2 does work for this example, since across each row, we do reuse the same output tensor with a different index for each sub component. The same logic holds for the column, we do not reuse the input value across a column, but we reuse the input tensor across the column.

Question

We now have seen 2 examples where both mental models contradict. For example 1 only mental model 1 works, but for example only mental model 2 works. Both seem to be incorrect, but I cannot figure out what the actual correct way is of thinking about the reuse keyword.

Could you explain where I have made a mistake?

Thanks in advance for helping me with this question!

[tanner-andrulis]

Thank you for the thoroughly-researched question!

One gotcha that is happening is that the reuse and may_reuse keywords apply across instances of a leaf, not within a leaf, a leaf having a spatial keyword creates multiple instances of that leaf. With that in mind, the correct mental model is 1, but with a slight change:

Reuse means that each sub component must reuse the same tile. So for an input of [1, 2, 3], one possibility is for all components to first use 1 for the first cycle, then all components use 2 for the second cycle, and last all components use 3 in the final cycle. Another possibility is, for an input of [1,2,3,4], all components use [1,2] in the first cycle, then [3,4] in the second cycle.

Under this interperetation, Example 1 is correct. For Example 2, there are 32 Columns, and we may reuse inputs across different columns**. Each individual Column receives the same tile of inputs [1,2,3]. Then, within each column, there are 32 Rows. In the first column all 32 rows generate the same output value $\alpha$, in the second column all 32 rows generate $\beta$, and in the third column $\gamma$.

Let me know if this makes sense and/or you have any other questions!

** There is an interesting reason for the may_reuse keyword here. "reuse" says that values must be reused, while "may_reuse" says that the hardware exists to reuse values, but it is OK if we decide to send different values to different columns. This can be useful specifically in CiM accelerators running convolutions, where we unroll the convolution (Toeplitz transform) directly in the array. After this transform, each input value goes only to a subset of the columns, so "reuse" forcing all the columns to use the same inputs would be over-restrictive. In general however, you should use "reuse" because it'll make the mapper faster because it then only needs to explore options that reuse.