NGrid
Open source grid computing

NGrid
One page code sample

The purpose of this page is to give a direct coding overview of the NGrid programming model. We propose here a grid sorting algorithm. A call to GridSort.Sort(Array array, IComparer comparer) will actually sort the values contained in array. This algorithm demonstrates how to design a grid object (inherited from GObject), how to handle grid threads (named GThread) and how to perform grid synchronization (using Lock).

The theorical complexity of this grid sorting algorithm is O(n) for sorting an array of n values if at least n grid hosts are available (remember that if only one single machine is available, the complexity lower bound for sorting is O(n log(n))). This algorithm has little practical interest because this algorithm is not efficient: the total work performed by the grid is O(n2). 

/* NGrid - one page code sample
 * (c) 2004 - Joannes Vermorel */

using System;
using System.Collections;
using System.Threading;

using NGrid;
using NGrid.Collections;
using NGrid.Threading;

namespace MyGridSort
{
    public class GridSort
    {
        // the 'Node's are chained to form a single linked list
        [Serializable]
        private class Node : GObject
        {
            private IComparer comparer;
            private object nodeValue;
            private Node left;
            
            private bool swap;

            public Node(IComparer comparer, Node left, object nodeValue)
            {
                this.comparer = comparer;
                this.left = left;
                this.nodeValue = nodeValue;
            }

            // compare with the values
            public void CompareSwap()
            {
                // locking 'left' and then 'this'
                using(new Lock(left))
                {
                    using(new Lock(this))
                    {
                        swap = (comparer.Compare(left.Value, this.Value) > 0);

                        if(swap)
                        {
                            object tmp = this.Value;
                            this.Value = left.Value;
                            left.Value = tmp;
                        }
                    }
                }
            }

            // value holded by this node
            public object Value
            {
                get { return nodeValue; }
                set { 
                    nodeValue = value; 
                }
            }

            // indicates if values were swaped when calling 'CompareSwap'
            public bool Swap
            {
                get { return swap; }
            }
        }

        public static void Sort(Array array, IComparer comparer)
        {
            // building the node single-linked list
            Node[] nodes = new Node[array.Length];
            nodes[0] = (Node) (new Node(comparer, null, array.GetValue(0))).GetProxy();
            for(int i = 1; i < array.Length; i++)
                nodes[i] = (Node) (new Node(comparer, nodes[i-1], array.GetValue(i))).GetProxy();

            // looping until no swap occurs any more
            bool swapOccured = true;
            while(swapOccured)
            {
                GThread[] threads = new GThread[array.Length - 1];

                // starting 'even' grid threads
                for(int j = 0; j < threads.Length; j += 2)
                {
                    threads[j] = (new GThread(new ThreadStart(nodes[j+1].CompareSwap))).GetProxy();
                    threads[j].Start();
                }

                // starting 'odd' grid threads
                for(int j = 1; j < threads.Length; j += 2)
                {
                    threads[j] = (new GThread(new ThreadStart(nodes[j+1].CompareSwap))).GetProxy();
                    threads[j].Start();
                }

                // joining and checking if a 'swap' occurred
                swapOccured = false;
                for(int j = 0; j < threads.Length; j++)
                {
                    threads[j].Join();
                    swapOccured |= nodes[j+1].Swap;
                }
            }

            // collecting the ordered values
            for(int i = 0; i < array.Length; i++)
            {
                array.SetValue(nodes[i].Value, i);
            }
        }
    }
}