#3 Improve run-time of JEdifCutset

[Keith Morgan]

"Finding FF Fanout Cutset..." takes a long time to execute, which is understandable. The annoying thing is that if you make a small change to your design and then run through the tools again, it takes just as long to execute. I don't know if this would be possible, but perhaps you could speed up the execution of subsequent iterations by emulating the Xilinx PAR "guide file" model. I believe it uses an old place and route file as the starting point for subsequent iterations of PAR. Perhaps you could do something similar. Perhaps you could save the old cutset to file and in subsequent runs suck in the old cutset as the starting point for the new cutset. Obviously you would have to get rid of cuts that don't exist anymore and then add cuts until you have a valid cutset again. Would that take longer than starting all over again? Just a thought.

[Brian Pratt]

My initial thoughts:

I think that we may be able to do that. It's been too long since I've been through that code to know for sure.

The cutset file we write out may be able to be re-associated with a different graph if the names match up, but Jon Johnson would know that better than me. He's been handling the serialization stuff lately. That would probably be the biggest hurdle. Then we'd just have to clean up the cutset like you suggested. We'd have to do the SCC decomposition all over again, but it may be faster since it would mostly be broken up. The rest of the algorithm would be skipped, pretty much, though, so that part should go fast. I guess it depends on what the slowest part of the algorithm was in the first place :-)

The only other thing is that you wouldn't get the same results as if you had started from scratch (at least not necessarily). Exact results aren't too big a deal, since part of the cutset determination is random anyway. But things like having multiple voters in a path, which the FF Fanout Cutset ensures that you don't have, wouldn't necessarily be true anymore. But if that's acceptable, then I think this might be possible, yeah.

-Brian