[m-rev.] for review: parallel execution mechanism (2/2)

Julien Fischer juliensf at csse.unimelb.edu.au
Wed Sep 20 17:22:15 AEST 2006


On Tue, 12 Sep 2006, Peter Wang wrote:

> Index: compiler/par_conj_gen.m
> ===================================================================
> RCS file: /home/mercury/mercury1/repository/mercury/compiler/par_conj_gen.m,v
> retrieving revision 1.28
> diff -u -r1.28 par_conj_gen.m
> --- compiler/par_conj_gen.m	22 Aug 2006 05:04:01 -0000	1.28
> +++ compiler/par_conj_gen.m	11 Sep 2006 05:04:48 -0000
> @@ -7,7 +7,7 @@
> %---------------------------------------------------------------------------%
> %
> % File: par_conj.m.
> -% Main authors: conway.
> +% Main authors: conway, wangp.
> %
> % The predicates of this module generate code for parallel conjunctions.
> %
> @@ -30,9 +30,8 @@
> %     predictable termination properties.
> %     Parallel conjunction does not of itself suggest any information
> %     about which order two goals should be executed, however if
> -%     coroutining (not currently implemented) is being used, then the
> -%     data dependencies between the two goals will constrain the order
> -%     of execution at runtime.
> +%     coroutining is being used, then the data dependencies between
> +%     the two goals will constrain the order of execution at runtime.
> %
> %   [Mode correctness]
> %   - `,'/2 has a *sequential* behaviour `A, B' proves `A' *then*
> @@ -47,23 +46,13 @@
> %     and-parallelism), but an and-parallel goal may use bindings made
> %     in conjoined goals which may lead to coroutining.
> %
> -% The current implementation only supports independent and-parallelism.
> +% The current implementation mainly supports independent and-parallelism.
> % The syntax for parallel conjunction is `&'/2 which behaves like `,'/2
> % in that sequences get flattened (ie A & (B & C) <=> (A & B) & C).
> +% A subset of dependent and-parallelism is supported (see dep_par_conj.m).
> %

How about:

 	The current implementation supports independent and-parallism
 	and a subset of dependent and-parallism (see dep_par_conj.m).

> % The code generated for a parallel conjunction consists of a piece of
> % initialization code which creates a term on the heap to be used for
> % controlling the synchronization of the conjuncts and the code for the
> -% conjuncts each proceeded by a command to start the conjunct as a new
> -% thread of execution (except the last which executes in the "parent"
> -% thread), and each succeeded by a command that signals that the execution
> -% of the conjunct has completed and terminates the thread (except for
> -% the "parent" thread which suspends till all the other parallel conjuncts
> -% have terminated, when it will be woken up). The synchronization terms
> -% are referred to in the code as 'sync_term's.
> +% conjuncts.  The synchronization terms are referred to in the code as
> +% 'sync_term's.  Conjuncts are executed "left to right".  At the start of
> +% the i'th conjunct is a command to "spark" the i+1'th conjunct, i.e.
> +% record enough information to begin executing the next conjunct either
> +% in parallel, or to return to it later when the current conjunct ends.

s/later when/after/

> +% At the end of each conjunct is a command that checks if all the
> +% conjuncts of the parallel conjunction have been executed and completed.
> +% If not, we begin execution of the next conjunct as recorded in the
> +% spark.  If so, the parallel conjunction is complete.  (In reality it's
> +% a lot more complicated.)

Unfortunately the Mercury developers (particularly those who will
have to maintain this piece of code) need to know about reality -
how/why is it more complicated?

...

> Index: runtime/mercury_context.c
> ===================================================================
> RCS file: /home/mercury/mercury1/repository/mercury/runtime/mercury_context.c,v
> retrieving revision 1.47
> diff -u -r1.47 mercury_context.c
> --- runtime/mercury_context.c	5 Jul 2006 03:00:43 -0000	1.47
> +++ runtime/mercury_context.c	11 Sep 2006 05:06:57 -0000
> @@ -33,10 +33,20 @@
> #include "mercury_reg_workarounds.h"    /* for `MR_fd*' stuff */
>
> static  void            MR_init_context_maybe_generator(MR_Context *c,
> -                            MR_Generator *gen);
> +                            const char *id, MR_Generator *gen);
>
> +/*---------------------------------------------------------------------------*/
> +
> +/*
> +** The run queue and spark queue are protected and signalled with the
> +** same lock and condition variable.
> +*/
> MR_Context              *MR_runqueue_head;
> MR_Context              *MR_runqueue_tail;
> +#ifndef MR_HIGHLEVEL_CODE
> +  MR_Spark              *MR_spark_queue_head;
> +  MR_Spark              *MR_spark_queue_tail;
> +#endif
> #ifdef  MR_THREAD_SAFE
>   MercuryLock           MR_runqueue_lock;
>   MercuryCond           MR_runqueue_cond;
> @@ -59,6 +69,11 @@
>   static MercuryLock    free_context_list_lock;
> #endif
>
> +int MR_num_idle_engines = 0;
> +int MR_num_outstanding_contexts_and_sparks = 0;


Is there any reason why these need to be signed ints?

> +
> +/*---------------------------------------------------------------------------*/
> +
> void
> MR_init_thread_stuff(void)
> {
> @@ -87,8 +102,9 @@
> #endif
> }
>
> -void
> -MR_init_context(MR_Context *c, const char *id, MR_Generator *gen)
> +static void
> +MR_init_context_maybe_generator(MR_Context *c, const char *id,
> +    MR_Generator *gen)
> {
>     c->MR_ctxt_id = id;
>     c->MR_ctxt_next = NULL;
> @@ -100,29 +116,29 @@
> #ifndef MR_HIGHLEVEL_CODE
>     c->MR_ctxt_succip = MR_ENTRY(MR_do_not_reached);
>
> -    if (c->MR_ctxt_detstack_zone != NULL) {
> -        MR_reset_redzone(c->MR_ctxt_detstack_zone);


I'm not certain that removing the calls to MR_reset_redzone is the right
thing to be do here.  (I don't know enough about this code to be able to
say so for sure.)


> -    } else if (gen != NULL) {
> -        c->MR_ctxt_detstack_zone = MR_create_zone("gen_detstack",
> -            0, MR_gen_detstack_size, MR_next_offset(),
> -            MR_gen_detstack_zone_size, MR_default_handler);
> -    } else {
> -        c->MR_ctxt_detstack_zone = MR_create_zone("detstack",
> -            0, MR_detstack_size, MR_next_offset(),
> -            MR_detstack_zone_size, MR_default_handler);
> +    if (c->MR_ctxt_detstack_zone == NULL) {
> +        if (gen != NULL) {
> +            c->MR_ctxt_detstack_zone = MR_create_zone("gen_detstack",
> +                    0, MR_gen_detstack_size, MR_next_offset(),
> +                    MR_gen_detstack_zone_size, MR_default_handler);
> +        } else {
> +            c->MR_ctxt_detstack_zone = MR_create_zone("detstack",
> +                    0, MR_detstack_size, MR_next_offset(),
> +                    MR_detstack_zone_size, MR_default_handler);
> +        }
>     }
>     c->MR_ctxt_sp = c->MR_ctxt_detstack_zone->MR_zone_min;
>
> -    if (c->MR_ctxt_nondetstack_zone != NULL) {
> -        MR_reset_redzone(c->MR_ctxt_nondetstack_zone);
> -    } else if (gen != NULL) {
> -        c->MR_ctxt_nondetstack_zone = MR_create_zone("gen_nondetstack",
> -            0, MR_gen_nonstack_size, MR_next_offset(),
> -            MR_gen_nonstack_zone_size, MR_default_handler);
> -    } else {
> -        c->MR_ctxt_nondetstack_zone = MR_create_zone("nondetstack",
> -            0, MR_nondstack_size, MR_next_offset(),
> -            MR_nondstack_zone_size, MR_default_handler);
> +    if (c->MR_ctxt_nondetstack_zone == NULL) {
> +        if (gen != NULL) {
> +            c->MR_ctxt_nondetstack_zone = MR_create_zone("gen_nondetstack",
> +                    0, MR_gen_nonstack_size, MR_next_offset(),
> +                    MR_gen_nonstack_zone_size, MR_default_handler);
> +        } else {
> +            c->MR_ctxt_nondetstack_zone = MR_create_zone("nondetstack",
> +                    0, MR_nondstack_size, MR_next_offset(),
> +                    MR_nondstack_zone_size, MR_default_handler);
> +        }
>     }
>     /*
>     ** Note that maxfr and curfr point to the last word in the frame,
> @@ -147,27 +163,21 @@
>             "generator and stack_copy");
>     }
>
> -    if (c->MR_ctxt_genstack_zone != NULL) {
> -        MR_reset_redzone(c->MR_ctxt_genstack_zone);
> -    } else {
> +    if (c->MR_ctxt_genstack_zone == NULL) {
>         c->MR_ctxt_genstack_zone = MR_create_zone("genstack", 0,
>             MR_genstack_size, MR_next_offset(),
>             MR_genstack_zone_size, MR_default_handler);
>     }
>     c->MR_ctxt_gen_next = 0;
>
> -    if (c->MR_ctxt_cutstack_zone != NULL) {
> -        MR_reset_redzone(c->MR_ctxt_cutstack_zone);
> -    } else {
> +    if (c->MR_ctxt_cutstack_zone == NULL) {
>         c->MR_ctxt_cutstack_zone = MR_create_zone("cutstack", 0,
>             MR_cutstack_size, MR_next_offset(),
>             MR_cutstack_zone_size, MR_default_handler);
>     }
>     c->MR_ctxt_cut_next = 0;
>
> -    if (c->MR_ctxt_pnegstack_zone != NULL) {
> -        MR_reset_redzone(c->MR_ctxt_pnegstack_zone);
> -    } else {
> +    if (c->MR_ctxt_pnegstack_zone == NULL) {
>         c->MR_ctxt_pnegstack_zone = MR_create_zone("pnegstack", 0,
>             MR_pnegstack_size, MR_next_offset(),
>             MR_pnegstack_zone_size, MR_default_handler);
> @@ -178,6 +188,10 @@
>   #ifdef MR_USE_MINIMAL_MODEL_OWN_STACKS
>     c->MR_ctxt_owner_generator = gen;
>   #endif /* MR_USE_MINIMAL_MODEL_OWN_STACKS */
> +
> +    c->MR_ctxt_parent_sp = NULL;
> +    c->MR_ctxt_spark_stack = NULL;
> +
> #endif /* !MR_HIGHLEVEL_CODE */
>
> #ifdef MR_USE_TRAIL
> @@ -185,9 +199,7 @@
>         MR_fatal_error("MR_init_context_maybe_generator: generator and trail");
>     }
>
> -    if (c->MR_ctxt_trail_zone != NULL) {
> -        MR_reset_redzone(c->MR_ctxt_trail_zone);
> -    } else {
> +    if (c->MR_ctxt_trail_zone == NULL) {
>         c->MR_ctxt_trail_zone = MR_create_zone("trail", 0,
>             MR_trail_size, MR_next_offset(),
>             MR_trail_zone_size, MR_default_handler);
> @@ -214,6 +226,9 @@
>     MR_Context  *c;
>
>     MR_LOCK(&free_context_list_lock, "create_context");
> +
> +    MR_num_outstanding_contexts_and_sparks++;
> +
>     if (free_context_list == NULL) {
>         MR_UNLOCK(&free_context_list_lock, "create_context i");
>         c = MR_GC_NEW(MR_Context);
> @@ -230,14 +245,30 @@
>         MR_UNLOCK(&free_context_list_lock, "create_context ii");
>     }
>
> -    MR_init_context(c, id, gen);
> +    MR_init_context_maybe_generator(c, id, gen);
>     return c;
> }
>

,,,


> Index: runtime/mercury_context.h
> ===================================================================
> RCS file: /home/mercury/mercury1/repository/mercury/runtime/mercury_context.h,v
> retrieving revision 1.30
> diff -u -r1.30 mercury_context.h
> --- runtime/mercury_context.h	8 Mar 2006 08:35:38 -0000	1.30
> +++ runtime/mercury_context.h	10 Sep 2006 13:37:23 -0000
> @@ -23,10 +23,10 @@
> ** by `context_ptr'. The context contains no rN or fN registers - all
> ** registers are "context save" (by analogy to caller-save).
> **
> -** When a new context is created information is passed to the new context
> -** on the stack. The top stackframe of the current context is copied to
> -** become the first det stackframe in the new process. (XXX this will need
> -** fixing eventually to include the nondet frame as well.)
> +** When a new context is created information is passed to and from the
> +** new context via the stack frame of the procedure that originated the
> +** parallel conjunction. The code of a parallel conjunct has access
> +** to the procedure's stack frame via the `parent_sp' register.
> **
> ** Contexts can migrate transparently between multiple Posix threads.
> **
> @@ -101,6 +101,9 @@
> ** pnegstack_zone   The possibly_negated_context stack zone for this context.
> ** pneg_next        The saved pneg_next for this context.
> **
> +** parent_sp        The saved parent_sp for this context.
> +** spark_stack      The sparks generated by this context, in a stack.
> +**
> ** trail_zone       The trail zone for this context.
> ** trail_ptr        The saved MR_trail_ptr for this context.
> ** ticket_counter   The saved MR_ticket_counter for this context.
> @@ -114,6 +117,8 @@
> */
>
> typedef struct MR_Context_Struct MR_Context;
> +typedef struct MR_Spark_Struct MR_Spark;
> +
> struct MR_Context_Struct {
>     const char          *MR_ctxt_id;
>     MR_Context          *MR_ctxt_next;
> @@ -146,6 +151,9 @@
>   #ifdef MR_USE_MINIMAL_MODEL_OWN_STACKS
>     MR_Generator        *MR_ctxt_owner_generator;
>   #endif /* MR_USE_MINIMAL_MODEL_OWN_STACKS */
> +
> +    MR_Word             *MR_ctxt_parent_sp;
> +    MR_Spark            *MR_ctxt_spark_stack;
> #endif /* !MR_HIGHLEVEL_CODE */
>
> #ifdef  MR_USE_TRAIL
> @@ -162,10 +170,41 @@
> };
>
> /*
> +** A spark contains just enough information to begin execution of a parallel
> +** conjunct.  Sparks are allocated on the heap, and can be stored in a
> +** context's spark stack, or in the global spark queue.  In the former case, a
> +** spark will eventually be executed on the same context (same detstack, etc.)

s/on the/by the/


> +** as the code that generated the spark.  In the latter case the spark can be
> +** picked up and executed by any idle engine in a different context.
> +**
> +** In the current implementation a spark is put on the global spark queue if,
> +** at the time a fork instruction is reached, we think the spark has a chance

s/at/by/


> +** of being picked up for execution by an idle engine.  Otherwise the spark
> +** goes on the context's spark stack.  This is an irrevocable decision.

 	At the moment this is an irrevocable ...

> +** A future possibility is to allow idle engines to steal work from the cold
> +** end of some context's spark stack.
> +*/
> +#ifndef MR_HIGHLEVEL_CODE
> +struct MR_Spark_Struct {
> +    MR_Spark            *MR_spark_next;
> +    MR_Code             *MR_spark_resume;
> +    MR_Word             *MR_spark_parent_sp;
> +};
> +#endif
> +
> +/*
> ** The runqueue is a linked list of contexts that are runnable.
> +** The spark_queue is a linked list of sparks that are runnable.
> +** We keep them separate to prioritise contexts (which are mainly
> +** computations which have already started) over sparks (which are
> +** computations which have not begun).
> */
> extern      MR_Context  *MR_runqueue_head;
> extern      MR_Context  *MR_runqueue_tail;
> +#ifndef MR_HIGHLEVEL_CODE
> +  extern    MR_Spark    *MR_spark_queue_head;
> +  extern    MR_Spark    *MR_spark_queue_tail;
> +#endif
> #ifdef  MR_THREAD_SAFE
>   extern    MercuryLock MR_runqueue_lock;
>   extern    MercuryCond MR_runqueue_cond;
> @@ -207,6 +246,32 @@
> #endif
>
> /*
> +** The number of engines waiting for work.
> +** We don't protect it with a separate lock, but updates to it are made while
> +** holding the MR_runqueue_lock.  Reads are made without the lock.  We may need
> +** to use atomic instructions or memory fences on some architectures.
> +*/

That last sentence should be an XXX.

> +extern  int         MR_num_idle_engines;
> +
> +/*
> +** The number of contexts that are not in the free list (i.e. are executing or
> +** suspended) plus the number of sparks in the spark queue.  We count those
> +** sparks as they can quickly accumulate on the spark queue before any of them
> +** are taken up for execution.  Once they do get taken up, many contexts would
> +** need to be allocated to execute them.  Sparks not on the spark queue are
> +** currently guaranteed to be executed on their originating context so won't
> +** cause allocation of more contexts.
> +**
> +** What we are mainly interested in here is preventing too many contexts from
> +** being allocated, as each context is quite large and we can quickly run out
> +** of memory.  Another problem is due to the context free list and conservative
> +** garbage collection: every context ever allocated will be scanned.  (Getting
> +** the garbage collector not to scan contexts on the free list should be
> +** possible though.)
> +*/
> +extern  int         MR_num_outstanding_contexts_and_sparks;
> +
> +/*
> ** Initializes a context structure, and gives it the given id. If gen is
> ** non-NULL, the context is for the given generator.
> */

...

> Index: runtime/mercury_wrapper.h
> ===================================================================
> RCS file: /home/mercury/mercury1/repository/mercury/runtime/mercury_wrapper.h,v
> retrieving revision 1.74
> diff -u -r1.74 mercury_wrapper.h
> --- runtime/mercury_wrapper.h	7 Aug 2006 06:21:32 -0000	1.74
> +++ runtime/mercury_wrapper.h	10 Sep 2006 05:45:56 -0000
> @@ -225,6 +225,15 @@
> /* heap expansion factor for accurate GC (see mercury_accurate_gc.c) */
> extern  double		MR_heap_expansion_factor;
>
> +/* number of outstanding contexts we can create per thread (soft limit) */
> +extern	MR_Unsigned	MR_contexts_per_thread;

Please fix the formatting of that comment, e.g.

 	/*
 	** The number of outstanding contexts we can create per thread
 	** (soft limit).
 	*/

> +/*
> +** number of outstanding contexts we can create
> +** (MR_contexts_per_thread * MR_num_threads)
> +*/
> +extern	MR_Unsigned	MR_max_outstanding_contexts;

Likewise (and in a few other spots as well).

Julien.
--------------------------------------------------------------------------
mercury-reviews mailing list
Post messages to:       mercury-reviews at csse.unimelb.edu.au
Administrative Queries: owner-mercury-reviews at csse.unimelb.edu.au
Subscriptions:          mercury-reviews-request at csse.unimelb.edu.au
--------------------------------------------------------------------------



More information about the reviews mailing list