Help: Systolic arrays and matrix multiplication

Commenter apit had given me a problem which I am unable to help with: Matrix multiplication using systolic arrays.

I searched and I came up with very little. About the only thing I understood was that the “array” was not the variable array in code. It’s an array of processors. Systolic arrays are used for parallel processing.

So how is it used for matrix multiplication?

Hmm… I’ve never heard of systolic arrays before this. So I asked my friend and he found a PowerPoint presentation that gave the best explanation that I could understand.

Systolic arrays & their applications, by Jonathan Break.

I believe apit didn’t understand that each “array cell” don’t have past memory of operations, only an intermediate result.

If you happen to understand it, and can explain it better than I do, please chime in with your comment. Thanks.

Minor irks between C# and VB.NET

It’s about the way you think about programming. This isn’t another debate on which language is better. Just noting the differences because of how I think. The first is…

Declaring variables

After I think through the logic I want, the first thing that comes to mind might be “I need an integer”. This works well:

int i;

This, not so much:

Dim i As Int32

In C#, the name of the variable is secondary, at least at the point when it’s created. I need an integer. I don’t really care what its name is (yet). Nor does the compiler.

In VB.NET, I have to come up with a name. And if my RPG days are any indication, I take a long time coming up with names. By the time I think up an appropriate name, I forgot what type it’s supposed to be.

It’s like the active-passive voice in English. “He ate the apple.” and “The apple was eaten.” Which do you want to focus on?

I might be wrong. VB views variables as containers for values, hence there’s no point in fixing the type at declaration (like Javascript)? And VB.NET inherits the language structure.

Arrays

In C#, arrays are declared like so:

int[] ia = new int[5];

In VB.NET, they are declared like so:

Dim ia(5) As Int32

There’s a catch though. The array in C# has 5 elements. The one in VB.NET has 6.

Both languages treat arrays with zero-based indices. In VB.NET, the number used in declaring the size of the array means the last index of the array.

So if I wanted 5 elements, I should declare it as:

Dim ia(4) As Int32

Ok, I guess my frustration has run its course…

Beginning C# – Arrays and iterations

Numbered mailboxes @iStockphoto / Eliza Snow So you’ve learnt a bit about variables such as ints and floats. What happens if you need, say a bunch of integer variables with similar purposes? For example, ten decimal variables to store prices. This is where arrays come in.

One and two dimensional arraysArrays offer a simple syntax to declare a series of variables of the same type with minimum work. Think of arrays as boxes in sequential order, where the boxes can only hold a certain type of item.

When someone uses the term “array”, the person usually means a one-dimensional array. What’s the difference? Imagine you have a series of boxes. That’s a one-dimensional array. Then imagine each of those boxes is the start of another series of boxes. That’s a two-dimensional array. You can even go on to three-dimensional arrays, where you stack two-dimensional arrays on top of each other.

Alright then, how do you use them? Here comes the source code.

            const int numberofelements = 10;
            double[] multiplesofpi = new double[numberofelements];
            int i;

            for (i = 0; i < numberofelements; ++i)
            {
                // The result of an operation between two numbers has
                // the precision of the number with the higher precision.
                // Math.PI is a double, which has a higher precision than
                // i, an integer. So the result of i * Math.PI is a
                // double.
                multiplesofpi[i] = i * Math.PI;
            }

            // reverse the for loop
            for (i = numberofelements - 1; i >= 0; ----i)
            {
                Console.WriteLine("Box {0} has {1}", i, multiplesofpi[i]);
            }

            Console.WriteLine("End of program");
            Console.ReadLine();

So we declare an array of doubles named multiplesofpi. Note the square brackets after the double. This line

            double[] multiplesofpi = new double[numberofelements];

just tells the compiler that we want an array of doubles. The new keyword simply tells the compiler to create a new array of doubles, with “numberofelements” number of doubles bunched together. Remember the const keyword we learnt?

            for (i = 0; i < numberofelements; ++i)
            {
                // The result of an operation between two numbers has
                // the precision of the number with the higher precision.
                // Math.PI is a double, which has a higher precision than
                // i, an integer. So the result of i * Math.PI is a
                // double.
                multiplesofpi[i] = i * Math.PI;
            }

In the for loop, we assign each element of the array with a value. Each array element can be accessed using an index, which in our case is the variable i.

There are 10 iterations in this case. An iteration refers to an instance of something being done repetitively, such as in a for loop, or while loop. In each iteration, we multiply the number of the iteration by the value of PI, which is about 3.14159. The Math library provided by .NET already contains the constant value of PI, so we’ll just use that.

It takes some getting used to, but computers really like counting from zero. We humans start counting from 1, and for a long time, cannot grasp the idea of nothingness. Computers however, have no problems with zero. Maybe they’re more advanced than us humans…

Anyway, we then practise reversing the for loop with

            // reverse the for loop
            for (i = numberofelements - 1; i >= 0; ----i)
            {
                Console.WriteLine("Box {0} has {1}", i, multiplesofpi[i]);
            }

This is important, because there will come a time in your programming life where going backwards and forwards in a sequential manner is critical. Besides, it trains your mind to think differently, and that’s great by itself.

Homework
Write the first for loop in reverse manner. Then try writing the second for loop in forward manner. Convince yourself that the array will contain the same values, regardless of whether the for loop is in forward manner or reverse manner.

Download the source code.