qat.experimental.dialect.pulse.transforms.timeline_normalization module

Implements a pass that operates on pulse level dialect IR, and resolves Synchronize operations into Wait operations where it can.

A synchronization can be resolved into waits using the following algorithm:

  1. We add up the accumulated times for each frame in the synchronization up to that point.

  2. Take the maximum over those accumulated times.

  3. Subtract the elapsed time from the maximum to determine the wait time.

  4. Wait (do nothing) on that frame for the wait time, bringing all frames in line.

The pass works by walking through the IR and tracking the temporal relationships between frames, and when it encounters a Synchronize operation, it resolves them using the above algorithm if the relationships are known.

Operations might be encountered that affect frames and the scheduling semantics of frames but in a way that is unknown. In that case, we lose all temporal relationships for the affected frames, which results in subsequent synchronization operation(s) not being resolvable. We do this conservatively; any unknown operation with a body (region(s)) invalidate temporal relationships for all frames, as we do not have context to understand the meaning of the region (and if it applies to all frames). For operations without a body that consume frames, we just invalidate the relationships of those frames.

In practice, the way we track temporal relationships is through “domains”. Domains contain frames as members. They are relative to a temporal “anchor point” that frames have an accumulated time relative to. Frames are added to and removed from domains as needed. Frame membership has the following rules:

  • Frames in the same domain have a known temporal relationship to each other, and can be synchronized explicitly with padding and known time expressions.

  • Frames in different domains have no known temporal relationship to each other, and cannot have synchronizations resolved between them. Instead, the frames in the synchronize are moved into a shared, new domain, and the synchronize is left unresolved.

  • Operations with unknown semantics move respective frames into new domains, one for each frame.

The temporal relationships are tracked via expressions over time SSA values. During analysis, we build up symbolic expressions for the accumulated time for each frame, but do not create operations immediately. This is because, in some cases, those expressions need not be materialised (e.g. if there are no subsequent synchronizations, or if synchronizations destroy the temporal relationships). When we do need to materialise those expressions, we insert them into the IR, at the position they’re calculated from (e.g. addition of times due to a pulse is inserted next to the pulse op).

When any expressions are need to be materialised, if not done already, we add the operations that represent those expressions to the IR at the position where the analysis calculated the expression. Any synchronizations that can be resolved are replaced with Wait operations, with operands that point to those expressions.

This pass isn’t yet robust to multiple blocks, as we need a more comprehensive analysis method that does fixed point analysis between strongly connected components to understand the temporal relationships between frames across blocks. For now, we just raise an error if we encounter that situation, but eventually, we need to handle that too. This works fine in a world where control flow is represented entirely in high-level representations, e.g., structured control flow, but not in an unstructured regime. COMPILER-1224

Additionally, as support for control flow (COMPILER-1225) and function calls (COMPILER-1226) on pulse-level programs is added, we’ll want to add specific support for those constructs in this pass, as they have well defined semantics that we can leverage.

class TimelineNormalization

Bases: ModulePass

Resolves Synchronize operations into Wait operations where possible by analyzing temporal relationships in program control flow.

This is a best effort pass, and might not be able to resolve all Synchronize operations but can help reduce the number of Synchronize operations in the IR. Resolving synchronizations is important for reducing latency overhead, and not all hardware supports synchronizations.

The following considerations are taken during timeline normalization:

  • Frames defined by a CreateFrameOp are treated as time zero within the scope they’re defined.

  • Frames that enter a block via block arguments have no assumptions on time, and the timing of the frames are treated as unknown.

  • Operations with regions are conservatively handled. For non-isolated operations we invalidate tracked frame relationships before visiting region bodies.

  • Isolated region operations are analyzed with a fresh tracker so they do not affect outer frame facts.

  • Unknown operations that consume frames are assumed to have unknown scheduling semantics, and all consumed frames are treated as having unknown timing after that operation.

Warning

Region scheduling semantics are handled conservatively. This pass currently does not model detailed interleaving costs for general control-flow constructs.

apply(ctx, op)
Return type:

None

name: ClassVar[str] = 'pulse.timeline-normalization'