Channels ▼

Cameron and Tracey Hughes

Dr. Dobb's Bloggers

Requires Serious Attention ... Concurrently

April 13, 2009

Whether your problems are computationally intense or computationally large, maybe multicores can help manage the possible solutions. In guessing our 12-character code (three letter prefix and the 9 remaining characters of any arrangement of letters and digits, with replacement), we are dealing with a very large search space; an exhaustive search requiring 263 x 369 possibilities to consider. How could we interject parallelism into solving such a problem?As mentioned, codes can be generated independently and in parallel. Each core could be used to create codes with certain patterns, codes ending with digits, codes ending with letters, code starting with certain letters, etc.

In assigning a core to generate certain patterns, we create smaller search spaces. The original problem is divided into subproblems that generate possible solutions (subgoals), in this case guesses. Although the problem-reduction approach generates subproblems independently, there may be constraints on how the subgoals are actually used to solve the original problem. These subproblems are significantly smaller (a large search space is divided into smaller search spaces) or significantly less complicated (which taste better, coke or pepsi question is subdivided into several layers that solve certain aspect of the original problem).

With the subgoals generated in parallel, AND/OR parallelism can be used to manage these alternatives. Hopefully reducing the search space to smaller search spaces seached in parallel can do the trick for an exhaustive search problem, Ah...hem.

The problem-reduction approach can be represented in an AND/OR tree. Here are the rules for an AND/OR tree:

  • Each node represents a single problem or a set of subproblems that are to be solved.
  • A terminal node is a node that has no descendants.
  • There are OR nodes in the tree.
  • There are AND nodes in the tree.

Let's use an OR tree for the guessing code problem:

P is the original problem. There are 263 * 369 terminal nodes. There are 26 direct descendant nodes from P representing the branches in the tree starting with a particular letter. The tree builds starting with two character patterns building to a 12 character code patterns. Cores can be initially assigned to two character code patterns starting with a specific letter or at any subsequent level. More cores may be assigned to generate other levels of patterns as needed, all working in parallel. A guess can't be made until the whole 12 character code is built then each core can check to see if its work was done in vain. Is this a viable approach to an exhaustive search using multicores and parallelism? Will the multicores and parallelism effectively deal with the time and space issues for exhaustive searches and combinatorial explosions problems?

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.