PIEO Trees for Fun and Profit

[anshumanmohan]

Sivaraman et al. claim that PIFO trees can handle non-work conserving behavior, and detail a mechanism that involves, for each node that desires non-work conserving behavior:

• A shaping transaction in addition to a scheduling transaction.
• A shaping PIFO in addition to a regular PIFO.

I'll let you work through the details in §2.3 of the paper, but the overall point is that a packet that is enqueued may not immediately be ready for popping. A quick description of their mechanism:

1. At push, the node's shaping transaction is run to determine when the packet will be ready. The packet gets enqueued into the target leaf but not into the ancestor nodes above it, violating Formal Abstractions' condition of well-formedness. The packet also gets enqueued into the shaping PIFO, ranked by the time computed for that packet by the shaping transaction.
2. The packet needs to bide its time in the leaf, essentially invisible to the nodes above it, until it becomes ready. When its time comes, it is dequeued from the shaping PIFO, references to it are enqueued into the its ancestors as usual, and the push is thus finally complete. Well-formedness is restored.
3. This finally makes the packet visible to the nodes above it and it can thus be popped as usual.

This whole thing is rather janky and was dropped from the formalism in Formal Abstractions. In particular, if you work through this carefully, you will notice that nothing actually shields this special packet from being popped by some previously enqueued downward reference in the tree! I have an email correspondence with Sivaraman where I confirm this using a little adversarial workflow.

My thesis is that:

• For each node that desires non-work conserving behavior, we should use a PIEO instead of a PIFO.
• If we do as I propose, we may just be able to use the tree-to-tree compiler from Formal Abstractions wholesale.

PIEOs instead of PIFOs

For each node that desires non-work conserving behavior, we should use a PIEO instead of a PIFO. Unrelated parts of the tree can continue to be PIFOs, but see my note below about ancestors of PIEO nodes.

This PIEO should use the predicate is_ready_at: time -> packet -> bool, partially applied with the current time. So is_ready_at time.now is indeed a predicate on packets. Caution, time.now is just an opaque thing I've cooked up; we'll need to make it more crisp.

Each ancestor of the PIEO node will also need to be a PIEO. These PIEOs store integer indices, and will need to use the predicate is_ready_at: time -> int -> bool, again partially applied as sketched above. For simplicity let's say the entire tree's non-work conserving nodes (leaves and internal nodes) use the same policy, is_ready_at: time -> int_or_packet -> bool.

Perk 1 of this approach are that we are always well-formed. Say a packet p_9 is enqueued at time 0. This packet is going to be ready only after time 9. This packet is fully pushed, all the way from the root to the leaf, by computing some path for it as described in Formal Abstractions. Wherever Formal Abstractions' scheduling transaction would have had us enqueue some index i into some ancestor node, we'll enqueue i_9, meaning that i will only be valid after time 9. No matter when you check well-formedness, this tree is well-formed. At time 0, it is well-formed but some coherent path is not going to answer to is_ready_at 0. At time 10, the tree is still well-formed and the entire tree also happens to answer to is_ready_at 10.

Perk 2 is the big one: packets that are meant to be invisible until some time actually remain invisible!

Compilation for Free

If we do as I propose, we may just be able to use the tree-to-tree compiler from Formal Abstractions wholesale.

This assertion requires a lot more thinking, but I have gotten excited by the possibility that a tree that is set up per my proposal will happily go through Formal Abstractions' compilation procedure! That is, we can create an topology-to-topology embedding f per §6, lift f to f-hat §5.2, massage things just a tiny bit more, and watch push and pop be preserved.

The lifting is, of course, the tricky part. Basically the existing lifting regime stretches insertion paths as needed to bridge over newly inserted transient nodes. Paths are stretched by dropping irrelevant path entires and duplicating some other path entries along with their ranks. The new lifting regime would similarly extend insertion paths, now duplicating path entries' ranks as well as their earliest dequeue times (9 in the example above) as needed.

[sampsyo]

This does make sense, and it seems quite promising! Like you, I haven't thought through the details of how the compilation would work, but it seems extremely plausible that it would. To summarize, a different way to put this proposal is:

• the entire tree is made up of PIEOs
• every entry in every queue (including both leaves and all internal nodes, including "transient" nodes) gets tagged with a "ready at" time
• we always dequeue by using pop-with-predicate, where the predicate is "packet's 'ready at' time is <= current time"
• for cases where we do not need work-conserving policies, enqueue packets with a "ready at" time equal to the current time, i.e., they are immediately ready (so the PIEOs degenerate into PIFOs)

Does that sound like an accurate summary?

Anyway, this is all to say it seems quite plausible and seems like a nice, clean generalization!

[anshumanmohan]

Yes, logically we could totally do it up such that work-conserving fragments of the tree are actually PIEOs, but with immediately-ready packets and indices! Just wanted not to require that, in case, at the implementation level, we learned that PIEOs with trivial filters are still more costly to lay out and run than PIFOs.

[sampsyo]

Yep, totally. The extremely silly distinction I'll make here is that a FIFO is a valid implementation of the interface "PIEO with an always-true extraction predicate." That is, following the spirit of allowing a lot of expressivity at the DSL/semantic level and then specializing in the implementation level, we could consider the system to be semantically PIEOs all the way down and then specialize to FIFOs when those PIEOs are used in a trivial way.

[anshumanmohan]

It's true! Very thrifty, I like it!

[KabirSamsi]

I really like this – I think if we can utilize the notion that all the structures we're looking for are just variants of a PIEO, this becomes very clean.

Perhaps here's what the hierarchy may look like? Just to crisp things up?

But then we should consider the question of how our fourth data structure, the PCQ (Calendar Queue) fits in with all of this. Digressing slightly from the topic of PIEOs, here's what I'm thinking:

Calendar queues are essentially lists of PIFOs. The width and current bucket pointer attributes add 'another dimension' of priority to the whole thing. So it follows that any PIFO should be able to be simulated on a Calendar Queue.

One issue, though, is that I don't think Calendar Queues can be simulated on a PIEO, since we can't achieve the 'rotate' functionality. So my diagram above would become rather odd, since we'd end up having two big sections (for PIEOs and PCQs), both of which can simulate PIFOs and by extension FIFOs.

However – since we can achieve the non-work conserving ability with PIEOs, is it worth considering whether we just go ahead with the PIEO $\rightarrow$ PIFO $\rightarrow$ FIFO model? And disregard Calendar Queues?

Sharma et. al proposes three packet scheduling algorithms which are best implemented on PCQs. I believe all three can be implemented with PIEOs (though I can look more into formal implementations), albeit they may potentially take a slight hit to time efficiency. But it may be worth it since we can cover an equal amount of ground with fewer structures.

[anshumanmohan]

Writing up an IRL discussion for the record.

This is a super helpful diagram, thanks! I feel your frustration re: trying to fit calendar queues in here and possibly even disregarding them if they don't fit, but I think it's all salvageable.

I think the diagram captures expressivity while calendarizing a queue is a matter of implementation efficiency. Yes, it's true that the calendar queues we've seen so far are just calendarizing PIFOs, but I see no reason why we can't also calendarize PIEOs and FIFOs, thereby sorta running up and down the hierarchy. If we do that, then calendarizing is orthogonal and complementary to your diagram.

The compiler may make decisions re: calendarizing based on capacity needs, for example. The compiler may say, "Whoa, you're gonna put up to 10,000 packets in this FIFO? I'll calendarize it into 100 'days' of 100 cells each". Or the compiler may say, "You only ever wish to put 64 packets in here? I'll just give you a straight and simple FIFO." Sorta how an industrial-strength array-sorting routine may actually run a cocktail of sorting algorithms under the hood based on the size of the array.

[polybeandip]

I've been thinking about formalizing PIEO trees (issue #19) and more broadly extending the math in the Formal Abstractions (tracker #17) along the lines @anshumanmohan describes above. This branch includes my (flawed) notes on this effort; relevant files: notes.tex and notes.pdf

I'd like to take this comment to describe the obstacles I've faced with issue #19.

Let's consider the following snapshot of a PIEO tree, with topology Node([✻, ✻]): that is, we have exactly one internal node and two leaves.

Fig 1: snapshot of PIEO tree

Just as with PIFO trees, we'd like PIEOs on leaves to contain packets while PIEOs on internal nodes contain pointers to their subtrees. Hence, the 1s and 2s in the root are pointers to the left and right children respectively, and the P_is each refer to distinct packets. We've colored these packets according to whether they satisfy a predicate f (the specifics of f don't matter): more explicitly,

f(P_2) = f(P_3) = f(P_4) = true
f(P_1) = f(P_5) = false

We want to come up with a way to color the 1s and 2s in the root PIEO that agrees with its children's colors. This way, the semantics of pop(pieo_tree, predicate) are straight forward. Simply do as we would with PIFO trees but pop each PIEO with predicate f:

• pop the root PIEO with predicate f
• if the root is a leaf, return the result
• otherwise, the result is a reference to a child with packet satisfying f; recursively pop this child with predicate f and return the result

This is the coloring we desire for the root PIEO of Fig 1.

Fig 2: snapshot of PIEO tree (with more colors!)

The key here is that the color of nth 1 (resp. 2) matches the color of the nth packet in left (resp. right) subtree.

So far, it seems like we have a sense for the kind of invariant we'd like to enforce, but how do we do it?

@anshumanmohan made a suggestion in the top-level post:

Perk 1 of this approach are that we are always well-formed. Say a packet p_9 ... also happens to answer to is_ready_at 10.

While his approach is specific to the is_ready_at predicate, it extends to quite naturally to general f. Essentially, when we push pkt, we add extra meta-data to any of the pointers we push to PIEOs on internal nodes. This way, the meta-data on pointers is what decides whether they satisfy f (i.e. what color they are).

Unfortunately, approaches like these, based around decorating pointers in internal PIEOs, don't work well. This is because a pointer to the ith child on an internal PIEO (or PIFO) will not always refer to the same packet in the ith child. Here's a concrete counter-example:

Fig 3: counter-example to meta-data strategy

Fig 3 is the result of pushing packet P_6 using the path (very_big_rank, 1) :: very_small_rank on to Fig 2. Notice how the second 1 in the root PIEO now refers to green packet P_2, BUT it's still red (since its color is determined by the extra data we decorated it with at enqueue). Further, if the white 1 and P_6 satisfy f, then popping with f removes white 1 and P_2; hence, there's a clear mismatch in the data held by pointers in the root and packets in the left child: no pointer is decorated with the data for P_6 and no packet contains the data that decorates the third 1 in Fig 3.

A few questions:

• Do we agree with my discussion of Fig 3?
• If so, do any ideas for fixing this issue jump out?

[polybeandip]

@sampsyo thank you for describing the semantics of push and pop in such detail; this was very helpful!

I have two minor nitpicks. First, regarding a potential typo. When popping internal nodes, we construct

the set of children whose minimum ready-at time exceed the threshold.

Instead, we'd want the children with minimum ready-at times below the threshold, correct? I ask because I've understood threshold to mean the time our pop takes place.

My next concern is that, by keeping track of only min_ts at internal nodes, we unintentionally depart from the semantics desired by the top-level post. More specifically, consider the PIEO tree below.

As before,

🟩 = satisfies the predicate
🟥 = does not satisfy the predicate

Since all packets in the left child are red, so should all 1s in the root. Similarly, the only 2 in the root should be green. Thankfully, our new semantics do just this!

Let's push a green packet P_5 via the path (very_small_rank, 1) :: very_small_rank.

Fig 1: post P_5 push

Now, the left child's min_ts is below threshold. Since this is all we use to determine the color of a reference, all 1s turn green: i.e. we obtain the coloring

as opposed to

If we were to pop the tree in Fig 1, we'd receive P_5 instead of P_4. This is perhaps strange because we pushed P_5 into our tree with small ranks at all internal and leaf PIEOs. Yet, it was still popped early because it could take advantage of the high ranks of its unripe neighbors from the same flow: P_1, P_2, and P_3.

A few questions:

• Do we agree my example here? I haven't misunderstood Adrian's recipe for push and pop, right?
• Is this departure from the top-level post all that important? I imagine setting our sights on specific NWC scheduling transactions to try and express via PIEO tree may make this clearer.

[anshumanmohan]

Thanks for a fascinating discussion! I have good news and bad news. And it's the same news: I don't see the problem! That is, I think the simple PIEO-only approach as suggested by the toplevel post will automatically and elegantly simulate what (to use this post's very helpful vocab) we are now calling a lazy internal policy.

The mantra to remember is that integer entries in internal nodes are child pointers, not packet pointers. I invite you to throw away any hope of tagging integers to packets and maintaining those tags as invariants. One, it is too hard; two, it is the wrong approach anyway. PIFO trees are powerful because of automatic target switching when it comes to packets. An integer index entry n simply says "I represent an opportunity for my nth child to propose the next packet".

In PIEO trees, we must generalize this a step further. Let's say we are at the root, r. An integer index entry n_10 is read like so:

• At time < 10, I am invisible.
• At time ≥ 10, I represent an opportunity for my nth child to propose the next packet.

We'll need to refer to r's nth child a lot, so let's call it Nora. In the pursuit of generality, I won't comment on whether Nora is a leaf or an internal node. By well-formedness, we know that Nora has some element in it, either a packet or a further index, whose value is opaque but whose readiness time is known to be 10, the same as n_10. Let's call this element x_10. Crucially, there may totally be some other element, y_9, in Nora. And even more crucially, y_9 may be ranked more favorably than x_10, such that the index n_10 in the root now points to y_9, not x_10. Some other entry in the root, n_9, points to x_10, because in the root n_10 is ranked more favorably than n_9 is. We have arrived at exactly the criss-cross @polybeandip was worried about here. The crucial point I am trying to make is that this is a-okay!!

Say no pop is called at time 9, and a pop is called at time 10. Then n_10 triggers the popping of y_9. Seems weird, yes, but is this not just the same as @sampsyo's lazy policy?

Well-formedness is the linchpin here, so a word about that.
At enqueue, the ripeness time of a packet and the ripeness times of all the integer metadata from root to leaf are not just determined from the same metadata, but are the same. We must insert some foo_t, bar_t, baz_t, ... pkt_t. These items will need ranks that will be determined à la Formal Abstractions. This means that when a packet in a leaf becomes ripe, a whole column of integer indices from that leaf to the root also become ripe in lockstep, and this preserves well-formedness.

Do let me know what you think! I am of course open to my funny lil original idea not working, but I wanted to give it one more chance to live because it is the simplest option by far!

[sampsyo]

This is at least mostly convincing to me! The counter-intuitive thing, of course, is that n_9 in the root points to x_10 in the leaf. So after popping once, we are left with n_10 pointing to y_9 (and x_10 is gone). This certainly looks weird because the root and leaf appear to disagree about the readiness times of the packet. But—correct me if I'm wrong—I think what you're saying is that this cannot possibly matter, because we are already at time 10, so all ready-at values ≤10 are equivalent at this point.

Now I am wondering how we would prove that this would work. We'd need to say something about the invariant that the PIEO tree maintains, right? And that invariant would definitely not be "the sequence of ready-at times in the root is equal to the sequence of ready-at times in the leaves" (since we have just seen how this fact can become false). It seems like the invariant would have to explicitly mention the monotonicity of ready-at times, maybe?

[sampsyo]

Also, sorry to be just catching up now, but @polybeandip's discussion here is also great; thanks for illustrating it in detail!

Instead, we'd want the children with minimum ready-at times below the threshold, correct?

Absolutely.

Do we agree my example here? I haven't misunderstood Adrian's recipe for push and pop, right?

Yeah, this does seem like exactly what would happen! And it does seem like a problem with my simple "min tracking" scheme, since it assumed that any child was equally viable. I guess I am hoping that @anshumanmohan is correct and we don't have to try to fix this?

[anshumanmohan]

Yes, I think we'll need something like Lemma 3.9 in Formal Abstractions. In the screenshot attached, turnstile is read "well-formed". The path $pt$ contains the ranks with which entries will be pushed into the respective PIFOs as we proceed from the root to the leaf.

In our PIEO tree, we'll have our extended definition of well-formed, and we'll extend paths to include a ready-at time that remains constant for all entries of a given path. In addition, the path-computing mechanism will need to be stateful so that it can guarantee monotonicity. Luckily scheduling transactions $z$ (see Defn 3.7) are already stateful, so I think we can just fold this monotonicity requirement into scheduling transactions!

[polybeandip]

For completeness and the benefit of others reading this, PR #35 (and issue #17) prove the compilation procedure here works!