I keep looking out for interesting examples of parallel software, and there is constant trickle of these. This past week I spotted a couple of new ones in the EDA field: SPICE simulation and chip timing analysis.
Mentor Graphics Olympus-SoC
Richard Goering at SCDSource has a good write-up of a recent announcement from Mentor Graphics on a parallelized version of the Olympus-SoC tool suite for timing analysis. The best bit is the description of how they found parallelism in what used to be a serial program: they went down to very small components of the overall computation, and did a data-flow analysis to find independent atomic units to compute on in parallel. Here, fine-grained is the key to finding lots of parallelism, while using larger units does not work as well.
Qouting the article:
“If you don’t work at the atomic level, it is very difficult to come up with tasks that are not dependent on each other,” Srinivas said. “We collect a lot of tasks, and we just keep all the cores busy all the time.” The goal, he said, is “minimal starvation” so that individual CPUs are not starved for tasks.A key technology that makes this possible is what Mentor calls “pin levelization.” With this approach, each node is assigned a level number. If another node has a higher number, there is a possible dependency. Pins at the same level, however, are independent, and their tasks can be collected together into one heterogeneous chunk.
Go read the rest of it for nice illustrations and more background.
Gemini SPICE Simulator
Daniel Payne at Chip Design writes about another fast SPICE simulator. Not as much detail here, but very nice graphs from the Gemini marketing folks. Not that they could not have been done in 2D with better information density, though. SPICE simulation would seem to be fairly parallellizable, which is not too surprising, considering the inherent parallelism of the domain. But as always, implementing a program to take advantage of such domain parallelism can be harder than expected if you did not do it from scratch. Which is what the Gemini people did, apparently.