Supplementary Materials for Nimble: Lightweight and Parallel GPU T ask Scheduling for Deep Learning Appendix A Proofs on the Stream Assignment Algorithm of Nimble

In this section, we provide detailed proofs on the theorems presented in Section 4.2. We assume that the computation graph of a neural network is given. Here we define important concepts and terminologies used in the following proofs. F or any (u,v) E, f ( u) = f (v) or there exists a path P E from u to v such that P Λ null= . Prior to the proof of Theorem 1-2, we describe and prove Lemma 1 and Lemma 2. Lemma 1. We will prove by contradiction.