Thread Local Remember Tables - Maple Help

# Online Help

###### All Products    Maple    MapleSim

Home : Support : Online Help : System : Information : Updates : Maple 17 : Thread Local Remember Tables

Thread Local Remember Tables

In Maple 17 remember tables are thread local by default.  When a procedure with a remember table is called by multiple threads, the remembered results are only available on the thread that created them.  This differs from previous versions of Maple where remember tables were shared between threads, thus changes to the table in one thread would effect other threads.

This change allows a procedure with a remember table that works when run on a single thread to continue to work when run in parallel, regardless of how the procedure uses its remember table.  In previous versions of Maple a procedure could manipulate its remember table in such away as to break the behavior of a parallel execution of the procedure.

The following procedures implement a sequence similar to Fibonacci, where each term is the sum of the previous two terms, however the user can specify the initial values.  A remember table is used to improve the performance of this procedure.  The initial values are stored in FibsHelper's remember table where they act as the termination condition for the recursion.

 > FibsHelper := proc (n::nonnegint)  option remember;  FibsHelper(n-1)+FibsHelper(n-2)   end proc;
 ${\mathrm{FibsHelper}}{:=}{\mathbf{proc}}\left({n}{::}{\mathrm{nonnegint}}\right)\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathbf{option}}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathrm{remember}}{;}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathrm{FibsHelper}}{}\left({n}{âˆ’}{1}\right){+}{\mathrm{FibsHelper}}{}\left({n}{âˆ’}{2}\right)\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathbf{end proc}}$ (1)

 > Fibs := proc (n::nonnegint, t1 := 1, t2 := 1)  subsop(4 = NULL, op(FibsHelper));  FibsHelper(0) := t1;  FibsHelper(1) := t2;  FibsHelper(n)  end proc;
 ${\mathrm{Fibs}}{:=}{\mathbf{proc}}\left({n}{::}{\mathrm{nonnegint}}{,}{\mathrm{t1}}{:=}{1}{,}{\mathrm{t2}}{:=}{1}\right)\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathrm{subsop}}{}\left({4}{=}{\mathrm{NULL}}{,}{\mathrm{op}}{}\left({\mathrm{FibsHelper}}\right)\right){;}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathrm{FibsHelper}}{}\left({0}\right){:=}{\mathrm{t1}}{;}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathrm{FibsHelper}}{}\left({1}\right){:=}{\mathrm{t2}}{;}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathrm{FibsHelper}}{}\left({n}\right)\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathbf{end proc}}$ (2)

 > seq(Fibs(i), i = 0 .. 10);
 ${1}{,}{1}{,}{2}{,}{3}{,}{5}{,}{8}{,}{13}{,}{21}{,}{34}{,}{55}{,}{89}$ (3)

 > seq(Fibs(i, 2, 2), i = 0 .. 10);
 ${2}{,}{2}{,}{4}{,}{6}{,}{10}{,}{16}{,}{26}{,}{42}{,}{68}{,}{110}{,}{178}$ (4)



 > seq(Fibs(i, 2, 38), i = 0 .. 10);
 ${2}{,}{38}{,}{40}{,}{78}{,}{118}{,}{196}{,}{314}{,}{510}{,}{824}{,}{1334}{,}{2158}$ (5)

This works when run on a single thread, and in Maple 17, it works when run in parallel.

 > task := proc (n, t1, t2) local i; [seq(Fibs(i, t1, t2), i = 0 .. 10)] end proc;
 ${\mathrm{task}}{:=}{\mathbf{proc}}\left({n}{,}{\mathrm{t1}}{,}{\mathrm{t2}}\right)\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathbf{local}}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{i}{;}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}\left[{\mathrm{seq}}{}\left({\mathrm{Fibs}}{}\left({i}{,}{\mathrm{t1}}{,}{\mathrm{t2}}\right){,}{i}{=}{0}{..}{10}\right)\right]\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathbf{end proc}}$ (6)

 > Threads:-Task:-Start(passed, Tasks = [task, [10, 1, 1], [10, 2, 2], [10, 2, 38]]);
 $\left[{1}{,}{1}{,}{2}{,}{3}{,}{5}{,}{8}{,}{13}{,}{21}{,}{34}{,}{55}{,}{89}\right]{,}\left[{2}{,}{2}{,}{4}{,}{6}{,}{10}{,}{16}{,}{26}{,}{42}{,}{68}{,}{110}{,}{178}\right]{,}\left[{2}{,}{38}{,}{40}{,}{78}{,}{118}{,}{196}{,}{314}{,}{510}{,}{824}{,}{1334}{,}{2158}\right]$ (7)

In previous versions of Maple, the parallel evaluation can fail.

A procedure with a shared remember table (Maple's previous behavior) can still be created in Maple 17 by specifying the shared option.  The following procedure will work when used in a single thread, but not in parallel.

 > SharedFibsHelper := proc (n::nonnegint)  options remember, shared;  SharedFibsHelper(n-1)+SharedFibsHelper(n-2)  end proc;
 ${\mathrm{SharedFibsHelper}}{:=}{\mathbf{proc}}\left({n}{::}{\mathrm{nonnegint}}\right)\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathbf{option}}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathrm{remember}}{,}{\mathrm{shared}}{;}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathrm{SharedFibsHelper}}{}\left({n}{âˆ’}{1}\right){+}{\mathrm{SharedFibsHelper}}{}\left({n}{âˆ’}{2}\right)\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathbf{end proc}}$ (8)

 > SharedFibs := proc (n::nonnegint, t1 := 1, t2 := 1)  subsop(4 = NULL, op(SharedFibsHelper));  SharedFibsHelper(0) := t1;  SharedFibsHelper(1) := t2;  SharedFibsHelper(n)  end proc;
 ${\mathrm{SharedFibs}}{:=}{\mathbf{proc}}\left({n}{::}{\mathrm{nonnegint}}{,}{\mathrm{t1}}{:=}{1}{,}{\mathrm{t2}}{:=}{1}\right)\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathrm{subsop}}{}\left({4}{=}{\mathrm{NULL}}{,}{\mathrm{op}}{}\left({\mathrm{SharedFibsHelper}}\right)\right){;}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathrm{SharedFibsHelper}}{}\left({0}\right){:=}{\mathrm{t1}}{;}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathrm{SharedFibsHelper}}{}\left({1}\right){:=}{\mathrm{t2}}{;}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathrm{SharedFibsHelper}}{}\left({n}\right)\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathbf{end proc}}$ (9)

 > seq(SharedFibs(i), i = 0 .. 10);
 ${1}{,}{1}{,}{2}{,}{3}{,}{5}{,}{8}{,}{13}{,}{21}{,}{34}{,}{55}{,}{89}$ (10)
 > seq(SharedFibs(i, 2, 2), i = 0 .. 10);
 ${2}{,}{2}{,}{4}{,}{6}{,}{10}{,}{16}{,}{26}{,}{42}{,}{68}{,}{110}{,}{178}$ (11)
 > seq(SharedFibs(i, 2, 38), i = 0 .. 10);
 ${2}{,}{38}{,}{40}{,}{78}{,}{118}{,}{196}{,}{314}{,}{510}{,}{824}{,}{1334}{,}{2158}$ (12)

When SharedFibs is called in parallel, incorrect results may be computed.  Note that due to the nature of parallel execution, incorrect results may not occur on every run.

 > sharedTask := proc (n, t1, t2)  local i;  [seq(SharedFibs(i, t1, t2), i = 0 .. 10)]  end proc;
 ${\mathrm{sharedTask}}{:=}{\mathbf{proc}}\left({n}{,}{\mathrm{t1}}{,}{\mathrm{t2}}\right)\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathbf{local}}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{i}{;}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}\left[{\mathrm{seq}}{}\left({\mathrm{SharedFibs}}{}\left({i}{,}{\mathrm{t1}}{,}{\mathrm{t2}}\right){,}{i}{=}{0}{..}{10}\right)\right]\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathbf{end proc}}$ (13)
 > Threads:-Task:-Start(passed, Tasks = [sharedTask, [10, 1, 1], [10, 2, 2], [10, 2, 38]]);
 $\left[{1}{,}{1}{,}{2}{,}{3}{,}{5}{,}{8}{,}{13}{,}{21}{,}{34}{,}{650}{,}{89}\right]{,}\left[{2}{,}{2}{,}{4}{,}{6}{,}{10}{,}{16}{,}{26}{,}{42}{,}{68}{,}{110}{,}{178}\right]{,}\left[{2}{,}{38}{,}{40}{,}{78}{,}{118}{,}{196}{,}{314}{,}{510}{,}{34}{,}{1334}{,}{2158}\right]$ (14)

There are various things that can go wrong.  Clearing the remember table in one thread can remove another thread's initial values, which will cause SharedFibsHelper to be called with invalid inputs (negative numbers).  One threads initial values can overwrite another threads, which will cause that thread to compute incorrect results.  One threads remembered values can be used by a different thread where those values are incorrect.

A procedure with a shared remember table can work correctly in parallel and computed results can be shared across threads.  However there are may complexities that require  procedures with shared remember tables to be written with care.  Maple 17's thread local remember tables makes it easier for procedure written for single threaded execution to work in parallel.

 See Also