[P0] Consider the WAR memory access dependency in taskflow

[ShangkunLi]

Current memory access dependency edges cannot represent the WAR dependency.

We need to fix it in both convert-affine-to-taskflow pass and resource-aware-optimization pass.

[tancheng]

Current memory access dependency edges cannot represent the WAR dependency.

Why? I thought you mention we can figure our the memory access based on memref read/write, so then dependency should be recognizable?

[ShangkunLi]

Current memory access dependency edges cannot represent the WAR dependency.

Why? I thought you mention we can figure our the memory access based on memref read/write, so then dependency should be recognizable?

For the current taskflow.task definition, we can only figure out the RAW and WAW memory access dependencies, because there is only $write_outputs in the results of the definition. We need to enhance the definition with a $read_outputs to support the WAR dependency representation.

// Defines a uniform computation task operation within a Taskflow graph.
def TaskflowTaskOp : TaskflowOpBase<"task", [
    IsolatedFromAbove,
    AutomaticAllocationScope,
    AttrSizedOperandSegments,
    AttrSizedResultSegments,
    SingleBlockImplicitTerminator<"TaskflowYieldOp">
]>{
  let summary = "Computation task operation within a Taskflow graph.";

  let description = [{
    Represents a computational task that takes data inputs and produces
    data outoputs. Tasks are isolated from their surrounding scope and can only
    communicate through explicit data dependencies.

    Tasks has two types of inputs/outputs:
    1. Memory dependencies: memrefs that are read or written by the task
    2. Value dependencies: SSA values from producer tasks

    The `read_memrefs` and `write_memrefs` attributes record the actural
    original memrefs that this task accesses,
    enabling data placement analysis for multi-CGRA mapping.

    Example:
      // Memory inputs: %mem, Value inputs: %val
      $out_mem, %out_val = taskflow.task "Task_0"
        read_inputs(%mem : memref<4xi32>)
        value_inputs(%val : i32)
        original_read_memrefs(%arg0 : memref<?x8x6xi32>)
        original_write_memrefs(%arg5 : memref<?xi32>) {
      ^bb0(%a0: memref<4xi32>, %a1: i32):
        affine.for %i = 0 to 4 {
          %v = affine.load %a0[%i] : memref<4xi32>
          %sum = arith.addi %v, %a1 : i32
          affine.store %sum, %a0[%i] : memref<4xi32>
        }
        taskflow.yield memory_outputs(%a0 : memref<4xi32>) value_outputs(%a1 : i32)
      } : (memref<4xi32>, i32) -> (memref<4xi32>, i32)
  }];

  let arguments = (ins
    Variadic<AnyMemRef>:$read_memrefs,
    Variadic<AnyMemRef>:$write_memrefs,
    Variadic<AnyType>:$value_inputs,
    StrAttr:$task_name,
    Variadic<AnyMemRef>:$original_read_memrefs,
    Variadic<AnyMemRef>:$original_write_memrefs
  );

  let results = (outs
    Variadic<AnyMemRef>:$write_outputs,
    Variadic<AnyType>:$value_outputs
  );

  let regions = (region SizedRegion<1>:$body);

  let hasCustomAssemblyFormat = 1;
}

[tancheng]

umm, i thought we already have read_memrefs, WAR can be captured by check read_memrefs and write_outputs , no? I don't get read_outputs' semantic meaning..

[ShangkunLi]

umm, i thought we already have read_memrefs, WAR can be captured by check read_memrefs and write_outputs , no? I don't get read_outputs' semantic meaning..

read_memrefs and write_outputs can only be used to capture the RAW dependency (i.e., the write_outputs of task_1 is the read_memrefs of task_2). But for WAR dependency (i.e., the read of memref_1 in task_1 should occur before the write to memref_1 in task_2), so we should use read_outputs to stand for the read of memref_1 in task_1, and use this output in the write_memrefs of task_2. The edge enables the correct execution order between task_1 and task_2.

[tancheng]

Then what is the meaning of in write_memrefs?

[ShangkunLi]

Then what is the meaning of in write_memrefs?

For example, if task_1 and task_2 havea WAR dependency (i.e., memref_1 should be read by task_1 before it is written by task_2), we can represent the dependency like:

%read_output = taskflow.task read_memrefs(%memref_1) ...  // The %read_output has the same memref value as the %memref_1
%write_output = taskflow.task read_memrefs(...) write_memrefs(%read_output) ...

[tancheng]

oh, so write_memrefs is for WAR on write side? Then why there is no read_output in your example?

And what is the diff between read_memrefs and original_read_memrefs?

[ShangkunLi]

oh, so write_memrefs is for WAR on write side? Then why there is no read_output in your example?

And what is the diff between read_memrefs and original_read_memrefs?

There is %read_output in the task, which serves as the produced result of the task.

The read_memrefs and write_memrefs record the write and read for dependent memrefs. They are used for building the memory access dependency edge.

The original_read_memrefs and original_write_memrefs record the actual original memrefs that this task accesses, enabling data placement analysis for multi-CGRA mapping.

[tancheng]

I don't see %read_output in #277 (comment)

[ShangkunLi]

I don't see %read_output in #277 (comment)

I only show the current taskflow.task definition here. The %read_outputs is the component we want to add to support WAR dependency representation.

[tancheng]

I don't see %read_output in #277 (comment)

I only show the current taskflow.task definition here. The %read_outputs is the component we want to add to support WAR dependency representation.

Yes, but if we not yet add %read_outputs, why %write_memrefs is there?

[ShangkunLi]

I don't see %read_output in #277 (comment)

I only show the current taskflow.task definition here. The %read_outputs is the component we want to add to support WAR dependency representation.

Yes, but if we not yet add %read_outputs, why %write_memrefs is there?

Because we still need the write_memrefs for WAW dependency representation.