3
$\begingroup$

Due to technical constraints, single thread performance has been increasing more slowly and adding cores has been adopted to offer greater potential increase in performance.

However, multicore support currently appears to require the programmer to manually divide the work, control communication/synchronization, etc. For many processor intensive games and simulations (such as DCS), such complicated multithreading effort has been limited, and these programs depend extremely heavily on single thread performance.

Could a processor with multiple cores divide the work automatically?

Alternatively, could a compile convert single-threaded code to mulithreaded code? In the current world, multicore support has to be done by hand as far as I know, with a result being that many processor intensive games and simulations (such as DCS) depend extremely heavily on one CPU core to avoid complicated multithreading.

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ Wikipedia's article on automatic parallelization is weak but is a decent place to start. Autoparallel results for SPEC CPU have made the benchmark suite less useful for evaluating single-thread performance (the 462.libquantum subtest clearly benefits substantially from auto parallelization). Intel's compiler supports autoparallelization. $\endgroup$
    – user4577
    Apr 11, 2015 at 22:47
  • $\begingroup$ You ask about processor-level but accept an answer that talks about compiler-level. What is it you are after? $\endgroup$
    – Raphael ♦
    Apr 12, 2015 at 9:05
  • $\begingroup$ @Raphael should a more compelling answer be posted, I can always change my accepted answer. I think his answer sufficiently hit my intent. $\endgroup$
    – Bassinator
    Apr 12, 2015 at 14:42

2 Answers 2

Reset to default
1
$\begingroup$

The short answer: yes it's possible, but right now it generates slower code.

The long answer: the thing to keep in mind here synchronization. Computation is not just a bunch of independent computations. The results of one computation are used in other ones. Sometimes the order doesn't matter, and sometimes it does.

Take for example, some hard to evaluate function $f$. If we want to compute $f(f(10) + f(20))$, we can evaluate $f(10)$ and $f(20)$ in parallel, but we can't evaluate the final result until we've done the two inner evaluations and added them together.

This process of making sure things happen in the right order is called synchronization. There are many ways to ensure synchronization happens and that the code produces the same result even if some operations are moved around.

There are many models of concurrency: some have shared memory with locks on variables, some have totally separate processes that pass messages. But in every model, the synchronization carries some overhead. Acquiring a lock, sending a message between processes, each of these adds time that wouldn't be required if you evaluated the code sequentially.

Likewise, scheduling causes some overhead. If you have 200 processes and only 8 cores, you will probably be slower than if you have, say 20 processes and 8 cores, since you have to do a lot more work scheduling, but don't get additional parallelism.

The key, then, is to adjust the "granularity" of your concurrency. Too coarse and you don't make use of all the processors, but too fine and you get too much overhead from synchronization and scheduling.

This sort of analysis is hard, and right now compilers don't do it well enough to make general code faster, but I suspect with heuristics, and maybe even a bit of AI/machine learning, in the future we'll be able to automatically adjust the granularity automatically.

I'm not a hardware person, but my guess is that computing these sorts of things are way too complicated and time-consuming to be done on-the-fly at the CPU level.

At a compiler level, it's possible, but depends on your language constructs. I'm fairly certain finding the "optimal" parallelization of a program is undecidable, since you can probably construct some example where you can parallelize a program iff an arbitrary program halts.

However, like most program analyses, we can do "safe" approximations. In particular, there has been interesting research into automatically parallelizing "pure" functional languages like Haskell. When any side-effects of a function are captured by the type system, it's a lot easier for the compiler to know what operations can safely be performed in parallel. But to my knowledge, none of these efforts have succeeded so far in producing fast code.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Check out the difference in 462.libquantum (which is written in C) results for this 16-core system (4.19 seconds; 403.gcc — the least broken SPEC CPU2006 subtest — took 239 seconds) and this 36-core system (2.58 seconds; 403.gcc took 228 seconds). (The latter system turboboosts 12.5% higher.) Some code has loop level parallelism that is amenable to autoparallelization and vectorization. $\endgroup$
    – user4577
    Apr 12, 2015 at 20:58
  • $\begingroup$ Is it numeric, vector-based code? That's a whole different kettle of fish. It tends to be very easy to parallelize, for example with what GPUs do all the time. But this is somewhat of a special case, since it can take advantage of SIMD, performing the same operation repeatedly on different data. (I don't know if that's what it's actually doing, but I'm just guessing). $\endgroup$
    – jmite
    Apr 12, 2015 at 21:05
  • $\begingroup$ Yes, this code has extensive loop-level parallelism and so is relatively easy to automatically use multiple threads. (The work is also know to be large enough to justify thread spawning overhead.) The point of my comment was not that such works in the general case (much less the bad case of C spaghetti code) but that autoparallelization does work in some cases. Runtime systems (and libraries) provide another mechanism for using thread-level parallelism without application-level code changes (worth mentioning but still "hand coded" parallelism). $\endgroup$
    – user4577
    Apr 12, 2015 at 21:23
  • 1
    $\begingroup$ The main issue is that people write code that is too ambiguous for the compiler; language issue. If a function takes two array pointers, it would need to be able to prove things like whether the arrays overlap in order to make some optimizations. If there is a for loop, it would need to know that there are no loop carried dependencies to run them all in parallel. Even when everything can be parallel, you may not have been specific about how much memory usage for a task is reasonable (ie: compute a million items in parallel in memory versus accumulating as they stream through). $\endgroup$
    – Rob
    Apr 23, 2015 at 19:33
0
$\begingroup$

Automatic parallelization of software (at the source code level down to the hardware level) has been actively researched and in some areas has achieved significant speed-ups. This effort can roughly be divided into three types: compiler autoparallelization, parallel runtime systems/libraries, and speculative multithreading.

Compiler autoparallelization currently is most effective on easily parallelized (e.g., vector-heavy) code. The Intel compiler's autoparallelization is able to substantially improve performance of the SPEC CPU2006 subbenchmark 462.libquantum (effectively breaking the benchmark as a measure of single thread performance). For example, this 36-core system has a 1.55x speedup (for 2.25x more cores) relative to 403.gcc (the least broken SPEC CPU2006 subbenchmark) compared to this 16-core system. This is nearly a 69% parallelization efficiency. Since the 36-core processor had 12.5% higher turboboost frequency (applied to 403.gcc but not 462.libquantum), the compiler actually achieved higher parallelization.

Compiler autoparallelization faces similar difficulties to compiler autovectorization in discovering the potential parallelism and expressing it in a manner that does not substantively change program semantics and is likely to improve performance. (Interestingly, recent x86 SIMD extension implementations have introduced warm-up and cool-off overheads somewhat conceptually similar to thread initialization overheads.) Processors ability to exploit unused power/thermal budget to increase clock frequency (e.g., Intel turboboost) makes the performance tradeoff more complex; a modest speed-up from parallel execution can result in a net slowdown due to lower clock frequency. Shared resources other than power/thermal budget can also bottleneck performance.

Runtime systems and libraries can also provide some support for parallel execution. A simple example of this is parallel garbage collection; simply by changing the run-time system or library, parallel execution (in a very limited context) can be provided. While such parallelization opportunities are generally limited and do not apply to the application code itself, the benefit is not insignificant.

Speculative multithreading, whether provided by hardware, by a software run-time system, or by some combination of these, can speculatively execute loop iterations and even function calls in parallel. Speculative execution has the advantage of being able to use parallelism that cannot be staticly guaranteed to be dependency-free by the compiler. While significant work has been done in this area, substantial research and development remains before significant adoption is practical.

Hardware support can substantially reduce the cost of conflict detection and thread activation. Versioned memory could provide multithreaded benefits similar to those register renaming provides for out-of-order execution (reducing name dependencies and facilitating roll-back after wrong speculation).

Before it was bought by Intel, Soft Machines was developing what it called VISC, which transparently translated single-threaded binaries to run on multiple cores with a different ISA. This February 2016 AnandTech article provides some information on VISC.

Side Note: Making Parallel Programming Easier

Obviously, if a compiler can seek opportunities for parallelization, it could also provide feedback to the programmer about cases where the compiler could not autoparallelize but might be able to do so with modest changes to the source code. Just as performance tuning tools have improved for single-threaded code, it should be expected that performance tuning (and correctness checking) tools for multithreading should improve, even if more gradually.

Hardware mechanisms such as hardware transactional memory can make some aspects of multithreaded programming easier. Transactional memory simplifies locking by facilitating the use of coarser-grained locks. Hardware transactional memory is still very young, so there is likely significant potential for improvement is hardware implementation and software use. Reducing the cost of system calls and interprocessor interrupts (or interprocessor procedure call) could make irregularity of work availability less problematic by reducing the cost of activating a thread. Faster handling of buffer-based inter-thread communication could increase the performance of simpler pipeline-based parallelism (e.g., instead of the reader pulling from the writer on demand, buffer writes could be pushed closer to their consumer).

Languages and libraries (as well as programmer education and hardware availability) are also likely to slowly make multithreaded programming easier and more common for performance-constrained software.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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