Parallel transformations tree update

The Problem for GPU

Since each tree in the forest must have its pre-requisite ancestor nodes processed first, as you noted, the tree-in-forest becomes the basic unit of parallelisation.

Without a fixed / similar topological structure for every tree in the forest, conditionals are needed (in shader code) to determine each tree's structure on the fly. This leads to non-parallel processing per tree, and would thus work better on CPU.

One possible solution for GPU

Decide on some maximally-defined tree structure, and then for certain trees, use null nodes, thereby clipping off some topology uniquely per tree. You'd write code specifically to operate on that maximal tree structure (say 1 root, 3 nodes at depth 1, etc. - specifically), no conditionals. The same amount of geometry would be rendered, but some branches etc. would simply be degenerate (taking up zero volume) due to the null nodes specifying them.

This has an increased chance of cache misses, due to the expanded (non-sparse) data for each tree; but this may be acceptable. Your choice of maximal tree size is going to be critical to the performance of this solution. Too large and you'll have too many cache misses; too small and your trees won't look so great or be particularly varied.

Either way... GPU or CPU

every single matrix update depends on another matrix somewhere back in the array and we have to know it's already updated

So you need a parent node to always appear before any children in that tree's linear list/array, so that it has already been processed within this running kernel instance, and thus guaranteed to have been run, by the time you reach its descendants. Try a depth-first, pre-order traversal of each distinct tree in the forest. To give you some idea of how to order this way (pseudocode):

int addToBuffer(TreeNode node) //returns the number of descendants
{
    //anything called here is pre-order...
    dataBuffer.append(node);

    //recurse
    int descendantCount = 0;
    for each (child in node.children) //or however you need to do this
    {
        descendantCount += addToBuffer(child);
    }
    
    //...anything called here is post-order (nothing in this example)
    
    return descendantCount;
}

int startIndex = 0;
int descendantCount;

foreach (treeNode in forest) //each treeNode is the root of a tree
{
    descendantCount = addToBuffer(treeNode);
    Rande range = new Range();
    range.startIndex = startIndex;
    range.length = descendantCount;
    rangesBuffer.append(range);
    
    startIndex += length;
}

Each tree's individual linearised data is pushed back-to-back into a buffer, and we have a second buffer containing Ranges i.e. start/end index tuples for each, pointing into the first buffer. Each kernel instance is then spawned given the offset i.e. start and length, and the dataBuffer itself.

Optional: To find specific ID'ed nodes in this list after having inserted them, you'd need a third buffer or array, which would be a lookup table (LUT) of indices keyed by ID.

If you end up doing this on CPU & single-threaded only, then you can also get away with ordering purely by increasing depth across the entire forest, which is simpler. (see level order traversal). EDIT: For reasons of data locality, this is probably a worse idea than simply processing each individual tree from root down.