Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

In cluster the Amdahl's law, Gustafson's law exists.

I though that there might be some law which states the relation between CPU Hz's and network speed: maximum network speed after which no additional Mbps would increase the calculations. Does such limits exists and what it depends on?

share|improve this question
    
it would only depend on the algorithm being calculated –  ratchet freak Feb 24 '13 at 15:37
    
@ratchetfreak: So, you think that connecting some old PC's with 1Ghz CPU with 1Gpbs network would be better than with 100Mpbs? –  m0nhawk Feb 24 '13 at 15:52
    
@m0nhawk: a 1 GHz chip can at least in theory pump out more than 100Mbps. So yes, it could. –  Mat Feb 24 '13 at 17:11
add comment

2 Answers

Mbps is not the only measure to measure network speed, the other arguable more important one is setup time (how long it takes for a pair of CPUs to be ready to send a packet) which is in many cases an order of magnitude larger that straight up bandwidth

this is the reason why most algorithms try to chunk as much sending as possible

so as soon as size the packet times the bandwidth becomes too small compared to the setup time it stops mattering how fast the network is

also the network topography and placement of the various info being calculated is very important to how fast sending can happen, (as each packet blocks the path it is traveling along)

I'll have to dredge up my parallel programming course to give more info on this if you want

share|improve this answer
add comment

For an algorithm with very little communication between computers (not sensitive to bandwidth limitations) that uses asynchronous communication (not sensitive to network latency), number of CPUs will dominate performance and networking is mostly irrelevant.

For an algorithm with high communication between computers (very sensitive to bandwidth limitations) that uses synchronous communication (very sensitive to network latency), number of CPUs isn't going to matter much.

In practice, all algorithms fit between these extremes somewhere.

Amdahl's law applies to these algorithms. It says (paraphrased as I'm lazy) "the total time is the time taken for the part that can't be done in parallel, plus the part that can be done in parallel divided by the number of CPUs". This ignores all networking/communication delays.

It would be trivial to amend Amdahl's law to take into account the networking/communication delays. For example: "the total time is the time taken for the part that can't be done in parallel, plus networking delays (telling other CPUs what to do), plus the part that can be done in parallel divided by the number of CPUs, plus networking delays (getting results back from other CPUs)". However note that this example only works for a certain style of networking (request and reply) and won't work for other cases (e.g. if the work is pipelined).

The problem is that software is typically not one algorithm - software is a collection of many algorithms. The "amended Amdahl's law" ends up being too complex (as different things can overlap with networking/communication delays; different communication styles can be in use for different pieces; it depends on timing and bandwidth and latency, etc).

At the end of the day; it's more practical to write a prototype/simulation and measure actual behaviour (and find bottlenecks, and improve/exchange algorithms, until you can't find a way of improving it further and give up and claim you've found an answer).

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.