OEP

100

Title

MOBILE data types

Summary

Add MOBILE reference types, where only one process may hold the reference at a time.

Owner

Fred Barnes <F.R.M.Barnes@kent.ac.uk>

Status

Accepted

Date-Proposed

2001-09-08

Date-Accepted

2001-09-08

Keywords

language mobiles communication types

Mobiles are a new type class in occam -- i.e. for most ordinary types, a compatible mobile version now exists. Mobiles are different in one key way: assignment and communication of mobiles uses a movement semantics, instead of the usual copying semantics. This implies that when a process outputs a mobile variable, it loses it -- and any subsequent attempt to read from the variable is undefined (illegal).

To the programmer, mobiles offer a potential performance gain, with only minor intrusion to code. The run-time system (on a single-memory machine) implements mobiles by pointer-swapping references, that is a very low-cost operation (mobile commstime is around 20ns more than the ordinary commstime). More importantly, however, mobiles provide an efficient means to implement the familiar "packet passing" abstraction (in the past, occam programs have moved pointers around at run-time, for efficiency, but this was wholly un-checked and required the use of in-line assembler).

Essentially, two basic types of mobile variables are supported:

Static mobiles are allocated (by the compiler) into a global memory "heap" known as mobilespace. Like workspace and vectorspace, the required size of this area is known at compile-time. Dynamic process creation (recursion, variable replicated PARs, and forked processes) complicates this slightly. For mobilespace requiring dynamic processes, hooks are allocated inside the enclosing mobilespace. Once dynamic memory has been allocated for mobilespace, it cannot be returned to the general memory pool -- since references inside mobilespace may have migrated into other processes. More details on the technical aspects of mobilespace can be found in the [Mobile Data, Dynamic Allocation and Zero Aliasing: an occam Experiment][mobiles] paper.

Dynamic mobile arrays are somewhat simpler, since they are largely run-time only -- but incur a greater overhead for allocation/release than static mobiles (tens of nano-seconds).

Mobile variables can be declared in two ways: using the "MOBILE" keyword directly in the declaration; or declaring variables of a named "MOBILE" type. The first, for example:

MOBILE INT x, y:
SEQ
  x := 42
  y := x
  -- "x" now undefined

MOBILE []REAL64 data:
SEQ
  data := MOBILE [128]REAL64
  data[42] := 99.0

The first fragment declares two simple mobile integers. The second is slightly more interesting, requiring a special allocation assignment to create the array. Until they are allocated, dynamic mobile arrays have zero-size and are considered to be undefined (as far as the undefinedness checker is concerned). Any attempt to access a non-existant element will result in the usual run-time (range) error.

Communication behaves in much the same way as assignment, for example:

CHAN MOBILE []INT vals:
PAR
  --(((  producer
  MOBILE []INT x:
  SEQ
    x := MOBILE [10]INT
    SEQ i = 0 FOR SIZE x
      x[i] := i
    c ! x
    -- "x" is no longer defined
  --)))
  --(((  consumer
  MOBILE []INT v:
  INT x:
  SEQ
    c ? v
    x := v[5]
  --)))

As far as type compatability goes: wherever a non-mobile variable is valid, its mobile equivalent is valid too. For example:

MOBILE REAL64 m.v:
REAL64 s.v:
SEQ
  m.v := 24.5 (REAL64)
  s.v := m.v
  -- m.v still valid (copy)

Assignment is only considered mobile if both variables (LHS and RHS) are themselves mobile -- i.e. mixed mobile/non-mobile assignment results in the usual copy semantics. Communication is only mobile if the channel protocol is mobile. The following, for example, uses non-mobile communication:

CHAN [5]INT c:
PAR
  --(((  producer
  MOBILE [5]INT x:
  SEQ
    SEQ i = 0 FOR SIZE x
      x[i] := i
    c ! x
    -- "x" is still defined
  --)))
  --(((  consumer
  MOBILE [5]INT v:
  INT x:
  SEQ
    c ? v
    x := v[5]
  --)))

Changing the channel declaration to "CHAN MOBILE [5]INT c:" would, as expected, result in mobile communication. This is static mobile communication, however, since the size of "[5]INT" is known at compile-time.

When a non-mobile variable is used in mobile communication or assignment, the compiler automatically promotes the variable to its mobile equivalent. For dynamic mobile arrays, this includes automatic allocation of the array, making the programmer's life somewhat easier.

The second method of declaring mobiles involves declaring mobile types. For example:

DATA TYPE STRING IS MOBILE []BYTE:

DATA TYPE PACKET
  MOBILE RECORD
    [1024]BYTE data:
    INT offset:
:

Then using that type as usual. For example, and demonstrating automatic mobile promotion:

STRING s:
PACKET p:
SEQ
  s := "hello, occam world!*n"
  [p[data] FOR SIZE s] := s
  p[offset] := SIZE s

The array constructor may also be used with dynamic mobile arrays and automatic promotion. For example:

CHAN MOBILE []REAL64 c:
PAR
  --(((  producer
  c ! [i = 0 FOR 128 | ((REAL64 i) * PI) / 128.0]
  --)))
  --(((  consumer
  MOBILE []REAL64 data:
  SEQ
    c ? data
    ...  use "data"
  --)))

In some cases, it may be desirable to prevent mobile assignment or communication, where movement semantics are the default. This is done through use of the "CLONE" operator, that produces a duplicate of its mobile argument. The compiler will not automatically promote a non-mobile operand given to CLONE, thus "CLONE 5" is illegal. The CLONE operator also helps resolve potential ambiguities. The following fragment, for example, leaves "x" and "y" both defined:

MOBILE INT x, y:
SEQ
  x := 42
  y := (x + 5)

But if we later removed the "+ 5":

MOBILE INT x, y:
SEQ
  x := 42
  y := (x)

It is not immediately clear whether this results in movement or copying semantics -- i.e. whether "x" is defined after the second assignment. In fact, the compiler will use copying semantics for this -- two reasons: firstly, because of the brackets; and secondly, because any mobile type less than or equal to 8 bytes is automatically made non-mobile (because the equivalent non-mobile assignments and communications are quicker).

The CLONE operator can clear this ambiguity up, however:

MOBILE INT x, y:
SEQ
  x := 42
  y := CLONE x

A more practical example might be:

DATA TYPE STRING IS MOBILE []BYTE:
CHAN STRING c:
PAR
  --(((  producer
  STRING x:
  SEQ
    x := "hello, world!*n"
    c ! CLONE x
    [x FROM 7 FOR 5] := "occam"
    c ! x
  --)))
  --(((  consumer
  STRING v, w:
  SEQ
    c ? v
    c ? w
    ...  use "v" and "w"
  --)))

Or in a mobile "tap" process (using the extended rendezvous), for example:

PROC mi.tap (CHAN MOBILE []INT in?, out!, report!)
  WHILE TRUE
    MOBILE []INT x:
    in ?? x
      out ! CLONE x
      report ! x
:

The compiler (and run-time system) also support multi-dimensional dynamic mobile arrays. These can be used with automatic-promotion and array constructors too. For example:

DATA TYPE I.MATRIX IS MOBILE [][]INT:

PAR
  --(((  producer
  I.MATRIX x:
  SEQ
    x := [i = 0 FOR 64 | [j = 0 FOR 64 | (i * j)]]
    c ! x
  --)))
  --(((  consumer
  I.MATRIX m:
  INT sum:
  SEQ
    c ? m
    sum := 0
    SEQ i = 0 FOR SIZE m
      SEQ j = 0 FOR SIZE m[i]
        sum := sum + m[i][j]

    ...  do something useful
  --)))

[mobiles]: http://www.cs.kent.ac.uk/pubs/2001/1295/index.html

OEP/100 (last edited 2007-09-26 23:45:58 by ats1)