parallel-algorithms

Parallel Algorithms

Overview

Core principle: analyze correctness before speed. A fork-join keyword says work may run in parallel; it does not prove race freedom, useful speedup, or production scalability.

Shared CLRS Conventions

Use the parent clrs skill for mathematical formatting, theorem tone, and answer discipline. Keep every bound, recurrence, ratio, and inequality in display LaTeX blocks. Keep Markdown tables verbal; put the formulas in nearby display blocks.

Output Discipline for Parallel Answers

Parallel-algorithm answers are notation-heavy, so formatting leaks are common. Do not announce that this skill is being used. Start with the review or solution.

Use prose names in sentences and tables, then put the notation in display blocks. For example, say "the work is quadratic" in prose, then show the bound below in a display block. Do not put work/span symbols, processor-count formulas, slackness ratios, or asymptotic bounds in table cells, headings, inline math, or inline code spans.

When a table needs a formula, write a verbal label in the cell, such as "quadratic work" or "polylogarithmic span," and put the exact expression immediately after the table.

Arithmetic is also a formula. Processor estimates such as a work term divided by a processor count plus a span term must be displayed in LaTeX blocks, not written as prose-line arithmetic with +, =, /, ÷, powers, or asymptotic notation.

Safe pattern:

The estimate for the first candidate is below.

$$
\frac{2048}{512} + 1 = 5
$$

The estimate for the second candidate is below.

$$
\frac{1024}{512} + 8 = 10
$$

Unsafe pattern:

Version A: 2048 / 512 + 1 = 5 seconds.

When to Use

Use this skill for:

• fork-join pseudocode using spawn, sync, or parallel for;
• serial projection, trace DAGs, strands, critical paths, and sequential consistency;
• work, span, speedup, parallelism, slackness, and greedy scheduling analysis;
• determinacy race reviews and shared-memory update patterns;
• parallel loops, matrix-vector multiplication, matrix multiplication, Strassen, parallel merge, and parallel merge sort;
• parallel reductions, scans, stencils, and randomized parallel algorithms;
• production reviews of textbook parallel algorithms, task granularity, scheduler overhead, work stealing, and coarsening.