Spartan: A Distributed Array Framework with Smart Tiling

Abstract

📜 Abstract

Application programmers in domains like machine learning, scientific computing, and computational biology are accustomed to using powerful, high productivity array languages such as MatLab, R and NumPy. Distributed array frameworks aim to scale array programs across machines. However, maximizing the locality of access to distributed arrays is an unsolved problem; such locality is critical for high performance. This paper presents Spartan, a distributed array framework that automatically determines how to best partition (aka “tile”) n-dimensional arrays and to co-locate data with computation to maximize locality. Spartan combines a lazy-evaluation based, optimizing frontend with a distributed tiled array backend. Central to Spartan’s design is a small number of carefully chosen parallel high-level operators, which form the expression graph captured by Spartan’s frontend during runtime. These operators simplify the programming of distributed applications. More importantly, their well-defined semantics allow Spartan’s runtime to calculate the costs of different tiling strategies and pick the best one for evaluating the entire expression graph. Using Spartan, we have implemented 12 applications from a variety of domains including machine learning and scientific computing. Our evaluations show that Spartan’s automatic tiling mechanism leads to good and scalable performance while eliminating the need for manual tiling.

Description

✨ Summary

Spartan is a distributed array framework intended to provide NumPy-like abstractions while scaling array computations across a cluster. Its central problem is tiling: deciding how multidimensional arrays should be partitioned across workers and how computation should be placed near the data to minimize network communication. The paper argues that manual partitioning can achieve good performance but imposes substantial complexity on application programmers.

The system uses a two-layer architecture. A Python frontend captures array operations lazily and represents them as an expression graph. A distributed backend then executes the optimized graph using in-memory tiled arrays and parallel worker tasks. Because arrays are immutable at the operator level, expression graphs are acyclic and can expose how an array is used across multiple operations before execution begins.

Spartan expresses array computations through five restricted high-level operators: map, filter, fold, scan, and join_update. Their constrained semantics make data-access patterns and communication costs explicit. For example, map favors identical tilings for all input arrays, reductions favor partitioning along the reduction axis, and join_update models computations such as matrix multiplication that combine tiles and aggregate updates. Views such as slicing and axis swapping allow the system to reason about logical transformations without necessarily copying data.

The tiling optimizer converts the expression graph into a weighted tiling graph. Candidate nodes represent alternative layouts, including row-wise, column-wise, block, and duplicated layouts. Edge weights estimate the communication cost associated with incompatible layouts or remote reads and updates. Since finding the globally optimal tiling is NP-complete, Spartan uses a greedy heuristic that processes highly connected operator groups first and selects the locally least-cost choice. Array duplication is supported when memory permits, which is particularly useful when the same array is repeatedly accessed along different axes, as in alternating least squares. Sparse arrays receive additional treatment through sampling, adaptive cost updates, and fine-grained tiles for work stealing.

The implementation supports more than 50 NumPy built-ins and executes user-defined NumPy functions on tiles. Workers maintain distributed in-memory arrays, while matching tiling hints cause corresponding regions of arrays to be co-located. The backend also checkpoints completed operator results to durable storage for failure recovery.

The evaluation covered 12 applications from machine learning, data mining, scientific computing, and computational finance on a local cluster and Amazon EC2. The optimizer selected the same layouts as a brute-force minimum-communication baseline for the evaluated applications, while reducing optimization time substantially: for a 14-operator alternating-least-squares computation, brute-force search took more than 500 seconds compared with 0.06 seconds for Spartan’s optimizer. The system also demonstrated scalable behavior for many workloads and achieved a reported 1.7× speedup over Presto on a k-means benchmark using one billion points. However, the optimizer considers network communication rather than cache locality or all other hardware effects; its greedy search is not optimal in general; join_update may require user hints; and workloads such as large-scale alternating least squares can remain communication-bound even with duplication.

The search found evidence that Spartan’s tiling formulation continued to influence research on distributed matrix partitioning. Distributed Matrix Tiling Using a Hypergraph Labeling Formulation explicitly identifies Spartan as a closely related runtime tiling model and develops a hypergraph-based formulation, additional hardness results, and a greedy algorithm for distributed matrix tiling. (researchgate.net) The original project was also maintained as an open-source implementation whose documentation describes lazy NumPy-like array expressions, compilation, optimization, and execution on a distributed backend. (github.com) The available evidence indicates primarily research and prototype-software influence; the search did not identify a clearly documented industrial product adoption of Spartan itself. The publication metadata and authorship were cross-checked against the USENIX record. (usenix.org)