Graph partitioning and scheduling for distributed dataflow computation

Abstract

During the last years, the amount of data which can be represented and processed as graph structured data has massively increased. To process these large data sets, graph processing systems have been developed which distribute and partition a graph among multiple machines. Due to an increase in processing power and data collection, machine learning and especially neural networks have become very popular. Consequently, machine learning systems like TensorFlow have emerged. Machine learning models can be represented as dataflow graphs and often take days to train as the dataflow graph is executed thousands of times. Graph partitioning determines how the graph is divided and which node is placed on which device. Scheduling decides which node should be computed next during execution. Smart partitioning and scheduling can drastically reduce the total execution time. Most existing solutions do not consider several important constraints like memory limitations, device or colocation constraints which can be directly derived from the machine learning library TensorFlow. This thesis presents and evaluates different partitioning and scheduling strategies meeting the constraints required for a realistic environment. One of these developed partitioning algorithms is based on a heuristic function considering execution time, memory and traffic and tries to map time-critical nodes on fast devices. This partitioning algorithm performed very well in combination with a scheduling strategy which schedules the executable node first whose upwards path takes longest to compute. On the evaluated graphs extracted from TensorFlow, this strategy was up to 75 % and at least 45% better in terms of graph execution time than the slightly adapted popular HEFT algorithm which is a common benchmark. In combination with the aforementioned scheduling strategy a partitioning which aims to assign the critical path nodes to the fastest device showed equally promising results.