Search

In vehicular edge computing (VEC), tasks and data collected by sensors on the vehicles can be offloaded to roadside units (RSUs) equipped with a set of servers through the wireless transmission. These tasks may be dependent of each other and can be modeled as a directed acyclic graph (DAG). The DAG scheduling problem is aimed at scheduling the tasks to the servers to minimize the scheduling length (makespan), i.e., the maximum finish time of all tasks. The conventional heuristic algorithms only utilize partial information of the DAG, so the performance of these algorithms is not stable. The state-of-the-art scheduling method employs the graph neural network to further reduce the makespan. However, this method ignores the fact that there are communication delays between tasks scheduled on different servers. In this paper, we tackle the DAG scheduling problem considering communication delays which makes the problem much more challenging. Our method is based on graph convolutional neural network and reinforcement learning. Experimental results show that our scheduling method reduces the DAG scheduling length by 8% to 15% compared with the representative scheduling strategies based on graph neural network models (GAT, GraphSAGE) and 15% to 25% compared with the conventional algorithms (HEFT, LC, and CPOP) and the sequence-to-sequence model. [ABSTRACT FROM AUTHOR]

Recently, there have been many disk-based systems proposed for iterative graph processing. In the popular vertex/edge-centric systems, an iterative directed graph algorithm needs to reprocess many partitions so as to update their vertices’ states according to other non-convergent vertices for the unawareness of their dependencies. As a result, it induces high data access cost and a long time to converge. To tackle this problem, we propose a novel system for iterative directed graph processing with taking advantage of the strongly connected component (SCC) structure. It stores a directed graph into a directed acyclic graph (DAG) sketch, with each node representing a SCC in the original data graph. During execution, the SCCs are loaded into memory for processing in a parallel way according to the topological order of the DAG sketch, and the vertices in each SCC are tried to be handled along the directed paths. In this way, each SCC is able to reach convergence in order and needs to be loaded into the main memory for exactly once, getting much lower data access cost and faster convergence. Besides, the vertices of each SCC need fewer updates for convergence. We further develop a lightweight approach to maintain the DAG sketch and handle SCCs in an incremental way for evolving graphs. Compared with the state-of-the-art methods, experimental results show that our approach achieves a performance improvements of 1.46-8.37 times for static graphs, and can reduce the execution time by 61.4-72.7 percent for evolving graphs. [ABSTRACT FROM AUTHOR]