Largest number moved to the end of the list by a series of compares and exchanges, strting at the opposite end
Actions repeated with subsequent numbers, stopping just before that previously positioned number
In this way, lage numbers move ("bubble") towrard one end
In [3]:
%%writefile codes/mpi4py/transposition.py
#!/usr/bin/env python
# transposition.py
import numpy as np
from mpi4py import MPI
comm = MPI.COMM_WORLD
rank = comm.Get_rank(); size = comm.Get_size(); status = MPI.Status();
N = 16
unsorted = np.zeros(N, dtype="int")
final_sorted = np.zeros(N, dtype="int")
local_array = np.zeros(int(N / size), dtype="int")
local_tmp = np.zeros(int(N / size), dtype="int")
local_remain = np.zeros(2 * int(N / size), dtype="int")
if rank == 0:
unsorted = np.random.randint(low=0,high=N,size=N)
print (unsorted)
comm.Scatter(unsorted, local_array, root = 0)
local_array.sort()
for step in range(0, size):
print ("Step: ", step)
if (step % 2 == 0):
if (rank % 2 == 0):
des = rank + 1
else:
des = rank - 1
else:
if (rank % 2 == 0):
des = rank - 1
else:
des = rank + 1
if (des >= 0 and des < size):
print ("My rank is ", rank, " and my des is ", des)
comm.Send(local_array, dest = des, tag = 0)
comm.Recv(local_tmp, source = des)
print ("Rank ", rank, " ", step, ": Initial local_array: ", local_array)
print ("Rank ", rank, " ", step, ": Received local_tmp:", local_tmp)
local_remain = np.concatenate((local_array, local_tmp), axis=0)
local_remain.sort()
if (rank < des):
local_array = local_remain[0:int(N/size)]
else:
local_array = local_remain[int(N/size):2 * int(N/size)]
print ("Rank ", rank, " ", step, ": Retained portions: ", local_array)
comm.Gather(local_array, final_sorted)
if (rank == 0):
print (final_sorted)
In [1]:
!chmod 755 codes/mpi4py/transposition.py
!module load gcc/5.3.0 openmpi/1.10.3; mpirun -np 4 codes/mpi4py/transposition.py
A classical sequential sorting algorithm using divide-and-conquer approach
Unsorted list first divided into half. Each half is again divided into two. Continued until individual numbers obtained.
Then pairs of numbers combined (merged) into sorted list of two numbers.
Pairs of these lists of four numbers are merged into sorted lists of eight numbers.
This is continued until the one fully sorted list is obtained.
In [5]:
%%writefile codes/mpi4py/merge.py
#!/usr/bin/env python
# merge.py
import numpy as np
from mpi4py import MPI
comm = MPI.COMM_WORLD
rank = comm.Get_rank(); size = comm.Get_size(); status = MPI.Status();
N = 16
unsorted = np.zeros(N, dtype="int")
final_sorted = np.zeros(N, dtype="int")
local_array = np.zeros(int(N / size), dtype="int")
local_tmp = np.zeros(int(N / size), dtype="int")
local_remain = np.zeros(2 * int(N / size), dtype="int")
if rank == 0:
unsorted = np.random.randint(low=0,high=N,size=N)
print (unsorted)
comm.Scatter(unsorted, local_array, root = 0)
local_array.sort()
step = size / 2
print ("Rank: ", rank)
while (step >= 1):
if (rank >= step and rank < step * 2):
comm.Send(local_array, rank - step, tag = 0)
elif (rank < step):
local_tmp = np.zeros(local_array.size, dtype="int")
local_remain = np.zeros(2 * local_array.size, dtype="int")
comm.Recv(local_tmp, rank + step, tag = 0)
i = 0 #local_array counter
j = 0 # local_tmp counter
for k in range (0, 2 * local_array.size):
if (i >= local_array.size):
local_remain[k] = local_tmp[j]
j += 1
elif (j >= local_array.size):
local_remain[k] = local_array[i]
i += 1
elif (local_array[i] > local_tmp[j]):
local_remain[k] = local_tmp[j]
j += 1
else:
local_remain[k] = local_array[i]
i += 1
print ("Step: ", step)
print ("local array: ", local_array)
print ("local tmp: ", local_tmp)
print ("local remain: ", local_remain)
local_array = local_remain
step = step / 2
if (rank == 0):
print (local_array)
In [5]:
!chmod 755 codes/mpi4py/merge.py
!module load gcc/5.3.0 openmpi/1.10.3; mpirun -np 4 codes/mpi4py/merge.py
In [ ]: