4 ms·

Almost all problems have data dependencies as graphs rather than stacks. e.g. Sandwich = egg + bacon + bread All of egg + bacon + bread are almost always in

Almost all problems have data dependencies as graphs rather than stacks. e.g. Sandwich = egg + bacon + bread All of egg + bacon + bread are almost always independent, and can be computed independently. A graph a.k.a. a register architecture enables this independence to be represented So register architectures are more complicated, but usefully so

amelius 4y ago
Are you talking about parallel computation? Because serially: def sandwich(): egg() bacon() bread() is pretty much where stacks shine.
- tsegratis 4y ago
  Yes :) it wasn't the clearest example. But is also slightly hard to express I think superscalar architecture for hardware benefits from an explicit graph of dependencies. Then equally the user benefits from reduced need to convert the stack to a graph with SWAP DUP etc -- which is one way to think of the role of those operators (as a stack to graph conversion) On the otherhand some problems are unrepresentable by a graph, and easily represented by a stack; for instance map, reduce, and a bunch of others What I'm suggesting is that both the hardware and the user and arguably even the problem, generally prefer graphs
uticus 4y ago
> data dependencies as graphs rather than stacks... > ...A graph a.k.a. a register architecture... This is a new thought for me. What resources would you suggest to help me better understand how "register architecture" better supports modelling data as graphs? * edited for better formatting
- tsegratis 4y ago
  Maybe https://en.m.wikipedia.org/wiki/Use-define_chain https://en.m.wikipedia.org/wiki/Use-define_chain SSA form might be a clearer expression of this idea, since there variable assignments more tightly conform to the idea of nodes in a graph, since they are assigned to once, and so produce a clear graph of the whole program If we just looked at registers (rather than SSA variables), then register reuse for different values would be more complex, since then the nodes of the graph would mean different things as the register is reassigned (assuming we were going for that representation) Another way to think about it would be as relations. For instance assembly ops like MULT ADD can be seen as ternary relations, and as you join relations togother into an expression, such as a+b*c, you are forming a graph This graph like correspondence is used to good effect in BDDs and ZDDs, which use that correspondance to compress the representation of expressions Part of the reason behind this is because nodes of a graph are restricted in the same way registers are -- they are only refered to by name, never by an offset. Whereas for stacks, they are refered to by offset, never by name We could remove this separation by naming the top 16 (say) offsets of a stack. Then registers could be referenced by name and by an offset index This would allow lots of fun things. If at the software level, it could mean having normal named variables, aswell as #n offset variables. Which might be a great addressing mode for assembly too. It is done for main memory with Base+Offset addressing, but not for registers The graph equivalent might be Register Direct. Or others, but at this point we're expanding to think beyond registers to memory itself Another path you might like to explore could be the G Machine, or Spineless Tagless G Machine which (along with many other compilers) represents data as a graph, to ultimately convert it into registers

amelius 4y ago

Are you talking about parallel computation? Because serially: def sandwich(): egg() bacon() bread() is pretty much where stacks shine.

tsegratis 4y ago
Yes :) it wasn't the clearest example. But is also slightly hard to express I think superscalar architecture for hardware benefits from an explicit graph of dependencies. Then equally the user benefits from reduced need to convert the stack to a graph with SWAP DUP etc -- which is one way to think of the role of those operators (as a stack to graph conversion) On the otherhand some problems are unrepresentable by a graph, and easily represented by a stack; for instance map, reduce, and a bunch of others What I'm suggesting is that both the hardware and the user and arguably even the problem, generally prefer graphs

uticus 4y ago

> data dependencies as graphs rather than stacks... > ...A graph a.k.a. a register architecture... This is a new thought for me. What resources would you suggest to help me better understand how "register architecture" better supports modelling data as graphs? * edited for better formatting

tsegratis 4y ago
Maybe https://en.m.wikipedia.org/wiki/Use-define_chain https://en.m.wikipedia.org/wiki/Use-define_chain SSA form might be a clearer expression of this idea, since there variable assignments more tightly conform to the idea of nodes in a graph, since they are assigned to once, and so produce a clear graph of the whole program If we just looked at registers (rather than SSA variables), then register reuse for different values would be more complex, since then the nodes of the graph would mean different things as the register is reassigned (assuming we were going for that representation) Another way to think about it would be as relations. For instance assembly ops like MULT ADD can be seen as ternary relations, and as you join relations togother into an expression, such as a+b*c, you are forming a graph This graph like correspondence is used to good effect in BDDs and ZDDs, which use that correspondance to compress the representation of expressions Part of the reason behind this is because nodes of a graph are restricted in the same way registers are -- they are only refered to by name, never by an offset. Whereas for stacks, they are refered to by offset, never by name We could remove this separation by naming the top 16 (say) offsets of a stack. Then registers could be referenced by name and by an offset index This would allow lots of fun things. If at the software level, it could mean having normal named variables, aswell as #n offset variables. Which might be a great addressing mode for assembly too. It is done for main memory with Base+Offset addressing, but not for registers The graph equivalent might be Register Direct. Or others, but at this point we're expanding to think beyond registers to memory itself Another path you might like to explore could be the G Machine, or Spineless Tagless G Machine which (along with many other compilers) represents data as a graph, to ultimately convert it into registers