-
Notifications
You must be signed in to change notification settings - Fork 7
/
alloc.txt
136 lines (105 loc) · 3.59 KB
/
alloc.txt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
goals
- be able to guarantee a project (with given keywords and GPU usage)
an average throughput
- be able to give projects a "share" that determines what they get
beyond their guarantee
- give priority to bursty projects to minimize batch turnaround
---------------
The current allocation mechanism (based on linear bounded model)
doesn't work at all.
Hard to keep balances from pegging at 0 or 1.
---------------
Problems
Is a set of guarantees supportable?
This could be NP-hard
heuristic:
order projects by
given a set of guarantees, and a project P,
what's the largest guarantee we can make for P?
============================
New algorithm
AC(P) = avg EC/sec over last week
"share" S(P) (arbitrary scale; bigger means get more computing)
Compute once per day (allocate.php)
AC(P) (su_project.ec_per_sec)
#projects (su_allocate.nprojects)
sum of AC(P)(su_allocate.ec_per_sec_total)
sum of S(P)(su_allocate.share_total)
RPC:
AC1(P) = AC(P) / sum of AC(P)
in 0..1
AC2(P) = AC1(P) * #projects
average is 1
SN(P) = S(P) / average S(P)
average is 1.
project score in project selection: subtract AC2(P)/SN(P)
average is 1 (more or less)
---
EC adjustment:
Other things being equal, the project with best score will
be assigned to all hosts for 24 hours.
This will cancel out over the long term,
but it would be good to smooth things out.
So when we assign a project P to a host H,
we'd like to add to AC(P) an estimate of the
EC per second that H will provide.
Similarly, if removing a previously attached project, subtract the estimate
Currently we have no record of recent EC at the (host, project) level.
Options:
1) use an estimate based on
- peak FLOPS for devices to be used,
divided by # of assigned projects using that device
- scaling factor (.2?) for GPUs
- avg host availability
I don't like this; too many other factors e.g. throttling prefs
2) maintain exp avg EC per (host, project).
but it may not have been attached continuously.
3) AC(P)/NH(P), where NH(P) is the number of hosts attached to P
during previous accounting period.
For each project, maintain
su_project.nhosts_today: increment in RPC
su_project.nhosts_yesterday: copy from today
Let's use 3). Note: what matters is average per-host contribution,
not this particular host.
To maintain NH(P):
add su_accounting_project.nhosts
On each RPC, for each project P
get su_accounting_project SAP
if previous RPC time is < SAP.create_time
increment SAP.nhosts, update
---
Implementation
su_allocate
nprojects: # active projects
avg_ec_total: sum of AC(P)
share_total: sum of S(P)
su_project
share
avg_ec (AC)
avg_ec_adjusted
Remaining problems:
- estimate the throughput a given project will get
- estimate the turnaround time of a batch
- how to assign S(P) so that certain projects get certain throughputs
- given a set of guarantees, what's the largest new guarantee we can make?
Do these by simulation?
========================
paper terminology
share/keyword scheduling
assignment algorithm that takes into account
shares
keywords
platforms/GPUs
throughput allocation
setting shares so that projects get a particular throughput
for some period
how to estimate what projects will get, given shares?
Easy to compute the max they can get if no other projects;
hard to compute actual w/ other projects
simulator: how would it work?
trace-driven
implement w/o DB access
each host does one RPC/day
Also could say: how much throughput would you get if
you could use GPU X;
how much if you didn't require VBox