Rethink the Addresser API

braised-babbage commented 2 years ago

The role of the addresser is to transform a source program (or part of a source program) into an equivalent form compatible with certain constraints indicated by the chip specification. In general, you may think of this as a function

(chip-spec, instr-list, options) -> (chip-sched, initial-rewiring, final-rewiring)

We might refer to the above as a 'nativizing' addresser, because the output is a chip schedule consisting of native (chip-supported) operations.

Proposal: Separate Addresser Initialization from Invocation

Currently, we support one general addressing scheme, greedy addressing, with variants along two primary axes: the choice of cost function (which is encoded via the specific addresser-state class),and the choice of swap selection heuristic (controlled via a global flag). There are some other small details of the addressing strategy that leak through (e.g. flags controlling the usage of 1Q queues). The addressing algorithm itself is mostly encapsulated by a FSM, but the state involved is nontrivial.

If we curry the above function, we see that it can break into two stages:

(chip-spec) -> (instr-list, options) -> (chip-sched, initial-rewiring, final-rewiring)

where

(instr-list, options) -> (chip-sched, initial-rewiring, final-rewiring) is the "addresser function", and should do whatever state initialization & cleanup is necessary to be invoked multiple times
(chip-spec) -> ... is the "addresser init function", responsible for constructing an addresser function.

compiler-hook could be parameterized by addresser init function, which it may only call once (to provide the chip spec, warm up state, etc) and then pass the instructions of each block to the resulting addresser function. It would not need to know anything about what parts of the addresser configuration are represented by choice of class vs other global defparam, caching or performance optimizations, etc.

Proposal: Add a notion of Non-Nativizing Addresser Passes

In practice, it may be useful to support notions of non-nativizing addressers; these would have the form

(chip-spec) -> (instr-list, options) -> (instr-list, initial-rewiring, final rewiring)

and could in principle be composed, as long as we knew how rewiring data from one maps to corresponding options of the other.

For example, the constraint-based 'qubit allocation' technique of https://arxiv.org/abs/2007.15671 could be used as a non-nativizing addresser which does the heavy lifting of placing operations, which the greedy addresser could subsequently nativize.

Note that non-greedy strategies can support different constraints than greedy ones: with the Tan-Cong approach one can request not just an initial rewiring but also a final rewiring, or even more obscure constraints on the layout (which may be relevant for specific devices or experiments).

Proposal: Addresser Initialization is Addresser Configuration

There are many qubit allocation techniques available; we should be able to experiment with them within quilc (even if this is handled via wrapping some C++ code for the actual task of addressing). There is still the matter of sanely propagating various settings to these specific addressing routines. I would suggest that, at least as a general goal, this should be entirely managed by the choice of addresser init function (using the language introduced above).

In other words, if we want to use the fidelity-addresser with 1Q queues disabled and A* search for swap selection, these settings should be requested by using a suitable init function. This might mean that for each broad type of addresser that there is another layer to the currying, e.g.

(addresser-specific-settings) -> (chip-spec) -> (instr-list, options) -> ...

so that one might do

(compiler-hook pp 
               chip-spec 
               :addresser-init-fn (configure-greedy-addresser 
                                   :state 'fidelity-addresser-state
                                   :enable-1q-queues nil
                                   :swap-heuristic :a*))

or something similar. The (configure-greedy-addresser ...) returns a function that takes a chip spec that ....

Some Caveats

Although I've argued for ordinary functions, perhaps a slightly different API is useful (so that e.g. we can look at something a bit more comfortable than a closure when debugging). This might mean that we have some generics like

(defgeneric make-addresser (addresser-init chip-spec)
  (:documentation "Construct an addresser from ADDRESSER-INIT, specialized for CHIP-SPEC.")) 

(defgeneric do-addressing (addresser instr-list &key initial-rewiring)
  (:documentation "Apply ADDRESSER to INSTR-LIST.

Returns (CHIP-SCHED, INITIAL-REWIRING, FINAL-REWIRING)"))

braised-babbage commented 2 years ago

I'm curious as to whether @ecpeterson has any thoughts / opinions / etc on this.

stylewarning commented 2 years ago

ecpeterson commented 2 years ago

I don't feel I have much to contribute to the discussion. When first penning the addresser, the possibility of inhomogeneous device features made it feel unlikely that we would be able to find good heuristics which were generally applicable, and I felt a little queasy at setting up a 'memory layout'-type problem that involved mapping nebulous, abstract objects onto concrete constraints.

These days I feel less strongly. Devices are actually relatively homogeneous, and the known decomposition routines often are entirely finesse-less and come down to "almost everywhere in the decomposition, you're going to need almost all-to-all connectivity", so you actually probably could have 'laid out' the abstract object and not missed much. So, from an algorithmic perspective, currying like this is probably fine. Maybe it's worth finding a couple of perhaps-not-so-distant cases to think about (e.g., links that support SWAPs only rather than universal computation) and establishing confidence that the proposal can still navigate those waters.

From a software engineering perspective, I'm still busy being grateful that we moved the addresser state out of defparameters and into an explicit object. With that as a baseline, it's hard to think carefully about these kinds of decisions — they all feel like icing. Someone newer / more involved may have more to say here.

In short, I'm in broad support.

quil-lang / quilc