UCT CSC2002 / 2023
Searching terrain in parallel
Split random terrain searches into fork/join tasks and reduce local minima into a shared result.
UCT / COURSE CONTEXT / 2023
CSC2002S · Computer Science 2002
Concurrent programming, computer architecture and interface design, with Java and assembler practicals.
Conceptual task lanes based on fork/join terrain search. Equal-length blocks are explanatory, not measured runtimes or a promised speedup. Shared visited-state contention and unseeded historical inputs limit direct comparisons.
ENGINEERING PERSPECTIVE
Inside the work
Explore when splitting independent searches is worth the overhead of parallel tasks. The terrain problem makes task granularity, result reduction and shared-state correctness tangible.
- Java ForkJoinPool / RecursiveTask
- Fork a left task, compute the right, join and reduce local minima.
- Terrain/search framework
- Supplied serial search and terrain/cache code support the individual parallel extension.
Partition searches
Halve the work array above the cutoff; execute smaller leaves sequentially.
- Divide and conquer
- Split the search array recursively until a sequential cutoff is reached.
- Granularity
- The source uses a cutoff of 1,000; the report explores smaller/larger cutoffs rather than a universal best setting.
- Benchmark validity
- Different random starting points, shared cache state and JVM warmup complicate speedup comparisons.
What the demonstration establishes
The browser explanation illustrates fork/join structure. Fresh serial/parallel smoke runs completed; 12 ms versus 10 ms on differing random work is not a speedup result.
Evidence behind this page
Named parallel report and source; supplied terrain classes remain attributed.
How it works
RecursiveTask divides the search array at its midpoint, forks the left half, computes the right and joins the two minima. A sequential cutoff of 1,000 bounds task overhead. Searches access a shared terrain cache and visitation state.
Results & recovery
- Serial and parallel programs compiled and completed a 100x100, density-0.2 smoke workload.
- Both fresh runs reported minimum -44841. Different random searches and visited counts make their 12 ms / 10 ms timings unsuitable as a speedup claim.
Technical limitations
A matching minimum in one random run is not proof of equivalence. Original benchmark tables are retained privately; shared-state races, workload variation and timing boundaries require review.
What I would improve now
Use identical seeded starting points, establish cache/visitation safety, warm up the JVM and repeat controlled measurements.