Multi-Core Programming

I'm aware that this topic deserves a whole book's worth of discussion, but my implementation should be relatively simple, so I'm wondering if I could dive right into it without understanding the underpinnings of multicore programming.

Objective: Having a large amount of data in row-column/table/matrix format, I want to split it up into equal P parts (P = # of cores) and send them to each respective core to perform a summation operation (or equivalently, the inner product of vectors).
The operation should be as simple as

where
x_i is a vector of length n
mu is a vector containing all the arithmetic means of all the x_i's

Question: How exactly do I "send" each operation to a specific core and have it carried out? How do I handle the returned values?

Use a thread for each part. How you do this depends on your language and platform.

Use a thread for each part. How you do this depends on your language and platform.

If the learning curve is not *too* steep, do you have a reading list you would suggest?

What programming language and operating system are you interested in? I'm on my phone now, will post some c# info when I get home.

If the learning curve is not *too* steep, do you have a reading list you would suggest?

A steep learning curve means the stuff is easy to get a grasp on :p

What programming language(s) do you use?

I'm most familiar with Java and GNU Octave, hoping to run this with Octave on Ubuntu 11.10 64bit, though.
If I want to use Java for these applications, I would have to learn to use a linear algebra package from scratch, though I imagine it can't be that hard.
Let me dig up my CPU information too. It's an Intel i7 2630-QM.

And oh, I kinda get it now, steepness does not represent the depth of the knowledge but rather the amount of knowledge that can be gained in a fixed period of time. Or maybe it's a bit of both, easy to grasp at introductory level, difficult without bounds later on.

Alright, so you're used to programming with a single thread of execution. Everything executes in the order that you put it.* If you have more than one thread of execution, some could be running at the same time. You do not have control over which threads execute on which core**, nor do you usually care. If your program has 4 threads ready to run (ie not blocked waiting for I/O or something) and your CPU has 4 cores, maybe only 3 will be running at a certain time because some other program is running on the other core.

Threads will be stopped and resumed at unpredictable times as the operating system schedules other threads (including threads from other processes). You have to be very careful to make sure that it is not possible for multiple threads to interfere with each other. For example, if thread 1 adds something to an ArrayList, thread 1 gets stopped in the middle of the add, then thread 2 tries to add something, the internals of the ArrayList will be in an unpredictable state. You can prevent this by making sure that when one thread is adding something to the ArrayList, no other thread can access the ArrayList. The key word to search for about this is "synchronization". One synchronization method Java offers is the "synchronized" keyword, which makes a thread block when calling the method if another thread is already inside the method.

Check out the java.util.concurrent, java.util.concurrent.locks, and java.util.concurrent.atomic packages.

Threads of the same process share the same address space, so changes to variables visible to other threads will be seen by those other threads.*** That's how you "pass back" results.


* Or "as if it was in the order you put it". Some languages permit the compiler to optimize by reordering statements if it can prove that doing so would have no observable effect on the program if it was single-threaded. The same goes for CPUs and reordering instructions.
** Unless you set the thread affinity. Then you can force certain threads to execute on certain processors. But it's generally best to let the operating system decide which processor to run a thread on.
*** As long as there is a proper memory barrier. Variables may be in a CPU register or in the cache. You need to tell the compiler and the CPU to get the value that's in memory, not from a register or the cache. In C# (but not C or C++!) this can be accomplished by marking the variable as volatile or using a lock statement, among other things.


Enough talk, here's some C# code. Sorry it's not Java, I'm not familiar enough with threading in Java to whip up an example, but the concepts are the same.

 Spoiler

Code:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading;

namespace ConsoleApplication1
{
    class MatrixStuff
    {
        public MatrixStuff(int index, CountdownEvent countdown)
        {
            Index = index;
            Countdown = countdown;
        }
        
        public int Index { get; private set; }
        public int Result { get; set; }
        public CountdownEvent Countdown { get; private set; }
    }
    
    class Program
    {
        static void Main(string[] args)
        {
            int numberOfProcessors = Environment.ProcessorCount;
            Console.WriteLine("{0} processors", numberOfProcessors);
            List<MatrixStuff> matrixThings = new List<MatrixStuff>();

            using (CountdownEvent countdown = new CountdownEvent(numberOfProcessors))
            {

                for (int i = 0; i < numberOfProcessors; i++)
                {
                    MatrixStuff objectToPassToThread = new MatrixStuff(i, countdown);
                    matrixThings.Add(objectToPassToThread);
                    ThreadPool.QueueUserWorkItem(MatrixThreadStart, objectToPassToThread);
                }

                // Wait for all worker threads to finish. This is a memory barrier, so reading matrixThings[x].Result
                // is guaranteed to get the result set by the worker thread.
                countdown.Wait();
            }

            for (int i = 0; i < numberOfProcessors; i++)
            {
                Console.WriteLine("Result for {0}: {1}", i, matrixThings[i].Result);
            }
        }

        static void MatrixThreadStart(object stuff)
        {
            MatrixStuff matrixStuff = (MatrixStuff)stuff;
            matrixStuff.Result = matrixStuff.Index * 10;

            matrixStuff.Countdown.Signal();
        }
    }
}

Threading is complicated. Many programmers do not know how to properly write multithreaded code and even for those that do, it is easy to make a mistake. I myself made a mistake when writing the example. I wrote "for (int i = 1; i < numberOfProcessors; i++)" in the loop that hands off the work to the thread pool, resulting in a deadlock because the main thread was waiting for 8 tasks to complete but only 7 were ever created.