# Cost Semantics for Parallelism

Cost semantics is to discuss: How long do programs run (abstractly)?

The idea of cost semantics for parallelism is that we have the concrete ability to compute simultaneously.

# Simple Example of Product Types

For sequential computation we have:

\[\frac{e_1\mapsto_{seq}e_1'}{(e_1,e_2)\mapsto_{seq}(e_1',e_2)}\] \[\frac{e_1\ val;e_2\mapsto_{seq}e_2'}{(e_1,e_2)\mapsto_{seq}(e_1,e_2')}\]For parallel computation we have:

\[\frac{e_1\mapsto_{par}e_1';e_2\mapsto_{par}e_2'}{(e_1,e_2)\mapsto_{par}(e_1',e_2')}\]# Deterministic Parallelism

\[e\mapsto_{seq}^*v\ iff\ e\Downarrow v\ iff\ e\mapsto_{par}^*v\]It means that we are getting the same answer, just (potentially) faster.

Given a closed program $e$, we can count the number of $\mapsto_{seq}$ (or $\mapsto^{w}$ “work”) and the number of $\mapsto_{par}$ (or $\mapsto^{s}$ “span”)

# Cost Semantics

We annotate $e\Downarrow^{w,s}v$ to keep tract of work and span.

\[\frac{e_1\Downarrow^{w_1,s_1}v_1;e_2\Downarrow^{w_2,s_2}v_2} {e_1,e_2)\Downarrow^{w_1+w_2,max(s_1,s_2)}(v_1,v_2)}\] \[\frac{e_1\Downarrow^{w_1,s_1}(v_1,v_2);[v_1/x][v_2/y]e_2\Downarrow^{w_2,s_2}v} {let(x,y)=e_1\ in\ e_2\Downarrow^{w_1+w_2+1,s_1+s_2+1}v}\] \[If\ e\Downarrow^{w,s}v\ then\ e\mapsto^w_{seq}v\ and\ e\mapsto^s_{par}v\] \[If\ e\mapsto_{seq}^w v\ then \exists s\ e\Downarrow^{w,s}v\] \[If\ e\mapsto_{par}^s v\ then \exists w\ e\Downarrow^{w,s}v\] \[If\ e\Downarrow^{w,s}v\ and\ e\Downarrow^{w',s'}v\ then\ w=w',s=s'\]# Brent’s Principle

In general, it is a principle about how work and span predict evaluation in some machine.

For example, for a machine that has $p$ processors:

\[If\ e\Downarrow^{w,s}v\ then\ e\ can\ be\ run\ to\ v\ in\ time\ O(max(\frac{w}{p},s))\]# Machine with States

## Local Transitions

\[\gamma\Sigma_{a_1,...,a_n}\{a_1\hookrightarrow s_1\otimes...a_n\hookrightarrow s_n\}\]$a$’s are names for the tasks, and

\[s:=e|join[a](x.e)|join[a_1,a_2](x,y.e)\]Where \(join[a](x.e)\) means to “wait for task $a$ to complete, and then plug it’s value in for $x$”, and \(join[a_1,a_2](x,y.e)\) means to wait for two tasks.

Suppose one of $e_1,e_2$ is not $val$, we have the following, which is also called `fork`

:

And we have `join`

:

Similarly for `let`

:

## Global Transitions

- Select $1\leq k\leq p$ tasks to make local transitions
- Step locally
- Each creates or garbage collectos processes (global synchronization by $\alpha-renaming$)

## Scheduling

How to we “Select $1\leq k\leq p$ tasks to make local transitions” e.g DFS, BFS