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

There's Good News and There's Bad News ...

November 10, 2009

Last week we gave the webinar scene a break. Instead, Tracey talked me into going with her to the new Bill Gates Hillman Complex located on Carnegie Mellon campus in Pittsburgh. Holger Hoos from the University of British Columbia was giving a talk called "Taming the Complexity Monster". I figured how could we go wrong!

Since we both are currently wandering in the wilderness of AI-Complete problems and our multicore machinations are turning out to give us deceptively correct answers. I thought just maybe Holger Hoos might have some encouraging words for us. After all Dr. Hoos is a founding member of the Bioinformatics, Theoretical and Empirical Algorithms Laboratory and a member of the Laboratory for Computational Intelligence with additional involvement with the Institute for Computational Intelligence and Cognitive Systems. Surely he could shed some light on our massive multicore vs. AI-Complete problem issue.

I remember thinking on the drive down that it felt like we were off to see the wizard. So after taking a wrong turn somewhere around Veteran's Bridge in downtown Pittsburgh and getting lost, we finally made it to the Gates Hillman Complex.

The Bill Gates Hillman Complex located on Carnegie Mellon campus

There were several eye-popping and jaw-dropping moments in the talk. Tracey and I were especially encouraged when he started talking about problems that were similar to the ones we are currently challenged with.

We weren't the only ones that were captivated by the talk. You could almost feel the excitement in the air. But with one click of the mouse everything went down hill for our multicore expectations. Out came the PowerPoint. Out came the performance graphs. Out came the truth (atleast the truth according Holger). He demonstrated that if we had one processor for every atom in the universe and if each processor could execute instructions at the speed of light that a parallel computational solution for the class of problems that we are trying to solve would take millions, billions, trillions of years to complete! Ouch! That was very bad news to hear.

He also suggested that for the class of problems that Tracey and I are stuck with that even with such large-scale massive parallelism, it would only offer extremely negligible speed up in relation to problem size. How could that be? I immediately pulled out my PSP (really I did) and then logged in to our private lab and research cluster, typed some numbers into Mupad, and slowly the bad news was retraced on the screen of my PSP.

And just as we were about to succumb to Holger's talk, he introduced a new approach to algorithm design. He had some new approaches to some of the classic NP-hard problems. These new approaches had a dramatic effect on algorithm design that brought computational solutions within practical reach. He introduced the Concorde TSP Solver, DPLL (Davis-Putnam-Logemann-Loveland) algorithm, and the new field of empirical algorithms approaches. As I looked closer I saw what at least looks like to me a striking intersection between some of the empirical algorithms and some of the findings of ICOT and the Fifth generation project. So it would seem that there is hope after all and that the ghosts of ICOT are trying to tell us something and that some of the stones we've turned over could lead to significant paradigm shifts for parallel programming and multicore computers. So our trip turned out to be good-news, bad-news.

The good news was that we heard an approach to solving our particular brand of problems. The bad news was that we heard an approach to solving our particular brand of problems but there was no short cut in sight, no easy way out, no silver bullet, no rest for the wicked.

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.