Block-side Port Arrays

[ducky64]

Potential implementation

• LinkArray construct, that allows an arbitrary-length parallel array of links. It has ports that remap to the internal links. For example, if the internal link is a DigitalLink with src: DigitalSource and sinks: Array[DigitalSink] ports, the LinkArray would have:
  • superclass DigitalLink
  • (once fully elaborated) ports src: Array[DigitalSource] and sinks: Array[Array[DigitalSink]]
  • (once fully elaborated) constraints to connect array.src[x] <=> array.links[x].src and array.sinks[0][x] <=> array.links[x].sinks[0]
  • Its length is equal to the length of all of its ports (bidirectional propagation / merged construct). It is ready to elaborate when any port's length is known.
  • TODO: how should width inference be handled in the constraint language - or should it be a special construct? Can it work for a fully directioned constraint language - in this case, where are the constraint directions set?
• LENGTH ReservedParam, which can be used on a PortArray to get a Int type corresponding to the length.
  • This is the mechanism for width inference. This LENGTH parameter can both be a value source (eg, in a generator, get the actual length of the block's ports) and a sink (eg, set the length from a generator)
• ALLOCATE ReservedParam, which can be used on a block-side PortArray to get a fresh "slice" of ports of the array. Dynamic length (length propagates to the block), and can be connected to either an element port (single link connect) or array port (link array "parallel" connect). The PortArray's length is the sum of the length of all ALLOCATE operations. Any PortArray can either be connected as a whole, or piecewise with its ALLOCATEd components (but never both - mutually exclusive).
  • The motivating use case is a microcontroller's digital IOs, which might consist of a mix of known-width connects and unknown-width (at compile time, but resolved by parameter propagation width inference in the backend) connects, and to make that representable in the IR.

Alternatives

• Instead of an PortArray.ALLOCATE operation, perhaps something can be done with a make_array expression, eg connect(make_array(io0, io1), link.io_array). But this doesn't capture the microcontroller digital IOs use case well, and would also collapse the links from multiple connect statements into one mega link-array which could make visualization and debugging less intuitive.
• However, make_array might be a good for for link-side array allocation - instead of connecting block ports to link.ios, all the block-side IOs in the connection can be grouped into one connect statement. Potentially simplifies the Python fake-backend code.
• Even for (single) links with array-typed IOs (eg, DigitalLink's arbitrary-length sinks), it might be worth indexing them with ALLOCATE in IR to distinguish an element connect from a vector (parallel) connect.
• Is it worth having a separate ALLOCATE_ARRAY for a array-typed slice vs. an element-typed slice?
  • Might need to in the frontend (mypy) type system. Doesn't necessarily need to propagate to IR?

Mockup example

Motivating example: an abstract analog switch generator, that has n-bit AnalogSink inputs, 1 AnalogSource output, and log(n) (parallel) DigitalSink control bits.

System-level

Overview: the AnalogSwitch is connected to n analog sources at the top level (through n independent links), and a parallel log2(n) digital control line from the microcontroller. Width inference goes n analog sources -> AnalogSwitch generator runs -> defines its log2(n)-wide control line -> defines the microcontroller digital IO array length -> microcontroller generator runs

Frontend mockup

self.mcu = self.Block(Microcontroller())
self.analog_switch = self.Block(AnalogSwitch())
self.connect(self.analog_switch.ins.allocate(), self.analog_in0)  # single element link connect
self.connect(self.analog_switch.ins.allocate(), self.analog_in1)  # single element link connect
...
self.connect(self.mcu.digital_ios.allocate(), self.analog_switch.control)  # link-array connect

IR mockup

• Blocks
  • analog_switch: AnalogSwitch
  • mcu: Microcontroller
• Links
  • ctl_link: Array[DigitalLink]
• Constraints
  • Export: analog_in0, analog_switch.ins.ALLOCATE
  • Export: analog_in1, analog_switch.ins.ALLOCATE
  • Note: the length of analog_switch.ins is inferred from these two connect statements
  • Connect: analog_switch.ctl, ctl_link.sinks[0]
  • Depending on if (element) link port allocations are done in the frontend
  • Connect: mcu.digital_ios.ALLOCATE, ctl_link.source
  • Note: the length of mcu.digital_ios can be inferred after the length of ctl_link.source is known, which happens after the length of analog_switch.ctl is known, which happens after the analog_switch generator runs
  • Note: mcu.digital_ios.ALLOCATE can be used in other connections, eg blinky LEDs and tactile switches

Analog Switch Generator

Overview: the switch generator requires the length of the analog inputs to be known before it can run, and provides the length of the digital control line.

Overall Computation Flow Mockup

1. The three export connections define all the allocations to analog_switch.in
2. Aggregating them, the port-array is of length 3. Solver knows analog_switch.in.length=3.
3. With the analog_switch.in.length defined, analog_sw is ready to generate. Inside, it also defines analog_switch.ctl.length = log2Ceil(3) = 2 and instantiates those internal connections.
4. With analog_switch.ctl.length defined, the link array is ready to elaborate. All the ports on the link array are constrained to have the same length.
5. Elaboration runs, the effects aren't visible externally (since the length equivalence on all ports is defined in the link array, not a product of elaboration).
6. All allocations to mcu.digital_ios are knows, and the solver knows mcu.digital_ios.length = 2.
7. mcu can elaborate.

Syntax Mockup

Frontend skeleton (__init__) mockup

self.in = self.Port(Vector(AnalogIn()))
self.out = self.Port(AnalogOut())
self.ctl = self.Port(Vector(DigitalIn()))
self.register_generator(  # mockup API for generators that are dependent on directed constraints (eg, can only run after some parameter is resolved)
    prereqs=self.in.length,
    outputs=self.ctl.length,  # optional?
    self.generate
)

Frontend generate mockup

length = self.get(self.in.length)
self.ctl.set_length(log2(length))  # instantiates (and allows indexing into) array elements

# and in a concrete implementation, which connects the abstract interface to an internal chip
self.ic = self.Block(SomeAnalogSwitchChip())
self.connect(self.in[0], self.ic.in0)
self.connect(self.in[1], self.ic.in1)
# there would probably be logic to handle array length mismatches
...  # to n inputs

self.connect(self.out, self.ic.out)

self.connect(self.ctl[0], self.ic.ctl0)
self.connect(self.ctl[1], self.ic.ctl1)
...  # to log2(n) control lines

IR mockup (post-generate; pre-generate is not interesting)

• Blocks
  • ic: SomeAnalogSwitchChip
• Ports
  • in: Array[AnalogSink]
  • out: AnalogSource
  • ctl: Array[DigitalSink]
• Constraints
  • Export: self.in[0], self.ic.in0
  • Export: self.in[1], self.ic.in1
  • ... (note: link-arrays are not used, to allow the generator to intelligently resolve certain length mismatches between the interface and internal chip where the chip is oversized for the application)
  • Export: self.out, self.ic.out
  • Export: self.ctl[0], self.ic.ctl0
  • Export: self.ctl[1], self.ic.ctl1
  • ...

[ducky64]

Scratchpad

• With the current constructs, a block elaboration has no dependencies - once the block is visited, all its connections can be expanded immediately.
• Connections to array ports on links are two-stage: they start off as ALLOCATE, but are first aggregated by port, the ALLOCATE replaced with a concrete index, then the connect is expanded in-place.
• Array connections can by implicitly inferred (connection to a LinkArray) or explicit (separate connect_array construct)
• Should array exports be supported? And how? How would directionality of elaboration work?
  • Assuming a wrapper around a block which propagates length across two port arrays: this requires elaborating the inner block before the outer block is fully defined. When elaborating the inner block, IS_CONNECTED is known for all ports, but LENGTH is not.
  • How would port adapters work? Would either need a generator or some kind of block-array construct (and now we have array versions of everything; but semantically this probably behaves like a link array).
  • IS_CONNECTED is mainly used for generators (pin mapper) and assertions - probably not too many implications there.
  • In general, this is true for elaborating a generator block that deals with port-arrays - some ports lengths (mainly outputs) may be of unknown length.
• With block-side port arrays, array-array connects can't expand until the width is known - but currently, the connect isn't expanded until one port is known anyways because the port contents (eg, parameters) are needed.
• Ports may not be fully elaborated when the block is elaborated, since its length may be missing until internal connects or generates resolve. Does this break anything?
• ~Link arrays can't elaborate until at least one connected port's length is known. This creates an any-of dependency structure (propagation is bidirectional) - but can be implemented using the current DependencyGraph by the first port generating the LinkArray.LENGTH value, and subsequent ports checking that for consistency.~
  • LENGTH on the array-side should be propagated using (bidirectional) equality semantics.
  • LENGTH on the block-side should be propagated with user-defined unidirectional constraints.
  • ~Alternatively, there can be a port-specific length ElaborateRecord that is run once per Port, but the first one (per LinkArray) sets and subsequent ones check.~
• Generators: how should LENGTH work?
  • Do generators declare which length parameters to wait on? (probably yes - support arbitrary propagation rules)
  • When instantiating a generator, how should infrastructure handle input-length port-arrays vs. output-length port arrays? Options:
  • In the example, there is a set_length construct. On all declared lengths in the generator, infrastructure calls set_length; and for other ports, the user calls set_length.
  • Alternatively, it is up to the user to call set_length on everything. Once the generator returns, length is consistency checked (which must be done anyways). Problem: this may lead to LENGTH being double-declared, once in whatever was assigning to it, and again in generate set_length.
  • What if set_length is not called? The port still allows unknown-length array operations, but does not allow indexing.
  • set_length can be used in a normal block to declare a static array length. (would this ever be useful? alternatively, when should LENGTH be used - which propagates length but does not allow indexing)
• Potential invariant: a fully elaborated block must define LENGTH on all its ports. Abstract blocks may have undefined LENGTHs, but this create a compiler error (LENGTH missing, in addition to having an abstract block)
  • Non-generator blocks can define a static LENGTH, useful when overriding a more generic abstract block with undefined length.
  • Generators can depend on a LENGTH variable, but post-generation must define LENGTH on all its ports.
  • It is an error to have a wider connection than the block-side port supports. Unclear if the opposite should be an error (some block-side ports would be not-connected)

Implications for implementation

• ~Port elaboration must be handled separately from Block elaboration, since it may be gated by its LENGTH field.~
• ~Port elaboration only gates connect elaboration, because the parameters need to be known. Port elaboration does not gate block and sub-block elaboration, because generators in inner blocks may set output port LENGTHs.~
• In #63: LENGTH propagation should be handled separately from connect elaboration, but per the above potential invariant the port LENGTH must be defined no later than post-elaboration of the containing block.
• connect expressions are array connects if the link side is a link array (don't need to check inner block port - which may not have been elaborated yet).
• export expressions are array exports if the exterior port is a port array (similar reasoning as above).
• Weirdness to handle LENGTH propagation aside (since it's not directed), LENGTH is treated like any other parameter. IS_CONNECTED is orthogonal from LENGTH.
  • TODO: Should LENGTH propagation be directioned? What would it look like in the frontend?
  • Some idea of input LENGTH and output LENGTH port arrays?
• LENGTH defined on a port gates the port's elaboration, which in turn gates connect elaboration.
  • LENGTH must be propagated before connect elaborates.
  • LENGTH propagation is included as part of connect and export (in terms of IR semantics), just as IS_CONNECTED does not require a separate constraint. Internally, this will probably expand into separate parameter propagations.
• LENGTH of a port is set by the sum of all ALLOCATEd connections.
  • TODO: what are the difference between when ALLOCATE is used vs. when it isn't used? Is ALLOCATE semantically meaningful, or just fluff? Does it indicate directionality?
• Generators can be declared on a LENGTH parameter. For those ports, the generator infrastructure will automatically allocate ports so the ports can be indexed by the generator.
  • set_length can be used to allocate output-length ports within the generator. This can be used in non-generator hardware description (though probably isn't very useful - at least until we get semantics for width mismatch connects).
  • Note, set_length is only needed to get indexable ports. In general, collective operations that don't depend on the port array length (really only parallel port connects / exports?) are preferred where possible.

[rohit507]

• What exactly is ALLOCATE in the context of the protos?
  • Is it a constraint expression?
  • A reserved/special local-step?

[ducky64]

ALLOCATE is currently a ReservedParam LocalStep. It gets replaced with a named LocalStep during the compilation process. Currently, there aren't array connects, so the constraint is just rewritten, but with this proposed feature array connects will need to compile / lower into multiple single connects.

[rohit507]

From my end, the key question is: How do I have non-directional semantics for an ALLOCATE?

In the local-step case, it would mean making both paths and array-like elements slightly more symbolic. I'd also have to explicitly bound the max size of an array, which is going to be interesting.

Finally, is there any issue with non-contiguous indices on arrays on your end? If I generate a design where an Array has elements at [0,2,5,7] will it break anything? Or do they have to be contiguous and minimal [0,1,2,3]? The former would make my implementation a bit simpler, and I'll be doing it regardless for an initial pass (since we don't plan to pipe things back from my solver) but it'd be something for me to keep in mind.

[ducky64]

What do you mean non-directional semantics for ALLOCATE?

There shouldn't be any issues with non-contiguous indices, I believe the current compiler is set up to handle arbitrary indices, though generates contiguous and minimal indices when rewriting ALLOCATEs.

[ducky64]

Rough roadmap:

Part 1 - Allocate support

• Open questions
  • Should block elaboration (in the static refinement case) be gated on connects?
  • Idea: blocks must fully define port array sizes on elaboration - there are no dependency issues. Length checks can be performed post-elaborate or as part of design validity checking. Over-connects are always invalid, but under-connects can be valid if optional is set.
  • It is an error to have a connect statement to a nonexisting port, but it is not an error (non-optional-ness aside) to not have a connect to a port array element - consistent with existing semantics
  • Generators remain consistent in that they can ask for the incoming connections pre-generate. Afterwards, they are fully-defined.
  • Otherwise, length / elements propagate like any other parameter.
• Add frontend changes to support these
• Unit test that the proto is expected
  • Test allocate-to-array connect (example use case: micro pin assignment, connecting to dynamically-sized ports eg n-ported analog switch), using existing (individual) connect constructs and individual links.
  • Test individual ports (inner) to array (boundary) exports.
• Compiler unit tests for array connect expansion
  • Array-to-fixed refinement (eg, N:1 analog switch refined to a 2:1 analog switch - at least if N <= 2)
• Write compiler support - expand array connects
  • Main change: allocate can be on both block and link ports, and array suballocates can be a thing
  • Array suballocates may be a parameter dependency, so now connect expansions, connect constraint expansions, and array definitions now need to be part of the dependency graph.
  • Blocks can still elaborate anytime, since they either define array lengths statically, or dependencies are encoded in generators.
  • Create a port array dependency target, that fires (defines the port array elements) once all the elements have been allocated. Links would be gated on this (all link-side port arrays must be defined), generator dependencies could be gated on this. Link arrays (in a separate part below) would be handled separately to allow propagation.
  • Connect lowering (from an ALLOCATE to a concrete index) is handled independently of the block and without knowledge of the size of elements on the block-side port array. Implications:
  • The connect lowering name assignment and port-array name assignment for non-named ports must be consistent. Currently, this is divided between the compiler (connect lowering - depends on block expansion) and HDL (concrete array element / length initializer)
  • As a result, array elements are effectively interchangeable (which is fine, arrays should mostly be a grab-bag kind of thing).
  • Naming can be used to pass data from outward-in, but not the other way around.
  • Note: the dependencies look like (combined with not-connected behavior):
  • Aggregation (find all connects to an array) -> width resolution (find length of all elements connected to an array - mainly for array connects below) -> generation (may depend on elements connected to a port array) -> block (defines the port array elements)
  • Connect lowering (ALLOCATE to a concrete index) -> is-connectedness "available" (a short circuit case is needed for generators depending on is-connected)
  • This proposal uses width resolution -> connect lowering -> is-connectedness available -> generation, which is nice and linear
  • An alternative would be block -> connect lowering, so the connect ALLOCATE can be based on the block port array elements as defined on the block (a true ALLOCATE). But this adds complexity (connect lowering delayed further, need short circuit path into generate dependency for port array elements, need some unknown way to deal with not-connected available for array elements)
  • Connect expansion would be gated on both arrays being defined - since that is needed to allocate the element name.
• ~End to end tests, as expansion of unit tests above~
• Milestone: N:1 voltage source merges, refactoring examples to use these

Part 2 - Generator Support

• IR changes
  • Named allocate structure, refactoring through existing code
  • Determine semantics of named allocate - would likely only matter for generators that can be 'reactive' to requested names? Named allocate on non-generator blocks / non-'reactive' ports would be an error (fails noisily - discards user data).
  • Named allocates would only propagate into generator array element dependencies?
• Design and build frontend API for arrays on generators
  • How can generators declare which ones are input arrays and which ones are output arrays? Perhaps port-array elements in the generator that map to arrays of names in the generator function?
  • How can generators handle outputs? Perhaps just as collections of leaf-to-array export, minus input arrays?
• Compiler support for arrays on generators
• Milestone: Refactor microcontroller pin assignment utility
  • Refactor examples to support this new style

Part 3 - LinkArray Support - this requires propagation of length (or elts) as an parameter in the compiler, across LinkArrays

• IR changes (2)
  • Add array_export and connect_export constructs
  • Add ALLOCATE_SUBARRAY?
• Add frontend changes to support these
• Unit test that the proto is expected
  • Test array-to-array connect (example use case: m-bit Digital control lines to micro pin IO), using new array-connect constructs and the link-array construct
  • Are array-array exports needed? Potentially to support the adapter pattern?
• Write compiler support - expand array connects
• Compiler unit tests for array connect expansion
• End to end tests, as expansion of unit tests above
• Milestone: N:1 analog switches (as an abstract base type, plus refinements of concrete SPDT switches)

Part 4 - Maximum Fun

• Can some kind of array map-extract support in ports be used to have the SPI bundle be entirely self-contained? So the SPI link would have a Digital array on one side (the entire bundle of CS on the host side) while each SPI device has its own CS line as part of the bundle (as opposed to CS being a completely separate Digital line)

[ducky64]

So it turns out that this still needs more through to deal with hierarchy.

There's good use cases for elements / length propagation in both directions of hierarchy (root-inward, and leaf-outward):

• root-inwards: used where the connections define the ports, for example with links or an abstract microcontroller
• leaf-outward: used for wrappers around an internal block that defines the IO, for example if we wanted to wrap the control pins on a N:1 analog switch - we want the wrapper ports to inherit the ports of the inner block

However, the current compiler structure has ports fully defined when elaborating a block. Leaf-outward elements propagation means that the port's elements can't be known until the inner block is elaborated - so the port-array can't be fully elaborated until the inner block is fully defined - possibly even several levels inward.

Possible solutions:

• Give up leaf-outward elements propagation. This would severely limit wrapper classes and the use of adapters. Highly not recommended.
• Support intermediate port arrays that are undefined (intermediate port arrays forward elements bidirectionally without elaborating ports explicitly). Poor conceptual integrity with the rest of the system and poor debugging support (since these empty ports would look weird when directly visualized), so not great.
• Support delayed elaboration of port arrays - not tied to their containing block. Complicates the compiler, but is probably the lesser evil?

If taking the delayed elaboration of port arrays approach:

• Elements propagation can be handled by the current parameter propagation system. Port elaboration would be a dependency on the elements parameter.
  • Propagation would be explicitly directioned, at least across hierarchy levels. Port-array elements could either:
  • In the case the port-array (as a whole) is exported from an internal port-array: by determined by external connections (propagate elements inward), or be determined by the internal port (propagate elements outward)
  • In other cases: be undefined (for abstract parts - which must be refined) or be explicitly defined (either statically or as a generator - the generator is required to handle port arrays defined by external connections)
    • Exception: link-side port arrays can be defined by external connections without generators - since their ports are empty (do not need parameters)
  • Propagation through link-arrays would be by bidirectional equality.
• In somewhat abstract terms, port arrays would be a way for parameters to define interfaces.
• Decent conceptual integrity, since this integrates into the parameter propagation system instead of being its own thing
• Risk of dataflow spaghetti
• Potential interplay issues with not-connected as generators parameters, but the idea will probably just be to explicitly not support those cases. They may be fundamentally impossible and nonsensical (ask for not-connected on a port-array that is defined by the generator).
  • Potential defining line: only support not-connected on top-level generator ports.