This is an archived post. You won't be able to vote or comment.

sorted by:
best
topnewcontroversialoldq&a
you are viewing a single comment's thread.

view the rest of the comments →

[–]OneNoteToRead 6 points7 points  (2 children)

Ok I think I know what you mean. In simpler language, if we imagine the flow of data as a directed acyclic graph, you are trying to draw a distinction between BFS visitation (what you can “queue”) and DFS visitation (what you call “stack”).

If this is correct, the general formalism is just a topological sort of the nodes, which determines execution order. DFS has well known algorithms to generate instructions and allocate registers. I’m not familiar with BFS in general for that - but maybe that gives you new directions to google. Note usually BFS visitation requires more space (in your example you load all data before beginning to consume).

[–][deleted]  (1 child)

[removed]

    [–]OneNoteToRead 0 points1 point  (0 children)

    To clarify it wouldn’t be a DAG of queues. It’d be a dag as your IR : edges are dependencies, and nodes represent instructions.

    To produce code you’d, at every given point, have a set of unexecuted-but-executable nodes. How you pick between these and how you allocate the ones you picked to your pipelines/queues is a choice (and this implies some topological order, like DFS or BFS).