Parallelize an already linear algorithm

Question

In practice, is there any case where an algorithm with linear time should be parallelized? My teacher claims that it is not worth it, but I do not believe in it.

Answer 1

Your teacher is wrong. The complexity of execution (O (n), O (log n), etc.) of the uniprocessor algorithm does not affect whether it will benefit from parallelization or not.

Changing the code using 1 processor to use K-processors will allow at best to divide the runtime by a factor of K. Since you cannot arbitrarily create processors from the air, K is actually a constant. Thus, parallelization does not affect runtime. All you can hope to do is achieve continuous improvement.

What can not be said that this is not worth doing - in some cases a twofold improvement is extremely useful. In addition, in a massive parallel system of thousands of processors, this constant becomes quite large.

Answer 2

I also disagree with your teacher. My argument is that many of the algorithms that run on MapReduce are linear time algorithms.

For example, indexing, moving many html pages (for example, all pages on wikipedia) and searching for specific words is an algorithm that is linear in the input. However, you cannot run it without parallelism.

Answer 3

Certain YES. Graphics cards offer parallelism, and switching from CPU to parallel computing on the GPU can save a lot of time. The linear time algorithm can have monumental acceleration in parallel execution. See GPGPU and the "applications" section, or Google for "computing graphics cards."

Although you didn’t ask, theoretically the answer is also defined, yes, there is an NC complexity class for problems that can be “effectively parallelized” (can be solved in logarithmic time with a polynomial number of processors), and “P -complete” problems that can be solved in polynomial time, but they are suspected that they are not in NK. (just like there are problems with P and problems with NP-complete, and NP-complete is suspected that they are not in P)

Answer 4

Given the relatively large input volume, it's worth it. Always.

Example: A naive algorithm for finding the largest number in an unordered "list" will simply traverse the list. It takes time of the order of O(n) to find the record.

This is normal if you have 100 or 1000 entries.

What if you had a billion records? You split the list among several processors, each finds a maximum, then you have a new smaller list for work. You can split it again => Parallel and faster. I believe this is O(log(n)) if you effectively split and reduce and have n processors .

Point: if your input is large enough, O(n) no longer enough. Depending on what needs to be done, O (n) can grow to too many seconds, minutes, hours compared to what you would like.

Note. When I say O(n) or O(log(n)) above, I mean the time taken to complete the search. that is, not the "common work" performed by all CPUs. Typically, parallelizing an algorithm increases the overall work performed by processors.

Answer 5

Given a single-core, single processor, a single computer environment, and a CPU-related task, your teacher is faithful. (although it can be argued that in this case, despite the fact that you can run multiple threads, they do not work really in parallel, just given the illusion of parallel operation)

Nowadays, however, single-core systems are rare, even many smartphones are switching to multi-core, so in practice you are likely to benefit from parallelization. I say this probably because if the tasks are small, the cost of creating threads will be higher than the benefits, there is also context switching, which costs processor cycles. If this is not done reasonably, there is always the possibility that performing a parallel operation will actually make it slower.