Source-linked AI summary
Scheduling Computation Graphs of Deep Learning Models on Manycore CPUs
Linpeng Tang, Yida Wang, Theodore L. Willke, Kai Li
TL;DR
Prior work emphasized individual operations rather than scheduling deep-learning computation graphs as a whole, while naive parallel execution can contend for resources on manycore CPUs. Graphi profiles graphs, limits interference, and prioritizes critical-path operations; on four neural networks, it outperformed TensorFlow on a 68-core Intel Xeon Phi.
Problem
Graph-wide scheduling on manycore CPUs has received little attention, and sequential or naive parallel execution can leave resources underused or create contention.
Source: §1 · p. 1Method
Graphi profiles a computation graph to set parallel resources, minimizes interference, and uses critical-path-first scheduling.
Source: §9 · p. 15Results
2.1x to 9.5x faster than TensorFlow, Graphi outperformed TensorFlow on four neural networks using an Intel Xeon Phi processor 7250.
Source: §9 · p. 15Takeaways & Limitations
Graphi demonstrates a high-performance parallel execution engine for deep-learning computation graphs on manycore CPUs.
Source: §9 · p. 15OpenMP could not guarantee thread reuse when team size changed dynamically, and context switches on the manycore CPU cost about 10–30 ms.
Source: §6 · p. 10
Abstract
from arXiv · showhide
For a deep learning model, efficient execution of its computation graph is key to achieving high performance. Previous work has focused on improving the performance for individual nodes of the computation graph, while ignoring the parallelization of the graph as a whole. However, we observe that running multiple operations simultaneously without interference is critical to efficiently perform parallelizable small operations. The attempt of executing the computation graph in parallel in deep learning frameworks usually involves much resource contention among concurrent operations, leading to inferior performance on manycore CPUs. To address these issues, in this paper, we propose Graphi, a generic and high-performance execution engine to efficiently execute a computation graph in parallel on manycore CPUs. Specifically, Graphi minimizes the interference on both software/hardware resources, discovers the best parallel setting with a profiler, and further optimizes graph execution with the critical-path first scheduling. Our experiments show that the parallel execution consistently outperforms the sequential one. The training times on four different neural networks with Graphi are 2.1x to 9.5x faster than those with TensorFlow on a 68-core Intel Xeon Phi processor.
1 Introduction
Deep-learning computation graphs have parallelizable operations, but prior work largely optimized individual operations, and naive concurrent execution can contend for resources on manycore CPUs. Graphi profiles and schedules graph execution to limit interference, and the paper reports faster training than TensorFlow on four networks.
1 Introduction
- Prior work emphasized single-operation primitives or distributed execution, while graph-wide scheduling on manycore processors received little attention; naive concurrent executors can contend for computing and memory resources.Deep-learning models are represented as computation graphs whose nodes are operations and whose edges encode dependencies.Source: §1 · p. 1
- Graphi profiles each computation graph to allocate resources among scheduler and executors, then intelligently schedules operations to minimize interference.The paper presents Graphi as the first high-performance parallel execution engine with intelligent scheduling for deep-learning graphs on manycore CPUs.Source: §1 · p. 2
- On the Intel Xeon Phi processor, Graphi outperforms TensorFlow by 2.1x to 9.5x on four popular deep-learning networks when using a proper parallelism scheme and optimized scheduling.Source: §1 · p. 2
- Parallel execution outperformed sequential execution by up to 3.4x, while typical deep-learning operations saturated at 8 or 16 cores on the Intel Xeon Phi.The paper argues that parallelizing multiple operations without unnecessary thread interference is preferable.Source: §1 · p. 2
- A centralized scheduler that imposes intelligent scheduling and eliminates software resource contention further boosted the execution engine’s performance by up to 19%.This is presented as an additional contribution beyond choosing a parallelism scheme and optimizing scheduling.Source: §1 · p. 2
2 Background
The background defines computation graphs and contrasts sequential execution with the use of multiple executors. It also describes the manycore CPU platform used in the study.
2 Background
- A computation graph is a directed acyclic graph whose operation nodes are connected by edges representing dependencies between operations.An edge from A to B means B depends on A’s output as part or all of its input.Source: §2 · p. 2
- Training executes forward and backward operations for a batch, whereas inference uses a smaller graph containing only forward operations.A complete graph execution corresponds to one training iteration or, for inference, typically a group of instances.Source: §2 · p. 2
- Sequential execution uses one executor to run operations in topological order, exploiting parallelism within each operation; it suits large operations and simple graphs.An operation can run only after its dependencies have completed.Source: §2 · p. 3
- Multiple executors can run operations in parallel when dependencies permit, a less-explored approach that may improve execution of complex networks.An executor leads a team of threads to run an operation, and the execution engine can configure or adjust the team size.Source: §2 · pp. 2–3
- Experiments on the manycore CPU used one thread per core to eliminate interference among hardware threads; in quadrant mode, it had 16 GB MCDRAM (>400 GB/s) and 96 GB DDR4 memory.Source: §2 · p. 3
3 Motivations
Small graph operations can leave manycore resources underused, while parallel execution introduces scheduling and resource-contention challenges. Microbenchmarks show that operations saturate before using all cores and that concurrent execution benefits from avoiding interference.
3.1 Challenges
- Executing small operations in parallel can improve utilization because thread-management overhead keeps conventional sequential execution from fully using manycore resources.This challenge is especially relevant to networks with small operations and complex links, such as LSTM and PathNet.Source: §3.1 · p. 4
- Scheduling a DAG’s operations across executors to minimize makespan is NP-hard, while a centralized ready-operation queue may perform poorly on manycore CPUs.The makespan is the time from execution start until every operation finishes.Source: §3.1 · p. 4
- Oversubscribed thread pools, unpinned threads, and global-queue polling can cause software and hardware contention that degrades parallel execution.With many executors and short operations, global queue polling overhead can become significant.Source: §3.1 · p. 4
3.2 Microbenchmark Performance
- GEMM saturates above 8 threads and element-wise multiplication above 16, so assigning all cores to one operation is not optimal.The benchmark uses LSTM operations and finds that parallel computing power is largely wasted beyond those saturation points.Source: §3.2 · p. 5
- Up to 45% higher overall FLOPS is achieved with pinned threads than with OS-managed threads in the multiple-operation benchmark.The authors attribute the difference to OS thread placement that can put multiple threads on one physical core, causing synchronization overheads and cache misses.Source: §3.2 · p. 5
- More than 6x higher overall performance comes from running multiple small operations together without interference rather than one operation using all available resources.This comparison draws on the peak FLOPS in Figures 2 and 3.Source: Figure 2 · p. 4, §3.2 · p. 5, Figure 3 · p. 5
4 Graphi Design
Graphi is a generic engine for parallel execution of deep-learning computation graphs on manycore CPUs. It profiles the graph, selects an executor configuration, and uses centralized critical-path-first scheduling and executor-specific resources to reduce interference.
4 Graphi Design
- Graphi is designed to execute different neural-network computation graphs while minimizing makespan and interference among its scheduler and multi-threaded executors.It treats the graph as a DAG and assumes the graph remains static during computation.Source: §4 · p. 6, §4.1 · p. 6
4.1 Overview
- Graphi profiles a graph during initial runs and uses execution statistics to improve scheduling for subsequent runs.The engine and profiler work in a feedback loop, with the profiler collecting information from graph execution.Source: §4.1 · p. 6
4.2 Profiler
- The profiler compares symmetric combinations of executor count and threads per executor, selecting the configuration with minimal execution makespan.It also estimates each operation’s runtime for use in later scheduling.Source: §4.2 · p. 6
4.3 Scheduler
- Graphi’s centralized scheduler assigns ready operations to executor-specific buffers and prioritizes operations with the highest estimated remaining path time.This critical-path-first policy prioritizes operations with the longest accumulated time to the graph’s sink; disjoint buffers eliminate contention among executors polling a shared queue.Source: §4.3 · p. 7
4.4 Executors
- Executors poll their own operation buffers, execute assigned operations, and report newly triggered operations to the scheduler.Assigning each executor exclusive tiles keeps executors from sharing compute units or L2 cache, largely avoiding the discussed hardware contention.Source: §4.4 · pp. 7–8
5 Implementation
Graphi uses the CGT compilation component but adds a profiler and replaces the execution engine. Its implementation combines critical-path scheduling, operation buffers, and pinned OpenMP thread teams.
5 Implementation
- Graphi uses CGT to compile models into computation graphs, while adding a profiler and completely redesigning and reimplementing the execution engine.The authors state that the implementation can also be migrated to other deep-learning frameworks.Source: §5 · p. 8
5.1 Overview of CGT
- CGT’s compiler translates model expressions into a processor-targeted computation graph, and variables may share memory locations when their lifespans do not overlap.Compute-intensive C++ operations are compiled into callable shared-library routines.Source: §5.1 · p. 8
5.2 Profiler and execution engine
- The scheduler uses profiled operation durations to prioritize ready operations by level, while executors use per-executor lock-free buffers and pinned OpenMP thread teams.Graphi buffers at most one operation because larger buffers caused load imbalance that offset their benefit; thread teams are chosen to avoid sharing tiles.Source: §5.2 · pp. 8–9
- A lightweight single-threaded executor on a reserved core handles small operations needed to bootstrap graph execution, leaving the client thread available for scheduling.Graphi also follows CGT and TensorFlow in directly running small operations in the current thread or executor rather than placing them in the ready-operation queue.Source: §5.2 · p. 9
6 Optimization Considerations
Graphi’s optimization experiments found that some plausible scheduling and locality refinements did not improve whole-graph execution or were constrained by implementation and hardware behavior.
Different executor thread team sizes
- Varying executor team sizes reduced total CPU time but did not improve graph makespan, as large operations could straggle on small teams.Graphi therefore uses symmetric executors; whether varying team sizes helps other models requires further investigation.Source: §6 · pp. 9–10
Dynamic number of executors
- Dynamic executor counts were ineffective: changing OpenMP team sizes could prevent thread reuse, while doubling parallelism after saturation reduced runtime only slightly.The reported context-switch overhead on the manycore CPU was about 10–30 ms.Source: §6 · p. 10
Data cache locality
- Cache-affinity scheduling modestly improved element-wise operations but not matrix multiplications; experiments confined to one tile showed modest, consistent improvement.The authors hypothesize that Intel MKL’s blocking scheme still sends data across L2 caches unless a team fits within one tile, a restrictive setting they did not pursue.Source: §6 · p. 10
- Writing element-wise results with stream stores slightly improved overall performance because overwritten data were unlikely to be reused by the same executor.Graphi adopted this technique in its design.Source: §6 · p. 10
7 Evaluation
Graphi’s evaluation compares training performance with TensorFlow and examines how executor parallelism and scheduling affect execution. Across four networks, Graphi outperforms TensorFlow, while the best executor count depends on model structure.
7.1 Experiment Setup
- The evaluation trained LSTM, PhasedLSTM, PathNet, and GoogleNet models, comparing Graphi with TensorFlow 1.2.0 on an Intel Xeon Phi 7250.Graphi compiled operations with ICC and used MKL for matrix multiplication and LIBXSMM for convolution; TensorFlow used MKL for matrix multiplication and convolution.Source: §7 · p. 10, §7.1 · p. 11
7.2 Overall Results
- 2.1–9.5× speedups over TensorFlow were achieved by Graphi across four networks on the manycore CPU.The comparison uses the best parallelization settings for both systems.Source: §7.2 · p. 11, Figure 5 · p. 12
- Graphi performed best relative to TensorFlow on medium-sized networks, which the authors associate with Eigen’s centralized queue contention and the way operation sizes affect queue overhead.For PathNet, Graphi’s speedups were about 4×, 7×, and 9.5× on small, medium, and large models; GoogleNet was about 3–4× faster at all three sizes.Source: §7.2 · p. 12
7.3 Varying number of executors
- Graphi’s parallel execution improved batch-training performance over sequential execution on all four networks, with peak gains of 2.3–3.1× for LSTM/PhasedLSTM, 1.2–2.1× for PathNet, and about 1.2× for GoogleNet.Small networks generally benefited more; GoogleNet performance declined rapidly beyond two executors.Source: §7.3 · pp. 12–13, Figure 6 · p. 13
- Profiling shows optimal executor count depends on model structure: four-layer LSTM/PhasedLSTM models have around 8–12 parallelizable operations; PathNet/GoogleNet have 6/2–3 parallel modules per layer, matching their optimal executor counts.Source: §7.3 · p. 13
7.4 Graphi scheduler
- Graphi’s scheduler achieved 8%–19% speedups over naive scheduling after executor thread interference was eliminated.The reported scheduler gains include reduced centralized-queue contention and critical-path-first scheduling based on operation profiling.Source: §7.4 · p. 14
- The scheduler’s gains were larger for LSTM and PhasedLSTM than GoogleNet; the authors attribute this partly to more small operations increasing queue contention and to greater critical-path-scheduling gains on more complex graphs.The critical-path scheduler recovered the diagonal parallel execution pattern of cuDNN’s hand-optimized LSTM implementation, unlike the baseline scheduler.Source: §7.4 · p. 14
8 Related Works
Related work has optimized individual deep-learning operations and parallel execution in specialized settings, while this paper focuses on scheduling entire computation graphs on manycore CPUs. Graphi combines graph-level scheduling with resource-contention mitigation and aims to apply across network variants.
8 Related Works
- Existing frameworks commonly execute graph operations sequentially; some offer parallel CPU execution, but simple scheduling and thread interference can yield suboptimal performance on manycore CPUs.Sequential execution can suit large operations and simple graph structures.Source: §8 · p. 14
- Graphi draws on prior work in online scheduling and critical-path-first scheduling, and applies resource-disjointness principles to reduce contention among its own threads.Earlier contention work discussed mapping separate applications to different cores or partitioning memory among applications.Source: §8 · p. 14
- Prior accelerator work focused on optimizing primitives such as convolution and matrix multiplication, whereas Graphi targets inter-operation optimization of the entire computation graph on manycore CPUs.The cited accelerator work includes GPU, FPGA, and first-generation Xeon Phi coprocessor efforts.Source: §8 · pp. 14–15
- Graphi is presented as a generic execution engine for LSTM variants, unlike network-specific optimizations such as fusion, pruning, or parallel execution for particular networks.The paper says Graphi’s techniques combine established ideas adapted to a complex deep-learning system.Source: §8 · p. 15
9 Conclusions
Graphi profiles computation graphs to select parallel settings, limit interference, and schedule operations by critical path. On four networks it outperformed TensorFlow on Xeon Phi, while the authors describe the work as a first step and identify broader settings for future work.
9 Conclusions
- Graphi profiles the graph to choose parallel settings, minimizes interference among parallel operations, and uses critical-path-first scheduling.The authors report that this scheduling automatically recovers a handcrafted LSTM parallelization scheme used in cuDNN.Source: §9 · p. 15
- Across four neural networks, Graphi outperformed TensorFlow optimized for CPU via MKL by 2.1× to 9.5× on Intel Xeon Phi 7250.The paper also reports 1.2× to 3.1× performance gains from proper parallelism without interference and 8% to 19% speedups from better scheduling.Source: §9 · p. 15
- The authors characterize this work as a first step toward efficient parallel engines for deep-learning computation graphs on manycore CPUs.Future directions include GPUs, FPGAs, distributed systems, dynamic computation graphs, and NUMA optimization.Source: §9 · p. 15