Week 1
CS7670
09/07 2022
https://naizhengtan.github.io/22fall/

0. in-class polices
1. Goals
2. What is NN4Sys?
3. Mechanics and admin
   (how are we going to run CS7670?)

------

0. in-class policies

  -- no laptop
  -- chocolate & willpower
  -- lottery for questions

  [a round of introduction]

1. Goals

  - Q: who read the paper "How to read a paper"?
     our homepage is
       https://naizhengtan.github.io/22fall

  - Goal 1: learn how to read papers
     know how to read papers and...practice!
       will read >15 papers
       will read some classic ones (= really old papers)
       will read some recent ones

     introduce "How to read a Paper"
     [ask if anyone can briefly introduce the paper]

     three passes:
       1. read abs, intro, and conclusion
          (now you know the problem statement,
           work's significance, and its high level idea)

       2. read the main contents
          (now you understand most of the paper; you should be able to teach
          someone who hasn't read the paper and should be able to answer
          clarification questions.)

       3. "virtually re-implement the paper"
          (you have internalized the paper.
           answer questions like "what if...")


  - Goal 2: study NN4Sys
    NN4Sys: neural networks for systems


2. What is NN4Sys?

   - my definition:
     using neural networks (NN) to replace some components in computer systems.

   - Q: what is a NN?
     (for now) a black-box function, f
     two steps to use f:

       (1) construct f (training):
           f is mutable in this step.
           given many (x,y) pairs for f, such that f learns f(x)->y

       (2) use f (inference/serving):
           f is immutable in this step.
           f(x_unseen) -> y_prediction

   - Q: what does a NN4Sys system look like?

     Imagine a fully NN-base OS kernel:

                       +-------------+
     app <-[syscall]-> | kernel (NN) |
                       +-------------+
     app:
        write(1, "hello world")

        fd = open("/tmp/abc", O_RDONLY)
        read(fd, &mem, size)

     kernel: ??

     (of course, we're far from this.)

   - real examples:
     [ask if anyone knows any NN4Sys?]

     -- NN-based scheduler
     -- learned database index
     -- learned congestion control in networking
     -- learned concurrency control in database
     -- many more
        see also the [Park project](https://github.com/park-project/park)

   - why NN4Sys is interesting?

     mainly for two reasons:

     a) NN can discover heuristics that are specific for the current context
        think of scheduling problem & algorithm:

        abstract preemptive scheduling problem:
          jobs arrive in some order
          each job has its own running time
          a machine will work on one job at a time
          machine can preempt jobs

        algorithm: multi-level feedback queue (MLFQ)

         [briefly intro to MLFQ; draw this]

         --Rule1: multiple queues, each with different priority

         --Rule2: round-robin within each queue

         --feedback: change job priorities
           --Rule3: "downgrade" a job after 5 unit of time running
           --Rule4: "promote" all jobs after every 100 units of time

        Q: Why we want these rules?
          Rule1: favor small/recent jobs
          Rule2: fairness
          Rule3: favor small/recent jobs
          Rule4: prevent starvation

        Notice that all of these are heuristics that may or may not apply to
        us; we may have:
          all jobs have the same running time
          having two types of jobs: 5.1 units of time and 5.0 unit of time (is RR fair?)

        NNs may learn specialized (and likely better) heuristics for the workloads.

     b) NN is a succinct (approximation) data structure
       -- can approximate arbitrary functions

       one example: bloom filter

       Bloom filter is a probabilistic data structure.
       A Bloom filter compresses a given set S into an array of bits.
       A Bloom filter allows false positives, but not false negatives.

       Learned bloom filter:

                 +-----------------+
         key --> | predict if in S |  --[Yes]--> "key is in S"
                 +-----------------+               ^
                         |                         |
                         +----[No]---> [bloom filter] --> "key is not in S"

       Bloom filter really is a lossy compression of knowledge.

       -- small memory footprints (compared with many traditional data structures)
          -- better cache locality?
       -- overfit the given data
          -- pro: good for reads
          -- con: bad for writes

   - Where are we in NN4Sys?
     - branch predictiors using NNs by AMD
       see https://www.amd.com/en/partner/amd-ryzen-7-changes-cpu-market
       search for "neural net"
     - Kraska's learned index paper (2018)
     - NNs in OS? not really


3. Mechanics and admin
   ---how are we going to run CS7670?

   Two classes a week
   Each class is one of {"lecture", "paper", "guest"}

   Goal 3: finish a collaborative project & submit a paper

     The project will be a system that uses machine learning (e.g., neural
     networks) to improve its performance.

     Our plan is to submit a systems paper together.

   Group students into two groups.
     Group A: Daniel and Matthew, work on Lab2 (learned index)
     Group B: Brent and Will, work on Lab1 (file system)

   Three stages (14 weeks)
     Basics: NN basics, FS, PMem, Sequential Consistency (concurrency)
     State-of-the-art: Learned index, PMem KV, new FS
     final project: ???

   Labs:
     Lab1: FS
     Lab2: NN basics & learned index
     Lab3--X: TBD

  Revisit three goals:
    1. learn how to read papers
    2. study NN4Sys
    3. finish a collaborative project & submit a paper

  TODOs for you:
     - read our homepage: https://naizhengtan.github.io/22fall/
     - email me your github id.
       I will add you to our github repo:
        https://github.com/Khoury-srg/cs7670-22fall