Multithreading a series of equations

Question

I have a long series of equations that looks something like this except with about 113 t's:

t1 = L1;
t2 = L2 + 5;
t3 = t2 + t1;
t4 = L3
...
t113 = t3 + t4
return t113;

Where L's are input arguments.

It takes a really long time to calculate t113. So I'm trying to split this up into several different threads in an attempt to make this quicker. Problem is I'm not sure how to do this. I tried drawing out the t's in the form of a tree by hand on paper so I could analyse it better, but it grew too large and unwieldy midway.

Are there other ways to make the calculations faster? Thanks.

EDIT: I'm using an 8 core DSP with SYS/BIOS. According to my predecessor, these inverse and forward kinematic equations will take the most time to process. My predecessor also knowingly chose this 8 core DSP as the hardware for implementation. So I'm assuming I should write the code in a way that takes advantage of all 8 cores.

Answer 1

With values that are dependent on other values, you're going to have a very tough time allocating the work to different threads. Then it's also likely that you'll have one thread waiting on another. And to fire off new threads is likely more expensive than calculating only 113 values.

Are you sure it's taking a long time to calculate t113? or is it something else that takes a long time.

Answer 2

If all the assignments are as simple as the ones you show, a reasonable compiler will reduce it fine. For the parts you show,

return L1 + L2 + L3 + 5, should be all the work it's doing.

Perhaps this could be done in two threads (on two CPUs) like:

T1:  L1 + L2
T2:  L3 + 5
Parent thread: Add the two results.

But with only 113 additions -- if that's what they are -- and modern computers are very good at adding, probably wont be "faster".

Answer 3

I'm assuming that the tasks are time intensive and more that just L2 + L3 or something. If not then the overhead in the threading is going to vastly exceed any minimal gains the threading.

If this was Java then I'd use a Executors.newCachedThreadPool(); which starts a new thread whenever needed and then allow the jobs themselves to submit jobs to the thread-pool and wait for the response. That's a bit of a strange pattern but it would work.

For example:

private final ExecutorService threadPool = Executors.newCachedThreadPool();
...
public class T3 implements Callable<Double> {
    public Double call() throws Exception {
        Future<Double> t2 = threadPool.submit(new T2());
        Future<Double> t1 = threadPool.submit(new T1());
        return t2.get() + t1.get();
    }
}

Then the final task would be:

Future<Double> t3 = threadPool.submit(new T3());
// this throws some exceptions that need to be caught
double result = t3.get();
threadPool.shutdown();

Then the thread pool would just take care of the results. It would do as much parallelization as it can. Now if the output of the T1 task was used in multiple places, this would not work.

If this is another language, maybe a similar pattern can be used depending on the thread libraries available.

Answer 4

Your simple example would automatically multithread (and optimise the solution path) using Excel multi-threaded calculation.
But you don't give enough specifics to tell whether this would be a sensible approach for your real world application.