rigetti / quil-rs

Quil Parser & Program Builder
https://rigetti.github.io/quil-rs/
Apache License 2.0
18 stars 9 forks source link

Reduce number of classical instruction edges in InstructionBlock::graph #350

Closed Shadow53 closed 4 months ago

Shadow53 commented 5 months ago

Copied from #324 with main merged in.


Per @erichulburd

The ultimate goal of this PR is to simplify the InstructionBlock::graph and thereby improve the ability of a hardware scheduler to schedule a Quil program by reducing the number of edges between classical instructions and block start/end.

Two types of edges in the InstructionBlock::graph are deemed extraneous in this work:

  1. An edge from two consecutive classical instructions that read from / write to different memory regions. Rather than insist on classical instruction execute in the particular order they are written in a Quil program, only represent ordering of classical Quil instructions based upon the memory regions they read and write to (this is already done with MemoryAccessQueue).
  2. Edges from BlockStart, if the node has other incoming edges, or to BlockEnd, if the node has other outgoing edges. Note that while this could apply equally to InstructionRole::RfControl, this change set deliberately only impacts edges to and from classical instructions.
DECLARE params1 REAL[10]
DECLARE params2 REAL[10]
DECLARE params3 REAL[10]
DECLARE params4 REAL[10]
DECLARE integer1 INTEGER[10]

LOAD params1[0] params2 integers[0] # LOAD_1 in graphs below
SHIFT-PHASE 0 "rf" params1[0]
LOAD params3[0] params4 integers[0] # LOAD_2 in graphs below

Old representation of InstructionBlock::graph.

flowchart TD
    BlockStart --> LOAD_1
    BlockStart --> SHIFT-PHASE
    LOAD_1 --> SHIFT-PHASE
    LOAD_1 --> LOAD_2
    LOAD_1 --> BlockEnd
    LOAD_2 --> BlockEnd
    SHIFT-PHASE --> BlockEnd

_In the original algorithm, there is an edge from LOAD1 to BlockEnd because there are pending reads on params1 and integers.

New representation of InstructionBlock::graph.

flowchart TD
    BlockStart --> LOAD_1
    BlockStart --> LOAD_2
    LOAD_1 --> SHIFT-PHASE
    LOAD_2 --> BlockEnd
    SHIFT-PHASE --> BlockEnd

There are three invariants of the InstructionBlock::graph that remain unchanged:

  1. There is always a path connecting the BlockStart to any classical node in the graph.
  2. There is always a path connecting any classical node in the graph to the BlockEnd.
  3. These invariants pertain to the BlockStart and BlockEnd as well. In other words, there is always a connecting path from the BlockStart to the BlockEnd regardless as to whether there are any instructions in the block.
github-actions[bot] commented 5 months ago

PR Preview Action v1.4.7 :---: :rocket: Deployed preview to https://rigetti.github.io/quil-rs/pr-preview/pr-350/ on branch quil-py-docs at 2024-04-18 14:27 UTC