4 ms·

>>(A software person might also think of it as: "If it takes 5 cores to compress 5 GB in 5 minutes, how long would it take 100 cores to compress 100 GB?") I do

>>(A software person might also think of it as: "If it takes 5 cores to compress 5 GB in 5 minutes, how long would it take 100 cores to compress 100 GB?") I don't think that most compression algorithms are Embarrassingly Parallel (http://en.wikipedia.org/wiki/Amdahl%27s_law http://en.wikipedia.org/wiki/Amdahl%27s_law), so it's not clear to me the software scenario is equivalent, or are you saying that the jobs come in 5 gigabyte chunks?

T-hawk 14y ago
Make your own chunks, and the algorithm easily becomes embarrassingly parallel. Give each of the 100 cores 1 GB, let them run independently, and don't sweat the few bits of compression efficiency you might lose. If Amdahl's Law comes into play, it's because you're constrained by memory or some other I/O system rather than the CPU core. Decompression may not be embarrassingly parallellizable for an existing algorithm, if it relies on state that persists through every bit in the data set. But a codec algorithm can be designed to be embarrassingly parallel for both legs.
gojomo 14y ago
You could raise the same objections to the original 'machines'/'widgets' formulation. (There are always economies or diseconomies of scale.) Typically such questions imply the unstated assumption, "answer to the same level of precision/abstraction as the question itself, and assume you have all the info needed to give an answer". With that assumption both questions should be answerable. Compression tends to be pretty parallelizable, if by nothing else than choosing to break the input into separate chunks. You might lose a little bit of efficiency in output size – more restarts, each compressor has less global information – but those don't mean slowdowns (and in a few contrived situations might even mean speedups at the cost of size). See for example 'pigz' and 'pbzip2'. If I were asking this question, I'd accept the 'rough, assuming perfect parallelization' answer as correct-enough in the spirit and level-of-precision implied by the question. If the answerer brought up the difficulties in assuming perfect parallelizability or specific to compression algorithms or choice of inputs, that'd be worth some extra credit, and would trigger followups along the lines of, "how would those factors affect the size?" and "what bottlenecks might you expect?" and "could it ever be faster when split among more machines?"
arethuza 14y ago
My general response to those kinds of performance questions is to measure rather than predict - let me go off, cook up some data sets of appropriate sizes and try it out.

T-hawk 14y ago

Make your own chunks, and the algorithm easily becomes embarrassingly parallel. Give each of the 100 cores 1 GB, let them run independently, and don't sweat the few bits of compression efficiency you might lose. If Amdahl's Law comes into play, it's because you're constrained by memory or some other I/O system rather than the CPU core. Decompression may not be embarrassingly parallellizable for an existing algorithm, if it relies on state that persists through every bit in the data set. But a codec algorithm can be designed to be embarrassingly parallel for both legs.

gojomo 14y ago

You could raise the same objections to the original 'machines'/'widgets' formulation. (There are always economies or diseconomies of scale.) Typically such questions imply the unstated assumption, "answer to the same level of precision/abstraction as the question itself, and assume you have all the info needed to give an answer". With that assumption both questions should be answerable. Compression tends to be pretty parallelizable, if by nothing else than choosing to break the input into separate chunks. You might lose a little bit of efficiency in output size – more restarts, each compressor has less global information – but those don't mean slowdowns (and in a few contrived situations might even mean speedups at the cost of size). See for example 'pigz' and 'pbzip2'. If I were asking this question, I'd accept the 'rough, assuming perfect parallelization' answer as correct-enough in the spirit and level-of-precision implied by the question. If the answerer brought up the difficulties in assuming perfect parallelizability or specific to compression algorithms or choice of inputs, that'd be worth some extra credit, and would trigger followups along the lines of, "how would those factors affect the size?" and "what bottlenecks might you expect?" and "could it ever be faster when split among more machines?"

arethuza 14y ago

My general response to those kinds of performance questions is to measure rather than predict - let me go off, cook up some data sets of appropriate sizes and try it out.