Lace Documentation

Lace is a C framework for fine-grained fork-join parallelism on multi-core computers. It uses work-stealing deques to distribute tasks across worker threads, providing scalable parallelism with low overhead.

Features

• ⚡ Low-overhead, lock-free work-stealing

• 💤 Sleeps when idle (exponential backoff) to save CPU time

• 📌 Optional thread pinning with hwloc

• 📈 Low-overhead statistics per worker

• ⛔ Interrupt support for coordinating all workers to a safe point (e.g. stop-the-world GC)

Lace uses a scalable double-ended queue for work-stealing. The owner thread pushes and pops tasks from its own deque in a wait-free manner. Thief threads steal from the other end in a lock-free manner. The design minimises cache line contention between workers.

Platform support

• 🐧 Linux (GCC, Clang)

• 🪟 Windows (MSVC, MSYS2/MinGW)

• 🍎 macOS (Apple Clang)

User Guide

• Getting Started
  • Prerequisites
  • Quick example
  • Building with CMake
• Building
  • Requirements
  • Building from source
  • Using Lace in your project
  • CMake options
  • Configuration recommendations
  • Installing
• Choosing a Variant
• Defining Tasks
  • Generated functions
  • SPAWN and SYNC
  • Calling NAME() from any context
  • Dropping a spawned task
  • Interrupting workers
• Benchmarks
  • Running benchmarks
  • Profiling with statistics
• Migrating from Lace v1
  • Key differences

API Reference

• Lifecycle
  • lace_start()
  • lace_stop()
  • lace_is_running()
  • lace_set_verbosity()
• Worker Context
  • lace_worker_count()
  • lace_is_worker()
  • lace_get_worker()
  • lace_worker_id()
  • lace_rng()
• Task Operations
  • lace_barrier()
  • lace_drop()
  • lace_is_stolen_task()
  • lace_is_completed_task()
  • lace_task_result()
  • lace_steal_random()
  • lace_check_yield()
  • lace_make_all_shared()
  • lace_get_head()
• Statistics
  • lace_count_reset()
  • lace_count_report_file()
  • lace_count_report()
• Miscellaneous
  • lace_sleep_us()

Publications

If you use Lace in your research, please cite the following publications:

• T. van Dijk and J.C. van de Pol (2014). Lace: Non-blocking Split Deque for Work-Stealing. In: Euro-Par 2014: Parallel Processing Workshops. LNCS 8806, Springer. doi:10.1007/978-3-319-14313-2_18

• T. van Dijk (2016). Sylvan: Multi-core Decision Diagrams. PhD Thesis, University of Twente. doi:10.3990/1.9789036541602

License

Lace is licensed under the Apache License, Version 2.0.