Dr. Dobb's is part of the Informa Tech Division of Informa PLC

This site is operated by a business or businesses owned by Informa PLC and all copyright resides with them. Informa PLC's registered office is 5 Howick Place, London SW1P 1WG. Registered in England and Wales. Number 8860726.

Channels ▼

Cameron and Tracey Hughes

Dr. Dobb's Bloggers

Find John Fast!!

June 29, 2009

The popular paradigm of the computer is a web client, and large chunks of the software development effort is connected to web development. But Tracey and I are still trapped with the notion of the computer as a problem solver, not as part of the solution but as a solver. We use the computer to solve hard problems and we currently are trying to solve unsolvable problems.In both cases we are struggling with Level 1 parallelism (see Figure 1). We are pursing a suspicious possibly spurious connection between problem complexity, search, and Level 1 massive parallelism.

In Level 1 parallelism, we are concerned with the inherent complexity of the problem, not necessarily the complexity of some algorithm used to solve the problem (see Figure 1). This can be a tricky distinction. Through either poor choice or poor programming I could come up with an overly complex algorithm for a simple problem. For example, I could come up with a search strategy that took exponential time to search a list that is in alphabetical order. It is well known that there are solutions to the problem of searching a ordered list that require far less work than any exponential search strategy. Binary search is a case in point. Even a brute force from start to end of the list search only requires that we look at each item in the list once. So in Level 1 parallelism our focus is not on the complexity of some algorithm we might choose to solve the problem, but on the complexity of the problem itself.

For example, our problem is to obtain tomorrow's winning lottery number from John Smith who is currently on Main Street somewhere in the United States. The winning lottery number happens to be the same as a telephone number + a three-digit office extension on one of the business cards that he has in his possession. Unfortunately, John doesn't know that he has the winning lottery number. Of course many of the issues in this problem are obvious. Where in the U.S is John? Which city? Further, which Main Street in that city? East Main? West Main, etc.?

Not only do we have to find the city and the correct Main Street, we also have to find which John Smith. Perhaps there is more than one John Smith currently standing on some Main Street in the U.S. After we have tracked down John Smith, we've got to see what business cards he has in his possession and which ones have phone numbers with 3 digit extensions. And then if there is time to buy lottery tickets before tomorrow's drawing!

There are lots of strategies that we could use in trying to accomplish our goal. Each of those strategies have their own complexities. But we are more concerned with the inherent complexity of the problem itself. Although this problem suggest extremely obvious applications of parallelism (embarrassingly parallel in this case). Is massive parallelism sufficient? What if there are tens of thousands of John Smith's currently on Main Street somewhere in America? What if most of those John Smiths are salesman and have thousands of applicable business cards in their possession? How do we distinguish our John Smith that's currently on Main Street somewhere in America from all of the other people who are currently on Main Street somewhere in America? Can we obtain the winning lottery number from John Smith before tomorrow's lottery drawing? What level of parallelism would make that possible? How would that parallelism be structured or organized? How would the parallelism be managed?

Keep in mind that we've made no mention of computers. Level 1 analysis and decomposition happens before computer solutions are modeled. The paradigm shift requires not only rethinking parallel approaches but also rethinking our approaches to problem and solution modeling. But yet there is hope from the ghosts of ICOT and the Fifth Generation project. Stay tuned.

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.