Rebel Science News
11/28/2012
Jeff Hawkins Is Close to Something Big
 
8/26/2012
The Myth of the Bayesian Brain
 
8/23/2012
The Second Great AI Red Herring Chase
 
8/15/2012
Rebel Speech Recognition Theory
 
8/8/2012
Rebel Speech Update
 

COSA Parallel QuickSort Example

 

 

 
Rebel Science Home
Why Software Is Bad
Project COSA
Operating System
Software Composition
Parallel QuickSort
The Devil's Advocate
COSA Discussion Forum
Not Associated with V.S. Merlot, Inc.
Contact Me

 

Abstract
Introduction
Sequential QuickSort
Parallel COSA QuickSort
  Qsort
  Loop
  Sort
  Launch
  Swap
   

Abstract: The following is a description of how a QuickSort  component can be constructed using the inherent parallelism of COSA components. Please note that this example is preliminary and was quickly put together in order to show that COSA can handle general-purpose, fine-grain parallelism. An actual COSA QuickSort would use supervisor or control components (not used here) and plain data connectors. See COSA: A New Kind of Programming for more.

Introduction

Newcomers to COSA are invariably surprised to learn that a comparison operation can be performed only when a change occurs that may affect the comparison. The reason is that the COSA software model is based on change. Comparison operators are sensors that detect specific changes in their assigned data. Comparisons are therefore never invoked directly as is normally done in conventional programming languages. Note that, since a comparison sensor must have access to the result of its previous comparison in order to determine whether or not a change has occurred, a special case exists when a component is first created. Upon creation, every sensor assumes by default that its previous test result was false. Note also that, after creation, a COSA component is inactive (asleep) and must be explicitly activated (awakened) in order to do anything. Every component has a special effector cell set aside for that purpose. A sensor can be specifically configured so that it immediately performs its comparison when its parent component is awakened.

Keep these things in mind while reading the rest of this page. Also, remember that, unlike certain so-called concurrent languages (e.g., Erlang), COSA is implicitly parallel. Components and cells are inherently concurrent. Sequential order is explicit, however. The designer must specify whether or not two operations must occur in a specific order. That's the difference between a true parallel programming environment and a sequential language that is advertised as being concurrent.

Sequential QuickSort

The normal QuickSort algorithm relies heavily on recursion to repeat the same function on portions of the array being sorted. This is what makes QuickSort such a nice candidate for parallel processing. Since the algorithm always operates on an independent part of the array, in a parallel environment, it makes sense to launch multiple copies of the same algorithm and have them work on the problem simultaneously. Below is a color-coded integer QuickSort algorithm written in C++. I assigned a different color to each part of the algorithm that will be implemented in a separate COSA component. 

 

Swap void swap(int *a, int *b)
{
   
int t;
    t=*a;
    *a=*b;
    *b=t;
}
 
QSort  void quickSort(int array[], int begin, int end)
{
    if (end > begin + 1)
    {
        int pivot, left, right;
        pivot = array[begin];
        left = begin + 1;
        right = end;
Loop         while (left < right)
        {
Sort             if (array[left] <= pivot)
            {
                left++;
            }
            else
            {
                right--;
                swap(&array[left], &array[right]);
            }
Loop         }
QSort         left--;
        swap(&array[left], &array[begin]);
Launch         quickSort(array, begin, left);
        quickSort(array, right, end);
QSort     }
}

Parallel COSA QuickSort

As seen below, the COSA QuickSort component consists of five sub-components: the QSort, the Loop, the Swap, the Sort and the Launch. Unlike some concurrent programming languages that try to minimize side effects between processes by copying everything on the message queue, COSA components do share memory via their message connectors. There is actually no absolute necessity to create a separate Swap component but it is always good to encapsulate things neatly. One of the reasons for using several sub-components has to do with the way comparison cells work in COSA. For example, if I had combined the Loop and Sort components into a single component, the (left < right) comparison would be triggered every time a change is made to either left or right. There are times when a comparison operation is not needed and it would impair performance if it were allowed. The solution is to place the comparison in a separate component and wake it up only when it is needed. Thus the first thing that happens when Loop is awakened by QSort is the (left < right) comparison (actually, there are two comparison cells in Loop but more on this later). A programmer must be careful about when to change a variable because the change may trigger a sensor at the wrong time. Timing constraints in COSA are so strict that it would trigger an error somewhere.

The main difference between the sequential QuickSort and the COSA QuickSort has to do with the recursive calls. While recursion is possible in COSA with the use of a stack component, in this case, it is better to take advantage of the inherent parallelism. The QSort component uses the Launch component, which, in turn, uses a special effector cell (Dup and Launch) to launch more QuickSort components to work concurrently on the left and right unfinished parts of the array. Ideally, for the sake of performance, the system should retain a number of these components in memory and simply reuse them when necessary. The end result is fast parallel sorting. Please refer to the COSA System and Software Composition pages for more info on components, cells and connectors.

 

One of COSA's forte is that it facilitates good program comprehension. Labels are created by the developer and can be in any language. No more cryptic code that only computer geeks can fall in love with. Note also that COSA components are plug-compatible. What this means is that all the sub-components in the QuickSort component know how to connect themselves to one another automatically and safely. Just drag them from the component library and drop them into the application. The newly formed QuickSort component can, in turn, be added to the library for easy reusability and experimentation in various applications. Eventually, once a comprehensive library of basic components is established, drag and drop programming will become the norm rather than the exception. Programming for the masses!

Loop Component

The Loop component is rather simple. It contains only three cells. The (!!) cell is the activation effector. When it receives a start signal (small white circle), it wakes up the component and the two comparison sensors perform their respective comparisons simultaneously. If the effector receives a stop signal (small black circle), the component goes back to sleep. Note that, when the component wakes up, only one sensor can fire because they are opposite. When either sensor fires, it sends out a Done or Not Done signal and the component goes back to sleep. The left and right variables are part of the data in memory that is shared with the other components via the message connectors. Both connectors are multi-connectors. The left one is connected to the QSort component and the top one to the Sort component. The arrangement of the cells and the connectors in a component is left to the designer's discretion.

Loop

while (left < right)
{
    DO-SORT();
}

 

Remark that, in a full development environment, Loop components will be part of a comprehensive library of pre-created components. Programming a loop will be mostly a matter of dragging and dropping. The same goes for the Swap component. In fact, the entire integer QuickSort component will be available for easy reuse.

QSort Component

The QSort component is a bit more complex but not by much. It looks a little crowded but only because I chose to keep things small for the web page. Click on the image to enlarge it. In a COSA editor, everything can be as big as desired and cells and connectors can be moved around and placed anywhere. Also, labels can be turned on and off. Constructing the QSort component is mostly a matter of dragging in some connectors, sensors and effectors, assigning their respective operations and data, and linking them together. Note that after the end > val comparison is done, three variables are initialized simultaneously. The developer does not need to specify this because parallelism is implicit in COSA. The COSA environment will automatically assign them to the available CPU cores for parallel processing. Immediately afterwards, the Loop component is sent a signal. After Loop is done, it is Swap's turn and then the Launch component is called. When Launch returns, the array is fully sorted, the QSort component goes back to sleep and return a signal that it's finished.

 
Click to enlarge

QSort

void quickSort(int array[], int begin, int end)
{
    val = begin + 1;
    if (end > val)
    {
        int pivot, left, right;
        pivot = array[begin];
        left = val;
        right = end;
        DO-LOOP();
        left--;
        DO-SWAP();
        DO-LAUNCH();
    }
    else
        DONE;
}       

 

Sort Component

The Sort component gets called as often as necessary by the Loop component, that is, while left is less than right. Note that, unlike so-called concurrent languages, parallelism is assumed in COSA. By contrast, sequential order must be specified by the designer.

 

Sort

if (array[left] <= pivot)
{
    left++;
}
else
{
     right--;
     swap(&array[left], &array[right]);
}

Launch Component

In the sequential QuickSort algorithm, two successive recursive calls are made. By contrast, in a parallel QuickSort component, two new parallel QuickSort components are launched simultaneously and both immediately start running concurrently. Each may, in turn, launch other components to work on independent parts of the array. Since there is no way to tell which of the two launched components is going to be done first, a special (ALL) detector is used to detect when both have returned. At that point, the sort is considered completed. The Dup and Launch effector (D&L) interacts directly with the COSA operating system to create a new QuickSort component (if one is not already available) somewhere in memory (it does not matter where). It copies any specified data from the current component to the new component, starts the new component and returns a signal when the new component is done processing. Every component has a unique ID that identifies its type. Note that the only variables that need to be copied are array, begin and end. The newly created QuickSort components will run concurrently and independently of each other.

Launch

quickSort(array, begin, left);
quickSort(array, right, end);

Swap Component

The Swap component is used by the QSort and the Sort modules. This means that there is a possibility of conflict. What if Swap is invoked simultaneously by both? If that happened, COSA's Principle of Motor Coordination would be applied. In case of conflict, the solution is to either redesign the client components to eliminate the possibility of conflicts or to use cloned targets, whichever is more appropriate. Luckily for us, neither the QSort nor the Sort component will ever invoke swap simultaneously. Otherwise, it might have been necessary to use two Swap components. One cool thing about COSA components is the cloned message effector (sorry, this is not yet documented on the COSA System page). Essentially, if a designer needs to connect multiple clients to a single target component but only one matching connector is available on the target, the designer has the option of cloning either the target component or the connector. Doing the former ensures that there will be no conflicts. Doing the latter saves memory space but the designer is forced to organize things so as to eliminate the possibility of conflict. Whenever a message arrives on a cloned connector, it changes the message pointer accordingly.

In this example, the Swap component uses two cloned connectors. However, for the sake of clarity, only one is shown when the component is opened up. Note also that, even though the example uses three consecutive steps, it is possible to do it in two steps in COSA by using two intermediate variables instead of one. I will leave it as an exercise for the reader to solve.

 
void swap(int *a, int *b)
{
    int t;
    t=*a;
    *a=*b;
    *b=t;
}

 

2007 Louis Savain

Copy and distribute freely