Section H2

Implementing asynch messages with time stamping (pend).

As mentioned in Section F), timing semantics of -core v1.0 does not define any method to emit asynchronous methods having the baseline set to the current time. In this section we will discuss how this can be done (actually it is one of the assignments to the Compiler Construction students at LTU fall 2014.)

Section H1 shows how a new statement ("halt") could be introduced in the language. Now we will look the altering the "pend" syntax and it's semantics (meaning). Checking out -core v1.0 you will find an "old" pend dating to the first implementation of the -core language. This statement emitted an asynchronous message to trigger a Task without any payload. (Later I extended the -core language with message passing and task instances, but left the "pend" there for the time being).

In any case, let us give pend the following syntax:
stmt:
  ...                                  
  | "pend" before ID ( C-params ) ;
  | "async" after? before? ID ( C-params ) ;
  ...

We see that it is now very similar to async, (but we have not the option to postpone the message).

What you need to do is to alter the AST.ml (to store the before time), and the grammar (Parser.mly). You will see that when changing the AST.ml also requires altering some additional files.

The tricky part is the task instation, so I will help you out here.

TaskGenSpec.ml

let task_of_p topl =
...
| Async ...
| Pend (be, id, par ) :: l -> 
      begin
          let nrpends = mcount id ((List.map fst) sal) in
          let new_path = path ^ "_" ^ id ^ "_" ^ string_of_int nrpends in
              begin
                match Env.lookup_task id topl with
                | TaskDef (_, al, sl) ->
                    let new_bl = (Usec(0)) in
                    let new_dl = 
                      if (usec_of_time be == 0) then 
                        raise (RtfmError("Explicit deadline for pend required")) 
                      else be in 
                    (* the new task *)
                    ITask (Infinite, new_dl, new_path, new_path, al, sl) :: 
                    (* tasks created by the new task *)
                    tasks nr new_bl new_dl new_path ((id, (new_path, new_dl))::aal) afl [] [] sl @ 
                    (* the remaining statements *)
                    tasks nr i_bl i_dl path aal afl ((id, (new_path, new_dl))::sal) sfl l 
                | _ -> raise (RtfmError("failed lookup: [" ^ id ^ "]")) 
              end
      end
...

This takes a bit of explanation.

When a program is parsed into the AST, each Task (in the program) is stored as a TaskDef in the AST.

The function task_of_p topl takes the AST and turns it into a SpecAST (where you have task instances ITask) for each unique occurrence of a Task.

These unique instances are created from the recursively invoke
let rec tasks nr i_bl i_dl path aal afl sal sfl sl

from the Root and Idle tasks.
  • aal is the accumulated path of asynchronous messages
  • afl is the accumulated path of synchronous messages
  • sal is the asynchronous messages for this specific task instance
  • sfl is the synchronous messages for this specific task instance

(Currently we do not check for cycles of pend you might want to add this check (optional).)

When encountering a pend id we lookup a TaskDefinition for id, if that fails we raise the exception
failed lookup:


We do not have any after for a pend:
                    let new_bl = (Usec(0)) in

We require an explicit deadline:
                    let new_dl = 
                      if (usec_of_time be == 0) then 
                        raise (RtfmError("Explicit deadline for pend required")) 
                      else be in 

We can now create the task instance for our pend:
                    (* the new task *)
                    ITask (Infinite, new_dl, new_path, new_path, al, sl) :: 

and the task instance created by our pend task:
                    (* tasks created by the new task *)
                    tasks nr new_bl new_dl new_path ((id, (new_path, new_dl))::aal) afl [] [] sl @ 

and create task instances fro the remaining statements of the task emitting the pend:
(* the remaining statements *)
tasks nr ibl idl path aal afl ((id, (newpath, newdl))::sal) sfl l
}}

The function
task_of_p topl
creates an SpecAST data structure holding all the task instances. After that is done, we can now specialise the program, (i.e., make the statements of the created task instances be specialised to the task instance). This is done by the function:
let spec_of_p topl

Here you will add:
    | Pend (be, id, par) :: l -> 
      let nrpends = mcount id sal in
      let new_path = (path ^ "_" ^ id ^ "_" ^ string_of_int nrpends) in
      Pend (be, new_path, par) :: stmts i_dl path (id::sal) sfl l


This is by far the single most complex part of the -core compiler.

As a side note, specialisation in general has the purpose to optimise the executable by reduce (or even totally) overcome run-time overhead (e.g., in case of an over-loaded function, instead of enforcing to check the type and of augments at run-time (and act accordingly) one can emit specialised function for each type, and let the caller point to the specialised function instead).

In our case we analyse the program and generate a static set of task instances. Hence already at compile time we foresee all task instance occurrences, which largely simplifies the run-time system. In fact, the RTFM-kernel can utilise the interrupt hardware for 0-overhead scheduling (and under threaded environments, all threads can be generated at system start, and will not need to be recycled in a thread pool).

Furthermore this allows us to allocate space for all message buffers directly on the (static) heap (no mallocs during run-time). This ensures that a system when started will never fail due to failing memory allocations, and the overhead of buffer management is 0. Moreover, we specialise each instance such that it operates directly on the (statically allocated) buffer without the need to de-reference any additional pointer.

You will need to make changes at a few other places of the compiler also, most of them should be straightforward, but I will help you out with ICGenRT.ml:

ICGenRT.ml

As mentioned in the side note above, the -core compiler performs task instantiation and specialisation. This is used by the run-time systems and the RTFM-Kernel, in our case we focus on the ICGenRT.ml. You will need to add support for the pend statement as follows:
...
let rec stmts path sl = myconcat nl (mymap (stmt path) sl)
  and stmt path = function
    | Claim (r, csl)          ->...
    | Pend (be, id, par)      -> 
      "arg_" ^ id ^ " = (ARG_" ^ id ^ "){" ^ par ^ "};" ^ nl ^
      "RTFM_pend(" ^ string_of_int (usec_of_time be) ^ ",  RTFM_id, " ^ id ^ "_nr);" 
...

where the first line:
      "arg_" ^ id ^ " = (ARG_" ^ id ^ "){" ^ par ^ "};" ^ nl ^

assigns the values/expressions (par) to the argument instance arg_.
(id will be the specialised name for the message, and arg_ ^ id will be the specialised message buffer.)
The type of the message is defined by a C-typedef for the C-struct ARG_ ^ id to which the argument (par) is casted to. (The interested reader may look for the typedef generation.)

The second line:
      "RTFM_pend(" ^ string_of_int (usec_of_time be) ^ ",  RTFM_id, " ^ id ^ "_nr);" 

is emitted to call the run-time system to perform the actual pend. In case of RTFM-Kernel, the pend amounts to raising the corresponding interrupt associated to the task, while under thread based run-times (such as PTCORE/WINCORE), it amounts to emitting a semaphore associated to the task.

For this assignment, we will provide you with the PTCORE/WINCORE run-times, so you do not need to implement the run-time functionality.

These instructions should hopefully be enough for you to implement pend.

(The task generation/specialisation is rather complex, and the implementation will be subject to future work to improve readability. If you do not get all the details, don't feel alarmed, consider it as a first encounter later to be re-visited.)

Per Lindgren, September 7th.
















Last edited Sep 8, 2014 at 6:34 AM by RTFMPerLindgren, version 9