Large Network Iterations - Parallelism?

I am writing an algorithm to measure the robustness of a large network under independent attacks. The network has around 2000 nodes and it faces 10^8 attacks. Initially I implemented my soution in Matlab, but too many iterations(10^8) didn't work out. Every iteartions tries to rewire the network by improving robus开发者_如何学JAVAtness.

The problem with simple parallelism is that everytime the network gets rewired the new iterations works on the rewired network.

I am not sure how to achieve a high degree of parallelism here in order to run my algorithm efficiently. Currently with no parallelism I belive it will take about 1477 days.

Each iteration is taking about 1.25 seconds. (about 4 billion clock cycles) That sounds like a long time, there must be some opportunity to optimise what you are doing and reduce it to milli-seconds. Optimising code can often improve performance greater than parrallelising it can. (as parrallelising code is limited by the amount of free hardware you have and the overhead of having co-ordinating multiple CPU/systems)

How much hardware do you have? If your process is CPU bound, you will make the application at most N times faster if you have N CPUs.

Say you have enough hardware e.g. 2048 CPUs to play with and taking 1 day is acceptiable. Instead of assuming you need to have a completely faithful end to end test, you can start the network in different random/likely configurations. Run 10^5 attacks on each network independantly and check your end state closingly matches a starting state of another run. i.e. you could notionally join the results together end-to-end.

Depending on how much memory you need you may find tower servers are the most cost effective.

You can buy a server with a Xeon Quad 2.5 GHz and 4 GB of memory for £354. Thats a lot of power for the money.

However if you have access to an existing resource you may be better off. e.g. do you work for a company that has 1,000 desktops which are not used over night. ;)

The way you formulate the problem, there seems to be no way to parallelize the iterations. Also, if the estimation of 1477 days is realistic, parallelizing will give you ~800 days on a two-core machine, which I guess is still inacceptable.

Instead, you could do the typical profiling workflow:

1. Identify a reasonably small piece of code that takes a long time to complete.
2. Optimize that piece of code by redesigning, rewriting in compiled language or tweaking.
3. Go to 1

If nothing of this gets you acceptable results, you will have to simplify your problem by doing less iterations or making some performance-critical assumptions.