Software:Taskflow

Taskflow

Original author(s)	T-W Huang
Initial release	2018
Written in	C++
Operating system	Linux, OS X, Windows
Type	library or framework
License	MIT License
Website	github.com/taskflow/taskflow

Taskflow is a general-purpose parallel and heterogeneous task programming library written in C++. Taskflow lets users describe a computation in terms of a task dependency graph. The system manages and schedules threads to execute these tasks.

Overview

Taskflow develops a new general-purpose task programming model to streamline the creation of large parallel applications on a heterogeneous node comprising manycore central processing units (CPUs) and graphics processing units (GPUs). It leverages the power of modern C++ to enable efficient implementation of parallel decomposition strategies that are particularly useful for irregular workloads, including dynamic control flow, graph computing, and optimization.

Taskflow implements work stealing to distribute tasks among available processing cores with dynamic load balancing. The runtime adapts the number of worker threads to available task parallelism at any time during the graph execution. The scheduling algorithm effectively avoids underutilized threads that are harmful to performance and prevents oversubscribed threads when tasks are scarce, improving the overall system performance of latency, energy efficiency, and throughput.

Taskflow has extensive real use cases in machine learning (ML), electronic design automation (EDA), high-performance computing (HPC), heterogeneous computing, and data science.

Programming Model

A basic example of Taskflow is shown below. The graph contains four tasks, A, B, C, and D, and four dependencies forcing A to run before B and C, and D to run after B and C. The code explains itself through a succinct and expressive graph description model. Users do not need to touch any threads or system-specific details.

#include <taskflow/taskflow.hpp>  

int main(){
  
  tf::Executor executor;
  tf::Taskflow taskflow;

  auto [A, B, C, D] = taskflow.emplace(
    [] () { std::cout << "TaskA\n"; },               //  task dependency graph
    [] () { std::cout << "TaskB\n"; },               // 
    [] () { std::cout << "TaskC\n"; },               //          +---+          
    [] () { std::cout << "TaskD\n"; }                //    +---->| B |-----+   
  );                                                 //    |     +---+     |
                                                     //  +---+           +-v-+ 
  A.precede(B);  // A runs before B                  //  | A |           | D | 
  A.precede(C);  // A runs before C                  //  +---+           +-^-+ 
  B.precede(D);  // B runs before D                  //    |     +---+     |    
  C.precede(D);  // C runs before D                  //    +---->| C |-----+    
                                                     //          +---+          
  executor.run(taskflow).wait();

  return 0;
}

Awards

Taskflow received a few awards to recognize its contributions to scientific computing:

• Second Price of the Open Source Software Competition in 2019 ACM Multimedia Conference (MM)
• Outstanding PhD Dissertation Award in 2019 ACM/SIGDA Design Automation Conference (DAC)
• Best Tool Award (part of OpenTimer) in 2018 Workshop of Open-source EDA Technology (WOSET) at International Conference of Computer-aided Design (ICCAD)
• Best Poster Award in 2018 C++ Conference (CppCon)

Systems supported

Taskflow depends only on C++ Standard Library and works for systems that support C++14 compilers:

• GNU C++ Compiler at least v5.0
• Clang C++ Compiler at least v4.0
• Microsoft Visual Studio at least v15.7 (MSVC++ 19.14)
• AppleClang Xcode Version at least v8
• Nvidia CUDA Toolkit and Compiler (nvcc) at least v10.0

Taskflow works on Linux, Windows, and Mac OS X. See the C++ compiler support status.

See also

• Task parallelism
• Data parallelism
• Fork–join model
• Parallel programming model

References of Taskflow

• Huang, Tsung-Wei; Lin, Dian-Lun; Lin, Yibo; Lin, Chun-Xun (2020), Cpp-Taskflow v2: A General-purpose Parallel and Heterogeneous Task Programming System at Scale, CoRR arXiv, https://arxiv.org/abs/2004.10908 
• Huang, Tsung-Wei; Lin, Chun-Xun; Guo, Guannan; Wong, Martin (2019), Cpp-Taskflow: Fast Task-Based Parallel Programming Using Modern C++, IEEE International Symposium on Parallel and Distributed Systems (IPDPS), https://ieeexplore.ieee.org/abstract/document/8821011/ 

Other References

• Skillicorn, David B. (1991), Models for practical parallel computation, International Journal of Parallel Programming, https://www.ida.liu.se/~chrke55/papers/modelsurvey.pdf 
• Ian Foster, Designing and Building Parallel Programs, http://www.mcs.anl.gov/~itf/dbpp 
• Blaise Barney, Introduction to Parallel Computing, https://computing.llnl.gov/tutorials/parallel_comp/ 
• Leijen, Daan; Schulte, Wolfram; Burckhardt, Sebastian (2009). "The Design of a Task Parallel Library". ACM SIGPLAN Notices 44 (10): 227. doi:10.1145/1639949.1640106. 

External links

• on GitHub