Is it possible to 'parallelize' this program?

Question

The original program has about 100 'firm' objects that compute an integer 'price' after comparing their own attributes with the attributes of adjacent firms.

The relationship between firms can be 'circular'. At some point, firm[99] will need information from firm[98] and firm[0] to produce a price. firm[0] will update itself after looking at firm[99] and firm[1].

The program currently takes about a minute and a half to complete. We're trying to adapt the program to work with a supercomputer, so that it may handle millions of firms in a similar amount of time. Thus we need to parallelize this program to work on multiple processors.

QUESTION:

Is it actually possible to parallelize this program, when each firm needs to wait for the previous firm to compute information before it can compute its own information?

My intuition and experience say this is impossible, but multi-threaded programming is new territory for me and I've been surprised by clever design before.

Answer 1

This doesn't - at all - have anything to do with multi-threading technology, multi-threading is used when your algorithm needs it, please note that the key word here is algorithm.

Programming languages are only languages in the end, the algorithm and the way of thinking and designing the algorithm define how we are going to get the desired results.

So to answer your question, from the information I have right now about your situation (which is nearly 0%), I can only say it's impossible logically and as you described it to do what you want to do.

There is one possible fix to this, which is making each node have initial values (like firm[0]), you can even make the algorithm a little bit smarter and design some kind of mathematical function to output an initial data from previously used data in the same/previous firm, but I think that would ruin the whole algorithm! so maybe you should consider redesigning the whole algorithm mathematically since your code was working fine and you have data to test on!

The only thing I am worried about is that your company is affording going with mainframe solutions (or I think it should be cloud solutions) providing services to million of possible users, but yet didn't think about hiring a project analysis team to go through the algorithm and try to fix it to suit the requested scenario before passing it to programming teams for implementation!!

UPDATE

Since you are working with N nodes as firms, you can think of creating N threads (i.e: one for each node) and a main one that will collect the information from each thread, now that doesn't mean it is a multi-threaded solution (logically as main process will be idle/waiting for data almost all the time), but from another perspective, each node process can submit its data to main process and get back to work again, main process will be the one waiting for data from process number i (0 < i < N).

Answer 2

Often, in forward time evolution algorithms, like you seem to be describing, an "approximation" that is made is that the value of all elements at t+1 depends only on the value of elements at t. A schematic representation would be:

time |         elements
  t  | ... [i-1] [i] [i+1] ...
     |          \ | /
 t+1 | ...       [i]       ...

If this is the case, then yes, you can parallelize the updates, as they are independent. The simplest approach would be to have each thread (or other type of logical worker unit) update an equal part of the set (so subdivide the work into N parts).

If of course you want to do something like this:

time |             elements
  t  | ... [i-1] [i] [i+1] [i+2] ...
_____|__________\_|_/__|___|________
     | ...       [i]   |   |     ...
 t+1 |               \  |  /
_____|_...____________[i+1]______...

then you're out of luck, because [i+1] depends on the t+1 value of [i], and thus there is no option for parallelization.