🚀 go-pugleaf

Tim Walker (tsw@netcom.com) wrote:
: 
:  Does anyone know if Occam3 will be recursive? This is a big drawback
: in Occam2 when trying to implement things like parallel searchs.
: 
:  -- Tim Walker  (tsw@netcom.com)

The short answer is `no'.

There is, however, a way to get fixed depth recursion.  Suppose the
definition you want to achieve is:

  PROC foo (formals)
    body  --  contains call to foo
  :

Then you can achieve recursion to depth n by repeating the code thus:

  PROC foo (formals)
    STOP
  :
  PROC foo (formals)
    body  --  contains call to foo
  :
  ...  repeat n-2 times
  PROC foo (formals)
    body  --  contains call to foo
  :

This might be regarded as a dirty hack.

More seriously, it does illustrate an important property of occam
processes, namely that their workspace requirements can be determined
statically.  If you can't do this, then the implementation of parallel
processes becomes much more difficult.  In current implementations of
occam, it is possible to allocate a fixed amount of workspace for each
parallel process.  If you allow recursive processes you cannot
determine statically how much workspace each process will need.  This
means that you have to know what to do with stack overflow when the
obvious place to extend it has been allocated to something else
already.  If you think you have a solution to this, and it does not
have an adverse affect on the context switch time, then I will be
interested to hear it.  In general, it is more important for an
embedded application to be sure of enough space in which to run.  After
all, you don't want to run out of memory just as you reach a critical
section of control code.

Geoff Barrett
INMOS Limited

tsw@netcom.com (Tim Walker) writes:
> Does anyone know if Occam3 will be recursive? This is a big drawback
>in Occam2 when trying to implement things like parallel searchs.

As the adding of recursion would prevent the compile-time-only memory
allocation from being performed (occam programs should never run out of
memory at runtime); I suspect not.

However, having recently implemented the Towers of Hanoi on a processor farm
and quicksort in occam (Tony Hoare's sort algorithm on C.S.P. hardware, hmm),
I found the building of my own stack to hold the details of the recursing on
to be the quite literally the easist part of the whole designing and writing
process, and it's not something I've had to do before.  Doing it all yourself
means you can build a queue instead of a stack and do things breadth-first if
you wish.

> -- Tim Walker  (tsw@netcom.com)

Warren

In article <1992Nov12.094835.8563@wraxall.inmos.co.uk> Geoff Barrett,
geoffb@inmos.co.uk writes:
>More seriously, it does illustrate an important property of occam
>processes, namely that their workspace requirements can be determined
>statically.  If you can't do this, then the implementation of parallel
>processes becomes much more difficult. In current implementations of
>occam, it is possible to allocate a fixed amount of workspace for each
>parallel process.  If you allow recursive processes you cannot
>determine statically how much workspace each process will need.  This
>means that you have to know what to do with stack overflow when the
>obvious place to extend it has been allocated to something else
>already.

Sofar, I agree.

>If you think you have a solution to this, and it does not
>have an adverse affect on the context switch time, then I will be
>interested to hear it.

I am confused. What do you mean when you talk about a 'context
switch'? It is clear that recursion implies additional overheads
at runtime during function calls. That it affects the time to
timeslice processes is totally new to me. Perhaps I am missing
a point here.

>In general, it is more important for an
>embedded application to be sure of enough space in which to run.  After
>all, you don't want to run out of memory just as you reach a critical
>section of control code.

Yes, but knowing how much stack space the embedded application needs
is no reason to rule out the possibility to use recursion in some
language:
If you don't need it, don't use it.

Marco Kesseler

Faculty of Mathematics and Computer Science
University of Nijmegen
Toernooiveld 1
6525 ED Nijmegen
The Netherlands

marcok@cs.kun.nl

In <BxnGAH.3t9@sci.kun.nl> Marco Kesseler <marcok@cs.kun.nl> writes:


>In article <1992Nov12.094835.8563@wraxall.inmos.co.uk> Geoff Barrett,
>geoffb@inmos.co.uk writes:

>>More seriously, it does illustrate an important property of occam
>>processes, namely that their workspace requirements can be determined
>>statically.  If you can't do this, then the implementation of parallel
>>processes becomes much more difficult. In current implementations of
>>occam, it is possible to allocate a fixed amount of workspace for each
>>parallel process.  If you allow recursive processes you cannot
>>determine statically how much workspace each process will need.  This
>>means that you have to know what to do with stack overflow when the
>>obvious place to extend it has been allocated to something else
>>already.

>Sofar, I agree.

Me too.  The obvious thing to do is to allocate a new chunk of memory
to use for the stack.  There's nothing very hard about this - many
compiler systems have done it for years, even before transputers
existed, and many transputer compiler systems support this as well.

>>If you think you have a solution to this, and it does not
>>have an adverse affect on the context switch time, then I will be
>>interested to hear it.

>I am confused. What do you mean when you talk about a 'context
>switch'? It is clear that recursion implies additional overheads
>at runtime during function calls. That it affects the time to
>timeslice processes is totally new to me. Perhaps I am missing
>a point here.

Stack checking and extension in the function prologue introduces
a certain overhead (typically some 5 to 10 percent with a straight-
forward implementation).  It does not introduce any context switch
overhead.  In time-critical code it makes sense to optimize the
stack use to ensure no stack extension is done (or even checked
for) in the 10% of your code that uses 90% of your cycles.  In this
way it is really quite easy to have arbitrary recursion where you
need it, at a negligible overhead.

Again, this is not very exciting or new, and is, IMHO, a rather
basic requirement for ANY professional transputer compiler
(especially C compilers, of course).  The existance of multiple
threads does not make this problem any harder, and does not
excuse the compiler system from supporting this.

Recursion is a very powerful programming tool, and is very clean
and `mathematically correct'.  The fact that it introduces variable-
size stacks is a tad inconvenient, but no excuse to remove the
feature from a modern programming language.  IMHO, of course.

>>In general, it is more important for an
>>embedded application to be sure of enough space in which to run.  After
>>all, you don't want to run out of memory just as you reach a critical
>>section of control code.

>Yes, but knowing how much stack space the embedded application needs
>is no reason to rule out the possibility to use recursion in some
>language:
>If you don't need it, don't use it.

Exactly!

>Marco Kesseler
>Faculty of Mathematics and Computer Science
>University of Nijmegen

Rob Kurver
PACT Parallel Architecture and Compiler Technology
--
     PACT                   Rob Kurver
    Foulkeslaan 87         rob@pact.nl
   2625 RB Delft     ph: +31 15 616864 
  The Netherlands   fax: +31 15 610032

In <2225@eagle.ukc.ac.uk> wgd@ukc.ac.uk (W.G.Day) writes:

>...

>As the adding of recursion would prevent the compile-time-only memory
>allocation from being performed (occam programs should never run out of
>memory at runtime); I suspect not.

>However, having recently implemented the Towers of Hanoi on a processor farm
>and quicksort in occam (Tony Hoare's sort algorithm on C.S.P. hardware, hmm),
>I found the building of my own stack to hold the details of the recursing on
>to be the quite literally the easist part of the whole designing and writing
>process, and it's not something I've had to do before.  Doing it all yourself
>means you can build a queue instead of a stack and do things breadth-first if
>you wish.

Personally, I wouldn't object to building my own stack, if I just
had `malloc' to do it with.  Building my own `malloc' I object to
more strongly.

>Warren

Bryan

dbc@ecs.soton.ac.uk (Bryan Carpenter) writes:
>
>Personally, I wouldn't object to building my own stack, if I just
>had `malloc' to do it with.  Building my own `malloc' I object to
>more strongly.
>
>Bryan
>

Building a memory allocation module isn't all that difficult (once
you've done it once or twice :-). Anyway in most "serious"
applications you layer an application specific allocator on the
"standard" allocator.

I worked on a (now defunct) TV animation product based on T800's. It
comprised a LARGE amount of occam (the last I heard it was up around
the 500,000 line mark) We used a dynamic memory allocation quite
extensively. We used a very obvious and simple method but it worked
quite well and gave us the facilities we needed.

I'll describe what we did but first I must state that we
didn't adopt the occam "way", i.e. we used dynamically allocated
things; we turned off the compiler's checking (it didn't work for us
anyway), etc... We were heathens! We used occam because it was the
only thing available at the time for transputers that could generate
reasonable code. There were the first C compilers available but we'd
gone too far by the time they were useful.

The system comprised a number of long lived processes, i.e. the
modules in the system. Each of these processes accepted a number of
parameters, one of which was a unsized vector of INT - the memory pool.

One of the standard "kernel" processes was a memory allocator. It
"owned" the memory pool vector and serviced requests for portions of
the pool - it serialised other processes attempts to modify the
memory allocator data structure.

The allocator process understood a few requests; allocate some memory,
add some memory to the freelist, report the largest block available,
etc... You know, standard general purpose allocator things. As I
recall we had a couple of procedures....

    PROC Alloc.Mem( [2]CHAN OF ANY mm.chans, VAL INT nbytes, INT ptr )
    PROC Free.Mem( [2]CHAN OF ANY mm.chans, INT ptr )

Notes:

    Yes we used CHAN OF ANY - it allowed our configuration langauage and
communications system work! The two element vector holds the "to"
channel and the "from" channel used to perform the RPC with the memory
allocator process (this use exposed a limitation in the compiler, it
assumed all channels in a vector were used in the same "direction")
Passing the channels also allowed these procs to be used with
different allocators (we had a few - one for the local processor's
memory, one for our processor board's shared memory and one for the
on-chip memory).

    The ptr parameter to Free.Mem is not a VAL INT. It should be the
exact same actual parameter passed as ptr in the call to Alloc.Mem.

"Addresses" were the (INT) index into the memory pool vector. You'd
send a message to the allocator process (or more specifically call a
proc that hid the protocol) requesting some memory and it would return
the index of the first word you could use. To free something you sent
the index back to the allocator and it would put a block onto the
freelist. This is quite open to abuse of course but in our environment
we had control and there are a number of simple techniques that assist
in detecting memory corruption and mis-use. We didn't have all that
much trouble.

This scheme goes totally against occam's usage checking! We were
passing a single vector to nearly every process in the system and
those processes are accessing practically any part of the vector. Not
a checkable thing really.

Okay this method is not safe (in fact its downright dangerous!) but it
gave us flexible dynamic allocation facilities. I'm not advocating its
use (its not wise to "bend" occam, if you want to do these things use
a language that supports them properly) but it did work.

-- 
Andy Newman (andy@research.canon.oz.au)

In article <BxyB6I.LLF@research.canon.oz.au> andy@research.canon.oz.au (Andy Newman) writes:
>    Yes we used CHAN OF ANY - it allowed our configuration langauage and
>communications system work! The two element vector holds the "to"
>channel and the "from" channel used to perform the RPC with the memory
>allocator process (this use exposed a limitation in the compiler, it
>assumed all channels in a vector were used in the same "direction")

This isn't a limitation of the _compiler_, it is a limitation of the
language: page 76 of the occam reference manual says that a channel
parameter may not be used for both input and output in a procedure.
This is so that an implementation can just remember that it's
either an `input channel array' or an `output channel array'
for usage checking, without having to keep a bit vector for each element.
It also means that arrays of unknown size are treated similarly.

---
Conor O'Neill, Software Group, INMOS Ltd., UK.
UK: conor@inmos.co.uk		US: conor@inmos.com
"It's state-of-the-art" "But it doesn't work!" "That is the state-of-the-art".

Andy Newman (andy@research.canon.oz.au) wrote recently about his
involvement with a project that developed a Dynamic Memory Allocator.

I liked his account of the memory allocation procedure - and his honesty
about its non-adherence to the occam usage checking rules!

I have one comment to add.  The parallel process in the middle (the
allocator process) can very easily become the performance bottleneck of
the whole of the rest of the system, since it queues up requests and
responds to them serially.

Apart from the problem of distributing permissions to access memory blocks
of varying sizes, one might consider implementing such an allocator with a
little extra buffering.  This would have the effect of eagerly outputting
(in parallel) a permission token to each process that it serves.  Only
when a process accepts its token does the allocator reschedule and send it
another one.  Returned tokens are processed along a different set of
channels which are quite separate from the first set.  Think of the
allocator and the client processes as each being separated in both
directions by small FIFOs, and notice the reduced latency that this
provides.  Obviously, more tokens will be in transit at any time, and the
scheme will use its memory pool less effectively - but the benefit could
be that the system runs rather faster.

A similar benefit could be gained when implementing the TCP/IP
communications protocol, if one has also decided to use the 'mbuf' memory
allocation scheme suggested in its specification.  In this case, and under
heavy network loads, the allocator will be very busy and the overhead
could be quite noticeable.  Of course, this shared memory model might not
be the best choice these days, anyway!


Roger M.A. Peel
Department of Electronic and     Phone : +44 483 509284   (0483 from UK)
      Electrical Engineering       Fax : +44 483 34139
University of Surrey             Telex : 859331
Guildford                        JANET : R.Peel@uk.ac.surrey.ee
Surrey  GU2 5XH                   UUCP : ...mcsun!ukc!ee.surrey.ac.uk!R.Peel
United Kingdom


-- 
Roger Peel