Chen Wu
ABSTRACT
Optimizing data-intensive workflow execution is essential to many modern scientific projects such as the Square Kilometre Array (SKA), which will be the largest radio telescope in the world, collecting terabytes of data per second for the next few decades. At the core of the SKA Science Data Processor is the graph execution engine, scheduling tens of thousands of algorithmic components to ingest and transform millions of parallel data chunks in order to solve a series of large-scale inverse problems within the power budget. To tackle this challenge, we have developed the Data Activated Liu Graph Engine (DALiuGE) to manage data processing pipelines for several SKA pathfinder projects. In this paper, we discuss the DALiuGE graph scheduling subsystem. By extending previous studies on graph scheduling and partitioning, we lay the foundation on which we can develop polynomial time optimization methods that minimize both workflow execution time and resource footprint while satisfying resource constraints imposed by individual algorithms. We show preliminary results obtained from three radio astronomy data pipelines.
- M. Bateni, S. Behnezhad, M. Derakhshan, M. Hajiaghayi, R. Kiveris, S. Lattanzi, and V. Mirrokni. Affinity clustering: Hierarchical clustering at scale. In Advances in Neural Information Processing Systems, pages 6867--6877, 2017.Google Scholar
- S. H. Bokhari. A shortest tree algorithm for optimal assignments across space and time in a distributed processor system. IEEE transactions on Software Engineering, (6):583--589, 1981. Google ScholarDigital Library
- R. Braun, T. Bourke, J. Green, E. Keane, and J. Wagg. Advancing astrophysics with the square kilometre array. Advancing Astrophysics with the Square Kilometre Array (AASKA14), 1:174, 2015.Google Scholar
- K. Cameron. Antichain sequences. Order, 2(3):249--255, 1985.Google Scholar
- V. Chaudhary and J. K. Aggarwal. A generalized scheme for mapping parallel algorithms. IEEE Transactions on Parallel and Distributed Systems, 4(3):328--346, 1993. Google ScholarDigital Library
- J. Cong. Computing maximum weighted k-families and k-cofamilies in partially ordered sets. Computer Science Department, University of California, 1993.Google Scholar
- J. B. Dennis and D. P. Misunas. A preliminary architecture for a basic data-flow processor. In ACM SIGARCH Computer Architecture News, volume 3, pages 126--132. ACM, 1975. Google ScholarDigital Library
- R. P. Dilworth. A decomposition theorem for partially ordered sets. Annals of Mathematics, pages 161--166, 1950.Google ScholarCross Ref
- D. R. Fulkerson. Note on dilworthÂĂŹs decomposition theorem for partially ordered sets. In Proc. Amer. Math. Soc, volume 7, pages 701--702, 1956.Google Scholar
- A. V. Goldberg and R. E. Tarjan. A new approach to the maximum-flow problem. Journal of the ACM (JACM), 35(4):921--940, 1988. Google ScholarDigital Library
- G. Karypis and V. Kumar. Multilevelk-way partitioning scheme for irregular graphs. Journal of Parallel and Distributed computing, 48(1):96--129, 1998. Google ScholarDigital Library
- Y.-K. Kwok and I. Ahmad. Static scheduling algorithms for allocating directed task graphs to multiprocessors. ACM Computing Surveys (CSUR), 31(4):406--471, 1999. Google ScholarDigital Library
- J.-C. Liou and M. A. Palis. A comparison of general approaches to multiprocessor scheduling. In Parallel Processing Symposium, 1997. Proceedings., 11th International, pages 152--156. IEEE, 1997. Google ScholarDigital Library
- D. Marcus. Graph theory: a problem oriented approach. The Mathematical Association of America, 2008.Google Scholar
- C. Martella, D. Logothetis, A. Loukas, and G. Siganos. Spinner: Scalable graph partitioning in the cloud. In Data Engineering (ICDE), 2017 IEEE 33rd International Conference on, pages 1083--1094. Ieee, 2017.Google ScholarCross Ref
- V. Sarkar. Partitioning and scheduling parallel programs for execution on multiprocessors. PhD thesis, 1987. Google ScholarDigital Library
- H. S. Stone. Multiprocessor scheduling with the aid of network flow algorithms. IEEE transactions on Software Engineering, (1):85--93, 1977. Google ScholarDigital Library
- H. Topcuoglu, S. Hariri, and M.-y. Wu. Performance-effective and low-complexity task scheduling for heterogeneous computing. Parallel and Distributed Systems, IEEE Transactions on, 13(3):260--274, 2002. Google ScholarDigital Library
- D. Towsley. Allocating programs containing branches and loops within a multiple processor system. IEEE Transactions on Software Engineering, (10):1018--1024, 1986. Google ScholarDigital Library
- C. Tsourakakis, C. Gkantsidis, B. Radunovic, and M. Vojnovic. Fennel: Streaming graph partitioning for massive scale graphs. In Proceedings of the 7th ACM international conference on Web search and data mining, pages 333--342. ACM, 2014. Google ScholarDigital Library
- C. Wu, R. Tobar, K. Vinsen, A. Wicenec, D. Pallot, B. Lao, R. Wang, T. An, M. Boulton, I. Cooper, et al. Daliuge: A graph execution framework for harnessing the astronomical data deluge. Astronomy and Computing, 20:1--15, 2017.Google ScholarCross Ref
Recommendations
Partitioning of a graph into induced subgraphs not containing prescribed cliques
AbstractLet K p be a complete graph of order p ≥ 2. A K p-free k-coloring of a graph H is a partition of V ( H ) into V 1 , V 2 … , V k such that H [ V i ] does not contain K p for each i ≤ k. In 1977 Borodin and Kostochka conjectured that any graph H ...
Partitioning a Graph into Complementary Subgraphs
WALCOM: Algorithms and ComputationAbstractIn the Partition Into Complementary Subgraphs (Comp-Sub) problem we are given a graph , and an edge set property , and asked whether G can be decomposed into two graphs, H and its complement , for some graph H, in such a way that the edge cut-set (...
On partitioning a graph into two connected subgraphs
Suppose a graph G is given with two vertex-disjoint sets of vertices Z"1 and Z"2. Can we partition the remaining vertices of G such that we obtain two connected vertex-disjoint subgraphs of G that contain Z"1 and Z"2, respectively? This problem is known ...
Comments