Requires Serious Attention ... Concurrently

Posted by Cameron Hughes, Tracey Hughes @ 05:18:PM | 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?

This Week's Multicore Reading List
MATLAB and Google App Engine
Logging In C++ : Part 2
 Improving log granularity
A Conversation with BitMagic's Developer
Prefer Structured Lifetimes: Local, Nested, Bounded, Deterministic

All Feature Stories

Real World Parallelism Webinar Series

  • November 17, 2009
    Visual Effects for Animation - presented by DreamWorks Animation
    Speaker: Ron Henderson (Bio)

    Ron Henderson manages the FX Tools group at DreamWorks Animation, where he is responsible for developing physical simulation and procedural modeling tools. These systems have been used for key visual effects in recent films such as Kung Fu Panda and Monsters vs. Aliens (March 2009).

    Prior to joining DreamWorks in 2002 he was a senior scientist at Caltech with a joint appointment to the Applied Math and Aeronautics departments, where he worked on efficient techniques for the direct numerical simulation of fluid turbulence.

    Abstract:
    In this webinar, Ron Henderson will show examples of visual effects, from hair and feathers to smoke and fire, from a variety of DreamWorks Animation feature films. He will discuss in general terms the kinds of techniques used to achieve particular visual effects. Finally, Henderson will show a detailed breakdown of the dam-breaking scene from Madagascar: Escape 2 Africa, demonstrating how different elements of key frame animation, simulation, and rendering are combined in a real production shot.

  • December 1, 2009
    A Quick and Easy Way to Parallelize a Legacy Codebase with Intel® Threading Building Blocks (TBBs)
    Speaker: Bernard Laberge, Avid, Senior Principal Engineer (Bio)

    Bernard Laberge is a senior principal engineer in the video editors division at Avid. During his seven years with the company he has been actively involved in the replacement of the legacy video processing engines used by Avid editors with a common hardware-abstracted, component-based video processing engine currently running on the CPU with SIMD optimized code, GPU, and dedicated hardware.

    Abstract:
    Learn how to overcome the limitations of a thread-based scheduler, including dealing with the absence of recursive parallelism support and the inefficient handling of unbalanced processing load. Bernard Laberge addresses how Avid resolved the expensive refactoring of their thread-based scheduler into a task-based solution by choosing Intel® Threading Building Blocks (TBBs). He explores how Avid was able to easily integrate the Intel TBBs into their video editor applications and more than 5 million lines of code.

  • December 15, 2009
    How to Use Intel® Parallel Studio to Streamline Code Development in a Multicore Environment
    Speaker: Matt Dunbar, Director for Performance Technology, SIMULIA (Bio)

    Matt Dunbar is the director for performance technology at SIMULIA. Since joining the company in 1993, he has worked on parallelization of the Abaqus suite of products, initially for shared memory architectures and more recently for distributed memory architectures. Dunbar has also been intimately involved in selecting both the hardware and software tools used in the development of the Abaqus product line.

    Abstract:
    Resolve elusive, costly multithreading errors quickly and efficiently with Intel® Parallel Studio. While many coding problems that lead to bugs in software applications are typically straightforward logic errors, errors in managing memory and in multithreading code can sometimes take weeks to months to diagnose and fix. Matt Dunbar explores how and why taking advantage of multicore processors through multithreaded code is critical for compute-intensive applications. While spotlighting his work on SIMULIA's Abaqus finite element solver, Dunbar addresses the need for multicore execution and shares his experiences using Intel Parallel Studio to streamline code development in a multicore environment.