ggml : expose hash table API from ggml.c and reuse in ggml-alloc

[ggerganov]

#548 adds hash table implementation:

https://github.com/ggerganov/ggml/blob/a094d9c2db1d4cb64bbea3655032523dbc3c75c4/src/ggml.c#L16926-L16985

It should be exposed through the API and reused in ggml-alloc

[slaren]

I need a hash table in ggml-backend to map tensors between different backends, so I am looking into this. I don't think that this can be exported and reused as is, because it is not good enough to have only values of type void *, but that can be solved. However, I am not convinced that this should be shared in ggml.h, it will become part of the public API and inevitable someone will try to use it in their code. I have said this before, but I think we need to be more careful about what we expose in the public headers. This will also need changes after we implement dynamically sized graphs, so the API would change in the near future.

So I am not sure if it is worth to do this. Should we add a private header file for internal use within ggml only?

[ggerganov]

Sure, we should add an internal header (e.g.ggml-impl.h or ggml-util.h) in src. We can also put things behind #ifdef GGML_PRIVATE_API when we think a new header isn't really necessary, but we want to restrict exposure to the users. Eventually, we will hide all internal structs behind accessors. It's just that at the start it is easier to have the internals exposed and not think about what would be the best API. But as people start to rely more on ggml we will have to indeed be careful.

Btw, I'm still not really worried about breaking things in the ggml API, so if there are improvements that you see in ggml_cplan, ggml_cgraph, etc. , we should make them without hesitating about breaking other projects. Changes are still easy to adapt to at this stage. In llama.cpp and whisper.cpp we have more stable APIs since these are being used more intensively, so there it is already more difficult to break the API

[slaren]

if there are improvements that you see in ggml_cplan, ggml_cgraph, etc. , we should make them without hesitating about breaking other projects.

I am very concerned about breaking our own examples, especially the training examples depend very strongly on the internals of all of this. I think that the whole graph building code should be redesigned. I don't know how to solve every problem with dependencies, but I think a good start would be to automatically attach all the tensors created in a context to a graph, with an option to explicitly detach them. Currently we do the opposite, we create all tensor detached and then attach them with calls to ggml_build_forward_expand, and I think that that makes ggml harder to use. If we start from that, we may also conclude that ggml_context and ggml_cgraph could be unified. But I don't think any of this would be doable without introducing a new API version and slowly adapting all the code.

[ggerganov]

I don't know how to solve every problem with dependencies, but I think a good start would be to automatically attach all the tensors created in a context to a graph, with an option to explicitly detach them.

That's a good idea. I think it is totally doable. The order of the nodes of the graph will be determined by the order of creation (i.e. the order of calling ggml_xxx()), so we avoid having to compute the dependencies, so not only we will resolve the dependency problems - we would likely speed things up for small networks.

The graph construction where we traverse the children / parents is probably completely unnecessary. It was one of the very first features in ggml and it was an experimental approach. I can imagine some use cases where you could benefit from having the option to compute certain nodes based only on their dependencies, but for the majority of practical uses this is irrelevant.

Edit: Actually it is relevant for the backward pass, since in that situation you could have many extra ops that are not necessary for the calculation of the gradients that you are interested. So in this case, traversing the dependencies will automatically avoid any unnecessary ops.

Maybe we can think of a way to support both modes - would make the API transition easier too.

[slaren]

The backwards pass should always start from a loss, right? So I think in that case it is perfectly reasonable to start from the loss node and follow the parents to build the backwards graph. But if we have all the nodes somewhere, we may be able to add missing dependencies automatically. The typical case is the KV update:

ggml_cpy(ctx0, Kcur, ggml_view_1d(ctx0, kv_self.k, ...));

struct ggml_tensor * K = ggml_view_3d(ctx0, kv_self.k, ...);

struct ggml_tensor * KQ = ggml_mul_mat(ctx0, K, Q);

The ggml_cpy is completely disconnected from KQ, but if we have all the nodes we can figure that there is a dependency there and add it automatically. This is more what I am thinking about with this. Currently it is very easy to build a graph with several nodes disconnected, and I can only imagine that this is very confusing unless you know the internal about the way graphs are built in ggml. So I think we should find ways to simplify this.

[ggerganov]

Let me think some more about the backward pass.

The ggml_cpy is completely disconnected from KQ, but if we have all the nodes we can figure that there is a dependency there and add it automatically.

Why would we need to figure out the dependency? The operations will be executed in the order that they have been declared, so no need to find the dependency. I am thinking more that we will basically record the node order while constructing the graph, instead of trying to determine it by traversing the nodes post-construction.

[slaren]

For parallel execution we need to know all the dependencies. To minimize backend switches when partial offloading we may need to reorder the evaluation order, but we can only do that if we know all the dependencies. I assume that we also need to know the dependencies to build the correct backwards pass, but I don't know enough about that.

We may also be able to find the best evaluation order to minimize memory usage during training if we know all the dependencies.

[ggerganov]

The order in which we invoke the ops (A) + the existing dependency information through ggml_tensor.src (B) is enough to achieve all goals. We currently do not store the order (A) and therefore we have cases where we cannot figure out the correct execution.

If we start recording the order, it will add extra constraints: an op x invoked before op y cannot be executed after y. Note that this not mean that x and y cannot be executed together.

The KV cache update example would be trivially solved if we start recording (A) and apply the new constraints. The parallelisation can be achieved with an extra pass that analyses the graph and takes both (A) and (B) into an account. Same goes for the training use cases.

Having (A), we also avoid the ggml_visit_parents() traversal for trivial cases - when we don't care about parallelisation, reordering, etc. We just evaluate the ops directly as they have been invoked during the graph creation.

Let me know if you agree - is there any other use case that you think we might need to cover?

[slaren]

an op x invoked before op y cannot be executed after y. Note that this not mean that x and y cannot be executed together.

I think this should be "an op x invoked before op y cannot be executed after y if x is a source of y (*)". Otherwise this is a contradiction.

(1): or if a view of x, or a view with the same view_src as x, are sources of y.

[ggerganov]

How is it a contradiction - I mean that in the example above, ggml_cpy() cannot be executed after ggml_mul_mat() because it is invoked earlier - we can enforce this using the order of invocation (i.e. the order of calling the ggml ops).

[slaren]

The contradiction is that x must be executed before y, but at the same time x and y can be executed together. If they can be executed together, that must imply that the order of evaluation doesn't matter. Maybe I am misunderstanding what you mean by "executed together"? As it is, this restriction implies that every op must be strictly executed in the order that they are invoked.