DZone
Thanks for visiting DZone today,
Edit Profile
  • Manage Email Subscriptions
  • How to Post to DZone
  • Article Submission Guidelines
Sign Out View Profile
  • Post an Article
  • Manage My Drafts
Over 2 million developers have joined DZone.
Log In / Join
Refcards Trend Reports Events Over 2 million developers have joined DZone. Join Today! Thanks for visiting DZone today,
Edit Profile Manage Email Subscriptions Moderation Admin Console How to Post to DZone Article Submission Guidelines
View Profile
Sign Out
Refcards
Trend Reports
Events
Zones
Culture and Methodologies Agile Career Development Methodologies Team Management
Data Engineering AI/ML Big Data Data Databases IoT
Software Design and Architecture Cloud Architecture Containers Integration Microservices Performance Security
Coding Frameworks Java JavaScript Languages Tools
Testing, Deployment, and Maintenance Deployment DevOps and CI/CD Maintenance Monitoring and Observability Testing, Tools, and Frameworks
Culture and Methodologies
Agile Career Development Methodologies Team Management
Data Engineering
AI/ML Big Data Data Databases IoT
Software Design and Architecture
Cloud Architecture Containers Integration Microservices Performance Security
Coding
Frameworks Java JavaScript Languages Tools
Testing, Deployment, and Maintenance
Deployment DevOps and CI/CD Maintenance Monitoring and Observability Testing, Tools, and Frameworks
  1. DZone
  2. Data Engineering
  3. AI/ML
  4. Parallelism for dummies

Parallelism for dummies

Giorgio Sironi user avatar by
Giorgio Sironi
·
Jun. 14, 11 · Interview
Like (0)
Save
Tweet
Share
14.56K Views

Join the DZone community and get the full member experience.

Join For Free

If you have not lived under a rock, you have probably heard that the clock frequencies of our CPUs haven't increased in years, and they probably won't in the next ones. This speed barrier, imposed by the limits to miniaturization, is the driving force behind many words we hear every day: concurrency, distributed computing, dual core, scalability, functional programming...

Yet what is parallelization? How the clock frequency wall impacts the average programmer? In this article we take a look at several facts and misconceptions about the topic, from a beginner's point of view.

At the instruction level

CPUs with more than one functional unit (let's say more circuits) may exploit their redundant capabilities by issuing and executing more than one execution at the time. These capabilities are transparent to the programmer, who just writes sequential code like he has always done; this model is called superscalar processor.

Yet if you have ever written some lines of assembly, you know that machine-level instructions are similar to every higher-level imperative languages, in the way they have functional dependencies between each other:

mov ax, bx #good old 8086 assembly
add ax, 42 #cannot dispatch it to the ALU simultaneously

Conflicts on registers and memory locations are very common in near instructions, so that they can't be parallelized automatically. It would be very nice, since everyone will just throw them sequential programs and get a speedup linear with the number of cores. Yet this kind of performance gain is limited, especially since it must be performed on-the-fly by the processor: static compiler-based optimizations would require to manage hundreds of different binary versions (for example a version for each number of cores).

Take away point: the good old sequence of assembly instructions is gaining another level of abstraction, consisting in out-of-order execution and in general in scheduling over different cores.

At the thread level

We cannot increase the clock frequency, and we cannot automatically execute instructions in parallel due to their dependencies. Thus, the next step is to require the programmer to write parallel programs; the resulting code may take different forms:

  • multiple threads which works over a shared memory, and sinchronize with locks or similar systems. This concurrency model has been implemented for decades in order to exploit a single-core CPU while some thread blocked waiting for input, and is probably one of the most popular causes of failure in programs due to race conditions, starvation, deadlocks...
  • multiple processes, which differ by threads for the absence of shared memory, but not very much in implementation. They communicate via explicit messages and are commonly juggled continuously in time-sharing by every OS written after 1980.
  • an actor model, like the one of Erlang, where actors substitute processes as the basic unit of computation (there's a whole mathematical theory behind concurrency based on actors).

Take away point: multiple independent units of computation are better leveraged if you throw away the abstraction level of a single execution flow and incorporate them in a programming model.

At the cluster level

When even a powerful machine doesn't cut it, replicating an application over a cluster is the only mean to increase performance or support more users simultaneously. Other reasons for moving to the parallel use of multiple machines are just their costs (N inexpensive servers costs less than a single server N times faster) and the built-in redundancy of this model. Many web applications, for example, distribute HTTP requests across a cluster of servers so that in case of a failure only 1/N users are affected before recovery takes place.

Yet parallelize an application over multiple machines is not banal. For a stateless part, like an HTTP server executing PHP code, is just a matter of copying files and balancing the requests; for a stateful component like a database, entire books have been written on the problem.

Take away point: throwing more hardware at the problem is a good idea, but it isn't always going to magically solve it.

Amdahl's law

In fact, when talking about parallelism, the first example is always an embarassingly parallel problem, like rendering a bunch of frames or simply summing the elements of a large array.

But not all problems are like that: in general, the time needed for an algorithm is divided into two parts, the sequential and parallel fractions. Parallelism can decrease the time needed for the P fraction, but cannot do anything for the S one.

The simple formula for the speedup by introducing N independent processors is:

1/((1-P) + P/S)

If you apply it simply to the execution time, you get that a time T on a single execution unit becomes:

T' = PT/N + (1-P)T

Tthe sequential fraction will never become shorter, no matter how many processors or machines you add.

Take away point: static analysis is no good in parallelism as in profiling; you must find out if a fraction of your code is large enough to gain significant performance before parallelizing it.

Conclusion

Parallelism is a difficult problem, that we're trying to solve at every level from the CPU instruction to the room full of servers. Our programming models may change in the future to exploit it, yet not every problem is prone to be solved by this model. Now you have started your journey into it...

Execution (computing) cluster application AI Machine Time-sharing philosophy Database Memory (storage engine) Programmer (hardware)

Opinions expressed by DZone contributors are their own.

Popular on DZone

  • Kubernetes vs Docker: Differences Explained
  • Kotlin Is More Fun Than Java And This Is a Big Deal
  • Implementing Infinite Scroll in jOOQ
  • Architectural Miscalculation and Hibernate Problem "Type UUID but Expression Is of Type Bytea"

Comments

Partner Resources

X

ABOUT US

  • About DZone
  • Send feedback
  • Careers
  • Sitemap

ADVERTISE

  • Advertise with DZone

CONTRIBUTE ON DZONE

  • Article Submission Guidelines
  • Become a Contributor
  • Visit the Writers' Zone

LEGAL

  • Terms of Service
  • Privacy Policy

CONTACT US

  • 600 Park Offices Drive
  • Suite 300
  • Durham, NC 27709
  • support@dzone.com
  • +1 (919) 678-0300

Let's be friends: