OPTIMISATION IN FACTORY
GAMES WITH MATHS
BY
GYULA RÁBAI
FLOW MANAGEMENT
DISTRIBUTING TASKS
DISTRIBUTING TASKS - BOTTLENECK
14 / 1.5 ~ 10
DISTRIBUTING TASKS - SPLITTING
Each path has a probability of 0.5.
DISTRIBUTING TASKS - INEFFICIENT SPLITTING
WORKING
DISTRIBUTING TASKS - INEFFICIENT SPLITTING NOT
WORKING
Parallel Machines 10 →
20
New Bottleneck 1.5 → 0.7
DISTRIBUTING TASKS - INEFFICIENT SPLITTING NOT
WORKING
14-13.7 = 0.3 LOSS = 2.1%
INEFFICIENCY
DISTRIBUTING TASKS - OUTPUT PROBABILITY
DIST
Exponential
Distribution
(This is balanced by the earlier machines
blocking but the conveyor belts cannot go
fast enough for this effect to persist over a
large number of splitters.)
DISTRIBUTING TASKS - DIFFERENT OUTPUT PROBABILITY
DISTRIBUTIONS
Exponentia
lBinomial
DISTRIBUTING TASKS - DIFFERENT OUTPUT PROBABILITY
DISTRIBUTIONS
Exponentia
lBinomial
DISTRIBUTING TASKS - OPTIMAL OUTPUT PROBABILITY
DISTRIBUTION
Only works for
powers of 2
FORMULA FOR APPROX 3
Let a, b, c be your channels:
a’ = (a + b)/2
b’ = (a’+ c)/2
c’ = (a’+ c)/2
APPROX FOR 3
One iteration of splitting:
a1 = x/2
b1 = x/4
c1 = x/4
APPROX FOR 3
Second iteration of splitting:
a2 = (x/2 + x/4) / 2 = x/4 + x/8
b2 = (x/4 + x/8 + x/4)/2 = (x/2 +x/8)/2 = x/4 + x/16
c2 = (x/4 + x/8 + x/4)/2 = (x/2 +x/8)/2 = x/4 + x/16
APPROX FOR 3
Third iteration of splitting:
a2 = (x/4 +x/8 + x/4+ x/16) / 2 = x/4 + x/16 + x/32
b2 = (x/4 + x/16 + x/32 + x/4+ x/16)/2 = (x/2 +x/8 +x/32)/2 = x/4 +
x/16 + x/64
c2 = (x/4 + x/16 + x/32 + x/4+ x/16)/2 = (x/2 +x/8 +x/32)/2 = x/4 +
x/16 + x/64
APPROX FOR 3
Consider b and c:
b = c
n = 1: x/4
n = 2: x/4 + x/16
n = 3: x/4 + x/16 + x/32
APPROX FOR 3
x(1/4)
x(1/4 + 1/16)
x(1/4 + 1/16 + 1/32)
APPROX FOR 3
x(2-2)
x(2-2 + 2-4)
x(2-2 + 2-4 + 2-6)
APPROX FOR 3
Why?
Consider a:
a = x(2-2 + 2-4 + 2-6+ ... +2-2n+2-2n+1)
Consider b:
b = x(2-2 + 2-4 + 2-6+ ... +2-2n+2-2(n+1))
APPROX FOR 3
a = x(2-2 + 2-4 + 2-6 + ... + 2-2n + 2-2n-1)
b = x(2-2 + 2-4 + 2-6 + ... + 2-2n + 2-2(n+1))
a’ = (a+b)/2 = x(2-2 + 2-2 + 2-4 + 2-4 + 2-6 + 2-6 + ... + 2-2n +2-2n + 2-2n-
1 + 2-2(n+1)) / 2
a’ = (a+b)/2 = x(2-1 + 2-3 + 2-5 + ... + 2-2n+1 + 2-2n-1
+ 2-2(n+1)) / 2
a’ = (a+b)/2 = x(2-1 + 2-3 + 2-5 + ... + 2-2n+1 + 2-2n-1 + 2-2(n+1)) / 2
a’ = (a+b)/2 = x(2-2 + 2-4 + 2-6 + ... + 2-2n + 2-2(n+1) + 2-2(n+1) - 1)
This is again in the form (n + 1 → n):
a = x(2-2 + 2-4 + 2-6 + ... + 2-2n + 2-2n-1)
APPROX FOR 3
Consider c and b:
c = b
c’ = b’ = (a’+ c)/2 = (a’+ b)/2
a’ = x(2-2 + 2-4 + 2-6 + ... + 2-2n + 2-2(n+1) + 2-2(n+1) - 1)
b = x(2-2 + 2-4 + 2-6 + ... + 2-2n + 2-2(n+1))
b’ = (a’+ b)/2 = x(2-2 + 2-2 + 2-4 + 2-4 + 2-6 + 2-6 + ... + 2-2n + 2-2n + 2-2(n+1) + 2-2(n+1) + 2-2(n+1) - 1)/2
b’ = (a’+ b)/2 = x(2-1 + 2-3 + 2-5 + ... + 2-2n+1 + 2-2(n+1) + 1 + 2-2(n+1) - 1)/2
b’ = (a’+ b)/2 = x(2-2 + 2-4 + 2-6 + ... + 2-2n + 2-2(n+1) + 2-2(n+2)) Which is again in the same form
(n + 2 → n + 1)
b = x(2-2 + 2-4 + 2-6+ ... +2-2n+2-2(n+1))
APPROX 3
Therefore, b and c will always be in the form
b = x(2-2 + 2-4 + 2-6+ ... +2-2n)
This is a geometric series series where
a
= ¼ and r = ¼
As n → ∞: b → xa/(1-r) = x(¼ /(1-¼)) = x(¼/(¾)) = x⅓
APPROX 3
Alternatively if we write the expansion in terms of binary
b = x(2-2 + 2-4 + 2-6+ ... +2-2n)
b = x(0.010101 …)
0.010101… = ⅓(the same way 0.3333… = ⅓)
QED
APPROX N
-(I won’t prove this but) One can construct any 2^n to 2^m mapping
where the output has a uniform distribution. By adding powers of two,
one can create any integer. By shuffling the power of 2 mappings
according to the binary expansion of the fraction we want and
stacking it infinitely one can create a mapping between n-inputs and
n-outputs where the distribution of the outputs is always uniform.
-We can create an exponential dist mapping from one to any integer.
We can then map this to a uniform dist using our n-to-n uniform dist
mapping.
-Therefore, by representing a fraction in binary you can approximate
any (discrete) uniform distribution.
APPROX 20 FOR MAX EFFICIENCY
20 = 4*5 Therefore we need to approx 5.
5 = 0.00110011…
n-to-uniform-n for n=4 looks like this:
4+1 = 5.
By alternating the extra output to an input of the 4-4 mapping every
iteration we can approximate 5 (you can get here from 0.0011 also):
APPROX 20 FOR MAX EFFICIENCY
14/14 = 100%
Efficiency
SAME SET OF SKILLS AS FOR SOFTWARE
ENGINEER:
E.g. how to multiply 1073741824 numbers with 1024 numbers (token
unembedding for llama 1B parameter model) using 124 (not a power of 2)
cores on the GPU?
E.g. where is the bottleneck in the code?
Etc.
ALSO CHIP DESIGN
