Automatic Schedulers through Projective Reparameterization

Learning Automatic Schedulers through
Projective Reparameterization
Ajay Jain
Saman Amarasinghe
Challenges in ML for Systems
 
Challenges in ML for Systems
1.
Discrete search spaces
Challenges in ML for Systems
1.
Discrete search spaces
2.
Large, combinatorial search spaces
Challenges in ML for Systems
1.
Discrete search spaces
2.
Large, combinatorial search spaces
3.
Highly constrained feasible sets
Challenging for supervised learning!
Motivating application: Instruction Scheduling
N! POSSIBLE
SCHEDULES
FEASIBLE
SCHEDULES
EFFICIENT
SCHEDULES
Motivating application: Instruction Scheduling
List scheduling with heuristics
Stochastic search & superoptimization
Integer linear programming
Reinforcement learning
Challenging for supervised learning!
 Baseline: Sinkhorn iteration from ranking literature
  
 
 
16
% of schedules are invalid
This work
Introduce EPOCS operator
General approach for learning under dynamic constraints
Formulate instruction scheduling as relaxed integer program
Imitate GCC compiler instruction schedules
Permutation matrix representation
0  1  2  3  4
1  0  2  3  4
ranking, scheduling, packet
switching, matching…
 
Learning automatic schedulers through projective reparameterization
Ajay Jain
Learning automatic schedulers through projective reparameterization
Ajay Jain
Evaluation
Train POCSNet to imitate GCC 4.9.4 schedules
       77,202 basic blocks from SPEC2006, SPEC2017 
[Mendis et al 2019]
Evaluate data dependency violations, accuracy
Baseline: Sinkhorn iteration
Imposing dynamic constraints reduces data dependency violations
Imposing constraints improves accuracy (+4%)
POCSNet schedule latencies are on par with GCC latencies
 mov    rdi, rbp
 
mov    
rsi, rbx
 add    rsp, 0x18
 pop    
rbx
 
pop    
rbp
Shuffled input block
Takeaways
EPOCS: General purpose op for dynamic constraints on NNs
One application: Job scheduling problems
A step toward correct-by-construction ML for Systems:
 
Enforce known constraints end-to-end for accuracy boost + guarantees
Contact: ajayj@berkeley.edu
 movsd   xmm5, qword ptr [rsp+0x20]
 
movsd   xmm3, qword ptr [r13+0xa0]
 
subsd
   xmm3, xmm5
 
divsd
   xmm3, xmm8
 
ucomisd
 xmm2, xmm3
 
movsd   xmm3, qword ptr [r13+0xa0]
 movsd   xmm5, qword ptr [rsp+0x20]
 subsd
   xmm3, xmm5
 
divsd
   xmm3, xmm8
 
ucomisd
 xmm2, xmm3
Shuffled input block
POCSNet scheduled block
 
movsxd  
rdx, dword ptr [rsp+0x0c]
 
mov
     rax, 0xffffffff
 
test
    edx, edx
 
cmovnz
  rax, rdx
 
mov
     r15, rax
 
movsxd  
rdx, dword ptr [rsp+0x0c]
 cmovnz
  rax, rdx
 
mov
     rax, 0xffffffff
 
test
    edx, edx
 mov
     r15, rax
Shuffled input block
POCSNet scheduled block
Enforcing constraints improves accuracy
POCSNet schedule latencies are on par with GCC latencies
Slide Note
Embed
Share

Explore the challenges in machine learning for systems and learn about automatic schedulers through projective reparameterization. Discover motivating applications like instruction scheduling and efficient schedules. Introduce the EPOCS operator for learning under dynamic constraints and imitate GCC compiler instruction schedules.

  • Machine Learning
  • Automatic Schedulers
  • Projective Reparameterization
  • Instruction Scheduling
  • Dynamic Constraints

Uploaded on Sep 25, 2024 | 0 Views


Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

E N D

Presentation Transcript


  1. Learning Automatic Schedulers through Projective Reparameterization Ajay Jain SamanAmarasinghe

  2. Challenges in ML for Systems Ajay Jain Learning automatic schedulers through projective reparameterization

  3. Challenges in ML for Systems 1. Discrete search spaces Ajay Jain Learning automatic schedulers through projective reparameterization

  4. Challenges in ML for Systems 1. Discrete search spaces 2. Large, combinatorial search spaces Ajay Jain Learning automatic schedulers through projective reparameterization

  5. Challenges in ML for Systems 1. Discrete search spaces 2. Large, combinatorial search spaces 3. Highly constrained feasible sets Challenging for supervised learning! Ajay Jain Learning automatic schedulers through projective reparameterization

  6. Motivating application: Instruction Scheduling EFFICIENT SCHEDULES FEASIBLE SCHEDULES N! POSSIBLE SCHEDULES Ajay Jain Learning automatic schedulers through projective reparameterization

  7. Motivating application: Instruction Scheduling List scheduling with heuristics Stochastic search & superoptimization Integer linear programming Reinforcement learning Challenging for supervised learning! Baseline: Sinkhorn iteration from ranking literature 16% of schedules are invalid Ajay Jain Learning automatic schedulers through projective reparameterization

  8. This work Introduce EPOCS operator General approach for learning under dynamic constraints Formulate instruction scheduling as relaxed integer program Imitate GCC compiler instruction schedules Ajay Jain Learning automatic schedulers through projective reparameterization

  9. Permutation matrix representation 0 1 2 3 4 1 0 2 3 4 Fixed constraints Input dependent partial order constraints ranking, scheduling, packet switching, matching Ajay Jain Learning automatic schedulers through projective reparameterization

  10. Ajay Jain Learning automatic schedulers through projective reparameterization

  11. Fixed constraints Dynamic constraints EPOCS operator Sinkhorn iteration Fixed constraints Dynamic constraints Ajay Jain Learning automatic schedulers through projective reparameterization

  12. One iteration of EPOCS for scheduling 1) Normalize* 2) Normalize* 3) ReLU 4) Project Ajay Jain Learning automatic schedulers through projective reparameterization

  13. Correct the relaxation with matching (Hungarian algorithm) Ajay Jain Learning automatic schedulers through projective reparameterization

  14. Evaluation Train POCSNet to imitate GCC 4.9.4 schedules 77,202 basic blocks from SPEC2006, SPEC2017 [Mendis et al 2019] Evaluate data dependency violations, accuracy Baseline: Sinkhorn iteration Ajay Jain Learning automatic schedulers through projective reparameterization

  15. + Dynamic constraints with EPOCS/POPOCS Fixed constraints only 16% of predicted schedules are infeasible Imposing dynamic constraints reduces data dependency violations Ajay Jain Learning automatic schedulers through projective reparameterization

  16. Accuracy of schedules 45% 0.397 40% 0.356 35% Fixed constraints Sinkhorn iteration Dynamic constraints EPOCS/POPOCS 30% 25% 35.6% 39.7% Accuracy 20% 15% Kendall tau distance 0.238 0.222 10% 5% 0% Fixed constraints Sinkhorn iteration Dynamic constraints EPOCS/POPOCS Imposing constraints improves accuracy (+4%) POCSNet schedule latencies are on par with GCC latencies Ajay Jain Learning automatic schedulers through projective reparameterization

  17. mov rdi, rbp mov rsi, rbx add rsp, 0x18 pop rbx pop rbp Shuffled input block add rsp, 0x18 mov rsi, rbx mov rdi, rbp pop rbx pop rbp POCSNet scheduled block Ajay Jain Learning automatic schedulers through projective reparameterization

  18. Takeaways EPOCS: General purpose op for dynamic constraints on NNs One application: Job scheduling problems A step toward correct-by-construction ML for Systems: Enforce known constraints end-to-end for accuracy boost + guarantees Contact: ajayj@berkeley.edu Ajay Jain Learning automatic schedulers through projective reparameterization

  19. movsd xmm3, qword ptr [r13+0xa0] movsd xmm5, qword ptr [rsp+0x20] subsd xmm3, xmm5 divsd xmm3, xmm8 ucomisd xmm2, xmm3 Shuffled input block movsd xmm5, qword ptr [rsp+0x20] movsd xmm3, qword ptr [r13+0xa0] subsd xmm3, xmm5 divsd xmm3, xmm8 ucomisd xmm2, xmm3 POCSNet scheduled block Ajay Jain Learning automatic schedulers through projective reparameterization

Related


More Related Content

giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#