Pages

Thursday, July 27, 2017

Pel Returns

Welcome » NERWous C » Pel
  1. Return Statement
  2. Release Statement
  3. Multi-Value Release
  4. Multi-Value Return


Return Statement

The return statement is used by a task to end itself with a return value. It is a combination of the <release> statement which does the value return, and the <end> statement which does the task ending. The <return> statement is the NERWous C embodiment of the C language return statement.

The return statement causes the ending task to generate a special return value, This return value is a readonly mel. By nature of a readonly mel, other tasks can all read this return value at the same time whenever it is made available, or wait for it if not yet available. By waiting on the return value of a task, the inquiring tasks can detect that the targeted task has ended, as the main task is doing below:
main () {
    <mel> int store;
    <pel> task_producer = <!> Producer (store);
    <pel> task_consumer = <!> Consumer (store);
    
    <?>task_producer;
    <terminate>task_consumer;
}
void Producer (<mel> int store) {
    while ( 1 ) {
        int c = produce();
        if ( c == 0 ) {
            <end>store;
            <return>;
        }
        <?>store = c;
    }
}
void Consumer ( int store) {
   while ( 1 ) {
     try {
         consume (store);
     }
     catch (pel<TERMED>) {
         printf ("I'm being terminated");
         return;
     }
   }
}
The wait that the main task is doing on <?>task_producer is the same pel feedback wait we have encountered in the previous Pel Endings chapter. This wait will be broken if the task_producer has ended via the <return> statement as seen in the Producer function code above.

Since the return signature of the function Producer is a void, the return value of task_producer is indefinite. Inquiring tasks can wait on this indefinite value to detect that a task has ended, but should not make use of it for any assignment or consumption. When there is no real value to be returned, the <return> statement acts simlarly like the <end> statement. This allows the same pel feedback wait to serve both statements.

Let's change the Producer function so that it returns an actual value to make the use of the <return> statement worthwhile:
main () {
    <mel> int store;
    <pel> task_producer = <!> Producer (store);
    <pel> task_consumer = <!> Consumer (store);
    
    printf ("Task Producer has ended with value [%d]", <?>task_producer);
    <terminate>task_consumer;
}
int Producer (<mel> int store) {
    while ( 1 ) {
    int c = produce();
        if ( c == 0 ) {
            <end>store;
            <return> c;
        }
        <?>store = c;
    }
}
The main task now waits for the Producer task to end, and also makes use of the return value (as seen in the printf function call).

Since the return value of a task is a readonly mel, multiple tasks can access it. For example, let's the Consumer task access the Producer return value too:
main () {
    <mel> int store;
    <pel> task_producer = <!> Producer (store);
    <pel> task_consumer = <!> Consumer (store, task_producer);
    
    printf ("Task Producer has ended with value [%d]", <?>task_producer);
    <?>task_consumer;
    printf ("Task Consumer has also ended");
}
int Producer (<mel> int store) {
    while ( 1 ) {
        int c = produce();
        if ( c == 0 ) {
            <close>store;
            <return> c;
        }
        <?>store = c;
    }
}
void Consumer (<mel> int store, <pel>tprod) {
    int c;
    while ( 1 ) {
      try {
        c = <?>(store || tprod);
        if ( c == 0 ) <end>;
        consume (c);
      }
      catch (store<CLOSED>) {
        printf ("I am ending due to a MEL CLOSURE");
        return;
      }
      catch (tprod<ENDED>) {
        printf ("I am ending due to the Producer having ended");
        return;
      }
    }
}
In this new version, the main task does not terminate the Consumer task any more. Instead, the latter will detect that the Producer has ended by accessing its return value, and then ends itself with its own <end> statement. With the statement <?>(store || tprod), the Consumer waits for either a value in the mel store, or the return value of the Producer task.

While both the main task and Consumer task wait on the return value of Producer, there is a difference between their wait. The wait from main is a single mel read wait while the wait from Consumer is a mel OR read wait. Normally Consumer waits on store being valued. However when Producer has ended, the store mel stops being valued; instead Consumer will pick up the return value of the ending Producer. When it sees the 0 value of the return value, the Consumer will explicitly ends with its own <end> statement.

Since the main does not invoke terminate on the Consumer task any more, the catch (pel<TERMED>) has been removed from the catch exception repertoire of the Consumer task. (It can be kept for reference but there is no event to trigger it.) It has been replaced by a new exception handling:
catch (tprod<ENDED>) {
    printf ("I am ending due to the Producer having ended");
    return;
}
There are now two methods for Consumer to detect that the Producer has ended: checking its return value via the pel feedback wait or getting the pel ENDED exception. With both methods present, the return value method takes precedence. The Consumer first determines if the return value is empty before it checks for any pel exception. In the Producer/Consumer example above, when the Producer ends, it generates a return value, causing the ENDED exception handler at Consumer not to be exercised.

Although playing a subservient role to the pel feedback wait, the ENDED exception handling is more general. It can handle the case where Producer has ended graciously with a proper return value, as well as the case where Producer has crashed without releasing any return value. As a matter of fact, we can remove the check for the 0-value (if ( c == 0) return) and make Consumer more succinct:
void Consumer (<mel> int store, <pel>tprod) {
    while ( 1 ) {
      try {
        consume ( <?>(store || tprod) );
      }
      catch (store<CLOSED>) {
        printf ("I am ending due to a MEL CLOSURE");
        return;
      }
      catch (tprod<ENDED>) {
        printf ("I am ending due to the Producer having ended");
        return;
      }
    }
}

Serial Return In Parallel

Sharp-eyed readers would notice that the exception handlers in the Consumer task use the C language return statement instead of the NERWous C <return> statement. This is done on purpose to illustrate that once a serial function is pelled to run in parallel, its return statement is transformed by the CHAOS runtime into the <return> statement. This allows simple functions to be invoked serially or in parallel, without having two versions:
int SimpleConsume (int c) {
    if ( !consume (c) ) return 1;    /* error from consume */
    return 0;    /* consume is successful */
}
int rescon;
rescon = SimpleConsume (10);    /* invoke serially */
rescon = <!> SimpleConsume (0);    /* pel to run in parallel */
In the second invocation, SimpleConsume runs as a pelled task. Its return statement then becomes <return> behind-the-scene. Without this automatic conversion, we would have to create a NERWous C version of SimpleConsume that used <return> in order to run it in parallel.

Parallel Return In Serial

Once a function makes use of the <return> statement, its invocation has unintended consequence when run serially:
int SimpleConsumeTask (int c) {
   if ( !consume (c) ) <return> 1;
   <return> 0;
}
main () {
    int rescon;
    rescon = <!> SimpleConsumeTask (0);    /* OK when pelled */
    rescon = SimpleConsumeTask (10);    /* Watch out when invoked */
}
The first invocation of <return> inside the task SimpleConsumeTask is what is intended - it ends this task and returns a value to the task main. The second invocation from a serial call to the function SimpleConsumeTask is done in the context of the main task, so when <return> is run in SimpleConsumeTask, it is not a return from that function, but a <return> from the main task, causing it to end.

Pel'N'Back Shortcut

This statement seems to be buggy:
rescon = <!> SimpleConsumeTask (0);
The left-hand-side of a pel <!> operator should be a pel variable, which rescon is not. However the above statement is all right since it is a shortcut of:

<pel> _p0 = <!> SimpleConsumeTask (0);
rescon = <?> _p0;
This shortcut is called pell'n'back because after pelling the task, the parent task immediately goes to the pel feedback wait. The required pel variable is not visible, it is created behind-the-scene, and is transient as a one-time use.

The pel'n'back shortcut is used when the code to be pelled has been written for task pelling, such as containing the <return> statement.

Return For Inline Code

Earlier, we see that return and <return> can be used interchangeably inside a pelled function. However if the pelled code is an inline block code, then only the NERWous C format of <return> is supported.

Let's put the Producer and Consumer functios as code blocks inside the main function:
main () {
    <mel> int store;
    
    /* Producer coded inline */
    <pel> task_producer = <!> {
        while ( 1 ) {
            int c = produce();
            if ( c == 0 ) {
               <end>store;
               <return inline> c;
            }
            <?>store = c;
        }
     }

    /* Consumer coded inline */
    <pel> task_consumer = <!> {
        while ( 1 ) {
          try {
             consume ( <?>(store || task_producer) );
          }
          catch (store<CLOSED>) {
             printf ("I am ending due to a MEL CLOSURE");
             <return>;
          }
          catch (task_producer<ENDED>) {
             printf ("I am ending due to the Producer having ended");
             <return>;
          }
        }
    }
        
    printf ("Task Producer has ended with value [%d]", <?>task_producer);
    <?>task_consumer;
    printf ("Task Consumer has also ended");
}
The serial format return are not permitted for the pelled inline codes because return works with functions and the inline code blocks are not functions.

The inline attribute used in the producer inline code is optional. It is a cosmetic reminder that the <return> statement is to be applied to the inline code block and not to the parent task (i.e. main). Since inline is cosmetic, the consumer inline code opts not to use it in its exception handlers. As a matter of style, it is recommended that the inline attribute should be used here as well.

The local variables store and task_producer are defined in the main task and passed over to the consumer inline task, as described in Local and Global Variables.


Release Statement

In the previous examples, we use the store mel variable to pass a product from the Producer task to the Consumer task. Another way is for the Producer to "stream" its products directly to the Consumer without using the store intermediary. This is supported by the NERWous C <release> statement:
main () {
    <pel> task_producer = <!> Producer ();
    <pel> task_consumer = <!> Consumer (task_producer);
    
    <?>task_producer<ENDED>;
    printf ("Task Producer has ended with value [%d]", <?>task_producer);
    <?>task_consumer<ENDED>;
    printf ("Task Consumer has ended");
}
int Producer () {
    while ( 1 ) {
        int c = produce();
        if ( c == 0 ) {
           <return> c;
        }
        <release> c;
    }
}
void Consumer (<pel>tprod) {
    try {
        consume (<?>tprod);
        <resume>;
    }
    catch (tprod<ENDED>) {
        printf ("I am ending due to the Producer having ended");
        return;
    }
}
The <release> statement writes to the same readonly mel return value used by the <return> statement. The difference is that <return> follows the mel write with a task ending, while the <release> lets the task resume processing. In the Producer code above, the task keeps invoking the release of newly produced items, until a zero-valued item is produced; at that time, the Producer task does a <return> on that last item.

The Consumer task gets newly produced items directly from the readonly mel return value of the Producer task. Instead of checking every time for a zero-valued item, it depends on the ENDED exception to know that the Producer task has ended.

The main task has a major change in how it detects that Producer has ended. Previously, it waits on the readonly mel return value of Producer since the latter only writes to this location once, at its end time. Now with this return value used as a streaming channel, main has to wait for Producer to have the ENDED status:
<?>task_producer<ENDED>;
The main task could still use the checking for the mel return value to detect the ending of Consumer since it only does a <return> and no <release>. However we also change the code for main to wait for the ENDED status of the Consumer task, to be consistent with the Producer detection.

The main task does the wait on the tasks ENDED status because it needs to do the printf statements. If it does not have to do printf, then there is no need for the explicit wait statements, and the main code would be simplified to:
main () {
    <pel> task_producer = <!> Producer ();
    <pel> task_consumer = <!> Consumer (task_producer);
}
After the two pel statements, the main task ends. When the Producer and Consumer tasks also end, the whole program exits.


Multi-Value Release

NERWous C supports a feature that is not part of the NERW Reference Model but can make writing some concurrent and serial programs easier: the capability to return multiple values. As we all know, the classic C language allows only one value to be returned.

Let's modify our example so that the Producer task produces one premium product for every 5 standard products, until over 1000 items are produced. We will have two consumer tasks, one to consume the premium products, and the other, the standard products:
main () {
    <pel> task_producer = <!> Producer ();
    <pel> task_consumer_std = <!> Consumer_Std (task_producer);
    <pel> task_consumer_prem = <!> Consumer_Prem (task_producer);
    
    <?>task_producer<ENDED>;
    printf ("Task Producer has ended with standard value [%d] and premium value [%d]", 
             <?>task_producer.std, <?>task_producer.prem);
    <?>task_consumer_std;
    <?>task_consumer_prem;
    printf ("Both Consumer tasks have ended");
}

(int prem, int std) Producer () {
    int count = 0;
    while ( count < 1000 ) {
        for (int i=0; i<5; ++i)
            <release name=std> produce_standard();
        <release prem> produce_premium();
        count += 6;
    }
    <release> (0, 0);
}
void Consumer_Std (<pel>tprod) {
    try {
        consume_std (<? name="std">tprod);
        <resume>;
    }
    catch (tprod<ENDED>) {
        printf ("I am ending due to the Producer having ended");
        return;
    }
}
void Consumer_Prem (<pel>tprod) {
    try {
        consume_prem (<? prem>tprod);
        <resume>;
    }
    catch (tprod<ENDED>) {
        printf ("I am ending due to the Producer having ended");
        return;
    }
}
The Producer now returns two readonly mel values, prem and std. These names are declared in the Producer function signature. The Producer task can release individual values by specifying their name, such as in:
<release name=std> produce_standard();
The name attribute can be omitted, as in:
<release prem> produce_premium();
When all the return values are specified, the <release> statement does not require the name attribute, as in:
<release> (0, 0);
Each Consumer task can wait for its own preferred product by specifying the name of the readonly mel value, as in consume_std (<? name=std>tprod) or consume_prem (<? prem>tprod).


Multi-Value Return

In the above example, the Producer task does a <release> with all the readonly mel values as the last statement in the function code block. Since it runs out of code to run, it will end. The equivalent is to use the <return> statement to signal the intention to terminate:
(int prem, int std) Producer () {
    int count = 0;
    while ( count < 1000 ) {
        for (int i=0; i<5; ++i)
            <release name=std> produce_standard();
        <release prem> produce_premium();
        count += 6;
    }
    <return> (0, 0);
}
Unlike the <release> statement, all the returned values of the function must be specified in a <return> statement. Any missing value will result in a syntax error during NERWous C translation time.

The multi-value feature is only supported for the NERWous C <return> statement. NERWous C leave it open for an implementation to extend that feature to standard C language <return> statement.


Previous Next Top

Wednesday, July 5, 2017

Pel Loops

Welcome » NERWous C » Pel
  1. Pel A Loop
  2. Loop Of Pels
  3. Loop Of Synchronous Pels
  4. Synchronous Loop Of Pels
  5. Pel A Loop Of Pels


Pel A Loop

In the following example, we will pel two tasks to run two serial while loops:
main () {
    <mel buffer=10> int store;
    <cel> fastcell;

    <! at=fastcell> {   // Producer inline task
        while ( 1 ) {   // to run this while loop in serial
            int c = produce();
            <?>store = c;
            if ( c == 0 ) <end>;
        }
    }

    <!> while ( 1 ) {    // Consumer inline task
        int c = <?>store;
        if ( c == 0 ) <end>;
        consume (c);
    }
}
There are 3 tasks in the above program. The main task pels a task to do production, and another task to do consumption. The while loops inside the pelled tasks are run serially, with one item produced at a time, and one item consumed at a time. The mel store is the communication channel between the two tasks. It has a buffer to allow the producer, which runs at a faster cel node (via the fastcel at attribute), to minimize waiting for the intermittently slower consumer task to catch up.

The consumer task uses the abbreviated form of the pel statement. It omits the enclosing { and } brackets of the pel statement <!> since there is only one statement (the while loop) inside the pel code block.

The producer task uses the standard form of the pel statement with both encapsulating { and } brackets. Although more verbose, it can support other statements before and after the while loop. For example, for monitoring purpose, we can include some sandwiching printf statements:
<! at=fastcel> {
    printf ("Before while loop\n");
    while ( 1 ) {    // to run this while loop in serial
        int c = produce();
        <?>store = c;
        if ( c == 0 ) <end>;
    }
    printf ("After while loop\n");
 }

We can replace the while loop with a do-while loop:
main () {
    <mel buffer=10> int store;
    <cel> fastcell;

    <! at=fastcel> {   // Producer inline task
        printf ("Before do-while loop\n");
        do {
            int c = produce();
            <?>store = c;
            if ( c == 0 ) <end>;
        }  while ( 1 );
        printf ("After do-while loop\n");
    }

    <!> do {    // Consumer inline task
        int c = <?>store;
        if ( c == 0 ) <end>;
        consume (c);
    }  while ( 1 );
}
The above example uses the <end> statement to break out of the do-while loops. This statement also ends the inline task. For the Consumer task, both activities are the same, since there is nothing else Consumer does after breaking out of the loop. For the Producer task, the <end> statement prevents the execution of the closing printf. The remedy is to use the C language's break statement:
    <! at=fastcel> {   // Producer inline task
        printf ("Before do-while loop\n");
        do {
            int c = produce();
            <?>store = c;
            if ( c == 0 ) break;
        }  while ( 1 );
        printf ("After do-while loop\n");
    }
After break'ing, the Producer task does the printf, and without any other activity programmed, the task just ends.


Loop Of Pels

Unlike the pel-a-loop method which pels a single task, the loop-of- pels method is a serial loop that pels a new task with each iteration. The number of tasks created is equal to the number of loop iterations. While the tasks are created one at a time, the loop iterations usually run fairly fast on modern machines, which gives the impression that the tasks are being created at the same time. Once the tasks are created, they run in parallel with one another.

Do-While Loops

Let's modify our do-while example to have the producing tasks producing exactly 3 items, to be stored separately, using 3 different producers. We also have 3 different consumers:
#define NUMITEMS 3
main () {
    <mel> int stores[NUMITEMS];
    <cel> producer[NUMITEMS] = { {"Producer 1"}, {"Producer 2"}, {"Producer 3"} };
    <cel> consumer[NUMITEMS] = { {"Consumer 1"}, {"Consumer 2"}, {"Consumer 3"} };

    int n = 0;
    do {
        <! at=producer[n]> {
            <?>stores[n] = produce();
        }
    } while ( ++n < NUMITEMS );    

    n = 0;
    do <! at=consumer[n]> {
       consume (<?>stores[n]);
    } while ( ++n < NUMITEMS );
}
To separate the products, we use the mel array stores. Each producer is represented by its own cel element.

The main task finishes the do-while loop for production before starting the do-while loop for consumption. Unless the runtime primitive to create a task is very demanding, both loops can be ripped through quickly. In a blink of time, we can have 7 tasks running: the main task, 3 producing tasks and 3 consuming tasks.

Like the producing tasks, the consuming tasks are assigned to specific cels, but for consumption. A consuming task may be already running while the product it is supposed to consume, is still being produced by the corresponding producing task. In this case, the consuming task will suspend itself at the mel wait, <?>stores[n], for the product to show up.

The local variable n is an interesting fellow. As discussed in the chapter on local variables, there are in total 6 instances of n in the above example. The instances belonging to the main task are shown in red below:
   int n = 0;
    do {
        <! at=producer[n]> {
            <?>stores[n] = produce();
        }
    } while ( ++n < NUMITEMS );    

    n = 0;
    do <! at=consumer[n]> {
       consume (<?>stores[n]);
    } while ( ++n < NUMITEMS );
On the other hand, the instance of n in:
<?>stores[n] = produce();
belongs to the producer inline tasks. Since there are 3 producing tasks, there are 3 different instances of n, each localized to a particular task. All these localized instances get their initial value from the instance in the main task at the time of the pelling.

Likewise, we have 3 instances of n for the consuming tasks. If we were to change n within a task, like:
   do <! at=consumer[n]> {
       consume (<?>stores[n]);
       n = 0;
    } while ( ++n < NUMITEMS );
that change would only be applicable to the instance n of that consuming task. It would not affect the instance of n in the while statement which belongs to the main task.

In the above examples, the producing tasks use the standard form of a loop of pels, while the the consuming tasks use the abbreviated form. The standard form allows codes to sandwich the task pelling, and run in the context of the pelling task. For example:
   do {
        printf ("Begin creating task for [%d]\n", n);
        <! at=producer[n]> {
            <?>stores[n] = produce();
        }
        printf ("Request for task [%d] submitted\n", n);
    } while ( ++n < NUMITEMS );    

While Loops

Let's now replace the do-while loops with while loops.
#define NUMITEMS 3
main () {
    <mel> int stores[NUMITEMS];
    <cel> producer[NUMITEMS] = { {"Producer 1"}, {"Producer 2"}, {"Producer 3"} };
    <cel> consumer[NUMITEMS] = { {"Consumer 1"}, {"Consumer 2"}, {"Consumer 3"} };

    int n = 0;
    while ( ++n <= NUMITEMS ) {
        printf ("Begin creating task for [%d]\n", n);
        <! at=producer[n]> {
            <?>stores[n] = produce();
        }
        printf ("Request for task [%d] submitted\n", n);
    }    

    n = 0;
    while ( ++n <= NUMITEMS )
    <! at=consumer[n]> {
       consume (<?>stores[n]);
    }
}
The post-pel printf statement says "Request for task [%d] submitted" -- "submitted" and not "created", because the pel statement is asynchronous. As long as the request to create a task has been accepted by the CHAOS runtime, the main task can return from the pel statement to iterate the while loop. The submitted task will be created in due time by CHAOS.

For Loops

Let's now replace the while loops with for loops.
#define NUMITEMS 3
main () {
    <mel> int stores[NUMITEMS];
    <cel> producer[NUMITEMS] = { {"Producer 1"}, {"Producer 2"}, {"Producer 3"} };
    <cel> consumer[NUMITEMS] = { {"Consumer 1"}, {"Consumer 2"}, {"Consumer 3"} };
 
    for ( int n = 0; n < NUMITEMS; ++n ) {
        printf ("Begin creating task for [%d]\n", n);
        <! at=producer[n]> {
            <?>stores[n] = produce();
        }
        printf ("Request for task [%d] submitted\n", n);
    }   

    for ( int n = 0; n < NUMITEMS; ++n )
    <! at=consumer[n]> {
       consume (<?>stores[n]);
    }
}
Again, the producer task uses the standard form and the consumer task, the abbreviated form for loops of pels.


Loop Of Synchronous Pels

The previous loop examples pel the task asynchronously. Once the pel requests have been accepted by the CHAOS runtime, the looping task can resume its looping endeavor without waiting for the pelled tasks to have been actually created. We now change the for loop example to use synchronous task creation method to allow the looping task to make sure that the pelled tasks have been actually created.
#define NUMITEMS 3
main () {
    <mel> int stores[NUMITEMS];
    <pel> prods[NUMITEMS];
    <pel> conss[NUMITEMS];
    <cel> producer[NUMITEMS] = { {"Producer 1"}, {"Producer 2"}, {"Producer 3"} };
    <cel> consumer[NUMITEMS] = { {"Consumer 1"}, {"Consumer 2"}, {"Consumer 3"} };

    /* Producer inline block */

    int tries;
    for ( int n = 0; n < NUMITEMS; ++n ) {
        printf ("Begin creating Producer task [%d]\n", n);
 
        tries = 0;
        prods[n] = <! at=producer[n] timeout> {
            <?>stores[n] = produce();
        }
        if ( prods[n]<status> == NERW_STATUS_FAILED ) {
            printf ("EXIT LOOP - Task [%d] failed to be created due to [%s]\n", 
                n, prods[n]<why>);
            <close> stores;
            break;
        }
        else if ( prods[n]<status> == NERW_STATUS_TIMEOUT ) {
            if ( ++tries < 2 ) {
                printf ("RETRY after 1st TIMEOUT\n");
                <resume>;
            }
            else {
                printf ("STOP TRYING after 2nd TIMEOUT\n");
                continue;
            }
        }
            
        printf ("End creating Producer task for [%d]\n", n);
    }
    
    /* Consumer inline block */
    
    for ( int n = 0; n < NUMITEMS; ++n ) {
        conss[n] = <! at=consumer[n]> {
            try {
                int tries = 0;
                consume (<?>stores[n]);
            }
            catch ( stores[n]<CLOSED> ) {
                printf ("STOP TRYING -- The producer for [%d] item may have FAILED", n);
                <end>;
            }
            catch ( stores[n]<TIMEOUT> ) {
                if ( ++tries < 2 ) {
                    printf ("RETRY after 1st TIMEOUT\n");
                    <resume>;
                }
                else {
                    printf ("STOP TRYING after 2nd TIMEOUT\n");
                    <end>;
                }
            }
        }
        if ( conss[n]<status> == NERW_STATUS_FAILED ) {
            printf ("Consumer task [%d] failed to be created due to [%s]\n", 
                n, conss[n]<why>);
            continue;
        }
    }
}
For the producer tasks, an array of pel elements, <pel> prods[NUMITEMS], are declared. They are used to receive the result of the pel statement executions:
prods[n] = <! at=producer[n] timeout> { ... }
By assigning a pel variable to a pel creation statement, the main task indicates that it is willing to wait to make sure that its request for the new task has been fulfilled (successfully or not). Via this synchronizing handshake, the main task can check for the two errors that could possibly happen during a task pelling: a failure error and a timeout error. These errors are detected by checking the <status> property in which CHAOS reports the outcome of the pelled task creation.

NERW_STATUS_FAILED

This status means that CHAOS has not been able to create the task. The main task decides to abort any further attempt to pel the rest of the tasks. It closes the mel stores, then invokes the C statement break to immediately get out of the serial for loop.

What happens to the producing tasks that the main task has been able to create before issuing the break statement? If they have produce'd a value to their stores[n] mel item, these values will be lost when main issues the <close> store command. At this time, main still runs the for loop for the producing tasks, and have not started the for loop for the consuming tasks; therefore there are no tasks to consume these produced values.

For producing tasks that have been created before the break statements but have not valued their stores[n], they continue to produce. However, when they try to deposit the produced item to stores[n], they will catch a mel CLOSED exception. For simplicity, we have not programmed in a try / catch handling for the producing tasks. These tasks then end with an abortion on the unhandled CLOSED exceptions.

NERW_STATUS_TIMEOUT

For the producing tasks, the main task handles the TIMEOUT status differently than the FAILED status. First it tries to wait some more. The <resume> statement jumps the processing flow back to the latest mel or pel statement, which in this case, is the pel creation statement, allowing the main task to repeat the task pelling:
<! at=producer[n] timeout>
The timeout attribute without any value means that the main task is willing to wait the default amount of milliseconds before abandoning the wait for the pel creation. At that time, the CHAOS runtime also aborts any pel creation work even if it is already partially successful.

On timeout of the 2nd retry, the main task aborts the attempt to pel the task, and continues its iteration to pel the next task. While the NERWous C <resume> statement jumps the processing back to the pel statement <! statement, the C language continue jumps the processing all the way to the for loop statement.

Consumer Tasks

How does a consuming task know if its corresponding producing task has been created or not? It does not care about this knowledge. What the consuming task cares is to access the mel stores[n] for a reading. If the reading times out, then the consuming task runs its own TIMEOUT exception handler. The TIMEOUT exception may be due to the slowness of the CHAOS runtime at that moment, or to the slowness of the corresponding producing task to generate a value, or to the producing task not being able to be created on the first place, such as it has "hung".

The "tries" Local Variables

Note that there are two tries local variables mentioned in the above example. They are separate and unrelated. The first one belongs to the main task, and is used for the pelling of the producing tasks. The second one is in the context of each consuming task, and is used in the access of the mel variable stores[n]. Thus, there are NUMITEMS + 1 instances of the tries variable when this program runs: one for main, and one for each of the NUMITEMS consuming tasks.


Synchronous Loop Of Pels

In the previous example, we have the main task waits for the pel tasks to be created before it continues. Now we will extend this wait so that main will wait for all the tasks to be actually finished before it continues:
#define NUMITEMS 3
main () {
    <mel> int stores[NUMITEMS];
    <pel> prods[NUMITEMS];
    <pel> conss[NUMITEMS];
    <cel> producer[NUMITEMS] = { {"Producer 1"}, {"Producer 2"}, {"Producer 3"} };
    <cel> consumer[NUMITEMS] = { {"Consumer 1"}, {"Consumer 2"}, {"Consumer 3"} };

    /* Producer inline block */

    int tries;
    <collect> for ( int n = 0; n < NUMITEMS; ++n ) {
        printf ("Begin creating Producing task [%d]\n", n);
 
        tries = 0;
        prods[n] = <! at=producer[n] timeout> {
            <?>stores[n] = produce();
        }
        if ( prods[n]<status> == NERW_STATUS_FAILED ) {
            printf ("EXIT LOOP - Task [%d] failed to be created due to [%s]\n", 
                n, prods[n]<why>);
            <close> stores;
            break;
        }
        else if ( prods[n]<status> == NERW_STATUS_TIMEOUT ) {
            if ( ++tries < 2 ) {
                printf ("RETRY after 1st TIMEOUT\n");
                <resume>;
            }
            else {
                printf ("STOP TRYING after 2nd TIMEOUT\n");
                continue;
            }
        }
            
        printf ("End creating Producing task for [%d]\n", n);
    } <? ENDED>;
    printf ("All the Producing tasks have ended\n");
    
    /* Consumer inline block */
    
    <collect> for ( int n = 0; n < NUMITEMS; ++n ) {
        conss[n] = <! at=consumer[n]> {
            try {
                int tries = 0;
                consume (<?>stores[n]);
            }
            catch ( stores[n]<CLOSED> ) {
                printf ("STOP TRYING -- The producer for [%d] item may have FAILED", n);
                <end>;
            }
            catch ( stores[n]<TIMEOUT> ) {
                if ( ++tries < 2 ) {
                    printf ("RETRY after 1st TIMEOUT\n");
                    <resume>;
                }
                else {
                    printf ("STOP TRYING after 2nd TIMEOUT\n");
                    <end>;
            }
        }
        if ( conss[n]<status> == NERW_STATUS_FAILED ) {
            printf ("Consuming task [%d] failed to be created due to [%s]\n", 
                n, conss[n]<why>);
            continue;
        }
    } <? ENDED>;
}
By using the wrapper construct <collect> { ... } <? ENDED>, the main task asks the CHAOS runtime to monitor all the tasks pelled between the wrapper. The main task will wait at the <? ENDED> until all the collected tasks have ended.

In the above example, the parallelism is more muted than in previous examples. There are no producing tasks running in parallel with any consuming tasks. All the inline producing tasks are pelled then run to completion before the main task pels the inline consuming tasks. The above example still has more parallelism than a pure serial program -- the produce and consume funtions are executed in parallel via their corresponding for loop of pels.


Pel A Loop Of Pels

In the previous section, we have the producing tasks not running in parallel with the consuming tasks because we want to collect the status of all the producing runs before letting the consuming tasks run. Let us modify that example to have these tasks run in parallel again, while keeping the status collection. We'll do this by combining the pel-a-loop method with the loop-of-pels method:
#define NUMITEMS 3
main () {
    <mel> int stores[NUMITEMS];
    <pel> prods[NUMITEMS];
    <pel> conss[NUMITEMS];
    <cel> producer[NUMITEMS] = { {"Producer 1"}, {"Producer 2"}, {"Producer 3"} };
    <cel> consumer[NUMITEMS] = { {"Consumer 1"}, {"Consumer 2"}, {"Consumer 3"} };

    /* Producer inline block */

    int tries;
    <?> {
        <collect> for ( int n = 0; n < NUMITEMS; ++n ) {
            printf ("Begin creating Producing task [%d]\n", n);
 
            tries = 0;
            prods[n] = <! at=producer[n] timeout> {
                <?>stores[n] = produce();
            }
            if ( prods[n]<status> == NERW_STATUS_FAILED ) {
                printf ("EXIT LOOP - Task [%d] failed to be created due to [%s]\n", 
                    n, prods[n]<why>);
                <close> stores;
                break;
            }
            else if ( prods[n]<status> == NERW_STATUS_TIMEOUT ) {
                if ( ++tries < 2 ) {
                    printf ("RETRY after 1st TIMEOUT\n");
                    <resume>;
                }
                else {
                    printf ("STOP TRYING after 2nd TIMEOUT\n");
                    continue;
                }
            }

            printf ("End creating Producing task for [%d]\n", n);
        } <? ENDED>;
        printf ("All the Producing tasks have ended\n");
     }
     
    /* Consumer inline block */
    
    <!> {
        <collect> for ( int n = 0; n < NUMITEMS; ++n ) {
            conss[n] = <! at=consumer[n]> {
                try {
                    int tries = 0;
                    consume (<?>stores[n]);
                }
                catch ( stores[n]<CLOSED> ) {
                    printf ("STOP TRYING -- The producer for [%d] item may have FAILED", n);
                    <end>;
                }
                catch ( stores[n]<TIMEOUT> ) {
                    if ( ++tries < 2 ) {
                        printf ("RETRY after 1st TIMEOUT\n");
                        <resume>;
                    }
                    else {
                        printf ("STOP TRYING after 2nd TIMEOUT\n");
                        <end>;
                }
             }
             if ( conss[n]<status> == NERW_STATUS_FAILED ) {
                 printf ("Consuming task [%d] failed to be created due to [%s]\n", 
                    n, conss[n]<why>);
                 continue;
             }
        } <? ENDED>;
    }
}
The number of tasks that are created is as follows. First the main task is created. It then pels two pel-a-loop tasks, one for production, the other for consumption. Once the pellings are done, the main task ends.

The pel-a-loop task for production then pels NUMITEMS tasks, one for each iteration of its for loop. The pel-a-loop task for consumption does the same, and its NUMITEMS loop-of-pels tasks run in parallel with those from the production side. Once they have pelled all of their tasks, the pel-a-loop tasks (one for production, one for onsumption) wait for their own pelled tasks to finish via the wait statement <? ENDED>. These waits are done in parallel because they are done by concurrent tasks.

Once all the tasks pelled from the for loops have ended, the pel-a-loop parent tasks are woken up from their <? ENDED> waits, do their post-for-loop processing if any, then end. Their endings allow the NERWous C program to exit.


Previous Next Top

Thursday, June 29, 2017

Pel Setup

Welcome » NERWous C » Pel
  1. Pel Attributes
  2. Import Attributes
  3. Timeout Attribute
  4. At Attribute
  5. Mode Attribute
  6. Name Attribute
  7. Priority Attribute
  8. Pel Variable


Pel Attributes

As introduced in the Pel Basic chapter, a pel creation statement accepts attributes:
OperationAttributesSynopsis
<!>code at
=cel
Request that code runs on the specific cel
import
=list-of-vars
Transfer the values of specific global variables to the created task
import-file
=list-of-files
Transfer the values of specific global variables in the listed files to the created task
mode
=setting
Request that the task be created with this mode: suspend (create then suspend execution), quickstart (create faster than normal), maintenance (create in maintenance mode for diagnostic messages), running (create and wait for the task to run)
name
=usn
Assign a unique user-specified name so the task can be referred to without knowing the system-generated task ID.
priority
=n
Request that code runs at the n-th priority level
timeout
=t
(Synchronous mode only) Request that the task be created within t msec.
<start>p Start a suspended task.
<suspend>p Suspend a running task.
<update>p name=usn Update the local properties of task p. If the name attribute is specified, update p from the task named with the specified user-specified name.
<terminate>p Request that the task p be terminated.
<kill>p Force the task p to end immediately.


Import Attributes

The import and import-file attributes are discussed in earlier chapter and chapter.


Previous Next Top

Monday, June 19, 2017

A MapReduce Example

Welcome » NERWous C » Examples
  1. Current Literature
  2. NERWous C Sample


Current Literature

MapReduce is a programming model that uses parallel algorithms to process big data sets using a large number of distributed computer nodes, The data flows through a MapReduce framework through five processing steps:
  • Input step: the data is read into the framework as (key 1, value 1) input data pairs.
  • Map step:the input data pairs are grouped into (key 2, value 2) domain data pairs.
  • Partition step: the domain data pairs are associated with the processing computer node.
  • Reduce step: the computer node processes all associated domain data pairs.
  • Output step: the results of the reduce step are collected to produce the final outcome.
Within each step, parallel processing occurs as much as possible. The steps themselves, although logically forming a processing sequence, can also be run in parallel, interleaving with one another as long as the same final outcome is produced


NERWous C Sample

The example is taken from the MapReduce Wikipedia page. The goal is to count the appearance of every word in a set of documents.

In the NERWous C code below, mel variables are used to pass data between the steps. Parallelism occurs inside the steps, but from step to step, it is sequential programming.
#include "nerw.h"

typedef char word[50] WORD;

/* Input data pair */.
typedef struct { char filename[64]; char line[256]; } INPUT_PAIR;
<mel>INPUT_PAIR InputPairs[];

/* Domain data */
typedef struct { WORD word; int count; } MAP_PAIR;
<mel>MAP_PAIR MapPairs[];

/* Partition data */
typedef struct { WORD word; char celid; } PARTITION_PAIR;
<mel>PARTITION_PAIR PartitionPairs[];

/* Output data pair */
typedef struct { WORD word; int count; } OUTPUT_PAIR;
<mel>OUTPUT_PAIR OutputPairs[];

/* Run the MapReduce steps */

void main (int argc, char **argv) {

   /* Read in the directory containing the files to be processed */
   char directory[MAX_PATH];    
   snprintf (directory, MAX_PATH, "%s", argv[1]);

   /* Invoke the steps sequentially */
   input_step (directory);
   map_step ();
   partition_step();
   reduce_step();
   output_step();
}

/* INPUT STEP:
** Read a directory full of text files and return each line as a record.
*/

void input_step (char *directory) {
   struct dirent *file;
   DIR *dir = opendir (directory);
    
   /* Run the INPUT step.
   ** The while loop sequentially goes through the directory.
   ** It skips subfolders, and processes files only.
   ** Each file is processed separately in its own sub-task.
   ** The INPUT step waits for all the sub-tasks to end before returning.
   */
   <collect> while ( (file = readdir(dir)) ) {
      if (file->d_type == DT_DIR) continue;
      <!> input_task (file->d_name);
      }      
   } <? ENDED>;
}

void input_task (char *filename) {
   FILE *fp = fopen(filename, "r");
   if (fp == NULL) return;

   char * line = NULL;
   size_t len = 0;
   ssize_t read;
    
   /* Read a file and collect all the lines in a [INPUT_PAIR] data pairs.
   ** Run the collection in parallel just to showcase the use of parallelism. 
   ** Sequential while loop may be faster in this case, due to the task setup cost.
   ** 
   ** Wait for all the collection tasks to finish with the collect-ENDED block.
   */
    <collect> while ((read = getline(&line, &len, fp)) != -1) {
      <!> {
         INPUT_PAIR inputpair;
         strcpy (inputpair.filename, filename);
         strcpy (inputpair.line, line);
         <insert item=inputpair> InputPairs;
      }
   } <? ENDED>;
}

/* MAP STEP:
** Break the line into separate words. 
** Each broken word has its own MAP_PAIR with count of 1.
** Similar words are not aggregated.
*/

void map_step () {
   int numitems = InputPairs<count>;
   for (int i=0; i<numitems; ++i)
   <!> {
      map_task (<?readonly>InputPairs[i]);
   }
}

void map_task (INPUT_PAIR inputpair) {
   WORD *wordarr[] = split(inputpair.line, " ");
   int numitems = sizeof(wordarr)/sizeof(WORD);
   <collect> for (int i=0; i<numitems; ++i)
   <!> {
       MAP_PAIR mappair;
       strcpy (mappair.word, wordarr[i]);
       mappair.count = 1;
       <insert item=mappair> MapPairs;
   } <? ENDED>;
}

/* PARTITION STEP:
** Allocate each word to a cel node for the Reduce step.
** The method chosen is to allocate based on the first character of the word.
** This method is not very efficient since some nodes will be loaded while others are not.
*/

<cel> nodes[26] = { 
{"A"}, {"B"}, {"C"}, {"D"}, {"E"}, {"F"}, {"G"}, {"H"},
{"I"}, {"J"}, {"K"}, {"L"}, {"M"}, {"N"}, {"O"}, {"P"},
{"Q"}, {"R"}, {"S"}, {"T"}, {"U"}, {"V"}, {"W"}, {"X"},
{"Y"}, {"Z"}};

void partition_step () {
   MAP_PAIR mappair;
   int numitems = MapPairs<count>;
   <collect> for (int i=0; i<numitems; ++i)
   <!> {
       partition_task (<?readonly>MapPairs[i].word);
   } <? ENDED>;
}

void partition_task (WORD aword) {
   PARTITION_PAIR partipair;
   partipair.word = aword;
   partipair.celid = uppercase(aword[0]);
   <insert item=partipair> PartitionPairs;
}

/* REDUCE STEP
** Count each word using the assigned cel.
*/

void reduce_step ()
   PARTITION_PAIR partipair;
    
   /* Run the [reduce_task] using the cel node identified in the Partition Pair.
   ** Wait for all tasks to finish their run before continuing.
   */
   int numitems = PartitionPairs<count>;
   <collect> for (int i=0; i<numitems; ++i) {
      partipair = <?readonly> ParititionPairs[i];
      <! at=partipair.celid> reduce_task (partipair.word);
   } <? ENDED>;
    
   /* Get exclusive access to the mel [OutputPairs], sort in place, and unlock it. */
   <?> OutputPairs {
      qsort(OutputPairs, OutputPairs<count>, sizeof(OUTPUT_PAIR), cmpfunc);
   }
}

int cmpfunc (OUTPUT_PAIR *a, OUTPUT_PAIR *b) {
   return a-<word[0] - b-<word[0];
}

void reduce_task (WORD aword) {
   OUTPUT_PAIR outputpair;
    
   /* For a given word, see if an Output Pair already exists or not.
   ** If it is, increment the count. If it is not, create a new Output Pair.
   ** The [found] mel variable is set if an existing Output Pair is found.
   ** If [found] still remains 0 after checking exiting Output Pairs, create a new one.
   */
   <mel> int found = 0;
   int numitems = OutputPairs<count>;
   <collect> for (int i=0; i<numitems; ++i)
   <!> {
       <? as=outputpair> OutputPairs[i] {
           if (!strcmp(outputpair.word, aword)) {
               ++outputpair.count;
               <?readonly> found = 1;    /* replace the value of found to 1 */
               <checkout replace>;
           }
       }
   } <? ENDED>;
    
   if ( <?> found == 0 ) {
      strcpy (outputpair.word, aword);
      outputpair.count = 1;
      <insert item=outputpair> OutputPairs;
   } 
}

/* OUTPUT STEP:
** Show all the word counts.
*/

void output_step ()
   int numitems = OutputPairs<count>;

   /* Use a sequential loop to guarantee that the output are printed in order */
   for (int i=0; i<numitems; ++i) {
      output_task (<?readonly>OutputPairs[i]);
   }
}

void output_task (OUTPUT_PAIR outputpair) {
   printf ("%s = %d", outputpair.word, outputpair.count);
}


Previous Next Top

Friday, April 28, 2017

A Thread Programming Example

Welcome » NERWous C » Examples
  1. Current Literature
  2. NERWous C Sample


Current Literature
Thread programming is one of the most popular way to write concurrent programs within a computer. It does not depend on a concurrent programming language. Instead it uses a serial programming language (such as C or C++), and invokes concurrency-enabling functions from a thread library. The library interacts with the operating system to time-share a single CPU into slices of executions or threads. A multi-core computer can distribute the threads into the CPU cores, thus boosting the concurrency and resulting in potentially higher performance.

This example comes from the School of Computer Science and Informatics of Cardiff University. It exercises the thr_create() library call to create multiple threads and thr_join() call to join them back at a later time. The source code of the example is copied verbatim below. The source page has an explanation of each thread.
#define _REENTRANT
#include <stdio.h>
#include <thread.h>

/* Function prototypes for thread routines */
void *sub_a(void *);
void *sub_b(void *);
void *sub_c(void *);
void *sub_d(void *);
void *sub_e(void *);
void *sub_f(void *);

thread_t thr_a, thr_b, thr_c;

void main()
{
    thread_t main_thr;

    main_thr = thr_self();
    printf("Main thread = %d\n", main_thr); 

    if (thr_create(NULL, 0, sub_b, NULL, THR_SUSPENDED|THR_NEW_LWP, &thr_b))
        fprintf(stderr,"Can't create thr_b\n"), exit(1);

    if (thr_create(NULL, 0, sub_a, (void *)thr_b, THR_NEW_LWP, &thr_a))
        fprintf(stderr,"Can't create thr_a\n"), exit(1);

    if (thr_create(NULL, 0, sub_c, (void *)main_thr, THR_NEW_LWP, &thr_c))
        fprintf(stderr,"Can't create thr_c\n"), exit(1);

    printf("Main Created threads A:%d B:%d C:%d\n", thr_a, thr_b, thr_c); 
    printf("Main Thread exiting...\n"); 
    thr_exit((void *)main_thr);
}

void *sub_a(void *arg)
{
    thread_t thr_b = (thread_t) arg;
    thread_t thr_d;
    int i;

    printf("A: In thread A...\n"); 

    if (thr_create(NULL, 0, sub_d, (void *)thr_b, THR_NEW_LWP, &thr_d))
        fprintf(stderr, "Can't create thr_d\n"), exit(1);

    printf("A: Created thread D:%d\n", thr_d); 

    /* process 
    */
    for (i=0;i<1000000*(int)thr_self();i++);
    printf("A: Thread exiting...\n"); 
    thr_exit((void *)77);
}

void * sub_b(void *arg)
{
    int i;

    printf("B: In thread B...\n"); 

    /* process 
    */

    for (i=0;i<1000000*(int)thr_self();i++);
    printf("B: Thread exiting...\n"); 
    thr_exit((void *)66);
}

void * sub_c(void *arg)
{
    void *status;
    int i;
    thread_t main_thr, ret_thr;

    main_thr = (thread_t)arg;

    printf("C: In thread C...\n"); 

    if (thr_create(NULL, 0, sub_f, (void *)0, THR_BOUND|THR_DAEMON, NULL))
        fprintf(stderr, "Can't create thr_f\n"), exit(1);

    printf("C: Join main thread\n"); 

    if (thr_join(main_thr,(thread_t *)&ret_thr, &status)) 
        fprintf(stderr, "thr_join Error\n"), exit(1);

    printf("C: Main thread (%d) returned thread (%d) w/status %d\n", main_thr, ret_thr, (int) status); 

    /* process 
    */

    for (i=0;i<1000000*(int)thr_self();i++);
    printf("C: Thread exiting...\n"); 
    thr_exit((void *)88);
}

void * sub_d(void *arg)
{
    thread_t thr_b = (thread_t) arg;
    int i;
    thread_t thr_e, ret_thr;
    void *status;

    printf("D: In thread D...\n"); 

    if (thr_create(NULL, 0, sub_e, NULL, THR_NEW_LWP, &thr_e))
        fprintf(stderr,"Can't create thr_e\n"), exit(1);

    printf("D: Created thread E:%d\n", thr_e); 
    printf("D: Continue B thread = %d\n", thr_b); 

    thr_continue(thr_b);
    printf("D: Join E thread\n"); 

    if(thr_join(thr_e,(thread_t *)&ret_thr, &status)) 
        fprintf(stderr,"thr_join Error\n"), exit(1);

    printf("D: E thread (%d) returned thread (%d) w/status %d\n", thr_e, 
    ret_thr, (int) status); 

    /* process 
    */

    for (i=0;i<1000000*(int)thr_self();i++);
    printf("D: Thread exiting...\n"); 
    thr_exit((void *)55);
}

void * sub_e(void *arg)
{
    int i;
    thread_t ret_thr;
    void *status;

    printf("E: In thread E...\n"); 
    printf("E: Join A thread\n"); 

    if(thr_join(thr_a,(thread_t *)&ret_thr, &status)) 
        fprintf(stderr,"thr_join Error\n"), exit(1);

    printf("E: A thread (%d) returned thread (%d) w/status %d\n", ret_thr, ret_thr, (int) status); 
    printf("E: Join B thread\n"); 

    if(thr_join(thr_b,(thread_t *)&ret_thr, &status)) 
        fprintf(stderr,"thr_join Error\n"), exit(1);

    printf("E: B thread (%d) returned thread (%d) w/status %d\n", thr_b, ret_thr, (int) status); 
    printf("E: Join C thread\n"); 

    if(thr_join(thr_c,(thread_t *)&ret_thr, &status)) 
        fprintf(stderr,"thr_join Error\n"), exit(1);

    printf("E: C thread (%d) returned thread (%d) w/status %d\n", thr_c, ret_thr, (int) status); 

    for (i=0;i<1000000*(int)thr_self();i++);

    printf("E: Thread exiting...\n"); 
    thr_exit((void *)44);
}

void *sub_f(void *arg)
{
    int i;

    printf("F: In thread F...\n"); 

    while (1) {
        for (i=0;i<10000000;i++);
        printf("F: Thread F is still running...\n"); 
    }
}

NERWous C Sample

The NERWous C version follows the original thread-reentrant version as closely as possible. Three global pel variables, PEL_a, PEL_b, PEL_c, are the NERWous C equivalent of the global thread_t variables, thr_a, thr_b, thr_c: They represent the first three tasks (A, B, C). The subsequent tasks (D, E, F) are then pel'led (i.e. created) from those first three tasks.
<pel>PEL_a, PEL_b, PEL_c;

void main() {
    PEL_b = <! name="PEL_B" mode=suspend>sub_b();
    PEL_a = <! name="PEL_A">sub_a(PEL_b);
    PEL_c = <! name="PEC_C">sub_c(pel);

    printf("Main created threads A:%d B:%d C:%d\n", PEL_a<id>, PEL_b<id>, PEL_c<id>); 
    printf("Main thread %d exiting...\n", pel<id>); 
}

int sub_a (<pel> pel_b) {
    printf("A: In thread A...\n"); 

    <pel>pel_d = <!>sub_d (pel_b);
    printf("A: Created thread D:%d\n", pel_d<id>); 

    /* process */
    for (int i=0;i<1000000*(int)pel<id>;i++);

    printf("A: Thread exiting...\n"); 
    return 77;
}

int sub_b () {
    printf("B: In thread B...\n"); 

    /* process */
    for (int i=0;i<1000000*(int)pel<id>;i++);

    printf("B: Thread exiting...\n"); 
    return 66;
}

int sub_c (<pel> pel_main) {
    printf("C: In thread C...\n"); 

    try { <pel>pel_f = <!>sub_f(); }
    catch (pel_f<FAILED>) { fprintf(stderr, "Can't create thread F\n"); return 1; }
    
    printf("C: Wait for main thread\n"); 
    <? ENDED>pel_main;
    printf("C: Main thread (%d) exits w/state %d\n", pel_main<id>, pel_main<state>); 

    /* process */
    for (int i=0;i<1000000*(int)pel<id>;i++);

    printf("C: Thread exiting...\n"); 
    return 88;
}

int sub_d (<pel> pel_b) {
    int ret;
    printf("D: In thread D...\n"); 

    try { <pel>pel_e = <!>sub_e (); }
    catch (pel_e<FAILED>) { fprintf(stderr,"Can't create thread E\n"), return 0; }
    printf("D: Created thread E:%d\n", pel_e<id>); 

    printf("D: Start B thread = %d\n", pel_b<id>);  
    <start>pel_b;

    printf("D: Wait for E thread\n");
    ret = <?>pel_e;
    printf("D: E thread (%d) returned value (%d) w/state %d\n", pel_e<id>, ret, pel_e<state>);

    /* process */
    for (inti=0;i<1000000*(int)pel<id>;i++);

    printf("D: Thread exiting...\n"); 
    return 55;
}

int sub_e()
{
    int ret;
    printf("E: In thread E...\n"); 

    printf("E: Wait for A thread\n"); 
    <update name="PEL_A">PEL_a;
    try { ret = <?>PEL_a; }
    catch ( PEL_a<FAILED> ) {
       fprintf(stderr,"wait Error\n");
       return(1);
    }
    printf("E: A thread (%d) returned value (%d) w/state %d\n", PEL_a<id>, ret, PEL_a<state>); 

    printf("E: Wait for B thread\n"); 
    <update name="PEL_B">PEL_b;
    try { ret = <?>PEL_b; }
    catch ( PEL_b<FAILED> ) {
       fprintf(stderr,"wait Error\n");
       return(1);
    }
    printf("E: B thread (%d) returned value (%d) w/state %d\n", PEL_b<id>, ret, PEL_b<state>); 
  
    printf("E: Wait for C thread\n"); 
    <update name="PEL_C">PEL_c;
    try { ret = <?>PEL_c; }
    catch ( PEL_c<FAILED> ) {
       fprintf(stderr,"wait Error\n");
       exit(1);
    }
    printf("E: C thread (%d) returned value (%d) w/state %d\n", PEL_c<id>, ret, PEL_c<state>); 

    /* process */
    for (int i=0;i<1000000*(int)pel<id>;i++);

    printf("E: Thread exiting...\n"); 
    return 44;
}

The main task pells the task B in suspend mode. The task B is created by main but does not run until task D (sub_d) invokes the pel operation start on task B. This is equivalent to the thr_continue library call in the thread-reentrant version.

The task A carries the pel presentation of task B in its pel argument pel_b. The main task initializes this argument with value from the global variable PEL_b at the time of pelling. Task A then transfers this value to task D so that it can start the suspended task B.

The task B is created and then immediately suspended by the main task. Once woken up (started by task D), it will spin a unique number of iterations based on its own task ID (pel<id>). The other tasks are doing the same spinning but using their own unique task ID.

The task C waits for the main task to complete by waiting on the return of that task (<?>pel_main). The return of a task is a read-only mel variable; being a mel, it allows waiting via the wait operator (<?>). This is equivalent to the thread library call thr_join which "suspends processing of the calling thread until the target thread completes".

The task D uses the pel operation start to start the suspended task B. The start operation is equivalent to the library function thr_continue used by the thread-reentrant version. This library call "resumes the execution of a suspended thread".

The task E makes use of the three global variables PEL_a, PEL_b, and PEL_c which are initialized all the way back in the main task. Based on the way NERWous C handles global variables, they are re-created in the context of the task E the first time that the sub_e code encounters them. However they are created un-initialized. One way to initialize them would be to carry their values from main to task A then task D then task E, via the import or import-file attribute. Since these global variables are pel variables, task E has another option -- which it uses here. Task E invokes the update operation on the pel variables in order to pull the necessary values of the task in real time. The update operation depends on finding the tasks. This is done via the name attribute, which the main task uniquely gives to the tasks that it pells.

An astute reader will notice that task E does not need to use global variables. Running an update operation on local pel variables will work just as well. The global variables are used to more closely match the thread-reentrant version which has them.


Previous Next Top

Monday, March 6, 2017

Local and Global Variables

Welcome » NERWous C » Pel
  1. Local Variables
  2. Global Variables
  3. Import Attribute
  4. Import-File Attribute
  5. Array Variables
  6. Mel Variable Properties


Local Variables

In the previous chapter, we say that in order to run something in parallel, we just pel it with the <!> construct. Actually, things are not that simple. For example, can we use local variables from the parent task? Let's take a look at this serial program:
/* VERSION 1 */
#define MAX 100
main () {
    int store[MAX];
    int counter;

    /* Producer first */
    counter = MAX;
    while ( --counter )
     store[counter] = Produce();

    /* Consumer next */
    counter = MAX;
    while ( --counter ) 
        Consume(store[counter]);
}
This contrived example uses a local variable, counter. It is used first in the Producer code to load the array store with Produced items. It is then used again in the Consumer code to unload the store array to Consume.

Let's change the Producer and Consumer codes to run in parallel, and see how the local variable counter behaves.
/* VERSION 2 */
#define MAX 100
main () {
    int counter = MAX;
    <mel buffer=counter/10> int store;

    <!> {    /* Producer task */
        while ( --counter ) 
            <?>store = Produce();
    }

    <!> {    /* Consumer task */
        while ( --counter ) 
            Consume(<?>store);
    }
}
First we transform the store array into a mel variable so that it can be shared between the Producer task and Consumer task. To increase concurrency, we give it a buffer with an arbitrary size of 10% of the number of iterations maintained by counter. Then we consecutively pel the code blocks for Producer and Consumer. The main task then ends. The whole program will exit at a later time when the Producer and Consumer tasks have also ended.

The item of interest here is the local variable counter. It appears in both pelled tasks. Unlike the serial VERSION 1 example, the value of counter when it gets to the Consumer task is still MAX as originally set by main. The reduction of counter in the Producer task (via the statement --counter) is done separately in that task and does not impact the counter in the main task. In fact, there are three distinct local counter variables in the VERSION 2 example, one for main, one for Producer, and one for Consumer.

During compile time, the NERW translator will analyze any block of code that is under the pel <!> construct. Any local variables from the pelling code (which is main here) that are re-used in the pelled code, will be duplicated in the pelled tasks. The values of the duplicated local variables will be the same as of the ones of the pelling code at the time of the pelling. This is why Consumer has its own counter variable and it is valued with the MAX value, same as Producer.

Let's look at another version:
/* VERSION 3 */
#define MAX 100
main () {
    int counter = MAX;
    int numtasks = 0;
    <mel buffer=counter/10> int store;

    <!> {    /* Producer task */
        while ( --counter )
            <?>store = Produce();
    }
    ++numtasks;

    <!> {    /* Consumer task */
        printf ("This is task [%]", numtasks);
        while ( --counter )
            Consume(<?>store);
    }
    ++numtasks;

    printf ("Waiting for %d pelled tasks to terminate", numtasks);
}
Like counter, numtasks is also a local variable of main. Unlike counter though, numtasks is not used in the Producer pelled code block. Thus, the NERWous C translator during compilation time will not generate behind-the-scene code to duplicate this variable for the Producer task. On the other hand, the Consumer pelled code block does use numtask. The NERWous C translator can detect this use during compilation, and will generate code to create a separate numtask local variable for the Consumer task. It also initializes this local variable with the value of numtask from the main task at the time of the pelling (which is 1 in the example above).

To support local variables, the compile-time NERWous C translator needs to be able to:
  1. re-create any local variables from the pelling task to the pelled task if they also appear in the pelled code as right-hand-side values,
  2. initialize these created local variables with the values of the eponymous local variables from the pelling task at the time of pelling.
An implementation of the NERWous C translator may initialize all duplicated local variables intead of just the ones used in the right-hand side. Such implementation may make sense in a single-server multi-threaded environment where local variables in a stack can be copied in bulk from one threaded task to another threaded task. For tasks that are distributed in separate nodes, especially over a wide area network, the cost of transferring data to initialize un-needed left-hand-side local variables may impact performance. Thus, the requirement for the NERWous C translator is to initialize only right-hand-side local variables.

Let's rewrite the above example, replacing code blocks by functions:
/* VERSION 4 */
#define MAX 100
main () {
    int counter = MAX;
    int numtasks = 0;
    <mel buffer=counter/10> int store;

    /* Producer task */
    <!>Producer (store, counter);
    ++numtasks;

    /* Consumer task */
    <!>Consumer (store, counter, numtasks);
    ++numtasks;

    printf ("Waiting for %d pelled tasks to terminate", numtasks);
}

void Producer (mel int store, int counter) {
    while ( --counter ) 
        <?>store = Produce();
}

void Consumer (mel int store, int counter, numtasks) {
    printf ("This is task [%]", numtasks);
    while ( --counter ) 
        Consume(<?>store);
}

With the Producer and Consumer tasks encapsulated in functions, whatever local variables from the main task are needed, have to be explicitly passed as functional arguments. Again, the values of the arguments are the values of the local variables of the pelling task at the time of pelling. In the example above, counter has the value of MAX for both Producer and Consumer tasks, and numtasks has the value of 1 on entry of the Consumer task.


Global Variables

In the previous examples, we look at local variables. In the following examples, let's consider global variables with pel statements. We start with a serial C program that contains three global variables:
/* VERSION 5 */
#define MAX 100
int Counter;
int Item;
int Version = 5;
main () {
    int store[MAX];

    /* Producer first */
    Counter = MAX;
    while ( --Counter ) {
        Item = Produce ();
        store[Counter] = Item;
        REPORT ("Producing");
    }

    /* Consumer next */
    Counter = MAX;
    while ( --Counter ) {
        Item = store[Counter];
        Consume(Item);
        REPORT ("Consuming");
    }
}

function REPORT (action) {
    printf ("Version [%d]: Action [%s], Counter [%d] Item [%d]\n", Version, action, Counter, Item);
}
The three global variables, Version, Counter and Item, are used so that we don't need to pass them to the REPORT function as arguments. (This may not be a good way to write a computer program, but we need something simplistic to discuss the complex issue of global variables.)

Now let's rewrite the Producer and Consumer code blocks to run in parallel:
/* VERSION 6 - BUGGY */
#define MAX 100
int Version = 6;
int Counter = MAX;
int Item;
main () {
    <mel buffer=counter/10> int store;

    /* Producer task */
    <!> while ( --Counter ) {
       Item = Produce ();
       <?>store = Item;
       REPORT ("Producing");
    }

    /* Consumer task */
    <!> while ( --Counter ) {
       Item = <?>store;
       Consume(Item);
       REPORT ("Consuming");
    }
}

function REPORT (action) {
    printf ("Version [%d]: Action [%s], Counter [%d] Item [%d]\n", Version, action, Counter, Item);
}
Like local variables, the global variables are automatically made available in the pelled tasks. The above example contains 3 sets of Version, Counter and Item The first set is in the main task, the second in the Producer task, and the third in the Consumer task. Each set is independent to each other, and is used for localized global access within a task only.

In NERWous C, a global variable is different from a memory element (mel) variable. A global variable is globally accessible in the compile-time scope, while a mel variable is globally accessible in the run-time scope. A compile-time scope means that a global variable can be accessed anywhere in the program: it is declared once and any block of code or function can refer to it with the help of the language compiler. A run-time scope means that a mel variable can be shared by different tasks that are forked (or in NERWous C parlance, pelled) during the running of the program. The shared access is provided by the CHAOS runtime environment. In the example above, the mel variable store is shared between the Producer task and the Consumer task. Note that store is declared as a local variable and not as a global variable for the compile-time scope.

This is how the NERWous C translator handles global variables at compile time:
  1. The translator collects the types and names of all global variables in the pelling task.
     
  2. When the translator first sees a variable in a pelled task and this variable is not a local variable, the translator automatically creates a global variable in the pelled task environment, using the type of the eponymous global variable collected from the pelling task.
     
  3. While the translator automatically re-creates global variables for pelled tasks, the translator does not automatically initialize them, unless the global variables are included in the import or import-file attribute.
The reason the translator does not do automatic initialization of re-created global variables for pelled tasks, while local variables are both re-created and initialized, is due to performance.

It can be hard to detect what global variables a pelled task will use, since global variables can appear in functions called deep in the execution thread starting from the first level of the pelled task. This differs from local variables where they only appear in the first level of a pelled code block -- which is easier to detect. Automatically initializing all global variables during run-time for any created pel task even if it never makes use of all of them, will likely impact the performance of a concurrent NERWous C program, especially when the tasks are distributed over a wide area network, and some global variables contain huge data.

The NERWous C translator will automatically create global variables in pelled tasks as they are needed, but initializes them only on demand, via the import or import-file attribute. In the example above, neither of these attributes is used, resulting in the program being "buggy". For example, the global variable Counter is re-created in the Producer and Consumer tasks, but neither of these copies are initialized. Thus the statement:
while ( --Counter ) {
will fail because Counter is undefined.

The import feature allows the pelling task to send data to the pelled task to initialize global variables. There is no export feature for the pelled task to update back the global variables in the pelling task. For this, the global variables must be declared as mel variables.


Import Attribute

Let's fix the above "buggy" example by making use of the import attribute to the pel <!> statement:
/* VERSION 7 */
#define MAX 100
int Version = 7;
int Counter = MAX;
int Item;
main () {
    <mel buffer=counter/10> int store;

    /* Producer task */
    <! import="Version,Counter"> while ( --Counter ) {
       Item = Produce ();
       <?>store = Item;
       REPORT ("Producing");
    }

    /* Consumer task */
    <! import="Version,Counter"> while ( --Counter ) {
       Item = <?>store;
       Consume(Item);
       REPORT ("Consuming");
    }
}

function REPORT (action) {
    printf ("Version [%d]: Action [%s], Counter [%d] Item [%d]\n", Version, action, Counter, Item);
}
The import attribute to the pel construct <!> instructs the NERWous C translator to generate behind-the-scene code to re-create the specified global variables (i.e. Version and Counter) in the pelled task, and to also initialize them with the current values of the same-named variables from the pelling task.

The global variable Item is not in the import list and is not created at the time of the pel statement. Only when the NERWous C translator encounters Item the first time in the Producer code block (or Consumer code block), then it will create a global variable for Item localized for the pelled task. That means that the Item created for the Producer task is different from the one created for the Consumer task, and both of them different from the one declared in the main task. The only sameness between these different global variables is the type (which is int) that the NERWous C translator knows from parsing the whole program.

Global variables, like Item, that are created on a needed basis, will not be initialized. The current values in the pelling task are not transferred to the pelled task. This is beneficial, not detrimental. In the example above, there is no need to transfer the value of Item over from the pelling task, and have the pelled task overrides it with the result of Produce() or the value of the mel store. Via the import attribute, the programmer can specify only the global variables whose values need to be transferred over.

What happens if the programmer forgets a global variable in the import list, such as in this code fragment:
<! import="Counter">
Since Version is not imported, it is created uninitialized on a needed basis. On the above example, this will be when the function REPORT is invoked. The printf will display the indeterminate value of the uninitialized Version, instead of the static value 7 from the main task.

The import and import-file (to be introduced next) attributes support one-way transfer of data from the pelling task to the pelled task, Any changes that the pelled task does to its copy of the global variables stay with the pelled task and not copied back to the pelling task. If this update is desired, then the global variables should be declared as mel global variables whom read/write access is shared to multiple tasks, including the pelling task.


Import-File Attribute

The import attribute is fine when we have a few global variables to transfer over. When the list grows long, it becomes hard to maintain. In this case, it may be better to put this list into a separate file and use the import-file attribute to the <!> pel statement.

In this import file, procon.h, we introduce the global variables to be imported with the C language extern:
/* procon.h */
extern int Version;
extern int Counter;
Let's modify our example to use procon.h:
/* VERSION 8 */
#define MAX 100
int Version = 8;
int Counter = MAX;
int Item;
main () {
    <mel buffer=counter/10> int store;

    /* Producer task */
    <! import-file="procon.h"> while ( --Counter ) {
       Item = Produce ();
       <?>store = Item;
       REPORT ("Producing");
    }

    /* Consumer task */
    <! import-file="procon.h"> while ( --Counter ) {
       Item = <?>store;
       Consume(Item);
       REPORT ("Consuming");
    }
}

function REPORT (action) {
    printf ("Version [%d]: Action [%s], Counter [%d] Item [%d]\n", Version, action, Counter, Item);
}
To find the location of procon.h the NERWous C translator follows the same resolution rule used by the C preprocessor for handling:
#include "procon.h"

The same file inclusion works similarly when the pelled tasks are encapsulated as functions:
/* VERSION 9 */
#define MAX 100
int Version = 9;
int Counter = MAX;
int Item;
main () {
    <mel buffer=counter/10> int store;

    /* Producer task */
    <! import-file="procon.h"> 
        Producer (store);

    /* Consumer task */
    <! import-file="procon.h"> 
        Consumer (store);
}

void Producer (mel int store) {
    while ( --Counter ) {
        Item = Produce ();
        <?>store = Item;
        REPORT ("Producing");
    }
}

void Consumer (mel int store) {
    while ( --Counter ) {
       Item = <?>store;
       Consume(Item);
       REPORT ("Consuming");
    }
}

function REPORT (action) {
    printf ("Version [%d]: Action [%s], Counter [%d] Item [%d]\n", Version, action, Counter, Item);
}
For both the Producer and Consumer tasks, their localized version of the global variables Counter and Version are created and initialized with the values from the main task right at the pel <!> statement. However they are not put to use until the execution flows into the Producer or Consumer function.

We can import multiple files with the import-file attribute:
<! import-file="file1.h, file2.h">

We can mix the import-file attribute with the import attribute:
<! import-file="file1.h, file2.h" import="var1, var2">
The imported files usually contain groups of global variables that are commonly imported by many tasks, while the individual imported global variables are specific to a certain task.


Array Variables

The previous examples use simple data types for the global variables. Now let's explore the use of arrays as variables, either local or global. If the whole array is to be imported to the pelled task, then an array variable is behaving no differently than a simple-typed variable. What interesting is the import facility allowing the transfer of a subset of the array to a pelled task.

Let's modify the above example again:
/* VERSION 10 */
#define MAX 100
#define BUNCH 5
int Version = 10;
int Counter;
int Item;
main () {
    int store[MAX];

    /* Producer task - run in serial */
    for (Counter=0; Counter<MAX; ++Counter) {
       Item = Produce ();
       store[Counter] = Item;
       REPORT ("Producing");
    }  

    /* Consumer task - run in parallel */
    for (int i=0; i<MAX; i += BUNCH)
    <! import="Version, store[i] ... store[i+BUNCH-1]"> {
       for (Counter=i; Counter<i+BUNCH; ++Counter) {
          Item = store[Counter];
          Consume (Item);
          REPORT ("Consuming");
       }
    }
}

function REPORT (action) {
    printf ("Version [%d]: Action [%s], Counter [%d] Item [%d]\n", Version, action, Counter, Item);
}
First, the mel array store is converted to a local array variable. The Producer then seeds this array with a seqential for loop. Once the array is seeded, it will be consumed in parallel, in a BUNCH items at a time. The main task uses the LIST (...) construct:
store[i] ... store[i+BUNCH-1]
to pass BUNCH items for the pelling task to use.

Note the use of the local variable i in these three consecutive lines:
    for (int i=0; i<MAX; i += BUNCH)
    <! import="Version, store[i] ... store[i+BUNCH-1]"> {
       for (Counter=i; Counter<i+BUNCH; ++Counter) {
The i variables appearing in the outer for statement and the import attribute are the same, and reside in the main task. On the other hand, the i used in the for loop belongs to the corresponding pelled task, and each pelled task has its own local version of i. Although they reside in different tasks than the main task, they get initialized with the value of the i variable of the main task at the time of the task creation.

We "cheat" a little bit in the previous example by making MAX divisible to BUNCH so that we don't have to worry the last iteration not having all BUNCH number of store elements. Let's update the pelling code to handle this boundary condition:
/* Consumer task - run in parallel */
    for (int i=0; i<MAX; i += BUNCH) {
        int upperbound = i+BUNCH-1;
        if ( upperbound >= MAX ) upperbound = MAX-1;
        
        <! import="Version, store[i ... upperbound]"> {
          for (Counter=i; Counter<=upperbound; ++Counter) {
              Item = store[Counter];
              Consume (Item);
              REPORT ("Consuming");
          }
        }
    }
Like the i variable, upperbound is also a local variable. This allows it to be automatically duplicated to the pelled task and be used there without much ado.


Mel Variable Properties

The properties of a mel variable are information about that mel variable that are cached locally in the requesting task so that they don't have to be constantly retrieved from the remote mel location. The mel properties of a mel variable have the same compile-time local or global scope as of that mel variable:
<mel> int store1;
main () {
    <mel> int store2;
    printf ("In [main], store1 buffer is [%d]", store1<buffersize>);
    printf ("In [main], store2 buffer is [%d]", store2<buffersize>);
 
    <!> {
        printf ("In pelled task, store1 buffer is [%d]", store1<buffersize>);
        printf ("In pelled task, store2 buffer is [%d]", store2<buffersize>);
    }
}
The store2 variable is declared as a local variable, and so are its properties. The properties of store2 are therefore automatically transferred from the main task to the pelled task. The printf statemetns for store2 will show the same buffer size.

Interestingly, both printf statements for store1 also show the same buffer size, even though store1 is a global variable. Its properties are thus also global, and we have been said that global variables are not initialized automatically in the pelled task. What was said is correct for regular variables, but not true for mel properties.

When the store1 is created in the statement:
<mel> int store1;
its properties are initialized with the current information of the newly created mel entity. The NERWous C translator, during compile time, sees that the main task makes use of the store1 variable, and so it adds an implicit import operation of store1 into main. This import is executed at run-time when main is created.

When main pels the inline task, the properties cache that main currently maintains for both store1 and store2 will be passed to the inline task. Let's expand the above example:
<mel> int store1;
main () {
    <mel> int store2;
    printf ("In [main], store1 buffer is [%d]", store1<buffersize>);
    printf ("In [main], store2 buffer is [%d]", store2<buffersize>);
    <rebuffer buffer+10> store1;
    <rebuffer buffer+10> store2;

    <!> {
        printf ("In pelled task, store1 buffer is [%d]", store1<buffersize>);
        printf ("In pelled task, store2 buffer is [%d]", store2<buffersize>);
    }
}
The printf statements now show different values. While those from main show the original buffer sizes of the mel variables, the ones from the pelled task show the buffer sizes as having been incremented by 10 due to the rebuffer operations. These values are what main have in the properties caches when it pels the inline task.

The reason for mel properties to be treated the same for both local and global scopes with automatic initialization is that the information on how to access the remote mel must be passed to the tasks so that they can do mel operations such as reads and writes. The rest of the properties thus piggy-backs on that. If programmers have to explicitly specify the import attribute for global mel variables every time they make use of the pel <!> statement, a NERWous C program would become unwieldy.

How about performance? Unlike regular variables which contain data, mel properties only contain metadata (i.e. the properties). The real data of a mel is stored centrally in the cel that hosts that mel. The local properties cache of each mel variable is quite manageable, and can be transferred to a pelled task without undue impact on performance.


Previous Next Top