Load Balancing Uneven LiDAR Tiles

TL;DR: Read each tile’s point count from its header, sort tiles largest first, submit them one per task to a process pool (no batching with chunksize), and collect with as_completed. Largest-first scheduling avoids the classic tail where one huge tile starts last and runs alone for twenty minutes while every other core sits idle.

# Context and Motivation

This guide is part of Parallel Execution in PDAL. Real LiDAR tiles are not equal. A 1 km² tile over farmland may hold 15 million points; the tile next to it, over forest with three overlapping flightlines, may hold 90 million and take eight times as long through SMRF and HAG. Parallel pools that hand out tiles in file-name order routinely end a batch with a long tail: the big tiles happen to come last, and wall time is set by the slowest one rather than by the average.

The fix is decades old — longest-processing-time-first scheduling — and costs one header read per tile. On typical LiDAR batches it cuts wall time by 20 to 40 percent without any change to the pipeline.

# Prerequisites and Assumptions

• A batch of tiles processed independently with a process pool, as in parallel tile processing with ProcessPoolExecutor.
• Run time roughly proportional to point count, which holds for most PDAL pipelines. If one stage is dominated by area instead (fine-resolution writers.gdal), use a blend of count and area.
• Python 3.10+; laspy or PDAL to read header counts quickly.

# Step-by-Step Implementation

# Step 1 — Read point counts from headers

laspy.open(path).header.point_count reads only the header — milliseconds per file even over a network mount.

# Step 2 — Sort largest first

Order tiles by descending point count. That is the entire algorithm.

# Step 3 — Submit one tile per task

Use executor.submit per tile, or map with chunksize=1. Larger chunk sizes bundle tiles into fixed groups and undo the balancing.

# Step 4 — Cap concurrent big tiles by memory

If the three largest tiles cannot run simultaneously, run them in a smaller dedicated pool first, or use a semaphore keyed on estimated memory.

# Step 5 — Collect as they complete

as_completed yields futures as they finish, so progress reporting and error handling do not wait for the slowest tile.

# Complete Working Example

"""Largest-first scheduling of PDAL tiles with a memory-aware cap on big tiles."""
from __future__ import annotations

import json
import os
from concurrent.futures import ProcessPoolExecutor, as_completed
from pathlib import Path

import laspy

WORKERS = int(os.environ.get("WORKERS", os.cpu_count() or 8))
MEM_GB = float(os.environ.get("MEM_GB", 64))
BYTES_PER_POINT_PEAK = 180        # measured peak bytes per point for this pipeline


def count(path: Path) -> int:
    with laspy.open(path) as f:
        return f.header.point_count


def process(tile: str) -> tuple[str, int]:
    os.environ["OMP_NUM_THREADS"] = "1"
    import pdal
    spec = {"pipeline": [
        tile,
        {"type": "filters.range", "limits": "Classification![7:7],Classification![18:18]"},
        {"type": "filters.smrf", "slope": 0.15, "window": 18, "threshold": 0.5},
        {"type": "filters.hag_nn", "count": 2},
        {"type": "writers.las", "filename": f"out/{Path(tile).stem}_hag.laz",
         "extra_dims": "HeightAboveGround=float", "minor_version": 4, "dataformat_id": 6},
    ]}
    return tile, pdal.Pipeline(json.dumps(spec)).execute()


def schedule(tiles: list[Path]) -> None:
    sized = sorted(((count(t), t) for t in tiles), reverse=True)
    peak_gb = [n * BYTES_PER_POINT_PEAK / 1e9 for n, _ in sized]
    big = [t for (n, t), gb in zip(sized, peak_gb) if gb > MEM_GB / WORKERS]
    small = [t for (n, t), gb in zip(sized, peak_gb) if gb <= MEM_GB / WORKERS]
    big_workers = max(1, int(MEM_GB // max(peak_gb[0], 1e-9)))
    print(f"{len(big)} big tiles on {big_workers} workers, {len(small)} on {WORKERS}")

    Path("out").mkdir(exist_ok=True)
    for group, n_workers in ((big, big_workers), (small, WORKERS)):
        if not group:
            continue
        with ProcessPoolExecutor(n_workers) as pool:
            futures = {pool.submit(process, str(t)): t for t in group}   # largest first
            for fut in as_completed(futures):
                try:
                    tile, n = fut.result()
                    print(f"done {Path(tile).name}: {n:,} points")
                except Exception as exc:                                 # noqa: BLE001
                    print(f"FAILED {futures[fut].name}: {exc}")


if __name__ == "__main__":
    schedule(sorted(Path("tiles").glob("*.laz")))

Big tiles run first on as many workers as memory allows; the small ones then fill every core. Within each group, submission order is largest first, and the pool hands the next tile to whichever worker frees up.

# Key Parameter Table

# Verification

• Worker idle time. Log start and end times per tile and plot a Gantt chart like the one above. The last quarter of the batch should still show all workers busy.
• Wall time against the lower bound. The best possible wall time is max(total work ÷ workers, longest single tile). Largest-first typically lands within 10–15 percent of it.
• No OOM kills. The kernel log (dmesg) should be clean; if not, lower the big-tile worker count.

# Gotchas and Edge Cases

Point count is only a proxy. Pipelines dominated by raster writing at fine resolution scale with area rather than points. Measure a few tiles and fit time ≈ a × points + b × area if needed.

Network storage skews early timings. The first tiles read from cold object storage may be slower than later ones. Balancing by count still helps; just do not calibrate from the first few timings.

Very large tiles may need a different plan. A tile that alone exceeds a worker’s memory will never succeed in the pool. Split it with filters.splitter or chipper or run it in streaming mode instead.

# Frequently Asked Questions

Why process the largest tiles first?

Because a large tile started late becomes a tail that runs alone after every other worker has finished. Starting the largest tiles first lets the many small tiles fill the remaining gaps, so all workers finish at about the same time.

Does Pool.map balance work automatically?

Only if each task is one tile. With a larger chunksize, tiles are bundled into fixed groups in submission order, and a group containing a large tile becomes the tail. Use a chunksize of one or submit tiles individually.

How do I get point counts without reading the points?

Read the LAS header, which stores the count. laspy’s open function or pdal info with the summary flag return it in milliseconds per file.

What if the biggest tiles do not fit in memory together?

Run them first in a smaller pool sized so their combined peak memory fits, then process the remaining tiles with every worker.

# Related

• Parallel Execution in PDAL — the parallelism model
• Threads vs Processes for PDAL Workloads — choosing the pool type
• Parallel Tile Processing with ProcessPoolExecutor — the base pattern extended here
• Estimating PDAL Memory from Point Layout — the bytes-per-point figure
• Tracking Tile Progress and Failures in Dask — the same ideas across many machines