PermutationOptimizerProcessor leads to improper split constraint

[arunkmv]

Hi,

While using 2D arrays with a spatial split constraint, I noticed the following issue.

When adding an incomplete spatial permutation, i.e. without specifying all the dimensions, along with a split constraint, the parsed processed output can be different than expected. If a dimension/factor is 1, then it is automatically inserted to the beginning of the permutation list by the PermutationOptimizerProcessor. However, while doing so, the spatial split constraint is not updated. This leads to an unexpected output and ultimately improper mappings.

timeloop-python/pytimeloop/timeloopfe/v4/processors/permutation_optimizer.py

Lines 35 to 41 in 1e2b963

	for c in constraints:
	for d, _, factor in c.factors.get_split_factors():
	if int(factor) == 1 and d not in c.permutation:
	c.permutation.insert(0, d)
	for d in problem.shape.dimensions:
	if problem.instance[d] == 1 and d not in c.permutation:
	c.permutation.insert(0, d)

Here is a sample input file to reproduce the issue:

The design uses a weight stationary 2D PE array to perform a "batched" 1D convolution. Batch size (N) is kept to 1 to trigger the issue.

architecture:
  version: 0.4
  nodes:
  - !Container
    name: System
    attributes:
      technology: "40nm"
      global_cycle_seconds: 1e-9

  - !Component
    name: MainMemory
    class: SRAM
    attributes:
      depth: 256
      width: 256
      datawidth: 8
    constraints:
      dataspace:
        keep_only: [Inputs, Outputs]

  - !Container
    name: PE
    spatial: {meshX: 3, meshY: 3}
    constraints:
      spatial:
        permutation: RP         # N is not mentioned in permutation list
        split: 1

  - !Component
    name: Register
    class: regfile
    attributes:
      depth: 1
      width: 8
      datawidth: 8
    constraints:
      temporal:
        no_reuse: [Outputs]
      dataspace:
        keep_only: [Weights]

  - !Component
    name: MACC
    class: intmac
    attributes:
      width: 8

problem:
  version: 0.4
  shape:
    name: Batched_Conv1D
    dimensions: [ N, R, P ]
    data_spaces:
    - name: Weights
      projection:
      - [ [R] ]
    - name: Inputs
      projection:
      - [ [N] ]
      - [ [R], [P] ]
    - name: Outputs
      projection:
      - [ [N] ]
      - [ [P] ]
      read_write: True

  instance:
    N: 1
    R: 3
    P: 3

mapper:
  version: 0.4
  optimization_metrics: [ last_level_accesses ]
  num_threads: 1
  algorithm: linear_pruned
  victory_condition: 1000
  timeout: 100
  diagnostics: True
  log_stats: True
  log_suboptimal: True
  live_status: False

mapspace:
    version: '0.4'
    template: "uber"

Here's the spatial constraint for the 2D PE array, after parsing and processing:

      - type: spatial
        permutation: NRP               # N inserted by PermutationOptimizerProcessor
        split: 1                       # Should be 2 for correctness
        target: inter_PE_spatial

Is the user expected to list all the loop dimensions in a permutation list when using a spatial split constraint? This does not seem to be intended behaviour, if I'm not mistaken. If so, I can work on a fix to update the split constraint as well within the processor.

Please let me know. Thank you for your efforts.

Cheers,
Arun