Mel Arrays

Welcome » NERWous C » Mel

1. Mel Arrays
2. Mel Array Value Property
3. Mel Array Closures
4. Mel Array Status Property
5. Mel Array Exceptions
6. Mel Array Boundary Exceptions
7. Mel Array Count Property
8. Mel Array Boundary Behaviors
9. Mel Array Consecutive Constructs
10. Mel Array OR Wait Examples
11. Mel Array AND Wait Examples
12. Mel Array LIST Wait Examples

---

Mel Arrays

So far in our previous examples, the mel variable is a single entity (for simplicity, we have chosen it to be an integer). Now let's explore how to handle a collection of mel entities of the same type using the mel array construct. In the new example below, we will have the Producer produces a series of products to be consumed:

#define NUMITEMS 30
#define NUMROUNDS 5
main () {
     <mel> int stores[NUMITEMS];
     <!>Producer (stores);
     <!>Consumer (stores);
}
/* PRODUCER VERSION 1 */
void Producer (<mel> int stores[]) {
     int round = 0;
     while (1) {
         for (int i=0; i<NUMITEMS; ++i) 
         <!collect> {
             <?>stores[i] = produce();
         } <? ENDED>;
         printf ("Done with round [%d]\n", round);
         if (++round >= NUMROUNDS) break;
     }
     <close>stores;
}

The main program forks the task Producer to run in parallel with the task Consumer. Within Producer, the tasks to produce are also run in parallel via the for-pel loop. Unlike a serial for loop, it is possible with the for-pel loop to have a stores[i+1] produce'd before a stores[i] since the produce'ing tasks may be assigned to different cels with different performance and load.

The value i is passed from the Producer task to each produce inline task via the automatic local variable import facility.

The tasks Producer and Consumer share the access to the mel array stores. Each element within a mel array is an independent mel entity. They are produced and consumed separately from one another. For example, the for-pel task for stores[i] may be suspended to wait for a consumer to retrieve that value and free the mel array item for a new write, while the for-pel task for stores[i+1], working with a faster consumer, has no problem depositing its product to its mel array item.

By using the collect-ENDED construct, the task Producer waits for all the inline tasks it pels to be finished. This marks the end of the first round. Producer then starts the second round with a new set of for-pel tasks. After NUMROUNDS rounds, the Producer task is done. Before ending itself, it calls the close operation on the mel array stores to inform any Consumer tasks of no more forthcoming products.

---

Mel Array Value Property

Let's now use the Consumer task to explore the value property for a mel array.

/* CONSUMER VERSION 1 */
void Consumer (<mel> int stores[]) {
   for (int i=0; i<NUMITEMS; ++i)
   <!> {
      while (1) {
         consume (<?>stores[i]);
         printf ("Just consumed item[%d] of value [%d]\n", i, stores[i]<value>);
      }
   }
}

Unlike the Producer which creates a new set of NUMITEMS tasks at each NUMROUND iteration, the Consumer uses a serial for loop to create a fixed set of tasks, one for each store element. Each task runs an infinite while loop to keep consume'ing its assigned store item, no matter in what round in Producer that that item has been produce'd.

Each while-loop inline task invokes a read operation with <?>stores[i]. Upon success, the read operation returns the read value as the result of the operation. This result is then consumed by the consume function. It also saves the result in the value property of the local cache representing the mel variable store[i]. This value property is later used as the argument for the printf statement.

Since there is no exception handler, all while loop inline tasks will automatically end via abortion when the mel array is closed by the Producer. With all tasks ended, the program can exit.

The while loop can be replaced by the resume operation:

/* CONSUMER VERSION 2 */
void Consumer (<mel> int stores[]) {
   for (int i=0; i<NUMITEMS; ++i)
   <!> {
      consume (<?>stores[i]);
      printf ("Just consumed item[%d] of value [%d]\n", i, stores[i]<value>);
      <resume>;
   }
}

The resume operation jumps back to the latest wait statement which is <?>stores[i], which is what the while(1) loop was doing

---

Mel Array Closures

Let's revisit the Producer use of

<close>stores;

That statement is semantically equivalent to closing all the independent mel elements in the mel array in parallel:

for (int i=0; i<NUMITEMS; ++i) <!> { <close>stores[i]; }

It is also possible to close a particular element separately:

/* PRODUCER VERSION 2 */
void Producer (<mel> int stores[]) {
   int round = 0;
   while (1) {
      for (int i=0; i<NUMITEMS; ++i) 
      <!collect> {
         int c = produce();
         if ( c == 0 ) <close>stores[i];
         else <?>stores[i] = c;
      } <? ENDED>;
      if (++round >= NUMROUNDS) break;
   }
   <close>stores;
}

Here, Producer can prematurely close an element in the mel array if the "product 0" condition is true for that element. After NUMROUNDS rounds, the Producer task closes the rest of the elements in the mel array. The <close>stores statement skips any elements that have already closed.

---

Mel Array Status Property

There is an issue with the Producer code above. It runs the for-pel loop NUMROUND times. What if it closes an element of the mel array in an earlier round and then attempts to produce for that item in the subsequent rounds? Since that element of the mel array has been closed, any subsequent write access to it will fail.

Let's modify the Producer to tackle this concern:

/* PRODUCER VERSION 3 */
void Producer (<mel> int stores[]) {
   int round = 0;
   for (int i=0; i<NUMITEMS; ++i) 
   <!collect> {
      while ( ++round < NUMROUNDS ) {
         if ( stores[i]<status> == NERW_STATUS_CLOSED ) <end>;
         int c = produce();
         if ( c == 0 ) <close>stores[i];
         else <?>stores[i] = c;
 
         if (++round >= NUMROUNDS) break;
      }
   } <? ENDED>;
   <close>stores;
}

The VERSION 3 of Producer flips the order of the for and while loops from the VERSION 2. In VERSION 2, we have a while loop that runs NUMROUNDS times, and each time, it pels NUMITEMS inline tasks and waits for them to finish. The total number of tasks that are created is therefore NUMROUNDS * NUMITEMS. In the new VERSION 3, we have a for loop that pels NUMITEMS tasks. Each task then runs its own while loop sequentially for NUMROUNDS times. The number of inline tasks created in VERSION 3 is much smaller than in VERSION 2.

When an inline task produces a 0 value, it closes its mel array element <close>stores[i]. We could end that inline task here. However for the sake of discussion, we allow it to loop back and does another round. The first thing it does is to check for the mel status property since there is no point of produce'ing if there is no stores element to put it into. The status propery value has been piggy-backed in the acknowledgement return package of the last operation to the mel entity, and saved in the local property cache. If the mel entity has been close'd from the previous round, its status will be NERW_STATUS_CLOSED on this round.

What would happen if the inline task did not check for the status of the mel array element that it plans to use? It would run produce. Then when it were to deposit that product to the mel array element with the mel write statement, <?>stores[i] = c, it would get a stores[i]<CLOSED> exception. Since it did not have a handler for this exception, it would also end, but now via a pel abortion.

---

Mel Array Exceptions

Let's now re-write the Consumer task to go with the above Producer, highlighting the use of exceptions with mel arrays:

/* CONSUMER VERSION 3 */
void Consumer (<mel> int stores[]) {
   int numitems = stores<count>;
   for (int i=0; i<numitems; ++i) {
      printf ("Task for [" + i + "] created");
      <!> while (1) { 
         try { consume(<? timeout>stores[i]); }
         catch ( stores[i]<TIMEDOUT> ) { 
            printf ("Keep trying");
            <resume>; 
         }
         catch ( stores[i]<CLOSED> ) { 
            printf ("stores[%d] has closed", i); 
            break; 
         }
         catch ( stores<CLOSED> ) { 
            printf ("the full array stores has closed"); 
            break; 
         }
         catch ( stores[i]<BOUNDARY> ) { 
            printf ("Boundary error on [%d] - Abort! ", i);
            break; 
         }
      }
   }
}

The above Consumer uses a serial for loop to print the "Task for ..." message and then pel a number of inline tasks, one for each item of the stores array. Once Consumer has done all the task creations, it will end, leaving its inline tasks to end on their own terms via one of the exception handlers. Since Consumer does not care when its inline tasks end, it does not have to wrap the for loop in a collect-ENDED construct like the Producer task.

Each inline task does an infinite while loop. For each iteration of the loop, the task waits for its own stores[i] mel element. The wait is limited by a default timeout. When the mel is valued, it is retrieved and consume'd. Then the wait resumes.

The TIMEOUT exception and the first CLOSED exception handlers are applicable to the specific stores[i] mel element. The second CLOSED exception handler, stores<CLOSED>, applies to the whole mel array.

There are three ways for an inline task to end. It can break out of the while loop when its mel element is closed, or when the whole mel array is closed. After getting off the while loop, with nothing else to do, the task ends.

The third way is via a boundary exception which is the topic of the next section.

---

Mel Array Boundary Exception

There is a new exception associated with a mel array, the boundary exception, as seen in the VERSION 3 of Consumer:

catch ( stores[i]<BOUNDARY> ) { 
    printf ("Boundary error on [%d] - Abort! ", i);
    break; 
}

This exception is raised if the mel element being accessed is beyond the mel array contents. For example, the mel array stores with NUMITEMS items contains stores[0] to stores[NUMITEMS-1]; accessing stores[-1] or lower will trigger this out-of-bound exception at the lower end, and accessing stores[NUMITEMS] or above will trigger this exception at the upper end.

Although for the Consumer version above, the for (int i=0; i<numitems; ++i) does not go out-of-bounds, and thus Consumer will not be hit by the Boundary exception, it is still good to include this exception handler for defensive programming.

---

Mel Array Count Property

The boundary exception depends on CHAOS knowing the items count in the mel array. Whenever a mel array argument is passed to a pel task, the items count is also passed along and cached locally as the count property of the mel array. To properly iterate through the mel array, the task Consumer makes use of the count property, instead of using the constant NUMITEMS as in the Producer:

int numitems = stores<count>;

NERWous C library functions that pushes items in or pops items out of a mel array are required to update the count value at the mel array itself. When such an action occurs, the count properties locally cached in the tasks will become stale. These tasks need to refresh their property cache either by accessing the mel array again for reads or writes, or by using the snaphot operation.

---

Mel Array Boundary Behaviors

The Consumer VERSION 3 handles the mel array boundary in two ways. We make sure that stores[i] does not go out of bounds by controlling the value of i. We also handle any out-of-bound condition via the boundary exception handler. Boundary behaviors is the third way for handling boundary conditions.

A boundary behavior sets up an automatic default handling when stores[i] is out-of-bound so that a boundary exception can be either enforced or avoided. NERWous C supports the following behaviors:

• Strict behavior:
  NERWous C strictly enforces the boundaries. If the item of the mel array is out of bound, the boundary exception is raised.
  
  This is the default behavior if no behavior is specified, unless the out-of-bound condition happens in a catch construct (see the flex behavior below).
   
• Flex behavior:
  NERWous C tries to accommodate the out-of-bound conditions as much as possible to prevent the boundary exception. This is accomplished via two methods:
  • Ignoring out-of-bound items if there are other items to process. For example, out-of-bound items in an OR list wait can be ignored, and the result of the OR list wait depends on the in-bound items. This method is the default for both reading and writing.
  • Stand-in values: this method is for reading only. When an item is out-of-bound, its value will be the stand-in value instead of causing an exception.
  If there are no stand-in values and all the items are out-of-bound, the flex behavior cannot prevent the boundary exception from occurring.
  
  The flex behavior is the default behavior in a catch construct as seen later in the Mel Array With Writer OR Zones example.
   
• Wrap and Wrapflex behaviors:
  NERWous C wraps around the out-of-bound items. Out-of-bound items in the upper boundary will wrap around to the lower boundary, and vice versa. Boundary conditions can still occur if there are not enough items in the mel array to accommodate the wrap around. In this case, the wrap behavior falls back to the strict behavior, and the wrapflex behavior, to the flex behavior.
  
  The wrapped-around item uses the same mel access as the out-of-bound item. For example, if the latter uses a mel readonly access, the former also uses readonly access.

These are the attributes of the boundary behaviors:

lbound	The specified behavior will be triggered on any array item that has its index equal to or lower than this lower boundary index. The default value is -1.
lval	The flex and wrapflex behaviors use this lower boundary value as the stand-in value for any array item at or below the lower boundary. If not specified, the default value is 0 for numerical items and null for non-numerical items.
ubound	The specified behavior will be triggered on any array item that has its index equal to or greater than this upper boundary index. The default value is the array count property.
uval	The flex and wrapflex behaviors use this upper boundary value as the stand-in value for any array item at or above the upper boundary. If not specified,the default value is 0 for numerical items and null for non-numerical items.

This is the coding format for the boundary behaviors, using stores[i]:

mel stores[20];
/* strict behavior - explicit */
<?>stores[i]<strict lbound=5 ubound=10>;

/* flex behavior */
<?>stores[i]<flex lbound=5 ubound=10 lval="111" uval="999">;

/* wrap behavior */
<?>stores[i]<wrap lbound=5 ubound=10>;

/* wrapflex behavior */
<?>stores[i]<wrapflex lbound=5 ubound=10 lval="111" uval="999">;

Although the mel array stores can contain 20 items, the above statements work on a subset of the array. With lbound set to 5, stores[0] to stores[5] will trigger the stated boundary behavior. Likewise, with ubound set to 10, stores[10] to stores[19] will trigger the stated boundary behaviors. Either or both of the attributes can be omitted, and the boundary behaviors use the default value of -1 for the lower bound, and 20 for the upper bound, which is the full size of the mel array.

The lval and uval attributes contain the stand-in values, and are needed only for the flex and wrapflex behaviors.

---

Mel Array Consecutive Constructs

When consecutive mel array items are used in an OR, AND or LIST reads or writes, instead of listing them individually, we can use the consecutive 2-dot construct (..), and specify only the first and last item.

The boundary behaviors can also be used with consecutive constructs. When specified, a behavior is applicable to all the mel array items in the consecutive construct. If different behaviors happen to be needed, the consecutive construct should not be used. Instead, the explicit list of the items will allow different behaviors to be assigned to different items.

The following code snippets use stores[i] Consecutive OR:

Explicit	<?>(stores[i] || stores[i+1] || stores[i+2])
Consecutive	<?>(stores[i] ..||.. stores[i+2])
with Strict	<?>(stores[i] ..||<strict lbound=5 ubound=10>.. stores[i+2])
with Flex	<?>(stores[i] ..||<flex lbound=5 ubound=10 lval="111" uval="999">.. stores[i+2])
with Wrap	<?>(stores[i] ..||<wrap lbound=5 ubound=10>.. stores[i+2])
with Wrapflex	<?>(stores[i] ..||<wrapflex lbound=5 ubound=10 lval="111" uval="999">.. stores[i+2])

Consecutive AND:

Explicit	<?>(stores[i] && stores[i+1] && stores[i+2])
Consecutive	<?>(stores[i] ..&&.. stores[i+2])
with Strict	<?>(stores[i] ..&&<strict lbound=5 ubound=10>.. stores[i+2])
with Flex	<?>(stores[i] ..&&<flex lbound=5 ubound=10 lval="111" uval="999">.. stores[i+2])
with Wrap	<?>(stores[i] ..&&<wrap lbound=5 ubound=10>.. stores[i+2])
with Wrapflex	<?>(stores[i] ..&&<wrapflex lbound=5 ubound=10 lval="111" uval="999">.. stores[i+2])

Consecutive LIST:

Explicit	<?>(stores[i], stores[i+1], stores[i+2])
Consecutive	<?>(stores[i] ... stores[i+2])
with Strict	<?>(stores[i] ..<strict lbound=5 ubound=10>.. stores[i+2])
with Flex	<?>(stores[i] ..<flex lbound=5 ubound=10 lval="111" uval="999">.. stores[i+2])
with Wrap	<?>(stores[i] ..<wrap lbound=5 ubound=10>.. stores[i+2])
with Wrapflex	<?>(stores[i] ..<wrapflex lbound=5 ubound=10 lval="111" uval="999">.. stores[i+2])

For a consecutive LIST, the unwieldy ..,.. construct is shortened to an ellipsis, .... On the same vein, the comma is also omitted in consecutive LIST constructs with boundary behaviors.

---

Mel Array OR Wait Examples

The following examples show the use of mel arrays with OR waits:

1. Mel Array with OR Writes
2. Mel Array with OR Reads
3. Mel Array with Reader OR Zones
4. Mel Array with Writer OR Zones

Mel Array With OR Writes

Let's start with mel OR writes by modifying the Producer so that it can write to either stores[i] or a common overflowstore.

/* PRODUCER VERSION 4 */
void Producer (<mel> int stores[], <mel> int overflowstore) {
     int round = 0;
     for (int i=0; i<NUMITEMS; ++i) 
     <!collect> {
         while ( ++round < NUMROUNDS ) {
              int c = produce();
             if ( c == 0 ) { 
                 <close>stores[i];
                 break;
             }
             <?>(stores[i] || overflowstore) = c;
         }
         if (++round >= NUMROUNDS) break;
     } <? ENDED>;
     <close>stores;
}

This version of Producer adds to the VERSION 3 the overflow mel variable. If stores[i] is full and cannot accept a new value, the new Producer will try the overflow variable. Unlike stores[i] which is exclusive to a for pel task, the overflow mel variable is shared between all the for pel tasks.

Mel Array With OR Reads

To illustrate the mel OR reads, let's modify the Consumer to read from either stores[i] or if it is empty, from overflowstore.

/* CONSUMER VERSION 4 */
void Consumer (<mel> int stores[], <mel> int overflowstore) {
    int numitems = stores<count>;
    for (int i=0; i<numitems; ++i) {
        printf ("Task for [" + i + "] created");
        <!> while (1) { 
            try { 
                consume(<? timeout>(stores[i] || overflowstore)); 
            }
            catch ( stores[i] || overflowstore)<TIMEDOUT> ) { 
                printf ("Keep trying"); 
                <resume>; 
            }
            catch ( stores[i]<CLOSED> ) { 
                printf ("Only me out!"); 
                break; 
            }
            catch ( stores<CLOSED> ) { 
                printf ("Everybody out!"); 
                break; 
            }
            catch ( stores<BOUNDARY> ) { 
                printf ("Boundary error - Abort! ");
                break; 
            }
            catch ( overflowstore<CLOSED> ) { 
                printf ("Keep trying with stores[i] only");
                <resume>; 
            }
        }
     }
}

There is a flaw in the above Consumer. A value in overflowstore may be originally destined to any item in the mel array stores, and not necessarily to stores[i]. This is because the same overflowstore is used by all the Producer tasks to deposit their "overflown" product.

Mel Array With Reader OR Zones

The previous Consumer makes use of only one item in the stores array. Let's modify Consumer to use 3 consecutive items in the array, to illustrate the use of an reader OR zone in conjunction with a consecutive OR construct.

/* CONSUMER VERSION 5 */
void Consumer (<mel> int stores[], <mel> int overflowstore) {
  int numitems = stores<count>;
  for (int i=0; i<numitems; ++i) 
  <!> {
    try <? as=consumable>(stores[i] ..||<flex>.. stores[i+2] || overflowstore) {
      printf ("Item to be consumed [%s] of value [%d]\n", consumable<name>, consumable);
      consume (consumable);
    } <resume>;     // use resume to loop back instead of while(1) loop
    catch ( (stores[i] ..&&.. stores[i+2] && overflowstore)<CLOSED> ) { }
  }
}

With the flex boundary behavior, if stores[i+1] or stores[i+2] are out-of-bound, they will be ignored in the processing of the OR list.

The consumable is the eponymous variable. It can be in the NERWous C mel format as in consumable<name> or in the basic C data type format, consumable. In fact, when used inside an exclusive zone, consumable is a shortcut for consumable<value>.

Mel Array With Writer OR Zones

Let's now modify Producer task to use a writer OR zone with consecutive mel array items.

/* PRODUCER VERSION 5 */
void Producer (<mel> int stores[], <mel> int overflowstore ) {
  int round = 0;
  while (1) {
    for (int i=0; i<NUMITEMS; ++i) 
    <!collect> {
      try <?writer mode=random as=product> 
      (stores[i] ..||<wrap>.. stores[i+2] || overflowstore) {
        product = produce();
        if ( product == 0 ) { 
          <close>product;
          printf ("Item [%s] is closed\n", product<name>);
        }
        printf ("Item [%s] contains value [%d]\n", product<name>, product);
      }
      catch ( (stores[i] ..&&.. stores[i+2] && overflowstore)<CLOSED> ) { 
        printf ("All items in OR list have closed\n");
      }
    } <? ENDED>;    
    if (++round >= NUMROUNDS) break;
  }
  <close>stores;
  <close>overflowstore;
}

The previous Producer VERSION 4 has a while loop inside a for loop, and pels exactly NUMITEMS tasks. For the sake of difference, this VERSION 5 reverses the order, and has a for loop inside a while loop. It pels NUMITEMS tasks every NUMROUNDS iterations, for a total of NUMITEMS * NUMROUNDS tasks for the life of Producer.

The writer attribute in the mel wait statement indicates that this wait is for a writer zone. When a task is inside the writer zone, it will prevent other tasks to access the writer's end of the mel variable to deposit a new value.

Is using a writer zone for this version of Producer an overkill, since a simple OR write statement can suffice?
<?> (stores[i] ..||<wrap>.. stores[i+2] || overflowstore) = produce();
The main difference is that with the writer zone, the mel access for writing is held up during the time the product is being produce'd, while with the simple write statement, the hold-up is only to deposit a value that has been already produce'd.

The OR list on entrance of the writer zone is also used on the checkout of the zone. The eponymous variable product has the value to be written into the mel variable. But which mel variable in the OR list? Since the random mode is used, the CHAOS runtime will randomly select either stores[i], stores[i+1], stores[i+2], or overflowstore. If it the first randomly selected mel variable has an empty slot, it will be put on hold while the task is in the writer zone, and on checkout, it will receive the value of the eponymous variable. If that mel variable is still full, CHAOS will randomly look at another mel variable in the list. If none of the variables are available, CHAOS will force the task to wait at the mel wait statement <?> until one mel variable is available for writing.

To handle boundary conditions, the wrap behavior starts to replace stores[i+1] and stores[i+2] with stores[0] and stores[1] when i reaches the end of the stores mel array (which is NUMITEMS-1).

When a 0 value is produced, the Producer decides to close the mel variable that has been selected, and currently represented by the eponymous variable product. Once that mel variable is closed, on the next round of the while loop, CHAOS will skip looking at this mel variable during the processing of the OR list.

If it happens that all the mel variables in the OR list have been previously closed, the mel zone wait statement will abort with the closure exception. Here, the exception handler just displays the message and implicitly ends the task.

The closure exception uses the AND consecutive construct for the mel array items (stores[i] ..&&.. stores[i+2]). When used in the catch construct, the flex behavior is implicit. This prevents a boundary exception when we are already handling a boundary condition.

Talking about implicit, there is an implict checkout of the writer zone at the closing }. This brings up the default behavior which is to update the writer's end of the selected mel variable with the value of the eponymous variable product.

Each while loop iteration pels NUMITEMS tasks and uses the collect-ENDED construct to wait for all the pelled tasks to finish, before the next round is started. It is also possible to omit the collect-ENDED construct. In that case, from NUMITEMS to NUMITEMS * NUMROUNDS tasks can exist at the same time and run in parallel. They will vie for the same stores and overflowstore shared resources but the writer zone wait will ensure that only one task can check out a resource, and the checkout follows the chronological order of the pel creations.

When NUMROUNDS rounds have completed, the Producer tasks closes the mel array stores and the mel variable overflow. The corresponding Consumer task will cue on these closures to end itself.

---

Mel Array AND Wait Examples

Let's now modify Consumer and Producer to illustrate the use of the AND operation with mel arrays. We will skip the AND reads and AND writes discussion, and delve only with AND zones:

1. Mel Array with Reader AND Zones
2. Mel Array with Writer AND Zones

Mel Array with Reader AND Zones
Unlike previous versions, this new Consumer consumes, not one but multiple items from the mel array store on every run. These mel elements are waited on using the reader AND zone:

/* CONSUMER VERSION 6 */
void Consumer (<mel> int stores[], <mel> int overflowstore) {
    int numitems = stores<count>;
    for (int i=0; i<numitems; ++i) 
    <!> {
        try <?>(stores[i] ..&&<flex uval=0>.. stores[i+2] && overflowstore)  {
            consume (stores[i]); 
            consume (stores[i+1]); 
            consume (stores[i+2]);
            consume (overflowstore); 
        } <resume>;     // loop back to zone wait
        catch ( (stores[i] ..||.. stores[i+2] || overflowstore)<CLOSED> ) { 
            break; 
        }
     }
}

There may be long waits at the reader AND zone entrance because each task iteration competes not only for its stores element (stores[i]) but also of the next two elements (stores[i+1] and stores[i+2]). And everybody competes for the same overflowstore mel variable. Here overflowstore acts as the serializer that allows only one task to be in the reader AND zone at a time. The mel AND wait will ensure that there is no deadlocks nor resource starvation, but the mechanism of an AND wait can impose performance penalty.

The AND list above uses the flex behavior with stand-in value 0 for any upper out-of-bound mel array items. For example, the last task that the for loop pels has i equals to NUMITEMS-1. Thus, stores[i] is in-bound, but stores[i+1] and stores[i+2] are out-of-bound. Instead of causing a boundary exception, they are assigned the stand-in value of 0, which is then consume'd inside the reader zone.

Mel Array with Writer AND Zones
To illustrate the use of a writer AND zone, let's modify the previous version of Producer:

/* PRODUCER VERSION 6 */
void Producer (<mel> int stores[], <mel> int overflowstore ) {
    int round = 0;
    while (1) {
       for (int i=0; i<NUMITEMS; ++i) 
       <!> {
           try <?writer>( stores[i] ..&&<flex>.. stores[i+2] && overflowstore)  {           
               if ( ! (stores[i] = produce()) )
                   <close>stores[i];
               if ( i < NUMITEMS-1 ) {
                   if (! (stores[i+1] = produce()) )
                       <close>stores[i+1];
               }
               if ( i < NUMITEMS-2 ) {
                   if ( ! (stores[i+2] = produce()) )
                       <close>stores[i+2];
               }
               if ( ! (overflowstore = produce()) )
                   <close>overflowstore;
           }
           catch ( (stores[i] ..||.. stores[i+2] || overflowstore)<CLOSED> ) {
               printf ("A required item has been closed by another task -- Abort");
               <end>;
           }           
       }
       if (++round >= NUMROUNDS) break;
    }
    <close>stores;
    <close>overflowstore;
}

This Producer also uses the flex behavior for its AND list. Since this is for a writer zone, there is no stand-in upper-bound value. Instead, any mel array item that is out-of-bound will be ignored. On entrance of the writer zone, the AND wait will skip checking stores[i+1] and stores[i+2] when i == NUMITEMS-1. On the same vein, on checkout of the writer zone, stores[i+1] and stores[i+2] will not be updated by the checkout operation if they are out-of-bound.

Inside the writer zone, the eponymous variables that stand for stores[i+1] and stores[i+2] can still be assigned values. But as said above, during the checkout, these values will not be used if the mel array items are out-of-bound. To prevent un-necessary produce activities which may deplete production resources, there are checks to validate i before produce is invoked.

The first task that produces a 0 value for overflowstore will cause subsequent tasks to hit the CLOSED exception. This is due to all the tasks include overflowstore in their AND mel waiting list.

---

Mel Array LIST Wait Examples

As we have discussed OR and AND operations with mel arrays, we will now wrap up this chapter with a discussion on LIST operations. Again we will skip the LIST reads and LIST writes, and focus on LIST zones.

1. Mel Array with Reader LIST Zones
2. Mel Array with Writer LIST Zones

A LIST exclusive zone requests all the specified mel elements like the AND exclusive zone, but unlike the AND zone, it holds on to a mel element whenever it is available. This is efficient but can result in deadlocks or starvation if other tasks are also requesting the same elements.

Single mel elements required by a LIST zone are stringed together via the comma (either for reads or writes, while consecutive LIST elements in a mel array uses 3-point ellipsis construct (...).

Mel Array with Reader LIST Zones
Let's again modify the Consumer task, this time to use the mel array stores with a reader LIST zone:

/* CONSUMER VERSION 7 */
void Consumer (<mel> int stores[], <mel> int overflowstore) {
    int numitems = stores<count>;
    for (int i=0; i<numitems; ++i) 
    <!> {
        try <?>(stores[i] ..<flex uval=0>.. stores[i+2],  overflowstore)  {
            consume (stores[i]); 
            consume (stores[i+1]); 
            consume (stores[i+2]);
            consume (overflowstore); 
        } <resume>;     // loop back to zone wait
        catch ( (stores[i] ..||.. stores[i+2] || overflowstore)<CLOSED> ) { 
            break; 
        }
     }
}

The difference between this LIST version and the "AND" version is the replacement of the consecutivve AND operator (..&&.. with the consecutive LIST operator (...). The "LIST" version also waits for all the specified elements -- stores[i], stores[i+1], stores[i+2], and overflowstore. However, while an AND wait requires all the elements to be available at the same time to prevent deadlock, the LIST wait allows the task to hold on a mel variable as it is made available. The task enters the reader LIST zone when it has accumulated holds on all the specified mel variables.

Mel Array with Writer LIST Zones
We now replace the writer AND zone of the previous Producer with a writer LIST zone to illustrate the use of such zone with mel arrays:

/* PRODUCER VERSION 7 */
void Producer (<mel> int stores[], <mel> int overflowstore ) {
    int round = 0;
    while (1) {
       for (int i=0; i<NUMITEMS; ++i) 
       <!> {
           try <?writer>( stores[i] ..<flex>.. stores[i+2], overflowstore)  {           
               if ( ! (stores[i] = produce()) )
                   <close>stores[i];
               if ( i < NUMITEMS-1 ) {
                   if (! (stores[i+1] = produce()) )
                       <close>stores[i+1];
               }
               if ( i < NUMITEMS-2 ) {
                   if ( ! (stores[i+2] = produce()) )
                       <close>stores[i+2];
               }
               if ( ! (overflowstore = produce()) )
                   <close>overflowstore;
           }
           catch ( (stores[i] ..||.. stores[i+2] || overflowstore)<CLOSED> ) {
               printf ("A required item has been closed by another task -- Abort");
               <end>;
           }           
       }
       if (++round >= NUMROUNDS) break;
    }
    <close>stores;
    <close>overflowstore;
}

Near the boundary condition, when i == NUMITEMS-1, the flex behavior instructs the LIST wait to ignore the out-of-the-bound mel array item, stores[i+2], and wait only on the inbound mel array items, stores[i] and stores[i+1], plus the mel variable overflowstore. Unlike an AND wait which waits for all these mel variables to be all available at the same time, the LIST zone wait allows the Producer to accumulate the holds of these mel variables as they become available. This wait is more efficient but may introduce deadlocks if another task is doing the same wait.

---

Previous Next Top

The Dining Philosophers

Welcome » NERWous C » Examples

1. Current Literature
2. NERWous C Samples

---

Current Literature

This classic problem of resource competition is best explained by this Wikipedia article:

Five silent philosophers sit at a round table with bowls of spaghetti. Forks are placed between each pair of adjacent philosophers.

Each philosopher must alternately think and eat. However, a philosopher can only eat spaghetti when they have both left and right forks. Each fork can be held by only one philosopher and so a philosopher can use the fork only if it is not being used by another philosopher. After an individual philosopher finishes eating, they need to put down both forks so that the forks become available to others. A philosopher can take the fork on their right or the one on their left as they become available, but cannot start eating before getting both forks.

Eating is not limited by the remaining amounts of spaghetti or stomach space; an infinite supply and an infinite demand are assumed.

For our discussion, we will change the unlimited "spaghetti" to limited, per this Oracle deadlock analysis:

The process is repeated until there are no more noodle.

Issues

The dining philosophers problem touches on three issues of resource competition:

1. Mutual exclusion
2. Deadlocks and livelocks
3. Resource starvation

On mutual exclusion, the forks are shared resources. Once a philosopher has grabbed a fork, it cannot be grabbed by his neighbor. Our philosopher has exclusive use of this shared resource.

Deadlocks appear when each philosopher has grabbed his left fork and is waiting for his right fork. Since nobody yields (philosophers are known to hold on to their principles), all the philosophers will wait until eternity. One way to break the deadlocks is to allow the philosophers to hold a fork for only 10 minutes and wait 5 minutes to grab a fork again. This solution can introduce livelocks where all philosophers come to the table at the same time, grab their left forks at the same time (which introduces deadlocks), wait 10 minutes, put down their forks at the same time (deadlocks are broken), wait the same 5 minutes, and grab their left forks again. The philosophers are not sitting idle waiting (i.e. stuck in deadlocks), but their grab-release make work actions are like hamsters in spinning wheels, without allowing them to eat and think.

There are several solutions to the deadlocks and livelocks issue. These solutions must also resolve the issue of resource starvation. One philosopher may also be a part-time magician and is quick with his hands. He may grab his forks faster than his left or right neighbors, "starving" them the opportunity to have the necessary forks to get to eat and think.

Solutions

There is an abundance of solutions and discussions on this classic problem on parallelism (see Google or Bing searches).

Here are some of the references:

• Cunningham & Cunningham, Inc -- philosophical discussion on the Dining Philosophers problem
• Oracle Sun Studio -- an implementation in the C language using POSIX threads
• Rosetta Code -- the Dining Philosophers solution in a number of programming languages

---

NERWous C Samples

Here are the Dining Philosophers solutions in NERWous C. We will start with one where the resources are localized, and then expand the solution to distributed resources.

Localized Resources

We follow the current literature where the forks are in the same local area and thus, can be presented by an array. For NERWous C, the array is a mel array:

#define NUM 5
void main () {
   <mel> int forks[NUM];
   for ( int i=0; i<NUM; ++i ) 
      <?>forks[i] = 1;

   for ( int i=0; i<NUM; ++i ) {
      int j = i+1;
      if ( j == NUM+1 ) j = 0;
      <!> {
         int done;
         ( <? as="leftfork, rightfork"> (forks[i] && forks[j) ) {
            if ( ! eat (leftfork, rightfork) ) done = 1;   /* no more eating */
            else done = 0;
            <checkout skip>;
         } 
         think ();
         if ( !done ) <resume>;
         else <end>;
      }
   }
   printf ("All the philosophers are seated. They will leave when they are done.");
}

The forks are shared resources so they are declared as items of a mel array. The for loop then values all forks so they become available for the philosophers. The value 1 is chosen but any value will do since the philosophers are interested in the availability of the forks and not their values.

The task main then runs the second for loop to create the philosopher tasks. Once the tasks are created, the task main displays the "Philosophers seated" message and ends itself leaving the philosopher tasks to run by themselves. Once a philosopher is done with the eating and thinking, its corresponding task will end. Once all the philosopher tasks have ended, the NERWous C program will exit.

The philosopher task is an inline task started by the <!> pel operator. It declares a local variable done to be used throughout its life. It then waits for its left and right fork using the reader AND zone facility to prevent deadlocks and starvations. Once inside the exclusive zone, it can do the eat'ing in peace.

With the eat'ing done, the philosopher task checks out of the exclusive zone with the skip attribute. This leaves the values of the forks it uses available for other philosopher tasks. Without the skip, the default behavior on checkout is to remove the values, causing the philosopher tasks to wait forever to enter the exclusive zones, since there is no other task to re-value the forks.

After think'ing, the philosopher task has to make a decision to continue or to end. If more eat'ing is wanted, the resume operation loops back to the reader AND zone wait. Note that resume loops back to the latest mel wait, and not to the beginning of the pel inline code. Thus, the declaration of the done variable is not re-executed.

Wrap Consecutive AND Construct

The above example has code to check for the boundary condition to wrap around the fork index for the last philosopher task. This code can be replaced by the wrap consecutive AND construct:

#define NUM 5
void main () {
   <mel> int forks[NUM];
   for ( int i=0; i<NUM; ++i ) 
      <?>forks[i] = 1;

   for ( int i=0; i<NUM; ++i ) {
      <!> {
         int done;
         ( <? as="leftfork, rightfork"> (forks[i] ..&&<wrap lbound=0 ubound=NUM>.. forks[i+1) ) {
            if ( ! eat (leftfork, rightfork) ) done = 1;   /* no more eating */
            else done = 0;
            <checkout skip>;
         } 
         think ();
         if ( !done ) <resume>;
         else <end>;
      }
   }
   printf ("All the philosophers are seated. They will leave when they are done.");
}

The wrap attribute automatically assigns forks[0] to forks[i+1] when i+1 is equal to NUM, since forks[NUM] is out of bound of the mel array forks.

Distributed Resources

Let's now assume that our philosophers are very picky. One fork comes from a warehouse in China, one from a warehouse in Italy, one from a comma-separated-value (CSV) file in a store, one from a corporate database, and one from the shared stash. To support such distributed resources, we have to create individual mel variables in order to assign the cel locality, and use the array of mels to assemble the resources:

#define NUM 5
void main () {
   cel cn = { "Chinese Manufacturers", "https://www.philoforks.cn/nerw/" };
   cel it = { "Italian Artisans", "https://www.philoforks.it/nerw/" };
   cel fs = { "Warehouse", "D:\warehouse\forks\modelXYZ.csv" };
   cel db = { "Ledger", "dbsqlforks" } ;

   <mel at=cn> int fork_cn = 1;
   <mel at=it> int fork_it = 1;
   <mel at=fs> int fork_fs = 1;
   <mel at=db> int fork_db = 1;
   <mel> int fork = 1;
   <mel> forks[NUM] = { fork_cn, fork_it, fork_fs, fork_db, fork };

   for ( int i=0; i<NUM; ++i ) {
      <!> {
         int done;
         ( <? as="leftfork, rightfork"> (forks[i] ..&&<wrap lbound=0 ubound=NUM>.. forks[i+1)) {
            if ( ! eat (leftfork, rightfork) ) done = 1;   /* no more eating */
            else done = 0;
            <checkout skip>;
         } 
         think ();
         if ( !done ) <resume>;
         else <end>;
      }
   }
   printf ("All the philosophers are seated. They will leave when they are done.");
}

In this setup, each mel is localized in a different cel.

For further resource distribution, let's define a cel node to be assigned to run for each philosopher:

  cel philo[NUM] = { 
   ("Philosopher 0", 0), ("Philosopher 1", 1), ("Philosopher 2", 2),
   ("Philosopher 3", 3), ("Philosopher 4", 4) };

   for ( int i=0; i<NUM; ++i ) {
      <! at=philo[i]> {
         int done;
         ( <? as="leftfork, rightfork"> (forks[i] ..&&<wrap lbound=0 ubound=NUM>.. forks[i+1)) {
            if ( ! eat (leftfork, rightfork) ) done = 1;   /* no more eating */
            else done = 0;
            <checkout skip>;
         } 
         think ();
         if ( !done ) <resume>;
         else <end>;
      }
   }
   printf ("All the philosophers are seated. They will leave when they are done.");

Each philosopher task runs on its own philo[i] computer element.

---

Previous Next Top

Pi Value Approximation

Welcome » NERWous C » Examples

1. Current Literature
2. NERWous C Sample

---

Current Literature

One method to approximate Π (Pi) is to randomly generate a great number of points in a square with a circle inscribed in it. Count the number of points that fall inside the circle. Divide that number by the total number of randomly generated points. The value of Π is approximately 4 times the resulting quotient.

The more points generated, the better the approximation. To speed up the process, each generated point can be processed in parallel.

Sample serial code:

void main()
{
    double niter = 10000000;
    double x,y,z,pi;
    int i;
    int count=0;
    srand(time(NULL));
    for (i=0; i<niter; ++i)
    {
        //get random points
        x = (double)random()/RAND_MAX;
        y = (double)random()/RAND_MAX;
        z = sqrt((x*x)+(y*y));    //check if point is inside circle
        if (z<=1) ++count;
    }
    pi = ((double)count/(double)niter)*4.0;
    printf("Pi: %f\n", pi);
}

References:

• Lawrence Livermore National Laboratory -- Introduction to Parallel Computing
• Oak Ridge National Laboratory -- Serial to Parallel: Monte Carlo Operation
• Appentra Team -- A very simple simulation program: Parallel computation of PI

---

NERWous C Sample

To run the above serial code in parallel with NERWous C, we need to make a few changes:

void main()
{
   double niter = 10000000;
   <mel> int count=0;
   srand(time(NULL));
   for (int i=0; i<niter; ++i)
   <! collect> {
       double x, y, z;
       //get random points
       x = (double)random()/RAND_MAX;
       y = (double)random()/RAND_MAX;
       z = sqrt((x*x)+(y*y));    //check if point is inside circle
       if (z<=1) <?>++count;
   } <? ENDED>;
   double pi = ((double)<?>count/(double)niter)*4.0;
   printf("Pi: %f\n", pi);
}

The for loop is still running serially, but each of its iterations creates a new task via the pel creation <!> operation to run in parallel. Each independent task uses their own local variables x, y, z to contain intermediate computations. If these variables were defined in the main task instead, they would have to be imported into each of the tasks.

Each task increments the shared value count if it processes a point that falls inside the circle. Thus, the variable count is now declared as a mel variable. The for loop is encased in a collect-ENDED block to allow the <? ENDED> statement to ensure that all pelled tasks have ended. This allows the computation of the local variable pi to work with a shared variable count that has collected all the results from the pelled tasks.

---

Previous Next Top