In [1]:
import numpy as np
import itertools
from test_life import hash_grid
from life import life_step
In [2]:
shape = (4,4)
In [3]:
A = np.random.randint(0,2,shape)
B = np.random.randint(0,2,shape)
print A
print B
Think of A and B as part of an overlapping horizontal decomposition of C, where the only "true" values are in the interior cells. The first thing we'll do is determine what the interior of C looks like
In [4]:
C = np.vstack((A[1:3,1:3],B[1:3,1:3]))
print C
Now let's communicate from A to B and B to A so that they have correct neighbor information
In [5]:
A[-1,1:-1] = B[1,1:-1]
B[0,1:-1] = A[2,1:-1]
print A
print B
Note that we only communicated an "interior" slice, as if we were using the diagonal trick. If we want to communicate an exterior slice, this is easy.
In [6]:
A[-1,:] = B[1,:]
B[0,:] = A[-2,:]
print A
print B
Okay, now we have the general idea, let's check it over the interior of a set of subgrids.
In [7]:
shape = (8,8)
A = np.random.randint(0,2,shape)
B = A.copy()
ng = (2, 2)
gridl = [s/n for s,n in zip(shape,ng)]
gs = [[l * i for i in range(ngi)] for ngi,l in zip(ng,gridl)]
gs = list(itertools.product(*gs))
slices = [[(slice(i,i+l)) for i, l in zip(gsi,gridl)] for gsi in gs]
sliceA = [slice(0,s) for s in shape]
grids = [A[i] for i in slices]
hashes = [hash_grid(g, s) for g, s in zip(grids, slices)]
print sum(hashes)
print hash_grid(A, sliceA)
Augment the four slices.
In [8]:
lgs = [[l*i-1 if i > 0 else 0 for i in range(ngi)] for ngi,l in zip(ng, gridl)]
lge = [[l*(i+1)+1 if i+1 < ngi else l*(i+1) for i in range(ngi)] for ngi,l in zip(ng, gridl)]
lgs = list(itertools.product(*lgs))
lge = list(itertools.product(*lge))
print lgs
print lge
#slices = [[slice(i,i+l) for i, l in zip(gsi, gridl)] for gsi in gs]
lslices = [[slice(i,j) for i, j in zip(gsi, gei)] for gsi, gei in zip(lgs, lge)]
lgrids = [A[i] for i in lslices]
For the next test, we'll perform ten time steps on an augmented set of grids, using communication, then compute the hash on the individual grids and the full grid.
In [9]:
for g in lgrids:
print g
In [10]:
def communicate(grid, left, right, up, down):
""" Communicates grid data.
Performs a simulated inner 'put' from grid into two left-right neighbors, then a full 'put' from grid into up-down neighbors"""
if left != None:
left[1:-1,-1] = grid[1:-1,1]
if right != None:
right[1:-1,0] = grid[1:-1,-2]
if up != None:
up[-1,:] = grid[1,:]
if down != None:
down[0,:] = grid[-2,:]
In [11]:
g00,g01,g10,g11 = [l.copy() for l in lgrids]
print A
In [12]:
print g00
In [13]:
print g01
In [14]:
print g10
In [15]:
print g11
In [16]:
n_00 = (None, g01, None, g10)
n_01 = (g00, None, None, g11)
n_10 = (None, g11, g00, None)
n_11 = (g10, None, g01, None)
In [17]:
g00[4,1:3] = 0
g00[1:3,4] = 0
In [18]:
communicate(g00, *n_00)
communicate(g01, *n_01)
communicate(g10, *n_10)
communicate(g11, *n_11)
In [19]:
print B
In [20]:
print g00
In [21]:
print g01
In [118]:
def build_grids(A, ng):
"""Create a decomposition of the grids on A"""
shape = A.shape
gridl = [s/n for s,n in zip(shape,ng)]
gs = [[l * i for i in range(ngi)] for ngi,l in zip(ng,gridl)]
gs = list(itertools.product(*gs))
slices = [[(slice(i,i+l)) for i, l in zip(gsi,gridl)] for gsi in gs]
sliceA = [slice(0,s) for s in shape]
return sliceA, slices, [A[i] for i in slices]
def build_local_grids(A, ng):
"""Create a copy of the local grids on A"""
shape = A.shape
gridl = [s/n for s,n in zip(shape,ng)]
lgs = [[l*i-1 if i > 0 else 0 for i in range(ngi)] for ngi,l in zip(ng, gridl)]
lge = [[l*(i+1)+1 if i+1 < ngi else l*(i+1) for i in range(ngi)] for ngi,l in zip(ng, gridl)]
lgs = list(itertools.product(*lgs))
lge = list(itertools.product(*lge))
lslices = [[slice(i,j) for i, j in zip(gsi, gei)] for gsi, gei in zip(lgs, lge)]
return [A[i].copy() for i in lslices]
def setup_4(A, local_grids, ng):
l_00, l_01, l_10, l_11 = [grid for grid in local_grids]
n_00 = (None, l_01, None, l_10)
n_01 = (l_00, None, None, l_11)
n_10 = (None, l_11, l_00, None)
n_11 = (l_10, None, l_01, None)
shape = A.shape
gridl = [s/n for s,n in zip(shape,ng)]
m0 = gridl[0]
m1 = gridl[1]
g_00 = l_00[:m0,:m1]
l_00[m0,:] = 0
l_00[1:m0-1,m1] = 0
g_01 = l_01[:m0,1:]
l_01[m0,:] = 0
l_01[1:m0-1,0] = 0
g_10 = l_10[1:,:m1]
l_10[0,:] = 0
l_10[1:m0-1,m1] = 0
g_11 = l_11[1:,1:]
l_11[0,:] = 0
l_11[1:m1-1,0] = 0
def comm_all():
communicate(l_00, *n_00[:2] + (None, None))
communicate(l_01, *n_01[:2] + (None, None))
communicate(l_10, *n_10[:2] + (None, None))
communicate(l_11, *n_11[:2] + (None, None))
communicate(l_00, *(None, None) + n_00[2:])
communicate(l_01, *(None, None) + n_01[2:])
communicate(l_10, *(None, None) + n_10[2:])
communicate(l_11, *(None, None) + n_11[2:])
grids = (g_00, g_01, g_10, g_11)
return grids, comm_all
In [119]:
def test_communicate():
"""Verify communications between processes"""
shape = (8,8)
A = np.random.randint(0,2,shape)
ng = (2, 2)
sliceA, slices, grids = build_grids(A, ng)
local_grids = build_local_grids(A, ng)
# check that subgrids match before we start
hashes = [hash_grid(g, s) for g, s in zip(grids, slices)]
assert(sum(hashes) == hash_grid(A, sliceA))
grids, comm_all = setup_4(A, local_grids, ng)
comm_all()
c_hashes = [hash_grid(g, s) for g, s in zip(grids, slices)]
assert(sum(hashes) == hash_grid(A, sliceA))
assert(sum(c_hashes) == hash_grid(A, sliceA))
In [120]:
test_communicate()
In [123]:
def test_communicating_steps():
"""Verify communications in running code between processes"""
shape = (4,4)
A = np.random.randint(0,2,shape)
sliceA = [slice(0,s) for s in shape]
slices = [[(slice(i,i+l)) for i, l in zip(gsi,gridl)] for gsi in gs]
B = A.copy()
B_swap = B.copy()
ng = (2, 2)
sliceA, slices, grids = build_grids(A, ng)
local_grids = build_local_grids(A, ng)
swap_local_grids = [local_grid.copy() for local_grid in local_grids]
# check that subgrids match before we start
hashes = [hash_grid(g, s) for g, s in zip(grids, slices)]
assert(sum(hashes) == hash_grid(A, sliceA))
grids, comm_all = setup_4(A, local_grids, ng)
swap_grids, swap_comm_all = setup_4(A, swap_local_grids, ng)
iters = 10
for i in range(iters):
comm_all()
for grid, swap_local_grid in zip(local_grids, swap_local_grids):
life_step(grid, swap_local_grid)
(local_grids, comm_all, grids, swap_local_grids, swap_comm_all, swap_grids) = \
swap_local_grids, swap_comm_all, swap_grids, local_grids, comm_all, grids
life_step(B, B_swap)
B_swap, B = B, B_swap
hashes = [hash_grid(g, s) for g, s in zip(grids, slices)]
if sum(hashes) != hash_grid(B, sliceA):
for grid in swap_local_grids:
print grid
print '-'*40
print B_swap
print '*'*40
for grid in local_grids:
print grid
print '-'
print B
hashes = [hash_grid(g, s) for g, s in zip(grids, slices)]
assert(sum(hashes) == hash_grid(B, sliceA))
In [124]:
test_communicating_steps()
In [105]:
In [ ]: