Requires Serious Attention ... Concurrently
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?