Channels ▼
RSS

Parallel

How Much Scalability Do You Have or Need?


In your application, how many independent pieces of work are ready to run at any given time? Put another way, how many cores (or hardware threads, or nodes) can your code harness to get its answers faster? And when should the answers to these questions not be "as many as possible"?

Table 1 summarizes three "orders" of throughput available in a given application or operation, using big-Oh notation to describe the amount of CPU-intensive work that will typically be ready to be actively executed at a given time. The rest of this article overviews these orders of scalability and summarizes when each one is appropriate.

Last month [2], we looked at three "pillars" of concurrency: Pillar 1, isolation by structuring work asynchronously and communicating through messages; Pillar 2, scalable throughput by exploiting parallelism in algorithms and data structures; and Pillar 3, dealing with mutable shared state. This month's topic delves into throughput-oriented techniques using techniques in Pillar 1 and Pillar 2.

Order O(1): Single-Core O(K): Fixed O(N): Scalable
Tagline One thing at a time Explicit threading Re-enable the free lunch
Summary Sequential applications, and bottlenecked parallel applications Explicitly express how much work can be done in parallel Express lots of latent concurrency in a way that can be efficiently mapped to N cores
Examples Multithreaded code convoyed on a global lock or message queue, occasional or intermittent background work Pipelining, hardwired division of tasks, regular or continuous background computation Tree traversal, quicksort, compilation
Applicability Single-core hardware, single-threaded OS, or nonCPU-bound app Hardware with fixed concurrency, or app whose CPU-bound parts have limited scalability Hardware with variable (esp. growing) concurrency, and app with CPU-bound parts that are scalably parallelizable
Examples Code targeting legacy hardware, small embedded systems, single-core game consoles; simple text processor Game targeting one multicore game console generation; code whose key operations are order-sensitive (e.g., can be pipelined but not fully parallelized) Mainstream desktop or server software with CPU-bound features and targeting commodity hardware or future upgradeable game consoles
Pillar (see Notes [2]), and today's mainstream tools Pillar 1: Threads, message queues, futures Pillar 2: Thread pools, futures, OpenMP

Table 1: Orders of throughput.


Related Reading


More Insights






Currently we allow the following HTML tags in comments:

Single tags

These tags can be used alone and don't need an ending tag.

<br> Defines a single line break

<hr> Defines a horizontal line

Matching tags

These require an ending tag - e.g. <i>italic text</i>

<a> Defines an anchor

<b> Defines bold text

<big> Defines big text

<blockquote> Defines a long quotation

<caption> Defines a table caption

<cite> Defines a citation

<code> Defines computer code text

<em> Defines emphasized text

<fieldset> Defines a border around elements in a form

<h1> This is heading 1

<h2> This is heading 2

<h3> This is heading 3

<h4> This is heading 4

<h5> This is heading 5

<h6> This is heading 6

<i> Defines italic text

<p> Defines a paragraph

<pre> Defines preformatted text

<q> Defines a short quotation

<samp> Defines sample computer code text

<small> Defines small text

<span> Defines a section in a document

<s> Defines strikethrough text

<strike> Defines strikethrough text

<strong> Defines strong text

<sub> Defines subscripted text

<sup> Defines superscripted text

<u> Defines underlined text

Dr. Dobb's encourages readers to engage in spirited, healthy debate, including taking us to task. However, Dr. Dobb's moderates all comments posted to our site, and reserves the right to modify or remove any content that it determines to be derogatory, offensive, inflammatory, vulgar, irrelevant/off-topic, racist or obvious marketing or spam. Dr. Dobb's further reserves the right to disable the profile of any commenter participating in said activities.

 
Disqus Tips To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.
 

Video