Re: [Gnucap-devel] [parallelism]

[al davis]

On Tuesday 04 March 2014, beranger six wrote:
> The PDF link : 
> https://www.dropbox.com/s/ogmazfro3wpbajo/answer_gnucap_diges
> t_88-1.pdf

I think you are making it harder than it needs to be and 
overlooking why/where it could be of benefit.

That sample matrix is not in the form you actually get.

The form you get is bordered-block-diagonal, possibly 
hierarchical.  By hierarchical I mean you will find a BBD form 
inside a block.

Blocks can be done in parallel with other blocks, then the 
borders must be done in the next pass.

In the netlist, blocks can be identified by subcircuit/module 
instantiations.  Borders can be identified by the next higher 
level and subcircuit/module calls.

The netlist node list is an adjacency matrix.

This stuff is available.  It will be faster and easier to use it 
rather than to try to extract that from the matrix.  By faster, 
I mean both faster to run and faster to develop.

Any block smaller that about 100 nodes is not worth decomposing 
further.  Just assume it is connected.

If you have a block that is big enough to split, the way to 
split is to look for ways to move nodes to a border.  This is 
the opposite of what traditional ordering methods do.

The block requirement for parallel is the same as for 
incremental update.

Global ordering takes at best O(n log(n)) time.  This is too 
slow.  The way to make it faster is local ordering and reuse.

Gnucap's ordering is non-optimal, but needs to stay early in the 
process.  It should be done before expansion.  That is one 
reason I never did anything with the post-expand ordering hook.