cloning

Cloning is needed to parallelize code. In order to make the parallelized code memory efficient, it is required that only the objects that really need cloning are cloned. Other objects can shared memory.

We define a flag safety for each node that indicates if it is thread-safe to evaluate this node in different threads concurrently. Unsafety propagates up the hierarchy. Any node that has an unsafe flag in its descendants must be copied.

Strategy

The strategy is thread-unsafe by itself.

Safety pass O(n)

This is a graph coloring problem

• Let each node have a flag enum is_safe { S_UNKNOWN, S_SAFE, S_UNSAFE} . Make sure that nodes that are initialized have S_UNKNOWN.

• pseudo code:

is_safe node::safetyFlagSetting():

if !this.isSafe():
is_safe_ = S_UNSAFE
else:
for node in dependencies:
if node.is_safe_ is S_UNKNOWN:
result = node.safetyFlagSetting()
else:
result = node.is_safe_
if result = S_UNSAFE:
is_safe_ = S_UNSAFE
break
is_safe_ = S_SAFE
return is_safe_

Copying pass O(n)

This is a graph coloring problem

• Let each node have a field SharedObjectNode * copy_to_. Make sure that nodes that are initialized have a null pointer here.
• pseudo code

is_safe node::deepcopy():

if is_safe_ = S_UNSAFE
if (!copy_to_)
copy_to_ = clone()
for node in dependencies:
node.deepcopy()
    

Clean up phase O(n)

• reset the is_safe and copy_to_ flags