DAG Queueing

Brendan Smithyman | January 2015


In [1]:
import numpy as np
import networkx

Plotting configuration


In [2]:
import matplotlib.pyplot as plt
import matplotlib.cm as cm
%matplotlib inline

import matplotlib
from IPython.display import set_matplotlib_formats
set_matplotlib_formats('png')
matplotlib.rcParams['savefig.dpi'] = 150 # Change this to adjust figure size

# Plotting options
font = {
    'family': 'Bitstream Vera Sans',
    'weight': 'normal',
    'size': 8,
}

matplotlib.rc('font', **font)

System / modelling configuration


In [3]:
cellSize    = 1             # m
freqs       = [1e2, 2e2, 3e2, 4e2]         # Hz
density     = 2700          # units of density
Q           = np.inf        # can be inf
nx          = 164           # count
nz          = 264           # count
freeSurf    = [False, False, False, False] # t r b l
dims        = (nx,nz)       # tuple
nPML        = 32
rho         = np.fliplr(np.ones(dims) * density)
nfreq       = len(freqs)    # number of frequencies
nky         = 48            # number of y-directional plane-wave components
nsp         = nfreq * nky   # total number of 2D subproblems

velocity    = 2500          # m/s
vanom       = 500           # m/s
cPert       = np.zeros(dims)
cPert[(nx/2)-20:(nx/2)+20,(nz/2)-20:(nz/2)+20] = vanom
c           = np.fliplr(np.ones(dims) * velocity)
cFlat       = c
c          += np.fliplr(cPert)
cTrue       = c

srcs        = np.array([np.ones(101)*32, np.zeros(101), np.linspace(32, 232, 101)]).T
recs        = np.array([np.ones(101)*132, np.zeros(101), np.linspace(32, 232, 101)]).T
nsrc        = len(srcs)
nrec        = len(recs)
recmode     = 'fixed'

geom        = {
    'src':  srcs,
    'rec':  recs,
    'mode': 'fixed',
}

cache       = False
cacheDir    = '.'

# Base configuration for all subproblems
systemConfig = {
    'dx':   cellSize,       # m
    'dz':   cellSize,       # m
    'c':        c.T,        # m/s
    'rho':      rho.T,      # density
    'Q':        Q,          # can be inf
    'nx':       nx,         # count
    'nz':       nz,         # count
    'freeSurf': freeSurf,   # t r b l
    'nPML':     nPML,
    'geom':     geom,
    'cache':    cache,
    'cacheDir': cacheDir,
    'freqs':    freqs,
    'nky':      nky,
}

In [4]:
class entryTracker(object):
    
    def __init__(self):
        self.entries = []
    
    def __call__(self, entry):
        self.entries.append(entry)
        return len(self.entries) - 1
    
    def __getitem__(self, slice):
        return self.entries[slice]

In [6]:
def systemGraph(systemConfig):

    G = networkx.DiGraph()
    et = entryTracker()

    basekey = et(systemConfig)
    G.add_node(basekey)
    for freq in systemConfig['freqs']:
        freqkey = et({'freq': freq})
        G.add_node(freqkey)
        G.add_edge(freqkey, basekey)
        for iky in xrange(systemConfig['nky']):
            ikykey = et({'freq': freq, 'iky': iky})
            G.add_node(ikykey)
            G.add_edge(ikykey, freqkey)

    return G, et

In [9]:
G, et = systemGraph(systemConfig)
networkx.draw_graphviz(G)



In [10]:
for item in networkx.topological_sort(G):
    if 'freq' in et[item]:
        if 'iky' in et[item]:
            print('Freq: %(freq)f\t iky: %(iky)d'%et[item])
        else:
            print('Freq: %(freq)f'%et[item])            
    else:
        print('Base')


Freq: 400.000000	 iky: 47
Freq: 400.000000	 iky: 46
Freq: 400.000000	 iky: 45
Freq: 400.000000	 iky: 44
Freq: 400.000000	 iky: 43
Freq: 400.000000	 iky: 42
Freq: 400.000000	 iky: 41
Freq: 400.000000	 iky: 40
Freq: 400.000000	 iky: 39
Freq: 400.000000	 iky: 38
Freq: 400.000000	 iky: 37
Freq: 400.000000	 iky: 36
Freq: 400.000000	 iky: 35
Freq: 400.000000	 iky: 34
Freq: 400.000000	 iky: 33
Freq: 400.000000	 iky: 32
Freq: 400.000000	 iky: 31
Freq: 400.000000	 iky: 30
Freq: 400.000000	 iky: 29
Freq: 400.000000	 iky: 28
Freq: 400.000000	 iky: 27
Freq: 400.000000	 iky: 26
Freq: 400.000000	 iky: 25
Freq: 400.000000	 iky: 24
Freq: 400.000000	 iky: 23
Freq: 400.000000	 iky: 22
Freq: 400.000000	 iky: 21
Freq: 400.000000	 iky: 20
Freq: 400.000000	 iky: 19
Freq: 400.000000	 iky: 18
Freq: 400.000000	 iky: 17
Freq: 400.000000	 iky: 16
Freq: 400.000000	 iky: 15
Freq: 400.000000	 iky: 14
Freq: 400.000000	 iky: 13
Freq: 400.000000	 iky: 12
Freq: 400.000000	 iky: 11
Freq: 400.000000	 iky: 10
Freq: 400.000000	 iky: 9
Freq: 400.000000	 iky: 8
Freq: 400.000000	 iky: 7
Freq: 400.000000	 iky: 6
Freq: 400.000000	 iky: 5
Freq: 400.000000	 iky: 4
Freq: 400.000000	 iky: 3
Freq: 400.000000	 iky: 2
Freq: 400.000000	 iky: 1
Freq: 400.000000	 iky: 0
Freq: 400.000000
Freq: 300.000000	 iky: 47
Freq: 300.000000	 iky: 46
Freq: 300.000000	 iky: 45
Freq: 300.000000	 iky: 44
Freq: 300.000000	 iky: 43
Freq: 300.000000	 iky: 42
Freq: 300.000000	 iky: 41
Freq: 300.000000	 iky: 40
Freq: 300.000000	 iky: 39
Freq: 300.000000	 iky: 38
Freq: 300.000000	 iky: 37
Freq: 300.000000	 iky: 36
Freq: 300.000000	 iky: 35
Freq: 300.000000	 iky: 34
Freq: 300.000000	 iky: 33
Freq: 300.000000	 iky: 32
Freq: 300.000000	 iky: 31
Freq: 300.000000	 iky: 30
Freq: 300.000000	 iky: 29
Freq: 300.000000	 iky: 28
Freq: 300.000000	 iky: 27
Freq: 300.000000	 iky: 26
Freq: 300.000000	 iky: 25
Freq: 300.000000	 iky: 24
Freq: 300.000000	 iky: 23
Freq: 300.000000	 iky: 22
Freq: 300.000000	 iky: 21
Freq: 300.000000	 iky: 20
Freq: 300.000000	 iky: 19
Freq: 300.000000	 iky: 18
Freq: 300.000000	 iky: 17
Freq: 300.000000	 iky: 16
Freq: 300.000000	 iky: 15
Freq: 300.000000	 iky: 14
Freq: 300.000000	 iky: 13
Freq: 300.000000	 iky: 12
Freq: 300.000000	 iky: 11
Freq: 300.000000	 iky: 10
Freq: 300.000000	 iky: 9
Freq: 300.000000	 iky: 8
Freq: 300.000000	 iky: 7
Freq: 300.000000	 iky: 6
Freq: 300.000000	 iky: 5
Freq: 300.000000	 iky: 4
Freq: 300.000000	 iky: 3
Freq: 300.000000	 iky: 2
Freq: 300.000000	 iky: 1
Freq: 300.000000	 iky: 0
Freq: 300.000000
Freq: 200.000000	 iky: 47
Freq: 200.000000	 iky: 46
Freq: 200.000000	 iky: 45
Freq: 200.000000	 iky: 44
Freq: 200.000000	 iky: 43
Freq: 200.000000	 iky: 42
Freq: 200.000000	 iky: 41
Freq: 200.000000	 iky: 40
Freq: 200.000000	 iky: 39
Freq: 200.000000	 iky: 38
Freq: 200.000000	 iky: 37
Freq: 200.000000	 iky: 36
Freq: 200.000000	 iky: 35
Freq: 200.000000	 iky: 34
Freq: 200.000000	 iky: 33
Freq: 200.000000	 iky: 32
Freq: 200.000000	 iky: 31
Freq: 200.000000	 iky: 30
Freq: 200.000000	 iky: 29
Freq: 200.000000	 iky: 28
Freq: 200.000000	 iky: 27
Freq: 200.000000	 iky: 26
Freq: 200.000000	 iky: 25
Freq: 200.000000	 iky: 24
Freq: 200.000000	 iky: 23
Freq: 200.000000	 iky: 22
Freq: 200.000000	 iky: 21
Freq: 200.000000	 iky: 20
Freq: 200.000000	 iky: 19
Freq: 200.000000	 iky: 18
Freq: 200.000000	 iky: 17
Freq: 200.000000	 iky: 16
Freq: 200.000000	 iky: 15
Freq: 200.000000	 iky: 14
Freq: 200.000000	 iky: 13
Freq: 200.000000	 iky: 12
Freq: 200.000000	 iky: 11
Freq: 200.000000	 iky: 10
Freq: 200.000000	 iky: 9
Freq: 200.000000	 iky: 8
Freq: 200.000000	 iky: 7
Freq: 200.000000	 iky: 6
Freq: 200.000000	 iky: 5
Freq: 200.000000	 iky: 4
Freq: 200.000000	 iky: 3
Freq: 200.000000	 iky: 2
Freq: 200.000000	 iky: 1
Freq: 200.000000	 iky: 0
Freq: 200.000000
Freq: 100.000000	 iky: 47
Freq: 100.000000	 iky: 46
Freq: 100.000000	 iky: 45
Freq: 100.000000	 iky: 44
Freq: 100.000000	 iky: 43
Freq: 100.000000	 iky: 42
Freq: 100.000000	 iky: 41
Freq: 100.000000	 iky: 40
Freq: 100.000000	 iky: 39
Freq: 100.000000	 iky: 38
Freq: 100.000000	 iky: 37
Freq: 100.000000	 iky: 36
Freq: 100.000000	 iky: 35
Freq: 100.000000	 iky: 34
Freq: 100.000000	 iky: 33
Freq: 100.000000	 iky: 32
Freq: 100.000000	 iky: 31
Freq: 100.000000	 iky: 30
Freq: 100.000000	 iky: 29
Freq: 100.000000	 iky: 28
Freq: 100.000000	 iky: 27
Freq: 100.000000	 iky: 26
Freq: 100.000000	 iky: 25
Freq: 100.000000	 iky: 24
Freq: 100.000000	 iky: 23
Freq: 100.000000	 iky: 22
Freq: 100.000000	 iky: 21
Freq: 100.000000	 iky: 20
Freq: 100.000000	 iky: 19
Freq: 100.000000	 iky: 18
Freq: 100.000000	 iky: 17
Freq: 100.000000	 iky: 16
Freq: 100.000000	 iky: 15
Freq: 100.000000	 iky: 14
Freq: 100.000000	 iky: 13
Freq: 100.000000	 iky: 12
Freq: 100.000000	 iky: 11
Freq: 100.000000	 iky: 10
Freq: 100.000000	 iky: 9
Freq: 100.000000	 iky: 8
Freq: 100.000000	 iky: 7
Freq: 100.000000	 iky: 6
Freq: 100.000000	 iky: 5
Freq: 100.000000	 iky: 4
Freq: 100.000000	 iky: 3
Freq: 100.000000	 iky: 2
Freq: 100.000000	 iky: 1
Freq: 100.000000	 iky: 0
Freq: 100.000000
Base

In [11]:
node0 = G[0]

In [14]:
G.predecessors(0)


Out[14]:
[1, 50, 99, 148]

In [10]:
# freqheads = G.predecessors(0)
# jobs = []
# for freqhead in freqheads:
#     freq = et[freqhead]['freq']
#     subprobs = G.predecessors(freqhead)
#     nsp = len(subprobs)
#     for subprob in subprobs:
#         jobs[subprob] = lview.apply_async(dothingsfunction, et[0].copy().update(et[subprob]))