Week 7.a
CS7670
10/17 2022
https://naizhengtan.github.io/22fall/

1. backgrounds: RL and Spark
2. learned scheduling
3. Decima
---

1. backgrounds: RL and Spark

  -- reinforcement learning

     +--------[states]---------+
     |                         |
     v                         |
  +-------+                 +-----+
  | agent | --[actions]---> | env |
  +-------+                 +-----+
     ^                         |
     |                         |
     +--------[rewards]--------+

  policy: \pi(a,s)=Pr(a_t=a | s_t =s)
  value function: V_\pi(s)

  -- basic of GNN

   A GNN is an optimizable transformation on all attributes of the graph
   (nodes, edges, global-context) that preserves graph symmetries
   (permutation invariances).

   Graph:
     -- components: nodes, edges, global
     -- parameters on all or some components
     -- train?
     -- inference?

   [for those who are interested, read:
        https://distill.pub/2021/gnn-intro/ ]


2. learned scheduling

  -- scheduling distributed data processing systems

   assuming five nodes
   [fig 16 in Appdx A]

   Q: what will happen, if we have 6 nodes?

   Q: what will happen, if we have inf nodes?

   Q: what will happen, if we have 1 node?

  -- problem abstraction

    job == DAG
      -- nodes are execution stages
      -- a stage is an operation that runs on many shards
      -- a task is an operation runs on one shard
      -- edges are data flow

    Q: how many parameters do you think?

    for one job,
    (1) #executors (parameters)
    (2) next task to run

    [Q: what's the difference between (ii) and (iii) in the 2nd last
        paragraph of S3?]

  -- general scheduling:
     states -> NN -> actions (scheduling)

     Q: what are the states?
     Q: what are the actions?

     interesting questions:
     Q: how to prevent NN predicts invalid actions?
     Q: how to prevent starving a job (or, more broadly, unfair scheduling)?


3. Decima

  [skipped]
  DISCUSSION: for scheduling, RL vs. Supervised learning
    "RL is well-suited to learning scheduling policies."

  Q: what're the true scientific contribution of this paper?

  -- idea: GNN + policy network

  [skipped]
  * Q: Fig3 is interesting:
       is the area of the same job among (a)--(d) the same? Why?

  * problem statement

    (a) job-level problem:
      given a job DAG,
         nodes are "stages" (a stage has multiple tasks);
         edges are data flow

      decide #executors first,
      and while scheduling, decide which task to run next.

    (b) system-level problem:
      given a _scheduling event_ (job completed or job arrival),
        based on the current _state_,
        what _action_ to execute?

  * Q: what are the true challenges?

    true challenges:
     -- encoding states (A)
     -- what are the actions? (B)
     -- train model (C)

  * Decima solution

(A) encoding states

  -- graph embedding
    -- inputs: job DAGs; nodes with attributes
    -- three types of embeddings:
      (1) per-node embeddings
      (2) per-job embeddings
      (3) global embedings

  -- per-node embedding:
    (G_i, x_v^i) -> e_v^i

    -- e_v^i is a tensor of size 16

  * Q: What is x_v^i?

    [S6.1, page 7:
      (1) #remaining tasks
      (2) avg task duration
      (3) #executors
      (4) #available executors
      (5) if executors are local to the job]

  -- per-job embedding (for job i)
     {\forall v \in G_i, (x_v^i, e_v^i)} -> y^i

  -- global embedding
     {all y^i} -> z

(B) actions

   -- actions
     (1) a stage to schedule next
     (2) #executors to use

   -- policy network
     -- input: three types of embeddings
     -- ouput: <v, l_i> 
           stage v; parallelism limit l_i

      -- for v:
         q_v^i = q(e_v^i, y^i, z)
      -- for l_i:
         w_l^i = w(y^i, z, l)

(C) training


  -- [systems paper writing]
     The intro structure:
      -- motivation
      -- idea or insight or observation
      -- challenges & solutions
      -- the system and results
      -- contributions