Channels ▼

Cameron and Tracey Hughes

Dr. Dobb's Bloggers

America's Next Top Model?

August 26, 2009

There are several concurrency schemes that describe how parallelism can be performed. Concurrency schemes such as peer-to-peer, boss-worker, workpile, and pipeline describes how tasks distribute work in parallel. SIMD (Single Instruction Multiple Data) and MIMD (Multiple Instructions Multiple Data) are concurrency schemes that achieve data level parallelism.The PRAM (Parallel Random-Access Machine) is a simplified theoretical model that can be used to estimate an algorithm's performance. In the PRAM model there are N processors labeled as P1, P2, P3, . . . PN, that share one global memory. All the processors have simultaneous read and write access to shared global memory. Each of these theoretical processors can access the global shared memory in one uninterruptible unit of time. The PRAM model has four basic algorithmic approaches to access the shared global memory:

  1. Concurrent read algorithms are allowed to read the same piece of memory simultaneously with no data corruption.
  2. Concurrent write algorithms allow multiple processors to write to the shared memory.
  3. Exclusive read algorithms are used to ensure that no two processors ever read the same memory location at the same time.
  4. Exclusive write ensures that no two processors write to the same memory at the same time.

They can be combined into the following four strategies for possible read-write access:

  • EREW (exclusive read and exclusive write)
  • CREW (concurrent read and exclusive write)
  • ERCW (exclusive read and concurrent write)
  • CRCW (concurrent read and concurrent write)

These strategies can be viewed as access policy implemented by the tasks sharing the data and executed on multiple cores. Figure 1 shows these access policies.

Each of these four access policies requires different levels and types of synchronization. They can be analyzed on a continuum with the access policy that requires the least amount of synchronization to implement on one end and the access policy that requires the most synchronization at the other end. EREW, the simplest to implement, means access to the shared memory is serialized where only one task at a time is given access to the shared memory (write or read access). An example of EREW access policy is the producer-consumer. You may have thought CRCW was the simplest because it means access to memory without restriction. But this is the most difficult to implement and requires the most synchronization. The goal is to implement a synchronization process that maintains data integrity and satisfactory system performance. So its on the far end of the continuum.

CREW access policy allow multiple reads of the shared memory and exclusive writes. There are no restrictions on how many tasks can read the shared memory concurrently but only one task can write to the shared memory. Concurrent reads can occur while an exclusive write is taking place. With this access policy, each reading task may read a different value while another task is writing. This may be intended, it may not. ERCW access policy is direct reverse of CREW. Only one task can read the shared data but concurrent writes are allowed. Ahem...

Considering massive multicores, is this model too tired or too old or could it be America's next top model?

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