Kun-Lung Wu

AAAI Conference 2020 Conference Paper

Generalizable Resource Allocation in Stream Processing via Deep Reinforcement Learning

• Xiang Ni
• Jing Li
• Mo Yu
• Wang Zhou
• Kun-Lung Wu

This paper considers the problem of resource allocation in stream processing, where continuous data flows must be processed in real time in a large distributed system. To maximize system throughput, the resource allocation strategy that partitions the computation tasks of a stream processing graph onto computing devices must simultaneously balance workload distribution and minimize communication. Since this problem of graph partitioning is known to be NP-complete yet crucial to practical streaming systems, many heuristic-based algorithms have been developed to find reasonably good solutions. In this paper, we present a graph-aware encoderdecoder framework to learn a generalizable resource allocation strategy that can properly distribute computation tasks of stream processing graphs unobserved from training data. We, for the first time, propose to leverage graph embedding to learn the structural information of the stream processing graphs. Jointly trained with the graph-aware decoder using deep reinforcement learning, our approach can effectively find optimized solutions for unseen graphs. Our experiments show that the proposed model outperforms both METIS, a state-of-the-art graph partitioning algorithm, and an LSTMbased encoder-decoder model, in about 70% of the test cases.

AAMAS Conference 2019 Conference Paper

Online Resource Allocation with Matching Constraints

• John P. Dickerson
• Karthik Abinav Sankararaman
• Kanthi Kiran Sarpatwar
• Aravind Srinivasan
• Kun-Lung Wu
• Pan Xu

Matching markets with historical data are abundant in many applications, e. g. , matching candidates to jobs in hiring, workers to tasks in crowdsourcing markets, and jobs to servers in cloud services. In all these applications, a match consumes one or more shared and limited resources and the goal is to best utilize these to maximize a global objective. Additionally, one often has historical data and hence some statistics (usually first-order moments) of the arriving agents (e. g. , candidates, workers, and jobs) can be learnt. To model these scenarios, we propose a unifying framework, called Multi- Budgeted Online Assignment with Known Adversarial Distributions. In this model, we have a set of offline servers with different deadlines and a set of online job types. At each time, a job of type j arrives. Assigning this job to a server i yields a profit wi, j while consuming ae ∈ [0, 1]K quantities of distinct resources. The goal is to design an (online) assignment policy that maximizes the total expected profit without violating the (hard) budget constraint. We propose and theoretically analyze two linear programming (LP) based algorithms which are almost optimal among all LP-based approaches. We also propose several heuristics adapted from our algorithms and compare them to other LP-agnostic algorithms using both synthetic as well as real-time cloud scheduling and public safety datasets. Experimental results show that our proposed algorithms are effective and significantly out-perform the baselines. Moreover, we show empirically the trade-off between fairness and efficiency of our algorithms which does well even on fairness metrics without explicitly optimizing for it. ∗Part of this work is done when Pan Xu was an intern at the IBM T. J. Watson Research Center during the summer of 2016. Aravind Srinivasan’s research was supported in part by NSF Awards CNS-1010789, CCF-1422569 and CCF-1749864, and by research awards from Adobe, Inc. Karthik Sankararaman’s research was supported in part by NSF Awards CNS-1010789 and CCF-1422569. John Dickerson’s research was supported by NSF IIS RI CAREER Award #1846237. Pan Xu’s research was supported by NSF Awards CNS-1010789, CCF-1422569 and NSF IIS RI CAREER Award #1846237. The authors also like to thank Google for a generous gift support. We thank Aditya Parameswaran and Xingjie Liu for useful discussions on datasets related to our problem. Proc. of the 18th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2019), N. Agmon, M. E. Taylor, E. Elkind, M. Veloso (eds.), May 13–17, 2019, Montreal, Canada. © 2019 International Foundation for Autonomous Agents and Multiagent Systems (www. ifaamas. org). All rights reserved.

AAMAS Conference 2017 Conference Paper

Budgeted Online Assignment in Crowdsourcing Markets: Theory and Practice

• Pan Xu
• Aravind Srinivasan
• Kanthi K. Sarpatwar
• Kun-Lung Wu